Clone block with icmp+branch if it likely results in further jump threading

[eraman]

Summary

If we have a block (B1) with an otherwise-unthreadable branch on a compare, and its predecessors are terminated by an unconditional jump, try cloning it to a predecessor (B2) if B1 has a successor B3 which is terminated by a branch whose condition is known in B2. The cloning would result in an edge B2->B3 which could be potentially threaded with the branch that terminates B3.

Part of this patch deals with renaming and refactoring DuplicateCondBranchOnPHIIntoPred and ProcessBranchOnPHI so that they can be reused to clone in this case.

[mcrosier]

lib/Transforms/Scalar/JumpThreading.cpp

897

This should be a cast, rather than a dyn_cast.

902

dyn_cast -> cast.

903

dyn_cast -> cast.

1322

ends -> end

test/Transforms/JumpThreading/basic.ll

182

Please remove the extra whitespace.

[eraman]

Address review feedback.

[eraman]

Ping

[eraman]

Ping.

[haicheng]

Hi Easwaran,

Please see the inlined comment.

Haicheng

lib/Transforms/Scalar/JumpThreading.cpp

906–907

If I understand it correctly, the predecessor that TryDuplicatePredsWithUncondBranch() finds is the first predecessor that has an unconditional branch. It may not be Pred here which can provide a constant condition.

[eraman]

Thanks for the comments!

lib/Transforms/Scalar/JumpThreading.cpp

906–907

Yes. I have fixed it by calling DuplicateBBIntoPreds directly with the right Pred.

[eraman]

Address Haicheng's comments.

[haicheng]

lib/Transforms/Scalar/JumpThreading.cpp

873

Do you still need to change ProcessBranchOnPHI()?

[eraman]

Leave ProcessBranchOnPHI untouched.

[haicheng]

A few more inline comments.

lib/Transforms/Scalar/JumpThreading.cpp

900

What about renaming Cond as SuccCond?

test/Transforms/JumpThreading/basic.ll

116–117

Do you need to change this test case? It seems %v1 is still the first IR of block T1 after your patch.

198

What about changing f1 to a different name to distinguish from the call in BB2?

[reames]

lib/Transforms/Scalar/JumpThreading.cpp

885

This comments needs clarified. I was going to do a quick drive by style review, but after reading this three times, I'm not clear what you're trying to do. That's a pretty good sign the comment needs adjusted. :)

I think you've mainly got a grammar problem; this reads as one long run on sentence which is hard to parse.

[eraman]

lib/Transforms/Scalar/JumpThreading.cpp

885

I've rewritten the comment. Let me know if this makes better sense.

test/Transforms/JumpThreading/basic.ll

116–117

It's not needed now. I've reverted the change.

[eraman]

Address review comments and rebase.

[haicheng]

Hi Easwaran,

My understanding is that your change requires duplicating 2 basic blocks (BB and Succ) to thread over a block. The normal cases in JumpThreading only need to duplicate 1 block. Would you mind sharing some performance data if possible?

Other than this, I don't have more comments. Maybe @mcrosier or @reames has more things to comment.

Haicheng

[davidxl]

lib/Transforms/Scalar/JumpThreading.cpp

890

Why is the Cmp->getParent() check needed?

902

is Checking the parent BB too restrictive here?

[sebpop]

I like the idea that this patch is trying to address.

In GCC one can jump-thread across several BBs, whereas this patch "hard-codes" the pattern-matching to only 2 BBs.
It would be good to extend this patch to add a flag that selects the max path length to be jump-threaded.
Then we would need some performance analysis to select a good default for that flag.

The idea is to perform the analysis backwards: one starts from a condition and walk back on the SSA to the definitions involved in that condition.
If on one of the paths the condition can be statically evaluated, then that path is duplicated, the condition is removed, and the final jump is to the destination evaluated at compile time.

This algorithm in turn can be extended to jump-thread across back-edges in loops: that gives about 30% speedup on Coremark, and of course that pattern is present in parsers that implement Finite State Machines (FSM) a loop containing a switch statement, and each case sets the value for the next switch condition in the next iteration. One other example hit by GCC's jump-threading is in libART.

The cost function for code duplication has to be adjusted to account for the full length of the path to be duplicated:
the code in DuplicateBBIntoPreds() evaluates the size of only one BB to be duplicated based on this flag:

static cl::opt<unsigned>
BBDuplicateThreshold("jump-threading-threshold",
        cl::desc("Max block size to duplicate for jump threading"),
        cl::init(6), cl::Hidden);

Now that we copy two BBs their length will be evaluated separately.
I think we need another flag that evaluates the length of the full path to be duplicated.

include/llvm/Transforms/Scalar/JumpThreading.h

112

