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