OSDN Git Service

49ce0262c97b01fdb1406a2f65e8a5dba64bafdc
[android-x86/external-llvm.git] / lib / Transforms / Scalar / StructurizeCFG.cpp
1 //===-- StructurizeCFG.cpp ------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/Transforms/Scalar.h"
11 #include "llvm/ADT/MapVector.h"
12 #include "llvm/ADT/PostOrderIterator.h"
13 #include "llvm/ADT/SCCIterator.h"
14 #include "llvm/Analysis/DivergenceAnalysis.h"
15 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/Analysis/RegionInfo.h"
17 #include "llvm/Analysis/RegionIterator.h"
18 #include "llvm/Analysis/RegionPass.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/IR/PatternMatch.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Transforms/Utils/SSAUpdater.h"
24
25 using namespace llvm;
26 using namespace llvm::PatternMatch;
27
28 #define DEBUG_TYPE "structurizecfg"
29
30 namespace {
31
32 // Definition of the complex types used in this pass.
33
34 typedef std::pair<BasicBlock *, Value *> BBValuePair;
35
36 typedef SmallVector<RegionNode*, 8> RNVector;
37 typedef SmallVector<BasicBlock*, 8> BBVector;
38 typedef SmallVector<BranchInst*, 8> BranchVector;
39 typedef SmallVector<BBValuePair, 2> BBValueVector;
40
41 typedef SmallPtrSet<BasicBlock *, 8> BBSet;
42
43 typedef MapVector<PHINode *, BBValueVector> PhiMap;
44 typedef MapVector<BasicBlock *, BBVector> BB2BBVecMap;
45
46 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
47 typedef DenseMap<BasicBlock *, Value *> BBPredicates;
48 typedef DenseMap<BasicBlock *, BBPredicates> PredMap;
49 typedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap;
50
51 // The name for newly created blocks.
52 static const char *const FlowBlockName = "Flow";
53
54 /// Finds the nearest common dominator of a set of BasicBlocks.
55 ///
56 /// For every BB you add to the set, you can specify whether we "remember" the
57 /// block.  When you get the common dominator, you can also ask whether it's one
58 /// of the blocks we remembered.
59 class NearestCommonDominator {
60   DominatorTree *DT;
61   BasicBlock *Result = nullptr;
62   bool ResultIsRemembered = false;
63
64   /// Add BB to the resulting dominator.
65   void addBlock(BasicBlock *BB, bool Remember) {
66     if (!Result) {
67       Result = BB;
68       ResultIsRemembered = Remember;
69       return;
70     }
71
72     BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
73     if (NewResult != Result)
74       ResultIsRemembered = false;
75     if (NewResult == BB)
76       ResultIsRemembered |= Remember;
77     Result = NewResult;
78   }
79
80 public:
81   explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
82
83   void addBlock(BasicBlock *BB) {
84     addBlock(BB, /* Remember = */ false);
85   }
86
87   void addAndRememberBlock(BasicBlock *BB) {
88     addBlock(BB, /* Remember = */ true);
89   }
90
91   /// Get the nearest common dominator of all the BBs added via addBlock() and
92   /// addAndRememberBlock().
93   BasicBlock *result() { return Result; }
94
95   /// Is the BB returned by getResult() one of the blocks we added to the set
96   /// with addAndRememberBlock()?
97   bool resultIsRememberedBlock() { return ResultIsRemembered; }
98 };
99
100 /// @brief Transforms the control flow graph on one single entry/exit region
101 /// at a time.
102 ///
103 /// After the transform all "If"/"Then"/"Else" style control flow looks like
104 /// this:
105 ///
106 /// \verbatim
107 /// 1
108 /// ||
109 /// | |
110 /// 2 |
111 /// | /
112 /// |/
113 /// 3
114 /// ||   Where:
115 /// | |  1 = "If" block, calculates the condition
116 /// 4 |  2 = "Then" subregion, runs if the condition is true
117 /// | /  3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
118 /// |/   4 = "Else" optional subregion, runs if the condition is false
119 /// 5    5 = "End" block, also rejoins the control flow
120 /// \endverbatim
121 ///
122 /// Control flow is expressed as a branch where the true exit goes into the
123 /// "Then"/"Else" region, while the false exit skips the region
124 /// The condition for the optional "Else" region is expressed as a PHI node.
125 /// The incoming values of the PHI node are true for the "If" edge and false
126 /// for the "Then" edge.
127 ///
128 /// Additionally to that even complicated loops look like this:
129 ///
130 /// \verbatim
131 /// 1
132 /// ||
133 /// | |
134 /// 2 ^  Where:
135 /// | /  1 = "Entry" block
136 /// |/   2 = "Loop" optional subregion, with all exits at "Flow" block
137 /// 3    3 = "Flow" block, with back edge to entry block
138 /// |
139 /// \endverbatim
140 ///
141 /// The back edge of the "Flow" block is always on the false side of the branch
142 /// while the true side continues the general flow. So the loop condition
143 /// consist of a network of PHI nodes where the true incoming values expresses
144 /// breaks and the false values expresses continue states.
145 class StructurizeCFG : public RegionPass {
146   bool SkipUniformRegions;
147
148   Type *Boolean;
149   ConstantInt *BoolTrue;
150   ConstantInt *BoolFalse;
151   UndefValue *BoolUndef;
152
153   Function *Func;
154   Region *ParentRegion;
155
156   DominatorTree *DT;
157   LoopInfo *LI;
158
159   SmallVector<RegionNode *, 8> Order;
160   BBSet Visited;
161
162   BBPhiMap DeletedPhis;
163   BB2BBVecMap AddedPhis;
164
165   PredMap Predicates;
166   BranchVector Conditions;
167
168   BB2BBMap Loops;
169   PredMap LoopPreds;
170   BranchVector LoopConds;
171
172   RegionNode *PrevNode;
173
174   void orderNodes();
175
176   void analyzeLoops(RegionNode *N);
177
178   Value *invert(Value *Condition);
179
180   Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
181
182   void gatherPredicates(RegionNode *N);
183
184   void collectInfos();
185
186   void insertConditions(bool Loops);
187
188   void delPhiValues(BasicBlock *From, BasicBlock *To);
189
190   void addPhiValues(BasicBlock *From, BasicBlock *To);
191
192   void setPhiValues();
193
194   void killTerminator(BasicBlock *BB);
195
196   void changeExit(RegionNode *Node, BasicBlock *NewExit,
197                   bool IncludeDominator);
198
199   BasicBlock *getNextFlow(BasicBlock *Dominator);
200
201   BasicBlock *needPrefix(bool NeedEmpty);
202
203   BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
204
205   void setPrevNode(BasicBlock *BB);
206
207   bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
208
209   bool isPredictableTrue(RegionNode *Node);
210
211   void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
212
213   void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
214
215   void createFlow();
216
217   void rebuildSSA();
218
219 public:
220   static char ID;
221
222   explicit StructurizeCFG(bool SkipUniformRegions = false)
223       : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
224     initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
225   }
226
227   bool doInitialization(Region *R, RGPassManager &RGM) override;
228
229   bool runOnRegion(Region *R, RGPassManager &RGM) override;
230
231   StringRef getPassName() const override { return "Structurize control flow"; }
232
233   void getAnalysisUsage(AnalysisUsage &AU) const override {
234     if (SkipUniformRegions)
235       AU.addRequired<DivergenceAnalysis>();
236     AU.addRequiredID(LowerSwitchID);
237     AU.addRequired<DominatorTreeWrapperPass>();
238     AU.addRequired<LoopInfoWrapperPass>();
239
240     AU.addPreserved<DominatorTreeWrapperPass>();
241     RegionPass::getAnalysisUsage(AU);
242   }
243 };
244
245 } // end anonymous namespace
246
247 char StructurizeCFG::ID = 0;
248
249 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
250                       false, false)
251 INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
252 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
253 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
254 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
255 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
256                     false, false)
257
258 /// \brief Initialize the types and constants used in the pass
259 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
260   LLVMContext &Context = R->getEntry()->getContext();
261
262   Boolean = Type::getInt1Ty(Context);
263   BoolTrue = ConstantInt::getTrue(Context);
264   BoolFalse = ConstantInt::getFalse(Context);
265   BoolUndef = UndefValue::get(Boolean);
266
267   return false;
268 }
269
270 /// \brief Build up the general order of nodes
271 void StructurizeCFG::orderNodes() {
272   ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
273   SmallDenseMap<Loop*, unsigned, 8> LoopBlocks;
274
275   // The reverse post-order traversal of the list gives us an ordering close
276   // to what we want.  The only problem with it is that sometimes backedges
277   // for outer loops will be visited before backedges for inner loops.
278   for (RegionNode *RN : RPOT) {
279     BasicBlock *BB = RN->getEntry();
280     Loop *Loop = LI->getLoopFor(BB);
281     ++LoopBlocks[Loop];
282   }
283
284   unsigned CurrentLoopDepth = 0;
285   Loop *CurrentLoop = nullptr;
286   for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
287     BasicBlock *BB = (*I)->getEntry();
288     unsigned LoopDepth = LI->getLoopDepth(BB);
289
290     if (is_contained(Order, *I))
291       continue;
292
293     if (LoopDepth < CurrentLoopDepth) {
294       // Make sure we have visited all blocks in this loop before moving back to
295       // the outer loop.
296
297       auto LoopI = I;
298       while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
299         LoopI++;
300         BasicBlock *LoopBB = (*LoopI)->getEntry();
301         if (LI->getLoopFor(LoopBB) == CurrentLoop) {
302           --BlockCount;
303           Order.push_back(*LoopI);
304         }
305       }
306     }
307
308     CurrentLoop = LI->getLoopFor(BB);
309     if (CurrentLoop)
310       LoopBlocks[CurrentLoop]--;
311
312     CurrentLoopDepth = LoopDepth;
313     Order.push_back(*I);
314   }
315
316   // This pass originally used a post-order traversal and then operated on
317   // the list in reverse. Now that we are using a reverse post-order traversal
318   // rather than re-working the whole pass to operate on the list in order,
319   // we just reverse the list and continue to operate on it in reverse.
320   std::reverse(Order.begin(), Order.end());
321 }
322
323 /// \brief Determine the end of the loops
324 void StructurizeCFG::analyzeLoops(RegionNode *N) {
325   if (N->isSubRegion()) {
326     // Test for exit as back edge
327     BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
328     if (Visited.count(Exit))
329       Loops[Exit] = N->getEntry();
330
331   } else {
332     // Test for sucessors as back edge
333     BasicBlock *BB = N->getNodeAs<BasicBlock>();
334     BranchInst *Term = cast<BranchInst>(BB->getTerminator());
335
336     for (BasicBlock *Succ : Term->successors())
337       if (Visited.count(Succ))
338         Loops[Succ] = BB;
339   }
340 }
341
342 /// \brief Invert the given condition
343 Value *StructurizeCFG::invert(Value *Condition) {
344   // First: Check if it's a constant
345   if (Constant *C = dyn_cast<Constant>(Condition))
346     return ConstantExpr::getNot(C);
347
348   // Second: If the condition is already inverted, return the original value
349   if (match(Condition, m_Not(m_Value(Condition))))
350     return Condition;
351
352   if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
353     // Third: Check all the users for an invert
354     BasicBlock *Parent = Inst->getParent();
355     for (User *U : Condition->users())
356       if (Instruction *I = dyn_cast<Instruction>(U))
357         if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
358           return I;
359
360     // Last option: Create a new instruction
361     return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
362   }
363
364   if (Argument *Arg = dyn_cast<Argument>(Condition)) {
365     BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
366     return BinaryOperator::CreateNot(Condition,
367                                      Arg->getName() + ".inv",
368                                      EntryBlock.getTerminator());
369   }
370
371   llvm_unreachable("Unhandled condition to invert");
372 }
373
374 /// \brief Build the condition for one edge
375 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
376                                       bool Invert) {
377   Value *Cond = Invert ? BoolFalse : BoolTrue;
378   if (Term->isConditional()) {
379     Cond = Term->getCondition();
380
381     if (Idx != (unsigned)Invert)
382       Cond = invert(Cond);
383   }
384   return Cond;
385 }
386
387 /// \brief Analyze the predecessors of each block and build up predicates
388 void StructurizeCFG::gatherPredicates(RegionNode *N) {
389   RegionInfo *RI = ParentRegion->getRegionInfo();
390   BasicBlock *BB = N->getEntry();
391   BBPredicates &Pred = Predicates[BB];
392   BBPredicates &LPred = LoopPreds[BB];
393
394   for (BasicBlock *P : predecessors(BB)) {
395     // Ignore it if it's a branch from outside into our region entry
396     if (!ParentRegion->contains(P))
397       continue;
398
399     Region *R = RI->getRegionFor(P);
400     if (R == ParentRegion) {
401       // It's a top level block in our region
402       BranchInst *Term = cast<BranchInst>(P->getTerminator());
403       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
404         BasicBlock *Succ = Term->getSuccessor(i);
405         if (Succ != BB)
406           continue;
407
408         if (Visited.count(P)) {
409           // Normal forward edge
410           if (Term->isConditional()) {
411             // Try to treat it like an ELSE block
412             BasicBlock *Other = Term->getSuccessor(!i);
413             if (Visited.count(Other) && !Loops.count(Other) &&
414                 !Pred.count(Other) && !Pred.count(P)) {
415
416               Pred[Other] = BoolFalse;
417               Pred[P] = BoolTrue;
418               continue;
419             }
420           }
421           Pred[P] = buildCondition(Term, i, false);
422         } else {
423           // Back edge
424           LPred[P] = buildCondition(Term, i, true);
425         }
426       }
427     } else {
428       // It's an exit from a sub region
429       while (R->getParent() != ParentRegion)
430         R = R->getParent();
431
432       // Edge from inside a subregion to its entry, ignore it
433       if (*R == *N)
434         continue;
435
436       BasicBlock *Entry = R->getEntry();
437       if (Visited.count(Entry))
438         Pred[Entry] = BoolTrue;
439       else
440         LPred[Entry] = BoolFalse;
441     }
442   }
443 }
444
445 /// \brief Collect various loop and predicate infos
446 void StructurizeCFG::collectInfos() {
447   // Reset predicate
448   Predicates.clear();
449
450   // and loop infos
451   Loops.clear();
452   LoopPreds.clear();
453
454   // Reset the visited nodes
455   Visited.clear();
456
457   for (RegionNode *RN : reverse(Order)) {
458     DEBUG(dbgs() << "Visiting: "
459                  << (RN->isSubRegion() ? "SubRegion with entry: " : "")
460                  << RN->getEntry()->getName() << " Loop Depth: "
461                  << LI->getLoopDepth(RN->getEntry()) << "\n");
462
463     // Analyze all the conditions leading to a node
464     gatherPredicates(RN);
465
466     // Remember that we've seen this node
467     Visited.insert(RN->getEntry());
468
469     // Find the last back edges
470     analyzeLoops(RN);
471   }
472 }
473
474 /// \brief Insert the missing branch conditions
475 void StructurizeCFG::insertConditions(bool Loops) {
476   BranchVector &Conds = Loops ? LoopConds : Conditions;
477   Value *Default = Loops ? BoolTrue : BoolFalse;
478   SSAUpdater PhiInserter;
479
480   for (BranchInst *Term : Conds) {
481     assert(Term->isConditional());
482
483     BasicBlock *Parent = Term->getParent();
484     BasicBlock *SuccTrue = Term->getSuccessor(0);
485     BasicBlock *SuccFalse = Term->getSuccessor(1);
486
487     PhiInserter.Initialize(Boolean, "");
488     PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
489     PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
490
491     BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
492
493     NearestCommonDominator Dominator(DT);
494     Dominator.addBlock(Parent);
495
496     Value *ParentValue = nullptr;
497     for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
498       BasicBlock *BB = BBAndPred.first;
499       Value *Pred = BBAndPred.second;
500
501       if (BB == Parent) {
502         ParentValue = Pred;
503         break;
504       }
505       PhiInserter.AddAvailableValue(BB, Pred);
506       Dominator.addAndRememberBlock(BB);
507     }
508
509     if (ParentValue) {
510       Term->setCondition(ParentValue);
511     } else {
512       if (!Dominator.resultIsRememberedBlock())
513         PhiInserter.AddAvailableValue(Dominator.result(), Default);
514
515       Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
516     }
517   }
518 }
519
520 /// \brief Remove all PHI values coming from "From" into "To" and remember
521 /// them in DeletedPhis
522 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
523   PhiMap &Map = DeletedPhis[To];
524   for (Instruction &I : *To) {
525     if (!isa<PHINode>(I))
526       break;
527     PHINode &Phi = cast<PHINode>(I);
528     while (Phi.getBasicBlockIndex(From) != -1) {
529       Value *Deleted = Phi.removeIncomingValue(From, false);
530       Map[&Phi].push_back(std::make_pair(From, Deleted));
531     }
532   }
533 }
534
535 /// \brief Add a dummy PHI value as soon as we knew the new predecessor
536 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
537   for (Instruction &I : *To) {
538     if (!isa<PHINode>(I))
539       break;
540     PHINode &Phi = cast<PHINode>(I);
541     Value *Undef = UndefValue::get(Phi.getType());
542     Phi.addIncoming(Undef, From);
543   }
544   AddedPhis[To].push_back(From);
545 }
546
547 /// \brief Add the real PHI value as soon as everything is set up
548 void StructurizeCFG::setPhiValues() {
549   SSAUpdater Updater;
550   for (const auto &AddedPhi : AddedPhis) {
551     BasicBlock *To = AddedPhi.first;
552     const BBVector &From = AddedPhi.second;
553
554     if (!DeletedPhis.count(To))
555       continue;
556
557     PhiMap &Map = DeletedPhis[To];
558     for (const auto &PI : Map) {
559       PHINode *Phi = PI.first;
560       Value *Undef = UndefValue::get(Phi->getType());
561       Updater.Initialize(Phi->getType(), "");
562       Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
563       Updater.AddAvailableValue(To, Undef);
564
565       NearestCommonDominator Dominator(DT);
566       Dominator.addBlock(To);
567       for (const auto &VI : PI.second) {
568         Updater.AddAvailableValue(VI.first, VI.second);
569         Dominator.addAndRememberBlock(VI.first);
570       }
571
572       if (!Dominator.resultIsRememberedBlock())
573         Updater.AddAvailableValue(Dominator.result(), Undef);
574
575       for (BasicBlock *FI : From) {
576         int Idx = Phi->getBasicBlockIndex(FI);
577         assert(Idx != -1);
578         Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI));
579       }
580     }
581
582     DeletedPhis.erase(To);
583   }
584   assert(DeletedPhis.empty());
585 }
586
587 /// \brief Remove phi values from all successors and then remove the terminator.
588 void StructurizeCFG::killTerminator(BasicBlock *BB) {
589   TerminatorInst *Term = BB->getTerminator();
590   if (!Term)
591     return;
592
593   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
594        SI != SE; ++SI)
595     delPhiValues(BB, *SI);
596
597   Term->eraseFromParent();
598 }
599
600 /// \brief Let node exit(s) point to NewExit
601 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
602                                 bool IncludeDominator) {
603   if (Node->isSubRegion()) {
604     Region *SubRegion = Node->getNodeAs<Region>();
605     BasicBlock *OldExit = SubRegion->getExit();
606     BasicBlock *Dominator = nullptr;
607
608     // Find all the edges from the sub region to the exit
609     for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) {
610       // Incrememt BBI before mucking with BB's terminator.
611       BasicBlock *BB = *BBI++;
612
613       if (!SubRegion->contains(BB))
614         continue;
615
616       // Modify the edges to point to the new exit
617       delPhiValues(BB, OldExit);
618       BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
619       addPhiValues(BB, NewExit);
620
621       // Find the new dominator (if requested)
622       if (IncludeDominator) {
623         if (!Dominator)
624           Dominator = BB;
625         else
626           Dominator = DT->findNearestCommonDominator(Dominator, BB);
627       }
628     }
629
630     // Change the dominator (if requested)
631     if (Dominator)
632       DT->changeImmediateDominator(NewExit, Dominator);
633
634     // Update the region info
635     SubRegion->replaceExit(NewExit);
636   } else {
637     BasicBlock *BB = Node->getNodeAs<BasicBlock>();
638     killTerminator(BB);
639     BranchInst::Create(NewExit, BB);
640     addPhiValues(BB, NewExit);
641     if (IncludeDominator)
642       DT->changeImmediateDominator(NewExit, BB);
643   }
644 }
645
646 /// \brief Create a new flow node and update dominator tree and region info
647 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
648   LLVMContext &Context = Func->getContext();
649   BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
650                        Order.back()->getEntry();
651   BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
652                                         Func, Insert);
653   DT->addNewBlock(Flow, Dominator);
654   ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
655   return Flow;
656 }
657
658 /// \brief Create a new or reuse the previous node as flow node
659 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
660   BasicBlock *Entry = PrevNode->getEntry();
661
662   if (!PrevNode->isSubRegion()) {
663     killTerminator(Entry);
664     if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
665       return Entry;
666   }
667
668   // create a new flow node
669   BasicBlock *Flow = getNextFlow(Entry);
670
671   // and wire it up
672   changeExit(PrevNode, Flow, true);
673   PrevNode = ParentRegion->getBBNode(Flow);
674   return Flow;
675 }
676
677 /// \brief Returns the region exit if possible, otherwise just a new flow node
678 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
679                                         bool ExitUseAllowed) {
680   if (!Order.empty() || !ExitUseAllowed)
681     return getNextFlow(Flow);
682
683   BasicBlock *Exit = ParentRegion->getExit();
684   DT->changeImmediateDominator(Exit, Flow);
685   addPhiValues(Flow, Exit);
686   return Exit;
687 }
688
689 /// \brief Set the previous node
690 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
691   PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
692                                         : nullptr;
693 }
694
695 /// \brief Does BB dominate all the predicates of Node?
696 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
697   BBPredicates &Preds = Predicates[Node->getEntry()];
698   return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
699     return DT->dominates(BB, Pred.first);
700   });
701 }
702
703 /// \brief Can we predict that this node will always be called?
704 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
705   BBPredicates &Preds = Predicates[Node->getEntry()];
706   bool Dominated = false;
707
708   // Regionentry is always true
709   if (!PrevNode)
710     return true;
711
712   for (std::pair<BasicBlock*, Value*> Pred : Preds) {
713     BasicBlock *BB = Pred.first;
714     Value *V = Pred.second;
715
716     if (V != BoolTrue)
717       return false;
718
719     if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
720       Dominated = true;
721   }
722
723   // TODO: The dominator check is too strict
724   return Dominated;
725 }
726
727 /// Take one node from the order vector and wire it up
728 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
729                               BasicBlock *LoopEnd) {
730   RegionNode *Node = Order.pop_back_val();
731   Visited.insert(Node->getEntry());
732
733   if (isPredictableTrue(Node)) {
734     // Just a linear flow
735     if (PrevNode) {
736       changeExit(PrevNode, Node->getEntry(), true);
737     }
738     PrevNode = Node;
739
740   } else {
741     // Insert extra prefix node (or reuse last one)
742     BasicBlock *Flow = needPrefix(false);
743
744     // Insert extra postfix node (or use exit instead)
745     BasicBlock *Entry = Node->getEntry();
746     BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
747
748     // let it point to entry and next block
749     Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
750     addPhiValues(Flow, Entry);
751     DT->changeImmediateDominator(Entry, Flow);
752
753     PrevNode = Node;
754     while (!Order.empty() && !Visited.count(LoopEnd) &&
755            dominatesPredicates(Entry, Order.back())) {
756       handleLoops(false, LoopEnd);
757     }
758
759     changeExit(PrevNode, Next, false);
760     setPrevNode(Next);
761   }
762 }
763
764 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
765                                  BasicBlock *LoopEnd) {
766   RegionNode *Node = Order.back();
767   BasicBlock *LoopStart = Node->getEntry();
768
769   if (!Loops.count(LoopStart)) {
770     wireFlow(ExitUseAllowed, LoopEnd);
771     return;
772   }
773
774   if (!isPredictableTrue(Node))
775     LoopStart = needPrefix(true);
776
777   LoopEnd = Loops[Node->getEntry()];
778   wireFlow(false, LoopEnd);
779   while (!Visited.count(LoopEnd)) {
780     handleLoops(false, LoopEnd);
781   }
782
783   // If the start of the loop is the entry block, we can't branch to it so
784   // insert a new dummy entry block.
785   Function *LoopFunc = LoopStart->getParent();
786   if (LoopStart == &LoopFunc->getEntryBlock()) {
787     LoopStart->setName("entry.orig");
788
789     BasicBlock *NewEntry =
790       BasicBlock::Create(LoopStart->getContext(),
791                          "entry",
792                          LoopFunc,
793                          LoopStart);
794     BranchInst::Create(LoopStart, NewEntry);
795     DT->setNewRoot(NewEntry);
796   }
797
798   // Create an extra loop end node
799   LoopEnd = needPrefix(false);
800   BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
801   LoopConds.push_back(BranchInst::Create(Next, LoopStart,
802                                          BoolUndef, LoopEnd));
803   addPhiValues(LoopEnd, LoopStart);
804   setPrevNode(Next);
805 }
806
807 /// After this function control flow looks like it should be, but
808 /// branches and PHI nodes only have undefined conditions.
809 void StructurizeCFG::createFlow() {
810   BasicBlock *Exit = ParentRegion->getExit();
811   bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
812
813   DeletedPhis.clear();
814   AddedPhis.clear();
815   Conditions.clear();
816   LoopConds.clear();
817
818   PrevNode = nullptr;
819   Visited.clear();
820
821   while (!Order.empty()) {
822     handleLoops(EntryDominatesExit, nullptr);
823   }
824
825   if (PrevNode)
826     changeExit(PrevNode, Exit, EntryDominatesExit);
827   else
828     assert(EntryDominatesExit);
829 }
830
831 /// Handle a rare case where the disintegrated nodes instructions
832 /// no longer dominate all their uses. Not sure if this is really nessasary
833 void StructurizeCFG::rebuildSSA() {
834   SSAUpdater Updater;
835   for (BasicBlock *BB : ParentRegion->blocks())
836     for (Instruction &I : *BB) {
837       bool Initialized = false;
838       // We may modify the use list as we iterate over it, so be careful to
839       // compute the next element in the use list at the top of the loop.
840       for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) {
841         Use &U = *UI++;
842         Instruction *User = cast<Instruction>(U.getUser());
843         if (User->getParent() == BB) {
844           continue;
845         } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
846           if (UserPN->getIncomingBlock(U) == BB)
847             continue;
848         }
849
850         if (DT->dominates(&I, User))
851           continue;
852
853         if (!Initialized) {
854           Value *Undef = UndefValue::get(I.getType());
855           Updater.Initialize(I.getType(), "");
856           Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
857           Updater.AddAvailableValue(BB, &I);
858           Initialized = true;
859         }
860         Updater.RewriteUseAfterInsertions(U);
861       }
862     }
863 }
864
865 static bool hasOnlyUniformBranches(const Region *R,
866                                    const DivergenceAnalysis &DA) {
867   for (const BasicBlock *BB : R->blocks()) {
868     const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
869     if (!Br || !Br->isConditional())
870       continue;
871
872     if (!DA.isUniform(Br->getCondition()))
873       return false;
874     DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
875   }
876   return true;
877 }
878
879 /// \brief Run the transformation for each region found
880 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
881   if (R->isTopLevelRegion())
882     return false;
883
884   if (SkipUniformRegions) {
885     // TODO: We could probably be smarter here with how we handle sub-regions.
886     auto &DA = getAnalysis<DivergenceAnalysis>();
887     if (hasOnlyUniformBranches(R, DA)) {
888       DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
889
890       // Mark all direct child block terminators as having been treated as
891       // uniform. To account for a possible future in which non-uniform
892       // sub-regions are treated more cleverly, indirect children are not
893       // marked as uniform.
894       MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
895       for (RegionNode *E : R->elements()) {
896         if (E->isSubRegion())
897           continue;
898
899         if (Instruction *Term = E->getEntry()->getTerminator())
900           Term->setMetadata("structurizecfg.uniform", MD);
901       }
902
903       return false;
904     }
905   }
906
907   Func = R->getEntry()->getParent();
908   ParentRegion = R;
909
910   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
911   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
912
913   orderNodes();
914   collectInfos();
915   createFlow();
916   insertConditions(false);
917   insertConditions(true);
918   setPhiValues();
919   rebuildSSA();
920
921   // Cleanup
922   Order.clear();
923   Visited.clear();
924   DeletedPhis.clear();
925   AddedPhis.clear();
926   Predicates.clear();
927   Conditions.clear();
928   Loops.clear();
929   LoopPreds.clear();
930   LoopConds.clear();
931
932   return true;
933 }
934
935 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
936   return new StructurizeCFG(SkipUniformRegions);
937 }