[JumpThreading] Ignore nil destionation when determining whether a block only goes to a single destination

[trentxintong]

Summary

Make sure UNDEF does not cause us to believe a block can have multiple possible destintations.

[trentxintong]

Handle when all destinations are null (i.e. UNDEF value). There is a slight change in pr22086.ll this is due
to we do not run SimplifyInstructionsInBlock after folding (we run after threading).

[trentxintong]

Friendly ping.

[brzycki]

Hi @trentxintong , I am just starting to review this diff and will get back to you with more meaningful comments soon. While I'm doing that could you tell me if this work is from a bug you discovered or for a new feature you'd like to see implemented. Looking at your .ll changes below makes me believe this is a new feature, but I'd like to be sure to know.

[trentxintong]

Hi @brzycki. This is a deficiency in a feature we already have. In jump threading, when we can tell all the predecessors of a block go to the same destination. we do not need to thread, we can just fold the terminator of the block. This has less impact on the CFG and also we do not have the problem of not being able to jump threading because the block can not be duplicated.

In case we have a Val being UNDEF, we can ignore it as it can be treated as going to any successor, i.e. we should not go to MultipleDestSentinel state because we see a DestBB==nullptr.

[brzycki]

My comments are inline. I'm also curious to know what kind of testing you've done on this (ninja check, ninja check-all, any test-suite runs, etc). I'd like more testing if it's just ninja check: the included tests are a small sampling of real-world code and test-suite is a bit better for this kind of change.

lib/Transforms/Scalar/JumpThreading.cpp

1608

It might be better to add a new counter and increment it here:

if (isa<UndefValue>(Val)) {
  ++PredWithUndefDest;
  continue;
} else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {

I dislike that the logic changes below include PredWithKnownDest for undef (unknown) destinations.

1623–1635

Nit: please convert the . to a , from the end of the previous line or consider re-wording the entire comment.

1655–1656

Instead of changing this core logic it might make more sense to do:

if (PredWithUndefDest && !OnlyDest)
  OnlyDest = BB->getTerminator()->getSuccessor(GetBestDestForJumpOnUndef(BB));
if (OnlyDest && OnlyDest != MultipleDestSentinel) {
  if ((PredWithKnownDest + PredWithUndefDest) == (size_t)pred_size(BB)) {
    ...

I say this because ProcessThreadableEdges() and the multiple calls from ProcessBlock() can create complex and subtle interplay. I try to not change the logic as much as possible between these two.

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

332

Is L5 necessary in this functional test? It's connected to nothing.

[brzycki]

Added small fix to suggested code.

lib/Transforms/Scalar/JumpThreading.cpp

1608

You also need to add before the continue:

PredToDestList.push_back(std::make_pair(Pred, nullptr));

inside the UndefValue check.

[brzycki]

Gentle ping for @trentxintong .

[llvm-commits]

Hi Brian

Thank you very much for the review. I have not taken a look at the
code after integrating what Danny has said. I will take a look at it
in the next few days and see whether this patch is still useful. In
case it is, I will definitely address your suggestions.

-Xin

[brzycki]

Hi @trentxintong , did you decide if this patch was useful?

lib/Transforms/Scalar/JumpThreading.cpp

for (const auto &PredValue : PredValues) {
     BasicBlock *Pred = PredValue.second;
     if (!SeenPreds.insert(Pred).second)
       continue;  // Duplicate predecessor entry.
 
     Constant *Val = PredValue.first;
 
     BasicBlock *DestBB;
     if (isa<UndefValue>(Val))
       DestBB = nullptr;
     else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
       assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
       DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
       assert(isa<ConstantInt>(Val) && "Expecting a constant integer");
       DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
     } else {
       assert(isa<IndirectBrInst>(BB->getTerminator())
               && "Unexpected terminator");
       assert(isa<BlockAddress>(Val) && "Expecting a constant blockaddress");
       DestBB = cast<BlockAddress>(Val)->getBasicBlock();
     }
 
     // If we have exactly one destination, remember it for efficiency below.
+    // and we can ignore null destination.
+    if (DestBB) {
       if (PredToDestList.empty()) {
         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.
+        // It possible we have same destination, but different value, e.g.
+        // default case in switchinst.
         if (Val != OnlyVal)
           OnlyVal = MultipleVal;
       }
+    }
 
     // We know where this predecessor is going.
     ++PredWithKnownDest;
 
     // If the predecessor ends with an indirect goto, we can't change its
     // destination.
     if (isa<IndirectBrInst>(Pred->getTerminator()))
       continue;
 
     PredToDestList.push_back(std::make_pair(Pred, DestBB));
   }
 
   // If all edges were unthreadable, we fail.
   if (PredToDestList.empty())
     return false;
 
   // If all the predecessors go to a single known successor, we want to fold,
   // not thread. By doing so, we do not need to duplicate the current block and
   // also miss potential opportunities in case we dont/cant duplicate.
   if (OnlyDest && OnlyDest != MultipleDestSentinel) {
     if (PredWithKnownDest == (size_t)pred_size(BB)) {
       bool SeenFirstBranchToOnlyDest = false;
       std::vector <DominatorTree::UpdateType> Updates;
       Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
       for (BasicBlock *SuccBB : successors(BB)) {
         if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
         } else {

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

 L2:
   call void @f3()
   ret void
 
 L3:
   call void @f3()
   ret void
 }
+
+; Make sure we can fold this branch ... We will not be able to thread it as
+; L0 is too big to duplicate. LX is the unreachable block here, and it feeds
+; UNDEF to L2. We want to make sure the UNDEF does not make jump threading think
+; L2 has multiple destinations. 
+; CHECK-LABEL: @test_br_folding_not_threading_multiple_preds_with_undef(
+; CHECK: L3:
+; CHECK: call i32 @f2()
+; CHECK: call void @f3()
+; CHECK-NEXT: ret void
+define void @test_br_folding_not_threading_multiple_preds_with_undef(i1 %condx, i1 %cond) nounwind {
+L0:
+  br i1 %condx, label %L2, label %L1
+
+L1:
+  br i1 %cond, label %L2, label %L5
+
+LX:
+  br label %L2
+
+L2:
+  %p = phi i1 [ %condx, %L0 ], [ %cond, %L1 ], [ undef, %LX]
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  call i32 @f2()
+  br i1 %p, label %L3, label %L4
+
+L3:
+  call void @f3()
+  ret void
+L4:
+  call void @f3()
+  ret void
+L5:
+  call void @f3()
+  ret void
+}