[EarlyCSE] Prepare EarlyCSE to work with non-instruction values

[mkazantsev]

Summary

Conditional branching, intrinsics experimental_guard and assume may state that their arguments are true/false.
This patch performs a refactoring (which is supposed to be a NFC) that changes interface and internals of SimpleValue
to accept Values instead of Instructions. Currently, all non-instruction values get rejected on in canHandle method to
preserve the existing behavior, but this will change in a follow-up patch.

[reames]

lib/Transforms/Scalar/EarlyCSE.cpp

68

These three cover functions seem to obscure more than they help clarify. Or at least they did for me. I'd advice removing them and just directly working with the Val field.

82

A tactical suggestion here: do the refactoring to change all the types w/o actually adding values to the canHandle predicate then separately check in the change which actually allows the Values to flow through. (i.e. basically return false here in the initial patch)

The reasoning here is that if this does expose a problem (miscompile, crash, etc..), knowing whether you made a mistake in the refactoring part or if the value handling itself was the actual guilty party will be useful.

Not a required change, but something I would encourage.

112

This would be more idiomatic as:
Instruction *Inst = dyn_cast<Instruction>(Val.Val);
if (!Inst)

return hash_combine(Val.Val);

[mkazantsev]

Splitting the change into two. This becomes a non-functional change of SimpleValue interface and internals.

[reames]

minor comments, once addressed looks likely ready to go. I do want to see the fixed patch before submission.

lib/Transforms/Scalar/EarlyCSE.cpp

101

Don't these need to change as well?

113

cast is a checked cast. The previous assert is unnecessary.

167

Again, checked casts.

[mkazantsev]

Addressed comments.

[reames]

LGTM.

[mkazantsev]

Hold this until https://reviews.llvm.org/D32641 is done properly. This patch does not make sense separately.

[mkazantsev]

Abandoning it so far, maybe will return to it in future.

