LLVM  15.0.0git
DFAJumpThreading.cpp
Go to the documentation of this file.
1 //===- DFAJumpThreading.cpp - Threads a switch statement inside a loop ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Transform each threading path to effectively jump thread the DFA. For
10 // example, the CFG below could be transformed as follows, where the cloned
11 // blocks unconditionally branch to the next correct case based on what is
12 // identified in the analysis.
13 //
14 // sw.bb sw.bb
15 // / | \ / | \
16 // case1 case2 case3 case1 case2 case3
17 // \ | / | | |
18 // determinator det.2 det.3 det.1
19 // br sw.bb / | \
20 // sw.bb.2 sw.bb.3 sw.bb.1
21 // br case2 br case3 br case1ยง
22 //
23 // Definitions and Terminology:
24 //
25 // * Threading path:
26 // a list of basic blocks, the exit state, and the block that determines
27 // the next state, for which the following notation will be used:
28 // < path of BBs that form a cycle > [ state, determinator ]
29 //
30 // * Predictable switch:
31 // The switch variable is always a known constant so that all conditional
32 // jumps based on switch variable can be converted to unconditional jump.
33 //
34 // * Determinator:
35 // The basic block that determines the next state of the DFA.
36 //
37 // Representing the optimization in C-like pseudocode: the code pattern on the
38 // left could functionally be transformed to the right pattern if the switch
39 // condition is predictable.
40 //
41 // X = A goto A
42 // for (...) A:
43 // switch (X) ...
44 // case A goto B
45 // X = B B:
46 // case B ...
47 // X = C goto C
48 //
49 // The pass first checks that switch variable X is decided by the control flow
50 // path taken in the loop; for example, in case B, the next value of X is
51 // decided to be C. It then enumerates through all paths in the loop and labels
52 // the basic blocks where the next state is decided.
53 //
54 // Using this information it creates new paths that unconditionally branch to
55 // the next case. This involves cloning code, so it only gets triggered if the
56 // amount of code duplicated is below a threshold.
57 //
58 //===----------------------------------------------------------------------===//
59 
61 #include "llvm/ADT/APInt.h"
62 #include "llvm/ADT/DenseMap.h"
63 #include "llvm/ADT/SmallSet.h"
64 #include "llvm/ADT/Statistic.h"
70 #include "llvm/IR/CFG.h"
71 #include "llvm/IR/Constants.h"
72 #include "llvm/IR/IntrinsicInst.h"
73 #include "llvm/InitializePasses.h"
74 #include "llvm/Pass.h"
76 #include "llvm/Support/Debug.h"
77 #include "llvm/Transforms/Scalar.h"
81 #include <algorithm>
82 #include <deque>
83 
84 #ifdef EXPENSIVE_CHECKS
85 #include "llvm/IR/Verifier.h"
86 #endif
87 
88 using namespace llvm;
89 
90 #define DEBUG_TYPE "dfa-jump-threading"
91 
92 STATISTIC(NumTransforms, "Number of transformations done");
93 STATISTIC(NumCloned, "Number of blocks cloned");
94 STATISTIC(NumPaths, "Number of individual paths threaded");
95 
96 static cl::opt<bool>
97  ClViewCfgBefore("dfa-jump-view-cfg-before",
98  cl::desc("View the CFG before DFA Jump Threading"),
99  cl::Hidden, cl::init(false));
100 
102  "dfa-max-path-length",
103  cl::desc("Max number of blocks searched to find a threading path"),
104  cl::Hidden, cl::init(20));
105 
106 static cl::opt<unsigned>
107  CostThreshold("dfa-cost-threshold",
108  cl::desc("Maximum cost accepted for the transformation"),
109  cl::Hidden, cl::init(50));
110 
111 namespace {
112 
113 class SelectInstToUnfold {
114  SelectInst *SI;
115  PHINode *SIUse;
116 
117 public:
118  SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {}
119 
120  SelectInst *getInst() { return SI; }
121  PHINode *getUse() { return SIUse; }
122 
123  explicit operator bool() const { return SI && SIUse; }
124 };
125 
126 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
127  std::vector<SelectInstToUnfold> *NewSIsToUnfold,
128  std::vector<BasicBlock *> *NewBBs);
129 
130 class DFAJumpThreading {
131 public:
132  DFAJumpThreading(AssumptionCache *AC, DominatorTree *DT,
134  : AC(AC), DT(DT), TTI(TTI), ORE(ORE) {}
135 
136  bool run(Function &F);
137 
138 private:
139  void
140  unfoldSelectInstrs(DominatorTree *DT,
141  const SmallVector<SelectInstToUnfold, 4> &SelectInsts) {
144  for (SelectInstToUnfold SIToUnfold : SelectInsts)
145  Stack.push_back(SIToUnfold);
146 
147  while (!Stack.empty()) {
148  SelectInstToUnfold SIToUnfold = Stack.pop_back_val();
149 
150  std::vector<SelectInstToUnfold> NewSIsToUnfold;
151  std::vector<BasicBlock *> NewBBs;
152  unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs);
153 
154  // Put newly discovered select instructions into the work list.
155  for (const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
156  Stack.push_back(NewSIToUnfold);
157  }
158  }
159 
160  AssumptionCache *AC;
161  DominatorTree *DT;
164 };
165 
166 class DFAJumpThreadingLegacyPass : public FunctionPass {
167 public:
168  static char ID; // Pass identification
169  DFAJumpThreadingLegacyPass() : FunctionPass(ID) {}
170 
171  void getAnalysisUsage(AnalysisUsage &AU) const override {
177  }
178 
179  bool runOnFunction(Function &F) override {
180  if (skipFunction(F))
181  return false;
182 
183  AssumptionCache *AC =
184  &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
185  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
187  &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
189  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
190 
191  return DFAJumpThreading(AC, DT, TTI, ORE).run(F);
192  }
193 };
194 } // end anonymous namespace
195 
197 INITIALIZE_PASS_BEGIN(DFAJumpThreadingLegacyPass, "dfa-jump-threading",
198  "DFA Jump Threading", false, false)
203 INITIALIZE_PASS_END(DFAJumpThreadingLegacyPass, "dfa-jump-threading",
204  "DFA Jump Threading", false, false)
205 
206 // Public interface to the DFA Jump Threading pass
208  return new DFAJumpThreadingLegacyPass();
209 }
210 
211 namespace {
212 
213 /// Create a new basic block and sink \p SIToSink into it.
214 void createBasicBlockAndSinkSelectInst(
215  DomTreeUpdater *DTU, SelectInst *SI, PHINode *SIUse, SelectInst *SIToSink,
216  BasicBlock *EndBlock, StringRef NewBBName, BasicBlock **NewBlock,
217  BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
218  std::vector<BasicBlock *> *NewBBs) {
219  assert(SIToSink->hasOneUse());
220  assert(NewBlock);
221  assert(NewBranch);
222  *NewBlock = BasicBlock::Create(SI->getContext(), NewBBName,
223  EndBlock->getParent(), EndBlock);
224  NewBBs->push_back(*NewBlock);
225  *NewBranch = BranchInst::Create(EndBlock, *NewBlock);
226  SIToSink->moveBefore(*NewBranch);
227  NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
228  DTU->applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
229 }
230 
231 /// Unfold the select instruction held in \p SIToUnfold by replacing it with
232 /// control flow.
233 ///
234 /// Put newly discovered select instructions into \p NewSIsToUnfold. Put newly
235 /// created basic blocks into \p NewBBs.
236 ///
237 /// TODO: merge it with CodeGenPrepare::optimizeSelectInst() if possible.
238 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
239  std::vector<SelectInstToUnfold> *NewSIsToUnfold,
240  std::vector<BasicBlock *> *NewBBs) {
241  SelectInst *SI = SIToUnfold.getInst();
242  PHINode *SIUse = SIToUnfold.getUse();
243  BasicBlock *StartBlock = SI->getParent();
244  BasicBlock *EndBlock = SIUse->getParent();
245  BranchInst *StartBlockTerm =
246  dyn_cast<BranchInst>(StartBlock->getTerminator());
247 
248  assert(StartBlockTerm && StartBlockTerm->isUnconditional());
249  assert(SI->hasOneUse());
250 
251  // These are the new basic blocks for the conditional branch.
252  // At least one will become an actual new basic block.
253  BasicBlock *TrueBlock = nullptr;
254  BasicBlock *FalseBlock = nullptr;
255  BranchInst *TrueBranch = nullptr;
256  BranchInst *FalseBranch = nullptr;
257 
258  // Sink select instructions to be able to unfold them later.
259  if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getTrueValue())) {
260  createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
261  "si.unfold.true", &TrueBlock, &TrueBranch,
262  NewSIsToUnfold, NewBBs);
263  }
264  if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getFalseValue())) {
265  createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
266  "si.unfold.false", &FalseBlock,
267  &FalseBranch, NewSIsToUnfold, NewBBs);
268  }
269 
270  // If there was nothing to sink, then arbitrarily choose the 'false' side
271  // for a new input value to the PHI.
272  if (!TrueBlock && !FalseBlock) {
273  FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false",
274  EndBlock->getParent(), EndBlock);
275  NewBBs->push_back(FalseBlock);
276  BranchInst::Create(EndBlock, FalseBlock);
277  DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
278  }
279 
280  // Insert the real conditional branch based on the original condition.
281  // If we did not create a new block for one of the 'true' or 'false' paths
282  // of the condition, it means that side of the branch goes to the end block
283  // directly and the path originates from the start block from the point of
284  // view of the new PHI.
285  BasicBlock *TT = EndBlock;
286  BasicBlock *FT = EndBlock;
287  if (TrueBlock && FalseBlock) {
288  // A diamond.
289  TT = TrueBlock;
290  FT = FalseBlock;
291 
292  // Update the phi node of SI.
293  SIUse->removeIncomingValue(StartBlock, /* DeletePHIIfEmpty = */ false);
294  SIUse->addIncoming(SI->getTrueValue(), TrueBlock);
295  SIUse->addIncoming(SI->getFalseValue(), FalseBlock);
296 
297  // Update any other PHI nodes in EndBlock.
298  for (PHINode &Phi : EndBlock->phis()) {
299  if (&Phi != SIUse) {
300  Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), TrueBlock);
301  Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), FalseBlock);
302  }
303  }
304  } else {
305  BasicBlock *NewBlock = nullptr;
306  Value *SIOp1 = SI->getTrueValue();
307  Value *SIOp2 = SI->getFalseValue();
308 
309  // A triangle pointing right.
310  if (!TrueBlock) {
311  NewBlock = FalseBlock;
312  FT = FalseBlock;
313  }
314  // A triangle pointing left.
315  else {
316  NewBlock = TrueBlock;
317  TT = TrueBlock;
318  std::swap(SIOp1, SIOp2);
319  }
320 
321  // Update the phi node of SI.
322  for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) {
323  if (SIUse->getIncomingBlock(Idx) == StartBlock)
324  SIUse->setIncomingValue(Idx, SIOp1);
325  }
326  SIUse->addIncoming(SIOp2, NewBlock);
327 
328  // Update any other PHI nodes in EndBlock.
329  for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
330  ++II) {
331  if (Phi != SIUse)
332  Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), NewBlock);
333  }
334  }
335  StartBlockTerm->eraseFromParent();
336  BranchInst::Create(TT, FT, SI->getCondition(), StartBlock);
337  DTU->applyUpdates({{DominatorTree::Insert, StartBlock, TT},
338  {DominatorTree::Insert, StartBlock, FT}});
339 
340  // The select is now dead.
341  SI->eraseFromParent();
342 }
343 
344 struct ClonedBlock {
345  BasicBlock *BB;
346  uint64_t State; ///< \p State corresponds to the next value of a switch stmnt.
347 };
348 
349 typedef std::deque<BasicBlock *> PathType;
350 typedef std::vector<PathType> PathsType;
351 typedef SmallPtrSet<const BasicBlock *, 8> VisitedBlocks;
352 typedef std::vector<ClonedBlock> CloneList;
353 
354 // This data structure keeps track of all blocks that have been cloned. If two
355 // different ThreadingPaths clone the same block for a certain state it should
356 // be reused, and it can be looked up in this map.
357 typedef DenseMap<BasicBlock *, CloneList> DuplicateBlockMap;
358 
359 // This map keeps track of all the new definitions for an instruction. This
360 // information is needed when restoring SSA form after cloning blocks.
362 
363 inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
364  OS << "< ";
365  for (const BasicBlock *BB : Path) {
366  std::string BBName;
367  if (BB->hasName())
368  raw_string_ostream(BBName) << BB->getName();
369  else
370  raw_string_ostream(BBName) << BB;
371  OS << BBName << " ";
372  }
373  OS << ">";
374  return OS;
375 }
376 
377 /// ThreadingPath is a path in the control flow of a loop that can be threaded
378 /// by cloning necessary basic blocks and replacing conditional branches with
379 /// unconditional ones. A threading path includes a list of basic blocks, the
380 /// exit state, and the block that determines the next state.
381 struct ThreadingPath {
382  /// Exit value is DFA's exit state for the given path.
383  uint64_t getExitValue() const { return ExitVal; }
384  void setExitValue(const ConstantInt *V) {
385  ExitVal = V->getZExtValue();
386  IsExitValSet = true;
387  }
388  bool isExitValueSet() const { return IsExitValSet; }
389 
390  /// Determinator is the basic block that determines the next state of the DFA.
391  const BasicBlock *getDeterminatorBB() const { return DBB; }
392  void setDeterminator(const BasicBlock *BB) { DBB = BB; }
393 
394  /// Path is a list of basic blocks.
395  const PathType &getPath() const { return Path; }
396  void setPath(const PathType &NewPath) { Path = NewPath; }
397 
398  void print(raw_ostream &OS) const {
399  OS << Path << " [ " << ExitVal << ", " << DBB->getName() << " ]";
400  }
401 
402 private:
403  PathType Path;
404  uint64_t ExitVal;
405  const BasicBlock *DBB = nullptr;
406  bool IsExitValSet = false;
407 };
408 
409 #ifndef NDEBUG
410 inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
411  TPath.print(OS);
412  return OS;
413 }
414 #endif
415 
416 struct MainSwitch {
417  MainSwitch(SwitchInst *SI, OptimizationRemarkEmitter *ORE) {
418  if (isPredictable(SI)) {
419  Instr = SI;
420  } else {
421  ORE->emit([&]() {
422  return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)
423  << "Switch instruction is not predictable.";
424  });
425  }
426  }
427 
428  virtual ~MainSwitch() = default;
429 
430  SwitchInst *getInstr() const { return Instr; }
431  const SmallVector<SelectInstToUnfold, 4> getSelectInsts() {
432  return SelectInsts;
433  }
434 
435 private:
436  /// Do a use-def chain traversal. Make sure the value of the switch variable
437  /// is always a known constant. This means that all conditional jumps based on
438  /// switch variable can be converted to unconditional jumps.
439  bool isPredictable(const SwitchInst *SI) {
440  std::deque<Instruction *> Q;
441  SmallSet<Value *, 16> SeenValues;
442  SelectInsts.clear();
443 
444  Value *FirstDef = SI->getOperand(0);
445  auto *Inst = dyn_cast<Instruction>(FirstDef);
446 
447  // If this is a function argument or another non-instruction, then give up.
448  // We are interested in loop local variables.
449  if (!Inst)
450  return false;
451 
452  // Require the first definition to be a PHINode
453  if (!isa<PHINode>(Inst))
454  return false;
455 
456  LLVM_DEBUG(dbgs() << "\tisPredictable() FirstDef: " << *Inst << "\n");
457 
458  Q.push_back(Inst);
459  SeenValues.insert(FirstDef);
460 
461  while (!Q.empty()) {
462  Instruction *Current = Q.front();
463  Q.pop_front();
464 
465  if (auto *Phi = dyn_cast<PHINode>(Current)) {
466  for (Value *Incoming : Phi->incoming_values()) {
467  if (!isPredictableValue(Incoming, SeenValues))
468  return false;
469  addInstToQueue(Incoming, Q, SeenValues);
470  }
471  LLVM_DEBUG(dbgs() << "\tisPredictable() phi: " << *Phi << "\n");
472  } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
473  if (!isValidSelectInst(SelI))
474  return false;
475  if (!isPredictableValue(SelI->getTrueValue(), SeenValues) ||
476  !isPredictableValue(SelI->getFalseValue(), SeenValues)) {
477  return false;
478  }
479  addInstToQueue(SelI->getTrueValue(), Q, SeenValues);
480  addInstToQueue(SelI->getFalseValue(), Q, SeenValues);
481  LLVM_DEBUG(dbgs() << "\tisPredictable() select: " << *SelI << "\n");
482  if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
483  SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
484  } else {
485  // If it is neither a phi nor a select, then we give up.
486  return false;
487  }
488  }
489 
490  return true;
491  }
492 
493  bool isPredictableValue(Value *InpVal, SmallSet<Value *, 16> &SeenValues) {
494  if (SeenValues.contains(InpVal))
495  return true;
496 
497  if (isa<ConstantInt>(InpVal))
498  return true;
499 
500  // If this is a function argument or another non-instruction, then give up.
501  if (!isa<Instruction>(InpVal))
502  return false;
503 
504  return true;
505  }
506 
507  void addInstToQueue(Value *Val, std::deque<Instruction *> &Q,
508  SmallSet<Value *, 16> &SeenValues) {
509  if (SeenValues.contains(Val))
510  return;
511  if (Instruction *I = dyn_cast<Instruction>(Val))
512  Q.push_back(I);
513  SeenValues.insert(Val);
514  }
515 
516  bool isValidSelectInst(SelectInst *SI) {
517  if (!SI->hasOneUse())
518  return false;
519 
520  Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
521  // The use of the select inst should be either a phi or another select.
522  if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
523  return false;
524 
525  BasicBlock *SIBB = SI->getParent();
526 
527  // Currently, we can only expand select instructions in basic blocks with
528  // one successor.
529  BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator());
530  if (!SITerm || !SITerm->isUnconditional())
531  return false;
532 
533  if (isa<PHINode>(SIUse) &&
534  SIBB->getSingleSuccessor() != cast<Instruction>(SIUse)->getParent())
535  return false;
536 
537  // If select will not be sunk during unfolding, and it is in the same basic
538  // block as another state defining select, then cannot unfold both.
539  for (SelectInstToUnfold SIToUnfold : SelectInsts) {
540  SelectInst *PrevSI = SIToUnfold.getInst();
541  if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI &&
542  PrevSI->getParent() == SI->getParent())
543  return false;
544  }
545 
546  return true;
547  }
548 
549  SwitchInst *Instr = nullptr;
551 };
552 
553 struct AllSwitchPaths {
554  AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE)
555  : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()),
556  ORE(ORE) {}
557 
558  std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
559  unsigned getNumThreadingPaths() { return TPaths.size(); }
560  SwitchInst *getSwitchInst() { return Switch; }
561  BasicBlock *getSwitchBlock() { return SwitchBlock; }
562 
563  void run() {
564  VisitedBlocks Visited;
565  PathsType LoopPaths = paths(SwitchBlock, Visited, /* PathDepth = */ 1);
566  StateDefMap StateDef = getStateDefMap();
567 
568  for (PathType Path : LoopPaths) {
569  ThreadingPath TPath;
570 
571  const BasicBlock *PrevBB = Path.back();
572  for (const BasicBlock *BB : Path) {
573  if (StateDef.count(BB) != 0) {
574  const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
575  assert(Phi && "Expected a state-defining instr to be a phi node.");
576 
577  const Value *V = Phi->getIncomingValueForBlock(PrevBB);
578  if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) {
579  TPath.setExitValue(C);
580  TPath.setDeterminator(BB);
581  TPath.setPath(Path);
582  }
583  }
584 
585  // Switch block is the determinator, this is the final exit value.
586  if (TPath.isExitValueSet() && BB == Path.front())
587  break;
588 
589  PrevBB = BB;
590  }
591 
592  if (TPath.isExitValueSet() && isSupported(TPath))
593  TPaths.push_back(TPath);
594  }
595  }
596 
597 private:
598  // Value: an instruction that defines a switch state;
599  // Key: the parent basic block of that instruction.
601 
602  PathsType paths(BasicBlock *BB, VisitedBlocks &Visited,
603  unsigned PathDepth) const {
604  PathsType Res;
605 
606  // Stop exploring paths after visiting MaxPathLength blocks
607  if (PathDepth > MaxPathLength) {
608  ORE->emit([&]() {
609  return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached",
610  Switch)
611  << "Exploration stopped after visiting MaxPathLength="
612  << ore::NV("MaxPathLength", MaxPathLength) << " blocks.";
613  });
614  return Res;
615  }
616 
617  Visited.insert(BB);
618 
619  // Some blocks have multiple edges to the same successor, and this set
620  // is used to prevent a duplicate path from being generated
621  SmallSet<BasicBlock *, 4> Successors;
622  for (BasicBlock *Succ : successors(BB)) {
623  if (!Successors.insert(Succ).second)
624  continue;
625 
626  // Found a cycle through the SwitchBlock
627  if (Succ == SwitchBlock) {
628  Res.push_back({BB});
629  continue;
630  }
631 
632  // We have encountered a cycle, do not get caught in it
633  if (Visited.contains(Succ))
634  continue;
635 
636  PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
637  for (PathType Path : SuccPaths) {
638  PathType NewPath(Path);
639  NewPath.push_front(BB);
640  Res.push_back(NewPath);
641  }
642  }
643  // This block could now be visited again from a different predecessor. Note
644  // that this will result in exponential runtime. Subpaths could possibly be
645  // cached but it takes a lot of memory to store them.
646  Visited.erase(BB);
647  return Res;
648  }
649 
650  /// Walk the use-def chain and collect all the state-defining instructions.
651  StateDefMap getStateDefMap() const {
652  StateDefMap Res;
653 
654  Value *FirstDef = Switch->getOperand(0);
655 
656  assert(isa<PHINode>(FirstDef) && "After select unfolding, all state "
657  "definitions are expected to be phi "
658  "nodes.");
659 
661  Stack.push_back(dyn_cast<PHINode>(FirstDef));
662  SmallSet<Value *, 16> SeenValues;
663 
664  while (!Stack.empty()) {
665  PHINode *CurPhi = Stack.pop_back_val();
666 
667  Res[CurPhi->getParent()] = CurPhi;
668  SeenValues.insert(CurPhi);
669 
670  for (Value *Incoming : CurPhi->incoming_values()) {
671  if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
672  SeenValues.contains(Incoming)) {
673  continue;
674  }
675 
676  assert(isa<PHINode>(Incoming) && "After select unfolding, all state "
677  "definitions are expected to be phi "
678  "nodes.");
679 
680  Stack.push_back(cast<PHINode>(Incoming));
681  }
682  }
683 
684  return Res;
685  }
686 
687  /// The determinator BB should precede the switch-defining BB.
688  ///
689  /// Otherwise, it is possible that the state defined in the determinator block
690  /// defines the state for the next iteration of the loop, rather than for the
691  /// current one.
692  ///
693  /// Currently supported paths:
694  /// \code
695  /// < switch bb1 determ def > [ 42, determ ]
696  /// < switch_and_def bb1 determ > [ 42, determ ]
697  /// < switch_and_def_and_determ bb1 > [ 42, switch_and_def_and_determ ]
698  /// \endcode
699  ///
700  /// Unsupported paths:
701  /// \code
702  /// < switch bb1 def determ > [ 43, determ ]
703  /// < switch_and_determ bb1 def > [ 43, switch_and_determ ]
704  /// \endcode
705  bool isSupported(const ThreadingPath &TPath) {
706  Instruction *SwitchCondI = dyn_cast<Instruction>(Switch->getCondition());
707  assert(SwitchCondI);
708  if (!SwitchCondI)
709  return false;
710 
711  const BasicBlock *SwitchCondDefBB = SwitchCondI->getParent();
712  const BasicBlock *SwitchCondUseBB = Switch->getParent();
713  const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
714 
715  assert(
716  SwitchCondUseBB == TPath.getPath().front() &&
717  "The first BB in a threading path should have the switch instruction");
718  if (SwitchCondUseBB != TPath.getPath().front())
719  return false;
720 
721  // Make DeterminatorBB the first element in Path.
722  PathType Path = TPath.getPath();
723  auto ItDet = std::find(Path.begin(), Path.end(), DeterminatorBB);
724  std::rotate(Path.begin(), ItDet, Path.end());
725 
726  bool IsDetBBSeen = false;
727  bool IsDefBBSeen = false;
728  bool IsUseBBSeen = false;
729  for (BasicBlock *BB : Path) {
730  if (BB == DeterminatorBB)
731  IsDetBBSeen = true;
732  if (BB == SwitchCondDefBB)
733  IsDefBBSeen = true;
734  if (BB == SwitchCondUseBB)
735  IsUseBBSeen = true;
736  if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
737  return false;
738  }
739 
740  return true;
741  }
742 
744  BasicBlock *SwitchBlock;
746  std::vector<ThreadingPath> TPaths;
747 };
748 
749 struct TransformDFA {
750  TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT,
754  : SwitchPaths(SwitchPaths), DT(DT), AC(AC), TTI(TTI), ORE(ORE),
755  EphValues(EphValues) {}
756 
757  void run() {
758  if (isLegalAndProfitableToTransform()) {
759  createAllExitPaths();
760  NumTransforms++;
761  }
762  }
763 
764 private:
765  /// This function performs both a legality check and profitability check at
766  /// the same time since it is convenient to do so. It iterates through all
767  /// blocks that will be cloned, and keeps track of the duplication cost. It
768  /// also returns false if it is illegal to clone some required block.
769  bool isLegalAndProfitableToTransform() {
771  SwitchInst *Switch = SwitchPaths->getSwitchInst();
772 
773  // Note that DuplicateBlockMap is not being used as intended here. It is
774  // just being used to ensure (BB, State) pairs are only counted once.
775  DuplicateBlockMap DuplicateMap;
776 
777  for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
778  PathType PathBBs = TPath.getPath();
779  uint64_t NextState = TPath.getExitValue();
780  const BasicBlock *Determinator = TPath.getDeterminatorBB();
781 
782  // Update Metrics for the Switch block, this is always cloned
783  BasicBlock *BB = SwitchPaths->getSwitchBlock();
784  BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
785  if (!VisitedBB) {
786  Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
787  DuplicateMap[BB].push_back({BB, NextState});
788  }
789 
790  // If the Switch block is the Determinator, then we can continue since
791  // this is the only block that is cloned and we already counted for it.
792  if (PathBBs.front() == Determinator)
793  continue;
794 
795  // Otherwise update Metrics for all blocks that will be cloned. If any
796  // block is already cloned and would be reused, don't double count it.
797  auto DetIt = std::find(PathBBs.begin(), PathBBs.end(), Determinator);
798  for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
799  BB = *BBIt;
800  VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
801  if (VisitedBB)
802  continue;
803  Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
804  DuplicateMap[BB].push_back({BB, NextState});
805  }
806 
807  if (Metrics.notDuplicatable) {
808  LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
809  << "non-duplicatable instructions.\n");
810  ORE->emit([&]() {
811  return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst",
812  Switch)
813  << "Contains non-duplicatable instructions.";
814  });
815  return false;
816  }
817 
818  if (Metrics.convergent) {
819  LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
820  << "convergent instructions.\n");
821  ORE->emit([&]() {
822  return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
823  << "Contains convergent instructions.";
824  });
825  return false;
826  }
827  }
828 
829  unsigned DuplicationCost = 0;
830 
831  unsigned JumpTableSize = 0;
832  TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr,
833  nullptr);
834  if (JumpTableSize == 0) {
835  // Factor in the number of conditional branches reduced from jump
836  // threading. Assume that lowering the switch block is implemented by
837  // using binary search, hence the LogBase2().
838  unsigned CondBranches =
839  APInt(32, Switch->getNumSuccessors()).ceilLogBase2();
840  DuplicationCost = Metrics.NumInsts / CondBranches;
841  } else {
842  // Compared with jump tables, the DFA optimizer removes an indirect branch
843  // on each loop iteration, thus making branch prediction more precise. The
844  // more branch targets there are, the more likely it is for the branch
845  // predictor to make a mistake, and the more benefit there is in the DFA
846  // optimizer. Thus, the more branch targets there are, the lower is the
847  // cost of the DFA opt.
848  DuplicationCost = Metrics.NumInsts / JumpTableSize;
849  }
850 
851  LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "
852  << SwitchPaths->getSwitchBlock()->getName()
853  << " is: " << DuplicationCost << "\n\n");
854 
855  if (DuplicationCost > CostThreshold) {
856  LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "
857  << "cost threshold.\n");
858  ORE->emit([&]() {
859  return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
860  << "Duplication cost exceeds the cost threshold (cost="
861  << ore::NV("Cost", DuplicationCost)
862  << ", threshold=" << ore::NV("Threshold", CostThreshold) << ").";
863  });
864  return false;
865  }
866 
867  ORE->emit([&]() {
868  return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch)
869  << "Switch statement jump-threaded.";
870  });
871 
872  return true;
873  }
874 
875  /// Transform each threading path to effectively jump thread the DFA.
876  void createAllExitPaths() {
878 
879  // Move the switch block to the end of the path, since it will be duplicated
880  BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
881  for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
882  LLVM_DEBUG(dbgs() << TPath << "\n");
883  PathType NewPath(TPath.getPath());
884  NewPath.push_back(SwitchBlock);
885  TPath.setPath(NewPath);
886  }
887 
888  // Transform the ThreadingPaths and keep track of the cloned values
889  DuplicateBlockMap DuplicateMap;
890  DefMap NewDefs;
891 
892  SmallSet<BasicBlock *, 16> BlocksToClean;
893  for (BasicBlock *BB : successors(SwitchBlock))
894  BlocksToClean.insert(BB);
895 
896  for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
897  createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
898  NumPaths++;
899  }
900 
901  // After all paths are cloned, now update the last successor of the cloned
902  // path so it skips over the switch statement
903  for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
904  updateLastSuccessor(TPath, DuplicateMap, &DTU);
905 
906  // For each instruction that was cloned and used outside, update its uses
907  updateSSA(NewDefs);
908 
909  // Clean PHI Nodes for the newly created blocks
910  for (BasicBlock *BB : BlocksToClean)
911  cleanPhiNodes(BB);
912  }
913 
914  /// For a specific ThreadingPath \p Path, create an exit path starting from
915  /// the determinator block.
916  ///
917  /// To remember the correct destination, we have to duplicate blocks
918  /// corresponding to each state. Also update the terminating instruction of
919  /// the predecessors, and phis in the successor blocks.
920  void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
921  DuplicateBlockMap &DuplicateMap,
922  SmallSet<BasicBlock *, 16> &BlocksToClean,
923  DomTreeUpdater *DTU) {
924  uint64_t NextState = Path.getExitValue();
925  const BasicBlock *Determinator = Path.getDeterminatorBB();
926  PathType PathBBs = Path.getPath();
927 
928  // Don't select the placeholder block in front
929  if (PathBBs.front() == Determinator)
930  PathBBs.pop_front();
931 
932  auto DetIt = std::find(PathBBs.begin(), PathBBs.end(), Determinator);
933  auto Prev = std::prev(DetIt);
934  BasicBlock *PrevBB = *Prev;
935  for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
936  BasicBlock *BB = *BBIt;
937  BlocksToClean.insert(BB);
938 
939  // We already cloned BB for this NextState, now just update the branch
940  // and continue.
941  BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
942  if (NextBB) {
943  updatePredecessor(PrevBB, BB, NextBB, DTU);
944  PrevBB = NextBB;
945  continue;
946  }
947 
948  // Clone the BB and update the successor of Prev to jump to the new block
949  BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
950  BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
951  DuplicateMap[BB].push_back({NewBB, NextState});
952  BlocksToClean.insert(NewBB);
953  PrevBB = NewBB;
954  }
955  }
956 
957  /// Restore SSA form after cloning blocks.
958  ///
959  /// Each cloned block creates new defs for a variable, and the uses need to be
960  /// updated to reflect this. The uses may be replaced with a cloned value, or
961  /// some derived phi instruction. Note that all uses of a value defined in the
962  /// same block were already remapped when cloning the block.
963  void updateSSA(DefMap &NewDefs) {
964  SSAUpdaterBulk SSAUpdate;
965  SmallVector<Use *, 16> UsesToRename;
966 
967  for (auto KV : NewDefs) {
968  Instruction *I = KV.first;
969  BasicBlock *BB = I->getParent();
970  std::vector<Instruction *> Cloned = KV.second;
971 
972  // Scan all uses of this instruction to see if it is used outside of its
973  // block, and if so, record them in UsesToRename.
974  for (Use &U : I->uses()) {
975  Instruction *User = cast<Instruction>(U.getUser());
976  if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
977  if (UserPN->getIncomingBlock(U) == BB)
978  continue;
979  } else if (User->getParent() == BB) {
980  continue;
981  }
982 
983  UsesToRename.push_back(&U);
984  }
985 
986  // If there are no uses outside the block, we're done with this
987  // instruction.
988  if (UsesToRename.empty())
989  continue;
990  LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I
991  << "\n");
992 
993  // We found a use of I outside of BB. Rename all uses of I that are
994  // outside its block to be uses of the appropriate PHI node etc. See
995  // ValuesInBlocks with the values we know.
996  unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());
997  SSAUpdate.AddAvailableValue(VarNum, BB, I);
998  for (Instruction *New : Cloned)
999  SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New);
1000 
1001  while (!UsesToRename.empty())
1002  SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val());
1003 
1004  LLVM_DEBUG(dbgs() << "\n");
1005  }
1006  // SSAUpdater handles phi placement and renaming uses with the appropriate
1007  // value.
1008  SSAUpdate.RewriteAllUses(DT);
1009  }
1010 
1011  /// Clones a basic block, and adds it to the CFG.
1012  ///
1013  /// This function also includes updating phi nodes in the successors of the
1014  /// BB, and remapping uses that were defined locally in the cloned BB.
1015  BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
1016  uint64_t NextState,
1017  DuplicateBlockMap &DuplicateMap,
1018  DefMap &NewDefs,
1019  DomTreeUpdater *DTU) {
1020  ValueToValueMapTy VMap;
1021  BasicBlock *NewBB = CloneBasicBlock(
1022  BB, VMap, ".jt" + std::to_string(NextState), BB->getParent());
1023  NewBB->moveAfter(BB);
1024  NumCloned++;
1025 
1026  for (Instruction &I : *NewBB) {
1027  // Do not remap operands of PHINode in case a definition in BB is an
1028  // incoming value to a phi in the same block. This incoming value will
1029  // be renamed later while restoring SSA.
1030  if (isa<PHINode>(&I))
1031  continue;
1032  RemapInstruction(&I, VMap,
1034  if (AssumeInst *II = dyn_cast<AssumeInst>(&I))
1035  AC->registerAssumption(II);
1036  }
1037 
1038  updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1039  updatePredecessor(PrevBB, BB, NewBB, DTU);
1040  updateDefMap(NewDefs, VMap);
1041 
1042  // Add all successors to the DominatorTree
1044  for (auto *SuccBB : successors(NewBB)) {
1045  if (SuccSet.insert(SuccBB).second)
1046  DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1047  }
1048  SuccSet.clear();
1049  return NewBB;
1050  }
1051 
1052  /// Update the phi nodes in BB's successors.
1053  ///
1054  /// This means creating a new incoming value from NewBB with the new
1055  /// instruction wherever there is an incoming value from BB.
1056  void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1057  uint64_t NextState, ValueToValueMapTy &VMap,
1058  DuplicateBlockMap &DuplicateMap) {
1059  std::vector<BasicBlock *> BlocksToUpdate;
1060 
1061  // If BB is the last block in the path, we can simply update the one case
1062  // successor that will be reached.
1063  if (BB == SwitchPaths->getSwitchBlock()) {
1064  SwitchInst *Switch = SwitchPaths->getSwitchInst();
1065  BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1066  BlocksToUpdate.push_back(NextCase);
1067  BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1068  if (ClonedSucc)
1069  BlocksToUpdate.push_back(ClonedSucc);
1070  }
1071  // Otherwise update phis in all successors.
1072  else {
1073  for (BasicBlock *Succ : successors(BB)) {
1074  BlocksToUpdate.push_back(Succ);
1075 
1076  // Check if a successor has already been cloned for the particular exit
1077  // value. In this case if a successor was already cloned, the phi nodes
1078  // in the cloned block should be updated directly.
1079  BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1080  if (ClonedSucc)
1081  BlocksToUpdate.push_back(ClonedSucc);
1082  }
1083  }
1084 
1085  // If there is a phi with an incoming value from BB, create a new incoming
1086  // value for the new predecessor ClonedBB. The value will either be the same
1087  // value from BB or a cloned value.
1088  for (BasicBlock *Succ : BlocksToUpdate) {
1089  for (auto II = Succ->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
1090  ++II) {
1091  Value *Incoming = Phi->getIncomingValueForBlock(BB);
1092  if (Incoming) {
1093  if (isa<Constant>(Incoming)) {
1094  Phi->addIncoming(Incoming, ClonedBB);
1095  continue;
1096  }
1097  Value *ClonedVal = VMap[Incoming];
1098  if (ClonedVal)
1099  Phi->addIncoming(ClonedVal, ClonedBB);
1100  else
1101  Phi->addIncoming(Incoming, ClonedBB);
1102  }
1103  }
1104  }
1105  }
1106 
1107  /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all
1108  /// other successors are kept as well.
1109  void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1110  BasicBlock *NewBB, DomTreeUpdater *DTU) {
1111  // When a path is reused, there is a chance that predecessors were already
1112  // updated before. Check if the predecessor needs to be updated first.
1113  if (!isPredecessor(OldBB, PrevBB))
1114  return;
1115 
1116  Instruction *PrevTerm = PrevBB->getTerminator();
1117  for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) {
1118  if (PrevTerm->getSuccessor(Idx) == OldBB) {
1119  OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true);
1120  PrevTerm->setSuccessor(Idx, NewBB);
1121  }
1122  }
1123  DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1124  {DominatorTree::Insert, PrevBB, NewBB}});
1125  }
1126 
1127  /// Add new value mappings to the DefMap to keep track of all new definitions
1128  /// for a particular instruction. These will be used while updating SSA form.
1129  void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
1131  NewDefsVector.reserve(VMap.size());
1132 
1133  for (auto Entry : VMap) {
1134  Instruction *Inst =
1135  dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
1136  if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1137  isa<SwitchInst>(Inst)) {
1138  continue;
1139  }
1140 
1141  Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1142  if (!Cloned)
1143  continue;
1144 
1145  NewDefsVector.push_back({Inst, Cloned});
1146  }
1147 
1148  // Sort the defs to get deterministic insertion order into NewDefs.
1149  sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {
1150  if (LHS.first == RHS.first)
1151  return LHS.second->comesBefore(RHS.second);
1152  return LHS.first->comesBefore(RHS.first);
1153  });
1154 
1155  for (const auto &KV : NewDefsVector)
1156  NewDefs[KV.first].push_back(KV.second);
1157  }
1158 
1159  /// Update the last branch of a particular cloned path to point to the correct
1160  /// case successor.
1161  ///
1162  /// Note that this is an optional step and would have been done in later
1163  /// optimizations, but it makes the CFG significantly easier to work with.
1164  void updateLastSuccessor(ThreadingPath &TPath,
1165  DuplicateBlockMap &DuplicateMap,
1166  DomTreeUpdater *DTU) {
1167  uint64_t NextState = TPath.getExitValue();
1168  BasicBlock *BB = TPath.getPath().back();
1169  BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1170 
1171  // Note multiple paths can end at the same block so check that it is not
1172  // updated yet
1173  if (!isa<SwitchInst>(LastBlock->getTerminator()))
1174  return;
1175  SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator());
1176  BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1177 
1178  std::vector<DominatorTree::UpdateType> DTUpdates;
1180  for (BasicBlock *Succ : successors(LastBlock)) {
1181  if (Succ != NextCase && SuccSet.insert(Succ).second)
1182  DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1183  }
1184 
1185  Switch->eraseFromParent();
1186  BranchInst::Create(NextCase, LastBlock);
1187 
1188  DTU->applyUpdates(DTUpdates);
1189  }
1190 
1191  /// After cloning blocks, some of the phi nodes have extra incoming values
1192  /// that are no longer used. This function removes them.
1193  void cleanPhiNodes(BasicBlock *BB) {
1194  // If BB is no longer reachable, remove any remaining phi nodes
1195  if (pred_empty(BB)) {
1196  std::vector<PHINode *> PhiToRemove;
1197  for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1198  PhiToRemove.push_back(Phi);
1199  }
1200  for (PHINode *PN : PhiToRemove) {
1201  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
1202  PN->eraseFromParent();
1203  }
1204  return;
1205  }
1206 
1207  // Remove any incoming values that come from an invalid predecessor
1208  for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1209  std::vector<BasicBlock *> BlocksToRemove;
1210  for (BasicBlock *IncomingBB : Phi->blocks()) {
1211  if (!isPredecessor(BB, IncomingBB))
1212  BlocksToRemove.push_back(IncomingBB);
1213  }
1214  for (BasicBlock *BB : BlocksToRemove)
1215  Phi->removeIncomingValue(BB);
1216  }
1217  }
1218 
1219  /// Checks if BB was already cloned for a particular next state value. If it
1220  /// was then it returns this cloned block, and otherwise null.
1221  BasicBlock *getClonedBB(BasicBlock *BB, uint64_t NextState,
1222  DuplicateBlockMap &DuplicateMap) {
1223  CloneList ClonedBBs = DuplicateMap[BB];
1224 
1225  // Find an entry in the CloneList with this NextState. If it exists then
1226  // return the corresponding BB
1227  auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {
1228  return C.State == NextState;
1229  });
1230  return It != ClonedBBs.end() ? (*It).BB : nullptr;
1231  }
1232 
1233  /// Helper to get the successor corresponding to a particular case value for
1234  /// a switch statement.
1235  BasicBlock *getNextCaseSuccessor(SwitchInst *Switch, uint64_t NextState) {
1236  BasicBlock *NextCase = nullptr;
1237  for (auto Case : Switch->cases()) {
1238  if (Case.getCaseValue()->getZExtValue() == NextState) {
1239  NextCase = Case.getCaseSuccessor();
1240  break;
1241  }
1242  }
1243  if (!NextCase)
1244  NextCase = Switch->getDefaultDest();
1245  return NextCase;
1246  }
1247 
1248  /// Returns true if IncomingBB is a predecessor of BB.
1249  bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1250  return llvm::find(predecessors(BB), IncomingBB) != pred_end(BB);
1251  }
1252 
1253  AllSwitchPaths *SwitchPaths;
1254  DominatorTree *DT;
1255  AssumptionCache *AC;
1259  std::vector<ThreadingPath> TPaths;
1260 };
1261 
1263  LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");
1264 
1265  if (F.hasOptSize()) {
1266  LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n");
1267  return false;
1268  }
1269 
1270  if (ClViewCfgBefore)
1271  F.viewCFG();
1272 
1273  SmallVector<AllSwitchPaths, 2> ThreadableLoops;
1274  bool MadeChanges = false;
1275 
1276  for (BasicBlock &BB : F) {
1277  auto *SI = dyn_cast<SwitchInst>(BB.getTerminator());
1278  if (!SI)
1279  continue;
1280 
1281  LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName()
1282  << " is predictable\n");
1283  MainSwitch Switch(SI, ORE);
1284 
1285  if (!Switch.getInstr())
1286  continue;
1287 
1288  LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
1289  << "candidate for jump threading\n");
1290  LLVM_DEBUG(SI->dump());
1291 
1292  unfoldSelectInstrs(DT, Switch.getSelectInsts());
1293  if (!Switch.getSelectInsts().empty())
1294  MadeChanges = true;
1295 
1296  AllSwitchPaths SwitchPaths(&Switch, ORE);
1297  SwitchPaths.run();
1298 
1299  if (SwitchPaths.getNumThreadingPaths() > 0) {
1300  ThreadableLoops.push_back(SwitchPaths);
1301 
1302  // For the time being limit this optimization to occurring once in a
1303  // function since it can change the CFG significantly. This is not a
1304  // strict requirement but it can cause buggy behavior if there is an
1305  // overlap of blocks in different opportunities. There is a lot of room to
1306  // experiment with catching more opportunities here.
1307  break;
1308  }
1309  }
1310 
1312  if (ThreadableLoops.size() > 0)
1313  CodeMetrics::collectEphemeralValues(&F, AC, EphValues);
1314 
1315  for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1316  TransformDFA Transform(&SwitchPaths, DT, AC, TTI, ORE, EphValues);
1317  Transform.run();
1318  MadeChanges = true;
1319  }
1320 
1321 #ifdef EXPENSIVE_CHECKS
1323  verifyFunction(F, &dbgs());
1324 #endif
1325 
1326  return MadeChanges;
1327 }
1328 
1329 } // end anonymous namespace
1330 
1331 /// Integrate with the new Pass Manager
1338 
1339  if (!DFAJumpThreading(&AC, &DT, &TTI, &ORE).run(F))
1340  return PreservedAnalyses::all();
1341 
1342  PreservedAnalyses PA;
1344  return PA;
1345 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
AssumptionCache.h
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2461
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:735
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:224
ValueMapper.h
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2750
llvm::ARM::PredBlockMask::TT
@ TT
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.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:780
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::Function
Definition: Function.h:60
llvm::SSAUpdaterBulk::AddUse
void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
Definition: SSAUpdaterBulk.cpp:61
Pass.h
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:632
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::CodeMetrics
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:30
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
DomTreeUpdater.h
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:113
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::verifyFunction
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:6129
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1410
APInt.h
llvm::coro::ABI::Switch
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
DenseMap.h
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:291
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
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::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet< const BasicBlock *, 8 >
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::SelectInst::getFalseValue
const Value * getFalseValue() const
Definition: Instructions.h:1786
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2763
ClViewCfgBefore
static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
CodeMetrics.h
llvm::ValueMap::size
size_type size() const
Definition: ValueMap.h:141
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::RemapInstruction
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
Definition: ValueMapper.h:254
llvm::createDFAJumpThreadingPass
FunctionPass * createDFAJumpThreadingPass()
Definition: DFAJumpThreading.cpp:207
SSAUpdaterBulk.h
Constants.h
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
paths
Reduce control height in the hot paths
Definition: ControlHeightReduction.cpp:139
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::SSAUpdaterBulk
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdaterBulk.h:39
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2849
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:355
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1769
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::CodeMetrics::collectEphemeralValues
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:70
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
llvm::pdb::PDB_ColorItem::Path
@ Path
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
llvm::RF_NoModuleLevelChanges
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:71
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:101
jump
The object format emitted by the WebAssembly backed is documented see the home and packaging for producing WebAssembly applications that can run in browsers and other environments wasi sdk provides a more minimal C C SDK based on llvm and a libc based on for producing WebAssemmbly applictions that use the WASI ABI Rust provides WebAssembly support integrated into Cargo There are two main which provides a relatively minimal environment that has an emphasis on being native wasm32 unknown which uses Emscripten internally and provides standard C C filesystem GL and SDL bindings For more and br_table instructions can support having a value on the value stack across the jump(sometimes). We should(a) model this
llvm::CloneBasicBlock
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
Definition: CloneFunction.cpp:41
llvm::cl::opt< bool >
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
uint64_t
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2517
CostThreshold
static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1627
llvm::DFAJumpThreadingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Integrate with the new Pass Manager.
Definition: DFAJumpThreading.cpp:1332
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2814
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3155
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::SelectInst::getTrueValue
const Value * getTrueValue() const
Definition: Instructions.h:1785
Metrics
Machine Trace Metrics
Definition: MachineTraceMetrics.cpp:53
llvm::pdb::PDB_MemoryType::Stack
@ Stack
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:162
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3177
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::BasicBlock::moveAfter
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:141
llvm::PHINode::blocks
iterator_range< block_iterator > blocks()
Definition: Instructions.h:2742
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Instruction::setSuccessor
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Definition: Instruction.cpp:801
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
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
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:868
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
DEBUG_TYPE
#define DEBUG_TYPE
Definition: DFAJumpThreading.cpp:90
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
llvm::OptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: DiagnosticInfo.h:781
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::ValueMap< const Value *, WeakTrackingVH >
Threading
dfa jump DFA Jump Threading
Definition: DFAJumpThreading.cpp:204
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1634
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:142
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:89
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:146
Verifier.h
rotate
The same transformation can work with an even modulo with the addition of a rotate
Definition: README.txt:680
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::SSAUpdaterBulk::AddVariable
unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
Definition: SSAUpdaterBulk.cpp:40
MaxPathLength
static cl::opt< unsigned > MaxPathLength("dfa-max-path-length", cl::desc("Max number of blocks searched to find a threading path"), cl::Hidden, cl::init(20))
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1552
llvm::APInt::ceilLogBase2
unsigned ceilLogBase2() const
Definition: APInt.h:1667
llvm::SSAUpdaterBulk::AddAvailableValue
void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdaterBulk.cpp:51
llvm::TargetTransformInfo::getEstimatedNumberOfCaseClusters
unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) const
Definition: TargetTransformInfo.cpp:210
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:690
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:86
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
TargetTransformInfo.h
llvm::SmallSet::clear
void clear()
Definition: SmallSet.h:220
llvm::PHINode
Definition: Instructions.h:2664
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:318
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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
threading
dfa jump threading
Definition: DFAJumpThreading.cpp:203
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3243
llvm::cl::desc
Definition: CommandLine.h:405
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3099
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::SSAUpdaterBulk::RewriteAllUses
void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
Definition: SSAUpdaterBulk.cpp:122
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(DFAJumpThreadingLegacyPass, "dfa-jump-threading", "DFA Jump Threading", false, false) INITIALIZE_PASS_END(DFAJumpThreadingLegacyPass
llvm::SmallSet::contains
bool contains(const T &V) const
Check if the SmallSet contains the given element.
Definition: SmallSet.h:238
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:96
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
SmallSet.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
DFAJumpThreading.h