Index: include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- include/llvm/Transforms/Scalar/JumpThreading.h +++ include/llvm/Transforms/Scalar/JumpThreading.h @@ -109,8 +109,8 @@ bool ProcessBlock(BasicBlock *BB); bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl &PredBBs, BasicBlock *SuccBB); - bool DuplicateCondBranchOnPHIIntoPred( - BasicBlock *BB, const SmallVectorImpl &PredBBs); + bool DuplicateBBIIntoPreds(BasicBlock *BB, + const SmallVectorImpl &PredBBs); bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, @@ -121,7 +121,7 @@ jumpthreading::ConstantPreference Preference, Instruction *CxtI = nullptr); - bool ProcessBranchOnPHI(PHINode *PN); + bool TryDuplicatePredsWithUncondBranch(BasicBlock *BB); bool ProcessBranchOnXOR(BinaryOperator *BO); bool ProcessImpliedCondition(BasicBlock *BB); Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -860,12 +860,14 @@ 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. + // We have an otherwise-unthreadable conditional branch on a PHI node in the + // current block. Try duplicate the contents into a predecessor that ends + // with an unconditional branch to improve the odds that the branch will be an + // analyzable instruction. + if (PHINode *PN = dyn_cast(CondInst)) if (PN->getParent() == BB && isa(BB->getTerminator())) - return ProcessBranchOnPHI(PN); - + return TryDuplicatePredsWithUncondBranch(BB); // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify. if (CondInst->getOpcode() == Instruction::Xor && @@ -877,6 +879,34 @@ if (ProcessImpliedCondition(BB)) return true; + // If this is an otherwise-unthreadable conditional branch on a compare, + // duplicate this into its predecessor if that will result in the value of the + // branch condition in a *successor to BB* - which will become a successor to + // a ccurrently predecessor of BB after duplication - to be known. + if (CmpInst *Cmp = dyn_cast(CondInst)) { + if (Cmp->getParent() != BB || !isa(BB->getTerminator())) + return false; + for (auto *Succ : successors(BB)) { + if (Succ->getSinglePredecessor() != BB) + continue; + if (!isa(Succ->getTerminator())) + continue; + BranchInst *SuccBranch = dyn_cast(Succ->getTerminator()); + if (!SuccBranch->isConditional()) + continue; + Value *Cond = SuccBranch->getCondition(); + if (!isa(Cond) || + dyn_cast(Cond)->getParent() == Succ || + dyn_cast(Cond)->getParent() == BB) + continue; + for (auto *Pred : predecessors(BB)) { + if (LVI->getConstantOnEdge(Cond, Pred, BB) && + TryDuplicatePredsWithUncondBranch(BB)) + return true; + } + } + } + return false; } @@ -1271,29 +1301,22 @@ 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(); +/// If any of the predecessors of BB ends with an unconditional branch, +/// see if we can duplicate BB into its predecessors. BB is duplicated into +/// at most one predecessor. +bool JumpThreadingPass::TryDuplicatePredsWithUncondBranch(BasicBlock *BB) { // TODO: We could make use of this to do it once for blocks with common PHI // values. SmallVector 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); + for (auto *PredBB : predecessors(BB)) { if (BranchInst *PredBr = dyn_cast(PredBB->getTerminator())) if (PredBr->isUnconditional()) { PredBBs[0] = PredBB; // Try to duplicate BB into PredBB. - if (DuplicateCondBranchOnPHIIntoPred(BB, PredBBs)) + if (DuplicateBBIIntoPreds(BB, PredBBs)) return true; } } @@ -1402,7 +1425,7 @@ } // Try to duplicate BB into PredBB. - return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto); + return DuplicateBBIIntoPreds(BB, BlocksToFoldInto); } @@ -1670,12 +1693,10 @@ } } -/// 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( +/// DuplicateBBIIntoPreds - 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::DuplicateBBIIntoPreds( BasicBlock *BB, const SmallVectorImpl &PredBBs) { assert(!PredBBs.empty() && "Can't handle an empty set"); @@ -1709,8 +1730,8 @@ // 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. Index: test/Transforms/JumpThreading/basic.ll =================================================================== --- test/Transforms/JumpThreading/basic.ll +++ test/Transforms/JumpThreading/basic.ll @@ -106,15 +106,15 @@ } -;; This tests that the branch in 'merge' can be cloned up into T1. +;; This tests that the branch in 'Merge' can be cloned into a predecessor +;; and the other predecessor gets threaded with 'Merge' 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: %v1 = call i32 @f1() ; CHECK-NEXT: %cond3 = icmp eq i32 %v1, 412 ; CHECK-NEXT: br i1 %cond3, label %T2, label %F2 @@ -176,6 +176,44 @@ } +;; 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 i32 @f1() +; CHECK-NEXT: icmp eq i32 %B + call i32 @f1() + 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) {