[CVP] Fold return values if possible

[reames]

Summary

In my previous change to CVP (251606), I made CVP much more aggressive about trying to constant fold comparisons. This patch is a reversal in direction. Rather than being agressive about every compare, we restore the non-block local restriction for most, and then try hard for compares feeding returns.

The motivation for this is two fold:

1. The more I thought about it, the less comfortable I got with the possible compile time impact of the other approach. There have been no reported issues, but after talking to a couple of folks, I've come to the conclusion the time probably isn't justified.
2. It turns out we need to know the context to leverage the full power of LVI. In particular, asking about something at the end of it's block (the use of a compare in a return) will frequently get more precise results than something in the middle of a block. This is an implementation detail, but it's also hard to get around since mid-block queries have to reason about possible throwing instructions and don't get to use most of LVI's block focused infrastructure. This will become particular important when combined with http://reviews.llvm.org/D14263.

[nlewycky]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

52

"Constant*" -> "Constant *"

198

chose -> choose (present tense)

200

"it's not it's primary purposes" -> "it's not its primary purpose". (it's -> its and purposes -> purpose)

333

Constant* -> Constant *

337

algorith -> algorithm

339–340

What about a single SelectInst?

351–354

Remove the else. See http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

(Yes I know you just copied it from code above.)

test/Transforms/CorrelatedValuePropagation/select.ll

74

Cool!

[reames]

Address Nick's review.

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

339–340

Do you have a particular pattern you'd want to handle? My preference would be a) a follow on change and b) not doing this until I can get this pushed down into LVI. (That's on my list, just need to clear some other LVI/CVP changes out first.)

[nlewycky]

Forgot to LGTM

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "correlated-value-propagation"
 
 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
+STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 
 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
     LazyValueInfo *LVI;
 
     bool processSelect(SelectInst *SI);
     bool processPHI(PHINode *P);
     bool processMemAccess(Instruction *I);
     bool processCmp(CmpInst *C);
     bool processSwitch(SwitchInst *SI);
     bool processCallSite(CallSite CS);
 
+    /// Return a constant value for V usable at At and everything it
+    /// dominates.  If no such Constant can be found, return nullptr.
+    Constant* getConstantAt(Value *V, Instruction *At);
+
   public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 

 /// or range information is sufficient to prove this comparison.  Even for
 /// local conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
   Value *Op0 = C->getOperand(0);
   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
   if (!Op1) return false;
 
+  // As a policy choice, we chose not waste compile time on anything where the
+  // comparison is testing local values.  While LVI can sometimes reason about
+  // such cases, it's not it's primary purposes.  We do make sure to do the
+  // block local query for uses from terminator instructions, but that's
+  // handled in the code for each terminator.
+  auto *I = dyn_cast<Instruction>(Op0);
+  if (I && I->getParent() == C->getParent())
+    return false;
+
   LazyValueInfo::Tristate Result =
     LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
   if (Result == LazyValueInfo::Unknown) return false;
 
   ++NumCmps;
   if (Result == LazyValueInfo::True)
     C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
   else
for (Value *V : CS.args()) {
     }
     ArgNo++;
   }
   assert(ArgNo == CS.arg_size() && "sanity check");
 
   return Changed;
 }
 
+Constant* CorrelatedValuePropagation::getConstantAt(Value *V, Instruction *At) {
+  if (Constant *C = LVI->getConstant(V, At->getParent(), At))
+    return C;
+
+  // TODO: The following really should be sunk inside LVI's core algorith, or
+  // at least the outer shims around such.
+  auto *C = dyn_cast<CmpInst>(V);
+  if (!C) return nullptr;
+
+  Value *Op0 = C->getOperand(0);
+  Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
+  if (!Op1) return nullptr;
+  
+  LazyValueInfo::Tristate Result =
+    LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At);
+  if (Result == LazyValueInfo::Unknown)
+    return nullptr;
+  
+  if (Result == LazyValueInfo::True)
+    return ConstantInt::getTrue(C->getContext());
+  else
+    return ConstantInt::getFalse(C->getContext());
+}
+
 bool CorrelatedValuePropagation::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   LVI = &getAnalysis<LazyValueInfo>();
 
   bool FnChanged = false;
 
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
       }
     }
 
     Instruction *Term = FI->getTerminator();
     switch (Term->getOpcode()) {
     case Instruction::Switch:
       BBChanged |= processSwitch(cast<SwitchInst>(Term));
       break;
+    case Instruction::Ret: {
+      auto *RI = cast<ReturnInst>(Term);
+      // Try to determine the return value if we can.  This is mainly here to
+      // simplify the writing of unit tests, but also helps to enable IPO by
+      // constant folding the return values of callees.
+      auto *RetVal = RI->getReturnValue();
+      if (!RetVal) break; // handle "ret void"
+      if (auto *C = getConstantAt(RetVal, RI)) {
+        ++NumReturns;
+        RI->replaceUsesOfWith(RetVal, C);
+        BBChanged = true;        
+      }
     }
+    };
 
     FnChanged |= BBChanged;
   }
 
   return FnChanged;
 }

test/Transforms/CorrelatedValuePropagation/select.ll

for.body:
   br i1 %cmp, label %for.body, label %if.end
 
 ; CHECK:      %[[sel:.*]] = select i1 icmp sgt (i32* @b, i32* @c), i32 0, i32 1
 ; CHECK-NEXT: %[[cmp:.*]] = icmp ne i32 %[[sel]], 1
 ; CHECK-NEXT: br i1 %[[cmp]]
 
 if.end:
   ret i32 %sel
-; CHECK: ret i32 %[[sel]]
+; CHECK: ret i32 1
 }