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