lib/Transforms/Scalar/EarlyCSE.cpp

 
 //===----------------------------------------------------------------------===//
 // SimpleValue
 //===----------------------------------------------------------------------===//
 
 namespace {
 /// \brief Struct representing the available values in the scoped hash table.
 struct SimpleValue {
-  Instruction *Inst;
+  Value *Val;
 
-  SimpleValue(Instruction *I) : Inst(I) {
-    assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
+  SimpleValue(Value *V) : Val(V) {
+    assert((isSentinel() || canHandle(V)) && "Value can't be handled!");
   }
 
   bool isSentinel() const {
-    return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
-           Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
+    return Val == DenseMapInfo<Value *>::getEmptyKey() ||
+           Val == DenseMapInfo<Value *>::getTombstoneKey();
   }
 
-  static bool canHandle(Instruction *Inst) {
+  Instruction *getInst() const {
+    assert(isInst() && "This SimpleValue does not represent an instruction!");
+    return cast<Instruction>(Val);
+  }
+
+  Value *getValue() const {
+    return Val;
+  }
+
+  bool isInst() const {
+    return !isSentinel() && isa<Instruction>(Val);
+  }
+
+  static bool canHandle(Value *Val) {
+    Instruction *Inst = dyn_cast<Instruction>(Val);
+    // We can handle all non-instruction values.
+    if (!Inst)
+      return true;
     // This can only handle non-void readnone functions.
     if (CallInst *CI = dyn_cast<CallInst>(Inst))
       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
     return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
            isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
            isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
            isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
            isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
   }
 };
 }
 
 namespace llvm {
 template <> struct DenseMapInfo<SimpleValue> {
   static inline SimpleValue getEmptyKey() {
     return DenseMapInfo<Instruction *>::getEmptyKey();
   }
   static inline SimpleValue getTombstoneKey() {
     return DenseMapInfo<Instruction *>::getTombstoneKey();
   }
   static unsigned getHashValue(SimpleValue Val);
   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
 };
 }
 
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
-  Instruction *Inst = Val.Inst;
+  if (!Val.isInst())
+    return hash_combine(Val.getValue());
+  Instruction *Inst = Val.getInst();
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *LHS = BinOp->getOperand(0);
     Value *RHS = BinOp->getOperand(1);
     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
       std::swap(LHS, RHS);
 
     return hash_combine(BinOp->getOpcode(), LHS, RHS);
unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
 
   // Mix in the opcode.
   return hash_combine(
       Inst->getOpcode(),
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 }
 
 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
-  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
+  // Equal values are both either instructions or not.
+  if (LHS.isInst() != RHS.isInst())
+    return false;
 
-  if (LHS.isSentinel() || RHS.isSentinel())
-    return LHSI == RHSI;
+  // If they are not instructions, simply compare values.
+  if (!LHS.isInst() || LHS.isSentinel() || RHS.isSentinel())
+    return LHS.getValue() == RHS.getValue();
+
+  // Otherwise try to prove equality of instructions.
+  Instruction *LHSI = LHS.getInst(), *RHSI = RHS.getInst();
 
   if (LHSI->getOpcode() != RHSI->getOpcode())
     return false;
   if (LHSI->isIdenticalToWhenDefined(RHSI))
     return true;
 
   // If we're not strictly identical, we still might be a commutable instruction
   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
bool EarlyCSE::processNode(DomTreeNode *Node) {
   // we can infer the value of the branch condition given that we took this
   // path.  We need the single predecessor to ensure there's not another path
   // which reaches this block where the condition might hold a different
   // value.  Since we're adding this to the scoped hash table (like any other
   // def), it will have been popped if we encounter a future merge block.
   if (BasicBlock *Pred = BB->getSinglePredecessor()) {
     auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
     if (BI && BI->isConditional()) {
-      auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
-      if (CondInst && SimpleValue::canHandle(CondInst)) {
+      auto *Cond = BI->getCondition();
+      if (SimpleValue::canHandle(Cond)) {
         assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
         auto *TorF = (BI->getSuccessor(0) == BB)
                          ? ConstantInt::getTrue(BB->getContext())
                          : ConstantInt::getFalse(BB->getContext());
-        AvailableValues.insert(CondInst, TorF);
+        AvailableValues.insert(Cond, TorF);
         DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
-                     << CondInst->getName() << "' as " << *TorF << " in "
+                     << Cond->getName() << "' as " << *TorF << " in "
                      << BB->getName() << "\n");
         // Replace all dominated uses with the known value.
         if (unsigned Count = replaceDominatedUsesWith(
-                CondInst, TorF, DT, BasicBlockEdge(Pred, BB))) {
+                Cond, TorF, DT, BasicBlockEdge(Pred, BB))) {
           Changed = true;
           NumCSECVP = NumCSECVP + Count;
         }
       }
     }
   }
 
   /// LastStore - Keep track of the last non-volatile store that we saw... for
if (isInstructionTriviallyDead(Inst, &TLI)) {
       continue;
     }
 
     // Skip assume intrinsics, they don't really have side effects (although
     // they're marked as such to ensure preservation of control dependencies),
     // and this pass will not bother with its removal. However, we should mark
     // its condition as true for all dominated blocks.
     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
-      auto *CondI =
-          dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0));
-      if (CondI && SimpleValue::canHandle(CondI)) {
+      auto *Cond = cast<CallInst>(Inst)->getArgOperand(0);
+      if (SimpleValue::canHandle(Cond)) {
         DEBUG(dbgs() << "EarlyCSE considering assumption: " << *Inst << '\n');
-        AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+        AvailableValues.insert(Cond, ConstantInt::getTrue(BB->getContext()));
       } else
         DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
       continue;
     }
 
     // Skip invariant.start intrinsics since they only read memory, and we can
     // forward values across it. Also, we dont need to consume the last store
     // since the semantics of invariant.start allow us to perform DSE of the
     // last store, if there was a store following invariant.start. Consider:
     //
     // store 30, i8* p
     // invariant.start(p)
     // store 40, i8* p
     // We can DSE the store to 30, since the store 40 to invariant location p
     // causes undefined behaviour.
     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))) {
-        if (SimpleValue::canHandle(CondI)) {
-          // Do we already know the actual value of this condition?
-          if (auto *KnownCond = AvailableValues.lookup(CondI)) {
-            // Is the condition known to be true?
-            if (isa<ConstantInt>(KnownCond) &&
-                cast<ConstantInt>(KnownCond)->isOneValue()) {
-              DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
-              removeMSSA(Inst);
-              Inst->eraseFromParent();
-              Changed = true;
-              continue;
-            } else
-              // Use the known value if it wasn't true.
-              cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
-          }
-          // The condition we're on guarding here is true for all dominated
-          // locations.
-          AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
-        }
+      auto *Cond = cast<CallInst>(Inst)->getArgOperand(0);
+      if (SimpleValue::canHandle(Cond)) {
+        if (auto *KnownCond = AvailableValues.lookup(Cond)) {
+        AvailableValues.insert(Cond, ConstantInt::getTrue(BB->getContext()));
       }
 
       // 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:    call void @llvm.assume(i1 %c)
 ; CHECK-NEXT:    call void @llvm.assume(i1 %c)
 ; CHECK-NEXT:    ret void
 
   call void @llvm.assume(i1 %c)
   call void @llvm.assume(i1 %c)
   ret void
 }
+
+define void @test19(i1 %c) {
+; Check that assume can mark a non-instruction value as true.
+
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:    call void @llvm.assume(i1 %c)
+; CHECK-NEXT:    ret void
+
+  call void @llvm.assume(i1 %c)
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  ret void
+}
+
+define void @test20(i1 %c) {
+; Check that guard can mark a non-instruction value as true.
+
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+; CHECK-NEXT:    ret void
+
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  ret void
+}
+
+define void @test21(i1 %c) {
+; Check that branching by a non-instruction condition allows to remove guards.
+
+; CHECK-LABEL: @test21(
+; CHECK:       entry:
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"() ]
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test22(i1 %cmp, i1 %c, i32* %ptr) {
+; Similar to test14, but with assumed condition being non-instruction.
+
+; CHECK-LABEL: @test22(
+; CHECK:       entry:
+; CHECK-NEXT:    call void @llvm.assume(i1 %cmp)
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 600, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  call void @llvm.assume(i1 %cmp)
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 500, i32* %ptr
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 600, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}
+
+define void @test23(i1 %cmp, i1 %c, i32* %ptr) {
+; Similar to test22, guard instead of assume.
+
+; CHECK-LABEL: @test23(
+; CHECK:       entry:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+; CHECK-NEXT:    store i32 400, i32* %ptr
+; CHECK-NEXT:    br i1 %c, label %if.true, label %if.false
+; CHECK:       if.true:
+; CHECK-NEXT:    store i32 500, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       if.false:
+; CHECK-NEXT:    store i32 600, i32* %ptr
+; CHECK-NEXT:    br label %merge
+; CHECK:       merge:
+; CHECK-NEXT:    ret void
+
+entry:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 100, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 200, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 300, i32* %ptr
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 400, i32* %ptr
+  br i1 %c, label %if.true, label %if.false
+
+if.true:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 500, i32* %ptr
+  br label %merge
+
+if.false:
+  call void (i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  store i32 600, i32* %ptr
+  br label %merge
+
+merge:
+  ret void
+}