StructurizeCFG.cpp revision e96466ecc0b2bdee0bed2156e12dc16f4adb2d50 
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    initializeStructurizeCFGPass(*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.addRequiredID(LowerSwitchID);
248    AU.addRequired<DominatorTree>();
249    AU.addPreserved<DominatorTree>();
250    RegionPass::getAnalysisUsage(AU);
251  }
252};
253
254} // end anonymous namespace
255
256char StructurizeCFG::ID = 0;
257
258INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
259                      false, false)
260INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
261INITIALIZE_PASS_DEPENDENCY(DominatorTree)
262INITIALIZE_PASS_DEPENDENCY(RegionInfo)
263INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
264                    false, false)
265
266/// \brief Initialize the types and constants used in the pass
267bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
268  LLVMContext &Context = R->getEntry()->getContext();
269
270  Boolean = Type::getInt1Ty(Context);
271  BoolTrue = ConstantInt::getTrue(Context);
272  BoolFalse = ConstantInt::getFalse(Context);
273  BoolUndef = UndefValue::get(Boolean);
274
275  return false;
276}
277
278/// \brief Build up the general order of nodes
279void StructurizeCFG::orderNodes() {
280  scc_iterator<Region *> I = scc_begin(ParentRegion),
281                         E = scc_end(ParentRegion);
282  for (Order.clear(); I != E; ++I) {
283    std::vector<RegionNode *> &Nodes = *I;
284    Order.append(Nodes.begin(), Nodes.end());
285  }
286}
287
288/// \brief Determine the end of the loops
289void StructurizeCFG::analyzeLoops(RegionNode *N) {
290  if (N->isSubRegion()) {
291    // Test for exit as back edge
292    BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
293    if (Visited.count(Exit))
294      Loops[Exit] = N->getEntry();
295
296  } else {
297    // Test for sucessors as back edge
298    BasicBlock *BB = N->getNodeAs<BasicBlock>();
299    BranchInst *Term = cast<BranchInst>(BB->getTerminator());
300
301    for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
302      BasicBlock *Succ = Term->getSuccessor(i);
303
304      if (Visited.count(Succ))
305        Loops[Succ] = BB;
306    }
307  }
308}
309
310/// \brief Invert the given condition
311Value *StructurizeCFG::invert(Value *Condition) {
312  // First: Check if it's a constant
313  if (Condition == BoolTrue)
314    return BoolFalse;
315
316  if (Condition == BoolFalse)
317    return BoolTrue;
318
319  if (Condition == BoolUndef)
320    return BoolUndef;
321
322  // Second: If the condition is already inverted, return the original value
323  if (match(Condition, m_Not(m_Value(Condition))))
324    return Condition;
325
326  if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
327    // Third: Check all the users for an invert
328    BasicBlock *Parent = Inst->getParent();
329    for (Value::use_iterator I = Condition->use_begin(),
330           E = Condition->use_end(); I != E; ++I) {
331
332      Instruction *User = dyn_cast<Instruction>(*I);
333      if (!User || User->getParent() != Parent)
334        continue;
335
336      if (match(*I, m_Not(m_Specific(Condition))))
337        return *I;
338    }
339
340    // Last option: Create a new instruction
341    return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
342  }
343
344  if (Argument *Arg = dyn_cast<Argument>(Condition)) {
345    BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
346    return BinaryOperator::CreateNot(Condition,
347                                     Arg->getName() + ".inv",
348                                     EntryBlock.getTerminator());
349  }
350
351  llvm_unreachable("Unhandled condition to invert");
352}
353
354/// \brief Build the condition for one edge
355Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
356                                      bool Invert) {
357  Value *Cond = Invert ? BoolFalse : BoolTrue;
358  if (Term->isConditional()) {
359    Cond = Term->getCondition();
360
361    if (Idx != (unsigned)Invert)
362      Cond = invert(Cond);
363  }
364  return Cond;
365}
366
367/// \brief Analyze the predecessors of each block and build up predicates
368void StructurizeCFG::gatherPredicates(RegionNode *N) {
369  RegionInfo *RI = ParentRegion->getRegionInfo();
370  BasicBlock *BB = N->getEntry();
371  BBPredicates &Pred = Predicates[BB];
372  BBPredicates &LPred = LoopPreds[BB];
373
374  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
375       PI != PE; ++PI) {
376
377    // Ignore it if it's a branch from outside into our region entry
378    if (!ParentRegion->contains(*PI))
379      continue;
380
381    Region *R = RI->getRegionFor(*PI);
382    if (R == ParentRegion) {
383
384      // It's a top level block in our region
385      BranchInst *Term = cast<BranchInst>((*PI)->getTerminator());
386      for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
387        BasicBlock *Succ = Term->getSuccessor(i);
388        if (Succ != BB)
389          continue;
390
391        if (Visited.count(*PI)) {
392          // Normal forward edge
393          if (Term->isConditional()) {
394            // Try to treat it like an ELSE block
395            BasicBlock *Other = Term->getSuccessor(!i);
396            if (Visited.count(Other) && !Loops.count(Other) &&
397                !Pred.count(Other) && !Pred.count(*PI)) {
398
399              Pred[Other] = BoolFalse;
400              Pred[*PI] = BoolTrue;
401              continue;
402            }
403          }
404          Pred[*PI] = buildCondition(Term, i, false);
405
406        } else {
407          // Back edge
408          LPred[*PI] = buildCondition(Term, i, true);
409        }
410      }
411
412    } else {
413
414      // It's an exit from a sub region
415      while(R->getParent() != ParentRegion)
416        R = R->getParent();
417
418      // Edge from inside a subregion to its entry, ignore it
419      if (R == N)
420        continue;
421
422      BasicBlock *Entry = R->getEntry();
423      if (Visited.count(Entry))
424        Pred[Entry] = BoolTrue;
425      else
426        LPred[Entry] = BoolFalse;
427    }
428  }
429}
430
431/// \brief Collect various loop and predicate infos
432void StructurizeCFG::collectInfos() {
433  // Reset predicate
434  Predicates.clear();
435
436  // and loop infos
437  Loops.clear();
438  LoopPreds.clear();
439
440  // Reset the visited nodes
441  Visited.clear();
442
443  for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend();
444       OI != OE; ++OI) {
445
446    // Analyze all the conditions leading to a node
447    gatherPredicates(*OI);
448
449    // Remember that we've seen this node
450    Visited.insert((*OI)->getEntry());
451
452    // Find the last back edges
453    analyzeLoops(*OI);
454  }
455}
456
457/// \brief Insert the missing branch conditions
458void StructurizeCFG::insertConditions(bool Loops) {
459  BranchVector &Conds = Loops ? LoopConds : Conditions;
460  Value *Default = Loops ? BoolTrue : BoolFalse;
461  SSAUpdater PhiInserter;
462
463  for (BranchVector::iterator I = Conds.begin(),
464       E = Conds.end(); I != E; ++I) {
465
466    BranchInst *Term = *I;
467    assert(Term->isConditional());
468
469    BasicBlock *Parent = Term->getParent();
470    BasicBlock *SuccTrue = Term->getSuccessor(0);
471    BasicBlock *SuccFalse = Term->getSuccessor(1);
472
473    PhiInserter.Initialize(Boolean, "");
474    PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
475    PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
476
477    BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
478
479    NearestCommonDominator Dominator(DT);
480    Dominator.addBlock(Parent, false);
481
482    Value *ParentValue = 0;
483    for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
484         PI != PE; ++PI) {
485
486      if (PI->first == Parent) {
487        ParentValue = PI->second;
488        break;
489      }
490      PhiInserter.AddAvailableValue(PI->first, PI->second);
491      Dominator.addBlock(PI->first);
492    }
493
494    if (ParentValue) {
495      Term->setCondition(ParentValue);
496    } else {
497      if (!Dominator.wasResultExplicitMentioned())
498        PhiInserter.AddAvailableValue(Dominator.getResult(), Default);
499
500      Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
501    }
502  }
503}
504
505/// \brief Remove all PHI values coming from "From" into "To" and remember
506/// them in DeletedPhis
507void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
508  PhiMap &Map = DeletedPhis[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    while (Phi.getBasicBlockIndex(From) != -1) {
514      Value *Deleted = Phi.removeIncomingValue(From, false);
515      Map[&Phi].push_back(std::make_pair(From, Deleted));
516    }
517  }
518}
519
520/// \brief Add a dummy PHI value as soon as we knew the new predecessor
521void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
522  for (BasicBlock::iterator I = To->begin(), E = To->end();
523       I != E && isa<PHINode>(*I);) {
524
525    PHINode &Phi = cast<PHINode>(*I++);
526    Value *Undef = UndefValue::get(Phi.getType());
527    Phi.addIncoming(Undef, From);
528  }
529  AddedPhis[To].push_back(From);
530}
531
532/// \brief Add the real PHI value as soon as everything is set up
533void StructurizeCFG::setPhiValues() {
534  SSAUpdater Updater;
535  for (BB2BBVecMap::iterator AI = AddedPhis.begin(), AE = AddedPhis.end();
536       AI != AE; ++AI) {
537
538    BasicBlock *To = AI->first;
539    BBVector &From = AI->second;
540
541    if (!DeletedPhis.count(To))
542      continue;
543
544    PhiMap &Map = DeletedPhis[To];
545    for (PhiMap::iterator PI = Map.begin(), PE = Map.end();
546         PI != PE; ++PI) {
547
548      PHINode *Phi = PI->first;
549      Value *Undef = UndefValue::get(Phi->getType());
550      Updater.Initialize(Phi->getType(), "");
551      Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
552      Updater.AddAvailableValue(To, Undef);
553
554      NearestCommonDominator Dominator(DT);
555      Dominator.addBlock(To, false);
556      for (BBValueVector::iterator VI = PI->second.begin(),
557           VE = PI->second.end(); VI != VE; ++VI) {
558
559        Updater.AddAvailableValue(VI->first, VI->second);
560        Dominator.addBlock(VI->first);
561      }
562
563      if (!Dominator.wasResultExplicitMentioned())
564        Updater.AddAvailableValue(Dominator.getResult(), Undef);
565
566      for (BBVector::iterator FI = From.begin(), FE = From.end();
567           FI != FE; ++FI) {
568
569        int Idx = Phi->getBasicBlockIndex(*FI);
570        assert(Idx != -1);
571        Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(*FI));
572      }
573    }
574
575    DeletedPhis.erase(To);
576  }
577  assert(DeletedPhis.empty());
578}
579
580/// \brief Remove phi values from all successors and then remove the terminator.
581void StructurizeCFG::killTerminator(BasicBlock *BB) {
582  TerminatorInst *Term = BB->getTerminator();
583  if (!Term)
584    return;
585
586  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
587       SI != SE; ++SI) {
588
589    delPhiValues(BB, *SI);
590  }
591
592  Term->eraseFromParent();
593}
594
595/// \brief Let node exit(s) point to NewExit
596void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
597                                bool IncludeDominator) {
598  if (Node->isSubRegion()) {
599    Region *SubRegion = Node->getNodeAs<Region>();
600    BasicBlock *OldExit = SubRegion->getExit();
601    BasicBlock *Dominator = 0;
602
603    // Find all the edges from the sub region to the exit
604    for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit);
605         I != E;) {
606
607      BasicBlock *BB = *I++;
608      if (!SubRegion->contains(BB))
609        continue;
610
611      // Modify the edges to point to the new exit
612      delPhiValues(BB, OldExit);
613      BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
614      addPhiValues(BB, NewExit);
615
616      // Find the new dominator (if requested)
617      if (IncludeDominator) {
618        if (!Dominator)
619          Dominator = BB;
620        else
621          Dominator = DT->findNearestCommonDominator(Dominator, BB);
622      }
623    }
624
625    // Change the dominator (if requested)
626    if (Dominator)
627      DT->changeImmediateDominator(NewExit, Dominator);
628
629    // Update the region info
630    SubRegion->replaceExit(NewExit);
631
632  } else {
633    BasicBlock *BB = Node->getNodeAs<BasicBlock>();
634    killTerminator(BB);
635    BranchInst::Create(NewExit, BB);
636    addPhiValues(BB, NewExit);
637    if (IncludeDominator)
638      DT->changeImmediateDominator(NewExit, BB);
639  }
640}
641
642/// \brief Create a new flow node and update dominator tree and region info
643BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
644  LLVMContext &Context = Func->getContext();
645  BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
646                       Order.back()->getEntry();
647  BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
648                                        Func, Insert);
649  DT->addNewBlock(Flow, Dominator);
650  ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
651  return Flow;
652}
653
654/// \brief Create a new or reuse the previous node as flow node
655BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
656  BasicBlock *Entry = PrevNode->getEntry();
657
658  if (!PrevNode->isSubRegion()) {
659    killTerminator(Entry);
660    if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
661      return Entry;
662
663  }
664
665  // create a new flow node
666  BasicBlock *Flow = getNextFlow(Entry);
667
668  // and wire it up
669  changeExit(PrevNode, Flow, true);
670  PrevNode = ParentRegion->getBBNode(Flow);
671  return Flow;
672}
673
674/// \brief Returns the region exit if possible, otherwise just a new flow node
675BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
676                                        bool ExitUseAllowed) {
677  if (Order.empty() && ExitUseAllowed) {
678    BasicBlock *Exit = ParentRegion->getExit();
679    DT->changeImmediateDominator(Exit, Flow);
680    addPhiValues(Flow, Exit);
681    return Exit;
682  }
683  return getNextFlow(Flow);
684}
685
686/// \brief Set the previous node
687void StructurizeCFG::setPrevNode(BasicBlock *BB) {
688  PrevNode =  ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) : 0;
689}
690
691/// \brief Does BB dominate all the predicates of Node ?
692bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
693  BBPredicates &Preds = Predicates[Node->getEntry()];
694  for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
695       PI != PE; ++PI) {
696
697    if (!DT->dominates(BB, PI->first))
698      return false;
699  }
700  return true;
701}
702
703/// \brief Can we predict that this node will always be called?
704bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
705  BBPredicates &Preds = Predicates[Node->getEntry()];
706  bool Dominated = false;
707
708  // Regionentry is always true
709  if (PrevNode == 0)
710    return true;
711
712  for (BBPredicates::iterator I = Preds.begin(), E = Preds.end();
713       I != E; ++I) {
714
715    if (I->second != BoolTrue)
716      return false;
717
718    if (!Dominated && DT->dominates(I->first, PrevNode->getEntry()))
719      Dominated = true;
720  }
721
722  // TODO: The dominator check is too strict
723  return Dominated;
724}
725
726/// Take one node from the order vector and wire it up
727void StructurizeCFG::wireFlow(bool ExitUseAllowed,
728                              BasicBlock *LoopEnd) {
729  RegionNode *Node = Order.pop_back_val();
730  Visited.insert(Node->getEntry());
731
732  if (isPredictableTrue(Node)) {
733    // Just a linear flow
734    if (PrevNode) {
735      changeExit(PrevNode, Node->getEntry(), true);
736    }
737    PrevNode = Node;
738
739  } else {
740    // Insert extra prefix node (or reuse last one)
741    BasicBlock *Flow = needPrefix(false);
742
743    // Insert extra postfix node (or use exit instead)
744    BasicBlock *Entry = Node->getEntry();
745    BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
746
747    // let it point to entry and next block
748    Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
749    addPhiValues(Flow, Entry);
750    DT->changeImmediateDominator(Entry, Flow);
751
752    PrevNode = Node;
753    while (!Order.empty() && !Visited.count(LoopEnd) &&
754           dominatesPredicates(Entry, Order.back())) {
755      handleLoops(false, LoopEnd);
756    }
757
758    changeExit(PrevNode, Next, false);
759    setPrevNode(Next);
760  }
761}
762
763void StructurizeCFG::handleLoops(bool ExitUseAllowed,
764                                 BasicBlock *LoopEnd) {
765  RegionNode *Node = Order.back();
766  BasicBlock *LoopStart = Node->getEntry();
767
768  if (!Loops.count(LoopStart)) {
769    wireFlow(ExitUseAllowed, LoopEnd);
770    return;
771  }
772
773  if (!isPredictableTrue(Node))
774    LoopStart = needPrefix(true);
775
776  LoopEnd = Loops[Node->getEntry()];
777  wireFlow(false, LoopEnd);
778  while (!Visited.count(LoopEnd)) {
779    handleLoops(false, LoopEnd);
780  }
781
782  // If the start of the loop is the entry block, we can't branch to it so
783  // insert a new dummy entry block.
784  Function *LoopFunc = LoopStart->getParent();
785  if (LoopStart == &LoopFunc->getEntryBlock()) {
786    LoopStart->setName("entry.orig");
787
788    BasicBlock *NewEntry =
789      BasicBlock::Create(LoopStart->getContext(),
790                         "entry",
791                         LoopFunc,
792                         LoopStart);
793    BranchInst::Create(LoopStart, NewEntry);
794  }
795
796  // Create an extra loop end node
797  LoopEnd = needPrefix(false);
798  BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
799  LoopConds.push_back(BranchInst::Create(Next, LoopStart,
800                                         BoolUndef, LoopEnd));
801  addPhiValues(LoopEnd, LoopStart);
802  setPrevNode(Next);
803}
804
805/// After this function control flow looks like it should be, but
806/// branches and PHI nodes only have undefined conditions.
807void StructurizeCFG::createFlow() {
808  BasicBlock *Exit = ParentRegion->getExit();
809  bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
810
811  DeletedPhis.clear();
812  AddedPhis.clear();
813  Conditions.clear();
814  LoopConds.clear();
815
816  PrevNode = 0;
817  Visited.clear();
818
819  while (!Order.empty()) {
820    handleLoops(EntryDominatesExit, 0);
821  }
822
823  if (PrevNode)
824    changeExit(PrevNode, Exit, EntryDominatesExit);
825  else
826    assert(EntryDominatesExit);
827}
828
829/// Handle a rare case where the disintegrated nodes instructions
830/// no longer dominate all their uses. Not sure if this is really nessasary
831void StructurizeCFG::rebuildSSA() {
832  SSAUpdater Updater;
833  for (Region::block_iterator I = ParentRegion->block_begin(),
834                              E = ParentRegion->block_end();
835       I != E; ++I) {
836
837    BasicBlock *BB = *I;
838    for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
839         II != IE; ++II) {
840
841      bool Initialized = false;
842      for (Use *I = &II->use_begin().getUse(), *Next; I; I = Next) {
843
844        Next = I->getNext();
845
846        Instruction *User = cast<Instruction>(I->getUser());
847        if (User->getParent() == BB) {
848          continue;
849
850        } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
851          if (UserPN->getIncomingBlock(*I) == BB)
852            continue;
853        }
854
855        if (DT->dominates(II, User))
856          continue;
857
858        if (!Initialized) {
859          Value *Undef = UndefValue::get(II->getType());
860          Updater.Initialize(II->getType(), "");
861          Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
862          Updater.AddAvailableValue(BB, II);
863          Initialized = true;
864        }
865        Updater.RewriteUseAfterInsertions(*I);
866      }
867    }
868  }
869}
870
871/// \brief Run the transformation for each region found
872bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
873  if (R->isTopLevelRegion())
874    return false;
875
876  Func = R->getEntry()->getParent();
877  ParentRegion = R;
878
879  DT = &getAnalysis<DominatorTree>();
880
881  orderNodes();
882  collectInfos();
883  createFlow();
884  insertConditions(false);
885  insertConditions(true);
886  setPhiValues();
887  rebuildSSA();
888
889  // Cleanup
890  Order.clear();
891  Visited.clear();
892  DeletedPhis.clear();
893  AddedPhis.clear();
894  Predicates.clear();
895  Conditions.clear();
896  Loops.clear();
897  LoopPreds.clear();
898  LoopConds.clear();
899
900  return true;
901}
902
903/// \brief Create the pass
904Pass *llvm::createStructurizeCFGPass() {
905  return new StructurizeCFG();
906}
907