Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -2540,6 +2540,13 @@ /// logical operations to pick the right destination. bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) { BasicBlock *BB = BI->getParent(); + dbgs() << "candidate: " << *BI << "\n"; + + if (pred_empty(BB)) + return false; + + // If we have a single predecessor, we can be slightly more general below + const BasicBlock *SinglePredBB = BB->getSinglePredecessor(); Instruction *Cond = nullptr; if (BI->isConditional()) @@ -2576,6 +2583,8 @@ Cond->getParent() != BB || !Cond->hasOneUse()) return false; + dbgs() << "here-1\n"; + // Make sure the instruction after the condition is the cond branch. BasicBlock::iterator CondIt = ++Cond->getIterator(); @@ -2586,6 +2595,7 @@ if (&*CondIt != BI) return false; + dbgs() << "here-2\n"; // Only allow this transformation if computing the condition doesn't involve // too many instructions and these involved instructions can be executed // unconditionally. We denote all involved instructions except the condition @@ -2593,15 +2603,24 @@ // number of the bonus instructions does not exceed a certain threshold. unsigned NumBonusInsts = 0; for (auto I = BB->begin(); Cond != &*I; ++I) { + dbgs() << *I << "\n"; // Ignore dbg intrinsics. if (isa(I)) continue; - if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I)) - return false; - // I has only one use and can be executed unconditionally. - Instruction *User = dyn_cast(I->user_back()); - if (User == nullptr || User->getParent() != BB) + dbgs() << I->hasOneUse() << " && " << isSafeToSpeculativelyExecute(&*I) << " \n"; + if (!isSafeToSpeculativelyExecute(&*I)) return false; + // If we have more than one predecessor, there's no single value with which + // to update out of block uses. + if (!SinglePredBB) { + if (!I->hasOneUse()) + return false; + // I has only one use and can be executed unconditionally. + Instruction *User = dyn_cast(I->user_back()); + if (User == nullptr || User->getParent() != BB) + return false; + } + dbgs() << *I << " (3)\n"; // I is used in the same BB. Since BI uses Cond and doesn't have more slots // to use any other instruction, User must be an instruction between next(I) // and Cond. @@ -2609,8 +2628,12 @@ // Early exits once we reach the limit. if (NumBonusInsts > BonusInstThreshold) return false; + dbgs() << *I << "(4)\n"; } + dbgs() << "here-3\n"; + + // Cond is known to be a compare or binary operator. Check to make sure that // neither operand is a potentially-trapping constant expression. if (ConstantExpr *CE = dyn_cast(Cond->getOperand(0))) @@ -2620,6 +2643,8 @@ if (CE->canTrap()) return false; + dbgs() << "here-4\n"; + // Finally, don't infinitely unroll conditional loops. BasicBlock *TrueDest = BI->getSuccessor(0); BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr; @@ -2630,6 +2655,9 @@ BasicBlock *PredBlock = *PI; BranchInst *PBI = dyn_cast(PredBlock->getTerminator()); + dbgs() << "PBI: " << *PBI << "\n"; + + // Check that we have two conditional branches. If there is a PHI node in // the common successor, verify that the same value flows in from both // blocks. @@ -2682,41 +2710,65 @@ PBI->swapSuccessors(); } - // If we have bonus instructions, clone them into the predecessor block. - // Note that there may be multiple predecessor blocks, so we cannot move - // bonus instructions to a predecessor block. - ValueToValueMapTy VMap; // maps original values to cloned values - // We already make sure Cond is the last instruction before BI. Therefore, - // all instructions before Cond other than DbgInfoIntrinsic are bonus - // instructions. - for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) { - if (isa(BonusInst)) - continue; - Instruction *NewBonusInst = BonusInst->clone(); - RemapInstruction(NewBonusInst, VMap, + Instruction *New = nullptr; + if (SinglePredBB) { + // For a single predeccessor we know we can a) move rather than clone and + // b) be sure any uses outside BB are themselves dominated by our single + // predecessor. + for (auto BonusInstItr = BB->begin(); Cond != &*BonusInstItr;) { + auto BonusInst = BonusInstItr; + BonusInstItr++; + if (isa(BonusInst)) + // Could move now, but sake of consistency, fall through to common + // code. + continue; + BonusInst->moveBefore(PBI); + + // Remove all potentially control dependent facts (TODO: could be more + // fine grained here) + BonusInst->dropUnknownNonDebugMetadata(); + } + // TODO: Not actually new, rename probably warranted. + New = Cond; + Cond->moveBefore(PBI); + } else { + // If we have bonus instructions, clone them into the predecessor block. + // Note that there may be multiple predecessor blocks, so we cannot move + // bonus instructions to a predecessor block. + ValueToValueMapTy VMap; // maps original values to cloned values + // We already make sure Cond is the last instruction before BI. Therefore, + // all instructions before Cond other than DbgInfoIntrinsic are bonus + // instructions. + for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) { + if (isa(BonusInst)) + continue; + Instruction *NewBonusInst = BonusInst->clone(); + RemapInstruction(NewBonusInst, VMap, + RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); + VMap[&*BonusInst] = NewBonusInst; + + // If we moved a load, we cannot any longer claim any knowledge about + // its potential value. The previous information might have been valid + // only given the branch precondition. + // For an analogous reason, we must also drop all the metadata whose + // semantics we don't understand. + NewBonusInst->dropUnknownNonDebugMetadata(); + + PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst); + NewBonusInst->takeName(&*BonusInst); + BonusInst->setName(BonusInst->getName() + ".old"); + } + + // Clone Cond into the predecessor basic block, and or/and the + // two conditions together. + New = Cond->clone(); + RemapInstruction(New, VMap, RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); - VMap[&*BonusInst] = NewBonusInst; - - // If we moved a load, we cannot any longer claim any knowledge about - // its potential value. The previous information might have been valid - // only given the branch precondition. - // For an analogous reason, we must also drop all the metadata whose - // semantics we don't understand. - NewBonusInst->dropUnknownNonDebugMetadata(); - - PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst); - NewBonusInst->takeName(&*BonusInst); - BonusInst->setName(BonusInst->getName() + ".old"); - } - - // Clone Cond into the predecessor basic block, and or/and the - // two conditions together. - Instruction *New = Cond->clone(); - RemapInstruction(New, VMap, - RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); - PredBlock->getInstList().insert(PBI->getIterator(), New); - New->takeName(Cond); - Cond->setName(New->getName() + ".old"); + PredBlock->getInstList().insert(PBI->getIterator(), New); + New->takeName(Cond); + Cond->setName(New->getName() + ".old"); + } + assert(New && "populated above!"); if (BI->isConditional()) { Instruction *NewCond = cast( @@ -2824,6 +2876,7 @@ if (isa(I)) I.clone()->insertBefore(PBI); + BB->getParent()->dump(); return true; } return false;