LLVM  14.0.0git
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 
10 #include "llvm/ADT/DenseMap.h"
11 #include "llvm/ADT/MapVector.h"
12 #include "llvm/ADT/SCCIterator.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/SmallVector.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/PassManager.h"
33 #include "llvm/IR/PatternMatch.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/Use.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/IR/ValueHandle.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Debug.h"
46 #include "llvm/Transforms/Scalar.h"
47 #include "llvm/Transforms/Utils.h"
50 #include <algorithm>
51 #include <cassert>
52 #include <utility>
53 
54 using namespace llvm;
55 using namespace llvm::PatternMatch;
56 
57 #define DEBUG_TYPE "structurizecfg"
58 
59 // The name for newly created blocks.
60 const char FlowBlockName[] = "Flow";
61 
62 namespace {
63 
64 static cl::opt<bool> ForceSkipUniformRegions(
65  "structurizecfg-skip-uniform-regions",
66  cl::Hidden,
67  cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
68  cl::init(false));
69 
70 static cl::opt<bool>
71  RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden,
72  cl::desc("Allow relaxed uniform region checks"),
73  cl::init(true));
74 
75 // Definition of the complex types used in this pass.
76 
77 using BBValuePair = std::pair<BasicBlock *, Value *>;
78 
79 using RNVector = SmallVector<RegionNode *, 8>;
80 using BBVector = SmallVector<BasicBlock *, 8>;
81 using BranchVector = SmallVector<BranchInst *, 8>;
82 using BBValueVector = SmallVector<BBValuePair, 2>;
83 
84 using BBSet = SmallPtrSet<BasicBlock *, 8>;
85 
87 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
88 
89 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
93 
94 // A traits type that is intended to be used in graph algorithms. The graph
95 // traits starts at an entry node, and traverses the RegionNodes that are in
96 // the Nodes set.
97 struct SubGraphTraits {
98  using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;
99  using BaseSuccIterator = GraphTraits<RegionNode *>::ChildIteratorType;
100 
101  // This wraps a set of Nodes into the iterator, so we know which edges to
102  // filter out.
103  class WrappedSuccIterator
104  : public iterator_adaptor_base<
105  WrappedSuccIterator, BaseSuccIterator,
106  typename std::iterator_traits<BaseSuccIterator>::iterator_category,
107  NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
109 
110  public:
111  WrappedSuccIterator(BaseSuccIterator It, SmallDenseSet<RegionNode *> *Nodes)
112  : iterator_adaptor_base(It), Nodes(Nodes) {}
113 
114  NodeRef operator*() const { return {*I, Nodes}; }
115  };
116 
117  static bool filterAll(const NodeRef &N) { return true; }
118  static bool filterSet(const NodeRef &N) { return N.second->count(N.first); }
119 
120  using ChildIteratorType =
121  filter_iterator<WrappedSuccIterator, bool (*)(const NodeRef &)>;
122 
123  static NodeRef getEntryNode(Region *R) {
124  return {GraphTraits<Region *>::getEntryNode(R), nullptr};
125  }
126 
127  static NodeRef getEntryNode(NodeRef N) { return N; }
128 
130  auto *filter = N.second ? &filterSet : &filterAll;
131  return make_filter_range(
132  make_range<WrappedSuccIterator>(
133  {GraphTraits<RegionNode *>::child_begin(N.first), N.second},
134  {GraphTraits<RegionNode *>::child_end(N.first), N.second}),
135  filter);
136  }
137 
138  static ChildIteratorType child_begin(const NodeRef &N) {
139  return children(N).begin();
140  }
141 
142  static ChildIteratorType child_end(const NodeRef &N) {
143  return children(N).end();
144  }
145 };
146 
147 /// Finds the nearest common dominator of a set of BasicBlocks.
148 ///
149 /// For every BB you add to the set, you can specify whether we "remember" the
150 /// block. When you get the common dominator, you can also ask whether it's one
151 /// of the blocks we remembered.
152 class NearestCommonDominator {
153  DominatorTree *DT;
154  BasicBlock *Result = nullptr;
155  bool ResultIsRemembered = false;
156 
157  /// Add BB to the resulting dominator.
158  void addBlock(BasicBlock *BB, bool Remember) {
159  if (!Result) {
160  Result = BB;
161  ResultIsRemembered = Remember;
162  return;
163  }
164 
165  BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
166  if (NewResult != Result)
167  ResultIsRemembered = false;
168  if (NewResult == BB)
169  ResultIsRemembered |= Remember;
170  Result = NewResult;
171  }
172 
173 public:
174  explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
175 
176  void addBlock(BasicBlock *BB) {
177  addBlock(BB, /* Remember = */ false);
178  }
179 
180  void addAndRememberBlock(BasicBlock *BB) {
181  addBlock(BB, /* Remember = */ true);
182  }
183 
184  /// Get the nearest common dominator of all the BBs added via addBlock() and
185  /// addAndRememberBlock().
186  BasicBlock *result() { return Result; }
187 
188  /// Is the BB returned by getResult() one of the blocks we added to the set
189  /// with addAndRememberBlock()?
190  bool resultIsRememberedBlock() { return ResultIsRemembered; }
191 };
192 
193 /// Transforms the control flow graph on one single entry/exit region
194 /// at a time.
195 ///
196 /// After the transform all "If"/"Then"/"Else" style control flow looks like
197 /// this:
198 ///
199 /// \verbatim
200 /// 1
201 /// ||
202 /// | |
203 /// 2 |
204 /// | /
205 /// |/
206 /// 3
207 /// || Where:
208 /// | | 1 = "If" block, calculates the condition
209 /// 4 | 2 = "Then" subregion, runs if the condition is true
210 /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
211 /// |/ 4 = "Else" optional subregion, runs if the condition is false
212 /// 5 5 = "End" block, also rejoins the control flow
213 /// \endverbatim
214 ///
215 /// Control flow is expressed as a branch where the true exit goes into the
216 /// "Then"/"Else" region, while the false exit skips the region
217 /// The condition for the optional "Else" region is expressed as a PHI node.
218 /// The incoming values of the PHI node are true for the "If" edge and false
219 /// for the "Then" edge.
220 ///
221 /// Additionally to that even complicated loops look like this:
222 ///
223 /// \verbatim
224 /// 1
225 /// ||
226 /// | |
227 /// 2 ^ Where:
228 /// | / 1 = "Entry" block
229 /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block
230 /// 3 3 = "Flow" block, with back edge to entry block
231 /// |
232 /// \endverbatim
233 ///
234 /// The back edge of the "Flow" block is always on the false side of the branch
235 /// while the true side continues the general flow. So the loop condition
236 /// consist of a network of PHI nodes where the true incoming values expresses
237 /// breaks and the false values expresses continue states.
238 
239 class StructurizeCFG {
240  Type *Boolean;
241  ConstantInt *BoolTrue;
242  ConstantInt *BoolFalse;
243  UndefValue *BoolUndef;
244 
245  Function *Func;
246  Region *ParentRegion;
247 
248  LegacyDivergenceAnalysis *DA = nullptr;
249  DominatorTree *DT;
250 
252  BBSet Visited;
253 
254  SmallVector<WeakVH, 8> AffectedPhis;
255  BBPhiMap DeletedPhis;
256  BB2BBVecMap AddedPhis;
257 
258  PredMap Predicates;
259  BranchVector Conditions;
260 
261  BB2BBMap Loops;
262  PredMap LoopPreds;
263  BranchVector LoopConds;
264 
265  RegionNode *PrevNode;
266 
267  void orderNodes();
268 
269  void analyzeLoops(RegionNode *N);
270 
271  Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
272 
273  void gatherPredicates(RegionNode *N);
274 
275  void collectInfos();
276 
277  void insertConditions(bool Loops);
278 
279  void delPhiValues(BasicBlock *From, BasicBlock *To);
280 
281  void addPhiValues(BasicBlock *From, BasicBlock *To);
282 
283  void setPhiValues();
284 
285  void simplifyAffectedPhis();
286 
287  void killTerminator(BasicBlock *BB);
288 
289  void changeExit(RegionNode *Node, BasicBlock *NewExit,
290  bool IncludeDominator);
291 
292  BasicBlock *getNextFlow(BasicBlock *Dominator);
293 
294  BasicBlock *needPrefix(bool NeedEmpty);
295 
296  BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
297 
298  void setPrevNode(BasicBlock *BB);
299 
300  bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
301 
302  bool isPredictableTrue(RegionNode *Node);
303 
304  void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
305 
306  void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
307 
308  void createFlow();
309 
310  void rebuildSSA();
311 
312 public:
313  void init(Region *R);
314  bool run(Region *R, DominatorTree *DT);
315  bool makeUniformRegion(Region *R, LegacyDivergenceAnalysis *DA);
316 };
317 
318 class StructurizeCFGLegacyPass : public RegionPass {
319  bool SkipUniformRegions;
320 
321 public:
322  static char ID;
323 
324  explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)
325  : RegionPass(ID), SkipUniformRegions(SkipUniformRegions_) {
326  if (ForceSkipUniformRegions.getNumOccurrences())
327  SkipUniformRegions = ForceSkipUniformRegions.getValue();
329  }
330 
331  bool runOnRegion(Region *R, RGPassManager &RGM) override {
332  StructurizeCFG SCFG;
333  SCFG.init(R);
334  if (SkipUniformRegions) {
335  LegacyDivergenceAnalysis *DA = &getAnalysis<LegacyDivergenceAnalysis>();
336  if (SCFG.makeUniformRegion(R, DA))
337  return false;
338  }
339  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
340  return SCFG.run(R, DT);
341  }
342 
343  StringRef getPassName() const override { return "Structurize control flow"; }
344 
345  void getAnalysisUsage(AnalysisUsage &AU) const override {
346  if (SkipUniformRegions)
350 
353  }
354 };
355 
356 } // end anonymous namespace
357 
359 
360 INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg",
361  "Structurize the CFG", false, false)
363 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
366 INITIALIZE_PASS_END(StructurizeCFGLegacyPass, "structurizecfg",
367  "Structurize the CFG", false, false)
368 
369 /// Build up the general order of nodes, by performing a topological sort of the
370 /// parent region's nodes, while ensuring that there is no outer cycle node
371 /// between any two inner cycle nodes.
372 void StructurizeCFG::orderNodes() {
373  Order.resize(std::distance(GraphTraits<Region *>::nodes_begin(ParentRegion),
374  GraphTraits<Region *>::nodes_end(ParentRegion)));
375  if (Order.empty())
376  return;
377 
379  auto EntryNode = SubGraphTraits::getEntryNode(ParentRegion);
380 
381  // A list of range indices of SCCs in Order, to be processed.
383  unsigned I = 0, E = Order.size();
384  while (true) {
385  // Run through all the SCCs in the subgraph starting with Entry.
386  for (auto SCCI =
388  EntryNode);
389  !SCCI.isAtEnd(); ++SCCI) {
390  auto &SCC = *SCCI;
391 
392  // An SCC up to the size of 2, can be reduced to an entry (the last node),
393  // and a possible additional node. Therefore, it is already in order, and
394  // there is no need to add it to the work-list.
395  unsigned Size = SCC.size();
396  if (Size > 2)
397  WorkList.emplace_back(I, I + Size);
398 
399  // Add the SCC nodes to the Order array.
400  for (auto &N : SCC) {
401  assert(I < E && "SCC size mismatch!");
402  Order[I++] = N.first;
403  }
404  }
405  assert(I == E && "SCC size mismatch!");
406 
407  // If there are no more SCCs to order, then we are done.
408  if (WorkList.empty())
409  break;
410 
411  std::tie(I, E) = WorkList.pop_back_val();
412 
413  // Collect the set of nodes in the SCC's subgraph. These are only the
414  // possible child nodes; we do not add the entry (last node) otherwise we
415  // will have the same exact SCC all over again.
416  Nodes.clear();
417  Nodes.insert(Order.begin() + I, Order.begin() + E - 1);
418 
419  // Update the entry node.
420  EntryNode.first = Order[E - 1];
421  EntryNode.second = &Nodes;
422  }
423 }
424 
425 /// Determine the end of the loops
426 void StructurizeCFG::analyzeLoops(RegionNode *N) {
427  if (N->isSubRegion()) {
428  // Test for exit as back edge
429  BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
430  if (Visited.count(Exit))
431  Loops[Exit] = N->getEntry();
432 
433  } else {
434  // Test for successors as back edge
435  BasicBlock *BB = N->getNodeAs<BasicBlock>();
436  BranchInst *Term = cast<BranchInst>(BB->getTerminator());
437 
438  for (BasicBlock *Succ : Term->successors())
439  if (Visited.count(Succ))
440  Loops[Succ] = BB;
441  }
442 }
443 
444 /// Build the condition for one edge
445 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
446  bool Invert) {
447  Value *Cond = Invert ? BoolFalse : BoolTrue;
448  if (Term->isConditional()) {
449  Cond = Term->getCondition();
450 
451  if (Idx != (unsigned)Invert)
453  }
454  return Cond;
455 }
456 
457 /// Analyze the predecessors of each block and build up predicates
458 void StructurizeCFG::gatherPredicates(RegionNode *N) {
459  RegionInfo *RI = ParentRegion->getRegionInfo();
460  BasicBlock *BB = N->getEntry();
461  BBPredicates &Pred = Predicates[BB];
462  BBPredicates &LPred = LoopPreds[BB];
463 
464  for (BasicBlock *P : predecessors(BB)) {
465  // Ignore it if it's a branch from outside into our region entry
466  if (!ParentRegion->contains(P))
467  continue;
468 
469  Region *R = RI->getRegionFor(P);
470  if (R == ParentRegion) {
471  // It's a top level block in our region
472  BranchInst *Term = cast<BranchInst>(P->getTerminator());
473  for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
474  BasicBlock *Succ = Term->getSuccessor(i);
475  if (Succ != BB)
476  continue;
477 
478  if (Visited.count(P)) {
479  // Normal forward edge
480  if (Term->isConditional()) {
481  // Try to treat it like an ELSE block
482  BasicBlock *Other = Term->getSuccessor(!i);
483  if (Visited.count(Other) && !Loops.count(Other) &&
484  !Pred.count(Other) && !Pred.count(P)) {
485 
486  Pred[Other] = BoolFalse;
487  Pred[P] = BoolTrue;
488  continue;
489  }
490  }
491  Pred[P] = buildCondition(Term, i, false);
492  } else {
493  // Back edge
494  LPred[P] = buildCondition(Term, i, true);
495  }
496  }
497  } else {
498  // It's an exit from a sub region
499  while (R->getParent() != ParentRegion)
500  R = R->getParent();
501 
502  // Edge from inside a subregion to its entry, ignore it
503  if (*R == *N)
504  continue;
505 
506  BasicBlock *Entry = R->getEntry();
507  if (Visited.count(Entry))
508  Pred[Entry] = BoolTrue;
509  else
510  LPred[Entry] = BoolFalse;
511  }
512  }
513 }
514 
515 /// Collect various loop and predicate infos
516 void StructurizeCFG::collectInfos() {
517  // Reset predicate
518  Predicates.clear();
519 
520  // and loop infos
521  Loops.clear();
522  LoopPreds.clear();
523 
524  // Reset the visited nodes
525  Visited.clear();
526 
527  for (RegionNode *RN : reverse(Order)) {
528  LLVM_DEBUG(dbgs() << "Visiting: "
529  << (RN->isSubRegion() ? "SubRegion with entry: " : "")
530  << RN->getEntry()->getName() << "\n");
531 
532  // Analyze all the conditions leading to a node
533  gatherPredicates(RN);
534 
535  // Remember that we've seen this node
536  Visited.insert(RN->getEntry());
537 
538  // Find the last back edges
539  analyzeLoops(RN);
540  }
541 }
542 
543 /// Insert the missing branch conditions
544 void StructurizeCFG::insertConditions(bool Loops) {
545  BranchVector &Conds = Loops ? LoopConds : Conditions;
546  Value *Default = Loops ? BoolTrue : BoolFalse;
547  SSAUpdater PhiInserter;
548 
549  for (BranchInst *Term : Conds) {
550  assert(Term->isConditional());
551 
552  BasicBlock *Parent = Term->getParent();
553  BasicBlock *SuccTrue = Term->getSuccessor(0);
554  BasicBlock *SuccFalse = Term->getSuccessor(1);
555 
556  PhiInserter.Initialize(Boolean, "");
557  PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
558  PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
559 
560  BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
561 
562  NearestCommonDominator Dominator(DT);
563  Dominator.addBlock(Parent);
564 
565  Value *ParentValue = nullptr;
566  for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
567  BasicBlock *BB = BBAndPred.first;
568  Value *Pred = BBAndPred.second;
569 
570  if (BB == Parent) {
571  ParentValue = Pred;
572  break;
573  }
574  PhiInserter.AddAvailableValue(BB, Pred);
575  Dominator.addAndRememberBlock(BB);
576  }
577 
578  if (ParentValue) {
579  Term->setCondition(ParentValue);
580  } else {
581  if (!Dominator.resultIsRememberedBlock())
582  PhiInserter.AddAvailableValue(Dominator.result(), Default);
583 
584  Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
585  }
586  }
587 }
588 
589 /// Remove all PHI values coming from "From" into "To" and remember
590 /// them in DeletedPhis
591 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
592  PhiMap &Map = DeletedPhis[To];
593  for (PHINode &Phi : To->phis()) {
594  bool Recorded = false;
595  while (Phi.getBasicBlockIndex(From) != -1) {
596  Value *Deleted = Phi.removeIncomingValue(From, false);
597  Map[&Phi].push_back(std::make_pair(From, Deleted));
598  if (!Recorded) {
599  AffectedPhis.push_back(&Phi);
600  Recorded = true;
601  }
602  }
603  }
604 }
605 
606 /// Add a dummy PHI value as soon as we knew the new predecessor
607 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
608  for (PHINode &Phi : To->phis()) {
609  Value *Undef = UndefValue::get(Phi.getType());
610  Phi.addIncoming(Undef, From);
611  }
612  AddedPhis[To].push_back(From);
613 }
614 
615 /// Add the real PHI value as soon as everything is set up
616 void StructurizeCFG::setPhiValues() {
617  SmallVector<PHINode *, 8> InsertedPhis;
618  SSAUpdater Updater(&InsertedPhis);
619  for (const auto &AddedPhi : AddedPhis) {
620  BasicBlock *To = AddedPhi.first;
621  const BBVector &From = AddedPhi.second;
622 
623  if (!DeletedPhis.count(To))
624  continue;
625 
626  PhiMap &Map = DeletedPhis[To];
627  for (const auto &PI : Map) {
628  PHINode *Phi = PI.first;
629  Value *Undef = UndefValue::get(Phi->getType());
630  Updater.Initialize(Phi->getType(), "");
631  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
632  Updater.AddAvailableValue(To, Undef);
633 
634  NearestCommonDominator Dominator(DT);
635  Dominator.addBlock(To);
636  for (const auto &VI : PI.second) {
637  Updater.AddAvailableValue(VI.first, VI.second);
638  Dominator.addAndRememberBlock(VI.first);
639  }
640 
641  if (!Dominator.resultIsRememberedBlock())
642  Updater.AddAvailableValue(Dominator.result(), Undef);
643 
644  for (BasicBlock *FI : From)
645  Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
646  AffectedPhis.push_back(Phi);
647  }
648 
649  DeletedPhis.erase(To);
650  }
651  assert(DeletedPhis.empty());
652 
653  AffectedPhis.append(InsertedPhis.begin(), InsertedPhis.end());
654 }
655 
656 void StructurizeCFG::simplifyAffectedPhis() {
657  bool Changed;
658  do {
659  Changed = false;
660  SimplifyQuery Q(Func->getParent()->getDataLayout());
661  Q.DT = DT;
662  for (WeakVH VH : AffectedPhis) {
663  if (auto Phi = dyn_cast_or_null<PHINode>(VH)) {
664  if (auto NewValue = SimplifyInstruction(Phi, Q)) {
665  Phi->replaceAllUsesWith(NewValue);
666  Phi->eraseFromParent();
667  Changed = true;
668  }
669  }
670  }
671  } while (Changed);
672 }
673 
674 /// Remove phi values from all successors and then remove the terminator.
675 void StructurizeCFG::killTerminator(BasicBlock *BB) {
676  Instruction *Term = BB->getTerminator();
677  if (!Term)
678  return;
679 
680  for (BasicBlock *Succ : successors(BB))
681  delPhiValues(BB, Succ);
682 
683  if (DA)
684  DA->removeValue(Term);
685  Term->eraseFromParent();
686 }
687 
688 /// Let node exit(s) point to NewExit
689 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
690  bool IncludeDominator) {
691  if (Node->isSubRegion()) {
692  Region *SubRegion = Node->getNodeAs<Region>();
693  BasicBlock *OldExit = SubRegion->getExit();
694  BasicBlock *Dominator = nullptr;
695 
696  // Find all the edges from the sub region to the exit.
697  // We use make_early_inc_range here because we modify BB's terminator.
699  if (!SubRegion->contains(BB))
700  continue;
701 
702  // Modify the edges to point to the new exit
703  delPhiValues(BB, OldExit);
704  BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
705  addPhiValues(BB, NewExit);
706 
707  // Find the new dominator (if requested)
708  if (IncludeDominator) {
709  if (!Dominator)
710  Dominator = BB;
711  else
712  Dominator = DT->findNearestCommonDominator(Dominator, BB);
713  }
714  }
715 
716  // Change the dominator (if requested)
717  if (Dominator)
718  DT->changeImmediateDominator(NewExit, Dominator);
719 
720  // Update the region info
721  SubRegion->replaceExit(NewExit);
722  } else {
723  BasicBlock *BB = Node->getNodeAs<BasicBlock>();
724  killTerminator(BB);
725  BranchInst::Create(NewExit, BB);
726  addPhiValues(BB, NewExit);
727  if (IncludeDominator)
728  DT->changeImmediateDominator(NewExit, BB);
729  }
730 }
731 
732 /// Create a new flow node and update dominator tree and region info
733 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
734  LLVMContext &Context = Func->getContext();
735  BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
736  Order.back()->getEntry();
738  Func, Insert);
739  DT->addNewBlock(Flow, Dominator);
740  ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
741  return Flow;
742 }
743 
744 /// Create a new or reuse the previous node as flow node
745 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
746  BasicBlock *Entry = PrevNode->getEntry();
747 
748  if (!PrevNode->isSubRegion()) {
749  killTerminator(Entry);
750  if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
751  return Entry;
752  }
753 
754  // create a new flow node
755  BasicBlock *Flow = getNextFlow(Entry);
756 
757  // and wire it up
758  changeExit(PrevNode, Flow, true);
759  PrevNode = ParentRegion->getBBNode(Flow);
760  return Flow;
761 }
762 
763 /// Returns the region exit if possible, otherwise just a new flow node
764 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
765  bool ExitUseAllowed) {
766  if (!Order.empty() || !ExitUseAllowed)
767  return getNextFlow(Flow);
768 
769  BasicBlock *Exit = ParentRegion->getExit();
770  DT->changeImmediateDominator(Exit, Flow);
771  addPhiValues(Flow, Exit);
772  return Exit;
773 }
774 
775 /// Set the previous node
776 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
777  PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
778  : nullptr;
779 }
780 
781 /// Does BB dominate all the predicates of Node?
782 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
783  BBPredicates &Preds = Predicates[Node->getEntry()];
784  return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
785  return DT->dominates(BB, Pred.first);
786  });
787 }
788 
789 /// Can we predict that this node will always be called?
790 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
791  BBPredicates &Preds = Predicates[Node->getEntry()];
792  bool Dominated = false;
793 
794  // Regionentry is always true
795  if (!PrevNode)
796  return true;
797 
798  for (std::pair<BasicBlock*, Value*> Pred : Preds) {
799  BasicBlock *BB = Pred.first;
800  Value *V = Pred.second;
801 
802  if (V != BoolTrue)
803  return false;
804 
805  if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
806  Dominated = true;
807  }
808 
809  // TODO: The dominator check is too strict
810  return Dominated;
811 }
812 
813 /// Take one node from the order vector and wire it up
814 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
815  BasicBlock *LoopEnd) {
816  RegionNode *Node = Order.pop_back_val();
817  Visited.insert(Node->getEntry());
818 
819  if (isPredictableTrue(Node)) {
820  // Just a linear flow
821  if (PrevNode) {
822  changeExit(PrevNode, Node->getEntry(), true);
823  }
824  PrevNode = Node;
825  } else {
826  // Insert extra prefix node (or reuse last one)
827  BasicBlock *Flow = needPrefix(false);
828 
829  // Insert extra postfix node (or use exit instead)
830  BasicBlock *Entry = Node->getEntry();
831  BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
832 
833  // let it point to entry and next block
834  Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
835  addPhiValues(Flow, Entry);
836  DT->changeImmediateDominator(Entry, Flow);
837 
838  PrevNode = Node;
839  while (!Order.empty() && !Visited.count(LoopEnd) &&
840  dominatesPredicates(Entry, Order.back())) {
841  handleLoops(false, LoopEnd);
842  }
843 
844  changeExit(PrevNode, Next, false);
845  setPrevNode(Next);
846  }
847 }
848 
849 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
850  BasicBlock *LoopEnd) {
851  RegionNode *Node = Order.back();
852  BasicBlock *LoopStart = Node->getEntry();
853 
854  if (!Loops.count(LoopStart)) {
855  wireFlow(ExitUseAllowed, LoopEnd);
856  return;
857  }
858 
859  if (!isPredictableTrue(Node))
860  LoopStart = needPrefix(true);
861 
862  LoopEnd = Loops[Node->getEntry()];
863  wireFlow(false, LoopEnd);
864  while (!Visited.count(LoopEnd)) {
865  handleLoops(false, LoopEnd);
866  }
867 
868  // If the start of the loop is the entry block, we can't branch to it so
869  // insert a new dummy entry block.
870  Function *LoopFunc = LoopStart->getParent();
871  if (LoopStart == &LoopFunc->getEntryBlock()) {
872  LoopStart->setName("entry.orig");
873 
874  BasicBlock *NewEntry =
875  BasicBlock::Create(LoopStart->getContext(),
876  "entry",
877  LoopFunc,
878  LoopStart);
879  BranchInst::Create(LoopStart, NewEntry);
880  DT->setNewRoot(NewEntry);
881  }
882 
883  // Create an extra loop end node
884  LoopEnd = needPrefix(false);
885  BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
886  LoopConds.push_back(BranchInst::Create(Next, LoopStart,
887  BoolUndef, LoopEnd));
888  addPhiValues(LoopEnd, LoopStart);
889  setPrevNode(Next);
890 }
891 
892 /// After this function control flow looks like it should be, but
893 /// branches and PHI nodes only have undefined conditions.
894 void StructurizeCFG::createFlow() {
895  BasicBlock *Exit = ParentRegion->getExit();
896  bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
897 
898  AffectedPhis.clear();
899  DeletedPhis.clear();
900  AddedPhis.clear();
901  Conditions.clear();
902  LoopConds.clear();
903 
904  PrevNode = nullptr;
905  Visited.clear();
906 
907  while (!Order.empty()) {
908  handleLoops(EntryDominatesExit, nullptr);
909  }
910 
911  if (PrevNode)
912  changeExit(PrevNode, Exit, EntryDominatesExit);
913  else
914  assert(EntryDominatesExit);
915 }
916 
917 /// Handle a rare case where the disintegrated nodes instructions
918 /// no longer dominate all their uses. Not sure if this is really necessary
919 void StructurizeCFG::rebuildSSA() {
920  SSAUpdater Updater;
921  for (BasicBlock *BB : ParentRegion->blocks())
922  for (Instruction &I : *BB) {
923  bool Initialized = false;
924  // We may modify the use list as we iterate over it, so we use
925  // make_early_inc_range.
926  for (Use &U : llvm::make_early_inc_range(I.uses())) {
927  Instruction *User = cast<Instruction>(U.getUser());
928  if (User->getParent() == BB) {
929  continue;
930  } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
931  if (UserPN->getIncomingBlock(U) == BB)
932  continue;
933  }
934 
935  if (DT->dominates(&I, User))
936  continue;
937 
938  if (!Initialized) {
939  Value *Undef = UndefValue::get(I.getType());
940  Updater.Initialize(I.getType(), "");
941  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
942  Updater.AddAvailableValue(BB, &I);
943  Initialized = true;
944  }
945  Updater.RewriteUseAfterInsertions(U);
946  }
947  }
948 }
949 
950 static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
951  const LegacyDivergenceAnalysis &DA) {
952  // Bool for if all sub-regions are uniform.
953  bool SubRegionsAreUniform = true;
954  // Count of how many direct children are conditional.
955  unsigned ConditionalDirectChildren = 0;
956 
957  for (auto E : R->elements()) {
958  if (!E->isSubRegion()) {
959  auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
960  if (!Br || !Br->isConditional())
961  continue;
962 
963  if (!DA.isUniform(Br))
964  return false;
965 
966  // One of our direct children is conditional.
967  ConditionalDirectChildren++;
968 
969  LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
970  << " has uniform terminator\n");
971  } else {
972  // Explicitly refuse to treat regions as uniform if they have non-uniform
973  // subregions. We cannot rely on DivergenceAnalysis for branches in
974  // subregions because those branches may have been removed and re-created,
975  // so we look for our metadata instead.
976  //
977  // Warning: It would be nice to treat regions as uniform based only on
978  // their direct child basic blocks' terminators, regardless of whether
979  // subregions are uniform or not. However, this requires a very careful
980  // look at SIAnnotateControlFlow to make sure nothing breaks there.
981  for (auto BB : E->getNodeAs<Region>()->blocks()) {
982  auto Br = dyn_cast<BranchInst>(BB->getTerminator());
983  if (!Br || !Br->isConditional())
984  continue;
985 
986  if (!Br->getMetadata(UniformMDKindID)) {
987  // Early exit if we cannot have relaxed uniform regions.
988  if (!RelaxedUniformRegions)
989  return false;
990 
991  SubRegionsAreUniform = false;
992  break;
993  }
994  }
995  }
996  }
997 
998  // Our region is uniform if:
999  // 1. All conditional branches that are direct children are uniform (checked
1000  // above).
1001  // 2. And either:
1002  // a. All sub-regions are uniform.
1003  // b. There is one or less conditional branches among the direct children.
1004  return SubRegionsAreUniform || (ConditionalDirectChildren <= 1);
1005 }
1006 
1007 void StructurizeCFG::init(Region *R) {
1008  LLVMContext &Context = R->getEntry()->getContext();
1009 
1011  BoolTrue = ConstantInt::getTrue(Context);
1012  BoolFalse = ConstantInt::getFalse(Context);
1013  BoolUndef = UndefValue::get(Boolean);
1014 
1015  this->DA = nullptr;
1016 }
1017 
1018 bool StructurizeCFG::makeUniformRegion(Region *R,
1020  if (R->isTopLevelRegion())
1021  return false;
1022 
1023  this->DA = DA;
1024  // TODO: We could probably be smarter here with how we handle sub-regions.
1025  // We currently rely on the fact that metadata is set by earlier invocations
1026  // of the pass on sub-regions, and that this metadata doesn't get lost --
1027  // but we shouldn't rely on metadata for correctness!
1028  unsigned UniformMDKindID =
1029  R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
1030 
1031  if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
1032  LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
1033  << '\n');
1034 
1035  // Mark all direct child block terminators as having been treated as
1036  // uniform. To account for a possible future in which non-uniform
1037  // sub-regions are treated more cleverly, indirect children are not
1038  // marked as uniform.
1039  MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
1040  for (RegionNode *E : R->elements()) {
1041  if (E->isSubRegion())
1042  continue;
1043 
1044  if (Instruction *Term = E->getEntry()->getTerminator())
1045  Term->setMetadata(UniformMDKindID, MD);
1046  }
1047 
1048  return true;
1049  }
1050  return false;
1051 }
1052 
1053 /// Run the transformation for each region found
1054 bool StructurizeCFG::run(Region *R, DominatorTree *DT) {
1055  if (R->isTopLevelRegion())
1056  return false;
1057 
1058  this->DT = DT;
1059 
1060  Func = R->getEntry()->getParent();
1061  ParentRegion = R;
1062 
1063  orderNodes();
1064  collectInfos();
1065  createFlow();
1066  insertConditions(false);
1067  insertConditions(true);
1068  setPhiValues();
1069  simplifyAffectedPhis();
1070  rebuildSSA();
1071 
1072  // Cleanup
1073  Order.clear();
1074  Visited.clear();
1075  DeletedPhis.clear();
1076  AddedPhis.clear();
1077  Predicates.clear();
1078  Conditions.clear();
1079  Loops.clear();
1080  LoopPreds.clear();
1081  LoopConds.clear();
1082 
1083  return true;
1084 }
1085 
1086 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
1087  return new StructurizeCFGLegacyPass(SkipUniformRegions);
1088 }
1089 
1090 static void addRegionIntoQueue(Region &R, std::vector<Region *> &Regions) {
1091  Regions.push_back(&R);
1092  for (const auto &E : R)
1093  addRegionIntoQueue(*E, Regions);
1094 }
1095 
1098 
1099  bool Changed = false;
1101  auto &RI = AM.getResult<RegionInfoAnalysis>(F);
1102  std::vector<Region *> Regions;
1103  addRegionIntoQueue(*RI.getTopLevelRegion(), Regions);
1104  while (!Regions.empty()) {
1105  Region *R = Regions.back();
1106  StructurizeCFG SCFG;
1107  SCFG.init(R);
1108  Changed |= SCFG.run(R, DT);
1109  Regions.pop_back();
1110  }
1111  if (!Changed)
1112  return PreservedAnalyses::all();
1113  PreservedAnalyses PA;
1115  return PA;
1116 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::SSAUpdater::Initialize
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
RegionInfo.h
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3306
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::initializeStructurizeCFGLegacyPassPass
void initializeStructurizeCFGLegacyPassPass(PassRegistry &)
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:238
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg", "Structurize the CFG", false, false) INITIALIZE_PASS_END(StructurizeCFGLegacyPass
Metadata.h
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
RegionPass.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
SCCIterator.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
Scalar.h
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
hasOnlyUniformBranches
static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const LegacyDivergenceAnalysis &DA)
Definition: StructurizeCFG.cpp:950
ErrorHandling.h
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:718
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
MapVector.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::WeakVH
A nullable Value handle that is nullable.
Definition: ValueHandle.h:144
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::filter_iterator_impl
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:416
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::Boolean
unsigned char Boolean
Definition: ConvertUTF.h:112
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:229
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1233
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:198
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
result
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s result
Definition: README_P9.txt:256
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LoopDeletionResult::Deleted
@ Deleted
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::all_of
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:1551
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::msgpack::Type::Map
@ Map
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
FlowBlockName
const char FlowBlockName[]
Definition: StructurizeCFG.cpp:60
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::RegionInfoAnalysis
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
llvm::User
Definition: User.h:44
InstrTypes.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::SSAUpdater::RewriteUseAfterInsertions
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Definition: SSAUpdater.cpp:199
StructurizeCFG.h
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6328
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:402
llvm::LegacyDivergenceAnalysis
Definition: LegacyDivergenceAnalysis.h:31
SmallPtrSet.h
PatternMatch.h
Utils.h
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::RegionNode
Definition: RegionInfo.h:879
llvm::RegionBase::blocks
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:622
llvm::RegionInfoBase::getRegionFor
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
Definition: RegionInfoImpl.h:817
BasicBlock.h
llvm::cl::opt< bool >
VI
@ VI
Definition: SIInstrInfo.cpp:7689
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
structurizecfg
structurizecfg
Definition: StructurizeCFG.cpp:366
llvm::SSAUpdater::GetValueInMiddleOfBlock
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::StructurizeCFGPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StructurizeCFG.cpp:1096
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3124
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1348
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegionIterator.h
llvm::PHINode::setIncomingValueForBlock
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Definition: Instructions.h:2825
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
CFG
Structurize the CFG
Definition: StructurizeCFG.cpp:367
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::RGPassManager
The pass manager to schedule RegionPasses.
Definition: RegionPass.h:86
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::RegionPass
A pass that runs on each Region in a function.
Definition: RegionPass.h:31
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:295
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2105
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
addRegionIntoQueue
static void addRegionIntoQueue(Region &R, std::vector< Region * > &Regions)
Definition: StructurizeCFG.cpp:1090
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::RegionInfo
Definition: RegionInfo.h:900
SSAUpdater.h
llvm::ifs::IFSSymbolType::Func
@ Func
ValueHandle.h
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:570
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:490
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:880
llvm::createStructurizeCFGPass
Pass * createStructurizeCFGPass(bool SkipUniformRegions=false)
When SkipUniformRegions is true the structizer will not structurize regions that only contain uniform...
Definition: StructurizeCFG.cpp:1086
Argument.h
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
Constant.h
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:873
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
Function.h
PassManager.h
llvm::TargetStackID::Default
@ Default
Definition: TargetFrameLowering.h:28
llvm::RegionBase::contains
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Definition: RegionInfoImpl.h:104
llvm::scc_iterator::isAtEnd
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
Definition: SCCIterator.h:108
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
LegacyDivergenceAnalysis.h
SmallVector.h
Flow
Annotate SI Control Flow
Definition: SIAnnotateControlFlow.cpp:118
User.h
Dominators.h
N
#define N
llvm::cl::opt_storage::getValue
DataType & getValue()
Definition: CommandLine.h:1363
InstructionSimplify.h
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::PHINode
Definition: Instructions.h:2633
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:35
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SSAUpdater::AddAvailableValue
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
llvm::cl::desc
Definition: CommandLine.h:412
llvm::Region
Definition: RegionInfo.h:889
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
raw_ostream.h
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
Value.h
llvm::RegionBase::getExit
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::RegionBase::replaceExit
void replaceExit(BlockT *BB)
Replace the exit basic block of the region with the new basic block.
Definition: RegionInfoImpl.h:62
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1184
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37