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