----- Original Message -----> From: "Tobias Edler von Koch" <tobias at codeaurora.org> > To: "Daniel Berlin" <dberlin at dberlin.org> > Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > Sent: Thursday, June 11, 2015 10:02:37 AM > Subject: Re: [LLVMdev] BasicAA unable to analyze recursive PHI nodes > > Hi Daniel, > > On Wed, 10 Jun 2015 17:11:02 -0700 Daniel Berlin > <dberlin at dberlin.org> > wrote: > > > > > I didn't see numbers one way or the other. It probably has some > > overhead, if it's the right solution, i'm sure it can be ade > > faster. > > As far as I remember, scev-aa is off because of limitations in the > current pass manager that would mean it would have to be recalculated > far too often.That's correct. It also may need some caching, or other performance-related work, to be sufficiently efficient to be on by default.> > > > > > I think this is a common enough case for it to be > > > handled by BasicAA. > > > > > > > Can you provide some evidence? > > > > IE hard numbers of how often it occurs on some set of benchmarks or > > something, and what the compile time cost is? > > > > It's really hard to say whether this is the right tradeoff without > > any data. > > I agree. We're seeing about 3% improvement on a number of internal > benchmarks, but I'll give this a try on SPEC etc. and share the > results > here (including compile time).Sounds good; please do. -Hal> > Thanks for your comments! > > Tobias > > -- > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a > Linux Foundation Collaborative Project. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Tobias Edler von Koch
2015-Jun-20 16:26 UTC
[LLVMdev] BasicAA unable to analyze recursive PHI nodes
Hi Daniel, Hal, I've evaluated the patch on the SPEC CPU2006 C/C++ benchmarks. Here are the results. 1. How many aliasPHI queries on recursive PHI nodes are there and what are their results? NoAlias 81317/10.6% (before) 118549/18.1% (after) MayAlias 685637/89.4% (before) 534856/81.4% (after) PartialAlias 0/ 0.0% (before) 3325/ 0.5% (after) Total 766954 (before) 656730 (after) As you can see, the share of NoAlias results for these queries goes up noticeably. What's also interesting is that there is a 14.4% reduction in total queries on recursive PHI nodes with the patch. 2. What is the average number of incoming values on recursive PHI nodes? There were 2 incoming values (one recursive, one 'real' value) in all but 102 (0.013%) of aliasPHI queries on recursive PHI nodes before the patch. With the patch, there were 103 queries with more than 2 incoming values. So two incoming values is indeed the common case. 3. What is the compile time impact of the change? I ran the SPEC2006 build 5 times, discarding the numbers for the first build to warm up the fs cache. Without the patch, the average build time over the remaining four builds is 5023.913s. With the patch, it is 5023.713s. Pretty much unchanged. 4. What is the impact of the change on the execution time of the benchmarks? This is with the ref data set, average of three runs. (Speedup, higher is better) 400.perlbench 0.991404586 401.bzip2 0.999081718 403.gcc 1.006213196 429.mcf 0.990988836 445.gobmk 0.994521527 456.hmmer 0.996110677 458.sjeng 0.993703064 462.libquantum 1.014540594 464.h264ref 0.996489267 471.omnetpp 0.986799815 473.astar 0.987321483 483.xalancbmk 0.985122405 433.milc 1.023695308 444.namd 0.998587195 447.dealII 0.999585507 450.soplex 1.001369759 453.povray 0.978606911 470.lbm 1.018186381 482.sphinx3 0.998224144 Average 0.997923809 Not a huge change here although the numbers tend to be more on the side of a slowdown. This is interesting - you'd think that better alias analysis shouldn't have that effect. Any idea what could be causing this? The numbers are from a real machine though so I'd expect something like 1-2% noise, so it could be just that. I hope this answers some of your questions! Tobias On Thu, 11 Jun 2015 10:20:02 -0500 Hal Finkel <hfinkel at anl.gov> wrote:> ----- Original Message ----- > > From: "Tobias Edler von Koch" <tobias at codeaurora.org> > > To: "Daniel Berlin" <dberlin at dberlin.org> > > Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> > > Sent: Thursday, June 11, 2015 10:02:37 AM > > Subject: Re: [LLVMdev] BasicAA unable to analyze recursive PHI nodes > > > > Hi Daniel, > > > > On Wed, 10 Jun 2015 17:11:02 -0700 Daniel Berlin > > <dberlin at dberlin.org> > > wrote: > > > > > > > > I didn't see numbers one way or the other. It probably has some > > > overhead, if it's the right solution, i'm sure it can be ade > > > faster. > > > > As far as I remember, scev-aa is off because of limitations in the > > current pass manager that would mean it would have to be recalculated > > far too often. > > That's correct. It also may need some caching, or other performance-related work, to be sufficiently efficient to be on by default. > > > > > > > > > > I think this is a common enough case for it to be > > > > handled by BasicAA. > > > > > > > > > > Can you provide some evidence? > > > > > > IE hard numbers of how often it occurs on some set of benchmarks or > > > something, and what the compile time cost is? > > > > > > It's really hard to say whether this is the right tradeoff without > > > any data. > > > > I agree. We're seeing about 3% improvement on a number of internal > > benchmarks, but I'll give this a try on SPEC etc. and share the > > results > > here (including compile time). > > Sounds good; please do. > > -Hal > > > > > Thanks for your comments! > > > > Tobias > > > > -- > > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a > > Linux Foundation Collaborative Project. > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Daniel Berlin
2015-Jun-20 16:55 UTC
[LLVMdev] BasicAA unable to analyze recursive PHI nodes
> Not a huge change here although the numbers tend to be more on the side > of a slowdown. This is interesting - you'd think that better alias > analysis shouldn't have that effect. Any idea what could be causing > this?LLVM's alias analysis is good but not amazing. If you improve it significantly (as you appear to have :P), you give the compiler more freedom to do things. What it chooses to do with that freedom may not always be good :) Basically, with any significant alias analysis change comes a lot of tuning of heuristics/etc, or looking through regressions, to determine what's going on now. *Usually* it's "something used to not be able to do a ton of <whatever>, and now it can. The cost model for <whatever> needs to be worked on so it doesn't go too crazy".
Maybe Matching Threads
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [LLVMdev] BasicAA unable to analyze recursive PHI nodes
- [RFC] BasicAA considers address spaces?