I see that the other functions in this file do not follow the convention:
now that you are changing the name of this function, please make it start with lower-case.

[haicheng]

In D22779#574260, @sebpop wrote:

The idea is to perform the analysis backwards: one starts from a condition and walk back on the SSA to the definitions involved in that condition.
If on one of the paths the condition can be statically evaluated, then that path is duplicated, the condition is removed, and the final jump is to the destination evaluated at compile time.

Maybe, JumpThreadingPass::ComputeValueKnownInPredecessors() can be refactored to do the backward analysis.

include/llvm/Transforms/Scalar/JumpThreading.h

void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }
 
   void FindLoopHeaders(Function &F);
   bool ProcessBlock(BasicBlock *BB);
   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
                   BasicBlock *SuccBB);
-  bool DuplicateCondBranchOnPHIIntoPred(
-      BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
+  bool DuplicateBBIntoPreds(BasicBlock *BB,
+                            const SmallVectorImpl<BasicBlock *> &PredBBs);
 
   bool
   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
                                   jumpthreading::PredValueInfo &Result,
                                   jumpthreading::ConstantPreference Preference,
                                   Instruction *CxtI = nullptr);
   bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                               jumpthreading::ConstantPreference Preference,

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
   if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator))
     return true;
 
   // If this is an otherwise-unfoldable branch on a phi node in the current
   // block, see if we can simplify.
   if (PHINode *PN = dyn_cast<PHINode>(CondInst))
     if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
       return ProcessBranchOnPHI(PN);
 
 
   // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
   if (CondInst->getOpcode() == Instruction::Xor &&
       CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
     return ProcessBranchOnXOR(cast<BinaryOperator>(CondInst));
 
   // Search for a stronger dominating condition that can be used to simplify a
   // conditional branch leaving BB.
   if (ProcessImpliedCondition(BB))
     return true;
 
+  // If this is an otherwise-unthreadable conditional branch on a compare,
+  // duplicate this into its predecessor under the following condition: the
+  // branch condition in a *successor to BB* can be inferred as a constant
+  // after the duplication.
+  if (CmpInst *Cmp = dyn_cast<CmpInst>(CondInst)) {
+    if (Cmp->getParent() != BB || !isa<BranchInst>(BB->getTerminator()))
+      return false;
+    for (auto *Succ : successors(BB)) {
+      if (Succ->getSinglePredecessor() != BB)
+        continue;
+      if (!isa<BranchInst>(Succ->getTerminator()))
+        continue;
+      BranchInst *SuccBranch = cast<BranchInst>(Succ->getTerminator());
+      if (!SuccBranch->isConditional())
+        continue;
+      Value *SuccCond = SuccBranch->getCondition();
+      if (!isa<Instruction>(SuccCond) ||
+          cast<Instruction>(SuccCond)->getParent() == Succ ||
+          cast<Instruction>(SuccCond)->getParent() == BB)
+        continue;
+      for (auto *Pred : predecessors(BB)) {
+        BranchInst *PredBr;
+        if ((PredBr = dyn_cast<BranchInst>(Pred->getTerminator())) &&
+            PredBr->isUnconditional() &&
+            LVI->getConstantOnEdge(SuccCond, Pred, BB) &&
+            DuplicateBBIntoPreds(BB, SmallVector<BasicBlock *, 1>({Pred})))
+          return true;
+      }
+    }
+  }
+
   return false;
 }
 
 bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
   auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
   return ThreadEdge(BB, PredsToFactor, MostPopularDest);
 }
 
 /// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on
 /// a PHI node in the current block.  See if there are any simplifications we
 /// can do based on inputs to the phi node.
 ///
 bool JumpThreadingPass::ProcessBranchOnPHI(PHINode *PN) {
   BasicBlock *BB = PN->getParent();
 
   // TODO: We could make use of this to do it once for blocks with common PHI
   // values.
   SmallVector<BasicBlock*, 1> PredBBs;
   PredBBs.resize(1);
 
   // If any of the predecessor blocks end in an unconditional branch, we can
   // *duplicate* the conditional branch into that block in order to further
   // encourage jump threading and to eliminate cases where we have branch on a
   // phi of an icmp (branch on icmp is much better).
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     BasicBlock *PredBB = PN->getIncomingBlock(i);
     if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
       if (PredBr->isUnconditional()) {
         PredBBs[0] = PredBB;
         // Try to duplicate BB into PredBB.
-        if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs))
+        if (DuplicateBBIntoPreds(BB, PredBBs))
           return true;
       }
   }
 
   return false;
 }
 
 /// ProcessBranchOnXOR - We have an otherwise unthreadable conditional branch on
if (!SplitVal) {
       // If all preds provide 1, set the computed value to 1.
       BO->setOperand(!isLHS, SplitVal);
     }
 
     return true;
   }
 
   // Try to duplicate BB into PredBB.
