1 //===-- AMDGPUStructurizeCFG.cpp - ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// The pass implemented in this file transforms the programs control flow
12 /// graph into a form that's suitable for code generation on hardware that
13 /// implements control flow by execution masking. This currently includes all
14 /// AMD GPUs but may as well be useful for other types of hardware.
16 //===----------------------------------------------------------------------===//
19 #include "llvm/Module.h"
20 #include "llvm/ADT/SCCIterator.h"
21 #include "llvm/Analysis/RegionIterator.h"
22 #include "llvm/Analysis/RegionInfo.h"
23 #include "llvm/Analysis/RegionPass.h"
24 #include "llvm/Transforms/Utils/SSAUpdater.h"
30 // Definition of the complex types used in this pass.
32 typedef std::pair<BasicBlock *, Value *> BBValuePair;
33 typedef ArrayRef<BasicBlock*> BBVecRef;
35 typedef SmallVector<RegionNode*, 8> RNVector;
36 typedef SmallVector<BasicBlock*, 8> BBVector;
37 typedef SmallVector<BBValuePair, 2> BBValueVector;
39 typedef DenseMap<PHINode *, BBValueVector> PhiMap;
40 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
41 typedef DenseMap<BasicBlock *, Value *> BBPredicates;
42 typedef DenseMap<BasicBlock *, BBPredicates> PredMap;
43 typedef DenseMap<BasicBlock *, unsigned> VisitedMap;
45 // The name for newly created blocks.
47 static const char *FlowBlockName = "Flow";
49 /// @brief Transforms the control flow graph on one single entry/exit region
52 /// After the transform all "If"/"Then"/"Else" style control flow looks like
64 /// | | 1 = "If" block, calculates the condition
65 /// 4 | 2 = "Then" subregion, runs if the condition is true
66 /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
67 /// |/ 4 = "Else" optional subregion, runs if the condition is false
68 /// 5 5 = "End" block, also rejoins the control flow
71 /// Control flow is expressed as a branch where the true exit goes into the
72 /// "Then"/"Else" region, while the false exit skips the region
73 /// The condition for the optional "Else" region is expressed as a PHI node.
74 /// The incomming values of the PHI node are true for the "If" edge and false
75 /// for the "Then" edge.
77 /// Additionally to that even complicated loops look like this:
84 /// | / 1 = "Entry" block
85 /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block
86 /// 3 3 = "Flow" block, with back edge to entry block
90 /// The back edge of the "Flow" block is always on the false side of the branch
91 /// while the true side continues the general flow. So the loop condition
92 /// consist of a network of PHI nodes where the true incoming values expresses
93 /// breaks and the false values expresses continue states.
94 class AMDGPUStructurizeCFG : public RegionPass {
99 ConstantInt *BoolTrue;
100 ConstantInt *BoolFalse;
101 UndefValue *BoolUndef;
104 Region *ParentRegion;
111 BBPhiMap DeletedPhis;
112 BBVector FlowsInserted;
114 BasicBlock *LoopStart;
116 BBPredicates LoopPred;
120 void buildPredicate(BranchInst *Term, unsigned Idx,
121 BBPredicates &Pred, bool Invert);
123 void analyzeBlock(BasicBlock *BB);
125 void analyzeLoop(BasicBlock *BB, unsigned &LoopIdx);
129 bool dominatesPredicates(BasicBlock *A, BasicBlock *B);
131 void killTerminator(BasicBlock *BB);
133 RegionNode *skipChained(RegionNode *Node);
135 void delPhiValues(BasicBlock *From, BasicBlock *To);
137 void addPhiValues(BasicBlock *From, BasicBlock *To);
139 BasicBlock *getNextFlow(BasicBlock *Prev);
141 bool isPredictableTrue(BasicBlock *Prev, BasicBlock *Node);
143 BasicBlock *wireFlowBlock(BasicBlock *Prev, RegionNode *Node);
147 void insertConditions();
152 AMDGPUStructurizeCFG():
155 initializeRegionInfoPass(*PassRegistry::getPassRegistry());
158 virtual bool doInitialization(Region *R, RGPassManager &RGM);
160 virtual bool runOnRegion(Region *R, RGPassManager &RGM);
162 virtual const char *getPassName() const {
163 return "AMDGPU simplify control flow";
166 void getAnalysisUsage(AnalysisUsage &AU) const {
168 AU.addRequired<DominatorTree>();
169 AU.addPreserved<DominatorTree>();
170 RegionPass::getAnalysisUsage(AU);
175 } // end anonymous namespace
177 char AMDGPUStructurizeCFG::ID = 0;
179 /// \brief Initialize the types and constants used in the pass
180 bool AMDGPUStructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
182 LLVMContext &Context = R->getEntry()->getContext();
184 Boolean = Type::getInt1Ty(Context);
185 BoolTrue = ConstantInt::getTrue(Context);
186 BoolFalse = ConstantInt::getFalse(Context);
187 BoolUndef = UndefValue::get(Boolean);
192 /// \brief Build up the general order of nodes
193 void AMDGPUStructurizeCFG::orderNodes() {
195 scc_iterator<Region *> I = scc_begin(ParentRegion),
196 E = scc_end(ParentRegion);
197 for (Order.clear(); I != E; ++I) {
198 std::vector<RegionNode *> &Nodes = *I;
199 Order.append(Nodes.begin(), Nodes.end());
203 /// \brief Build blocks and loop predicates
204 void AMDGPUStructurizeCFG::buildPredicate(BranchInst *Term, unsigned Idx,
205 BBPredicates &Pred, bool Invert) {
207 Value *True = Invert ? BoolFalse : BoolTrue;
208 Value *False = Invert ? BoolTrue : BoolFalse;
210 RegionInfo *RI = ParentRegion->getRegionInfo();
211 BasicBlock *BB = Term->getParent();
213 // Handle the case where multiple regions start at the same block
214 Region *R = BB != ParentRegion->getEntry() ?
215 RI->getRegionFor(BB) : ParentRegion;
217 if (R == ParentRegion) {
218 // It's a top level block in our region
220 if (Term->isConditional()) {
221 BasicBlock *Other = Term->getSuccessor(!Idx);
223 if (Visited.count(Other)) {
224 if (!Pred.count(Other))
231 Cond = Term->getCondition();
234 Cond = BinaryOperator::CreateNot(Cond, "", Term);
239 } else if (ParentRegion->contains(R)) {
240 // It's a block in a sub region
241 while(R->getParent() != ParentRegion)
244 Pred[R->getEntry()] = True;
247 // It's a branch from outside into our parent region
252 /// \brief Analyze the successors of each block and build up predicates
253 void AMDGPUStructurizeCFG::analyzeBlock(BasicBlock *BB) {
255 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
256 BBPredicates &Pred = Predicates[BB];
258 for (; PI != PE; ++PI) {
259 BranchInst *Term = cast<BranchInst>((*PI)->getTerminator());
261 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
262 BasicBlock *Succ = Term->getSuccessor(i);
265 buildPredicate(Term, i, Pred, false);
270 /// \brief Analyze the conditions leading to loop to a previous block
271 void AMDGPUStructurizeCFG::analyzeLoop(BasicBlock *BB, unsigned &LoopIdx) {
273 BranchInst *Term = cast<BranchInst>(BB->getTerminator());
275 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
276 BasicBlock *Succ = Term->getSuccessor(i);
278 // Ignore it if it's not a back edge
279 if (!Visited.count(Succ))
282 buildPredicate(Term, i, LoopPred, true);
285 if (Visited[Succ] < LoopIdx) {
286 LoopIdx = Visited[Succ];
292 /// \brief Collect various loop and predicate infos
293 void AMDGPUStructurizeCFG::collectInfos() {
295 unsigned Number = 0, LoopIdx = ~0;
301 LoopStart = LoopEnd = 0;
304 RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend();
305 for (Visited.clear(); OI != OE; Visited[(*OI++)->getEntry()] = ++Number) {
307 // Analyze all the conditions leading to a node
308 analyzeBlock((*OI)->getEntry());
310 if ((*OI)->isSubRegion())
313 // Find the first/last loop nodes and loop predicates
314 analyzeLoop((*OI)->getNodeAs<BasicBlock>(), LoopIdx);
318 /// \brief Does A dominate all the predicates of B ?
319 bool AMDGPUStructurizeCFG::dominatesPredicates(BasicBlock *A, BasicBlock *B) {
321 BBPredicates &Preds = Predicates[B];
322 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
325 if (!DT->dominates(A, PI->first))
331 /// \brief Remove phi values from all successors and the remove the terminator.
332 void AMDGPUStructurizeCFG::killTerminator(BasicBlock *BB) {
334 TerminatorInst *Term = BB->getTerminator();
338 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
341 delPhiValues(BB, *SI);
344 Term->eraseFromParent();
347 /// First: Skip forward to the first region node that either isn't a subregion or not
348 /// dominating it's exit, remove all the skipped nodes from the node order.
350 /// Second: Handle the first successor directly if the resulting nodes successor
351 /// predicates are still dominated by the original entry
352 RegionNode *AMDGPUStructurizeCFG::skipChained(RegionNode *Node) {
354 BasicBlock *Entry = Node->getEntry();
356 // Skip forward as long as it is just a linear flow
358 BasicBlock *Entry = Node->getEntry();
361 if (Node->isSubRegion()) {
362 Exit = Node->getNodeAs<Region>()->getExit();
364 TerminatorInst *Term = Entry->getTerminator();
365 if (Term->getNumSuccessors() != 1)
367 Exit = Term->getSuccessor(0);
370 // It's a back edge, break here so we can insert a loop node
371 if (!Visited.count(Exit))
374 // More than node edges are pointing to exit
375 if (!DT->dominates(Entry, Exit))
378 RegionNode *Next = ParentRegion->getNode(Exit);
379 RNVector::iterator I = std::find(Order.begin(), Order.end(), Next);
380 assert(I != Order.end());
382 Visited.erase(Next->getEntry());
387 BasicBlock *BB = Node->getEntry();
388 TerminatorInst *Term = BB->getTerminator();
389 if (Term->getNumSuccessors() != 2)
392 // Our node has exactly two succesors, check if we can handle
393 // any of them directly
394 BasicBlock *Succ = Term->getSuccessor(0);
395 if (!Visited.count(Succ) || !dominatesPredicates(Entry, Succ)) {
396 Succ = Term->getSuccessor(1);
397 if (!Visited.count(Succ) || !dominatesPredicates(Entry, Succ))
400 BasicBlock *Succ2 = Term->getSuccessor(1);
401 if (Visited.count(Succ2) && Visited[Succ] > Visited[Succ2] &&
402 dominatesPredicates(Entry, Succ2))
406 RegionNode *Next = ParentRegion->getNode(Succ);
407 RNVector::iterator E = Order.end();
408 RNVector::iterator I = std::find(Order.begin(), E, Next);
412 FlowsInserted.push_back(BB);
415 return ParentRegion->getNode(wireFlowBlock(BB, Next));
418 /// \brief Remove all PHI values coming from "From" into "To" and remember
419 /// them in DeletedPhis
420 void AMDGPUStructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
422 PhiMap &Map = DeletedPhis[To];
423 for (BasicBlock::iterator I = To->begin(), E = To->end();
424 I != E && isa<PHINode>(*I);) {
426 PHINode &Phi = cast<PHINode>(*I++);
427 while (Phi.getBasicBlockIndex(From) != -1) {
428 Value *Deleted = Phi.removeIncomingValue(From, false);
429 Map[&Phi].push_back(std::make_pair(From, Deleted));
434 /// \brief Add the PHI values back once we knew the new predecessor
435 void AMDGPUStructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
437 if (!DeletedPhis.count(To))
440 PhiMap &Map = DeletedPhis[To];
443 for (PhiMap::iterator I = Map.begin(), E = Map.end(); I != E; ++I) {
445 PHINode *Phi = I->first;
446 Updater.Initialize(Phi->getType(), "");
447 BasicBlock *Fallback = To;
448 bool HaveFallback = false;
450 for (BBValueVector::iterator VI = I->second.begin(), VE = I->second.end();
453 Updater.AddAvailableValue(VI->first, VI->second);
454 BasicBlock *Dom = DT->findNearestCommonDominator(Fallback, VI->first);
455 if (Dom == VI->first)
457 else if (Dom != Fallback)
458 HaveFallback = false;
462 Value *Undef = UndefValue::get(Phi->getType());
463 Updater.AddAvailableValue(Fallback, Undef);
466 Phi->addIncoming(Updater.GetValueAtEndOfBlock(From), From);
468 DeletedPhis.erase(To);
471 /// \brief Create a new flow node and update dominator tree and region info
472 BasicBlock *AMDGPUStructurizeCFG::getNextFlow(BasicBlock *Prev) {
474 LLVMContext &Context = Func->getContext();
475 BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
476 Order.back()->getEntry();
477 BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
479 DT->addNewBlock(Flow, Prev);
480 ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
481 FlowsInserted.push_back(Flow);
485 /// \brief Can we predict that this node will always be called?
486 bool AMDGPUStructurizeCFG::isPredictableTrue(BasicBlock *Prev,
489 BBPredicates &Preds = Predicates[Node];
490 bool Dominated = false;
492 for (BBPredicates::iterator I = Preds.begin(), E = Preds.end();
495 if (I->second != BoolTrue)
498 if (!Dominated && DT->dominates(I->first, Prev))
504 /// \brief Wire up the new control flow by inserting or updating the branch
505 /// instructions at node exits
506 BasicBlock *AMDGPUStructurizeCFG::wireFlowBlock(BasicBlock *Prev,
509 BasicBlock *Entry = Node->getEntry();
511 if (LoopStart == Entry) {
513 LoopPred[Prev] = BoolTrue;
516 // Wire it up temporary, skipChained may recurse into us
517 BranchInst::Create(Entry, Prev);
518 DT->changeImmediateDominator(Entry, Prev);
519 addPhiValues(Prev, Entry);
521 Node = skipChained(Node);
523 BasicBlock *Next = getNextFlow(Prev);
524 if (!isPredictableTrue(Prev, Entry)) {
525 // Let Prev point to entry and next block
526 Prev->getTerminator()->eraseFromParent();
527 BranchInst::Create(Entry, Next, BoolUndef, Prev);
529 DT->changeImmediateDominator(Next, Entry);
532 // Let node exit(s) point to next block
533 if (Node->isSubRegion()) {
534 Region *SubRegion = Node->getNodeAs<Region>();
535 BasicBlock *Exit = SubRegion->getExit();
537 // Find all the edges from the sub region to the exit
539 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
540 if (SubRegion->contains(*I))
544 // Modify the edges to point to the new flow block
545 for (BBVector::iterator I = ToDo.begin(), E = ToDo.end(); I != E; ++I) {
546 delPhiValues(*I, Exit);
547 TerminatorInst *Term = (*I)->getTerminator();
548 Term->replaceUsesOfWith(Exit, Next);
551 // Update the region info
552 SubRegion->replaceExit(Next);
555 BasicBlock *BB = Node->getNodeAs<BasicBlock>();
557 BranchInst::Create(Next, BB);
566 /// Destroy node order and visited map, build up flow order instead.
567 /// After this function control flow looks like it should be, but
568 /// branches only have undefined conditions.
569 void AMDGPUStructurizeCFG::createFlow() {
573 BasicBlock *Prev = Order.pop_back_val()->getEntry();
574 assert(Prev == ParentRegion->getEntry() && "Incorrect node order!");
577 if (LoopStart == Prev) {
578 // Loop starts at entry, split entry so that we can predicate it
579 BasicBlock::iterator Insert = Prev->getFirstInsertionPt();
580 BasicBlock *Split = Prev->splitBasicBlock(Insert, FlowBlockName);
581 DT->addNewBlock(Split, Prev);
582 ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion);
583 Predicates[Split] = Predicates[Prev];
584 Order.push_back(ParentRegion->getBBNode(Split));
585 LoopPred[Prev] = BoolTrue;
587 } else if (LoopStart == Order.back()->getEntry()) {
588 // Loop starts behind entry, split entry so that we can jump to it
589 Instruction *Term = Prev->getTerminator();
590 BasicBlock *Split = Prev->splitBasicBlock(Term, FlowBlockName);
591 DT->addNewBlock(Split, Prev);
592 ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion);
596 killTerminator(Prev);
597 FlowsInserted.clear();
598 FlowsInserted.push_back(Prev);
600 while (!Order.empty()) {
601 RegionNode *Node = Order.pop_back_val();
602 Visited.erase(Node->getEntry());
603 Prev = wireFlowBlock(Prev, Node);
604 if (LoopStart && !LoopEnd) {
605 // Create an extra loop end node
607 Prev = getNextFlow(LoopEnd);
608 BranchInst::Create(Prev, LoopStart, BoolUndef, LoopEnd);
609 addPhiValues(LoopEnd, LoopStart);
613 BasicBlock *Exit = ParentRegion->getExit();
614 BranchInst::Create(Exit, Prev);
615 addPhiValues(Prev, Exit);
616 if (DT->dominates(ParentRegion->getEntry(), Exit))
617 DT->changeImmediateDominator(Exit, Prev);
619 if (LoopStart && LoopEnd) {
620 BBVector::iterator FI = std::find(FlowsInserted.begin(),
623 for (; *FI != LoopEnd; ++FI) {
624 addPhiValues(*FI, (*FI)->getTerminator()->getSuccessor(0));
628 assert(Order.empty());
629 assert(Visited.empty());
630 assert(DeletedPhis.empty());
633 /// \brief Insert the missing branch conditions
634 void AMDGPUStructurizeCFG::insertConditions() {
636 SSAUpdater PhiInserter;
638 for (BBVector::iterator FI = FlowsInserted.begin(), FE = FlowsInserted.end();
641 BranchInst *Term = cast<BranchInst>((*FI)->getTerminator());
642 if (Term->isUnconditional())
645 PhiInserter.Initialize(Boolean, "");
646 PhiInserter.AddAvailableValue(&Func->getEntryBlock(), BoolFalse);
648 BasicBlock *Succ = Term->getSuccessor(0);
649 BBPredicates &Preds = (*FI == LoopEnd) ? LoopPred : Predicates[Succ];
650 for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
653 PhiInserter.AddAvailableValue(PI->first, PI->second);
656 Term->setCondition(PhiInserter.GetValueAtEndOfBlock(*FI));
660 /// Handle a rare case where the disintegrated nodes instructions
661 /// no longer dominate all their uses. Not sure if this is really nessasary
662 void AMDGPUStructurizeCFG::rebuildSSA() {
665 for (Region::block_iterator I = ParentRegion->block_begin(),
666 E = ParentRegion->block_end();
670 for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
673 bool Initialized = false;
674 for (Use *I = &II->use_begin().getUse(), *Next; I; I = Next) {
678 Instruction *User = cast<Instruction>(I->getUser());
679 if (User->getParent() == BB) {
682 } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
683 if (UserPN->getIncomingBlock(*I) == BB)
687 if (DT->dominates(II, User))
691 Value *Undef = UndefValue::get(II->getType());
692 Updater.Initialize(II->getType(), "");
693 Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
694 Updater.AddAvailableValue(BB, II);
697 Updater.RewriteUseAfterInsertions(*I);
703 /// \brief Run the transformation for each region found
704 bool AMDGPUStructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
706 if (R->isTopLevelRegion())
709 Func = R->getEntry()->getParent();
712 DT = &getAnalysis<DominatorTree>();
724 FlowsInserted.clear();
729 /// \brief Create the pass
730 Pass *llvm::createAMDGPUStructurizeCFGPass() {
731 return new AMDGPUStructurizeCFG();