LLVM  16.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/SmallSet.h"
16 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/PassManager.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Use.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/IR/ValueHandle.h"
37 #include "llvm/InitializePasses.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Casting.h"
41 #include "llvm/Support/Debug.h"
43 #include "llvm/Transforms/Scalar.h"
44 #include "llvm/Transforms/Utils.h"
47 #include <algorithm>
48 #include <cassert>
49 #include <utility>
50 
51 using namespace llvm;
52 using namespace llvm::PatternMatch;
53 
54 #define DEBUG_TYPE "structurizecfg"
55 
56 // The name for newly created blocks.
57 const char FlowBlockName[] = "Flow";
58 
59 namespace {
60 
61 static cl::opt<bool> ForceSkipUniformRegions(
62  "structurizecfg-skip-uniform-regions",
63  cl::Hidden,
64  cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
65  cl::init(false));
66 
67 static cl::opt<bool>
68  RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden,
69  cl::desc("Allow relaxed uniform region checks"),
70  cl::init(true));
71 
72 // Definition of the complex types used in this pass.
73 
74 using BBValuePair = std::pair<BasicBlock *, Value *>;
75 
76 using RNVector = SmallVector<RegionNode *, 8>;
77 using BBVector = SmallVector<BasicBlock *, 8>;
78 using BranchVector = SmallVector<BranchInst *, 8>;
79 using BBValueVector = SmallVector<BBValuePair, 2>;
80 
81 using BBSet = SmallPtrSet<BasicBlock *, 8>;
82 
84 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
85 
86 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
90 
91 using BranchDebugLocMap = DenseMap<BasicBlock *, DebugLoc>;
92 
93 // A traits type that is intended to be used in graph algorithms. The graph
94 // traits starts at an entry node, and traverses the RegionNodes that are in
95 // the Nodes set.
96 struct SubGraphTraits {
97  using NodeRef = std::pair<RegionNode *, SmallDenseSet<RegionNode *> *>;
98  using BaseSuccIterator = GraphTraits<RegionNode *>::ChildIteratorType;
99 
100  // This wraps a set of Nodes into the iterator, so we know which edges to
101  // filter out.
102  class WrappedSuccIterator
103  : public iterator_adaptor_base<
104  WrappedSuccIterator, BaseSuccIterator,
105  typename std::iterator_traits<BaseSuccIterator>::iterator_category,
106  NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
108 
109  public:
110  WrappedSuccIterator(BaseSuccIterator It, SmallDenseSet<RegionNode *> *Nodes)
111  : iterator_adaptor_base(It), Nodes(Nodes) {}
112 
113  NodeRef operator*() const { return {*I, Nodes}; }
114  };
115 
116  static bool filterAll(const NodeRef &N) { return true; }
117  static bool filterSet(const NodeRef &N) { return N.second->count(N.first); }
118 
119  using ChildIteratorType =
120  filter_iterator<WrappedSuccIterator, bool (*)(const NodeRef &)>;
121 
122  static NodeRef getEntryNode(Region *R) {
123  return {GraphTraits<Region *>::getEntryNode(R), nullptr};
124  }
125 
126  static NodeRef getEntryNode(NodeRef N) { return N; }
127 
129  auto *filter = N.second ? &filterSet : &filterAll;
130  return make_filter_range(
131  make_range<WrappedSuccIterator>(
132  {GraphTraits<RegionNode *>::child_begin(N.first), N.second},
133  {GraphTraits<RegionNode *>::child_end(N.first), N.second}),
134  filter);
135  }
136 
137  static ChildIteratorType child_begin(const NodeRef &N) {
138  return children(N).begin();
139  }
140 
141  static ChildIteratorType child_end(const NodeRef &N) {
142  return children(N).end();
143  }
144 };
145 
146 /// Finds the nearest common dominator of a set of BasicBlocks.
147 ///
148 /// For every BB you add to the set, you can specify whether we "remember" the
149 /// block. When you get the common dominator, you can also ask whether it's one
150 /// of the blocks we remembered.
151 class NearestCommonDominator {
152  DominatorTree *DT;
153  BasicBlock *Result = nullptr;
154  bool ResultIsRemembered = false;
155 
156  /// Add BB to the resulting dominator.
157  void addBlock(BasicBlock *BB, bool Remember) {
158  if (!Result) {
159  Result = BB;
160  ResultIsRemembered = Remember;
161  return;
162  }
163 
164  BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
165  if (NewResult != Result)
166  ResultIsRemembered = false;
167  if (NewResult == BB)
168  ResultIsRemembered |= Remember;
169  Result = NewResult;
170  }
171 
172 public:
173  explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
174 
175  void addBlock(BasicBlock *BB) {
176  addBlock(BB, /* Remember = */ false);
177  }
178 
179  void addAndRememberBlock(BasicBlock *BB) {
180  addBlock(BB, /* Remember = */ true);
181  }
182 
183  /// Get the nearest common dominator of all the BBs added via addBlock() and
184  /// addAndRememberBlock().
185  BasicBlock *result() { return Result; }
186 
187  /// Is the BB returned by getResult() one of the blocks we added to the set
188  /// with addAndRememberBlock()?
189  bool resultIsRememberedBlock() { return ResultIsRemembered; }
190 };
191 
192 /// Transforms the control flow graph on one single entry/exit region
193 /// at a time.
194 ///
195 /// After the transform all "If"/"Then"/"Else" style control flow looks like
196 /// this:
197 ///
198 /// \verbatim
199 /// 1
200 /// ||
201 /// | |
202 /// 2 |
203 /// | /
204 /// |/
205 /// 3
206 /// || Where:
207 /// | | 1 = "If" block, calculates the condition
208 /// 4 | 2 = "Then" subregion, runs if the condition is true
209 /// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
210 /// |/ 4 = "Else" optional subregion, runs if the condition is false
211 /// 5 5 = "End" block, also rejoins the control flow
212 /// \endverbatim
213 ///
214 /// Control flow is expressed as a branch where the true exit goes into the
215 /// "Then"/"Else" region, while the false exit skips the region
216 /// The condition for the optional "Else" region is expressed as a PHI node.
217 /// The incoming values of the PHI node are true for the "If" edge and false
218 /// for the "Then" edge.
219 ///
220 /// Additionally to that even complicated loops look like this:
221 ///
222 /// \verbatim
223 /// 1
224 /// ||
225 /// | |
226 /// 2 ^ Where:
227 /// | / 1 = "Entry" block
228 /// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block
229 /// 3 3 = "Flow" block, with back edge to entry block
230 /// |
231 /// \endverbatim
232 ///
233 /// The back edge of the "Flow" block is always on the false side of the branch
234 /// while the true side continues the general flow. So the loop condition
235 /// consist of a network of PHI nodes where the true incoming values expresses
236 /// breaks and the false values expresses continue states.
237 
238 class StructurizeCFG {
239  Type *Boolean;
240  ConstantInt *BoolTrue;
241  ConstantInt *BoolFalse;
242  UndefValue *BoolUndef;
243 
244  Function *Func;
245  Region *ParentRegion;
246 
247  LegacyDivergenceAnalysis *DA = nullptr;
248  DominatorTree *DT;
249 
251  BBSet Visited;
252  BBSet FlowSet;
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  BranchDebugLocMap TermDL;
266 
267  RegionNode *PrevNode;
268 
269  void orderNodes();
270 
271  void analyzeLoops(RegionNode *N);
272 
273  Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
274 
275  void gatherPredicates(RegionNode *N);
276 
277  void collectInfos();
278 
279  void insertConditions(bool Loops);
280 
281  void simplifyConditions();
282 
283  void delPhiValues(BasicBlock *From, BasicBlock *To);
284 
285  void addPhiValues(BasicBlock *From, BasicBlock *To);
286 
287  void findUndefBlocks(BasicBlock *PHIBlock,
288  const SmallSet<BasicBlock *, 8> &Incomings,
289  SmallVector<BasicBlock *> &UndefBlks) const;
290  void setPhiValues();
291 
292  void simplifyAffectedPhis();
293 
294  void killTerminator(BasicBlock *BB);
295 
296  void changeExit(RegionNode *Node, BasicBlock *NewExit,
297  bool IncludeDominator);
298 
299  BasicBlock *getNextFlow(BasicBlock *Dominator);
300 
301  BasicBlock *needPrefix(bool NeedEmpty);
302 
303  BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
304 
305  void setPrevNode(BasicBlock *BB);
306 
307  bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
308 
309  bool isPredictableTrue(RegionNode *Node);
310 
311  void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
312 
313  void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
314 
315  void createFlow();
316 
317  void rebuildSSA();
318 
319 public:
320  void init(Region *R);
321  bool run(Region *R, DominatorTree *DT);
322  bool makeUniformRegion(Region *R, LegacyDivergenceAnalysis *DA);
323 };
324 
325 class StructurizeCFGLegacyPass : public RegionPass {
326  bool SkipUniformRegions;
327 
328 public:
329  static char ID;
330 
331  explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)
332  : RegionPass(ID), SkipUniformRegions(SkipUniformRegions_) {
333  if (ForceSkipUniformRegions.getNumOccurrences())
334  SkipUniformRegions = ForceSkipUniformRegions.getValue();
336  }
337 
338  bool runOnRegion(Region *R, RGPassManager &RGM) override {
339  StructurizeCFG SCFG;
340  SCFG.init(R);
341  if (SkipUniformRegions) {
342  LegacyDivergenceAnalysis *DA = &getAnalysis<LegacyDivergenceAnalysis>();
343  if (SCFG.makeUniformRegion(R, DA))
344  return false;
345  }
346  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
347  return SCFG.run(R, DT);
348  }
349 
350  StringRef getPassName() const override { return "Structurize control flow"; }
351 
352  void getAnalysisUsage(AnalysisUsage &AU) const override {
353  if (SkipUniformRegions)
357 
360  }
361 };
362 
363 } // end anonymous namespace
364 
366 
367 INITIALIZE_PASS_BEGIN(StructurizeCFGLegacyPass, "structurizecfg",
368  "Structurize the CFG", false, false)
370 INITIALIZE_PASS_DEPENDENCY(LowerSwitchLegacyPass)
373 INITIALIZE_PASS_END(StructurizeCFGLegacyPass, "structurizecfg",
374  "Structurize the CFG", false, false)
375 
376 /// Build up the general order of nodes, by performing a topological sort of the
377 /// parent region's nodes, while ensuring that there is no outer cycle node
378 /// between any two inner cycle nodes.
379 void StructurizeCFG::orderNodes() {
380  Order.resize(std::distance(GraphTraits<Region *>::nodes_begin(ParentRegion),
381  GraphTraits<Region *>::nodes_end(ParentRegion)));
382  if (Order.empty())
383  return;
384 
386  auto EntryNode = SubGraphTraits::getEntryNode(ParentRegion);
387 
388  // A list of range indices of SCCs in Order, to be processed.
390  unsigned I = 0, E = Order.size();
391  while (true) {
392  // Run through all the SCCs in the subgraph starting with Entry.
393  for (auto SCCI =
395  EntryNode);
396  !SCCI.isAtEnd(); ++SCCI) {
397  auto &SCC = *SCCI;
398 
399  // An SCC up to the size of 2, can be reduced to an entry (the last node),
400  // and a possible additional node. Therefore, it is already in order, and
401  // there is no need to add it to the work-list.
402  unsigned Size = SCC.size();
403  if (Size > 2)
404  WorkList.emplace_back(I, I + Size);
405 
406  // Add the SCC nodes to the Order array.
407  for (const auto &N : SCC) {
408  assert(I < E && "SCC size mismatch!");
409  Order[I++] = N.first;
410  }
411  }
412  assert(I == E && "SCC size mismatch!");
413 
414  // If there are no more SCCs to order, then we are done.
415  if (WorkList.empty())
416  break;
417 
418  std::tie(I, E) = WorkList.pop_back_val();
419 
420  // Collect the set of nodes in the SCC's subgraph. These are only the
421  // possible child nodes; we do not add the entry (last node) otherwise we
422  // will have the same exact SCC all over again.
423  Nodes.clear();
424  Nodes.insert(Order.begin() + I, Order.begin() + E - 1);
425 
426  // Update the entry node.
427  EntryNode.first = Order[E - 1];
428  EntryNode.second = &Nodes;
429  }
430 }
431 
432 /// Determine the end of the loops
433 void StructurizeCFG::analyzeLoops(RegionNode *N) {
434  if (N->isSubRegion()) {
435  // Test for exit as back edge
436  BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
437  if (Visited.count(Exit))
438  Loops[Exit] = N->getEntry();
439 
440  } else {
441  // Test for successors as back edge
442  BasicBlock *BB = N->getNodeAs<BasicBlock>();
443  BranchInst *Term = cast<BranchInst>(BB->getTerminator());
444 
445  for (BasicBlock *Succ : Term->successors())
446  if (Visited.count(Succ))
447  Loops[Succ] = BB;
448  }
449 }
450 
451 /// Build the condition for one edge
452 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
453  bool Invert) {
454  Value *Cond = Invert ? BoolFalse : BoolTrue;
455  if (Term->isConditional()) {
456  Cond = Term->getCondition();
457 
458  if (Idx != (unsigned)Invert)
460  }
461  return Cond;
462 }
463 
464 /// Analyze the predecessors of each block and build up predicates
465 void StructurizeCFG::gatherPredicates(RegionNode *N) {
466  RegionInfo *RI = ParentRegion->getRegionInfo();
467  BasicBlock *BB = N->getEntry();
468  BBPredicates &Pred = Predicates[BB];
469  BBPredicates &LPred = LoopPreds[BB];
470 
471  for (BasicBlock *P : predecessors(BB)) {
472  // Ignore it if it's a branch from outside into our region entry
473  if (!ParentRegion->contains(P))
474  continue;
475 
476  Region *R = RI->getRegionFor(P);
477  if (R == ParentRegion) {
478  // It's a top level block in our region
479  BranchInst *Term = cast<BranchInst>(P->getTerminator());
480  for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
481  BasicBlock *Succ = Term->getSuccessor(i);
482  if (Succ != BB)
483  continue;
484 
485  if (Visited.count(P)) {
486  // Normal forward edge
487  if (Term->isConditional()) {
488  // Try to treat it like an ELSE block
489  BasicBlock *Other = Term->getSuccessor(!i);
490  if (Visited.count(Other) && !Loops.count(Other) &&
491  !Pred.count(Other) && !Pred.count(P)) {
492 
493  Pred[Other] = BoolFalse;
494  Pred[P] = BoolTrue;
495  continue;
496  }
497  }
498  Pred[P] = buildCondition(Term, i, false);
499  } else {
500  // Back edge
501  LPred[P] = buildCondition(Term, i, true);
502  }
503  }
504  } else {
505  // It's an exit from a sub region
506  while (R->getParent() != ParentRegion)
507  R = R->getParent();
508 
509  // Edge from inside a subregion to its entry, ignore it
510  if (*R == *N)
511  continue;
512 
513  BasicBlock *Entry = R->getEntry();
514  if (Visited.count(Entry))
515  Pred[Entry] = BoolTrue;
516  else
517  LPred[Entry] = BoolFalse;
518  }
519  }
520 }
521 
522 /// Collect various loop and predicate infos
523 void StructurizeCFG::collectInfos() {
524  // Reset predicate
525  Predicates.clear();
526 
527  // and loop infos
528  Loops.clear();
529  LoopPreds.clear();
530 
531  // Reset the visited nodes
532  Visited.clear();
533 
534  for (RegionNode *RN : reverse(Order)) {
535  LLVM_DEBUG(dbgs() << "Visiting: "
536  << (RN->isSubRegion() ? "SubRegion with entry: " : "")
537  << RN->getEntry()->getName() << "\n");
538 
539  // Analyze all the conditions leading to a node
540  gatherPredicates(RN);
541 
542  // Remember that we've seen this node
543  Visited.insert(RN->getEntry());
544 
545  // Find the last back edges
546  analyzeLoops(RN);
547  }
548 
549  // Reset the collected term debug locations
550  TermDL.clear();
551 
552  for (BasicBlock &BB : *Func) {
553  if (const DebugLoc &DL = BB.getTerminator()->getDebugLoc())
554  TermDL[&BB] = DL;
555  }
556 }
557 
558 /// Insert the missing branch conditions
559 void StructurizeCFG::insertConditions(bool Loops) {
560  BranchVector &Conds = Loops ? LoopConds : Conditions;
561  Value *Default = Loops ? BoolTrue : BoolFalse;
562  SSAUpdater PhiInserter;
563 
564  for (BranchInst *Term : Conds) {
565  assert(Term->isConditional());
566 
567  BasicBlock *Parent = Term->getParent();
568  BasicBlock *SuccTrue = Term->getSuccessor(0);
569  BasicBlock *SuccFalse = Term->getSuccessor(1);
570 
571  PhiInserter.Initialize(Boolean, "");
572  PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
573  PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
574 
575  BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
576 
577  NearestCommonDominator Dominator(DT);
578  Dominator.addBlock(Parent);
579 
580  Value *ParentValue = nullptr;
581  for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
582  BasicBlock *BB = BBAndPred.first;
583  Value *Pred = BBAndPred.second;
584 
585  if (BB == Parent) {
586  ParentValue = Pred;
587  break;
588  }
589  PhiInserter.AddAvailableValue(BB, Pred);
590  Dominator.addAndRememberBlock(BB);
591  }
592 
593  if (ParentValue) {
594  Term->setCondition(ParentValue);
595  } else {
596  if (!Dominator.resultIsRememberedBlock())
597  PhiInserter.AddAvailableValue(Dominator.result(), Default);
598 
599  Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
600  }
601  }
602 }
603 
604 /// Simplify any inverted conditions that were built by buildConditions.
605 void StructurizeCFG::simplifyConditions() {
606  SmallVector<Instruction *> InstToErase;
607  for (auto &I : concat<PredMap::value_type>(Predicates, LoopPreds)) {
608  auto &Preds = I.second;
609  for (auto &J : Preds) {
610  auto &Cond = J.second;
611  Instruction *Inverted;
612  if (match(Cond, m_Not(m_OneUse(m_Instruction(Inverted)))) &&
613  !Cond->use_empty()) {
614  if (auto *InvertedCmp = dyn_cast<CmpInst>(Inverted)) {
615  InvertedCmp->setPredicate(InvertedCmp->getInversePredicate());
616  Cond->replaceAllUsesWith(InvertedCmp);
617  InstToErase.push_back(cast<Instruction>(Cond));
618  }
619  }
620  }
621  }
622  for (auto *I : InstToErase)
623  I->eraseFromParent();
624 }
625 
626 /// Remove all PHI values coming from "From" into "To" and remember
627 /// them in DeletedPhis
628 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
629  PhiMap &Map = DeletedPhis[To];
630  for (PHINode &Phi : To->phis()) {
631  bool Recorded = false;
632  while (Phi.getBasicBlockIndex(From) != -1) {
633  Value *Deleted = Phi.removeIncomingValue(From, false);
634  Map[&Phi].push_back(std::make_pair(From, Deleted));
635  if (!Recorded) {
636  AffectedPhis.push_back(&Phi);
637  Recorded = true;
638  }
639  }
640  }
641 }
642 
643 /// Add a dummy PHI value as soon as we knew the new predecessor
644 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
645  for (PHINode &Phi : To->phis()) {
646  Value *Undef = UndefValue::get(Phi.getType());
647  Phi.addIncoming(Undef, From);
648  }
649  AddedPhis[To].push_back(From);
650 }
651 
652 /// When we are reconstructing a PHI inside \p PHIBlock with incoming values
653 /// from predecessors \p Incomings, we have a chance to mark the available value
654 /// from some blocks as undefined. The function will find out all such blocks
655 /// and return in \p UndefBlks.
656 void StructurizeCFG::findUndefBlocks(
657  BasicBlock *PHIBlock, const SmallSet<BasicBlock *, 8> &Incomings,
658  SmallVector<BasicBlock *> &UndefBlks) const {
659  // We may get a post-structured CFG like below:
660  //
661  // | P1
662  // |/
663  // F1
664  // |\
665  // | N
666  // |/
667  // F2
668  // |\
669  // | P2
670  // |/
671  // F3
672  // |\
673  // B
674  //
675  // B is the block that has a PHI being reconstructed. P1/P2 are predecessors
676  // of B before structurization. F1/F2/F3 are flow blocks inserted during
677  // structurization process. Block N is not a predecessor of B before
678  // structurization, but are placed between the predecessors(P1/P2) of B after
679  // structurization. This usually means that threads went to N never take the
680  // path N->F2->F3->B. For example, the threads take the branch F1->N may
681  // always take the branch F2->P2. So, when we are reconstructing a PHI
682  // originally in B, we can safely say the incoming value from N is undefined.
683  SmallSet<BasicBlock *, 8> VisitedBlock;
685  if (PHIBlock == ParentRegion->getExit()) {
686  for (auto P : predecessors(PHIBlock)) {
687  if (ParentRegion->contains(P))
688  Stack.push_back(P);
689  }
690  } else {
691  append_range(Stack, predecessors(PHIBlock));
692  }
693 
694  // Do a backward traversal over the CFG, and stop further searching if
695  // the block is not a Flow. If a block is neither flow block nor the
696  // incoming predecessor, then the incoming value from the block is
697  // undefined value for the PHI being reconstructed.
698  while (!Stack.empty()) {
699  BasicBlock *Current = Stack.pop_back_val();
700  if (VisitedBlock.contains(Current))
701  continue;
702 
703  VisitedBlock.insert(Current);
704  if (FlowSet.contains(Current)) {
705  for (auto P : predecessors(Current))
706  Stack.push_back(P);
707  } else if (!Incomings.contains(Current)) {
708  UndefBlks.push_back(Current);
709  }
710  }
711 }
712 
713 /// Add the real PHI value as soon as everything is set up
714 void StructurizeCFG::setPhiValues() {
715  SmallVector<PHINode *, 8> InsertedPhis;
716  SSAUpdater Updater(&InsertedPhis);
717  for (const auto &AddedPhi : AddedPhis) {
718  BasicBlock *To = AddedPhi.first;
719  const BBVector &From = AddedPhi.second;
720 
721  if (!DeletedPhis.count(To))
722  continue;
723 
724  SmallVector<BasicBlock *> UndefBlks;
725  bool CachedUndefs = false;
726  PhiMap &Map = DeletedPhis[To];
727  for (const auto &PI : Map) {
728  PHINode *Phi = PI.first;
729  Value *Undef = UndefValue::get(Phi->getType());
730  Updater.Initialize(Phi->getType(), "");
731  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
732  Updater.AddAvailableValue(To, Undef);
733 
734  SmallSet<BasicBlock *, 8> Incomings;
735  SmallVector<BasicBlock *> ConstantPreds;
736  for (const auto &VI : PI.second) {
737  Incomings.insert(VI.first);
738  Updater.AddAvailableValue(VI.first, VI.second);
739  if (isa<Constant>(VI.second))
740  ConstantPreds.push_back(VI.first);
741  }
742 
743  if (!CachedUndefs) {
744  findUndefBlocks(To, Incomings, UndefBlks);
745  CachedUndefs = true;
746  }
747 
748  for (auto UB : UndefBlks) {
749  // If this undef block is dominated by any predecessor(before
750  // structurization) of reconstructed PHI with constant incoming value,
751  // don't mark the available value as undefined. Setting undef to such
752  // block will stop us from getting optimal phi insertion.
753  if (any_of(ConstantPreds,
754  [&](BasicBlock *CP) { return DT->dominates(CP, UB); }))
755  continue;
756  Updater.AddAvailableValue(UB, Undef);
757  }
758 
759  for (BasicBlock *FI : From)
760  Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
761  AffectedPhis.push_back(Phi);
762  }
763 
764  DeletedPhis.erase(To);
765  }
766  assert(DeletedPhis.empty());
767 
768  AffectedPhis.append(InsertedPhis.begin(), InsertedPhis.end());
769 }
770 
771 void StructurizeCFG::simplifyAffectedPhis() {
772  bool Changed;
773  do {
774  Changed = false;
775  SimplifyQuery Q(Func->getParent()->getDataLayout());
776  Q.DT = DT;
777  // Setting CanUseUndef to true might extend value liveness, set it to false
778  // to achieve better register pressure.
779  Q.CanUseUndef = false;
780  for (WeakVH VH : AffectedPhis) {
781  if (auto Phi = dyn_cast_or_null<PHINode>(VH)) {
782  if (auto NewValue = simplifyInstruction(Phi, Q)) {
783  Phi->replaceAllUsesWith(NewValue);
784  Phi->eraseFromParent();
785  Changed = true;
786  }
787  }
788  }
789  } while (Changed);
790 }
791 
792 /// Remove phi values from all successors and then remove the terminator.
793 void StructurizeCFG::killTerminator(BasicBlock *BB) {
794  Instruction *Term = BB->getTerminator();
795  if (!Term)
796  return;
797 
798  for (BasicBlock *Succ : successors(BB))
799  delPhiValues(BB, Succ);
800 
801  if (DA)
802  DA->removeValue(Term);
803  Term->eraseFromParent();
804 }
805 
806 /// Let node exit(s) point to NewExit
807 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
808  bool IncludeDominator) {
809  if (Node->isSubRegion()) {
810  Region *SubRegion = Node->getNodeAs<Region>();
811  BasicBlock *OldExit = SubRegion->getExit();
812  BasicBlock *Dominator = nullptr;
813 
814  // Find all the edges from the sub region to the exit.
815  // We use make_early_inc_range here because we modify BB's terminator.
817  if (!SubRegion->contains(BB))
818  continue;
819 
820  // Modify the edges to point to the new exit
821  delPhiValues(BB, OldExit);
822  BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
823  addPhiValues(BB, NewExit);
824 
825  // Find the new dominator (if requested)
826  if (IncludeDominator) {
827  if (!Dominator)
828  Dominator = BB;
829  else
830  Dominator = DT->findNearestCommonDominator(Dominator, BB);
831  }
832  }
833 
834  // Change the dominator (if requested)
835  if (Dominator)
836  DT->changeImmediateDominator(NewExit, Dominator);
837 
838  // Update the region info
839  SubRegion->replaceExit(NewExit);
840  } else {
841  BasicBlock *BB = Node->getNodeAs<BasicBlock>();
842  killTerminator(BB);
843  BranchInst *Br = BranchInst::Create(NewExit, BB);
844  Br->setDebugLoc(TermDL[BB]);
845  addPhiValues(BB, NewExit);
846  if (IncludeDominator)
847  DT->changeImmediateDominator(NewExit, BB);
848  }
849 }
850 
851 /// Create a new flow node and update dominator tree and region info
852 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
853  LLVMContext &Context = Func->getContext();
854  BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
855  Order.back()->getEntry();
857  Func, Insert);
858  FlowSet.insert(Flow);
859 
860  // use a temporary variable to avoid a use-after-free if the map's storage is
861  // reallocated
862  DebugLoc DL = TermDL[Dominator];
863  TermDL[Flow] = std::move(DL);
864 
865  DT->addNewBlock(Flow, Dominator);
866  ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
867  return Flow;
868 }
869 
870 /// Create a new or reuse the previous node as flow node
871 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
872  BasicBlock *Entry = PrevNode->getEntry();
873 
874  if (!PrevNode->isSubRegion()) {
875  killTerminator(Entry);
876  if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
877  return Entry;
878  }
879 
880  // create a new flow node
881  BasicBlock *Flow = getNextFlow(Entry);
882 
883  // and wire it up
884  changeExit(PrevNode, Flow, true);
885  PrevNode = ParentRegion->getBBNode(Flow);
886  return Flow;
887 }
888 
889 /// Returns the region exit if possible, otherwise just a new flow node
890 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
891  bool ExitUseAllowed) {
892  if (!Order.empty() || !ExitUseAllowed)
893  return getNextFlow(Flow);
894 
895  BasicBlock *Exit = ParentRegion->getExit();
896  DT->changeImmediateDominator(Exit, Flow);
897  addPhiValues(Flow, Exit);
898  return Exit;
899 }
900 
901 /// Set the previous node
902 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
903  PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
904  : nullptr;
905 }
906 
907 /// Does BB dominate all the predicates of Node?
908 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
909  BBPredicates &Preds = Predicates[Node->getEntry()];
910  return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
911  return DT->dominates(BB, Pred.first);
912  });
913 }
914 
915 /// Can we predict that this node will always be called?
916 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
917  BBPredicates &Preds = Predicates[Node->getEntry()];
918  bool Dominated = false;
919 
920  // Regionentry is always true
921  if (!PrevNode)
922  return true;
923 
924  for (std::pair<BasicBlock*, Value*> Pred : Preds) {
925  BasicBlock *BB = Pred.first;
926  Value *V = Pred.second;
927 
928  if (V != BoolTrue)
929  return false;
930 
931  if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
932  Dominated = true;
933  }
934 
935  // TODO: The dominator check is too strict
936  return Dominated;
937 }
938 
939 /// Take one node from the order vector and wire it up
940 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
941  BasicBlock *LoopEnd) {
942  RegionNode *Node = Order.pop_back_val();
943  Visited.insert(Node->getEntry());
944 
945  if (isPredictableTrue(Node)) {
946  // Just a linear flow
947  if (PrevNode) {
948  changeExit(PrevNode, Node->getEntry(), true);
949  }
950  PrevNode = Node;
951  } else {
952  // Insert extra prefix node (or reuse last one)
953  BasicBlock *Flow = needPrefix(false);
954 
955  // Insert extra postfix node (or use exit instead)
956  BasicBlock *Entry = Node->getEntry();
957  BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
958 
959  // let it point to entry and next block
960  BranchInst *Br = BranchInst::Create(Entry, Next, BoolUndef, Flow);
961  Br->setDebugLoc(TermDL[Flow]);
962  Conditions.push_back(Br);
963  addPhiValues(Flow, Entry);
964  DT->changeImmediateDominator(Entry, Flow);
965 
966  PrevNode = Node;
967  while (!Order.empty() && !Visited.count(LoopEnd) &&
968  dominatesPredicates(Entry, Order.back())) {
969  handleLoops(false, LoopEnd);
970  }
971 
972  changeExit(PrevNode, Next, false);
973  setPrevNode(Next);
974  }
975 }
976 
977 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
978  BasicBlock *LoopEnd) {
979  RegionNode *Node = Order.back();
980  BasicBlock *LoopStart = Node->getEntry();
981 
982  if (!Loops.count(LoopStart)) {
983  wireFlow(ExitUseAllowed, LoopEnd);
984  return;
985  }
986 
987  if (!isPredictableTrue(Node))
988  LoopStart = needPrefix(true);
989 
990  LoopEnd = Loops[Node->getEntry()];
991  wireFlow(false, LoopEnd);
992  while (!Visited.count(LoopEnd)) {
993  handleLoops(false, LoopEnd);
994  }
995 
996  assert(LoopStart != &LoopStart->getParent()->getEntryBlock());
997 
998  // Create an extra loop end node
999  LoopEnd = needPrefix(false);
1000  BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
1001  BranchInst *Br = BranchInst::Create(Next, LoopStart, BoolUndef, LoopEnd);
1002  Br->setDebugLoc(TermDL[LoopEnd]);
1003  LoopConds.push_back(Br);
1004  addPhiValues(LoopEnd, LoopStart);
1005  setPrevNode(Next);
1006 }
1007 
1008 /// After this function control flow looks like it should be, but
1009 /// branches and PHI nodes only have undefined conditions.
1010 void StructurizeCFG::createFlow() {
1011  BasicBlock *Exit = ParentRegion->getExit();
1012  bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
1013 
1014  AffectedPhis.clear();
1015  DeletedPhis.clear();
1016  AddedPhis.clear();
1017  Conditions.clear();
1018  LoopConds.clear();
1019 
1020  PrevNode = nullptr;
1021  Visited.clear();
1022 
1023  while (!Order.empty()) {
1024  handleLoops(EntryDominatesExit, nullptr);
1025  }
1026 
1027  if (PrevNode)
1028  changeExit(PrevNode, Exit, EntryDominatesExit);
1029  else
1030  assert(EntryDominatesExit);
1031 }
1032 
1033 /// Handle a rare case where the disintegrated nodes instructions
1034 /// no longer dominate all their uses. Not sure if this is really necessary
1035 void StructurizeCFG::rebuildSSA() {
1036  SSAUpdater Updater;
1037  for (BasicBlock *BB : ParentRegion->blocks())
1038  for (Instruction &I : *BB) {
1039  bool Initialized = false;
1040  // We may modify the use list as we iterate over it, so we use
1041  // make_early_inc_range.
1042  for (Use &U : llvm::make_early_inc_range(I.uses())) {
1043  Instruction *User = cast<Instruction>(U.getUser());
1044  if (User->getParent() == BB) {
1045  continue;
1046  } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
1047  if (UserPN->getIncomingBlock(U) == BB)
1048  continue;
1049  }
1050 
1051  if (DT->dominates(&I, User))
1052  continue;
1053 
1054  if (!Initialized) {
1055  Value *Undef = UndefValue::get(I.getType());
1056  Updater.Initialize(I.getType(), "");
1057  Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
1058  Updater.AddAvailableValue(BB, &I);
1059  Initialized = true;
1060  }
1061  Updater.RewriteUseAfterInsertions(U);
1062  }
1063  }
1064 }
1065 
1066 static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
1067  const LegacyDivergenceAnalysis &DA) {
1068  // Bool for if all sub-regions are uniform.
1069  bool SubRegionsAreUniform = true;
1070  // Count of how many direct children are conditional.
1071  unsigned ConditionalDirectChildren = 0;
1072 
1073  for (auto *E : R->elements()) {
1074  if (!E->isSubRegion()) {
1075  auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
1076  if (!Br || !Br->isConditional())
1077  continue;
1078 
1079  if (!DA.isUniform(Br))
1080  return false;
1081 
1082  // One of our direct children is conditional.
1083  ConditionalDirectChildren++;
1084 
1085  LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
1086  << " has uniform terminator\n");
1087  } else {
1088  // Explicitly refuse to treat regions as uniform if they have non-uniform
1089  // subregions. We cannot rely on DivergenceAnalysis for branches in
1090  // subregions because those branches may have been removed and re-created,
1091  // so we look for our metadata instead.
1092  //
1093  // Warning: It would be nice to treat regions as uniform based only on
1094  // their direct child basic blocks' terminators, regardless of whether
1095  // subregions are uniform or not. However, this requires a very careful
1096  // look at SIAnnotateControlFlow to make sure nothing breaks there.
1097  for (auto *BB : E->getNodeAs<Region>()->blocks()) {
1098  auto Br = dyn_cast<BranchInst>(BB->getTerminator());
1099  if (!Br || !Br->isConditional())
1100  continue;
1101 
1102  if (!Br->getMetadata(UniformMDKindID)) {
1103  // Early exit if we cannot have relaxed uniform regions.
1104  if (!RelaxedUniformRegions)
1105  return false;
1106 
1107  SubRegionsAreUniform = false;
1108  break;
1109  }
1110  }
1111  }
1112  }
1113 
1114  // Our region is uniform if:
1115  // 1. All conditional branches that are direct children are uniform (checked
1116  // above).
1117  // 2. And either:
1118  // a. All sub-regions are uniform.
1119  // b. There is one or less conditional branches among the direct children.
1120  return SubRegionsAreUniform || (ConditionalDirectChildren <= 1);
1121 }
1122 
1123 void StructurizeCFG::init(Region *R) {
1124  LLVMContext &Context = R->getEntry()->getContext();
1125 
1127  BoolTrue = ConstantInt::getTrue(Context);
1128  BoolFalse = ConstantInt::getFalse(Context);
1129  BoolUndef = UndefValue::get(Boolean);
1130 
1131  this->DA = nullptr;
1132 }
1133 
1134 bool StructurizeCFG::makeUniformRegion(Region *R,
1136  if (R->isTopLevelRegion())
1137  return false;
1138 
1139  this->DA = DA;
1140  // TODO: We could probably be smarter here with how we handle sub-regions.
1141  // We currently rely on the fact that metadata is set by earlier invocations
1142  // of the pass on sub-regions, and that this metadata doesn't get lost --
1143  // but we shouldn't rely on metadata for correctness!
1144  unsigned UniformMDKindID =
1145  R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
1146 
1147  if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
1148  LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
1149  << '\n');
1150 
1151  // Mark all direct child block terminators as having been treated as
1152  // uniform. To account for a possible future in which non-uniform
1153  // sub-regions are treated more cleverly, indirect children are not
1154  // marked as uniform.
1155  MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
1156  for (RegionNode *E : R->elements()) {
1157  if (E->isSubRegion())
1158  continue;
1159 
1160  if (Instruction *Term = E->getEntry()->getTerminator())
1161  Term->setMetadata(UniformMDKindID, MD);
1162  }
1163 
1164  return true;
1165  }
1166  return false;
1167 }
1168 
1169 /// Run the transformation for each region found
1171  if (R->isTopLevelRegion())
1172  return false;
1173 
1174  this->DT = DT;
1175 
1176  Func = R->getEntry()->getParent();
1177  ParentRegion = R;
1178 
1179  orderNodes();
1180  collectInfos();
1181  createFlow();
1182  insertConditions(false);
1183  insertConditions(true);
1184  setPhiValues();
1185  simplifyConditions();
1186  simplifyAffectedPhis();
1187  rebuildSSA();
1188 
1189  // Cleanup
1190  Order.clear();
1191  Visited.clear();
1192  DeletedPhis.clear();
1193  AddedPhis.clear();
1194  Predicates.clear();
1195  Conditions.clear();
1196  Loops.clear();
1197  LoopPreds.clear();
1198  LoopConds.clear();
1199  FlowSet.clear();
1200  TermDL.clear();
1201 
1202  return true;
1203 }
1204 
1205 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
1206  return new StructurizeCFGLegacyPass(SkipUniformRegions);
1207 }
1208 
1209 static void addRegionIntoQueue(Region &R, std::vector<Region *> &Regions) {
1210  Regions.push_back(&R);
1211  for (const auto &E : R)
1212  addRegionIntoQueue(*E, Regions);
1213 }
1214 
1217 
1218  bool Changed = false;
1220  auto &RI = AM.getResult<RegionInfoAnalysis>(F);
1221  std::vector<Region *> Regions;
1222  addRegionIntoQueue(*RI.getTopLevelRegion(), Regions);
1223  while (!Regions.empty()) {
1224  Region *R = Regions.back();
1225  StructurizeCFG SCFG;
1226  SCFG.init(R);
1227  Changed |= SCFG.run(R, DT);
1228  Regions.pop_back();
1229  }
1230  if (!Changed)
1231  return PreservedAnalyses::all();
1232  PreservedAnalyses PA;
1234  return PA;
1235 }
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:52
RegionInfo.h
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3438
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:236
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:104
RegionPass.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
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:774
Scalar.h
llvm::Function
Definition: Function.h:60
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:374
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
hasOnlyUniformBranches
static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const LegacyDivergenceAnalysis &DA)
Definition: StructurizeCFG.cpp:1066
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:691
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:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
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:560
llvm::Boolean
unsigned char Boolean
Definition: ConvertUTF.h:131
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
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:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
STLExtras.h
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2289
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:1400
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
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:1709
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::msgpack::Type::Map
@ Map
FlowBlockName
const char FlowBlockName[]
Definition: StructurizeCFG.cpp:57
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
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
false
Definition: StackSlotColoring.cpp:141
llvm::SSAUpdater::RewriteUseAfterInsertions
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Definition: SSAUpdater.cpp:198
StructurizeCFG.h
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
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:364
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
llvm::cl::Option::getNumOccurrences
int getNumOccurrences() const
Definition: CommandLine.h:403
llvm::LegacyDivergenceAnalysis
Definition: LegacyDivergenceAnalysis.h:31
SmallPtrSet.h
PatternMatch.h
Utils.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:271
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
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:803
BasicBlock.h
llvm::cl::opt< bool >
llvm::AArch64PACKey::DA
@ DA
Definition: AArch64BaseInfo.h:821
VI
@ VI
Definition: SIInstrInfo.cpp:7883
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:110
structurizecfg
structurizecfg
Definition: StructurizeCFG.cpp:373
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:97
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:46
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::StructurizeCFGPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StructurizeCFG.cpp:1215
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3189
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1356
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
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:716
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:6582
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::pdb::PDB_MemoryType::Stack
@ Stack
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:2890
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
CFG
Structurize the CFG
Definition: StructurizeCFG.cpp:374
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::RGPassManager
The pass manager to schedule RegionPasses.
Definition: RegionPass.h:87
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:32
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2134
addRegionIntoQueue
static void addRegionIntoQueue(Region &R, std::vector< Region * > &Regions)
Definition: StructurizeCFG.cpp:1209
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1716
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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:97
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1988
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::RegionInfo
Definition: RegionInfo.h:900
SSAUpdater.h
llvm::ifs::IFSSymbolType::Func
@ Func
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
ValueHandle.h
llvm::LowerSwitchID
char & LowerSwitchID
Definition: LowerSwitch.cpp:577
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:632
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
llvm::createStructurizeCFGPass
Pass * createStructurizeCFGPass(bool SkipUniformRegions=false)
When SkipUniformRegions is true the structizer will not structurize regions that only contain uniform...
Definition: StructurizeCFG.cpp:1205
llvm::HexagonISD::CP
@ CP
Definition: HexagonISelLowering.h:53
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
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:102
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::scc_iterator::isAtEnd
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
Definition: SCCIterator.h:112
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
LegacyDivergenceAnalysis.h
SmallVector.h
Flow
Annotate SI Control Flow
Definition: SIAnnotateControlFlow.cpp:118
Dominators.h
N
#define N
llvm::cl::opt_storage::getValue
DataType & getValue()
Definition: CommandLine.h:1343
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::PHINode
Definition: Instructions.h:2698
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
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:98
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:279
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:37
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
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:69
llvm::cl::desc
Definition: CommandLine.h:413
llvm::Region
Definition: RegionInfo.h:889
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3133
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:60
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3212
llvm::SmallSet::contains
bool contains(const T &V) const
Check if the SmallSet contains the given element.
Definition: SmallSet.h:235
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
SmallSet.h