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