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