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