347 lines · cpp
1//===- ControlFlowUtils.cpp - Control Flow Utilities -----------------------==//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Utilities to manipulate the CFG and restore SSA for the new control flow.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Transforms/Utils/ControlFlowUtils.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/Analysis/DomTreeUpdater.h"16#include "llvm/Analysis/LoopInfo.h"17#include "llvm/IR/Constants.h"18#include "llvm/IR/Instructions.h"19#include "llvm/IR/ValueHandle.h"20#include "llvm/Transforms/Utils/Local.h"21 22#define DEBUG_TYPE "control-flow-hub"23 24using namespace llvm;25 26using BBPredicates = DenseMap<BasicBlock *, Instruction *>;27using EdgeDescriptor = ControlFlowHub::BranchDescriptor;28 29// Redirects the terminator of the incoming block to the first guard block in30// the hub. Returns the branch condition from `BB` if it exits.31// - If only one of Succ0 or Succ1 is not null, the corresponding branch32// successor is redirected to the FirstGuardBlock.33// - Else both are not null, and branch is replaced with an unconditional34// branch to the FirstGuardBlock.35static Value *redirectToHub(BasicBlock *BB, BasicBlock *Succ0,36 BasicBlock *Succ1, BasicBlock *FirstGuardBlock) {37 assert(isa<BranchInst>(BB->getTerminator()) &&38 "Only support branch terminator.");39 auto *Branch = cast<BranchInst>(BB->getTerminator());40 auto *Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;41 42 assert(Succ0 || Succ1);43 44 if (Branch->isUnconditional()) {45 assert(Succ0 == Branch->getSuccessor(0));46 assert(!Succ1);47 Branch->setSuccessor(0, FirstGuardBlock);48 } else {49 assert(!Succ1 || Succ1 == Branch->getSuccessor(1));50 if (Succ0 && !Succ1) {51 Branch->setSuccessor(0, FirstGuardBlock);52 } else if (Succ1 && !Succ0) {53 Branch->setSuccessor(1, FirstGuardBlock);54 } else {55 Branch->eraseFromParent();56 BranchInst::Create(FirstGuardBlock, BB);57 }58 }59 60 return Condition;61}62 63// Setup the branch instructions for guard blocks.64//65// Each guard block terminates in a conditional branch that transfers66// control to the corresponding outgoing block or the next guard67// block. The last guard block has two outgoing blocks as successors.68static void setupBranchForGuard(ArrayRef<BasicBlock *> GuardBlocks,69 ArrayRef<BasicBlock *> Outgoing,70 BBPredicates &GuardPredicates) {71 assert(Outgoing.size() > 1);72 assert(GuardBlocks.size() == Outgoing.size() - 1);73 int I = 0;74 for (int E = GuardBlocks.size() - 1; I != E; ++I) {75 BasicBlock *Out = Outgoing[I];76 BranchInst::Create(Out, GuardBlocks[I + 1], GuardPredicates[Out],77 GuardBlocks[I]);78 }79 BasicBlock *Out = Outgoing[I];80 BranchInst::Create(Out, Outgoing[I + 1], GuardPredicates[Out],81 GuardBlocks[I]);82}83 84// Assign an index to each outgoing block. At the corresponding guard85// block, compute the branch condition by comparing this index.86static void calcPredicateUsingInteger(ArrayRef<EdgeDescriptor> Branches,87 ArrayRef<BasicBlock *> Outgoing,88 ArrayRef<BasicBlock *> GuardBlocks,89 BBPredicates &GuardPredicates) {90 LLVMContext &Context = GuardBlocks.front()->getContext();91 BasicBlock *FirstGuardBlock = GuardBlocks.front();92 Type *Int32Ty = Type::getInt32Ty(Context);93 94 auto *Phi = PHINode::Create(Int32Ty, Branches.size(), "merged.bb.idx",95 FirstGuardBlock);96 97 for (auto [BB, Succ0, Succ1] : Branches) {98 Value *Condition = redirectToHub(BB, Succ0, Succ1, FirstGuardBlock);99 Value *IncomingId = nullptr;100 if (Succ0 && Succ1) {101 auto Succ0Iter = find(Outgoing, Succ0);102 auto Succ1Iter = find(Outgoing, Succ1);103 Value *Id0 =104 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), Succ0Iter));105 Value *Id1 =106 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), Succ1Iter));107 IncomingId = SelectInst::Create(Condition, Id0, Id1, "target.bb.idx",108 BB->getTerminator()->getIterator());109 } else {110 // Get the index of the non-null successor.111 auto SuccIter = Succ0 ? find(Outgoing, Succ0) : find(Outgoing, Succ1);112 IncomingId =113 ConstantInt::get(Int32Ty, std::distance(Outgoing.begin(), SuccIter));114 }115 Phi->addIncoming(IncomingId, BB);116 }117 118 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {119 BasicBlock *Out = Outgoing[I];120 LLVM_DEBUG(dbgs() << "Creating integer guard for " << Out->getName()121 << "\n");122 auto *Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,123 ConstantInt::get(Int32Ty, I),124 Out->getName() + ".predicate", GuardBlocks[I]);125 GuardPredicates[Out] = Cmp;126 }127}128 129// Determine the branch condition to be used at each guard block from the130// original boolean values.131static void calcPredicateUsingBooleans(132 ArrayRef<EdgeDescriptor> Branches, ArrayRef<BasicBlock *> Outgoing,133 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates,134 SmallVectorImpl<WeakVH> &DeletionCandidates) {135 LLVMContext &Context = GuardBlocks.front()->getContext();136 auto *BoolTrue = ConstantInt::getTrue(Context);137 auto *BoolFalse = ConstantInt::getFalse(Context);138 BasicBlock *FirstGuardBlock = GuardBlocks.front();139 140 // The predicate for the last outgoing is trivially true, and so we141 // process only the first N-1 successors.142 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {143 BasicBlock *Out = Outgoing[I];144 LLVM_DEBUG(dbgs() << "Creating boolean guard for " << Out->getName()145 << "\n");146 147 auto *Phi =148 PHINode::Create(Type::getInt1Ty(Context), Branches.size(),149 StringRef("Guard.") + Out->getName(), FirstGuardBlock);150 GuardPredicates[Out] = Phi;151 }152 153 for (auto [BB, Succ0, Succ1] : Branches) {154 Value *Condition = redirectToHub(BB, Succ0, Succ1, FirstGuardBlock);155 156 // Optimization: Consider an incoming block A with both successors157 // Succ0 and Succ1 in the set of outgoing blocks. The predicates158 // for Succ0 and Succ1 complement each other. If Succ0 is visited159 // first in the loop below, control will branch to Succ0 using the160 // corresponding predicate. But if that branch is not taken, then161 // control must reach Succ1, which means that the incoming value of162 // the predicate from `BB` is true for Succ1.163 bool OneSuccessorDone = false;164 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I) {165 BasicBlock *Out = Outgoing[I];166 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);167 if (Out != Succ0 && Out != Succ1) {168 Phi->addIncoming(BoolFalse, BB);169 } else if (!Succ0 || !Succ1 || OneSuccessorDone) {170 // Optimization: When only one successor is an outgoing block,171 // the incoming predicate from `BB` is always true.172 Phi->addIncoming(BoolTrue, BB);173 } else {174 assert(Succ0 && Succ1);175 if (Out == Succ0) {176 Phi->addIncoming(Condition, BB);177 } else {178 Value *Inverted = invertCondition(Condition);179 DeletionCandidates.push_back(Condition);180 Phi->addIncoming(Inverted, BB);181 }182 OneSuccessorDone = true;183 }184 }185 }186}187 188// Capture the existing control flow as guard predicates, and redirect189// control flow from \p Incoming block through the \p GuardBlocks to the190// \p Outgoing blocks.191//192// There is one guard predicate for each outgoing block OutBB. The193// predicate represents whether the hub should transfer control flow194// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates195// them in the same order as the Outgoing set-vector, and control196// branches to the first outgoing block whose predicate evaluates to true.197//198// The last guard block has two outgoing blocks as successors since the199// condition for the final outgoing block is trivially true. So we create one200// less block (including the first guard block) than the number of outgoing201// blocks.202static void convertToGuardPredicates(203 ArrayRef<EdgeDescriptor> Branches, ArrayRef<BasicBlock *> Outgoing,204 SmallVectorImpl<BasicBlock *> &GuardBlocks,205 SmallVectorImpl<WeakVH> &DeletionCandidates, const StringRef Prefix,206 std::optional<unsigned> MaxControlFlowBooleans) {207 BBPredicates GuardPredicates;208 Function *F = Outgoing.front()->getParent();209 210 for (int I = 0, E = Outgoing.size() - 1; I != E; ++I)211 GuardBlocks.push_back(212 BasicBlock::Create(F->getContext(), Prefix + ".guard", F));213 214 // When we are using an integer to record which target block to jump to, we215 // are creating less live values, actually we are using one single integer to216 // store the index of the target block. When we are using booleans to store217 // the branching information, we need (N-1) boolean values, where N is the218 // number of outgoing block.219 if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans)220 calcPredicateUsingBooleans(Branches, Outgoing, GuardBlocks, GuardPredicates,221 DeletionCandidates);222 else223 calcPredicateUsingInteger(Branches, Outgoing, GuardBlocks, GuardPredicates);224 225 setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates);226}227 228// After creating a control flow hub, the operands of PHINodes in an outgoing229// block Out no longer match the predecessors of that block. Predecessors of Out230// that are incoming blocks to the hub are now replaced by just one edge from231// the hub. To match this new control flow, the corresponding values from each232// PHINode must now be moved a new PHINode in the first guard block of the hub.233//234// This operation cannot be performed with SSAUpdater, because it involves one235// new use: If the block Out is in the list of Incoming blocks, then the newly236// created PHI in the Hub will use itself along that edge from Out to Hub.237static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,238 ArrayRef<EdgeDescriptor> Incoming,239 BasicBlock *FirstGuardBlock) {240 auto I = Out->begin();241 while (I != Out->end() && isa<PHINode>(I)) {242 auto *Phi = cast<PHINode>(I);243 auto *NewPhi =244 PHINode::Create(Phi->getType(), Incoming.size(),245 Phi->getName() + ".moved", FirstGuardBlock->begin());246 bool AllUndef = true;247 for (auto [BB, Succ0, Succ1] : Incoming) {248 Value *V = PoisonValue::get(Phi->getType());249 if (Phi->getBasicBlockIndex(BB) != -1) {250 V = Phi->removeIncomingValue(BB, false);251 if (BB == Out) {252 V = NewPhi;253 }254 AllUndef &= isa<UndefValue>(V);255 }256 257 NewPhi->addIncoming(V, BB);258 }259 assert(NewPhi->getNumIncomingValues() == Incoming.size());260 Value *NewV = NewPhi;261 if (AllUndef) {262 NewPhi->eraseFromParent();263 NewV = PoisonValue::get(Phi->getType());264 }265 if (Phi->getNumOperands() == 0) {266 Phi->replaceAllUsesWith(NewV);267 I = Phi->eraseFromParent();268 continue;269 }270 Phi->addIncoming(NewV, GuardBlock);271 ++I;272 }273}274 275std::pair<BasicBlock *, bool> ControlFlowHub::finalize(276 DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,277 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) {278#ifndef NDEBUG279 SmallPtrSet<BasicBlock *, 8> Incoming;280#endif281 SetVector<BasicBlock *> Outgoing;282 283 for (auto [BB, Succ0, Succ1] : Branches) {284#ifndef NDEBUG285 assert(286 (Incoming.insert(BB).second || isa<CallBrInst>(BB->getTerminator())) &&287 "Duplicate entry for incoming block.");288#endif289 if (Succ0)290 Outgoing.insert(Succ0);291 if (Succ1)292 Outgoing.insert(Succ1);293 }294 295 if (Outgoing.size() < 2)296 return {Outgoing.front(), false};297 298 SmallVector<DominatorTree::UpdateType, 16> Updates;299 if (DTU) {300 for (auto [BB, Succ0, Succ1] : Branches) {301 if (Succ0)302 Updates.push_back({DominatorTree::Delete, BB, Succ0});303 if (Succ1)304 Updates.push_back({DominatorTree::Delete, BB, Succ1});305 }306 }307 308 SmallVector<WeakVH, 8> DeletionCandidates;309 convertToGuardPredicates(Branches, Outgoing.getArrayRef(), GuardBlocks,310 DeletionCandidates, Prefix, MaxControlFlowBooleans);311 BasicBlock *FirstGuardBlock = GuardBlocks.front();312 313 // Update the PHINodes in each outgoing block to match the new control flow.314 for (int I = 0, E = GuardBlocks.size(); I != E; ++I)315 reconnectPhis(Outgoing[I], GuardBlocks[I], Branches, FirstGuardBlock);316 // Process the Nth (last) outgoing block with the (N-1)th (last) guard block.317 reconnectPhis(Outgoing.back(), GuardBlocks.back(), Branches, FirstGuardBlock);318 319 if (DTU) {320 int NumGuards = GuardBlocks.size();321 322 for (auto [BB, Succ0, Succ1] : Branches)323 Updates.push_back({DominatorTree::Insert, BB, FirstGuardBlock});324 325 for (int I = 0; I != NumGuards - 1; ++I) {326 Updates.push_back({DominatorTree::Insert, GuardBlocks[I], Outgoing[I]});327 Updates.push_back(328 {DominatorTree::Insert, GuardBlocks[I], GuardBlocks[I + 1]});329 }330 // The second successor of the last guard block is an outgoing block instead331 // of having a "next" guard block.332 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],333 Outgoing[NumGuards - 1]});334 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],335 Outgoing[NumGuards]});336 DTU->applyUpdates(Updates);337 }338 339 for (auto I : DeletionCandidates) {340 if (I->use_empty())341 if (auto *Inst = dyn_cast_or_null<Instruction>(I))342 Inst->eraseFromParent();343 }344 345 return {FirstGuardBlock, true};346}347