Home | History | Annotate | Download | only in Scalar 
      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 
     21 using namespace llvm;
     22 using namespace llvm::PatternMatch;
     23 
     24 namespace {
     25 
     26 // Definition of the complex types used in this pass.
     27 
     28 typedef std::pair<BasicBlock *, Value *> BBValuePair;
     29 
     30 typedef SmallVector<RegionNode*, 8> RNVector;
     31 typedef SmallVector<BasicBlock*, 8> BBVector;
     32 typedef SmallVector<BranchInst*, 8> BranchVector;
     33 typedef SmallVector<BBValuePair, 2> BBValueVector;
     34 
     35 typedef SmallPtrSet<BasicBlock *, 8> BBSet;
     36 
     37 typedef MapVector<PHINode *, BBValueVector> PhiMap;
     38 typedef MapVector<BasicBlock *, BBVector> BB2BBVecMap;
     39 
     40 typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap;
     41 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
     42 typedef DenseMap<BasicBlock *, Value *> BBPredicates;
     43 typedef DenseMap<BasicBlock *, BBPredicates> PredMap;
     44 typedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap;
     45 
     46 // The name for newly created blocks.
     47 
     48 static 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
     54 class NearestCommonDominator {
     55   DominatorTree *DT;
     56 
     57   DTN2UnsignedMap IndexMap;
     58 
     59   BasicBlock *Result;
     60   unsigned ResultIndex;
     61   bool ExplicitMentioned;
     62 
     63 public:
     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.
    158 class 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 
    229 public:
    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 
    255 char StructurizeCFG::ID = 0;
    256 
    257 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
    258                       false, false)
    259 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
    260 INITIALIZE_PASS_DEPENDENCY(RegionInfo)
    261 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
    262                     false, false)
    263 
    264 /// \brief Initialize the types and constants used in the pass
    265 bool 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
    277 void 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
    287 void 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
    309 Value *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
    342 Value *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
    355 void 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
    419 void 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
    445 void 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
    494 void 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
    508 void 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
    520 void 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.
    568 void 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
    583 void 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
    630 BasicBlock *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
    642 BasicBlock *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
    662 BasicBlock *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
    674 void 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 ?
    679 bool 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?
    691 bool 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
    714 void 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 
    750 void 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.
    780 void 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
    804 void 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
    845 bool 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
    877 Pass *llvm::createStructurizeCFGPass() {
    878   return new StructurizeCFG();
    879 }
    880