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