While trying to find a solution for this bug http://llvm.org/bugs/show_bug.cgi?id=11235 , I came to the conclusion that the following things can happen while optimizing: - after gvn, I get new constants which are inserted into br and add/sum/..., so there should be at least one more jump-threading and/or instsimplify - after instsimplify, I get new constants which are inserted into br, so there should be one more jump-threading pass - after jump-threading, new bigger blocks occur with redundant loads which need an other gvn pass At least for -O3 we will need those optimizations. Is there a kind of "I need at least one more $XYZ pass" call that can be invoked from a Pass? So my suggestion to implement in LLVM is: - Detect where exactly constants are inserted - Detect which pass is responsible to continue folding it - Insert that pass if allowed and if it is not in the queue by a ProposePass function ProposePass should decide wether it's worth to further constant fold the block by running the proposed pass. Once accepted, the pass should be inserted into the pass queue at a position where it is most effective. What do you think about that idea? How much would be the effort of implementing it? Does it fit the layering design? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111202/2fd507cd/attachment.html>
On Fri, Dec 2, 2011 at 11:56 AM, Carl-Philip Hänsch <cphaensch at googlemail.com> wrote:> While trying to find a solution for this bug > http://llvm.org/bugs/show_bug.cgi?id=11235 , > I came to the conclusion that the following things can happen while > optimizing: > - after gvn, I get new constants which are inserted into br and > add/sum/..., so there should be at least one more jump-threading and/or > instsimplify > - after instsimplify, I get new constants which are inserted into br, so > there should be one more jump-threading pass > - after jump-threading, new bigger blocks occur with redundant loads which > need an other gvn pass > > At least for -O3 we will need those optimizations. > Is there a kind of "I need at least one more $XYZ pass" call that can be > invoked from a Pass? > > So my suggestion to implement in LLVM is: > - Detect where exactly constants are inserted > - Detect which pass is responsible to continue folding it > - Insert that pass if allowed and if it is not in the queue by a > ProposePass function > > ProposePass should decide wether it's worth to further constant fold the > block by running the proposed pass. Once accepted, the pass should be > inserted into the pass queue at a position where it is most effective. > > What do you think about that idea? How much would be the effort of > implementing it? Does it fit the layering design?One thing that this proposal doesn't really address is that running GVN is expensive; on common testcases, it takes much more time to run than any other pass. We really don't want to be inserting extra runs of GVN into the pass pipeline. -Eli
On Fri, 2011-12-02 at 12:51 -0800, Eli Friedman wrote:> On Fri, Dec 2, 2011 at 11:56 AM, Carl-Philip Hänsch > <cphaensch at googlemail.com> wrote: > > While trying to find a solution for this bug > > http://llvm.org/bugs/show_bug.cgi?id=11235 , > > I came to the conclusion that the following things can happen while > > optimizing: > > - after gvn, I get new constants which are inserted into br and > > add/sum/..., so there should be at least one more jump-threading and/or > > instsimplify > > - after instsimplify, I get new constants which are inserted into br, so > > there should be one more jump-threading pass > > - after jump-threading, new bigger blocks occur with redundant loads which > > need an other gvn pass > > > > At least for -O3 we will need those optimizations. > > Is there a kind of "I need at least one more $XYZ pass" call that can be > > invoked from a Pass? > > > > So my suggestion to implement in LLVM is: > > - Detect where exactly constants are inserted > > - Detect which pass is responsible to continue folding it > > - Insert that pass if allowed and if it is not in the queue by a > > ProposePass function > > > > ProposePass should decide wether it's worth to further constant fold the > > block by running the proposed pass. Once accepted, the pass should be > > inserted into the pass queue at a position where it is most effective. > > > > What do you think about that idea? How much would be the effort of > > implementing it? Does it fit the layering design? > > One thing that this proposal doesn't really address is that running > GVN is expensive; on common testcases, it takes much more time to run > than any other pass. We really don't want to be inserting extra runs > of GVN into the pass pipeline.I also think that this is a good idea. To Eli's point, it would probably be a good idea to be able to tag individual blocks and functions as needing additional work instead of just having an expensive pass go over everything again. -Hal> > -Eli > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-- Hal Finkel Postdoctoral Appointee Leadership Computing Facility Argonne National Laboratory
GVN may be expensive, but for a release build, execution time is more important than build time for releases. This fact is noted in my proposal: the ProposePass function can decide if it will allow a further GVN or not. ProposePass can decide to run every other pass before running into a new GVN. ProposePass can ensure, that GVN is not called twice in a -O2 or -O1 build. In my profilings, I noted that llc needs about 45% of the total compilation time while opt needs 33%. In the testcase i worked with, I was able to shrink the code size to 30% (to, not by!). This means less data passed to the code generator and btw a faster compiler, too when compiled with clang. 2011/12/2 Eli Friedman <eli.friedman at gmail.com>> On Fri, Dec 2, 2011 at 11:56 AM, Carl-Philip Hänsch > <cphaensch at googlemail.com> wrote: > > While trying to find a solution for this bug > > http://llvm.org/bugs/show_bug.cgi?id=11235 , > > I came to the conclusion that the following things can happen while > > optimizing: > > - after gvn, I get new constants which are inserted into br and > > add/sum/..., so there should be at least one more jump-threading and/or > > instsimplify > > - after instsimplify, I get new constants which are inserted into br, so > > there should be one more jump-threading pass > > - after jump-threading, new bigger blocks occur with redundant loads > which > > need an other gvn pass > > > > At least for -O3 we will need those optimizations. > > Is there a kind of "I need at least one more $XYZ pass" call that can be > > invoked from a Pass? > > > > So my suggestion to implement in LLVM is: > > - Detect where exactly constants are inserted > > - Detect which pass is responsible to continue folding it > > - Insert that pass if allowed and if it is not in the queue by a > > ProposePass function > > > > ProposePass should decide wether it's worth to further constant fold the > > block by running the proposed pass. Once accepted, the pass should be > > inserted into the pass queue at a position where it is most effective. > > > > What do you think about that idea? How much would be the effort of > > implementing it? Does it fit the layering design? > > One thing that this proposal doesn't really address is that running > GVN is expensive; on common testcases, it takes much more time to run > than any other pass. We really don't want to be inserting extra runs > of GVN into the pass pipeline. > > -Eli >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111203/dacb6cd1/attachment.html>
On Dec 2, 2011, at 11:56 AM, Carl-Philip Hänsch wrote:> While trying to find a solution for this bug http://llvm.org/bugs/show_bug.cgi?id=11235 , > I came to the conclusion that the following things can happen while optimizing: > - after gvn, I get new constants which are inserted into br and add/sum/..., so there should be at least one more jump-threading and/or instsimplify > - after instsimplify, I get new constants which are inserted into br, so there should be one more jump-threading pass > - after jump-threading, new bigger blocks occur with redundant loads which need an other gvn pass > > At least for -O3 we will need those optimizations. > Is there a kind of "I need at least one more $XYZ pass" call that can be invoked from a Pass? > > So my suggestion to implement in LLVM is: > - Detect where exactly constants are inserted > - Detect which pass is responsible to continue folding it > - Insert that pass if allowed and if it is not in the queue by a ProposePass function > > ProposePass should decide wether it's worth to further constant fold the block by running the proposed pass. Once accepted, the pass should be inserted into the pass queue at a position where it is most effective. > > What do you think about that idea? How much would be the effort of implementing it? Does it fit the layering design?This looks like a slippery slope towards finding optimal optimization pass sequence. Why not fix pass sequence manually by updating PassManagerBuilder directly ? - Devang -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111205/1357c2c5/attachment.html>
When you think this fixes bug 11235 and all test cases that are more complex than that, why not? 2011/12/5 Devang Patel <dpatel at apple.com>> > On Dec 2, 2011, at 11:56 AM, Carl-Philip Hänsch wrote: > > While trying to find a solution for this bug > http://llvm.org/bugs/show_bug.cgi?id=11235 , > I came to the conclusion that the following things can happen while > optimizing: > - after gvn, I get new constants which are inserted into br and > add/sum/..., so there should be at least one more jump-threading and/or > instsimplify > - after instsimplify, I get new constants which are inserted into br, so > there should be one more jump-threading pass > - after jump-threading, new bigger blocks occur with redundant loads > which need an other gvn pass > > At least for -O3 we will need those optimizations. > Is there a kind of "I need at least one more $XYZ pass" call that can be > invoked from a Pass? > > So my suggestion to implement in LLVM is: > - Detect where exactly constants are inserted > - Detect which pass is responsible to continue folding it > - Insert that pass if allowed and if it is not in the queue by a > ProposePass function > > ProposePass should decide wether it's worth to further constant fold the > block by running the proposed pass. Once accepted, the pass should be > inserted into the pass queue at a position where it is most effective. > > What do you think about that idea? How much would be the effort of > implementing it? Does it fit the layering design? > > > This looks like a slippery slope towards finding optimal optimization pass > sequence. > > Why not fix pass sequence manually by updating PassManagerBuilder directly > ? > - > Devang > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111205/6fc526a8/attachment.html>