-  return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
+  return DuplicateBBIntoPreds(BB, BlocksToFoldInto);
 }
 
 
 /// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
 /// predecessor to the PHIBB block.  If it has PHI nodes, add entries for
 /// NewPred using the entries from OldPred (suitably mapped).
 static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB,
                                             BasicBlock *OldPred,
if (BBSuccProbs.size() >= 2) {
 
     auto TI = BB->getTerminator();
     TI->setMetadata(
         LLVMContext::MD_prof,
         MDBuilder(TI->getParent()->getContext()).createBranchWeights(Weights));
   }
 }
 
-/// DuplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
-/// to BB which contains an i1 PHI node and a conditional branch on that PHI.
-/// If we can duplicate the contents of BB up into PredBB do so now, this
-/// improves the odds that the branch will be on an analyzable instruction like
-/// a compare.
-bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
+/// DuplicateBBIntoPreds - PredBBs is a list of blocks that contain an
+/// unconditional branch to BB. Duplicate the contents of BB into Preds if the
+/// duplication cost is within the threshold.
+bool JumpThreadingPass::DuplicateBBIntoPreds(
     BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs) {
   assert(!PredBBs.empty() && "Can't handle an empty set");
 
   // If BB is a loop header, then duplicating this block outside the loop would
   // cause us to transform this into an irreducible loop, don't do this.
   // See the comments above FindLoopHeaders for justifications and caveats.
   if (LoopHeaders.count(BB)) {
     DEBUG(dbgs() << "  Not duplicating loop header '" << BB->getName()
else {
     DEBUG(dbgs() << "  Factoring out " << PredBBs.size()
           << " common predecessors.\n");
     PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
   }
 
   // Okay, we decided to do this!  Clone all the instructions in BB onto the end
   // of PredBB.
   DEBUG(dbgs() << "  Duplicating block '" << BB->getName() << "' into end of '"
-        << PredBB->getName() << "' to eliminate branch on phi.  Cost: "
-        << DuplicationCost << " block is:" << *BB << "\n");
+               << PredBB->getName() << "'.  Cost: " << DuplicationCost
+               << " block is:" << *BB << "\n");
 
   // Unless PredBB ends with an unconditional branch, split the edge so that we
   // can just clone the bits from BB into the end of the new PredBB.
   BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
 
   if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
     PredBB = SplitEdge(PredBB, BB);
     OldPredBranch = cast<BranchInst>(PredBB->getTerminator());

test/Transforms/JumpThreading/basic.ll

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

 
 
 ;; This tests that the branch in 'merge' can be cloned up into T1.
 define i32 @test5(i1 %cond, i1 %cond2) {
 ; CHECK-LABEL: @test5(
 
   br i1 %cond, label %T1, label %F1
 
 T1:
 ; CHECK: T1:
 ; CHECK-NEXT:   %v1 = call i32 @f1()
 ; CHECK-NEXT:   %cond3 = icmp eq i32 %v1, 412
 ; CHECK-NEXT:   br i1 %cond3, label %T2, label %F2
 
   %v1 = call i32 @f1()
         %cond3 = icmp eq i32 %v1, 412
   br label %Merge
 
call i32 @f2()
         ret i32 3
 
 BB4:
   call void @f3()
   ret i32 4
 }
 
 
+;; Clone a block if any of its successor ends with a conditional branch whose
+;; condition is known at a predecessor.
+
+
+define i32 @test6a(i32 %A, i32 %B) {
+; CHECK-LABEL: @test6a(
+  %tmp455 = icmp eq i32 %A, 42
+  br i1 %tmp455, label %BB5, label %BB2
+
+BB2:
+  call i32 @f1()
+  br label %BB11
+
+BB5:
+; One of BB11's successor is BB1 which ends with a conditional branch. The
+; condition used is %tmp455 whose value is known here. So BB11 is cloned here.
+; CHECK: call void @f4()
+; CHECK-NEXT: icmp eq i32 %B
+  call void @f4()
+  br label %BB11
+
+BB11:
+  %tmp5 = icmp eq i32 %B, 42
+  br i1 %tmp5, label %BB1, label %BB3
+
+BB1:
+  call i32 @f2()
+  br i1 %tmp455, label %BB3, label %BB4
+
+BB3:
+        ret i32 3
+
+BB4:
+  call void @f3()
+  ret i32 4
+}
+
+
 ;; This tests that the branch in 'merge' can be cloned up into T1.
 ;; rdar://7367025
 define i32 @test7(i1 %cond, i1 %cond2) {
 Entry:
 ; CHECK-LABEL: @test7(
   %v1 = call i32 @f1()
   br i1 %cond, label %Merge, label %F1