[JumpThread] We want to fold (not thread) when all predecessor go to single BB's successor. .

[trentxintong]

Summary

In case all predecessor go to a single successor of current BB. We want to fold (not thread).

[majnemer]

lib/Transforms/Scalar/JumpThreading.cpp

1297

I'd use size_t instead of unsigned here.

1298

This can be successors(BB)

1312

This can be auto *CondInst

[• dberlin]

lib/Transforms/Scalar/JumpThreading.cpp

1297

If you are going to check predecessors a bunch, please use the prediteratorcache to cache the size.
This is not a cheap operation.

[trentxintong]

lib/Transforms/Scalar/JumpThreading.cpp

1297

I think thats a good suggestion. There are a few places we get the predecessors of the block currently being processed, we could use a PredIterCache for them. But I prefer to put it in as another commit.

[trentxintong]

Address comments.

[trentxintong]

Gentle Ping.

lib/Transforms/Scalar/JumpThreading.cpp

1297

dberlin is doing experiment about preditercache. I will rewrite this part if needed when that is done in another commit.

[trentxintong]

Update comments and change how predecessors with known successor is computed.

[trentxintong]

Ping ...

[trentxintong]

PING ?

[trentxintong]

Update comment

[trentxintong]

PING 4X

[trentxintong]

Ping ...

[sanjoy]

Comments inline.

lib/Transforms/Scalar/JumpThreading.cpp

1289

This logic looks like it isn't tested?

In any case, I'd suggest not putting it in this first patch, but doing it as an improvement on the fold-instead-of-threading logic.

test/Transforms/JumpThreading/basic.ll

21

Can you please add a test case with multiple preds of L0?

[trentxintong]

Address sanjoy's comments

[trentxintong]

Remove PredWithKnownSuccessor. its not really needed.

[sanjoy]

lgtm with nits

lib/Transforms/Scalar/JumpThreading.cpp

1294

s/dont/don't
s/cant/can't

1299

In this case, it may be cleaner to write the loop as:

for (BasicBlock *SuccBB : successors(BB))
  if (SuccBB != OnlyDest)
    SuccBB->removePredecessor(BB, true);  // Unreachable successor

[trentxintong]

Address comments.

lib/Transforms/Scalar/JumpThreading.cpp

if (PredToDestList.empty())
       OnlyDest = DestBB;
     else if (OnlyDest != DestBB)
       OnlyDest = MultipleDestSentinel;
 
     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 (PredToDestList.size() ==
+        (size_t)std::distance(pred_begin(BB), pred_end(BB))) {
+      for (BasicBlock *SuccBB : successors(BB)) {
+        if (SuccBB == OnlyDest)
+          continue;
+        // This is unreachable successor.
+        SuccBB->removePredecessor(BB, true);
+      }
+
+      // 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.
+      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.
   BasicBlock *MostPopularDest = OnlyDest;
 
   if (MostPopularDest == MultipleDestSentinel)
     MostPopularDest = FindMostPopularDest(BB, PredToDestList);

test/Transforms/JumpThreading/basic.ll

 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 
 declare i32 @f1()
 declare i32 @f2()
 declare void @f3()
 
+; Make sure we can fold this branch ... We will not be able to thread it as
+; L0 is too big to duplicate. L2 is the unreachable block here.
+;
+; CHECK-LABEL: @test_br_folding_not_threading(
+; CHECK: L1:
+; CHECK: call i32 @f2()
+; CHECK: call void @f3()
+; CHECK-NEXT: ret void
+; CHECK-NOT: br
+; CHECK: L3:
+define void @test_br_folding_not_threading(i1 %cond) nounwind {
+entry:
+  br i1 %cond, label %L0, label %L3 
+L0:
+  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 %cond, label %L1, label %L2 
+
+L1:
+  call void @f3()
+  ret void
+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. L2 is the unreachable block here.
+; With more than 1 predecessors.
+;
+; CHECK-LABEL: @test_br_folding_not_threading_multiple_preds(
+; CHECK: L1:
+; CHECK: call i32 @f2()
+; CHECK: call void @f3()
+; CHECK-NEXT: ret void
+; CHECK-NOT: br
+; CHECK: L3:
+define void @test_br_folding_not_threading_multiple_preds(i1 %condx, i1 %cond) nounwind {
+entry:
+  br i1 %condx, label %X0, label %X1
+
+X0:
+  br i1 %cond, label %L0, label %L3 
+
+X1:
+  br i1 %cond, label %L0, label %L3 
+
+L0:
+  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 %cond, label %L1, label %L2 
+
+L1:
+  call void @f3()
+  ret void
+L2:
+  call void @f3()
+  ret void
+L3:
+  call void @f3()
+  ret void
+}
+
 define i32 @test1(i1 %cond) {
 ; CHECK-LABEL: @test1(
 
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge