[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

90

Don't these need to change as well?

102

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

152

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

 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) {
+  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.
+    if (!Inst)
+      return false;
     // This can only handle non-void readnone functions.
     if (CallInst *CI = dyn_cast<CallInst>(Inst))
       return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();

 namespace llvm {
 template <> struct DenseMapInfo<SimpleValue> {
   static inline SimpleValue getEmptyKey() {
-    return DenseMapInfo<Instruction *>::getEmptyKey();
+    return DenseMapInfo<Value *>::getEmptyKey();
   }
   static inline SimpleValue getTombstoneKey() {
-    return DenseMapInfo<Instruction *>::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 = Val.Inst;
+  Instruction *Inst = cast<Instruction>(Val.Val);
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *LHS = BinOp->getOperand(0);

 }
 
 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
-  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
-
   if (LHS.isSentinel() || RHS.isSentinel())
-    return LHSI == RHSI;
+    return LHS.Val == RHS.Val;
+
+  // Otherwise try to prove equality of instructions.
+  Instruction *LHSI = cast<Instruction>(LHS.Val);
+  Instruction *RHSI = cast<Instruction>(RHS.Val);
 
   if (LHSI->getOpcode() != RHSI->getOpcode())
     return false;

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

     // 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;

       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)) {
+        // Do we already know the actual value of this condition?
+        if (auto *KnownCond = AvailableValues.lookup(Cond)) {
+          // 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(Cond, ConstantInt::getTrue(BB->getContext()));
       }
 
       // Guard intrinsics read all memory, but don't write any memory.