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