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/SmallSet.h"
64 #include "llvm/ADT/Statistic.h"
65 #include "llvm/Analysis/AssumptionCache.h"
66 #include "llvm/Analysis/CodeMetrics.h"
67 #include "llvm/Analysis/DomTreeUpdater.h"
68 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
69 #include "llvm/Analysis/TargetTransformInfo.h"
70 #include "llvm/IR/CFG.h"
71 #include "llvm/IR/Constants.h"
72 #include "llvm/IR/IntrinsicInst.h"
73 #include "llvm/Support/CommandLine.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Transforms/Utils/Cloning.h"
76 #include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
77 #include "llvm/Transforms/Utils/ValueMapper.h"
78 #include <algorithm>
79 #include <deque>
80
81 #ifdef EXPENSIVE_CHECKS
82 #include "llvm/IR/Verifier.h"
83 #endif
84
85 using namespace llvm;
86
87 #define DEBUG_TYPE "dfa-jump-threading"
88
89 STATISTIC(NumTransforms, "Number of transformations done");
90 STATISTIC(NumCloned, "Number of blocks cloned");
91 STATISTIC(NumPaths, "Number of individual paths threaded");
92
93 static cl::opt<bool>
94 ClViewCfgBefore("dfa-jump-view-cfg-before",
95 cl::desc("View the CFG before DFA Jump Threading"),
96 cl::Hidden, cl::init(false));
97
98 static cl::opt<unsigned> MaxPathLength(
99 "dfa-max-path-length",
100 cl::desc("Max number of blocks searched to find a threading path"),
101 cl::Hidden, cl::init(20));
102
103 static cl::opt<unsigned>
104 MaxNumPaths("dfa-max-num-paths",
105 cl::desc("Max number of paths enumerated around a switch"),
106 cl::Hidden, cl::init(200));
107
108 static cl::opt<unsigned>
109 CostThreshold("dfa-cost-threshold",
110 cl::desc("Maximum cost accepted for the transformation"),
111 cl::Hidden, cl::init(50));
112
113 namespace {
114
115 class SelectInstToUnfold {
116 SelectInst *SI;
117 PHINode *SIUse;
118
119 public:
SelectInstToUnfold(SelectInst * SI,PHINode * SIUse)120 SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {}
121
getInst()122 SelectInst *getInst() { return SI; }
getUse()123 PHINode *getUse() { return SIUse; }
124
operator bool() const125 explicit operator bool() const { return SI && SIUse; }
126 };
127
128 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
129 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
130 std::vector<BasicBlock *> *NewBBs);
131
132 class DFAJumpThreading {
133 public:
DFAJumpThreading(AssumptionCache * AC,DominatorTree * DT,TargetTransformInfo * TTI,OptimizationRemarkEmitter * ORE)134 DFAJumpThreading(AssumptionCache *AC, DominatorTree *DT,
135 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)
136 : AC(AC), DT(DT), TTI(TTI), ORE(ORE) {}
137
138 bool run(Function &F);
139
140 private:
141 void
unfoldSelectInstrs(DominatorTree * DT,const SmallVector<SelectInstToUnfold,4> & SelectInsts)142 unfoldSelectInstrs(DominatorTree *DT,
143 const SmallVector<SelectInstToUnfold, 4> &SelectInsts) {
144 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
145 SmallVector<SelectInstToUnfold, 4> Stack;
146 for (SelectInstToUnfold SIToUnfold : SelectInsts)
147 Stack.push_back(SIToUnfold);
148
149 while (!Stack.empty()) {
150 SelectInstToUnfold SIToUnfold = Stack.pop_back_val();
151
152 std::vector<SelectInstToUnfold> NewSIsToUnfold;
153 std::vector<BasicBlock *> NewBBs;
154 unfold(&DTU, SIToUnfold, &NewSIsToUnfold, &NewBBs);
155
156 // Put newly discovered select instructions into the work list.
157 for (const SelectInstToUnfold &NewSIToUnfold : NewSIsToUnfold)
158 Stack.push_back(NewSIToUnfold);
159 }
160 }
161
162 AssumptionCache *AC;
163 DominatorTree *DT;
164 TargetTransformInfo *TTI;
165 OptimizationRemarkEmitter *ORE;
166 };
167
168 } // end anonymous namespace
169
170 namespace {
171
172 /// Create a new basic block and sink \p SIToSink into it.
createBasicBlockAndSinkSelectInst(DomTreeUpdater * DTU,SelectInst * SI,PHINode * SIUse,SelectInst * SIToSink,BasicBlock * EndBlock,StringRef NewBBName,BasicBlock ** NewBlock,BranchInst ** NewBranch,std::vector<SelectInstToUnfold> * NewSIsToUnfold,std::vector<BasicBlock * > * NewBBs)173 void createBasicBlockAndSinkSelectInst(
174 DomTreeUpdater *DTU, SelectInst *SI, PHINode *SIUse, SelectInst *SIToSink,
175 BasicBlock *EndBlock, StringRef NewBBName, BasicBlock **NewBlock,
176 BranchInst **NewBranch, std::vector<SelectInstToUnfold> *NewSIsToUnfold,
177 std::vector<BasicBlock *> *NewBBs) {
178 assert(SIToSink->hasOneUse());
179 assert(NewBlock);
180 assert(NewBranch);
181 *NewBlock = BasicBlock::Create(SI->getContext(), NewBBName,
182 EndBlock->getParent(), EndBlock);
183 NewBBs->push_back(*NewBlock);
184 *NewBranch = BranchInst::Create(EndBlock, *NewBlock);
185 SIToSink->moveBefore(*NewBranch);
186 NewSIsToUnfold->push_back(SelectInstToUnfold(SIToSink, SIUse));
187 DTU->applyUpdates({{DominatorTree::Insert, *NewBlock, EndBlock}});
188 }
189
190 /// Unfold the select instruction held in \p SIToUnfold by replacing it with
191 /// control flow.
192 ///
193 /// Put newly discovered select instructions into \p NewSIsToUnfold. Put newly
194 /// created basic blocks into \p NewBBs.
195 ///
196 /// TODO: merge it with CodeGenPrepare::optimizeSelectInst() if possible.
unfold(DomTreeUpdater * DTU,SelectInstToUnfold SIToUnfold,std::vector<SelectInstToUnfold> * NewSIsToUnfold,std::vector<BasicBlock * > * NewBBs)197 void unfold(DomTreeUpdater *DTU, SelectInstToUnfold SIToUnfold,
198 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
199 std::vector<BasicBlock *> *NewBBs) {
200 SelectInst *SI = SIToUnfold.getInst();
201 PHINode *SIUse = SIToUnfold.getUse();
202 BasicBlock *StartBlock = SI->getParent();
203 BasicBlock *EndBlock = SIUse->getParent();
204 BranchInst *StartBlockTerm =
205 dyn_cast<BranchInst>(StartBlock->getTerminator());
206
207 assert(StartBlockTerm && StartBlockTerm->isUnconditional());
208 assert(SI->hasOneUse());
209
210 // These are the new basic blocks for the conditional branch.
211 // At least one will become an actual new basic block.
212 BasicBlock *TrueBlock = nullptr;
213 BasicBlock *FalseBlock = nullptr;
214 BranchInst *TrueBranch = nullptr;
215 BranchInst *FalseBranch = nullptr;
216
217 // Sink select instructions to be able to unfold them later.
218 if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getTrueValue())) {
219 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
220 "si.unfold.true", &TrueBlock, &TrueBranch,
221 NewSIsToUnfold, NewBBs);
222 }
223 if (SelectInst *SIOp = dyn_cast<SelectInst>(SI->getFalseValue())) {
224 createBasicBlockAndSinkSelectInst(DTU, SI, SIUse, SIOp, EndBlock,
225 "si.unfold.false", &FalseBlock,
226 &FalseBranch, NewSIsToUnfold, NewBBs);
227 }
228
229 // If there was nothing to sink, then arbitrarily choose the 'false' side
230 // for a new input value to the PHI.
231 if (!TrueBlock && !FalseBlock) {
232 FalseBlock = BasicBlock::Create(SI->getContext(), "si.unfold.false",
233 EndBlock->getParent(), EndBlock);
234 NewBBs->push_back(FalseBlock);
235 BranchInst::Create(EndBlock, FalseBlock);
236 DTU->applyUpdates({{DominatorTree::Insert, FalseBlock, EndBlock}});
237 }
238
239 // Insert the real conditional branch based on the original condition.
240 // If we did not create a new block for one of the 'true' or 'false' paths
241 // of the condition, it means that side of the branch goes to the end block
242 // directly and the path originates from the start block from the point of
243 // view of the new PHI.
244 BasicBlock *TT = EndBlock;
245 BasicBlock *FT = EndBlock;
246 if (TrueBlock && FalseBlock) {
247 // A diamond.
248 TT = TrueBlock;
249 FT = FalseBlock;
250
251 // Update the phi node of SI.
252 SIUse->addIncoming(SI->getTrueValue(), TrueBlock);
253 SIUse->addIncoming(SI->getFalseValue(), FalseBlock);
254
255 // Update any other PHI nodes in EndBlock.
256 for (PHINode &Phi : EndBlock->phis()) {
257 if (&Phi != SIUse) {
258 Value *OrigValue = Phi.getIncomingValueForBlock(StartBlock);
259 Phi.addIncoming(OrigValue, TrueBlock);
260 Phi.addIncoming(OrigValue, FalseBlock);
261 }
262
263 // Remove incoming place of original StartBlock, which comes in a indirect
264 // way (through TrueBlock and FalseBlock) now.
265 Phi.removeIncomingValue(StartBlock, /* DeletePHIIfEmpty = */ false);
266 }
267 } else {
268 BasicBlock *NewBlock = nullptr;
269 Value *SIOp1 = SI->getTrueValue();
270 Value *SIOp2 = SI->getFalseValue();
271
272 // A triangle pointing right.
273 if (!TrueBlock) {
274 NewBlock = FalseBlock;
275 FT = FalseBlock;
276 }
277 // A triangle pointing left.
278 else {
279 NewBlock = TrueBlock;
280 TT = TrueBlock;
281 std::swap(SIOp1, SIOp2);
282 }
283
284 // Update the phi node of SI.
285 for (unsigned Idx = 0; Idx < SIUse->getNumIncomingValues(); ++Idx) {
286 if (SIUse->getIncomingBlock(Idx) == StartBlock)
287 SIUse->setIncomingValue(Idx, SIOp1);
288 }
289 SIUse->addIncoming(SIOp2, NewBlock);
290
291 // Update any other PHI nodes in EndBlock.
292 for (auto II = EndBlock->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
293 ++II) {
294 if (Phi != SIUse)
295 Phi->addIncoming(Phi->getIncomingValueForBlock(StartBlock), NewBlock);
296 }
297 }
298 StartBlockTerm->eraseFromParent();
299 BranchInst::Create(TT, FT, SI->getCondition(), StartBlock);
300 DTU->applyUpdates({{DominatorTree::Insert, StartBlock, TT},
301 {DominatorTree::Insert, StartBlock, FT}});
302
303 // The select is now dead.
304 assert(SI->use_empty() && "Select must be dead now");
305 SI->eraseFromParent();
306 }
307
308 struct ClonedBlock {
309 BasicBlock *BB;
310 APInt State; ///< \p State corresponds to the next value of a switch stmnt.
311 };
312
313 typedef std::deque<BasicBlock *> PathType;
314 typedef std::vector<PathType> PathsType;
315 typedef SmallPtrSet<const BasicBlock *, 8> VisitedBlocks;
316 typedef std::vector<ClonedBlock> CloneList;
317
318 // This data structure keeps track of all blocks that have been cloned. If two
319 // different ThreadingPaths clone the same block for a certain state it should
320 // be reused, and it can be looked up in this map.
321 typedef DenseMap<BasicBlock *, CloneList> DuplicateBlockMap;
322
323 // This map keeps track of all the new definitions for an instruction. This
324 // information is needed when restoring SSA form after cloning blocks.
325 typedef MapVector<Instruction *, std::vector<Instruction *>> DefMap;
326
operator <<(raw_ostream & OS,const PathType & Path)327 inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
328 OS << "< ";
329 for (const BasicBlock *BB : Path) {
330 std::string BBName;
331 if (BB->hasName())
332 raw_string_ostream(BBName) << BB->getName();
333 else
334 raw_string_ostream(BBName) << BB;
335 OS << BBName << " ";
336 }
337 OS << ">";
338 return OS;
339 }
340
341 /// ThreadingPath is a path in the control flow of a loop that can be threaded
342 /// by cloning necessary basic blocks and replacing conditional branches with
343 /// unconditional ones. A threading path includes a list of basic blocks, the
344 /// exit state, and the block that determines the next state.
345 struct ThreadingPath {
346 /// Exit value is DFA's exit state for the given path.
getExitValue__anon6d7772f80211::ThreadingPath347 APInt getExitValue() const { return ExitVal; }
setExitValue__anon6d7772f80211::ThreadingPath348 void setExitValue(const ConstantInt *V) {
349 ExitVal = V->getValue();
350 IsExitValSet = true;
351 }
isExitValueSet__anon6d7772f80211::ThreadingPath352 bool isExitValueSet() const { return IsExitValSet; }
353
354 /// Determinator is the basic block that determines the next state of the DFA.
getDeterminatorBB__anon6d7772f80211::ThreadingPath355 const BasicBlock *getDeterminatorBB() const { return DBB; }
setDeterminator__anon6d7772f80211::ThreadingPath356 void setDeterminator(const BasicBlock *BB) { DBB = BB; }
357
358 /// Path is a list of basic blocks.
getPath__anon6d7772f80211::ThreadingPath359 const PathType &getPath() const { return Path; }
setPath__anon6d7772f80211::ThreadingPath360 void setPath(const PathType &NewPath) { Path = NewPath; }
361
print__anon6d7772f80211::ThreadingPath362 void print(raw_ostream &OS) const {
363 OS << Path << " [ " << ExitVal << ", " << DBB->getName() << " ]";
364 }
365
366 private:
367 PathType Path;
368 APInt ExitVal;
369 const BasicBlock *DBB = nullptr;
370 bool IsExitValSet = false;
371 };
372
373 #ifndef NDEBUG
operator <<(raw_ostream & OS,const ThreadingPath & TPath)374 inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
375 TPath.print(OS);
376 return OS;
377 }
378 #endif
379
380 struct MainSwitch {
MainSwitch__anon6d7772f80211::MainSwitch381 MainSwitch(SwitchInst *SI, OptimizationRemarkEmitter *ORE) {
382 if (isCandidate(SI)) {
383 Instr = SI;
384 } else {
385 ORE->emit([&]() {
386 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)
387 << "Switch instruction is not predictable.";
388 });
389 }
390 }
391
392 virtual ~MainSwitch() = default;
393
getInstr__anon6d7772f80211::MainSwitch394 SwitchInst *getInstr() const { return Instr; }
getSelectInsts__anon6d7772f80211::MainSwitch395 const SmallVector<SelectInstToUnfold, 4> getSelectInsts() {
396 return SelectInsts;
397 }
398
399 private:
400 /// Do a use-def chain traversal starting from the switch condition to see if
401 /// \p SI is a potential condidate.
402 ///
403 /// Also, collect select instructions to unfold.
isCandidate__anon6d7772f80211::MainSwitch404 bool isCandidate(const SwitchInst *SI) {
405 std::deque<Value *> Q;
406 SmallSet<Value *, 16> SeenValues;
407 SelectInsts.clear();
408
409 Value *SICond = SI->getCondition();
410 LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n");
411 if (!isa<PHINode>(SICond))
412 return false;
413
414 addToQueue(SICond, Q, SeenValues);
415
416 while (!Q.empty()) {
417 Value *Current = Q.front();
418 Q.pop_front();
419
420 if (auto *Phi = dyn_cast<PHINode>(Current)) {
421 for (Value *Incoming : Phi->incoming_values()) {
422 addToQueue(Incoming, Q, SeenValues);
423 }
424 LLVM_DEBUG(dbgs() << "\tphi: " << *Phi << "\n");
425 } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
426 if (!isValidSelectInst(SelI))
427 return false;
428 addToQueue(SelI->getTrueValue(), Q, SeenValues);
429 addToQueue(SelI->getFalseValue(), Q, SeenValues);
430 LLVM_DEBUG(dbgs() << "\tselect: " << *SelI << "\n");
431 if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
432 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
433 } else if (isa<Constant>(Current)) {
434 LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n");
435 continue;
436 } else {
437 LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n");
438 // Allow unpredictable values. The hope is that those will be the
439 // initial switch values that can be ignored (they will hit the
440 // unthreaded switch) but this assumption will get checked later after
441 // paths have been enumerated (in function getStateDefMap).
442 continue;
443 }
444 }
445
446 return true;
447 }
448
addToQueue__anon6d7772f80211::MainSwitch449 void addToQueue(Value *Val, std::deque<Value *> &Q,
450 SmallSet<Value *, 16> &SeenValues) {
451 if (SeenValues.contains(Val))
452 return;
453 Q.push_back(Val);
454 SeenValues.insert(Val);
455 }
456
isValidSelectInst__anon6d7772f80211::MainSwitch457 bool isValidSelectInst(SelectInst *SI) {
458 if (!SI->hasOneUse())
459 return false;
460
461 Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
462 // The use of the select inst should be either a phi or another select.
463 if (!SIUse && !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
464 return false;
465
466 BasicBlock *SIBB = SI->getParent();
467
468 // Currently, we can only expand select instructions in basic blocks with
469 // one successor.
470 BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator());
471 if (!SITerm || !SITerm->isUnconditional())
472 return false;
473
474 // Only fold the select coming from directly where it is defined.
475 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
476 if (PHIUser && PHIUser->getIncomingBlock(*SI->use_begin()) != SIBB)
477 return false;
478
479 // If select will not be sunk during unfolding, and it is in the same basic
480 // block as another state defining select, then cannot unfold both.
481 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
482 SelectInst *PrevSI = SIToUnfold.getInst();
483 if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI &&
484 PrevSI->getParent() == SI->getParent())
485 return false;
486 }
487
488 return true;
489 }
490
491 SwitchInst *Instr = nullptr;
492 SmallVector<SelectInstToUnfold, 4> SelectInsts;
493 };
494
495 struct AllSwitchPaths {
AllSwitchPaths__anon6d7772f80211::AllSwitchPaths496 AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE)
497 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()),
498 ORE(ORE) {}
499
getThreadingPaths__anon6d7772f80211::AllSwitchPaths500 std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
getNumThreadingPaths__anon6d7772f80211::AllSwitchPaths501 unsigned getNumThreadingPaths() { return TPaths.size(); }
getSwitchInst__anon6d7772f80211::AllSwitchPaths502 SwitchInst *getSwitchInst() { return Switch; }
getSwitchBlock__anon6d7772f80211::AllSwitchPaths503 BasicBlock *getSwitchBlock() { return SwitchBlock; }
504
run__anon6d7772f80211::AllSwitchPaths505 void run() {
506 VisitedBlocks Visited;
507 PathsType LoopPaths = paths(SwitchBlock, Visited, /* PathDepth = */ 1);
508 StateDefMap StateDef = getStateDefMap(LoopPaths);
509
510 if (StateDef.empty()) {
511 ORE->emit([&]() {
512 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",
513 Switch)
514 << "Switch instruction is not predictable.";
515 });
516 return;
517 }
518
519 for (PathType Path : LoopPaths) {
520 ThreadingPath TPath;
521
522 const BasicBlock *PrevBB = Path.back();
523 for (const BasicBlock *BB : Path) {
524 if (StateDef.contains(BB)) {
525 const PHINode *Phi = dyn_cast<PHINode>(StateDef[BB]);
526 assert(Phi && "Expected a state-defining instr to be a phi node.");
527
528 const Value *V = Phi->getIncomingValueForBlock(PrevBB);
529 if (const ConstantInt *C = dyn_cast<const ConstantInt>(V)) {
530 TPath.setExitValue(C);
531 TPath.setDeterminator(BB);
532 TPath.setPath(Path);
533 }
534 }
535
536 // Switch block is the determinator, this is the final exit value.
537 if (TPath.isExitValueSet() && BB == Path.front())
538 break;
539
540 PrevBB = BB;
541 }
542
543 if (TPath.isExitValueSet() && isSupported(TPath))
544 TPaths.push_back(TPath);
545 }
546 }
547
548 private:
549 // Value: an instruction that defines a switch state;
550 // Key: the parent basic block of that instruction.
551 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
552
paths__anon6d7772f80211::AllSwitchPaths553 PathsType paths(BasicBlock *BB, VisitedBlocks &Visited,
554 unsigned PathDepth) const {
555 PathsType Res;
556
557 // Stop exploring paths after visiting MaxPathLength blocks
558 if (PathDepth > MaxPathLength) {
559 ORE->emit([&]() {
560 return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached",
561 Switch)
562 << "Exploration stopped after visiting MaxPathLength="
563 << ore::NV("MaxPathLength", MaxPathLength) << " blocks.";
564 });
565 return Res;
566 }
567
568 Visited.insert(BB);
569
570 // Some blocks have multiple edges to the same successor, and this set
571 // is used to prevent a duplicate path from being generated
572 SmallSet<BasicBlock *, 4> Successors;
573 for (BasicBlock *Succ : successors(BB)) {
574 if (!Successors.insert(Succ).second)
575 continue;
576
577 // Found a cycle through the SwitchBlock
578 if (Succ == SwitchBlock) {
579 Res.push_back({BB});
580 continue;
581 }
582
583 // We have encountered a cycle, do not get caught in it
584 if (Visited.contains(Succ))
585 continue;
586
587 PathsType SuccPaths = paths(Succ, Visited, PathDepth + 1);
588 for (const PathType &Path : SuccPaths) {
589 PathType NewPath(Path);
590 NewPath.push_front(BB);
591 Res.push_back(NewPath);
592 if (Res.size() >= MaxNumPaths) {
593 return Res;
594 }
595 }
596 }
597 // This block could now be visited again from a different predecessor. Note
598 // that this will result in exponential runtime. Subpaths could possibly be
599 // cached but it takes a lot of memory to store them.
600 Visited.erase(BB);
601 return Res;
602 }
603
604 /// Walk the use-def chain and collect all the state-defining instructions.
605 ///
606 /// Return an empty map if unpredictable values encountered inside the basic
607 /// blocks of \p LoopPaths.
getStateDefMap__anon6d7772f80211::AllSwitchPaths608 StateDefMap getStateDefMap(const PathsType &LoopPaths) const {
609 StateDefMap Res;
610
611 // Basic blocks belonging to any of the loops around the switch statement.
612 SmallPtrSet<BasicBlock *, 16> LoopBBs;
613 for (const PathType &Path : LoopPaths) {
614 for (BasicBlock *BB : Path)
615 LoopBBs.insert(BB);
616 }
617
618 Value *FirstDef = Switch->getOperand(0);
619
620 assert(isa<PHINode>(FirstDef) && "The first definition must be a phi.");
621
622 SmallVector<PHINode *, 8> Stack;
623 Stack.push_back(dyn_cast<PHINode>(FirstDef));
624 SmallSet<Value *, 16> SeenValues;
625
626 while (!Stack.empty()) {
627 PHINode *CurPhi = Stack.pop_back_val();
628
629 Res[CurPhi->getParent()] = CurPhi;
630 SeenValues.insert(CurPhi);
631
632 for (BasicBlock *IncomingBB : CurPhi->blocks()) {
633 Value *Incoming = CurPhi->getIncomingValueForBlock(IncomingBB);
634 bool IsOutsideLoops = LoopBBs.count(IncomingBB) == 0;
635 if (Incoming == FirstDef || isa<ConstantInt>(Incoming) ||
636 SeenValues.contains(Incoming) || IsOutsideLoops) {
637 continue;
638 }
639
640 // Any unpredictable value inside the loops means we must bail out.
641 if (!isa<PHINode>(Incoming))
642 return StateDefMap();
643
644 Stack.push_back(cast<PHINode>(Incoming));
645 }
646 }
647
648 return Res;
649 }
650
651 /// The determinator BB should precede the switch-defining BB.
652 ///
653 /// Otherwise, it is possible that the state defined in the determinator block
654 /// defines the state for the next iteration of the loop, rather than for the
655 /// current one.
656 ///
657 /// Currently supported paths:
658 /// \code
659 /// < switch bb1 determ def > [ 42, determ ]
660 /// < switch_and_def bb1 determ > [ 42, determ ]
661 /// < switch_and_def_and_determ bb1 > [ 42, switch_and_def_and_determ ]
662 /// \endcode
663 ///
664 /// Unsupported paths:
665 /// \code
666 /// < switch bb1 def determ > [ 43, determ ]
667 /// < switch_and_determ bb1 def > [ 43, switch_and_determ ]
668 /// \endcode
isSupported__anon6d7772f80211::AllSwitchPaths669 bool isSupported(const ThreadingPath &TPath) {
670 Instruction *SwitchCondI = dyn_cast<Instruction>(Switch->getCondition());
671 assert(SwitchCondI);
672 if (!SwitchCondI)
673 return false;
674
675 const BasicBlock *SwitchCondDefBB = SwitchCondI->getParent();
676 const BasicBlock *SwitchCondUseBB = Switch->getParent();
677 const BasicBlock *DeterminatorBB = TPath.getDeterminatorBB();
678
679 assert(
680 SwitchCondUseBB == TPath.getPath().front() &&
681 "The first BB in a threading path should have the switch instruction");
682 if (SwitchCondUseBB != TPath.getPath().front())
683 return false;
684
685 // Make DeterminatorBB the first element in Path.
686 PathType Path = TPath.getPath();
687 auto ItDet = llvm::find(Path, DeterminatorBB);
688 std::rotate(Path.begin(), ItDet, Path.end());
689
690 bool IsDetBBSeen = false;
691 bool IsDefBBSeen = false;
692 bool IsUseBBSeen = false;
693 for (BasicBlock *BB : Path) {
694 if (BB == DeterminatorBB)
695 IsDetBBSeen = true;
696 if (BB == SwitchCondDefBB)
697 IsDefBBSeen = true;
698 if (BB == SwitchCondUseBB)
699 IsUseBBSeen = true;
700 if (IsDetBBSeen && IsUseBBSeen && !IsDefBBSeen)
701 return false;
702 }
703
704 return true;
705 }
706
707 SwitchInst *Switch;
708 BasicBlock *SwitchBlock;
709 OptimizationRemarkEmitter *ORE;
710 std::vector<ThreadingPath> TPaths;
711 };
712
713 struct TransformDFA {
TransformDFA__anon6d7772f80211::TransformDFA714 TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT,
715 AssumptionCache *AC, TargetTransformInfo *TTI,
716 OptimizationRemarkEmitter *ORE,
717 SmallPtrSet<const Value *, 32> EphValues)
718 : SwitchPaths(SwitchPaths), DT(DT), AC(AC), TTI(TTI), ORE(ORE),
719 EphValues(EphValues) {}
720
run__anon6d7772f80211::TransformDFA721 void run() {
722 if (isLegalAndProfitableToTransform()) {
723 createAllExitPaths();
724 NumTransforms++;
725 }
726 }
727
728 private:
729 /// This function performs both a legality check and profitability check at
730 /// the same time since it is convenient to do so. It iterates through all
731 /// blocks that will be cloned, and keeps track of the duplication cost. It
732 /// also returns false if it is illegal to clone some required block.
isLegalAndProfitableToTransform__anon6d7772f80211::TransformDFA733 bool isLegalAndProfitableToTransform() {
734 CodeMetrics Metrics;
735 SwitchInst *Switch = SwitchPaths->getSwitchInst();
736
737 // Don't thread switch without multiple successors.
738 if (Switch->getNumSuccessors() <= 1)
739 return false;
740
741 // Note that DuplicateBlockMap is not being used as intended here. It is
742 // just being used to ensure (BB, State) pairs are only counted once.
743 DuplicateBlockMap DuplicateMap;
744
745 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
746 PathType PathBBs = TPath.getPath();
747 APInt NextState = TPath.getExitValue();
748 const BasicBlock *Determinator = TPath.getDeterminatorBB();
749
750 // Update Metrics for the Switch block, this is always cloned
751 BasicBlock *BB = SwitchPaths->getSwitchBlock();
752 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
753 if (!VisitedBB) {
754 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
755 DuplicateMap[BB].push_back({BB, NextState});
756 }
757
758 // If the Switch block is the Determinator, then we can continue since
759 // this is the only block that is cloned and we already counted for it.
760 if (PathBBs.front() == Determinator)
761 continue;
762
763 // Otherwise update Metrics for all blocks that will be cloned. If any
764 // block is already cloned and would be reused, don't double count it.
765 auto DetIt = llvm::find(PathBBs, Determinator);
766 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
767 BB = *BBIt;
768 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
769 if (VisitedBB)
770 continue;
771 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
772 DuplicateMap[BB].push_back({BB, NextState});
773 }
774
775 if (Metrics.notDuplicatable) {
776 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
777 << "non-duplicatable instructions.\n");
778 ORE->emit([&]() {
779 return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst",
780 Switch)
781 << "Contains non-duplicatable instructions.";
782 });
783 return false;
784 }
785
786 if (Metrics.convergent) {
787 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
788 << "convergent instructions.\n");
789 ORE->emit([&]() {
790 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
791 << "Contains convergent instructions.";
792 });
793 return false;
794 }
795
796 if (!Metrics.NumInsts.isValid()) {
797 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
798 << "instructions with invalid cost.\n");
799 ORE->emit([&]() {
800 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
801 << "Contains instructions with invalid cost.";
802 });
803 return false;
804 }
805 }
806
807 InstructionCost DuplicationCost = 0;
808
809 unsigned JumpTableSize = 0;
810 TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr,
811 nullptr);
812 if (JumpTableSize == 0) {
813 // Factor in the number of conditional branches reduced from jump
814 // threading. Assume that lowering the switch block is implemented by
815 // using binary search, hence the LogBase2().
816 unsigned CondBranches =
817 APInt(32, Switch->getNumSuccessors()).ceilLogBase2();
818 assert(CondBranches > 0 &&
819 "The threaded switch must have multiple branches");
820 DuplicationCost = Metrics.NumInsts / CondBranches;
821 } else {
822 // Compared with jump tables, the DFA optimizer removes an indirect branch
823 // on each loop iteration, thus making branch prediction more precise. The
824 // more branch targets there are, the more likely it is for the branch
825 // predictor to make a mistake, and the more benefit there is in the DFA
826 // optimizer. Thus, the more branch targets there are, the lower is the
827 // cost of the DFA opt.
828 DuplicationCost = Metrics.NumInsts / JumpTableSize;
829 }
830
831 LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "
832 << SwitchPaths->getSwitchBlock()->getName()
833 << " is: " << DuplicationCost << "\n\n");
834
835 if (DuplicationCost > CostThreshold) {
836 LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "
837 << "cost threshold.\n");
838 ORE->emit([&]() {
839 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
840 << "Duplication cost exceeds the cost threshold (cost="
841 << ore::NV("Cost", DuplicationCost)
842 << ", threshold=" << ore::NV("Threshold", CostThreshold) << ").";
843 });
844 return false;
845 }
846
847 ORE->emit([&]() {
848 return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch)
849 << "Switch statement jump-threaded.";
850 });
851
852 return true;
853 }
854
855 /// Transform each threading path to effectively jump thread the DFA.
createAllExitPaths__anon6d7772f80211::TransformDFA856 void createAllExitPaths() {
857 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager);
858
859 // Move the switch block to the end of the path, since it will be duplicated
860 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
861 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
862 LLVM_DEBUG(dbgs() << TPath << "\n");
863 PathType NewPath(TPath.getPath());
864 NewPath.push_back(SwitchBlock);
865 TPath.setPath(NewPath);
866 }
867
868 // Transform the ThreadingPaths and keep track of the cloned values
869 DuplicateBlockMap DuplicateMap;
870 DefMap NewDefs;
871
872 SmallSet<BasicBlock *, 16> BlocksToClean;
873 for (BasicBlock *BB : successors(SwitchBlock))
874 BlocksToClean.insert(BB);
875
876 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
877 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
878 NumPaths++;
879 }
880
881 // After all paths are cloned, now update the last successor of the cloned
882 // path so it skips over the switch statement
883 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
884 updateLastSuccessor(TPath, DuplicateMap, &DTU);
885
886 // For each instruction that was cloned and used outside, update its uses
887 updateSSA(NewDefs);
888
889 // Clean PHI Nodes for the newly created blocks
890 for (BasicBlock *BB : BlocksToClean)
891 cleanPhiNodes(BB);
892 }
893
894 /// For a specific ThreadingPath \p Path, create an exit path starting from
895 /// the determinator block.
896 ///
897 /// To remember the correct destination, we have to duplicate blocks
898 /// corresponding to each state. Also update the terminating instruction of
899 /// the predecessors, and phis in the successor blocks.
createExitPath__anon6d7772f80211::TransformDFA900 void createExitPath(DefMap &NewDefs, ThreadingPath &Path,
901 DuplicateBlockMap &DuplicateMap,
902 SmallSet<BasicBlock *, 16> &BlocksToClean,
903 DomTreeUpdater *DTU) {
904 APInt NextState = Path.getExitValue();
905 const BasicBlock *Determinator = Path.getDeterminatorBB();
906 PathType PathBBs = Path.getPath();
907
908 // Don't select the placeholder block in front
909 if (PathBBs.front() == Determinator)
910 PathBBs.pop_front();
911
912 auto DetIt = llvm::find(PathBBs, Determinator);
913 // When there is only one BB in PathBBs, the determinator takes itself as a
914 // direct predecessor.
915 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);
916 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
917 BasicBlock *BB = *BBIt;
918 BlocksToClean.insert(BB);
919
920 // We already cloned BB for this NextState, now just update the branch
921 // and continue.
922 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
923 if (NextBB) {
924 updatePredecessor(PrevBB, BB, NextBB, DTU);
925 PrevBB = NextBB;
926 continue;
927 }
928
929 // Clone the BB and update the successor of Prev to jump to the new block
930 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
931 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
932 DuplicateMap[BB].push_back({NewBB, NextState});
933 BlocksToClean.insert(NewBB);
934 PrevBB = NewBB;
935 }
936 }
937
938 /// Restore SSA form after cloning blocks.
939 ///
940 /// Each cloned block creates new defs for a variable, and the uses need to be
941 /// updated to reflect this. The uses may be replaced with a cloned value, or
942 /// some derived phi instruction. Note that all uses of a value defined in the
943 /// same block were already remapped when cloning the block.
updateSSA__anon6d7772f80211::TransformDFA944 void updateSSA(DefMap &NewDefs) {
945 SSAUpdaterBulk SSAUpdate;
946 SmallVector<Use *, 16> UsesToRename;
947
948 for (const auto &KV : NewDefs) {
949 Instruction *I = KV.first;
950 BasicBlock *BB = I->getParent();
951 std::vector<Instruction *> Cloned = KV.second;
952
953 // Scan all uses of this instruction to see if it is used outside of its
954 // block, and if so, record them in UsesToRename.
955 for (Use &U : I->uses()) {
956 Instruction *User = cast<Instruction>(U.getUser());
957 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
958 if (UserPN->getIncomingBlock(U) == BB)
959 continue;
960 } else if (User->getParent() == BB) {
961 continue;
962 }
963
964 UsesToRename.push_back(&U);
965 }
966
967 // If there are no uses outside the block, we're done with this
968 // instruction.
969 if (UsesToRename.empty())
970 continue;
971 LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I
972 << "\n");
973
974 // We found a use of I outside of BB. Rename all uses of I that are
975 // outside its block to be uses of the appropriate PHI node etc. See
976 // ValuesInBlocks with the values we know.
977 unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());
978 SSAUpdate.AddAvailableValue(VarNum, BB, I);
979 for (Instruction *New : Cloned)
980 SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New);
981
982 while (!UsesToRename.empty())
983 SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val());
984
985 LLVM_DEBUG(dbgs() << "\n");
986 }
987 // SSAUpdater handles phi placement and renaming uses with the appropriate
988 // value.
989 SSAUpdate.RewriteAllUses(DT);
990 }
991
992 /// Clones a basic block, and adds it to the CFG.
993 ///
994 /// This function also includes updating phi nodes in the successors of the
995 /// BB, and remapping uses that were defined locally in the cloned BB.
cloneBlockAndUpdatePredecessor__anon6d7772f80211::TransformDFA996 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
997 const APInt &NextState,
998 DuplicateBlockMap &DuplicateMap,
999 DefMap &NewDefs,
1000 DomTreeUpdater *DTU) {
1001 ValueToValueMapTy VMap;
1002 BasicBlock *NewBB = CloneBasicBlock(
1003 BB, VMap, ".jt" + std::to_string(NextState.getLimitedValue()),
1004 BB->getParent());
1005 NewBB->moveAfter(BB);
1006 NumCloned++;
1007
1008 for (Instruction &I : *NewBB) {
1009 // Do not remap operands of PHINode in case a definition in BB is an
1010 // incoming value to a phi in the same block. This incoming value will
1011 // be renamed later while restoring SSA.
1012 if (isa<PHINode>(&I))
1013 continue;
1014 RemapInstruction(&I, VMap,
1015 RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
1016 if (AssumeInst *II = dyn_cast<AssumeInst>(&I))
1017 AC->registerAssumption(II);
1018 }
1019
1020 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1021 updatePredecessor(PrevBB, BB, NewBB, DTU);
1022 updateDefMap(NewDefs, VMap);
1023
1024 // Add all successors to the DominatorTree
1025 SmallPtrSet<BasicBlock *, 4> SuccSet;
1026 for (auto *SuccBB : successors(NewBB)) {
1027 if (SuccSet.insert(SuccBB).second)
1028 DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1029 }
1030 SuccSet.clear();
1031 return NewBB;
1032 }
1033
1034 /// Update the phi nodes in BB's successors.
1035 ///
1036 /// This means creating a new incoming value from NewBB with the new
1037 /// instruction wherever there is an incoming value from BB.
updateSuccessorPhis__anon6d7772f80211::TransformDFA1038 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1039 const APInt &NextState, ValueToValueMapTy &VMap,
1040 DuplicateBlockMap &DuplicateMap) {
1041 std::vector<BasicBlock *> BlocksToUpdate;
1042
1043 // If BB is the last block in the path, we can simply update the one case
1044 // successor that will be reached.
1045 if (BB == SwitchPaths->getSwitchBlock()) {
1046 SwitchInst *Switch = SwitchPaths->getSwitchInst();
1047 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1048 BlocksToUpdate.push_back(NextCase);
1049 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1050 if (ClonedSucc)
1051 BlocksToUpdate.push_back(ClonedSucc);
1052 }
1053 // Otherwise update phis in all successors.
1054 else {
1055 for (BasicBlock *Succ : successors(BB)) {
1056 BlocksToUpdate.push_back(Succ);
1057
1058 // Check if a successor has already been cloned for the particular exit
1059 // value. In this case if a successor was already cloned, the phi nodes
1060 // in the cloned block should be updated directly.
1061 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1062 if (ClonedSucc)
1063 BlocksToUpdate.push_back(ClonedSucc);
1064 }
1065 }
1066
1067 // If there is a phi with an incoming value from BB, create a new incoming
1068 // value for the new predecessor ClonedBB. The value will either be the same
1069 // value from BB or a cloned value.
1070 for (BasicBlock *Succ : BlocksToUpdate) {
1071 for (auto II = Succ->begin(); PHINode *Phi = dyn_cast<PHINode>(II);
1072 ++II) {
1073 Value *Incoming = Phi->getIncomingValueForBlock(BB);
1074 if (Incoming) {
1075 if (isa<Constant>(Incoming)) {
1076 Phi->addIncoming(Incoming, ClonedBB);
1077 continue;
1078 }
1079 Value *ClonedVal = VMap[Incoming];
1080 if (ClonedVal)
1081 Phi->addIncoming(ClonedVal, ClonedBB);
1082 else
1083 Phi->addIncoming(Incoming, ClonedBB);
1084 }
1085 }
1086 }
1087 }
1088
1089 /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all
1090 /// other successors are kept as well.
updatePredecessor__anon6d7772f80211::TransformDFA1091 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1092 BasicBlock *NewBB, DomTreeUpdater *DTU) {
1093 // When a path is reused, there is a chance that predecessors were already
1094 // updated before. Check if the predecessor needs to be updated first.
1095 if (!isPredecessor(OldBB, PrevBB))
1096 return;
1097
1098 Instruction *PrevTerm = PrevBB->getTerminator();
1099 for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) {
1100 if (PrevTerm->getSuccessor(Idx) == OldBB) {
1101 OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true);
1102 PrevTerm->setSuccessor(Idx, NewBB);
1103 }
1104 }
1105 DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1106 {DominatorTree::Insert, PrevBB, NewBB}});
1107 }
1108
1109 /// Add new value mappings to the DefMap to keep track of all new definitions
1110 /// for a particular instruction. These will be used while updating SSA form.
updateDefMap__anon6d7772f80211::TransformDFA1111 void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
1112 SmallVector<std::pair<Instruction *, Instruction *>> NewDefsVector;
1113 NewDefsVector.reserve(VMap.size());
1114
1115 for (auto Entry : VMap) {
1116 Instruction *Inst =
1117 dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
1118 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1119 isa<SwitchInst>(Inst)) {
1120 continue;
1121 }
1122
1123 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1124 if (!Cloned)
1125 continue;
1126
1127 NewDefsVector.push_back({Inst, Cloned});
1128 }
1129
1130 // Sort the defs to get deterministic insertion order into NewDefs.
1131 sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {
1132 if (LHS.first == RHS.first)
1133 return LHS.second->comesBefore(RHS.second);
1134 return LHS.first->comesBefore(RHS.first);
1135 });
1136
1137 for (const auto &KV : NewDefsVector)
1138 NewDefs[KV.first].push_back(KV.second);
1139 }
1140
1141 /// Update the last branch of a particular cloned path to point to the correct
1142 /// case successor.
1143 ///
1144 /// Note that this is an optional step and would have been done in later
1145 /// optimizations, but it makes the CFG significantly easier to work with.
updateLastSuccessor__anon6d7772f80211::TransformDFA1146 void updateLastSuccessor(ThreadingPath &TPath,
1147 DuplicateBlockMap &DuplicateMap,
1148 DomTreeUpdater *DTU) {
1149 APInt NextState = TPath.getExitValue();
1150 BasicBlock *BB = TPath.getPath().back();
1151 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1152
1153 // Note multiple paths can end at the same block so check that it is not
1154 // updated yet
1155 if (!isa<SwitchInst>(LastBlock->getTerminator()))
1156 return;
1157 SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator());
1158 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1159
1160 std::vector<DominatorTree::UpdateType> DTUpdates;
1161 SmallPtrSet<BasicBlock *, 4> SuccSet;
1162 for (BasicBlock *Succ : successors(LastBlock)) {
1163 if (Succ != NextCase && SuccSet.insert(Succ).second)
1164 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1165 }
1166
1167 Switch->eraseFromParent();
1168 BranchInst::Create(NextCase, LastBlock);
1169
1170 DTU->applyUpdates(DTUpdates);
1171 }
1172
1173 /// After cloning blocks, some of the phi nodes have extra incoming values
1174 /// that are no longer used. This function removes them.
cleanPhiNodes__anon6d7772f80211::TransformDFA1175 void cleanPhiNodes(BasicBlock *BB) {
1176 // If BB is no longer reachable, remove any remaining phi nodes
1177 if (pred_empty(BB)) {
1178 std::vector<PHINode *> PhiToRemove;
1179 for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1180 PhiToRemove.push_back(Phi);
1181 }
1182 for (PHINode *PN : PhiToRemove) {
1183 PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));
1184 PN->eraseFromParent();
1185 }
1186 return;
1187 }
1188
1189 // Remove any incoming values that come from an invalid predecessor
1190 for (auto II = BB->begin(); PHINode *Phi = dyn_cast<PHINode>(II); ++II) {
1191 std::vector<BasicBlock *> BlocksToRemove;
1192 for (BasicBlock *IncomingBB : Phi->blocks()) {
1193 if (!isPredecessor(BB, IncomingBB))
1194 BlocksToRemove.push_back(IncomingBB);
1195 }
1196 for (BasicBlock *BB : BlocksToRemove)
1197 Phi->removeIncomingValue(BB);
1198 }
1199 }
1200
1201 /// Checks if BB was already cloned for a particular next state value. If it
1202 /// was then it returns this cloned block, and otherwise null.
getClonedBB__anon6d7772f80211::TransformDFA1203 BasicBlock *getClonedBB(BasicBlock *BB, const APInt &NextState,
1204 DuplicateBlockMap &DuplicateMap) {
1205 CloneList ClonedBBs = DuplicateMap[BB];
1206
1207 // Find an entry in the CloneList with this NextState. If it exists then
1208 // return the corresponding BB
1209 auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {
1210 return C.State == NextState;
1211 });
1212 return It != ClonedBBs.end() ? (*It).BB : nullptr;
1213 }
1214
1215 /// Helper to get the successor corresponding to a particular case value for
1216 /// a switch statement.
getNextCaseSuccessor__anon6d7772f80211::TransformDFA1217 BasicBlock *getNextCaseSuccessor(SwitchInst *Switch, const APInt &NextState) {
1218 BasicBlock *NextCase = nullptr;
1219 for (auto Case : Switch->cases()) {
1220 if (Case.getCaseValue()->getValue() == NextState) {
1221 NextCase = Case.getCaseSuccessor();
1222 break;
1223 }
1224 }
1225 if (!NextCase)
1226 NextCase = Switch->getDefaultDest();
1227 return NextCase;
1228 }
1229
1230 /// Returns true if IncomingBB is a predecessor of BB.
isPredecessor__anon6d7772f80211::TransformDFA1231 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1232 return llvm::is_contained(predecessors(BB), IncomingBB);
1233 }
1234
1235 AllSwitchPaths *SwitchPaths;
1236 DominatorTree *DT;
1237 AssumptionCache *AC;
1238 TargetTransformInfo *TTI;
1239 OptimizationRemarkEmitter *ORE;
1240 SmallPtrSet<const Value *, 32> EphValues;
1241 std::vector<ThreadingPath> TPaths;
1242 };
1243
run(Function & F)1244 bool DFAJumpThreading::run(Function &F) {
1245 LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");
1246
1247 if (F.hasOptSize()) {
1248 LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n");
1249 return false;
1250 }
1251
1252 if (ClViewCfgBefore)
1253 F.viewCFG();
1254
1255 SmallVector<AllSwitchPaths, 2> ThreadableLoops;
1256 bool MadeChanges = false;
1257
1258 for (BasicBlock &BB : F) {
1259 auto *SI = dyn_cast<SwitchInst>(BB.getTerminator());
1260 if (!SI)
1261 continue;
1262
1263 LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName()
1264 << " is a candidate\n");
1265 MainSwitch Switch(SI, ORE);
1266
1267 if (!Switch.getInstr())
1268 continue;
1269
1270 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
1271 << "candidate for jump threading\n");
1272 LLVM_DEBUG(SI->dump());
1273
1274 unfoldSelectInstrs(DT, Switch.getSelectInsts());
1275 if (!Switch.getSelectInsts().empty())
1276 MadeChanges = true;
1277
1278 AllSwitchPaths SwitchPaths(&Switch, ORE);
1279 SwitchPaths.run();
1280
1281 if (SwitchPaths.getNumThreadingPaths() > 0) {
1282 ThreadableLoops.push_back(SwitchPaths);
1283
1284 // For the time being limit this optimization to occurring once in a
1285 // function since it can change the CFG significantly. This is not a
1286 // strict requirement but it can cause buggy behavior if there is an
1287 // overlap of blocks in different opportunities. There is a lot of room to
1288 // experiment with catching more opportunities here.
1289 break;
1290 }
1291 }
1292
1293 SmallPtrSet<const Value *, 32> EphValues;
1294 if (ThreadableLoops.size() > 0)
1295 CodeMetrics::collectEphemeralValues(&F, AC, EphValues);
1296
1297 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1298 TransformDFA Transform(&SwitchPaths, DT, AC, TTI, ORE, EphValues);
1299 Transform.run();
1300 MadeChanges = true;
1301 }
1302
1303 #ifdef EXPENSIVE_CHECKS
1304 assert(DT->verify(DominatorTree::VerificationLevel::Full));
1305 verifyFunction(F, &dbgs());
1306 #endif
1307
1308 return MadeChanges;
1309 }
1310
1311 } // end anonymous namespace
1312
1313 /// Integrate with the new Pass Manager
run(Function & F,FunctionAnalysisManager & AM)1314 PreservedAnalyses DFAJumpThreadingPass::run(Function &F,
1315 FunctionAnalysisManager &AM) {
1316 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
1317 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
1318 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
1319 OptimizationRemarkEmitter ORE(&F);
1320
1321 if (!DFAJumpThreading(&AC, &DT, &TTI, &ORE).run(F))
1322 return PreservedAnalyses::all();
1323
1324 PreservedAnalyses PA;
1325 PA.preserve<DominatorTreeAnalysis>();
1326 return PA;
1327 }
1328