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