LLVM 22.0.0git
DFAJumpThreading.cpp
Go to the documentation of this file.
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
61#include "llvm/ADT/APInt.h"
62#include "llvm/ADT/DenseMap.h"
63#include "llvm/ADT/Statistic.h"
70#include "llvm/IR/CFG.h"
71#include "llvm/IR/Constants.h"
74#include "llvm/Support/Debug.h"
78#include <deque>
79
80#ifdef EXPENSIVE_CHECKS
81#include "llvm/IR/Verifier.h"
82#endif
83
84using namespace llvm;
85
86#define DEBUG_TYPE "dfa-jump-threading"
87
88STATISTIC(NumTransforms, "Number of transformations done");
89STATISTIC(NumCloned, "Number of blocks cloned");
90STATISTIC(NumPaths, "Number of individual paths threaded");
91
92namespace llvm {
93static 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
99 "dfa-early-exit-heuristic",
100 cl::desc("Exit early if an unpredictable value come from the same loop"),
101 cl::Hidden, cl::init(true));
102
104 "dfa-max-path-length",
105 cl::desc("Max number of blocks searched to find a threading path"),
106 cl::Hidden, cl::init(20));
107
109 "dfa-max-num-visited-paths",
110 cl::desc(
111 "Max number of blocks visited while enumerating paths around a switch"),
112 cl::Hidden, cl::init(2500));
113
115 MaxNumPaths("dfa-max-num-paths",
116 cl::desc("Max number of paths enumerated around a switch"),
117 cl::Hidden, cl::init(200));
118
120 CostThreshold("dfa-cost-threshold",
121 cl::desc("Maximum cost accepted for the transformation"),
122 cl::Hidden, cl::init(50));
123
125
126} // namespace llvm
127
129 "dfa-max-cloned-rate",
130 cl::desc(
131 "Maximum cloned instructions rate accepted for the transformation"),
132 cl::Hidden, cl::init(7.5));
133
134namespace {
135class SelectInstToUnfold {
136 SelectInst *SI;
137 PHINode *SIUse;
138
139public:
140 SelectInstToUnfold(SelectInst *SI, PHINode *SIUse) : SI(SI), SIUse(SIUse) {}
141
142 SelectInst *getInst() { return SI; }
143 PHINode *getUse() { return SIUse; }
144
145 explicit operator bool() const { return SI && SIUse; }
146};
147
148class DFAJumpThreading {
149public:
150 DFAJumpThreading(AssumptionCache *AC, DominatorTree *DT, LoopInfo *LI,
151 TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE)
152 : AC(AC), DT(DT), LI(LI), TTI(TTI), ORE(ORE) {}
153
154 bool run(Function &F);
155 bool LoopInfoBroken;
156
157private:
158 void
159 unfoldSelectInstrs(DominatorTree *DT,
160 const SmallVector<SelectInstToUnfold, 4> &SelectInsts) {
161 // TODO: Have everything use a single lazy DTU
162 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
164
165 while (!Stack.empty()) {
166 SelectInstToUnfold SIToUnfold = Stack.pop_back_val();
167
168 std::vector<SelectInstToUnfold> NewSIsToUnfold;
169 std::vector<BasicBlock *> NewBBs;
170 unfold(&DTU, LI, SIToUnfold, &NewSIsToUnfold, &NewBBs);
171
172 // Put newly discovered select instructions into the work list.
173 llvm::append_range(Stack, NewSIsToUnfold);
174 }
175 }
176
177 static void unfold(DomTreeUpdater *DTU, LoopInfo *LI,
178 SelectInstToUnfold SIToUnfold,
179 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
180 std::vector<BasicBlock *> *NewBBs);
181
182 AssumptionCache *AC;
183 DominatorTree *DT;
184 LoopInfo *LI;
185 TargetTransformInfo *TTI;
186 OptimizationRemarkEmitter *ORE;
187};
188} // namespace
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.
197void DFAJumpThreading::unfold(DomTreeUpdater *DTU, LoopInfo *LI,
198 SelectInstToUnfold SIToUnfold,
199 std::vector<SelectInstToUnfold> *NewSIsToUnfold,
200 std::vector<BasicBlock *> *NewBBs) {
201 SelectInst *SI = SIToUnfold.getInst();
202 PHINode *SIUse = SIToUnfold.getUse();
203 assert(SI->hasOneUse());
204 // The select may come indirectly, instead of from where it is defined.
205 BasicBlock *StartBlock = SIUse->getIncomingBlock(*SI->use_begin());
206 BranchInst *StartBlockTerm =
207 dyn_cast<BranchInst>(StartBlock->getTerminator());
208 assert(StartBlockTerm);
209
210 if (StartBlockTerm->isUnconditional()) {
211 BasicBlock *EndBlock = StartBlock->getUniqueSuccessor();
212 // Arbitrarily choose the 'false' side for a new input value to the PHI.
213 BasicBlock *NewBlock = BasicBlock::Create(
214 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
215 EndBlock->getParent(), EndBlock);
216 NewBBs->push_back(NewBlock);
217 BranchInst::Create(EndBlock, NewBlock);
218 DTU->applyUpdates({{DominatorTree::Insert, NewBlock, EndBlock}});
219
220 // StartBlock
221 // | \
222 // | NewBlock
223 // | /
224 // EndBlock
225 Value *SIOp1 = SI->getTrueValue();
226 Value *SIOp2 = SI->getFalseValue();
227
228 PHINode *NewPhi = PHINode::Create(SIUse->getType(), 1,
229 Twine(SIOp2->getName(), ".si.unfold.phi"),
230 NewBlock->getFirstInsertionPt());
231 NewPhi->addIncoming(SIOp2, StartBlock);
232
233 // Update any other PHI nodes in EndBlock.
234 for (PHINode &Phi : EndBlock->phis()) {
235 if (SIUse == &Phi)
236 continue;
237 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlock);
238 }
239
240 // Update the phi node of SI, which is its only use.
241 if (EndBlock == SIUse->getParent()) {
242 SIUse->addIncoming(NewPhi, NewBlock);
243 SIUse->replaceUsesOfWith(SI, SIOp1);
244 } else {
245 PHINode *EndPhi = PHINode::Create(SIUse->getType(), pred_size(EndBlock),
246 Twine(SI->getName(), ".si.unfold.phi"),
247 EndBlock->getFirstInsertionPt());
248 for (BasicBlock *Pred : predecessors(EndBlock)) {
249 if (Pred != StartBlock && Pred != NewBlock)
250 EndPhi->addIncoming(EndPhi, Pred);
251 }
252
253 EndPhi->addIncoming(SIOp1, StartBlock);
254 EndPhi->addIncoming(NewPhi, NewBlock);
255 SIUse->replaceUsesOfWith(SI, EndPhi);
256 SIUse = EndPhi;
257 }
258
259 if (auto *OpSi = dyn_cast<SelectInst>(SIOp1))
260 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, SIUse));
261 if (auto *OpSi = dyn_cast<SelectInst>(SIOp2))
262 NewSIsToUnfold->push_back(SelectInstToUnfold(OpSi, NewPhi));
263
264 // Insert the real conditional branch based on the original condition.
265 StartBlockTerm->eraseFromParent();
266 auto *BI =
267 BranchInst::Create(EndBlock, NewBlock, SI->getCondition(), StartBlock);
269 BI->setMetadata(LLVMContext::MD_prof,
270 SI->getMetadata(LLVMContext::MD_prof));
271 DTU->applyUpdates({{DominatorTree::Insert, StartBlock, EndBlock},
272 {DominatorTree::Insert, StartBlock, NewBlock}});
273 } else {
274 BasicBlock *EndBlock = SIUse->getParent();
275 BasicBlock *NewBlockT = BasicBlock::Create(
276 SI->getContext(), Twine(SI->getName(), ".si.unfold.true"),
277 EndBlock->getParent(), EndBlock);
278 BasicBlock *NewBlockF = BasicBlock::Create(
279 SI->getContext(), Twine(SI->getName(), ".si.unfold.false"),
280 EndBlock->getParent(), EndBlock);
281
282 NewBBs->push_back(NewBlockT);
283 NewBBs->push_back(NewBlockF);
284
285 // Def only has one use in EndBlock.
286 // Before transformation:
287 // StartBlock(Def)
288 // | \
289 // EndBlock OtherBlock
290 // (Use)
291 //
292 // After transformation:
293 // StartBlock(Def)
294 // | \
295 // | OtherBlock
296 // NewBlockT
297 // | \
298 // | NewBlockF
299 // | /
300 // | /
301 // EndBlock
302 // (Use)
303 BranchInst::Create(EndBlock, NewBlockF);
304 // Insert the real conditional branch based on the original condition.
305 auto *BI =
306 BranchInst::Create(EndBlock, NewBlockF, SI->getCondition(), NewBlockT);
308 BI->setMetadata(LLVMContext::MD_prof,
309 SI->getMetadata(LLVMContext::MD_prof));
310 DTU->applyUpdates({{DominatorTree::Insert, NewBlockT, NewBlockF},
311 {DominatorTree::Insert, NewBlockT, EndBlock},
312 {DominatorTree::Insert, NewBlockF, EndBlock}});
313
314 Value *TrueVal = SI->getTrueValue();
315 Value *FalseVal = SI->getFalseValue();
316
317 PHINode *NewPhiT = PHINode::Create(
318 SIUse->getType(), 1, Twine(TrueVal->getName(), ".si.unfold.phi"),
319 NewBlockT->getFirstInsertionPt());
320 PHINode *NewPhiF = PHINode::Create(
321 SIUse->getType(), 1, Twine(FalseVal->getName(), ".si.unfold.phi"),
322 NewBlockF->getFirstInsertionPt());
323 NewPhiT->addIncoming(TrueVal, StartBlock);
324 NewPhiF->addIncoming(FalseVal, NewBlockT);
325
326 if (auto *TrueSI = dyn_cast<SelectInst>(TrueVal))
327 NewSIsToUnfold->push_back(SelectInstToUnfold(TrueSI, NewPhiT));
328 if (auto *FalseSi = dyn_cast<SelectInst>(FalseVal))
329 NewSIsToUnfold->push_back(SelectInstToUnfold(FalseSi, NewPhiF));
330
331 SIUse->addIncoming(NewPhiT, NewBlockT);
332 SIUse->addIncoming(NewPhiF, NewBlockF);
333 SIUse->removeIncomingValue(StartBlock);
334
335 // Update any other PHI nodes in EndBlock.
336 for (PHINode &Phi : EndBlock->phis()) {
337 if (SIUse == &Phi)
338 continue;
339 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockT);
340 Phi.addIncoming(Phi.getIncomingValueForBlock(StartBlock), NewBlockF);
341 Phi.removeIncomingValue(StartBlock);
342 }
343
344 // Update the appropriate successor of the start block to point to the new
345 // unfolded block.
346 unsigned SuccNum = StartBlockTerm->getSuccessor(1) == EndBlock ? 1 : 0;
347 StartBlockTerm->setSuccessor(SuccNum, NewBlockT);
348 DTU->applyUpdates({{DominatorTree::Delete, StartBlock, EndBlock},
349 {DominatorTree::Insert, StartBlock, NewBlockT}});
350 }
351
352 // Preserve loop info
353 if (Loop *L = LI->getLoopFor(StartBlock)) {
354 for (BasicBlock *NewBB : *NewBBs)
355 L->addBasicBlockToLoop(NewBB, *LI);
356 }
357
358 // The select is now dead.
359 assert(SI->use_empty() && "Select must be dead now");
360 SI->eraseFromParent();
361}
362
363namespace {
364struct ClonedBlock {
365 BasicBlock *BB;
366 APInt State; ///< \p State corresponds to the next value of a switch stmnt.
367};
368} // namespace
369
370typedef std::deque<BasicBlock *> PathType;
371typedef std::vector<PathType> PathsType;
373typedef std::vector<ClonedBlock> CloneList;
374
375// This data structure keeps track of all blocks that have been cloned. If two
376// different ThreadingPaths clone the same block for a certain state it should
377// be reused, and it can be looked up in this map.
379
380// This map keeps track of all the new definitions for an instruction. This
381// information is needed when restoring SSA form after cloning blocks.
383
384inline raw_ostream &operator<<(raw_ostream &OS, const PathType &Path) {
385 OS << "< ";
386 for (const BasicBlock *BB : Path) {
387 std::string BBName;
388 if (BB->hasName())
389 raw_string_ostream(BBName) << BB->getName();
390 else
391 raw_string_ostream(BBName) << BB;
392 OS << BBName << " ";
393 }
394 OS << ">";
395 return OS;
396}
397
398namespace {
399/// ThreadingPath is a path in the control flow of a loop that can be threaded
400/// by cloning necessary basic blocks and replacing conditional branches with
401/// unconditional ones. A threading path includes a list of basic blocks, the
402/// exit state, and the block that determines the next state.
403struct ThreadingPath {
404 /// Exit value is DFA's exit state for the given path.
405 APInt getExitValue() const { return ExitVal; }
406 void setExitValue(const ConstantInt *V) {
407 ExitVal = V->getValue();
408 IsExitValSet = true;
409 }
410 bool isExitValueSet() const { return IsExitValSet; }
411
412 /// Determinator is the basic block that determines the next state of the DFA.
413 const BasicBlock *getDeterminatorBB() const { return DBB; }
414 void setDeterminator(const BasicBlock *BB) { DBB = BB; }
415
416 /// Path is a list of basic blocks.
417 const PathType &getPath() const { return Path; }
418 void setPath(const PathType &NewPath) { Path = NewPath; }
419 void push_back(BasicBlock *BB) { Path.push_back(BB); }
420 void push_front(BasicBlock *BB) { Path.push_front(BB); }
421 void appendExcludingFirst(const PathType &OtherPath) {
422 llvm::append_range(Path, llvm::drop_begin(OtherPath));
423 }
424
425 void print(raw_ostream &OS) const {
426 OS << Path << " [ " << ExitVal << ", " << DBB->getName() << " ]";
427 }
428
429private:
430 PathType Path;
431 APInt ExitVal;
432 const BasicBlock *DBB = nullptr;
433 bool IsExitValSet = false;
434};
435
436#ifndef NDEBUG
437inline raw_ostream &operator<<(raw_ostream &OS, const ThreadingPath &TPath) {
438 TPath.print(OS);
439 return OS;
440}
441#endif
442
443struct MainSwitch {
444 MainSwitch(SwitchInst *SI, LoopInfo *LI, OptimizationRemarkEmitter *ORE)
445 : LI(LI) {
446 if (isCandidate(SI)) {
447 Instr = SI;
448 } else {
449 ORE->emit([&]() {
450 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable", SI)
451 << "Switch instruction is not predictable.";
452 });
453 }
454 }
455
456 virtual ~MainSwitch() = default;
457
458 SwitchInst *getInstr() const { return Instr; }
459 const SmallVector<SelectInstToUnfold, 4> getSelectInsts() {
460 return SelectInsts;
461 }
462
463private:
464 /// Do a use-def chain traversal starting from the switch condition to see if
465 /// \p SI is a potential condidate.
466 ///
467 /// Also, collect select instructions to unfold.
468 bool isCandidate(const SwitchInst *SI) {
469 std::deque<std::pair<Value *, BasicBlock *>> Q;
470 SmallPtrSet<Value *, 16> SeenValues;
471 SelectInsts.clear();
472
473 Value *SICond = SI->getCondition();
474 LLVM_DEBUG(dbgs() << "\tSICond: " << *SICond << "\n");
475 if (!isa<PHINode>(SICond))
476 return false;
477
478 // The switch must be in a loop.
479 const Loop *L = LI->getLoopFor(SI->getParent());
480 if (!L)
481 return false;
482
483 addToQueue(SICond, nullptr, Q, SeenValues);
484
485 while (!Q.empty()) {
486 Value *Current = Q.front().first;
487 BasicBlock *CurrentIncomingBB = Q.front().second;
488 Q.pop_front();
489
490 if (auto *Phi = dyn_cast<PHINode>(Current)) {
491 for (BasicBlock *IncomingBB : Phi->blocks()) {
492 Value *Incoming = Phi->getIncomingValueForBlock(IncomingBB);
493 addToQueue(Incoming, IncomingBB, Q, SeenValues);
494 }
495 LLVM_DEBUG(dbgs() << "\tphi: " << *Phi << "\n");
496 } else if (SelectInst *SelI = dyn_cast<SelectInst>(Current)) {
497 if (!isValidSelectInst(SelI))
498 return false;
499 addToQueue(SelI->getTrueValue(), CurrentIncomingBB, Q, SeenValues);
500 addToQueue(SelI->getFalseValue(), CurrentIncomingBB, Q, SeenValues);
501 LLVM_DEBUG(dbgs() << "\tselect: " << *SelI << "\n");
502 if (auto *SelIUse = dyn_cast<PHINode>(SelI->user_back()))
503 SelectInsts.push_back(SelectInstToUnfold(SelI, SelIUse));
504 } else if (isa<Constant>(Current)) {
505 LLVM_DEBUG(dbgs() << "\tconst: " << *Current << "\n");
506 continue;
507 } else {
508 LLVM_DEBUG(dbgs() << "\tother: " << *Current << "\n");
509 // Allow unpredictable values. The hope is that those will be the
510 // initial switch values that can be ignored (they will hit the
511 // unthreaded switch) but this assumption will get checked later after
512 // paths have been enumerated (in function getStateDefMap).
513
514 // If the unpredictable value comes from the same inner loop it is
515 // likely that it will also be on the enumerated paths, causing us to
516 // exit after we have enumerated all the paths. This heuristic save
517 // compile time because a search for all the paths can become expensive.
518 if (EarlyExitHeuristic &&
519 L->contains(LI->getLoopFor(CurrentIncomingBB))) {
521 << "\tExiting early due to unpredictability heuristic.\n");
522 return false;
523 }
524
525 continue;
526 }
527 }
528
529 return true;
530 }
531
532 void addToQueue(Value *Val, BasicBlock *BB,
533 std::deque<std::pair<Value *, BasicBlock *>> &Q,
534 SmallPtrSet<Value *, 16> &SeenValues) {
535 if (SeenValues.insert(Val).second)
536 Q.push_back({Val, BB});
537 }
538
539 bool isValidSelectInst(SelectInst *SI) {
540 if (!SI->hasOneUse())
541 return false;
542
543 Instruction *SIUse = dyn_cast<Instruction>(SI->user_back());
544 // The use of the select inst should be either a phi or another select.
545 if (!SIUse || !(isa<PHINode>(SIUse) || isa<SelectInst>(SIUse)))
546 return false;
547
548 BasicBlock *SIBB = SI->getParent();
549
550 // Currently, we can only expand select instructions in basic blocks with
551 // one successor.
552 BranchInst *SITerm = dyn_cast<BranchInst>(SIBB->getTerminator());
553 if (!SITerm || !SITerm->isUnconditional())
554 return false;
555
556 // Only fold the select coming from directly where it is defined.
557 // TODO: We have dealt with the select coming indirectly now. This
558 // constraint can be relaxed.
559 PHINode *PHIUser = dyn_cast<PHINode>(SIUse);
560 if (PHIUser && PHIUser->getIncomingBlock(*SI->use_begin()) != SIBB)
561 return false;
562
563 // If select will not be sunk during unfolding, and it is in the same basic
564 // block as another state defining select, then cannot unfold both.
565 for (SelectInstToUnfold SIToUnfold : SelectInsts) {
566 SelectInst *PrevSI = SIToUnfold.getInst();
567 if (PrevSI->getTrueValue() != SI && PrevSI->getFalseValue() != SI &&
568 PrevSI->getParent() == SI->getParent())
569 return false;
570 }
571
572 return true;
573 }
574
575 LoopInfo *LI;
576 SwitchInst *Instr = nullptr;
578};
579
580struct AllSwitchPaths {
581 AllSwitchPaths(const MainSwitch *MSwitch, OptimizationRemarkEmitter *ORE,
582 LoopInfo *LI, Loop *L)
583 : Switch(MSwitch->getInstr()), SwitchBlock(Switch->getParent()), ORE(ORE),
584 LI(LI), SwitchOuterLoop(L) {}
585
586 std::vector<ThreadingPath> &getThreadingPaths() { return TPaths; }
587 unsigned getNumThreadingPaths() { return TPaths.size(); }
588 SwitchInst *getSwitchInst() { return Switch; }
589 BasicBlock *getSwitchBlock() { return SwitchBlock; }
590
591 void run() {
592 StateDefMap StateDef = getStateDefMap();
593 if (StateDef.empty()) {
594 ORE->emit([&]() {
595 return OptimizationRemarkMissed(DEBUG_TYPE, "SwitchNotPredictable",
596 Switch)
597 << "Switch instruction is not predictable.";
598 });
599 return;
600 }
601
602 auto *SwitchPhi = cast<PHINode>(Switch->getOperand(0));
603 auto *SwitchPhiDefBB = SwitchPhi->getParent();
604 VisitedBlocks VB;
605 // Get paths from the determinator BBs to SwitchPhiDefBB
606 std::vector<ThreadingPath> PathsToPhiDef =
607 getPathsFromStateDefMap(StateDef, SwitchPhi, VB, MaxNumPaths);
608 if (SwitchPhiDefBB == SwitchBlock || PathsToPhiDef.empty()) {
609 TPaths = std::move(PathsToPhiDef);
610 return;
611 }
612
613 assert(MaxNumPaths >= PathsToPhiDef.size() && !PathsToPhiDef.empty());
614 auto PathsLimit = MaxNumPaths / PathsToPhiDef.size();
615 // Find and append paths from SwitchPhiDefBB to SwitchBlock.
616 PathsType PathsToSwitchBB =
617 paths(SwitchPhiDefBB, SwitchBlock, VB, /* PathDepth = */ 1, PathsLimit);
618 if (PathsToSwitchBB.empty())
619 return;
620
621 std::vector<ThreadingPath> TempList;
622 for (const ThreadingPath &Path : PathsToPhiDef) {
623 for (const PathType &PathToSw : PathsToSwitchBB) {
624 ThreadingPath PathCopy(Path);
625 PathCopy.appendExcludingFirst(PathToSw);
626 TempList.push_back(PathCopy);
627 }
628 }
629 TPaths = std::move(TempList);
630 }
631
632private:
633 // Value: an instruction that defines a switch state;
634 // Key: the parent basic block of that instruction.
635 typedef DenseMap<const BasicBlock *, const PHINode *> StateDefMap;
636 std::vector<ThreadingPath> getPathsFromStateDefMap(StateDefMap &StateDef,
637 PHINode *Phi,
638 VisitedBlocks &VB,
639 unsigned PathsLimit) {
640 std::vector<ThreadingPath> Res;
641 auto *PhiBB = Phi->getParent();
642 VB.insert(PhiBB);
643
644 VisitedBlocks UniqueBlocks;
645 for (auto *IncomingBB : Phi->blocks()) {
646 if (Res.size() >= PathsLimit)
647 break;
648 if (!UniqueBlocks.insert(IncomingBB).second)
649 continue;
650 if (!SwitchOuterLoop->contains(IncomingBB))
651 continue;
652
653 Value *IncomingValue = Phi->getIncomingValueForBlock(IncomingBB);
654 // We found the determinator. This is the start of our path.
655 if (auto *C = dyn_cast<ConstantInt>(IncomingValue)) {
656 // SwitchBlock is the determinator, unsupported unless its also the def.
657 if (PhiBB == SwitchBlock &&
658 SwitchBlock != cast<PHINode>(Switch->getOperand(0))->getParent())
659 continue;
660 ThreadingPath NewPath;
661 NewPath.setDeterminator(PhiBB);
662 NewPath.setExitValue(C);
663 // Don't add SwitchBlock at the start, this is handled later.
664 if (IncomingBB != SwitchBlock)
665 NewPath.push_back(IncomingBB);
666 NewPath.push_back(PhiBB);
667 Res.push_back(NewPath);
668 continue;
669 }
670 // Don't get into a cycle.
671 if (VB.contains(IncomingBB) || IncomingBB == SwitchBlock)
672 continue;
673 // Recurse up the PHI chain.
674 auto *IncomingPhi = dyn_cast<PHINode>(IncomingValue);
675 if (!IncomingPhi)
676 continue;
677 auto *IncomingPhiDefBB = IncomingPhi->getParent();
678 if (!StateDef.contains(IncomingPhiDefBB))
679 continue;
680
681 // Direct predecessor, just add to the path.
682 if (IncomingPhiDefBB == IncomingBB) {
683 assert(PathsLimit > Res.size());
684 std::vector<ThreadingPath> PredPaths = getPathsFromStateDefMap(
685 StateDef, IncomingPhi, VB, PathsLimit - Res.size());
686 for (ThreadingPath &Path : PredPaths) {
687 Path.push_back(PhiBB);
688 Res.push_back(std::move(Path));
689 }
690 continue;
691 }
692 // Not a direct predecessor, find intermediate paths to append to the
693 // existing path.
694 if (VB.contains(IncomingPhiDefBB))
695 continue;
696
697 PathsType IntermediatePaths;
698 assert(PathsLimit > Res.size());
699 auto InterPathLimit = PathsLimit - Res.size();
700 IntermediatePaths = paths(IncomingPhiDefBB, IncomingBB, VB,
701 /* PathDepth = */ 1, InterPathLimit);
702 if (IntermediatePaths.empty())
703 continue;
704
705 assert(InterPathLimit >= IntermediatePaths.size());
706 auto PredPathLimit = InterPathLimit / IntermediatePaths.size();
707 std::vector<ThreadingPath> PredPaths =
708 getPathsFromStateDefMap(StateDef, IncomingPhi, VB, PredPathLimit);
709 for (const ThreadingPath &Path : PredPaths) {
710 for (const PathType &IPath : IntermediatePaths) {
711 ThreadingPath NewPath(Path);
712 NewPath.appendExcludingFirst(IPath);
713 NewPath.push_back(PhiBB);
714 Res.push_back(NewPath);
715 }
716 }
717 }
718 VB.erase(PhiBB);
719 return Res;
720 }
721
722 PathsType paths(BasicBlock *BB, BasicBlock *ToBB, VisitedBlocks &Visited,
723 unsigned PathDepth, unsigned PathsLimit) {
724 PathsType Res;
725
726 // Stop exploring paths after visiting MaxPathLength blocks
727 if (PathDepth > MaxPathLength) {
728 ORE->emit([&]() {
729 return OptimizationRemarkAnalysis(DEBUG_TYPE, "MaxPathLengthReached",
730 Switch)
731 << "Exploration stopped after visiting MaxPathLength="
732 << ore::NV("MaxPathLength", MaxPathLength) << " blocks.";
733 });
734 return Res;
735 }
736
737 Visited.insert(BB);
738 if (++NumVisited > MaxNumVisitiedPaths)
739 return Res;
740
741 // Stop if we have reached the BB out of loop, since its successors have no
742 // impact on the DFA.
743 if (!SwitchOuterLoop->contains(BB))
744 return Res;
745
746 // Some blocks have multiple edges to the same successor, and this set
747 // is used to prevent a duplicate path from being generated
748 SmallPtrSet<BasicBlock *, 4> Successors;
749 for (BasicBlock *Succ : successors(BB)) {
750 if (Res.size() >= PathsLimit)
751 break;
752 if (!Successors.insert(Succ).second)
753 continue;
754
755 // Found a cycle through the final block.
756 if (Succ == ToBB) {
757 Res.push_back({BB, ToBB});
758 continue;
759 }
760
761 // We have encountered a cycle, do not get caught in it
762 if (Visited.contains(Succ))
763 continue;
764
765 auto *CurrLoop = LI->getLoopFor(BB);
766 // Unlikely to be beneficial.
767 if (Succ == CurrLoop->getHeader())
768 continue;
769 // Skip for now, revisit this condition later to see the impact on
770 // coverage and compile time.
771 if (LI->getLoopFor(Succ) != CurrLoop)
772 continue;
773 assert(PathsLimit > Res.size());
774 PathsType SuccPaths =
775 paths(Succ, ToBB, Visited, PathDepth + 1, PathsLimit - Res.size());
776 for (PathType &Path : SuccPaths) {
777 Path.push_front(BB);
778 Res.push_back(Path);
779 }
780 }
781 // This block could now be visited again from a different predecessor. Note
782 // that this will result in exponential runtime. Subpaths could possibly be
783 // cached but it takes a lot of memory to store them.
784 Visited.erase(BB);
785 return Res;
786 }
787
788 /// Walk the use-def chain and collect all the state-defining blocks and the
789 /// PHI nodes in those blocks that define the state.
790 StateDefMap getStateDefMap() const {
791 StateDefMap Res;
792 PHINode *FirstDef = dyn_cast<PHINode>(Switch->getOperand(0));
793 assert(FirstDef && "The first definition must be a phi.");
794
796 Stack.push_back(FirstDef);
797 SmallPtrSet<Value *, 16> SeenValues;
798
799 while (!Stack.empty()) {
800 PHINode *CurPhi = Stack.pop_back_val();
801
802 Res[CurPhi->getParent()] = CurPhi;
803 SeenValues.insert(CurPhi);
804
805 for (BasicBlock *IncomingBB : CurPhi->blocks()) {
806 PHINode *IncomingPhi =
807 dyn_cast<PHINode>(CurPhi->getIncomingValueForBlock(IncomingBB));
808 if (!IncomingPhi)
809 continue;
810 bool IsOutsideLoops = !SwitchOuterLoop->contains(IncomingBB);
811 if (SeenValues.contains(IncomingPhi) || IsOutsideLoops)
812 continue;
813
814 Stack.push_back(IncomingPhi);
815 }
816 }
817
818 return Res;
819 }
820
821 unsigned NumVisited = 0;
822 SwitchInst *Switch;
823 BasicBlock *SwitchBlock;
824 OptimizationRemarkEmitter *ORE;
825 std::vector<ThreadingPath> TPaths;
826 LoopInfo *LI;
827 Loop *SwitchOuterLoop;
828};
829
830struct TransformDFA {
831 TransformDFA(AllSwitchPaths *SwitchPaths, DominatorTree *DT,
832 AssumptionCache *AC, TargetTransformInfo *TTI,
833 OptimizationRemarkEmitter *ORE,
834 SmallPtrSet<const Value *, 32> EphValues)
835 : SwitchPaths(SwitchPaths), DT(DT), AC(AC), TTI(TTI), ORE(ORE),
836 EphValues(EphValues) {}
837
838 bool run() {
839 if (isLegalAndProfitableToTransform()) {
840 createAllExitPaths();
841 NumTransforms++;
842 return true;
843 }
844 return false;
845 }
846
847private:
848 /// This function performs both a legality check and profitability check at
849 /// the same time since it is convenient to do so. It iterates through all
850 /// blocks that will be cloned, and keeps track of the duplication cost. It
851 /// also returns false if it is illegal to clone some required block.
852 bool isLegalAndProfitableToTransform() {
853 CodeMetrics Metrics;
854 uint64_t NumClonedInst = 0;
855 SwitchInst *Switch = SwitchPaths->getSwitchInst();
856
857 // Don't thread switch without multiple successors.
858 if (Switch->getNumSuccessors() <= 1)
859 return false;
860
861 // Note that DuplicateBlockMap is not being used as intended here. It is
862 // just being used to ensure (BB, State) pairs are only counted once.
863 DuplicateBlockMap DuplicateMap;
864 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
865 PathType PathBBs = TPath.getPath();
866 APInt NextState = TPath.getExitValue();
867 const BasicBlock *Determinator = TPath.getDeterminatorBB();
868
869 // Update Metrics for the Switch block, this is always cloned
870 BasicBlock *BB = SwitchPaths->getSwitchBlock();
871 BasicBlock *VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
872 if (!VisitedBB) {
873 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
874 NumClonedInst += BB->sizeWithoutDebug();
875 DuplicateMap[BB].push_back({BB, NextState});
876 }
877
878 // If the Switch block is the Determinator, then we can continue since
879 // this is the only block that is cloned and we already counted for it.
880 if (PathBBs.front() == Determinator)
881 continue;
882
883 // Otherwise update Metrics for all blocks that will be cloned. If any
884 // block is already cloned and would be reused, don't double count it.
885 auto DetIt = llvm::find(PathBBs, Determinator);
886 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
887 BB = *BBIt;
888 VisitedBB = getClonedBB(BB, NextState, DuplicateMap);
889 if (VisitedBB)
890 continue;
891 Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
892 NumClonedInst += BB->sizeWithoutDebug();
893 DuplicateMap[BB].push_back({BB, NextState});
894 }
895
896 if (Metrics.notDuplicatable) {
897 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
898 << "non-duplicatable instructions.\n");
899 ORE->emit([&]() {
900 return OptimizationRemarkMissed(DEBUG_TYPE, "NonDuplicatableInst",
901 Switch)
902 << "Contains non-duplicatable instructions.";
903 });
904 return false;
905 }
906
907 // FIXME: Allow jump threading with controlled convergence.
908 if (Metrics.Convergence != ConvergenceKind::None) {
909 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
910 << "convergent instructions.\n");
911 ORE->emit([&]() {
912 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
913 << "Contains convergent instructions.";
914 });
915 return false;
916 }
917
918 if (!Metrics.NumInsts.isValid()) {
919 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, contains "
920 << "instructions with invalid cost.\n");
921 ORE->emit([&]() {
922 return OptimizationRemarkMissed(DEBUG_TYPE, "ConvergentInst", Switch)
923 << "Contains instructions with invalid cost.";
924 });
925 return false;
926 }
927 }
928
929 // Too much cloned instructions slow down later optimizations, especially
930 // SLPVectorizer.
931 // TODO: Thread the switch partially before reaching the threshold.
932 uint64_t NumOrigInst = 0;
933 for (auto *BB : DuplicateMap.keys())
934 NumOrigInst += BB->sizeWithoutDebug();
935 if (double(NumClonedInst) / double(NumOrigInst) > MaxClonedRate) {
936 LLVM_DEBUG(dbgs() << "DFA Jump Threading: Not jump threading, too much "
937 "instructions wll be cloned\n");
938 ORE->emit([&]() {
939 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
940 << "Too much instructions will be cloned.";
941 });
942 return false;
943 }
944
945 InstructionCost DuplicationCost = 0;
946
947 unsigned JumpTableSize = 0;
948 TTI->getEstimatedNumberOfCaseClusters(*Switch, JumpTableSize, nullptr,
949 nullptr);
950 if (JumpTableSize == 0) {
951 // Factor in the number of conditional branches reduced from jump
952 // threading. Assume that lowering the switch block is implemented by
953 // using binary search, hence the LogBase2().
954 unsigned CondBranches =
955 APInt(32, Switch->getNumSuccessors()).ceilLogBase2();
956 assert(CondBranches > 0 &&
957 "The threaded switch must have multiple branches");
958 DuplicationCost = Metrics.NumInsts / CondBranches;
959 } else {
960 // Compared with jump tables, the DFA optimizer removes an indirect branch
961 // on each loop iteration, thus making branch prediction more precise. The
962 // more branch targets there are, the more likely it is for the branch
963 // predictor to make a mistake, and the more benefit there is in the DFA
964 // optimizer. Thus, the more branch targets there are, the lower is the
965 // cost of the DFA opt.
966 DuplicationCost = Metrics.NumInsts / JumpTableSize;
967 }
968
969 LLVM_DEBUG(dbgs() << "\nDFA Jump Threading: Cost to jump thread block "
970 << SwitchPaths->getSwitchBlock()->getName()
971 << " is: " << DuplicationCost << "\n\n");
972
973 if (DuplicationCost > CostThreshold) {
974 LLVM_DEBUG(dbgs() << "Not jump threading, duplication cost exceeds the "
975 << "cost threshold.\n");
976 ORE->emit([&]() {
977 return OptimizationRemarkMissed(DEBUG_TYPE, "NotProfitable", Switch)
978 << "Duplication cost exceeds the cost threshold (cost="
979 << ore::NV("Cost", DuplicationCost)
980 << ", threshold=" << ore::NV("Threshold", CostThreshold) << ").";
981 });
982 return false;
983 }
984
985 ORE->emit([&]() {
986 return OptimizationRemark(DEBUG_TYPE, "JumpThreaded", Switch)
987 << "Switch statement jump-threaded.";
988 });
989
990 return true;
991 }
992
993 /// Transform each threading path to effectively jump thread the DFA.
994 void createAllExitPaths() {
995 // Move the switch block to the end of the path, since it will be duplicated
996 BasicBlock *SwitchBlock = SwitchPaths->getSwitchBlock();
997 for (ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
998 LLVM_DEBUG(dbgs() << TPath << "\n");
999 // TODO: Fix exit path creation logic so that we dont need this
1000 // placeholder.
1001 TPath.push_front(SwitchBlock);
1002 }
1003
1004 // Transform the ThreadingPaths and keep track of the cloned values
1005 DuplicateBlockMap DuplicateMap;
1006 DefMap NewDefs;
1007
1008 SmallPtrSet<BasicBlock *, 16> BlocksToClean;
1009 BlocksToClean.insert_range(successors(SwitchBlock));
1010
1011 {
1012 DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy);
1013 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths()) {
1014 createExitPath(NewDefs, TPath, DuplicateMap, BlocksToClean, &DTU);
1015 NumPaths++;
1016 }
1017
1018 // After all paths are cloned, now update the last successor of the cloned
1019 // path so it skips over the switch statement
1020 for (const ThreadingPath &TPath : SwitchPaths->getThreadingPaths())
1021 updateLastSuccessor(TPath, DuplicateMap, &DTU);
1022 }
1023
1024 // For each instruction that was cloned and used outside, update its uses
1025 updateSSA(NewDefs);
1026
1027 // Clean PHI Nodes for the newly created blocks
1028 for (BasicBlock *BB : BlocksToClean)
1029 cleanPhiNodes(BB);
1030 }
1031
1032 /// For a specific ThreadingPath \p Path, create an exit path starting from
1033 /// the determinator block.
1034 ///
1035 /// To remember the correct destination, we have to duplicate blocks
1036 /// corresponding to each state. Also update the terminating instruction of
1037 /// the predecessors, and phis in the successor blocks.
1038 void createExitPath(DefMap &NewDefs, const ThreadingPath &Path,
1039 DuplicateBlockMap &DuplicateMap,
1040 SmallPtrSet<BasicBlock *, 16> &BlocksToClean,
1041 DomTreeUpdater *DTU) {
1042 APInt NextState = Path.getExitValue();
1043 const BasicBlock *Determinator = Path.getDeterminatorBB();
1044 PathType PathBBs = Path.getPath();
1045
1046 // Don't select the placeholder block in front
1047 if (PathBBs.front() == Determinator)
1048 PathBBs.pop_front();
1049
1050 auto DetIt = llvm::find(PathBBs, Determinator);
1051 // When there is only one BB in PathBBs, the determinator takes itself as a
1052 // direct predecessor.
1053 BasicBlock *PrevBB = PathBBs.size() == 1 ? *DetIt : *std::prev(DetIt);
1054 for (auto BBIt = DetIt; BBIt != PathBBs.end(); BBIt++) {
1055 BasicBlock *BB = *BBIt;
1056 BlocksToClean.insert(BB);
1057
1058 // We already cloned BB for this NextState, now just update the branch
1059 // and continue.
1060 BasicBlock *NextBB = getClonedBB(BB, NextState, DuplicateMap);
1061 if (NextBB) {
1062 updatePredecessor(PrevBB, BB, NextBB, DTU);
1063 PrevBB = NextBB;
1064 continue;
1065 }
1066
1067 // Clone the BB and update the successor of Prev to jump to the new block
1068 BasicBlock *NewBB = cloneBlockAndUpdatePredecessor(
1069 BB, PrevBB, NextState, DuplicateMap, NewDefs, DTU);
1070 DuplicateMap[BB].push_back({NewBB, NextState});
1071 BlocksToClean.insert(NewBB);
1072 PrevBB = NewBB;
1073 }
1074 }
1075
1076 /// Restore SSA form after cloning blocks.
1077 ///
1078 /// Each cloned block creates new defs for a variable, and the uses need to be
1079 /// updated to reflect this. The uses may be replaced with a cloned value, or
1080 /// some derived phi instruction. Note that all uses of a value defined in the
1081 /// same block were already remapped when cloning the block.
1082 void updateSSA(DefMap &NewDefs) {
1083 SSAUpdaterBulk SSAUpdate;
1084 SmallVector<Use *, 16> UsesToRename;
1085
1086 for (const auto &KV : NewDefs) {
1087 Instruction *I = KV.first;
1088 BasicBlock *BB = I->getParent();
1089 std::vector<Instruction *> Cloned = KV.second;
1090
1091 // Scan all uses of this instruction to see if it is used outside of its
1092 // block, and if so, record them in UsesToRename.
1093 for (Use &U : I->uses()) {
1094 Instruction *User = cast<Instruction>(U.getUser());
1095 if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
1096 if (UserPN->getIncomingBlock(U) == BB)
1097 continue;
1098 } else if (User->getParent() == BB) {
1099 continue;
1100 }
1101
1102 UsesToRename.push_back(&U);
1103 }
1104
1105 // If there are no uses outside the block, we're done with this
1106 // instruction.
1107 if (UsesToRename.empty())
1108 continue;
1109 LLVM_DEBUG(dbgs() << "DFA-JT: Renaming non-local uses of: " << *I
1110 << "\n");
1111
1112 // We found a use of I outside of BB. Rename all uses of I that are
1113 // outside its block to be uses of the appropriate PHI node etc. See
1114 // ValuesInBlocks with the values we know.
1115 unsigned VarNum = SSAUpdate.AddVariable(I->getName(), I->getType());
1116 SSAUpdate.AddAvailableValue(VarNum, BB, I);
1117 for (Instruction *New : Cloned)
1118 SSAUpdate.AddAvailableValue(VarNum, New->getParent(), New);
1119
1120 while (!UsesToRename.empty())
1121 SSAUpdate.AddUse(VarNum, UsesToRename.pop_back_val());
1122
1123 LLVM_DEBUG(dbgs() << "\n");
1124 }
1125 // SSAUpdater handles phi placement and renaming uses with the appropriate
1126 // value.
1127 SSAUpdate.RewriteAllUses(DT);
1128 }
1129
1130 /// Clones a basic block, and adds it to the CFG.
1131 ///
1132 /// This function also includes updating phi nodes in the successors of the
1133 /// BB, and remapping uses that were defined locally in the cloned BB.
1134 BasicBlock *cloneBlockAndUpdatePredecessor(BasicBlock *BB, BasicBlock *PrevBB,
1135 const APInt &NextState,
1136 DuplicateBlockMap &DuplicateMap,
1137 DefMap &NewDefs,
1138 DomTreeUpdater *DTU) {
1139 ValueToValueMapTy VMap;
1140 BasicBlock *NewBB = CloneBasicBlock(
1141 BB, VMap, ".jt" + std::to_string(NextState.getLimitedValue()),
1142 BB->getParent());
1143 NewBB->moveAfter(BB);
1144 NumCloned++;
1145
1146 for (Instruction &I : *NewBB) {
1147 // Do not remap operands of PHINode in case a definition in BB is an
1148 // incoming value to a phi in the same block. This incoming value will
1149 // be renamed later while restoring SSA.
1150 if (isa<PHINode>(&I))
1151 continue;
1152 RemapInstruction(&I, VMap,
1154 if (AssumeInst *II = dyn_cast<AssumeInst>(&I))
1156 }
1157
1158 updateSuccessorPhis(BB, NewBB, NextState, VMap, DuplicateMap);
1159 updatePredecessor(PrevBB, BB, NewBB, DTU);
1160 updateDefMap(NewDefs, VMap);
1161
1162 // Add all successors to the DominatorTree
1163 SmallPtrSet<BasicBlock *, 4> SuccSet;
1164 for (auto *SuccBB : successors(NewBB)) {
1165 if (SuccSet.insert(SuccBB).second)
1166 DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}});
1167 }
1168 SuccSet.clear();
1169 return NewBB;
1170 }
1171
1172 /// Update the phi nodes in BB's successors.
1173 ///
1174 /// This means creating a new incoming value from NewBB with the new
1175 /// instruction wherever there is an incoming value from BB.
1176 void updateSuccessorPhis(BasicBlock *BB, BasicBlock *ClonedBB,
1177 const APInt &NextState, ValueToValueMapTy &VMap,
1178 DuplicateBlockMap &DuplicateMap) {
1179 std::vector<BasicBlock *> BlocksToUpdate;
1180
1181 // If BB is the last block in the path, we can simply update the one case
1182 // successor that will be reached.
1183 if (BB == SwitchPaths->getSwitchBlock()) {
1184 SwitchInst *Switch = SwitchPaths->getSwitchInst();
1185 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1186 BlocksToUpdate.push_back(NextCase);
1187 BasicBlock *ClonedSucc = getClonedBB(NextCase, NextState, DuplicateMap);
1188 if (ClonedSucc)
1189 BlocksToUpdate.push_back(ClonedSucc);
1190 }
1191 // Otherwise update phis in all successors.
1192 else {
1193 for (BasicBlock *Succ : successors(BB)) {
1194 BlocksToUpdate.push_back(Succ);
1195
1196 // Check if a successor has already been cloned for the particular exit
1197 // value. In this case if a successor was already cloned, the phi nodes
1198 // in the cloned block should be updated directly.
1199 BasicBlock *ClonedSucc = getClonedBB(Succ, NextState, DuplicateMap);
1200 if (ClonedSucc)
1201 BlocksToUpdate.push_back(ClonedSucc);
1202 }
1203 }
1204
1205 // If there is a phi with an incoming value from BB, create a new incoming
1206 // value for the new predecessor ClonedBB. The value will either be the same
1207 // value from BB or a cloned value.
1208 for (BasicBlock *Succ : BlocksToUpdate) {
1209 for (PHINode &Phi : Succ->phis()) {
1210 Value *Incoming = Phi.getIncomingValueForBlock(BB);
1211 if (Incoming) {
1212 if (isa<Constant>(Incoming)) {
1213 Phi.addIncoming(Incoming, ClonedBB);
1214 continue;
1215 }
1216 Value *ClonedVal = VMap[Incoming];
1217 if (ClonedVal)
1218 Phi.addIncoming(ClonedVal, ClonedBB);
1219 else
1220 Phi.addIncoming(Incoming, ClonedBB);
1221 }
1222 }
1223 }
1224 }
1225
1226 /// Sets the successor of PrevBB to be NewBB instead of OldBB. Note that all
1227 /// other successors are kept as well.
1228 void updatePredecessor(BasicBlock *PrevBB, BasicBlock *OldBB,
1229 BasicBlock *NewBB, DomTreeUpdater *DTU) {
1230 // When a path is reused, there is a chance that predecessors were already
1231 // updated before. Check if the predecessor needs to be updated first.
1232 if (!isPredecessor(OldBB, PrevBB))
1233 return;
1234
1235 Instruction *PrevTerm = PrevBB->getTerminator();
1236 for (unsigned Idx = 0; Idx < PrevTerm->getNumSuccessors(); Idx++) {
1237 if (PrevTerm->getSuccessor(Idx) == OldBB) {
1238 OldBB->removePredecessor(PrevBB, /* KeepOneInputPHIs = */ true);
1239 PrevTerm->setSuccessor(Idx, NewBB);
1240 }
1241 }
1242 DTU->applyUpdates({{DominatorTree::Delete, PrevBB, OldBB},
1243 {DominatorTree::Insert, PrevBB, NewBB}});
1244 }
1245
1246 /// Add new value mappings to the DefMap to keep track of all new definitions
1247 /// for a particular instruction. These will be used while updating SSA form.
1248 void updateDefMap(DefMap &NewDefs, ValueToValueMapTy &VMap) {
1250 NewDefsVector.reserve(VMap.size());
1251
1252 for (auto Entry : VMap) {
1253 Instruction *Inst =
1254 dyn_cast<Instruction>(const_cast<Value *>(Entry.first));
1255 if (!Inst || !Entry.second || isa<BranchInst>(Inst) ||
1256 isa<SwitchInst>(Inst)) {
1257 continue;
1258 }
1259
1260 Instruction *Cloned = dyn_cast<Instruction>(Entry.second);
1261 if (!Cloned)
1262 continue;
1263
1264 NewDefsVector.push_back({Inst, Cloned});
1265 }
1266
1267 // Sort the defs to get deterministic insertion order into NewDefs.
1268 sort(NewDefsVector, [](const auto &LHS, const auto &RHS) {
1269 if (LHS.first == RHS.first)
1270 return LHS.second->comesBefore(RHS.second);
1271 return LHS.first->comesBefore(RHS.first);
1272 });
1273
1274 for (const auto &KV : NewDefsVector)
1275 NewDefs[KV.first].push_back(KV.second);
1276 }
1277
1278 /// Update the last branch of a particular cloned path to point to the correct
1279 /// case successor.
1280 ///
1281 /// Note that this is an optional step and would have been done in later
1282 /// optimizations, but it makes the CFG significantly easier to work with.
1283 void updateLastSuccessor(const ThreadingPath &TPath,
1284 DuplicateBlockMap &DuplicateMap,
1285 DomTreeUpdater *DTU) {
1286 APInt NextState = TPath.getExitValue();
1287 BasicBlock *BB = TPath.getPath().back();
1288 BasicBlock *LastBlock = getClonedBB(BB, NextState, DuplicateMap);
1289
1290 // Note multiple paths can end at the same block so check that it is not
1291 // updated yet
1292 if (!isa<SwitchInst>(LastBlock->getTerminator()))
1293 return;
1294 SwitchInst *Switch = cast<SwitchInst>(LastBlock->getTerminator());
1295 BasicBlock *NextCase = getNextCaseSuccessor(Switch, NextState);
1296
1297 std::vector<DominatorTree::UpdateType> DTUpdates;
1298 SmallPtrSet<BasicBlock *, 4> SuccSet;
1299 for (BasicBlock *Succ : successors(LastBlock)) {
1300 if (Succ != NextCase && SuccSet.insert(Succ).second)
1301 DTUpdates.push_back({DominatorTree::Delete, LastBlock, Succ});
1302 }
1303
1304 Switch->eraseFromParent();
1305 BranchInst::Create(NextCase, LastBlock);
1306
1307 DTU->applyUpdates(DTUpdates);
1308 }
1309
1310 /// After cloning blocks, some of the phi nodes have extra incoming values
1311 /// that are no longer used. This function removes them.
1312 void cleanPhiNodes(BasicBlock *BB) {
1313 // If BB is no longer reachable, remove any remaining phi nodes
1314 if (pred_empty(BB)) {
1315 for (PHINode &PN : make_early_inc_range(BB->phis())) {
1316 PN.replaceAllUsesWith(PoisonValue::get(PN.getType()));
1317 PN.eraseFromParent();
1318 }
1319 return;
1320 }
1321
1322 // Remove any incoming values that come from an invalid predecessor
1323 for (PHINode &Phi : BB->phis())
1324 Phi.removeIncomingValueIf([&](unsigned Index) {
1325 BasicBlock *IncomingBB = Phi.getIncomingBlock(Index);
1326 return !isPredecessor(BB, IncomingBB);
1327 });
1328 }
1329
1330 /// Checks if BB was already cloned for a particular next state value. If it
1331 /// was then it returns this cloned block, and otherwise null.
1332 BasicBlock *getClonedBB(BasicBlock *BB, const APInt &NextState,
1333 DuplicateBlockMap &DuplicateMap) {
1334 CloneList ClonedBBs = DuplicateMap[BB];
1335
1336 // Find an entry in the CloneList with this NextState. If it exists then
1337 // return the corresponding BB
1338 auto It = llvm::find_if(ClonedBBs, [NextState](const ClonedBlock &C) {
1339 return C.State == NextState;
1340 });
1341 return It != ClonedBBs.end() ? (*It).BB : nullptr;
1342 }
1343
1344 /// Helper to get the successor corresponding to a particular case value for
1345 /// a switch statement.
1346 BasicBlock *getNextCaseSuccessor(SwitchInst *Switch, const APInt &NextState) {
1347 BasicBlock *NextCase = nullptr;
1348 for (auto Case : Switch->cases()) {
1349 if (Case.getCaseValue()->getValue() == NextState) {
1350 NextCase = Case.getCaseSuccessor();
1351 break;
1352 }
1353 }
1354 if (!NextCase)
1355 NextCase = Switch->getDefaultDest();
1356 return NextCase;
1357 }
1358
1359 /// Returns true if IncomingBB is a predecessor of BB.
1360 bool isPredecessor(BasicBlock *BB, BasicBlock *IncomingBB) {
1361 return llvm::is_contained(predecessors(BB), IncomingBB);
1362 }
1363
1364 AllSwitchPaths *SwitchPaths;
1365 DominatorTree *DT;
1366 AssumptionCache *AC;
1367 TargetTransformInfo *TTI;
1368 OptimizationRemarkEmitter *ORE;
1369 SmallPtrSet<const Value *, 32> EphValues;
1370 std::vector<ThreadingPath> TPaths;
1371};
1372} // namespace
1373
1374bool DFAJumpThreading::run(Function &F) {
1375 LLVM_DEBUG(dbgs() << "\nDFA Jump threading: " << F.getName() << "\n");
1376
1377 if (F.hasOptSize()) {
1378 LLVM_DEBUG(dbgs() << "Skipping due to the 'minsize' attribute\n");
1379 return false;
1380 }
1381
1382 if (ClViewCfgBefore)
1383 F.viewCFG();
1384
1385 SmallVector<AllSwitchPaths, 2> ThreadableLoops;
1386 bool MadeChanges = false;
1387 LoopInfoBroken = false;
1388
1389 for (BasicBlock &BB : F) {
1391 if (!SI)
1392 continue;
1393
1394 LLVM_DEBUG(dbgs() << "\nCheck if SwitchInst in BB " << BB.getName()
1395 << " is a candidate\n");
1396 MainSwitch Switch(SI, LI, ORE);
1397
1398 if (!Switch.getInstr()) {
1399 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is not a "
1400 << "candidate for jump threading\n");
1401 continue;
1402 }
1403
1404 LLVM_DEBUG(dbgs() << "\nSwitchInst in BB " << BB.getName() << " is a "
1405 << "candidate for jump threading\n");
1406 LLVM_DEBUG(SI->dump());
1407
1408 unfoldSelectInstrs(DT, Switch.getSelectInsts());
1409 if (!Switch.getSelectInsts().empty())
1410 MadeChanges = true;
1411
1412 AllSwitchPaths SwitchPaths(&Switch, ORE, LI,
1413 LI->getLoopFor(&BB)->getOutermostLoop());
1414 SwitchPaths.run();
1415
1416 if (SwitchPaths.getNumThreadingPaths() > 0) {
1417 ThreadableLoops.push_back(SwitchPaths);
1418
1419 // For the time being limit this optimization to occurring once in a
1420 // function since it can change the CFG significantly. This is not a
1421 // strict requirement but it can cause buggy behavior if there is an
1422 // overlap of blocks in different opportunities. There is a lot of room to
1423 // experiment with catching more opportunities here.
1424 // NOTE: To release this contraint, we must handle LoopInfo invalidation
1425 break;
1426 }
1427 }
1428
1429#ifdef NDEBUG
1430 LI->verify(*DT);
1431#endif
1432
1433 SmallPtrSet<const Value *, 32> EphValues;
1434 if (ThreadableLoops.size() > 0)
1435 CodeMetrics::collectEphemeralValues(&F, AC, EphValues);
1436
1437 for (AllSwitchPaths SwitchPaths : ThreadableLoops) {
1438 TransformDFA Transform(&SwitchPaths, DT, AC, TTI, ORE, EphValues);
1439 if (Transform.run())
1440 MadeChanges = LoopInfoBroken = true;
1441 }
1442
1443#ifdef EXPENSIVE_CHECKS
1444 assert(DT->verify(DominatorTree::VerificationLevel::Full));
1445 verifyFunction(F, &dbgs());
1446#endif
1447
1448 return MadeChanges;
1449}
1450
1451/// Integrate with the new Pass Manager
1456 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1459 DFAJumpThreading ThreadImpl(&AC, &DT, &LI, &TTI, &ORE);
1460 if (!ThreadImpl.run(F))
1461 return PreservedAnalyses::all();
1462
1465 if (!ThreadImpl.LoopInfoBroken)
1466 PA.preserve<LoopAnalysis>();
1467 return PA;
1468}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
std::deque< BasicBlock * > PathType
std::vector< PathType > PathsType
MapVector< Instruction *, std::vector< Instruction * > > DefMap
std::vector< ClonedBlock > CloneList
DenseMap< BasicBlock *, CloneList > DuplicateBlockMap
static cl::opt< double > MaxClonedRate("dfa-max-cloned-rate", cl::desc("Maximum cloned instructions rate accepted for the transformation"), cl::Hidden, cl::init(7.5))
This file defines the DenseMap class.
#define DEBUG_TYPE
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
Machine Trace Metrics
uint64_t IntrinsicInst * II
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition APInt.h:475
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM_ABI void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:528
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
LLVM_ABI void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
LLVM_ABI const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
LLVM_ABI filter_iterator< BasicBlock::const_iterator, std::function< bool(constInstruction &)> >::difference_type sizeWithoutDebug() const
Return the size of the basic block ignoring debug instructions.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition BasicBlock.h:233
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Analysis pass which computes a DominatorTree.
Definition Dominators.h:284
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:165
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:569
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:36
The optimization diagnostic interface.
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
iterator_range< const_block_iterator > blocks() const
LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:132
LLVM_ABI unsigned AddVariable(StringRef Name, Type *Ty)
Add a new variable to the SSA rewriter.
LLVM_ABI void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
LLVM_ABI void RewriteAllUses(DominatorTree *DT, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Perform all the necessary updates, including new PHI-nodes insertion and the requested uses update.
LLVM_ABI void AddUse(unsigned Var, Use *U)
Record a use of the symbolic value.
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getTrueValue() const
bool erase(PtrType Ptr)
Remove pointer from the set.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void reserve(size_type N)
void push_back(const T &Elt)
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) const
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition User.cpp:21
Value * getOperand(unsigned i) const
Definition User.h:232
size_type size() const
Definition ValueMap.h:144
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:256
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:322
const ParentTy * getParent() const
Definition ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
A raw_ostream that writes to an std::string.
@ Entry
Definition COFF.h:862
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:81
initializer< Ty > init(const Ty &Val)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
Definition CoroShape.h:31
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ User
could "use" a pointer
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:318
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1753
static cl::opt< unsigned > MaxNumPaths("dfa-max-num-paths", cl::desc("Max number of paths enumerated around a switch"), cl::Hidden, cl::init(200))
LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:644
LLVM_ABI bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2138
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:634
auto pred_size(const MachineBasicBlock *BB)
static cl::opt< bool > ClViewCfgBefore("dfa-jump-view-cfg-before", cl::desc("View the CFG before DFA Jump Threading"), cl::Hidden, cl::init(false))
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1624
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition ValueMapper.h:98
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition ValueMapper.h:80
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:548
static cl::opt< unsigned > MaxNumVisitiedPaths("dfa-max-num-visited-paths", cl::desc("Max number of blocks visited while enumerating paths around a switch"), cl::Hidden, cl::init(2500))
TargetTransformInfo TTI
static cl::opt< bool > EarlyExitHeuristic("dfa-early-exit-heuristic", cl::desc("Exit early if an unpredictable value come from the same loop"), cl::Hidden, cl::init(true))
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:560
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1760
static cl::opt< unsigned > MaxPathLength("dfa-max-path-length", cl::desc("Max number of blocks searched to find a threading path"), cl::Hidden, cl::init(20))
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1899
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
bool pred_empty(const BasicBlock *BB)
Definition CFG.h:119
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
static cl::opt< unsigned > CostThreshold("dfa-cost-threshold", cl::desc("Maximum cost accepted for the transformation"), cl::Hidden, cl::init(50))
static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Integrate with the new Pass Manager.