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