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

[mkazantsev]

Summary

Conditional branching, intrinsics experimental_guard and assume may state that their arguments are true/false.
These values are not always instructions. For example, it can be method parameters. This patch allows to store known values (true or false, in particular) for such values.

[mkazantsev]

Rebase due to underlying patch changes.

[mkazantsev]

Fix a typo in comment.

[mkazantsev]

Ping

[• dberlin]

Sorry, thought Phillip looked at this one, looking now

[• dberlin]

lib/Transforms/Scalar/EarlyCSE.cpp

101

This is not correct.
Example: ConstantExpr

157

FWIW: It's possible for a constantexpr to be equivalent to an expression.
This is not likely to happen that often, but.

[mkazantsev]

Thanks for pointing that out, I need to check the applicability of this more accurately.

[mkazantsev]

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

lib/Transforms/Scalar/EarlyCSE.cpp

struct SimpleValue {
 
   bool isSentinel() const {
     return Val == DenseMapInfo<Value *>::getEmptyKey() ||
            Val == DenseMapInfo<Value *>::getTombstoneKey();
   }
 
   static bool canHandle(Value *Val) {
     Instruction *Inst = dyn_cast<Instruction>(Val);
-    // TODO: We reject all non-instruction values so far, but will accept them
-    // in follow-up patch. This is done to diagnose the reason of potential
-    // problems with transition from working with instructions only to values.
+    // Since non-instruction values hever have side effects, we can safely work
+    // with them.
     if (!Inst)
-      return false;
+      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);
static inline SimpleValue getTombstoneKey() {
     return DenseMapInfo<Value *>::getTombstoneKey();
   }
   static unsigned getHashValue(SimpleValue Val);
   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
 };
 }
 
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
-  Instruction *Inst = cast<Instruction>(Val.Val);
+  Instruction *Inst = dyn_cast<Instruction>(Val.Val);
+  // Non-instruction values do not have operands.q
+  if (!Inst)
+    return hash_combine(Val.Val);
   // 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);
return hash_combine(
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 }
 
 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
   if (LHS.isSentinel() || RHS.isSentinel())
     return LHS.Val == RHS.Val;
 
   // Otherwise try to prove equality of instructions.
-  Instruction *LHSI = cast<Instruction>(LHS.Val);
-  Instruction *RHSI = cast<Instruction>(RHS.Val);
+  Instruction *LHSI = dyn_cast<Instruction>(LHS.Val);
+  Instruction *RHSI = dyn_cast<Instruction>(RHS.Val);
+
+  // For non-instruction values, we just compare references.
+  if (!LHSI || !RHSI)
+    return LHS.Val == RHS.Val;
 
   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)) {

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
+}