Passes propose passes

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

> 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

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@gmail.com>

This looks like a slippery slope towards finding optimal optimization pass sequence.

Why not fix pass sequence manually by updating PassManagerBuilder directly ?

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@apple.com>