[JumpThread] Do RAUW in case Cond folds to a constant in the CFG

[trentxintong]

Summary

[JumpThread] Do RAUW in case Cond folds to a constant in the CFG

[trentxintong]

Accidentally removed a few lines.

[sanjoy]

lgtm with nits

lib/Transforms/Scalar/JumpThreading.cpp

1252–1254

Separately, it may be better to use DenseMapInfo<BasicBlock *>::getTombStoneKey() here.

1317

I'd structure this as:

if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
  if (CondInst->use_empty()) {
  } else if (OnlyVal && ...) {
  }
}

Another thing is that this code needs to check !CondInst->mayHaveSideEffects() before removing it.

test/Transforms/JumpThreading/fold-not-thread.ll

142

Please also add a negative test where %add = add i32 %value, 64 is not in L0.

[trentxintong]

lib/Transforms/Scalar/JumpThreading.cpp

1317

Good catch with the extra check !

[trentxintong]

Address Comments

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
   // Decide what we want to thread through.  Convert our list of known values to
   // a list of known destinations for each pred.  This also discards duplicate
   // predecessors and keeps track of the undefined inputs (which are represented
   // as a null dest in the PredToDestList).
   SmallPtrSet<BasicBlock*, 16> SeenPreds;
   SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList;
 
   BasicBlock *OnlyDest = nullptr;
   BasicBlock *MultipleDestSentinel = (BasicBlock*)(intptr_t)~0ULL;
+  Constant *OnlyVal = nullptr;
+  Constant *MultipleVal = (Constant *)(intptr_t)~0ULL;
 
   for (const auto &PredValue : PredValues) {
     BasicBlock *Pred = PredValue.second;
     if (!SeenPreds.insert(Pred).second)
       continue;  // Duplicate predecessor entry.
 
-    // If the predecessor ends with an indirect goto, we can't change its
-    // destination.
-    if (isa<IndirectBrInst>(Pred->getTerminator()))
-      continue;
-
     Constant *Val = PredValue.first;
 
     BasicBlock *DestBB;
     if (isa<UndefValue>(Val))
       DestBB = nullptr;
     else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
       DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
     else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
       DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
     } else {
       assert(isa<IndirectBrInst>(BB->getTerminator())
               && "Unexpected terminator");
       DestBB = cast<BlockAddress>(Val)->getBasicBlock();
     }
 
     // If we have exactly one destination, remember it for efficiency below.
-    if (PredToDestList.empty())
+    if (PredToDestList.empty()) {
       OnlyDest = DestBB;
-    else if (OnlyDest != DestBB)
+      OnlyVal = Val;
+    } else {
+      if (OnlyDest != DestBB)
         OnlyDest = MultipleDestSentinel;
+      // It possible we have same destination, but different value, e.g. default
+      // case in switchinst.
+      if (Val != OnlyVal)
+        OnlyVal = MultipleVal;
+    }
 
     PredToDestList.push_back(std::make_pair(Pred, DestBB));
   }
 
   // If all edges were unthreadable, we fail.
   if (PredToDestList.empty())
     return false;
 
if (PredToDestList.size() ==
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       auto *CondInst = dyn_cast<Instruction>(Cond);
       if (CondInst && CondInst->use_empty())
         CondInst->eraseFromParent();
-      // FIXME: in case this instruction is defined in the current BB and it
-      // resolves to a single value from all predecessors, we can do RAUW.
+      else if (CondInst && OnlyVal && OnlyVal != MultipleVal &&
+               CondInst->getParent() == BB) {
+        // If we just learned Cond is the same value for all uses of the
+        // condition, replace it with a constant value
+        CondInst->replaceAllUsesWith(OnlyVal);
+        CondInst->eraseFromParent();
+      }
       return true;
     }
   }
 
   // Determine which is the most common successor.  If we have many inputs and
   // this block is a switch, we want to start by threading the batch that goes
   // to the most popular destination first.  If we only know about one
   // threadable destination (the common case) we can avoid this.

test/Transforms/JumpThreading/basic.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 
-declare i32 @f1()
-declare i32 @f2()
-declare void @f3()
-
 define i32 @test1(i1 %cond) {
 ; CHECK-LABEL: @test1(
 
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge

test/Transforms/JumpThreading/fold-not-thread.ll

 L2:
   call void @f3()
   ret void
 L3:
   call void @f3()
   ret void
 }
 
+; Make sure we can do the RAUW for %add...
+;
+; CHECK-LABEL: @rauw_if_possible(
+; CHECK: call void @f4(i32 96) 
+define void @rauw_if_possible(i32 %value) nounwind {
+entry:
+  %cmp = icmp eq i32 %value, 32
+  br i1 %cmp, label %L0, label %L3 
+L0:
+  call i32 @f2()
+  call i32 @f2()
+  %add = add i32 %value, 64
+  switch i32 %add, label %L3 [
+    i32 32, label %L1
+    i32 96, label %L2
+    ]
+
+L1:
+  call void @f3()
+  ret void
+L2:
+  call void @f4(i32 %add)
+  ret void
+L3:
+  call void @f3()
+  ret void
+}
+
+