> What version of LLVM does your analysis use currently?We are working with LLVM 3.0 (stable release)> It sounds like your analysis is fast. Can you show results on how fast it > is on various programs? Do you have measurements on how much memory it > uses? How large is the largest program you've compiled with it?Yes, we have a very extensive report about it. Take a look into the pdf at http://code.google.com/p/range-analysis/source/browse/trunk/doc/Manuscript/paper.pdf In particular, take a look into fig.10, that shows program size vs runtime. We are truly linear on the program size. The largest program that we have compiled is SPEC CPU 2006 gcc. It takes less than 10 seconds to analyze it. This is the largest program that we had here. Its constraint graph has almost 1.5 million nodes.> We in the SAFECode project would be interested in trying your analysis out > for eliminating bounds checks. We just haven't had the time to do thatyet> (I'm assuming you're the same person that wanted to do Value Rangeanalysis> last year).No, that was Douglas, a friend of mine. He is in Texas nowadays. Now I am responsible for the range analysis project at UFMG. There are two other guys working with me on it too. And there are a few users, outside our school that use the pass. If you guys are willing to give our pass a try, we will be more than happy to help you. Notice that we have put some detailed instructions at http://code.google.com/p/range-analysis/wiki/HowToUseRangeAnalysisInAnotherPass about how to use our range analysis.> The idea of integrating your pass as a lazy value pass sounds good. The > question I have is what optimizations benefit from LazyInfo? I only see > one or two transforms that use it in LLVM 3.0.Yes, I do not think there are many optimizations that use LazyInfo so far. But maybe, backed by a more aggressive analysis, LazyInfo will be more effective. I can implement dead-code elimination based on value ranges, and I think it can be quite effective, even more in code that is produced out of type-safe languages, such as Java, which is full of safety checks. 2012/3/29 John Criswell <criswell at illinois.edu>> On 3/29/12 3:59 PM, Victor Campos wrote: > > Dear LLVMers, > > I have been working on Douglas's range analysis, and today, after > toiling with it for two years, we have a very mature and robust > implementation, which is publicly available at > http://code.google.com/p/range-analysis/. We can, at this point, > perform range analysis on very large benchmarks in a few seconds. To > give you an idea, we take less than 10 seconds to globally analyze > SPEC 2006 gcc benchmark with function inlining enabled. And the > analysis is fairly precise. We have a gallery of examples at > http://code.google.com/p/range-analysis/wiki/gallery that will give > you an idea of what kind of information we can find. Our analysis > comes together with a dynamic profiler that points the minimum and > maximum values that each variable assumes during program execution > too. And it uses a live range splitting strategy to obtain data-flow > sparsity that is lightning fast. It is more than 100x faster than the > original implementation of SSI in LLVM 2.7, for instance. There are a > number of LLVMers, outside my university, that use our analysis. > > > What version of LLVM does your analysis use currently? > > It sounds like your analysis is fast. Can you show results on how fast it > is on various programs? Do you have measurements on how much memory it > uses? How large is the largest program you've compiled with it? > > > So, I would like to propose a summer of code that consists in (i) > integrating our infra-structure in the LLVM main tree, and (ii) > writing a dead-code elimination pass that uses the analysis as a > client. So far people have been using our analysis to check for buffer > overflows, and to eliminate array bound checks. > > > If possible, I think you should first implement the dead-code elimination > optimization that uses your analysis to show how much of a performance win > your analysis provides for LLVM. If the optimization is sufficiently fast > and provides enough of a speedup, then it can be integrated into LLVM > (because you will have proof that it is a performance win; that will help > convince current developers with commit access to review your code for > inclusion). > > We in the SAFECode project would be interested in trying your analysis out > for eliminating bounds checks. We just haven't had the time to do that yet > (I'm assuming you're the same person that wanted to do Value Range analysis > last year). > > > Yet, I think there is > a lot of potential to optimizations. Dead code elimination at branches > would be one such optimization. Given that the analysis is pretty > mature, I think that it would not be too difficult to integrate it in > the current infra-structure that LLVM offers, e.g., Lazy Values. As > for dead-code, we already can flag variables that have impossible > intervals, in which the lower bound is larger than the upper bound. > So, it is only a matter of adapting it to remove this code. > > > > Regarding a dead-code elimination algorithm, I can see something like an > Aggressive Dead Code Elimination pass using your analysis to prove that > certain branches are never taken. One thing you could do would be to write > a pass that looks for icmp instructions and uses your analysis to change > them to true/false when possible. SCCP, ADCE, and other optimizations > would then take care of the rest. > > The idea of integrating your pass as a lazy value pass sounds good. The > question I have is what optimizations benefit from LazyInfo? I only see > one or two transforms that use it in LLVM 3.0. > > > > I would like to hear from you what you think about this Summer of Code > project. If you think it could be interesting, I will write a proposal > richer in details. > > > My interest in range analysis is for using it with SAFECode, but if it can > be used for standard compiler optimization and gets integrated into LLVM, > all the better for me. > > -- John T. > > > Sincerely yours, > > Victor > > > _______________________________________________ > LLVM Developers mailing listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120330/0a6ff87f/attachment.html>
On 3/30/12 2:32 PM, Victor Campos wrote:> > What version of LLVM does your analysis use currently? > > We are working with LLVM 3.0 (stable release) > > > It sounds like your analysis is fast. Can you show results on how > fast it > > is on various programs? Do you have measurements on how much memory it > > uses? How large is the largest program you've compiled with it? > > Yes, we have a very extensive report about it. Take a look into the > pdf at > http://code.google.com/p/range-analysis/source/browse/trunk/doc/Manuscript/paper.pdfI took a brief look at your report. I'm not sure what others in the LLVM community think (and I'd like their input), but I suspect that 10-15 seconds for analyzing GCC means that users would want your analysis enabled at optimization levels higher than -O2. When I asked for memory usage, I meant the amount of RAM used by the analysis. As far as I can tell, your paper only reports the number of constraints, so it doesn't really tell me how much RAM the analysis uses. That said, your test machine had about 3 GB of RAM, so I assume all your test runs used less than that. Do you have a more precise (and hopefully smaller) upper-bound? One other thing I've been wondering about is whether your analysis is able to find value ranges for the results of load instructions. Can it do that? If so, I assume it relies on a points-to analysis. Finally, do you think it would be possible in the future to use parallelism to improve the performance of your analysis?> > In particular, take a look into fig.10, that shows program size vs > runtime. We are truly linear on the program size. The largest program > that we have compiled is SPEC CPU 2006 gcc. It takes less than 10 > seconds to analyze it. This is the largest program that we had here. > Its constraint graph has almost 1.5 million nodes.I recommend that your proposal mention that you'll try your analysis on larger and more diverse codes (especially non-benchmark codes). Programs like Apache, Firefox, MySQL, LLVM, and the FreeBSD kernel come to mind. I'm not sure that the GCC SPEC benchmark is considered a monster-sized program these days.> > > We in the SAFECode project would be interested in trying your > analysis out > > for eliminating bounds checks. We just haven't had the time to do > that yet > > (I'm assuming you're the same person that wanted to do Value Range > analysis > > last year). > > No, that was Douglas, a friend of mine. He is in Texas nowadays.Fascinating. A former student of ours is a postdoc at UT-Austin. Small world.> Now I > am responsible for the range analysis project at UFMG. There are two > other guys working with me on it too. And there are a few users, > outside our school that use the pass. If you guys are willing to give > our pass a try, we will be more than happy to help you. Notice that we > have put some detailed instructions at > http://code.google.com/p/range-analysis/wiki/HowToUseRangeAnalysisInAnotherPass > about how to use our range analysis.I'd like to look into that, but my schedule to date hasn't permitted me to do so. We have a new person, though, that might be able to look into that in the coming months. It seems Raphael Ernani Rodrigues may be interested in working on it, too.> > > The idea of integrating your pass as a lazy value pass sounds good. The > > question I have is what optimizations benefit from LazyInfo? I only see > > one or two transforms that use it in LLVM 3.0. > > Yes, I do not think there are many optimizations that use LazyInfo so > far. But maybe, backed by a more aggressive analysis, LazyInfo will be > more effective. I can implement dead-code elimination based on value > ranges, and I think it can be quite effective, even more in code that > is produced out of type-safe languages, such as Java, which is full of > safety checks.Regarding your comment about Java, I think you're correct that your range analysis would be better at optimizing Java code. However, LLVM really isn't used for Java, so I'm not sure if that's a strong argument for your proposal. To get the best bang for the buck, I think your analysis will need to work well in optimizing C/C++/Objective-C[++] code. One thing that concerns me is that your project currently sounds like a small research project: you want to hook your analysis into dead code elimination and see how well it works. I'm not sure if the GSoC people are really looking for a project like that; they may want something with a higher assurance of a payoff. One thing you could do to mitigate that problem is to do an experiment that *shows* that your analysis has the potential to find more optimization opportunities than what LLVM does today. For example, for dead code elimination, you could run your analysis on optimized LLVM bitcode and find the percentage of icmp/fcmp instructions that can be changed into constants. If you find a large percentage, then it is more likely that your analysis will help dead code elimination or other optimizations. I'd also recommend that you think of other optimizations that could benefit from range analysis and at least list them in your proposal as optimizations you'll look at if time permits. -- John T.
Hi John,> Regarding your comment about Java, I think you're correct that your > range analysis would be better at optimizing Java code. However, LLVM > really isn't used for Java, so I'm not sure if that's a strong argument > for your proposal. To get the best bang for the buck, I think your > analysis will need to work well in optimizing C/C++/Objective-C[++] code.I use LLVM for compiling Ada. Ada turns into LLVM IR which is chock-a-block full of range checks, so this analysis might be helpful for Ada.> One thing you could do to mitigate that problem is to do an experiment > that *shows* that your analysis has the potential to find more > optimization opportunities than what LLVM does today. For example, for > dead code elimination, you could run your analysis on optimized LLVM > bitcode and find the percentage of icmp/fcmp instructions that can be > changed into constants. If you find a large percentage, then it is more > likely that your analysis will help dead code elimination or other > optimizations.In short, if you can speed up important programs using your analysis then that would be a great selling point. Ciao, Duncan.
On Sat, 31 Mar 2012, John Criswell wrote:> One thing you could do to mitigate that problem is to do an experiment > that *shows* that your analysis has the potential to find more > optimization opportunities than what LLVM does today.I strongly agree. If the analysis doesn't provide a good value proposition, almost nobody will care about it. A great use case for value range analysis (that I'm personally very interested in) is improving the performance of codes that check for integer overflows: http://embed.cs.utah.edu/ioc/ The synergy should be obvious. To improve the performance of these codes, someone will need to write a pass that uses value ranges to optimize the LLVM intrinsics that check for math overflows. Ideally, the overhead of overflow checking could be reduced to the point where some users might enable it in production codes. John Regehr