Passes propose passes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Passes propose passes

Carl-Philip Hänsch
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?

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Passes propose passes

Eli Friedman-2
On Fri, Dec 2, 2011 at 11:56 AM, Carl-Philip Hänsch
<[hidden email]> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Passes propose passes

Hal Finkel
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
> <[hidden email]> 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
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Passes propose passes

Carl-Philip Hänsch
In reply to this post by Eli Friedman-2
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 <[hidden email]>
On Fri, Dec 2, 2011 at 11:56 AM, Carl-Philip Hänsch
<[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Passes propose passes

Devang Patel
In reply to this post by Carl-Philip Hänsch

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


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Passes propose passes

Carl-Philip Hänsch
When you think this fixes bug 11235 and all test cases that are more complex than that, why not?

2011/12/5 Devang Patel <[hidden email]>

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



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev