diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -1630,6 +1630,8 @@ static std::tuple redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing) { + assert(isa(BB->getTerminator()) && + "Only support branch terminator.\n"); auto Branch = cast(BB->getTerminator()); auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr; @@ -1657,31 +1659,62 @@ assert(Succ0 || Succ1); return std::make_tuple(Condition, Succ0, Succ1); } +// Setup the branch instructions for guard blocks. +// +// Each guard block terminates in a conditional branch that transfers +// control to the corresponding outgoing block or the next guard +// block. The last guard block has two outgoing blocks as successors +// since the condition for the final outgoing block is trivially +static void setupBranchForGuard(SmallVectorImpl &GuardBlocks, + const BBSetVector &Outgoing, + BBPredicates &GuardPredicates) { + // To help keep the loop simple, temporarily append the last + // outgoing block to the list of guard blocks. + GuardBlocks.push_back(Outgoing.back()); + + for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) { + auto Out = Outgoing[i]; + assert(GuardPredicates.count(Out)); + BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out], + GuardBlocks[i]); + } + + // Remove the last block from the guard list. + GuardBlocks.pop_back(); +} // Capture the existing control flow as guard predicates, and redirect -// control flow from every incoming block to the first guard block in -// the hub. +// control flow from \p Incoming block through the \p GuardBlocks to the +// \p Outgoing blocks. // // There is one guard predicate for each outgoing block OutBB. The -// predicate is a PHINode with one input for each InBB which -// represents whether the hub should transfer control flow to OutBB if -// it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub -// evaluates them in the same order as the Outgoing set-vector, and -// control branches to the first outgoing block whose predicate -// evaluates to true. -static void convertToGuardPredicates( - BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, - SmallVectorImpl &DeletionCandidates, const BBSetVector &Incoming, - const BBSetVector &Outgoing) { +// predicate represents whether the hub should transfer control flow +// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates +// them in the same order as the Outgoing set-vector, and control +// branches to the first outgoing block whose predicate evaluates to true. +static void +convertToGuardPredicates(SmallVectorImpl &GuardBlocks, + SmallVectorImpl &DeletionCandidates, + const BBSetVector &Incoming, + const BBSetVector &Outgoing, const StringRef Prefix) { + BBPredicates GuardPredicates; + auto F = Incoming.front()->getParent(); auto &Context = Incoming.front()->getContext(); auto BoolTrue = ConstantInt::getTrue(Context); auto BoolFalse = ConstantInt::getFalse(Context); + for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) + GuardBlocks.push_back( + BasicBlock::Create(F->getContext(), Prefix + ".guard", F)); + + auto FirstGuardBlock = GuardBlocks.front(); + // The predicate for the last outgoing is trivially true, and so we // process only the first N-1 successors. for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n"); + auto Phi = PHINode::Create(Type::getInt1Ty(Context), Incoming.size(), StringRef("Guard.") + Out->getName(), FirstGuardBlock); @@ -1700,105 +1733,70 @@ // for Succ0 and Succ1 complement each other. If Succ0 is visited // first in the loop below, control will branch to Succ0 using the // corresponding predicate. But if that branch is not taken, then - // control must reach Succ1, which means that the predicate for - // Succ1 is always true. + // control must reach Succ1, which means that the incoming value of + // the predicate from `In` is true for Succ1. bool OneSuccessorDone = false; for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { auto Out = Outgoing[i]; auto Phi = GuardPredicates[Out]; if (Out != Succ0 && Out != Succ1) { Phi->addIncoming(BoolFalse, In); - continue; - } - // Optimization: When only one successor is an outgoing block, - // the predicate is always true. - if (!Succ0 || !Succ1 || OneSuccessorDone) { + } else if (!Succ0 || !Succ1 || OneSuccessorDone) { + // Optimization: When only one successor is an outgoing block, + // the incoming predicate from `In` is always true. Phi->addIncoming(BoolTrue, In); - continue; - } - assert(Succ0 && Succ1); - OneSuccessorDone = true; - if (Out == Succ0) { - Phi->addIncoming(Condition, In); - continue; + } else { + assert(Succ0 && Succ1); + if (Out == Succ0) { + Phi->addIncoming(Condition, In); + } else { + auto Inverted = invertCondition(Condition); + DeletionCandidates.push_back(Condition); + Phi->addIncoming(Inverted, In); + } + OneSuccessorDone = true; } - auto Inverted = invertCondition(Condition); - DeletionCandidates.push_back(Condition); - Phi->addIncoming(Inverted, In); } } -} -// For each outgoing block OutBB, create a guard block in the Hub. The -// first guard block was already created outside, and available as the -// first element in the vector of guard blocks. -// -// Each guard block terminates in a conditional branch that transfers -// control to the corresponding outgoing block or the next guard -// block. The last guard block has two outgoing blocks as successors -// since the condition for the final outgoing block is trivially -// true. So we create one less block (including the first guard block) -// than the number of outgoing blocks. -static void createGuardBlocks(SmallVectorImpl &GuardBlocks, - Function *F, const BBSetVector &Outgoing, - BBPredicates &GuardPredicates, StringRef Prefix) { - for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) { - GuardBlocks.push_back( - BasicBlock::Create(F->getContext(), Prefix + ".guard", F)); - } - assert(GuardBlocks.size() == GuardPredicates.size()); - - // To help keep the loop simple, temporarily append the last - // outgoing block to the list of guard blocks. - GuardBlocks.push_back(Outgoing.back()); - - for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) { - auto Out = Outgoing[i]; - assert(GuardPredicates.count(Out)); - BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out], - GuardBlocks[i]); - } - - // Remove the last block from the guard list. - GuardBlocks.pop_back(); + setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates); } BasicBlock *llvm::CreateControlFlowHub( DomTreeUpdater *DTU, SmallVectorImpl &GuardBlocks, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix) { - auto F = Incoming.front()->getParent(); - auto FirstGuardBlock = - BasicBlock::Create(F->getContext(), Prefix + ".guard", F); + if (Outgoing.size() < 2) + return Outgoing.front(); SmallVector Updates; if (DTU) { for (auto In : Incoming) { - Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock}); - for (auto Succ : successors(In)) { + for (auto Succ : successors(In)) if (Outgoing.count(Succ)) Updates.push_back({DominatorTree::Delete, In, Succ}); - } } } - BBPredicates GuardPredicates; SmallVector DeletionCandidates; - convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates, - Incoming, Outgoing); + convertToGuardPredicates(GuardBlocks, DeletionCandidates, Incoming, Outgoing, + Prefix); - GuardBlocks.push_back(FirstGuardBlock); - createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix); + auto FirstGuardBlock = GuardBlocks.front(); // Update the PHINodes in each outgoing block to match the new control flow. - for (int i = 0, e = GuardBlocks.size(); i != e; ++i) { + for (int i = 0, e = GuardBlocks.size(); i != e; ++i) reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock); - } + reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock); if (DTU) { int NumGuards = GuardBlocks.size(); assert((int)Outgoing.size() == NumGuards + 1); + + for (auto In : Incoming) + Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock}); + for (int i = 0; i != NumGuards - 1; ++i) { Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]}); Updates.push_back(