LLVM 22.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/Statistic.h"
71#include "llvm/IR/CFG.h"
72#include "llvm/IR/Constants.h"
75#include "llvm/Support/Debug.h"
79#include <deque>
80
81#ifdef EXPENSIVE_CHECKS
82#include "llvm/IR/Verifier.h"
83#endif
84
85using namespace llvm;
86
87#define DEBUG_TYPE "dfa-jump-threading"
88
89STATISTIC(NumTransforms, "Number of transformations done");
90STATISTIC(NumCloned, "Number of blocks cloned");
91STATISTIC(NumPaths, "Number of individual paths threaded");
92
93namespace llvm {
94static cl::opt<bool>
95 ClViewCfgBefore("dfa-jump-view-cfg-before",
96 cl::desc("View the CFG before DFA Jump Threading"),
97 cl::Hidden, cl::init(false));
98
100 "dfa-early-exit-heuristic",
101 cl::desc("Exit early if an unpredictable value come from the same loop"),
102 cl::Hidden, cl::init(true));
103
105 "dfa-max-path-length",
106 cl::desc("Max number of blocks searched to find a threading path"),
107 cl::Hidden, cl::init(20));
108
110 "dfa-max-num-visited-paths",
111 cl::desc(
112 "Max number of blocks visited while enumerating paths around a switch"),
113 cl::Hidden, cl::init(2500));
114
116 MaxNumPaths("dfa-max-num-paths",
117 cl::desc("Max number of paths enumerated around a switch"),
118 cl::Hidden, cl::init(200));
119
121 CostThreshold("dfa-cost-threshold",
122 cl::desc("Maximum cost accepted for the transformation"),
123 cl::Hidden, cl::init(50));
124
126 "dfa-max-cloned-rate",
127 cl::desc(
128 "Maximum cloned instructions rate accepted for the transformation"),
129 cl::Hidden, cl::init(7.5));
130
132 MaxOuterUseBlocks("dfa-max-out-use-blocks",
133 cl::desc("Maximum unduplicated blocks with outer uses "
134 "accepted for the transformation"),
135 cl::Hidden, cl::init(40));
136
138
139} // namespace llvm
140
141namespace {
142class SelectInstToUnfold {
143 SelectInst *SI;
144 PHINode *SIUse;
145
146public:
147 SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {}
148
149 SelectInst *getInst() { return SI; }
150 PHINode *getUse() { return SIUse; }
151
152 explicit operator bool() const { return SI && SIUse; }
153};
154
155class DFAJumpThreading {
156public:
157 DFAJumpThreading(AssumptionCache *AC, DomTreeUpdater *DTU, LoopInfo *LI,
158 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)
159 : AC(AC), DTU(DTU), LI(LI), TTI(TTI), ORE(ORE) {}
160
161 bool run(Function &F);
162 bool LoopInfoBroken;
163
164private:
165 void
166 unfoldSelectInstrs(const SmallVector<SelectInstToUnfold, 4> &SelectInsts) {
168
169 while (!Stack.empty()) {
170 SelectInstToUnfold SIToUnfold = Stack.pop_back_val();
171
172 std::vector<SelectInstToUnfold> NewSIsToUnfold;
173 std::vector<BasicBlock *> NewBBs;
174 unfold(DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
175
176 // Put newly discovered select instructions into the work list.
177 llvm::append_range(Stack, NewSIsToUnfold);
178 }
179 }
180
181 static void unfold(DomTreeUpdater *DTU, LoopInfo *LI,
182 SelectInstToUnfold SIToUnfold,
183 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
184 std::vector<BasicBlock *> *NewBBs);
185
186 AssumptionCache *AC;
187 DomTreeUpdater *DTU;
188 LoopInfo *LI;
189 TargetTransformInfo *TTI;
190 OptimizationRemarkEmitter *ORE;
191};
192} // namespace
193
194/// Unfold the select instruction held in \p SIToUnfold by replacing it with
195/// control flow.
196///
197/// Put newly discovered select instructions into \p NewSIsToUnfold. Put newly
198/// created basic blocks into \p NewBBs.
199///
200/// TODO: merge it with CodeGenPrepare::optimizeSelectInst() if possible.
201void DFAJumpThreading::unfold(DomTreeUpdater *DTU, LoopInfo *LI,
202 SelectInstToUnfold SIToUnfold,
203 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
204 std::vector<BasicBlock *> *NewBBs) {
205 SelectInst *SI = SIToUnfold.getInst();
206 PHINode *SIUse = SIToUnfold.getUse();
207 assert(SI->hasOneUse());
208 // The select may come indirectly, instead of from where it is defined.
209 BasicBlock *StartBlock = SIUse->getIncomingBlock(*SI->use_begin());
210 BranchInst *StartBlockTerm =
211 dyn_cast<BranchInst>(StartBlock->getTerminator());
212 assert(StartBlockTerm);
213
214 if (StartBlockTerm->isUnconditional()) {
215 BasicBlock *EndBlock = StartBlock->getUniqueSuccessor();
216 // Arbitrarily choose the 'false' side for a new input value to the PHI.
217 BasicBlock *NewBlock = BasicBlock::Create(
218 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
219 EndBlock->getParent(), EndBlock);
220 NewBBs->push_back(NewBlock);
221 BranchInst::Create(EndBlock, NewBlock);
222 DTU->applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
223
224 // StartBlock
225 // | \
226 // | NewBlock
227 // | /
228 // EndBlock
229 Value *SIOp1 = SI->getTrueValue();
230 Value *SIOp2 = SI->getFalseValue();
231
232 PHINode *NewPhi = PHINode::Create(SIUse->getType(), 1,
233 Twine(SIOp2->getName(), ".si.unfold.phi"),
234 NewBlock->getFirstInsertionPt());
235 NewPhi->addIncoming(SIOp2, StartBlock);
236
237 // Update any other PHI nodes in EndBlock.
238 for (PHINode &Phi : EndBlock->phis()) {
239 if (SIUse == &Phi)
240 continue;
241 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlock);
242 }
243
244 // Update the phi node of SI, which is its only use.
245 if (EndBlock == SIUse->getParent()) {
246 SIUse->addIncoming(NewPhi, NewBlock);
247 SIUse->replaceUsesOfWith(SI, SIOp1);
248 } else {
249 PHINode *EndPhi = PHINode::Create(SIUse->getType(), pred_size(EndBlock),
250 Twine(SI->getName(), ".si.unfold.phi"),
251 EndBlock->getFirstInsertionPt());
252 for (BasicBlock *Pred : predecessors(EndBlock)) {
253 if (Pred != StartBlock && Pred != NewBlock)
254 EndPhi->addIncoming(EndPhi, Pred);
255 }
256
257 EndPhi->addIncoming(SIOp1, StartBlock);
258 EndPhi->addIncoming(NewPhi, NewBlock);
259 SIUse->replaceUsesOfWith(SI, EndPhi);
260 SIUse = EndPhi;
261 }
262
263 if (auto *OpSi = dyn_cast<SelectInst>(SIOp1))
264 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
265 if (auto *OpSi = dyn_cast<SelectInst>(SIOp2))
266 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
267
268 // Insert the real conditional branch based on the original condition.
269 StartBlockTerm->eraseFromParent();
270 auto *BI =
271 BranchInst::Create(EndBlock, NewBlock, SI->getCondition(), StartBlock);
273 BI->setMetadata(LLVMContext::MD_prof,
274 SI->getMetadata(LLVMContext::MD_prof));
275 DTU->applyUpdates({{DominatorTree::Insert, StartBlock, NewBlock}});
276 } else {
277 BasicBlock *EndBlock = SIUse->getParent();
278 BasicBlock *NewBlockT = BasicBlock::Create(
279 SI->getContext(), Twine(SI->getName(), ".si.unfold.true"),
280 EndBlock->getParent(), EndBlock);
281 BasicBlock *NewBlockF = BasicBlock::Create(
282 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
283 EndBlock->getParent(), EndBlock);
284
285 NewBBs->push_back(NewBlockT);
286 NewBBs->push_back(NewBlockF);
287
288 // Def only has one use in EndBlock.
289 // Before transformation:
290 // StartBlock(Def)
291 // | \
292 // EndBlock OtherBlock
293 // (Use)
294 //
295 // After transformation:
296 // StartBlock(Def)
297 // | \
298 // | OtherBlock
299 // NewBlockT
300 // | \
301 // | NewBlockF
302 // | /
303 // | /
304 // EndBlock
305 // (Use)
306 BranchInst::Create(EndBlock, NewBlockF);
307 // Insert the real conditional branch based on the original condition.
308 auto *BI =
309 BranchInst::Create(EndBlock, NewBlockF, SI->getCondition(), NewBlockT);
311 BI->setMetadata(LLVMContext::MD_prof,
312 SI->getMetadata(LLVMContext::MD_prof));
313 DTU->applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
314 {DominatorTree::Insert, NewBlockT, EndBlock},
315 {DominatorTree::Insert, NewBlockF, EndBlock}});
316
317 Value *TrueVal = SI->getTrueValue();
318 Value *FalseVal = SI->getFalseValue();
319
320 PHINode *NewPhiT = PHINode::Create(
321 SIUse->getType(), 1, Twine(TrueVal->getName(), ".si.unfold.phi"),
322 NewBlockT->getFirstInsertionPt());
323 PHINode *NewPhiF = PHINode::Create(
324 SIUse->getType(), 1, Twine(FalseVal->getName(), ".si.unfold.phi"),
325 NewBlockF->getFirstInsertionPt());
326 NewPhiT->addIncoming(TrueVal, StartBlock);
327 NewPhiF->addIncoming(FalseVal, NewBlockT);
328
329 if (auto *TrueSI = dyn_cast<SelectInst>(TrueVal))
330 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
331 if (auto *FalseSi = dyn_cast<SelectInst>(FalseVal))
332 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
333
334 SIUse->addIncoming(NewPhiT, NewBlockT);
335 SIUse->addIncoming(NewPhiF, NewBlockF);
336 SIUse->removeIncomingValue(StartBlock);
337
338 // Update any other PHI nodes in EndBlock.
339 for (PHINode &Phi : EndBlock->phis()) {
340 if (SIUse == &Phi)
341 continue;
342 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
343 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
344 Phi.removeIncomingValue(StartBlock);
345 }
346
347 // Update the appropriate successor of the start block to point to the new
348 // unfolded block.
349 unsigned SuccNum = StartBlockTerm->getSuccessor(1) == EndBlock ? 1 : 0;
350 StartBlockTerm->setSuccessor(SuccNum, NewBlockT);
351 DTU->applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
352 {DominatorTree::Insert, StartBlock, NewBlockT}});
353 }
354
355 // Preserve loop info
356 if (Loop *L = LI->getLoopFor(StartBlock)) {
357 for (BasicBlock *NewBB : *NewBBs)
358 L->addBasicBlockToLoop(NewBB, *LI);
359 }
360
361 // The select is now dead.
362 assert(SI->use_empty() && "Select must be dead now");
363 SI->eraseFromParent();
364}
365
366namespace {
367struct ClonedBlock {
368 BasicBlock *BB;
369 APInt State; ///< \p State corresponds to the next value of a switch stmnt.
370};
371} // namespace
372
373typedef std::deque<BasicBlock *> PathType;
374typedef std::vector<PathType> PathsType;
376typedef std::vector<ClonedBlock> CloneList;
377
378// This data structure keeps track of all blocks that have been cloned. If two
379// different ThreadingPaths clone the same block for a certain state it should
380// be reused, and it can be looked up in this map.
382
383// This map keeps track of all the new definitions for an instruction. This
384// information is needed when restoring SSA form after cloning blocks.
386
387inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
388 auto BBNames = llvm::map_range(
389 Path, [](const BasicBlock *BB) { return BB->getNameOrAsOperand(); });
390 OS << "< " << llvm::join(BBNames, ", ") << " >";
391 return OS;
392}
393
394namespace {
395/// ThreadingPath is a path in the control flow of a loop that can be threaded
396/// by cloning necessary basic blocks and replacing conditional branches with
397/// unconditional ones. A threading path includes a list of basic blocks, the
398/// exit state, and the block that determines the next state.
399struct ThreadingPath {
400 /// Exit value is DFA's exit state for the given path.
401 APInt getExitValue() const { return ExitVal; }
402 void setExitValue(const ConstantInt *V) {
403 ExitVal = V->getValue();
404 IsExitValSet = true;
405 }
406 void setExitValue(const APInt &V) {
407 ExitVal = V;
408 IsExitValSet = true;
409 }
410 bool isExitValueSet() const { return IsExitValSet; }
411
412 /// Determinator is the basic block that determines the next state of the DFA.
413 const BasicBlock *getDeterminatorBB() const { return DBB; }
414 void setDeterminator(const BasicBlock *BB) { DBB = BB; }
415
416 /// Path is a list of basic blocks.
417 const PathType &getPath() const { return Path; }
418 void setPath(const PathType &NewPath) { Path = NewPath; }
419 void push_back(BasicBlock *BB) { Path.push_back(BB); }
420 void push_front(BasicBlock *BB) { Path.push_front(BB); }
421 void appendExcludingFirst(const PathType &OtherPath) {
422 llvm::append_range(Path, llvm::drop_begin(OtherPath));
423 }
424
425 void print(raw_ostream &OS) const {
426 OS << Path << " [ " << ExitVal << ", " << DBB->getNameOrAsOperand() << " ]";
427 }
428
429private:
430 PathType Path;
431 APInt ExitVal;
432 const BasicBlock *DBB = nullptr;
433 bool IsExitValSet = false;
434};
435
436#ifndef NDEBUG
437inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
438 TPath.print(OS);
439 return OS;
440}
441#endif
442
443struct MainSwitch {
444 MainSwitch(SwitchInst *SI, LoopInfo *LI, OptimizationRemarkEmitter *ORE)
445 : LI(LI) {
446 if (isCandidate(SI)) {
447 Instr = SI;
448 } else {
449 ORE->emit([&]() {
450 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)
451 << "Switch instruction is not predictable.";
452 });
453 }
454 }
455
456 virtual ~MainSwitch() = default;
457
458 SwitchInst *getInstr() const { return Instr; }
459 const SmallVector<SelectInstToUnfold, 4> getSelectInsts() {
460 return SelectInsts;
461 }
462
463private:
464 /// Do a use-def chain traversal starting from the switch condition to see if
465 /// \p SI is a potential condidate.
466 ///
467 /// Also, collect select instructions to unfold.
468 bool isCandidate(const SwitchInst *SI) {
469 std::deque<std::pair<Value *, BasicBlock *>> Q;
470 SmallPtrSet<Value *, 16> SeenValues;
471 SelectInsts.clear();
472
473 Value *SICond = SI->getCondition();
474 LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n");
475 if (!isa<PHINode>(SICond))
476 return false;
477
478 // The switch must be in a loop.
479 const Loop *L = LI->getLoopFor(SI->getParent());
480 if (!L)
481 return false;
482
483 addToQueue(SICond, nullptr, Q, SeenValues);
484
485 while (!Q.empty()) {
486 Value *Current = Q.front().first;
487 BasicBlock *CurrentIncomingBB = Q.front().second;
488 Q.pop_front();
489
490 if (auto *Phi = dyn_cast<PHINode>(Current)) {
491 for (BasicBlock *IncomingBB : Phi->blocks()) {
492 Value *Incoming = Phi->getIncomingValueForBlock(IncomingBB);
493 addToQueue(Incoming, IncomingBB, Q, SeenValues);
494 }
495 LLVM_DEBUG(dbgs() << "\tphi: " << *Phi << "\n");
496 } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
497 if (!isValidSelectInst(SelI))
498 return false;
499 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
500 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
501 LLVM_DEBUG(dbgs() << "\tselect: " << *SelI << "\n");
502 if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
503 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
504 } else if (isa<Constant>(Current)) {
505 LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n");
506 continue;
507 } else {
508 LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n");
509 // Allow unpredictable values. The hope is that those will be the
510 // initial switch values that can be ignored (they will hit the
511 // unthreaded switch) but this assumption will get checked later after
512 // paths have been enumerated (in function getStateDefMap).
513
514 // If the unpredictable value comes from the same inner loop it is
515 // likely that it will also be on the enumerated paths, causing us to
516 // exit after we have enumerated all the paths. This heuristic save
517 // compile time because a search for all the paths can become expensive.
518 if (EarlyExitHeuristic &&
519 L->contains(LI->getLoopFor(CurrentIncomingBB))) {
521 << "\tExiting early due to unpredictability heuristic.\n");
522 return false;
523 }
524
525 continue;
526 }
527 }
528
529 return true;
530 }
531
532 void addToQueue(Value *Val, BasicBlock *BB,
533 std::deque<std::pair<Value *, BasicBlock *>> &Q,
534 SmallPtrSet<Value *, 16> &SeenValues) {
535 if (SeenValues.insert(Val).second)
536 Q.push_back({Val, BB});
537 }
538
539 bool isValidSelectInst(SelectInst *SI) {
540 if (!SI->hasOneUse())
541 return false;
542
543 Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
544 // The use of the select inst should be either a phi or another select.
545 if (!SIUse || !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
546 return false;
547
548 BasicBlock *SIBB = SI->getParent();
549
550 // Currently, we can only expand select instructions in basic blocks with
551 // one successor.
552 BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator());
553 if (!SITerm || !SITerm->isUnconditional())
554 return false;
555
556 // Only fold the select coming from directly where it is defined.
557 // TODO: We have dealt with the select coming indirectly now. This
558 // constraint can be relaxed.
559 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
560 if (PHIUser && PHIUser->getIncomingBlock(*SI->use_begin()) != SIBB)
561 return false;
562
563 // If select will not be sunk during unfolding, and it is in the same basic
564 // block as another state defining select, then cannot unfold both.
565 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
566 SelectInst *PrevSI = SIToUnfold.getInst();
567 if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI &&
568 PrevSI->getParent() == SI->getParent())
569 return false;
570 }
571
572 return true;
573 }
574
575 LoopInfo *LI;
576 SwitchInst *Instr = nullptr;
578};
579
580struct AllSwitchPaths {
581 AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE,
582 LoopInfo *LI, Loop *L)
583 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()), ORE(ORE),
584 LI(LI), SwitchOuterLoop(L) {}
585
586 std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
587 unsigned getNumThreadingPaths() { return TPaths.size(); }
588 SwitchInst *getSwitchInst() { return Switch; }
589 BasicBlock *getSwitchBlock() { return SwitchBlock; }
590
591 void run() {
592 findTPaths();
593 unifyTPaths();
594 }
595
596private:
597 // Value: an instruction that defines a switch state;
598 // Key: the parent basic block of that instruction.
599 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
600 std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
601 PHINode *Phi,
602 VisitedBlocks &VB,
603 unsigned PathsLimit) {
604 std::vector<ThreadingPath> Res;
605 auto *PhiBB = Phi->getParent();
606 VB.insert(PhiBB);
607
608 VisitedBlocks UniqueBlocks;
609 for (auto *IncomingBB : Phi->blocks()) {
610 if (Res.size() >= PathsLimit)
611 break;
612 if (!UniqueBlocks.insert(IncomingBB).second)
613 continue;
614 if (!SwitchOuterLoop->contains(IncomingBB))
615 continue;
616
617 Value *IncomingValue = Phi->getIncomingValueForBlock(IncomingBB);
618 // We found the determinator. This is the start of our path.
619 if (auto *C = dyn_cast<ConstantInt>(IncomingValue)) {
620 // SwitchBlock is the determinator, unsupported unless its also the def.
621 if (PhiBB == SwitchBlock &&
622 SwitchBlock != cast<PHINode>(Switch->getOperand(0))->getParent())
623 continue;
624 ThreadingPath NewPath;
625 NewPath.setDeterminator(PhiBB);
626 NewPath.setExitValue(C);
627 // Don't add SwitchBlock at the start, this is handled later.
628 if (IncomingBB != SwitchBlock)
629 NewPath.push_back(IncomingBB);
630 NewPath.push_back(PhiBB);
631 Res.push_back(NewPath);
632 continue;
633 }
634 // Don't get into a cycle.
635 if (VB.contains(IncomingBB) || IncomingBB == SwitchBlock)
636 continue;
637 // Recurse up the PHI chain.
638 auto *IncomingPhi = dyn_cast<PHINode>(IncomingValue);
639 if (!IncomingPhi)
640 continue;
641 auto *IncomingPhiDefBB = IncomingPhi->getParent();
642 if (!StateDef.contains(IncomingPhiDefBB))
643 continue;
644
645 // Direct predecessor, just add to the path.
646 if (IncomingPhiDefBB == IncomingBB) {
647 assert(PathsLimit > Res.size());
648 std::vector<ThreadingPath> PredPaths = getPathsFromStateDefMap(
649 StateDef, IncomingPhi, VB, PathsLimit - Res.size());
650 for (ThreadingPath &Path : PredPaths) {
651 Path.push_back(PhiBB);
652 Res.push_back(std::move(Path));
653 }
654 continue;
655 }
656 // Not a direct predecessor, find intermediate paths to append to the
657 // existing path.
658 if (VB.contains(IncomingPhiDefBB))
659 continue;
660
661 PathsType IntermediatePaths;
662 assert(PathsLimit > Res.size());
663 auto InterPathLimit = PathsLimit - Res.size();
664 IntermediatePaths = paths(IncomingPhiDefBB, IncomingBB, VB,
665 /* PathDepth = */ 1, InterPathLimit);
666 if (IntermediatePaths.empty())
667 continue;
668
669 assert(InterPathLimit >= IntermediatePaths.size());
670 auto PredPathLimit = InterPathLimit / IntermediatePaths.size();
671 std::vector<ThreadingPath> PredPaths =
672 getPathsFromStateDefMap(StateDef, IncomingPhi, VB, PredPathLimit);
673 for (const ThreadingPath &Path : PredPaths) {
674 for (const PathType &IPath : IntermediatePaths) {
675 ThreadingPath NewPath(Path);
676 NewPath.appendExcludingFirst(IPath);
677 NewPath.push_back(PhiBB);
678 Res.push_back(NewPath);
679 }
680 }
681 }
682 VB.erase(PhiBB);
683 return Res;
684 }
685
686 PathsType paths(BasicBlock *BB, BasicBlock *ToBB, VisitedBlocks &Visited,
687 unsigned PathDepth, unsigned PathsLimit) {
688 PathsType Res;
689
690 // Stop exploring paths after visiting MaxPathLength blocks
691 if (PathDepth > MaxPathLength) {
692 ORE->emit([&]() {
693 return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached",
694 Switch)
695 << "Exploration stopped after visiting MaxPathLength="
696 << ore::NV("MaxPathLength", MaxPathLength) << " blocks.";
697 });
698 return Res;
699 }
700
701 Visited.insert(BB);
702 if (++NumVisited > MaxNumVisitiedPaths)
703 return Res;
704
705 // Stop if we have reached the BB out of loop, since its successors have no
706 // impact on the DFA.
707 if (!SwitchOuterLoop->contains(BB))
708 return Res;
709
710 // Some blocks have multiple edges to the same successor, and this set
711 // is used to prevent a duplicate path from being generated
712 SmallPtrSet<BasicBlock *, 4> Successors;
713 for (BasicBlock *Succ : successors(BB)) {
714 if (Res.size() >= PathsLimit)
715 break;
716 if (!Successors.insert(Succ).second)
717 continue;
718
719 // Found a cycle through the final block.
720 if (Succ == ToBB) {
721 Res.push_back({BB, ToBB});
722 continue;
723 }
724
725 // We have encountered a cycle, do not get caught in it
726 if (Visited.contains(Succ))
727 continue;
728
729 auto *CurrLoop = LI->getLoopFor(BB);
730 // Unlikely to be beneficial.
731 if (Succ == CurrLoop->getHeader())
732 continue;
733 // Skip for now, revisit this condition later to see the impact on
734 // coverage and compile time.
735 if (LI->getLoopFor(Succ) != CurrLoop)
736 continue;
737 assert(PathsLimit > Res.size());
738 PathsType SuccPaths =
739 paths(Succ, ToBB, Visited, PathDepth + 1, PathsLimit - Res.size());
740 for (PathType &Path : SuccPaths) {
741 Path.push_front(BB);
742 Res.push_back(Path);
743 }
744 }
745 // This block could now be visited again from a different predecessor. Note
746 // that this will result in exponential runtime. Subpaths could possibly be
747 // cached but it takes a lot of memory to store them.
748 Visited.erase(BB);
749 return Res;
750 }
751
752 /// Walk the use-def chain and collect all the state-defining blocks and the
753 /// PHI nodes in those blocks that define the state.
754 StateDefMap getStateDefMap() const {
755 StateDefMap Res;
756 PHINode *FirstDef = dyn_cast<PHINode>(Switch->getOperand(0));
757 assert(FirstDef && "The first definition must be a phi.");
758
760 Stack.push_back(FirstDef);
761 SmallPtrSet<Value *, 16> SeenValues;
762
763 while (!Stack.empty()) {
764 PHINode *CurPhi = Stack.pop_back_val();
765
766 Res[CurPhi->getParent()] = CurPhi;
767 SeenValues.insert(CurPhi);
768
769 for (BasicBlock *IncomingBB : CurPhi->blocks()) {
770 PHINode *IncomingPhi =
771 dyn_cast<PHINode>(CurPhi->getIncomingValueForBlock(IncomingBB));
772 if (!IncomingPhi)
773 continue;
774 bool IsOutsideLoops = !SwitchOuterLoop->contains(IncomingBB);
775 if (SeenValues.contains(IncomingPhi) || IsOutsideLoops)
776 continue;
777
778 Stack.push_back(IncomingPhi);
779 }
780 }
781
782 return Res;
783 }
784
785 // Find all threadable paths.
786 void findTPaths() {
787 StateDefMap StateDef = getStateDefMap();
788 if (StateDef.empty()) {
789 ORE->emit([&]() {
790 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",
791 Switch)
792 << "Switch instruction is not predictable.";
793 });
794 return;
795 }
796
797 auto *SwitchPhi = cast<PHINode>(Switch->getOperand(0));
798 auto *SwitchPhiDefBB = SwitchPhi->getParent();
799 VisitedBlocks VB;
800 // Get paths from the determinator BBs to SwitchPhiDefBB
801 std::vector<ThreadingPath> PathsToPhiDef =
802 getPathsFromStateDefMap(StateDef, SwitchPhi, VB, MaxNumPaths);
803 if (SwitchPhiDefBB == SwitchBlock || PathsToPhiDef.empty()) {
804 TPaths = std::move(PathsToPhiDef);
805 return;
806 }
807
808 assert(MaxNumPaths >= PathsToPhiDef.size() && !PathsToPhiDef.empty());
809 auto PathsLimit = MaxNumPaths / PathsToPhiDef.size();
810 // Find and append paths from SwitchPhiDefBB to SwitchBlock.
811 PathsType PathsToSwitchBB =
812 paths(SwitchPhiDefBB, SwitchBlock, VB, /* PathDepth = */ 1, PathsLimit);
813 if (PathsToSwitchBB.empty())
814 return;
815
816 std::vector<ThreadingPath> TempList;
817 for (const ThreadingPath &Path : PathsToPhiDef) {
818 for (const PathType &PathToSw : PathsToSwitchBB) {
819 ThreadingPath PathCopy(Path);
820 PathCopy.appendExcludingFirst(PathToSw);
821 TempList.push_back(PathCopy);
822 }
823 }
824 TPaths = std::move(TempList);
825 }
826
827 /// Fast helper to get the successor corresponding to a particular case value
828 /// for a switch statement.
829 BasicBlock *getNextCaseSuccessor(const APInt &NextState) {
830 // Precompute the value => successor mapping
831 if (CaseValToDest.empty()) {
832 for (auto Case : Switch->cases()) {
833 APInt CaseVal = Case.getCaseValue()->getValue();
834 CaseValToDest[CaseVal] = Case.getCaseSuccessor();
835 }
836 }
837
838 auto SuccIt = CaseValToDest.find(NextState);
839 return SuccIt == CaseValToDest.end() ? Switch->getDefaultDest()
840 : SuccIt->second;
841 }
842
843 // Two states are equivalent if they have the same switch destination.
844 // Unify the states in different threading path if the states are equivalent.
845 void unifyTPaths() {
846 SmallDenseMap<BasicBlock *, APInt> DestToState;
847 for (ThreadingPath &Path : TPaths) {
848 APInt NextState = Path.getExitValue();
849 BasicBlock *Dest = getNextCaseSuccessor(NextState);
850 auto [StateIt, Inserted] = DestToState.try_emplace(Dest, NextState);
851 if (Inserted)
852 continue;
853 if (NextState != StateIt->second) {
854 LLVM_DEBUG(dbgs() << "Next state in " << Path << " is equivalent to "
855 << StateIt->second << "\n");
856 Path.setExitValue(StateIt->second);
857 }
858 }
859 }
860
861 unsigned NumVisited = 0;
862 SwitchInst *Switch;
863 BasicBlock *SwitchBlock;
864 OptimizationRemarkEmitter *ORE;
865 std::vector<ThreadingPath> TPaths;
866 DenseMap<APInt, BasicBlock *> CaseValToDest;
867 LoopInfo *LI;
868 Loop *SwitchOuterLoop;
869};
870
871struct TransformDFA {
872 TransformDFA(AllSwitchPaths *SwitchPaths, DomTreeUpdater *DTU,
873 AssumptionCache *AC, TargetTransformInfo *TTI,
874 OptimizationRemarkEmitter *ORE,
875 SmallPtrSet<const Value *, 32> EphValues)
876 : SwitchPaths(SwitchPaths), DTU(DTU), AC(AC), TTI(TTI), ORE(ORE),
877 EphValues(EphValues) {}
878
879 bool run() {
880 if (isLegalAndProfitableToTransform()) {
881 createAllExitPaths();
882 NumTransforms++;
883 return true;
884 }
885 return false;
886 }
887
888private:
889 /// This function performs both a legality check and profitability check at
890 /// the same time since it is convenient to do so. It iterates through all
891 /// blocks that will be cloned, and keeps track of the duplication cost. It
892 /// also returns false if it is illegal to clone some required block.
893 bool isLegalAndProfitableToTransform() {
894 CodeMetrics Metrics;
895 uint64_t NumClonedInst = 0;
896 SwitchInst *Switch = SwitchPaths->getSwitchInst();
897
898 // Don't thread switch without multiple successors.
899 if (Switch->getNumSuccessors() <= 1)
900 return false;
901
902 // Note that DuplicateBlockMap is not being used as intended here. It is
903 // just being used to ensure (BB, State) pairs are only counted once.
904 DuplicateBlockMap DuplicateMap;
905 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
906 PathType PathBBs = TPath.getPath();
907 APInt NextState = TPath.getExitValue();
908 const BasicBlock *Determinator = TPath.getDeterminatorBB();
909
910 // Update Metrics for the Switch block, this is always cloned
911 BasicBlock *BB = SwitchPaths->getSwitchBlock();
912 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
913 if (!VisitedBB) {
914 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
915 NumClonedInst += BB->sizeWithoutDebug();
916 DuplicateMap[BB].push_back({BB, NextState});
917 }
918
919 // If the Switch block is the Determinator, then we can continue since
920 // this is the only block that is cloned and we already counted for it.
921 if (PathBBs.front() == Determinator)
922 continue;
923
924 // Otherwise update Metrics for all blocks that will be cloned. If any
925 // block is already cloned and would be reused, don't double count it.
926 auto DetIt = llvm::find(PathBBs, Determinator);
927 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
928 BB = *BBIt;
929 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
930 if (VisitedBB)
931 continue;
932 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
933 NumClonedInst += BB->sizeWithoutDebug();
934 DuplicateMap[BB].push_back({BB, NextState});
935 }
936
937 if (Metrics.notDuplicatable) {
938 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
939 << "non-duplicatable instructions.\n");
940 ORE->emit([&]() {
941 return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst",
942 Switch)
943 << "Contains non-duplicatable instructions.";
944 });
945 return false;
946 }
947
948 // FIXME: Allow jump threading with controlled convergence.
949 if (Metrics.Convergence != ConvergenceKind::None) {
950 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
951 << "convergent instructions.\n");
952 ORE->emit([&]() {
953 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
954 << "Contains convergent instructions.";
955 });
956 return false;
957 }
958
959 if (!Metrics.NumInsts.isValid()) {
960 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
961 << "instructions with invalid cost.\n");
962 ORE->emit([&]() {
963 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
964 << "Contains instructions with invalid cost.";
965 });
966 return false;
967 }
968 }
969
970 // Too much cloned instructions slow down later optimizations, especially
971 // SLPVectorizer.
972 // TODO: Thread the switch partially before reaching the threshold.
973 uint64_t NumOrigInst = 0;
974 uint64_t NumOuterUseBlock = 0;
975 for (auto *BB : DuplicateMap.keys()) {
976 NumOrigInst += BB->sizeWithoutDebug();
977 // Only unduplicated blocks with single predecessor require new phi
978 // nodes.
979 for (auto *Succ : successors(BB))
980 if (!DuplicateMap.count(Succ) && Succ->getSinglePredecessor())
981 NumOuterUseBlock++;
982 }
983
984 if (double(NumClonedInst) / double(NumOrigInst) > MaxClonedRate) {
985 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, too much "
986 "instructions wll be cloned\n");
987 ORE->emit([&]() {
988 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
989 << "Too much instructions will be cloned.";
990 });
991 return false;
992 }
993
994 // Too much unduplicated blocks with outer uses may cause too much
995 // insertions of phi nodes for duplicated definitions. TODO: Drop this
996 // threshold if we come up with another way to reduce the number of inserted
997 // phi nodes.
998 if (NumOuterUseBlock > MaxOuterUseBlocks) {
999 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, too much "
1000 "blocks with outer uses\n");
1001 ORE->emit([&]() {
1002 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
1003 << "Too much blocks with outer uses.";
1004 });
1005 return false;
1006 }
1007
1008 InstructionCost DuplicationCost = 0;
1009
1010 unsigned JumpTableSize = 0;
1011 TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr,
1012 nullptr);
1013 if (JumpTableSize == 0) {
1014 // Factor in the number of conditional branches reduced from jump
1015 // threading. Assume that lowering the switch block is implemented by
1016 // using binary search, hence the LogBase2().
1017 unsigned CondBranches =
1018 APInt(32, Switch->getNumSuccessors()).ceilLogBase2();
1019 assert(CondBranches > 0 &&
1020 "The threaded switch must have multiple branches");
1021 DuplicationCost = Metrics.NumInsts / CondBranches;
1022 } else {
1023 // Compared with jump tables, the DFA optimizer removes an indirect branch
1024 // on each loop iteration, thus making branch prediction more precise. The
1025 // more branch targets there are, the more likely it is for the branch
1026 // predictor to make a mistake, and the more benefit there is in the DFA
1027 // optimizer. Thus, the more branch targets there are, the lower is the
1028 // cost of the DFA opt.
1029 DuplicationCost = Metrics.NumInsts / JumpTableSize;
1030 }
1031
1032 LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "
1033 << SwitchPaths->getSwitchBlock()->getName()
1034 << " is: " << DuplicationCost << "\n\n");
1035
1036 if (DuplicationCost > CostThreshold) {
1037 LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "
1038 << "cost threshold.\n");
1039 ORE->emit([&]() {
1040 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
1041 << "Duplication cost exceeds the cost threshold (cost="
1042 << ore::NV("Cost", DuplicationCost)
1043 << ", threshold=" << ore::NV("Threshold", CostThreshold) << ").";
1044 });
1045 return false;
1046 }
1047
1048 ORE->emit([&]() {
1049 return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch)
1050 << "Switch statement jump-threaded.";
1051 });
1052
1053 return true;
1054 }
1055
1056 /// Transform each threading path to effectively jump thread the DFA.
1057 void createAllExitPaths() {
1058 // Move the switch block to the end of the path, since it will be duplicated
1059 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
1060 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1061 LLVM_DEBUG(dbgs() << TPath << "\n");
1062 // TODO: Fix exit path creation logic so that we dont need this
1063 // placeholder.
1064 TPath.push_front(SwitchBlock);
1065 }
1066
1067 // Transform the ThreadingPaths and keep track of the cloned values
1068 DuplicateBlockMap DuplicateMap;
1069 DefMap NewDefs;
1070
1071 SmallPtrSet<BasicBlock *, 16> BlocksToClean;
1072 BlocksToClean.insert_range(successors(SwitchBlock));
1073
1074 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1075 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, DTU);
1076 NumPaths++;
1077 }
1078
1079 // After all paths are cloned, now update the last successor of the cloned
1080 // path so it skips over the switch statement
1081 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
1082 updateLastSuccessor(TPath, DuplicateMap, DTU);
1083
1084 // For each instruction that was cloned and used outside, update its uses
1085 updateSSA(NewDefs);
1086
1087 // Clean PHI Nodes for the newly created blocks
1088 for (BasicBlock *BB : BlocksToClean)
1089 cleanPhiNodes(BB);
1090 }
1091
1092 /// For a specific ThreadingPath \p Path, create an exit path starting from
1093 /// the determinator block.
1094 ///
1095 /// To remember the correct destination, we have to duplicate blocks
1096 /// corresponding to each state. Also update the terminating instruction of
1097 /// the predecessors, and phis in the successor blocks.
1098 void createExitPath(DefMap &NewDefs, const ThreadingPath &Path,
1099 DuplicateBlockMap &DuplicateMap,
1100 SmallPtrSet<BasicBlock *, 16> &BlocksToClean,
1101 DomTreeUpdater *DTU) {
1102 APInt NextState = Path.getExitValue();
1103 const BasicBlock *Determinator = Path.getDeterminatorBB();
1104 PathType PathBBs = Path.getPath();
1105
1106 // Don't select the placeholder block in front
1107 if (PathBBs.front() == Determinator)
1108 PathBBs.pop_front();
1109
1110 auto DetIt = llvm::find(PathBBs, Determinator);
1111 // When there is only one BB in PathBBs, the determinator takes itself as a
1112 // direct predecessor.
1113 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);
1114 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
1115 BasicBlock *BB = *BBIt;
1116 BlocksToClean.insert(BB);
1117
1118 // We already cloned BB for this NextState, now just update the branch
1119 // and continue.
1120 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
1121 if (NextBB) {
1122 updatePredecessor(PrevBB, BB, NextBB, DTU);
1123 PrevBB = NextBB;
1124 continue;
1125 }
1126
1127 // Clone the BB and update the successor of Prev to jump to the new block
1128 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
1129 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
1130 DuplicateMap[BB].push_back({NewBB, NextState});
1131 BlocksToClean.insert(NewBB);
1132 PrevBB = NewBB;
1133 }
1134 }
1135
1136 /// Restore SSA form after cloning blocks.
1137 ///
1138 /// Each cloned block creates new defs for a variable, and the uses need to be
1139 /// updated to reflect this. The uses may be replaced with a cloned value, or
1140 /// some derived phi instruction. Note that all uses of a value defined in the
1141 /// same block were already remapped when cloning the block.
1142 void updateSSA(DefMap &NewDefs) {
1143 SSAUpdaterBulk SSAUpdate;
1144 SmallVector<Use *, 16> UsesToRename;
1145
1146 for (const auto &KV : NewDefs) {
1147 Instruction *I = KV.first;
1148 BasicBlock *BB = I->getParent();
1149 std::vector<Instruction *> Cloned = KV.second;
1150
1151 // Scan all uses of this instruction to see if it is used outside of its
1152 // block, and if so, record them in UsesToRename.
1153 for (Use &U : I->uses()) {
1154 Instruction *User = cast<Instruction>(U.getUser());
1155 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
1156 if (UserPN->getIncomingBlock(U) == BB)
1157 continue;
1158 } else if (User->getParent() == BB) {
1159 continue;
1160 }
1161
1162 UsesToRename.push_back(&U);
1163 }
1164
1165 // If there are no uses outside the block, we're done with this
1166 // instruction.
1167 if (UsesToRename.empty())
1168 continue;
1169 LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I
1170 << "\n");
1171
1172 // We found a use of I outside of BB. Rename all uses of I that are
1173 // outside its block to be uses of the appropriate PHI node etc. See
1174 // ValuesInBlocks with the values we know.
1175 unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());
1176 SSAUpdate.AddAvailableValue(VarNum, BB, I);
1177 for (Instruction *New : Cloned)
1178 SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New);
1179
1180 while (!UsesToRename.empty())
1181 SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val());
1182
1183 LLVM_DEBUG(dbgs() << "\n");
1184 }
1185 // SSAUpdater handles phi placement and renaming uses with the appropriate
1186 // value.
1187 SSAUpdate.RewriteAllUses(&DTU->getDomTree());
1188 }
1189
1190 /// Helper to get the successor corresponding to a particular case value for
1191 /// a switch statement.
1192 /// TODO: Unify it with SwitchPaths->getNextCaseSuccessor(SwitchInst *Switch)
1193 /// by updating cached value => successor mapping during threading.
1194 static BasicBlock *getNextCaseSuccessor(SwitchInst *Switch,
1195 const APInt &NextState) {
1196 BasicBlock *NextCase = nullptr;
1197 for (auto Case : Switch->cases()) {
1198 if (Case.getCaseValue()->getValue() == NextState) {
1199 NextCase = Case.getCaseSuccessor();
1200 break;
1201 }
1202 }
1203 if (!NextCase)
1204 NextCase = Switch->getDefaultDest();
1205 return NextCase;
1206 }
1207
1208 /// Clones a basic block, and adds it to the CFG.
1209 ///
1210 /// This function also includes updating phi nodes in the successors of the
1211 /// BB, and remapping uses that were defined locally in the cloned BB.
1212 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
1213 const APInt &NextState,
1214 DuplicateBlockMap &DuplicateMap,
1215 DefMap &NewDefs,
1216 DomTreeUpdater *DTU) {
1217 ValueToValueMapTy VMap;
1218 BasicBlock *NewBB = CloneBasicBlock(
1219 BB, VMap, ".jt" + std::to_string(NextState.getLimitedValue()),
1220 BB->getParent());
1221 NewBB->moveAfter(BB);
1222 NumCloned++;
1223
1224 for (Instruction &I : *NewBB) {
1225 // Do not remap operands of PHINode in case a definition in BB is an
1226 // incoming value to a phi in the same block. This incoming value will
1227 // be renamed later while restoring SSA.
1228 if (isa<PHINode>(&I))
1229 continue;
1230 RemapInstruction(&I, VMap,
1232 if (AssumeInst *II = dyn_cast<AssumeInst>(&I))
1234 }
1235
1236 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1237 updatePredecessor(PrevBB, BB, NewBB, DTU);
1238 updateDefMap(NewDefs, VMap);
1239
1240 // Add all successors to the DominatorTree
1241 SmallPtrSet<BasicBlock *, 4> SuccSet;
1242 for (auto *SuccBB : successors(NewBB)) {
1243 if (SuccSet.insert(SuccBB).second)
1244 DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1245 }
1246 SuccSet.clear();
1247 return NewBB;
1248 }
1249
1250 /// Update the phi nodes in BB's successors.
1251 ///
1252 /// This means creating a new incoming value from NewBB with the new
1253 /// instruction wherever there is an incoming value from BB.
1254 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1255 const APInt &NextState, ValueToValueMapTy &VMap,
1256 DuplicateBlockMap &DuplicateMap) {
1257 std::vector<BasicBlock *> BlocksToUpdate;
1258
1259 // If BB is the last block in the path, we can simply update the one case
1260 // successor that will be reached.
1261 if (BB == SwitchPaths->getSwitchBlock()) {
1262 SwitchInst *Switch = SwitchPaths->getSwitchInst();
1263 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1264 BlocksToUpdate.push_back(NextCase);
1265 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1266 if (ClonedSucc)
1267 BlocksToUpdate.push_back(ClonedSucc);
1268 }
1269 // Otherwise update phis in all successors.
1270 else {
1271 for (BasicBlock *Succ : successors(BB)) {
1272 BlocksToUpdate.push_back(Succ);
1273
1274 // Check if a successor has already been cloned for the particular exit
1275 // value. In this case if a successor was already cloned, the phi nodes
1276 // in the cloned block should be updated directly.
1277 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1278 if (ClonedSucc)
1279 BlocksToUpdate.push_back(ClonedSucc);
1280 }
1281 }
1282
1283 // If there is a phi with an incoming value from BB, create a new incoming
1284 // value for the new predecessor ClonedBB. The value will either be the same
1285 // value from BB or a cloned value.
1286 for (BasicBlock *Succ : BlocksToUpdate) {
1287 for (PHINode &Phi : Succ->phis()) {
1288 Value *Incoming = Phi.getIncomingValueForBlock(BB);
1289 if (Incoming) {
1290 if (isa<Constant>(Incoming)) {
1291 Phi.addIncoming(Incoming, ClonedBB);
1292 continue;
1293 }
1294 Value *ClonedVal = VMap[Incoming];
1295 if (ClonedVal)
1296 Phi.addIncoming(ClonedVal, ClonedBB);
1297 else
1298 Phi.addIncoming(Incoming, ClonedBB);
1299 }
1300 }
1301 }
1302 }
1303
1304 /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all
1305 /// other successors are kept as well.
1306 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1307 BasicBlock *NewBB, DomTreeUpdater *DTU) {
1308 // When a path is reused, there is a chance that predecessors were already
1309 // updated before. Check if the predecessor needs to be updated first.
1310 if (!isPredecessor(OldBB, PrevBB))
1311 return;
1312
1313 Instruction *PrevTerm = PrevBB->getTerminator();
1314 for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) {
1315 if (PrevTerm->getSuccessor(Idx) == OldBB) {
1316 OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true);
1317 PrevTerm->setSuccessor(Idx, NewBB);
1318 }
1319 }
1320 DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1321 {DominatorTree::Insert, PrevBB, NewBB}});
1322 }
1323
1324 /// Add new value mappings to the DefMap to keep track of all new definitions
1325 /// for a particular instruction. These will be used while updating SSA form.
1326 void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
1328 NewDefsVector.reserve(VMap.size());
1329
1330 for (auto Entry : VMap) {
1331 Instruction *Inst =
1332 dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
1333 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1334 isa<SwitchInst>(Inst)) {
1335 continue;
1336 }
1337
1338 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1339 if (!Cloned)
1340 continue;
1341
1342 NewDefsVector.push_back({Inst, Cloned});
1343 }
1344
1345 // Sort the defs to get deterministic insertion order into NewDefs.
1346 sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {
1347 if (LHS.first == RHS.first)
1348 return LHS.second->comesBefore(RHS.second);
1349 return LHS.first->comesBefore(RHS.first);
1350 });
1351
1352 for (const auto &KV : NewDefsVector)
1353 NewDefs[KV.first].push_back(KV.second);
1354 }
1355
1356 /// Update the last branch of a particular cloned path to point to the correct
1357 /// case successor.
1358 ///
1359 /// Note that this is an optional step and would have been done in later
1360 /// optimizations, but it makes the CFG significantly easier to work with.
1361 void updateLastSuccessor(const ThreadingPath &TPath,
1362 DuplicateBlockMap &DuplicateMap,
1363 DomTreeUpdater *DTU) {
1364 APInt NextState = TPath.getExitValue();
1365 BasicBlock *BB = TPath.getPath().back();
1366 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1367
1368 // Note multiple paths can end at the same block so check that it is not
1369 // updated yet
1370 if (!isa<SwitchInst>(LastBlock->getTerminator()))
1371 return;
1372 SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator());
1373 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1374
1375 std::vector<DominatorTree::UpdateType> DTUpdates;
1376 SmallPtrSet<BasicBlock *, 4> SuccSet;
1377 for (BasicBlock *Succ : successors(LastBlock)) {
1378 if (Succ != NextCase && SuccSet.insert(Succ).second)
1379 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1380 }
1381
1382 Switch->eraseFromParent();
1383 BranchInst::Create(NextCase, LastBlock);
1384
1385 DTU->applyUpdates(DTUpdates);
1386 }
1387
1388 /// After cloning blocks, some of the phi nodes have extra incoming values
1389 /// that are no longer used. This function removes them.
1390 void cleanPhiNodes(BasicBlock *BB) {
1391 // If BB is no longer reachable, remove any remaining phi nodes
1392 if (pred_empty(BB)) {
1393 for (PHINode &PN : make_early_inc_range(BB->phis())) {
1394 PN.replaceAllUsesWith(PoisonValue::get(PN.getType()));
1395 PN.eraseFromParent();
1396 }
1397 return;
1398 }
1399
1400 // Remove any incoming values that come from an invalid predecessor
1401 for (PHINode &Phi : BB->phis())
1402 Phi.removeIncomingValueIf([&](unsigned Index) {
1403 BasicBlock *IncomingBB = Phi.getIncomingBlock(Index);
1404 return !isPredecessor(BB, IncomingBB);
1405 });
1406 }
1407
1408 /// Checks if BB was already cloned for a particular next state value. If it
1409 /// was then it returns this cloned block, and otherwise null.
1410 BasicBlock *getClonedBB(BasicBlock *BB, const APInt &NextState,
1411 DuplicateBlockMap &DuplicateMap) {
1412 CloneList ClonedBBs = DuplicateMap[BB];
1413
1414 // Find an entry in the CloneList with this NextState. If it exists then
1415 // return the corresponding BB
1416 auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {
1417 return C.State == NextState;
1418 });
1419 return It != ClonedBBs.end() ? (*It).BB : nullptr;
1420 }
1421
1422 /// Returns true if IncomingBB is a predecessor of BB.
1423 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1424 return llvm::is_contained(predecessors(BB), IncomingBB);
1425 }
1426
1427 AllSwitchPaths *SwitchPaths;
1428 DomTreeUpdater *DTU;
1429 AssumptionCache *AC;
1430 TargetTransformInfo *TTI;
1431 OptimizationRemarkEmitter *ORE;
1432 SmallPtrSet<const Value *, 32> EphValues;
1433 std::vector<ThreadingPath> TPaths;
1434};
1435} // namespace
1436
1437bool DFAJumpThreading::run(Function &F) {
1438 LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");
1439
1440 if (F.hasOptSize()) {
1441 LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n");
1442 return false;
1443 }
1444
1445 if (ClViewCfgBefore)
1446 F.viewCFG();
1447
1448 SmallVector<AllSwitchPaths, 2> ThreadableLoops;
1449 bool MadeChanges = false;
1450 LoopInfoBroken = false;
1451
1452 for (BasicBlock &BB : F) {
1454 if (!SI)
1455 continue;
1456
1457 LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName()
1458 << " is a candidate\n");
1459 MainSwitch Switch(SI, LI, ORE);
1460
1461 if (!Switch.getInstr()) {
1462 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is not a "
1463 << "candidate for jump threading\n");
1464 continue;
1465 }
1466
1467 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
1468 << "candidate for jump threading\n");
1469 LLVM_DEBUG(SI->dump());
1470
1471 unfoldSelectInstrs(Switch.getSelectInsts());
1472 if (!Switch.getSelectInsts().empty())
1473 MadeChanges = true;
1474
1475 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
1476 LI->getLoopFor(&BB)->getOutermostLoop());
1477 SwitchPaths.run();
1478
1479 if (SwitchPaths.getNumThreadingPaths() > 0) {
1480 ThreadableLoops.push_back(SwitchPaths);
1481
1482 // For the time being limit this optimization to occurring once in a
1483 // function since it can change the CFG significantly. This is not a
1484 // strict requirement but it can cause buggy behavior if there is an
1485 // overlap of blocks in different opportunities. There is a lot of room to
1486 // experiment with catching more opportunities here.
1487 // NOTE: To release this contraint, we must handle LoopInfo invalidation
1488 break;
1489 }
1490 }
1491
1492#ifdef NDEBUG
1493 LI->verify(DTU->getDomTree());
1494#endif
1495
1496 SmallPtrSet<const Value *, 32> EphValues;
1497 if (ThreadableLoops.size() > 0)
1498 CodeMetrics::collectEphemeralValues(&F, AC, EphValues);
1499
1500 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1501 TransformDFA Transform(&SwitchPaths, DTU, AC, TTI, ORE, EphValues);
1502 if (Transform.run())
1503 MadeChanges = LoopInfoBroken = true;
1504 }
1505
1506 DTU->flush();
1507
1508#ifdef EXPENSIVE_CHECKS
1509 verifyFunction(F, &dbgs());
1510#endif
1511
1512 if (MadeChanges && VerifyDomInfo)
1513 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Full) &&
1514 "Failed to maintain validity of domtree!");
1515
1516 return MadeChanges;
1517}
1518
1519/// Integrate with the new Pass Manager
1524 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1527
1528 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1529 DFAJumpThreading ThreadImpl(&AC, &DTU, &LI, &TTI, &ORE);
1530 if (!ThreadImpl.run(F))
1531 return PreservedAnalyses::all();
1532
1535 if (!ThreadImpl.LoopInfoBroken)
1536 PA.preserve<LoopAnalysis>();
1537 return PA;
1538}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
std::deque< BasicBlock * > PathType
std::vector< PathType > PathsType
MapVector< Instruction *, std::vector< Instruction * > > DefMap
std::vector< ClonedBlock > CloneList
DenseMap< BasicBlock *, CloneList > DuplicateBlockMap
This file defines the DenseMap class.
#define DEBUG_TYPE
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
Machine Trace Metrics
uint64_t IntrinsicInst * II
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
This file contains some functions that are useful when dealing with strings.
#define LLVM_DEBUG(...)
Definition Debug.h:114
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition APInt.h:475
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:528
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
LLVM_ABI void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI filter_iterator< BasicBlock::const_iterator, std::function< bool(constInstruction &)> >::difference_type sizeWithoutDebug() const
Return the size of the basic block ignoring debug instructions.
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:233
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition DenseMap.h:248
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:174
Analysis pass which computes a DominatorTree.
Definition Dominators.h:284
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:165
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:569
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:36
The optimization diagnostic interface.
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:132
LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
LLVM_ABI void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
LLVM_ABI void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getTrueValue() const
bool erase(PtrType Ptr)
Remove pointer from the set.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void reserve(size_type N)
void push_back(const T &Elt)
BasicBlock * getDefaultDest() const
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) const
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition User.cpp:21
Value * getOperand(unsigned i) const
Definition User.h:232
size_type size() const
Definition ValueMap.h:144
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:256
LLVM_ABI std::string getNameOrAsOperand() const
Definition Value.cpp:457
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:322
const ParentTy * getParent() const
Definition ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
@ Entry
Definition COFF.h:862
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:81
initializer< Ty > init(const Ty &Val)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
Definition CoroShape.h:31
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
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:1751
static cl::opt< unsigned > MaxNumPaths("dfa-max-num-paths", cl::desc("Max number of paths enumerated around a switch"), cl::Hidden, cl::init(200))
LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2136
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:632
auto pred_size(const MachineBasicBlock *BB)
static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))
auto map_range(ContainerTy &&C, FuncTy F)
Definition STLExtras.h:364
static cl::opt< double > MaxClonedRate("dfa-max-cloned-rate", cl::desc("Maximum cloned instructions rate accepted for the transformation"), cl::Hidden, cl::init(7.5))
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1622
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition ValueMapper.h:98
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition ValueMapper.h:80
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
static cl::opt< unsigned > MaxNumVisitiedPaths("dfa-max-num-visited-paths", cl::desc("Max number of blocks visited while enumerating paths around a switch"), cl::Hidden, cl::init(2500))
TargetTransformInfo TTI
std::string join(IteratorT Begin, IteratorT End, StringRef Separator)
Joins the strings in the range [Begin, End), adding Separator between the elements.
static cl::opt< bool > EarlyExitHeuristic("dfa-early-exit-heuristic", cl::desc("Exit early if an unpredictable value come from the same loop"), cl::Hidden, cl::init(true))
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI bool VerifyDomInfo
Enables verification of dominator trees.
static cl::opt< unsigned > MaxOuterUseBlocks("dfa-max-out-use-blocks", cl::desc("Maximum unduplicated blocks with outer uses " "accepted for the transformation"), cl::Hidden, cl::init(40))
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
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:1758
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))
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1897
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
bool pred_empty(const BasicBlock *BB)
Definition CFG.h:119
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))
static LLVM_ABI 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).
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Integrate with the new Pass Manager.