[EarlyCSE] infer conditional equalities within basic blocks

[reames]

Summary

Both llvm.experimental.guard and llvm.assume intrinsics can introduce facts in the middle of a basic block. Previously, EarlyCSE was not exploiting these facts when visiting later instructions in the same block.

Worth noting is that the choice to visit each operand does make the algorithm O(n^2) in the number of instructions. However, this is not new. We have to hash the operands, so we're already O(n^2). Apparently, most real code doesn't consist of long series of calls which consume each previous instruction. Who knew?

[reames]

fix the bug I noticed immediate after uploading the first version...

[sanjoy]

Comments inline.

lib/Transforms/Scalar/EarlyCSE.cpp

620

In the pathological case that you mentioned won't this be O(I^3), since you're doing:

for each Inst in BB:
  for each operand I of Inst:
    for each operand X of I:
      hash(X)

Maybe we can find an better bound as a function of the number of total uses?

674

This bit is NFC right (just adds the debug output)? If so, I'd just land this without review.

test/Transforms/EarlyCSE/guards.ll

195

This will get the case where the second guard was using %cond1 = <same expression as %cond0> right? If so, please add a test case that checks that.

[reames]

Abandoning the revision as I don't have time to get back to this. mkazantsev will be picking up this line of work and will be posting a revised patch at some point in the not to distant future.

lib/Transforms/Scalar/EarlyCSE.cpp

if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
             assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
             auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ?
               ConstantInt::getTrue(BB->getContext()) :
               ConstantInt::getFalse(BB->getContext());
             AvailableValues.insert(CondInst, ConditionalConstant);
             DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
                   << CondInst->getName() << "' as " << *ConditionalConstant
                   << " in " << BB->getName() << "\n");
-            // Replace all dominated uses with the known value.
-            if (unsigned Count =
-                    replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
-                                             BasicBlockEdge(Pred, BB))) {
-              Changed = true;
-              NumCSECVP = NumCSECVP + Count;
-            }
           }
 
   /// LastStore - Keep track of the last non-volatile store that we saw... for
   /// as long as there in no instruction that reads memory.  If we see a store
   /// to the same location, we delete the dead store.  This zaps trivial dead
   /// stores which can occur in bitfield code among other things.
   Instruction *LastStore = nullptr;
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
   // See if any instructions in the block can be eliminated.  If so, do it.  If
   // not, add them to AvailableValues.
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     Instruction *Inst = &*I++;
 
+    // Use the available value table to replace any operands we can.  This
+    // kicks in when we've inferred a control dependent equivelence fact.  Note
+    // that this does make the algorithm O(I^2) in the worst case (a series of
+    // calls which each use the previous instructions), but this was already
+    // true given we have to hash all the operands as well.
+    for (Value *V : Inst->operands())
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        if (SimpleValue::canHandle(I))
+          // See if the instruction has an available value.  If so, use it.
+          if (Value *Rep = AvailableValues.lookup(I)) {
+            DEBUG(dbgs() << "EarlyCSE replaced operand" << *I
+                         << " with " << *Rep << " in " << *Inst << '\n');
+            Inst->replaceUsesOfWith(V, Rep);
+            Changed = true;
+            NumCSECVP++;
+          }
+
     // Dead instructions should just be removed.
     if (isInstructionTriviallyDead(Inst, &TLI)) {
       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
       removeMSSA(Inst);
       Inst->eraseFromParent();
       Changed = true;
       ++NumSimplify;
       continue;
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
       continue;
 
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
         // The condition we're on guarding here is true for all dominated
         // locations.
-        if (SimpleValue::canHandle(CondI))
-          AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+        if (SimpleValue::canHandle(CondI)) {
+          DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
+                << CondI->getName() << "' as true after "
+                << Inst->getName()  << "\n");
+
+          auto *True = ConstantInt::getTrue(BB->getContext());
+          AvailableValues.insert(CondI, True);
+        }
       }
 
       // Guard intrinsics read all memory, but don't write any memory.
       // Accordingly, don't update the generation but consume the last store (to
       // avoid an incorrect DSE).
       LastStore = nullptr;
       continue;
     }

test/Transforms/EarlyCSE/guards.ll

 ; CHECK-NEXT:  store i32 600, i32* %ptr
 
 
   store i32 500, i32* %ptr
   call void(i1,...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
   store i32 600, i32* %ptr
   ret void
 }
+
+define i32 @test7(i32 %val) {
+; After a guard has executed the condition it was guarding is known to
+; be true.  Unlike test3, uses the same condition for both guards and 
+; return value.
+
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:  %cond0 = icmp slt i32 %val, 40
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+; CHECK-NEXT:  ret i32 -1
+
+  %cond0 = icmp slt i32 %val, 40
+  call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+  call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
+  %rval = sext i1 %cond0 to i32
+  ret i32 %rval
+}