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