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