LLVM  7.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"
43 #include "llvm/Transforms/Utils.h"
45 #include <algorithm>
46 #include <cassert>
47 #include <utility>
48 
49 using namespace llvm;
50 using namespace llvm::PatternMatch;
51 
52 #define DEBUG_TYPE "structurizecfg"
53 
54 // The name for newly created blocks.
55 static const char *const FlowBlockName = "Flow";
56 
57 namespace {
58 
59 static cl::opt<bool> ForceSkipUniformRegions(
60  "structurizecfg-skip-uniform-regions",
61  cl::Hidden,
62  cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
63  cl::init(false));
64 
65 // Definition of the complex types used in this pass.
66 
67 using BBValuePair = std::pair<BasicBlock *, Value *>;
68 
69 using RNVector = SmallVector<RegionNode *, 8>;
70 using BBVector = SmallVector<BasicBlock *, 8>;
71 using BranchVector = SmallVector<BranchInst *, 8>;
72 using BBValueVector = SmallVector<BBValuePair, 2>;
73 
74 using BBSet = SmallPtrSet<BasicBlock *, 8>;
75 
77 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
78 
79 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
80 using BBPredicates = DenseMap<BasicBlock *, Value *>;
83 
84 /// Finds the nearest common dominator of a set of BasicBlocks.
85 ///
86 /// For every BB you add to the set, you can specify whether we "remember" the
87 /// block. When you get the common dominator, you can also ask whether it's one
88 /// of the blocks we remembered.
89 class NearestCommonDominator {
90  DominatorTree *DT;
91  BasicBlock *Result = nullptr;
92  bool ResultIsRemembered = false;
93 
94  /// Add BB to the resulting dominator.
95  void addBlock(BasicBlock *BB, bool Remember) {
96  if (!Result) {
97  Result = BB;
98  ResultIsRemembered = Remember;
99  return;
100  }
101 
102  BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
103  if (NewResult != Result)
104  ResultIsRemembered = false;
105  if (NewResult == BB)
106  ResultIsRemembered |= Remember;
107  Result = NewResult;
108  }
109 
110 public:
111  explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
112 
113  void addBlock(BasicBlock *BB) {
114  addBlock(BB, /* Remember = */ false);
115  }
116 
117  void addAndRememberBlock(BasicBlock *BB) {
118  addBlock(BB, /* Remember = */ true);
119  }
120 
121  /// Get the nearest common dominator of all the BBs added via addBlock() and
122  /// addAndRememberBlock().
123  BasicBlock *result() { return Result; }
124 
125  /// Is the BB returned by getResult() one of the blocks we added to the set
126  /// with addAndRememberBlock()?
127  bool resultIsRememberedBlock() { return ResultIsRemembered; }
128 };
129 
130 /// @brief Transforms the control flow graph on one single entry/exit region
131 /// at a time.
132 ///
133 /// After the transform all "If"/"Then"/"Else" style control flow looks like
134 /// this:
135 ///
136 /// \verbatim
137 /// 1
138 /// ||
139 /// | |
140 /// 2 |
141 /// | /
142 /// |/
143 /// 3
144 /// || Where:
145 /// | | 1 = "If" block, calculates the condition
146 /// 4 | 2 = "Then" subregion, runs if the condition is true
147 /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
148 /// |/ 4 = "Else" optional subregion, runs if the condition is false
149 /// 5 5 = "End" block, also rejoins the control flow
150 /// \endverbatim
151 ///
152 /// Control flow is expressed as a branch where the true exit goes into the
153 /// "Then"/"Else" region, while the false exit skips the region
154 /// The condition for the optional "Else" region is expressed as a PHI node.
155 /// The incoming values of the PHI node are true for the "If" edge and false
156 /// for the "Then" edge.
157 ///
158 /// Additionally to that even complicated loops look like this:
159 ///
160 /// \verbatim
161 /// 1
162 /// ||
163 /// | |
164 /// 2 ^ Where:
165 /// | / 1 = "Entry" block
166 /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block
167 /// 3 3 = "Flow" block, with back edge to entry block
168 /// |
169 /// \endverbatim
170 ///
171 /// The back edge of the "Flow" block is always on the false side of the branch
172 /// while the true side continues the general flow. So the loop condition
173 /// consist of a network of PHI nodes where the true incoming values expresses
174 /// breaks and the false values expresses continue states.
175 class StructurizeCFG : public RegionPass {
176  bool SkipUniformRegions;
177 
178  Type *Boolean;
179  ConstantInt *BoolTrue;
180  ConstantInt *BoolFalse;
181  UndefValue *BoolUndef;
182 
183  Function *Func;
184  Region *ParentRegion;
185 
186  DivergenceAnalysis *DA;
187  DominatorTree *DT;
188  LoopInfo *LI;
189 
191  BBSet Visited;
192 
193  BBPhiMap DeletedPhis;
194  BB2BBVecMap AddedPhis;
195 
196  PredMap Predicates;
197  BranchVector Conditions;
198 
199  BB2BBMap Loops;
200  PredMap LoopPreds;
201  BranchVector LoopConds;
202 
203  RegionNode *PrevNode;
204 
205  void orderNodes();
206 
207  void analyzeLoops(RegionNode *N);
208 
209  Value *invert(Value *Condition);
210 
211  Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
212 
213  void gatherPredicates(RegionNode *N);
214 
215  void collectInfos();
216 
217  void insertConditions(bool Loops);
218 
219  void delPhiValues(BasicBlock *From, BasicBlock *To);
220 
221  void addPhiValues(BasicBlock *From, BasicBlock *To);
222 
223  void setPhiValues();
224 
225  void killTerminator(BasicBlock *BB);
226 
227  void changeExit(RegionNode *Node, BasicBlock *NewExit,
228  bool IncludeDominator);
229 
230  BasicBlock *getNextFlow(BasicBlock *Dominator);
231 
232  BasicBlock *needPrefix(bool NeedEmpty);
233 
234  BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
235 
236  void setPrevNode(BasicBlock *BB);
237 
238  bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
239 
240  bool isPredictableTrue(RegionNode *Node);
241 
242  void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
243 
244  void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
245 
246  void createFlow();
247 
248  void rebuildSSA();
249 
250 public:
251  static char ID;
252 
253  explicit StructurizeCFG(bool SkipUniformRegions_ = false)
254  : RegionPass(ID),
255  SkipUniformRegions(SkipUniformRegions_) {
256  if (ForceSkipUniformRegions.getNumOccurrences())
257  SkipUniformRegions = ForceSkipUniformRegions.getValue();
259  }
260 
261  bool doInitialization(Region *R, RGPassManager &RGM) override;
262 
263  bool runOnRegion(Region *R, RGPassManager &RGM) override;
264 
265  StringRef getPassName() const override { return "Structurize control flow"; }
266 
267  void getAnalysisUsage(AnalysisUsage &AU) const override {
268  if (SkipUniformRegions)
273 
276  }
277 };
278 
279 } // end anonymous namespace
280 
281 char StructurizeCFG::ID = 0;
282 
283 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
284  false, false)
286 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
289 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
290  false, false)
291 
292 /// \brief Initialize the types and constants used in the pass
293 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
294  LLVMContext &Context = R->getEntry()->getContext();
295 
296  Boolean = Type::getInt1Ty(Context);
297  BoolTrue = ConstantInt::getTrue(Context);
298  BoolFalse = ConstantInt::getFalse(Context);
299  BoolUndef = UndefValue::get(Boolean);
300 
301  return false;
302 }
303 
304 /// \brief Build up the general order of nodes
305 void StructurizeCFG::orderNodes() {
306  ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
308 
309  // The reverse post-order traversal of the list gives us an ordering close
310  // to what we want. The only problem with it is that sometimes backedges
311  // for outer loops will be visited before backedges for inner loops.
312  for (RegionNode *RN : RPOT) {
313  BasicBlock *BB = RN->getEntry();
314  Loop *Loop = LI->getLoopFor(BB);
315  ++LoopBlocks[Loop];
316  }
317 
318  unsigned CurrentLoopDepth = 0;
319  Loop *CurrentLoop = nullptr;
320  for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
321  BasicBlock *BB = (*I)->getEntry();
322  unsigned LoopDepth = LI->getLoopDepth(BB);
323 
324  if (is_contained(Order, *I))
325  continue;
326 
327  if (LoopDepth < CurrentLoopDepth) {
328  // Make sure we have visited all blocks in this loop before moving back to
329  // the outer loop.
330 
331  auto LoopI = I;
332  while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
333  LoopI++;
334  BasicBlock *LoopBB = (*LoopI)->getEntry();
335  if (LI->getLoopFor(LoopBB) == CurrentLoop) {
336  --BlockCount;
337  Order.push_back(*LoopI);
338  }
339  }
340  }
341 
342  CurrentLoop = LI->getLoopFor(BB);
343  if (CurrentLoop)
344  LoopBlocks[CurrentLoop]--;
345 
346  CurrentLoopDepth = LoopDepth;
347  Order.push_back(*I);
348  }
349 
350  // This pass originally used a post-order traversal and then operated on
351  // the list in reverse. Now that we are using a reverse post-order traversal
352  // rather than re-working the whole pass to operate on the list in order,
353  // we just reverse the list and continue to operate on it in reverse.
354  std::reverse(Order.begin(), Order.end());
355 }
356 
357 /// \brief Determine the end of the loops
358 void StructurizeCFG::analyzeLoops(RegionNode *N) {
359  if (N->isSubRegion()) {
360  // Test for exit as back edge
361  BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
362  if (Visited.count(Exit))
363  Loops[Exit] = N->getEntry();
364 
365  } else {
366  // Test for successors as back edge
367  BasicBlock *BB = N->getNodeAs<BasicBlock>();
368  BranchInst *Term = cast<BranchInst>(BB->getTerminator());
369 
370  for (BasicBlock *Succ : Term->successors())
371  if (Visited.count(Succ))
372  Loops[Succ] = BB;
373  }
374 }
375 
376 /// \brief Invert the given condition
377 Value *StructurizeCFG::invert(Value *Condition) {
378  // First: Check if it's a constant
379  if (Constant *C = dyn_cast<Constant>(Condition))
380  return ConstantExpr::getNot(C);
381 
382  // Second: If the condition is already inverted, return the original value
383  if (match(Condition, m_Not(m_Value(Condition))))
384  return Condition;
385 
386  if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
387  // Third: Check all the users for an invert
388  BasicBlock *Parent = Inst->getParent();
389  for (User *U : Condition->users())
390  if (Instruction *I = dyn_cast<Instruction>(U))
391  if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
392  return I;
393 
394  // Last option: Create a new instruction
395  return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
396  }
397 
398  if (Argument *Arg = dyn_cast<Argument>(Condition)) {
399  BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
400  return BinaryOperator::CreateNot(Condition,
401  Arg->getName() + ".inv",
402  EntryBlock.getTerminator());
403  }
404 
405  llvm_unreachable("Unhandled condition to invert");
406 }
407 
408 /// \brief Build the condition for one edge
409 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
410  bool Invert) {
411  Value *Cond = Invert ? BoolFalse : BoolTrue;
412  if (Term->isConditional()) {
413  Cond = Term->getCondition();
414 
415  if (Idx != (unsigned)Invert)
416  Cond = invert(Cond);
417  }
418  return Cond;
419 }
420 
421 /// \brief Analyze the predecessors of each block and build up predicates
422 void StructurizeCFG::gatherPredicates(RegionNode *N) {
423  RegionInfo *RI = ParentRegion->getRegionInfo();
424  BasicBlock *BB = N->getEntry();
425  BBPredicates &Pred = Predicates[BB];
426  BBPredicates &LPred = LoopPreds[BB];
427 
428  for (BasicBlock *P : predecessors(BB)) {
429  // Ignore it if it's a branch from outside into our region entry
430  if (!ParentRegion->contains(P))
431  continue;
432 
433  Region *R = RI->getRegionFor(P);
434  if (R == ParentRegion) {
435  // It's a top level block in our region
436  BranchInst *Term = cast<BranchInst>(P->getTerminator());
437  for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
438  BasicBlock *Succ = Term->getSuccessor(i);
439  if (Succ != BB)
440  continue;
441 
442  if (Visited.count(P)) {
443  // Normal forward edge
444  if (Term->isConditional()) {
445  // Try to treat it like an ELSE block
446  BasicBlock *Other = Term->getSuccessor(!i);
447  if (Visited.count(Other) && !Loops.count(Other) &&
448  !Pred.count(Other) && !Pred.count(P)) {
449 
450  Pred[Other] = BoolFalse;
451  Pred[P] = BoolTrue;
452  continue;
453  }
454  }
455  Pred[P] = buildCondition(Term, i, false);
456  } else {
457  // Back edge
458  LPred[P] = buildCondition(Term, i, true);
459  }
460  }
461  } else {
462  // It's an exit from a sub region
463  while (R->getParent() != ParentRegion)
464  R = R->getParent();
465 
466  // Edge from inside a subregion to its entry, ignore it
467  if (*R == *N)
468  continue;
469 
470  BasicBlock *Entry = R->getEntry();
471  if (Visited.count(Entry))
472  Pred[Entry] = BoolTrue;
473  else
474  LPred[Entry] = BoolFalse;
475  }
476  }
477 }
478 
479 /// \brief Collect various loop and predicate infos
480 void StructurizeCFG::collectInfos() {
481  // Reset predicate
482  Predicates.clear();
483 
484  // and loop infos
485  Loops.clear();
486  LoopPreds.clear();
487 
488  // Reset the visited nodes
489  Visited.clear();
490 
491  for (RegionNode *RN : reverse(Order)) {
492  DEBUG(dbgs() << "Visiting: "
493  << (RN->isSubRegion() ? "SubRegion with entry: " : "")
494  << RN->getEntry()->getName() << " Loop Depth: "
495  << LI->getLoopDepth(RN->getEntry()) << "\n");
496 
497  // Analyze all the conditions leading to a node
498  gatherPredicates(RN);
499 
500  // Remember that we've seen this node
501  Visited.insert(RN->getEntry());
502 
503  // Find the last back edges
504  analyzeLoops(RN);
505  }
506 }
507 
508 /// \brief Insert the missing branch conditions
509 void StructurizeCFG::insertConditions(bool Loops) {
510  BranchVector &Conds = Loops ? LoopConds : Conditions;
511  Value *Default = Loops ? BoolTrue : BoolFalse;
512  SSAUpdater PhiInserter;
513 
514  for (BranchInst *Term : Conds) {
515  assert(Term->isConditional());
516 
517  BasicBlock *Parent = Term->getParent();
518  BasicBlock *SuccTrue = Term->getSuccessor(0);
519  BasicBlock *SuccFalse = Term->getSuccessor(1);
520 
521  PhiInserter.Initialize(Boolean, "");
522  PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
523  PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
524 
525  BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
526 
527  NearestCommonDominator Dominator(DT);
528  Dominator.addBlock(Parent);
529 
530  Value *ParentValue = nullptr;
531  for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
532  BasicBlock *BB = BBAndPred.first;
533  Value *Pred = BBAndPred.second;
534 
535  if (BB == Parent) {
536  ParentValue = Pred;
537  break;
538  }
539  PhiInserter.AddAvailableValue(BB, Pred);
540  Dominator.addAndRememberBlock(BB);
541  }
542 
543  if (ParentValue) {
544  Term->setCondition(ParentValue);
545  } else {
546  if (!Dominator.resultIsRememberedBlock())
547  PhiInserter.AddAvailableValue(Dominator.result(), Default);
548 
549  Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
550  }
551  }
552 }
553 
554 /// \brief Remove all PHI values coming from "From" into "To" and remember
555 /// them in DeletedPhis
556 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
557  PhiMap &Map = DeletedPhis[To];
558  for (PHINode &Phi : To->phis()) {
559  while (Phi.getBasicBlockIndex(From) != -1) {
560  Value *Deleted = Phi.removeIncomingValue(From, false);
561  Map[&Phi].push_back(std::make_pair(From, Deleted));
562  }
563  }
564 }
565 
566 /// \brief Add a dummy PHI value as soon as we knew the new predecessor
567 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
568  for (PHINode &Phi : To->phis()) {
569  Value *Undef = UndefValue::get(Phi.getType());
570  Phi.addIncoming(Undef, From);
571  }
572  AddedPhis[To].push_back(From);
573 }
574 
575 /// \brief Add the real PHI value as soon as everything is set up
576 void StructurizeCFG::setPhiValues() {
577  SSAUpdater Updater;
578  for (const auto &AddedPhi : AddedPhis) {
579  BasicBlock *To = AddedPhi.first;
580  const BBVector &From = AddedPhi.second;
581 
582  if (!DeletedPhis.count(To))
583  continue;
584 
585  PhiMap &Map = DeletedPhis[To];
586  for (const auto &PI : Map) {
587  PHINode *Phi = PI.first;
588  Value *Undef = UndefValue::get(Phi->getType());
589  Updater.Initialize(Phi->getType(), "");
590  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
591  Updater.AddAvailableValue(To, Undef);
592 
593  NearestCommonDominator Dominator(DT);
594  Dominator.addBlock(To);
595  for (const auto &VI : PI.second) {
596  Updater.AddAvailableValue(VI.first, VI.second);
597  Dominator.addAndRememberBlock(VI.first);
598  }
599 
600  if (!Dominator.resultIsRememberedBlock())
601  Updater.AddAvailableValue(Dominator.result(), Undef);
602 
603  for (BasicBlock *FI : From) {
604  int Idx = Phi->getBasicBlockIndex(FI);
605  assert(Idx != -1);
606  Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI));
607  }
608  }
609 
610  DeletedPhis.erase(To);
611  }
612  assert(DeletedPhis.empty());
613 }
614 
615 /// \brief Remove phi values from all successors and then remove the terminator.
616 void StructurizeCFG::killTerminator(BasicBlock *BB) {
617  TerminatorInst *Term = BB->getTerminator();
618  if (!Term)
619  return;
620 
621  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
622  SI != SE; ++SI)
623  delPhiValues(BB, *SI);
624 
625  if (DA)
626  DA->removeValue(Term);
627  Term->eraseFromParent();
628 }
629 
630 /// \brief Let node exit(s) point to NewExit
631 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
632  bool IncludeDominator) {
633  if (Node->isSubRegion()) {
634  Region *SubRegion = Node->getNodeAs<Region>();
635  BasicBlock *OldExit = SubRegion->getExit();
636  BasicBlock *Dominator = nullptr;
637 
638  // Find all the edges from the sub region to the exit
639  for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) {
640  // Incrememt BBI before mucking with BB's terminator.
641  BasicBlock *BB = *BBI++;
642 
643  if (!SubRegion->contains(BB))
644  continue;
645 
646  // Modify the edges to point to the new exit
647  delPhiValues(BB, OldExit);
648  BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
649  addPhiValues(BB, NewExit);
650 
651  // Find the new dominator (if requested)
652  if (IncludeDominator) {
653  if (!Dominator)
654  Dominator = BB;
655  else
656  Dominator = DT->findNearestCommonDominator(Dominator, BB);
657  }
658  }
659 
660  // Change the dominator (if requested)
661  if (Dominator)
662  DT->changeImmediateDominator(NewExit, Dominator);
663 
664  // Update the region info
665  SubRegion->replaceExit(NewExit);
666  } else {
667  BasicBlock *BB = Node->getNodeAs<BasicBlock>();
668  killTerminator(BB);
669  BranchInst::Create(NewExit, BB);
670  addPhiValues(BB, NewExit);
671  if (IncludeDominator)
672  DT->changeImmediateDominator(NewExit, BB);
673  }
674 }
675 
676 /// \brief Create a new flow node and update dominator tree and region info
677 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
678  LLVMContext &Context = Func->getContext();
679  BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
680  Order.back()->getEntry();
681  BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
682  Func, Insert);
683  DT->addNewBlock(Flow, Dominator);
684  ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
685  return Flow;
686 }
687 
688 /// \brief Create a new or reuse the previous node as flow node
689 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
690  BasicBlock *Entry = PrevNode->getEntry();
691 
692  if (!PrevNode->isSubRegion()) {
693  killTerminator(Entry);
694  if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
695  return Entry;
696  }
697 
698  // create a new flow node
699  BasicBlock *Flow = getNextFlow(Entry);
700 
701  // and wire it up
702  changeExit(PrevNode, Flow, true);
703  PrevNode = ParentRegion->getBBNode(Flow);
704  return Flow;
705 }
706 
707 /// \brief Returns the region exit if possible, otherwise just a new flow node
708 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
709  bool ExitUseAllowed) {
710  if (!Order.empty() || !ExitUseAllowed)
711  return getNextFlow(Flow);
712 
713  BasicBlock *Exit = ParentRegion->getExit();
714  DT->changeImmediateDominator(Exit, Flow);
715  addPhiValues(Flow, Exit);
716  return Exit;
717 }
718 
719 /// \brief Set the previous node
720 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
721  PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
722  : nullptr;
723 }
724 
725 /// \brief Does BB dominate all the predicates of Node?
726 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
727  BBPredicates &Preds = Predicates[Node->getEntry()];
728  return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
729  return DT->dominates(BB, Pred.first);
730  });
731 }
732 
733 /// \brief Can we predict that this node will always be called?
734 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
735  BBPredicates &Preds = Predicates[Node->getEntry()];
736  bool Dominated = false;
737 
738  // Regionentry is always true
739  if (!PrevNode)
740  return true;
741 
742  for (std::pair<BasicBlock*, Value*> Pred : Preds) {
743  BasicBlock *BB = Pred.first;
744  Value *V = Pred.second;
745 
746  if (V != BoolTrue)
747  return false;
748 
749  if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
750  Dominated = true;
751  }
752 
753  // TODO: The dominator check is too strict
754  return Dominated;
755 }
756 
757 /// Take one node from the order vector and wire it up
758 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
759  BasicBlock *LoopEnd) {
760  RegionNode *Node = Order.pop_back_val();
761  Visited.insert(Node->getEntry());
762 
763  if (isPredictableTrue(Node)) {
764  // Just a linear flow
765  if (PrevNode) {
766  changeExit(PrevNode, Node->getEntry(), true);
767  }
768  PrevNode = Node;
769  } else {
770  // Insert extra prefix node (or reuse last one)
771  BasicBlock *Flow = needPrefix(false);
772 
773  // Insert extra postfix node (or use exit instead)
774  BasicBlock *Entry = Node->getEntry();
775  BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
776 
777  // let it point to entry and next block
778  Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
779  addPhiValues(Flow, Entry);
780  DT->changeImmediateDominator(Entry, Flow);
781 
782  PrevNode = Node;
783  while (!Order.empty() && !Visited.count(LoopEnd) &&
784  dominatesPredicates(Entry, Order.back())) {
785  handleLoops(false, LoopEnd);
786  }
787 
788  changeExit(PrevNode, Next, false);
789  setPrevNode(Next);
790  }
791 }
792 
793 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
794  BasicBlock *LoopEnd) {
795  RegionNode *Node = Order.back();
796  BasicBlock *LoopStart = Node->getEntry();
797 
798  if (!Loops.count(LoopStart)) {
799  wireFlow(ExitUseAllowed, LoopEnd);
800  return;
801  }
802 
803  if (!isPredictableTrue(Node))
804  LoopStart = needPrefix(true);
805 
806  LoopEnd = Loops[Node->getEntry()];
807  wireFlow(false, LoopEnd);
808  while (!Visited.count(LoopEnd)) {
809  handleLoops(false, LoopEnd);
810  }
811 
812  // If the start of the loop is the entry block, we can't branch to it so
813  // insert a new dummy entry block.
814  Function *LoopFunc = LoopStart->getParent();
815  if (LoopStart == &LoopFunc->getEntryBlock()) {
816  LoopStart->setName("entry.orig");
817 
818  BasicBlock *NewEntry =
819  BasicBlock::Create(LoopStart->getContext(),
820  "entry",
821  LoopFunc,
822  LoopStart);
823  BranchInst::Create(LoopStart, NewEntry);
824  DT->setNewRoot(NewEntry);
825  }
826 
827  // Create an extra loop end node
828  LoopEnd = needPrefix(false);
829  BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
830  LoopConds.push_back(BranchInst::Create(Next, LoopStart,
831  BoolUndef, LoopEnd));
832  addPhiValues(LoopEnd, LoopStart);
833  setPrevNode(Next);
834 }
835 
836 /// After this function control flow looks like it should be, but
837 /// branches and PHI nodes only have undefined conditions.
838 void StructurizeCFG::createFlow() {
839  BasicBlock *Exit = ParentRegion->getExit();
840  bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
841 
842  DeletedPhis.clear();
843  AddedPhis.clear();
844  Conditions.clear();
845  LoopConds.clear();
846 
847  PrevNode = nullptr;
848  Visited.clear();
849 
850  while (!Order.empty()) {
851  handleLoops(EntryDominatesExit, nullptr);
852  }
853 
854  if (PrevNode)
855  changeExit(PrevNode, Exit, EntryDominatesExit);
856  else
857  assert(EntryDominatesExit);
858 }
859 
860 /// Handle a rare case where the disintegrated nodes instructions
861 /// no longer dominate all their uses. Not sure if this is really nessasary
862 void StructurizeCFG::rebuildSSA() {
863  SSAUpdater Updater;
864  for (BasicBlock *BB : ParentRegion->blocks())
865  for (Instruction &I : *BB) {
866  bool Initialized = false;
867  // We may modify the use list as we iterate over it, so be careful to
868  // compute the next element in the use list at the top of the loop.
869  for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) {
870  Use &U = *UI++;
871  Instruction *User = cast<Instruction>(U.getUser());
872  if (User->getParent() == BB) {
873  continue;
874  } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
875  if (UserPN->getIncomingBlock(U) == BB)
876  continue;
877  }
878 
879  if (DT->dominates(&I, User))
880  continue;
881 
882  if (!Initialized) {
883  Value *Undef = UndefValue::get(I.getType());
884  Updater.Initialize(I.getType(), "");
885  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
886  Updater.AddAvailableValue(BB, &I);
887  Initialized = true;
888  }
889  Updater.RewriteUseAfterInsertions(U);
890  }
891  }
892 }
893 
894 static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
895  const DivergenceAnalysis &DA) {
896  for (auto E : R->elements()) {
897  if (!E->isSubRegion()) {
898  auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
899  if (!Br || !Br->isConditional())
900  continue;
901 
902  if (!DA.isUniform(Br))
903  return false;
904  DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
905  << " has uniform terminator\n");
906  } else {
907  // Explicitly refuse to treat regions as uniform if they have non-uniform
908  // subregions. We cannot rely on DivergenceAnalysis for branches in
909  // subregions because those branches may have been removed and re-created,
910  // so we look for our metadata instead.
911  //
912  // Warning: It would be nice to treat regions as uniform based only on
913  // their direct child basic blocks' terminators, regardless of whether
914  // subregions are uniform or not. However, this requires a very careful
915  // look at SIAnnotateControlFlow to make sure nothing breaks there.
916  for (auto BB : E->getNodeAs<Region>()->blocks()) {
917  auto Br = dyn_cast<BranchInst>(BB->getTerminator());
918  if (!Br || !Br->isConditional())
919  continue;
920 
921  if (!Br->getMetadata(UniformMDKindID))
922  return false;
923  }
924  }
925  }
926  return true;
927 }
928 
929 /// \brief Run the transformation for each region found
930 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
931  if (R->isTopLevelRegion())
932  return false;
933 
934  DA = nullptr;
935 
936  if (SkipUniformRegions) {
937  // TODO: We could probably be smarter here with how we handle sub-regions.
938  // We currently rely on the fact that metadata is set by earlier invocations
939  // of the pass on sub-regions, and that this metadata doesn't get lost --
940  // but we shouldn't rely on metadata for correctness!
941  unsigned UniformMDKindID =
942  R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
943  DA = &getAnalysis<DivergenceAnalysis>();
944 
945  if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
946  DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
947 
948  // Mark all direct child block terminators as having been treated as
949  // uniform. To account for a possible future in which non-uniform
950  // sub-regions are treated more cleverly, indirect children are not
951  // marked as uniform.
952  MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
953  for (RegionNode *E : R->elements()) {
954  if (E->isSubRegion())
955  continue;
956 
957  if (Instruction *Term = E->getEntry()->getTerminator())
958  Term->setMetadata(UniformMDKindID, MD);
959  }
960 
961  return false;
962  }
963  }
964 
965  Func = R->getEntry()->getParent();
966  ParentRegion = R;
967 
968  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
969  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
970 
971  orderNodes();
972  collectInfos();
973  createFlow();
974  insertConditions(false);
975  insertConditions(true);
976  setPhiValues();
977  rebuildSSA();
978 
979  // Cleanup
980  Order.clear();
981  Visited.clear();
982  DeletedPhis.clear();
983  AddedPhis.clear();
984  Predicates.clear();
985  Conditions.clear();
986  Loops.clear();
987  LoopPreds.clear();
988  LoopConds.clear();
989 
990  return true;
991 }
992 
993 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
994  return new StructurizeCFG(SkipUniformRegions);
995 }
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:67
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:574
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
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:846
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
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:1260
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:295
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:767
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:237
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:142
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:21
bool isUniform(const Value *V) const
const BasicBlock & getEntryBlock() const
Definition: Function.h:621
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:55
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:202
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
int getNumOccurrences() const
Definition: CommandLine.h:367
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:481
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:2171
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:1382
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:1222
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:862
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:567
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:405
static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const DivergenceAnalysis &DA)
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:224
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
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:308
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:254
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.
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
const BasicBlock * getParent() const
Definition: Instruction.h:67
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:905