CVP: Make CVP iterate in an order that maximizes reuse of LVI cache

[• dberlin]

Summary

After the DFS order change for LVI, i have a few testcases that now
take forever.

The TL;DR - This is mainly due to the overdefined cache, but that
requires predicateinfo to fix[1]

In order to maximize reuse of the LVI cache for now, change the order
we iterate in.

This reduces my testcase from 5 minutes to 4 seconds.

I have verified cases like gmic do not get slower.

I am playing with whether the order should be postorder or idf.

[1] In practice, overdefined anywhere should be overdefined
everywhere, so this cache should be global. That also fixes this bug.
The problem, however, is that LVI relies on this cache being filled in
per-block because it wants different values in different blocks due to
precisely the naming issue that predicateinfo fixes. With
predicateinfo, making the cache global works fine on individual
passes, and also resolves this issue.

[echristo]

Seems reasonable to me and probably something you can just commit :)

[davide]

In D29679#669878, @echristo wrote:

Seems reasonable to me and probably something you can just commit :)

+1

[• dberlin]

Ugh. I reverted this.
CVP is completely borked as an optimization, it gets no answers if you iterate in anything but top-down order.

That is , given
define i32 @test1(i1 %C) nounwind {

br i1 %C, label %exit, label %body

body: ; preds = %0

%A = select i1 %C, i32 10, i32 11               ; <i32> [#uses=1]
ret i32 %A

exit: ; preds = %0

ret i32 10

}
if you process body before entry, it gives "overdefined" for %A
if you process entry before body, it gives "11" for %A

Any reasonable optimization would get right answers but slower :(

This is

1. Sad because it makes LVI's laziness utterly and completely pointless.
2. It means my one testcase is pretty much unfixable without predicateinfo.

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   return (Result == LazyValueInfo::True) ?
     ConstantInt::getTrue(C->getContext()) :
     ConstantInt::getFalse(C->getContext());
 }
 
 static bool runImpl(Function &F, LazyValueInfo *LVI) {
   bool FnChanged = false;
 
-  // Visiting in a pre-order depth-first traversal causes us to simplify early
-  // blocks before querying later blocks (which require us to analyze early
-  // blocks).  Eagerly simplifying shallow blocks means there is strictly less
-  // work to do for deep blocks.  This also means we don't visit unreachable
-  // blocks. 
-  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
+  // Visiting in an inverse depth first traversal maximizes reuse of the LVI
+  // cache, as it currently iterates in depth first order upwards, caching
+  // overdefined info as it goes.
+
+  for (BasicBlock *BB : inverse_depth_first(&F.getEntryBlock())) {
     bool BBChanged = false;
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
       Instruction *II = &*BI++;
       switch (II->getOpcode()) {
       case Instruction::Select:
         BBChanged |= processSelect(cast<SelectInst>(II), LVI);
         break;
       case Instruction::PHI: