LLVM 19.0.0git
LowerSwitch.cpp
Go to the documentation of this file.
1//===- LowerSwitch.cpp - Eliminate Switch instructions --------------------===//
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// The LowerSwitch transformation rewrites switch instructions with a sequence
10// of branches, which allows targets to get away with not implementing the
11// switch instruction until it is convenient.
12//
13//===----------------------------------------------------------------------===//
14
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CFG.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/Function.h"
28#include "llvm/IR/InstrTypes.h"
30#include "llvm/IR/PassManager.h"
31#include "llvm/IR/Value.h"
33#include "llvm/Pass.h"
36#include "llvm/Support/Debug.h"
41#include <algorithm>
42#include <cassert>
43#include <cstdint>
44#include <iterator>
45#include <vector>
46
47using namespace llvm;
48
49#define DEBUG_TYPE "lower-switch"
50
51namespace {
52
53struct IntRange {
54 APInt Low, High;
55};
56
57} // end anonymous namespace
58
59namespace {
60// Return true iff R is covered by Ranges.
61bool IsInRanges(const IntRange &R, const std::vector<IntRange> &Ranges) {
62 // Note: Ranges must be sorted, non-overlapping and non-adjacent.
63
64 // Find the first range whose High field is >= R.High,
65 // then check if the Low field is <= R.Low. If so, we
66 // have a Range that covers R.
67 auto I = llvm::lower_bound(
68 Ranges, R, [](IntRange A, IntRange B) { return A.High.slt(B.High); });
69 return I != Ranges.end() && I->Low.sle(R.Low);
70}
71
72struct CaseRange {
75 BasicBlock *BB;
76
77 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
78 : Low(low), High(high), BB(bb) {}
79};
80
81using CaseVector = std::vector<CaseRange>;
82using CaseItr = std::vector<CaseRange>::iterator;
83
84/// The comparison function for sorting the switch case values in the vector.
85/// WARNING: Case ranges should be disjoint!
86struct CaseCmp {
87 bool operator()(const CaseRange &C1, const CaseRange &C2) {
88 const ConstantInt *CI1 = cast<const ConstantInt>(C1.Low);
89 const ConstantInt *CI2 = cast<const ConstantInt>(C2.High);
90 return CI1->getValue().slt(CI2->getValue());
91 }
92};
93
94/// Used for debugging purposes.
96raw_ostream &operator<<(raw_ostream &O, const CaseVector &C) {
97 O << "[";
98
99 for (CaseVector::const_iterator B = C.begin(), E = C.end(); B != E;) {
100 O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";
101 if (++B != E)
102 O << ", ";
103 }
104
105 return O << "]";
106}
107
108/// Update the first occurrence of the "switch statement" BB in the PHI
109/// node with the "new" BB. The other occurrences will:
110///
111/// 1) Be updated by subsequent calls to this function. Switch statements may
112/// have more than one outcoming edge into the same BB if they all have the same
113/// value. When the switch statement is converted these incoming edges are now
114/// coming from multiple BBs.
115/// 2) Removed if subsequent incoming values now share the same case, i.e.,
116/// multiple outcome edges are condensed into one. This is necessary to keep the
117/// number of phi values equal to the number of branches to SuccBB.
118void FixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
119 const APInt &NumMergedCases) {
120 for (auto &I : SuccBB->phis()) {
121 PHINode *PN = cast<PHINode>(&I);
122
123 // Only update the first occurrence if NewBB exists.
124 unsigned Idx = 0, E = PN->getNumIncomingValues();
125 APInt LocalNumMergedCases = NumMergedCases;
126 for (; Idx != E && NewBB; ++Idx) {
127 if (PN->getIncomingBlock(Idx) == OrigBB) {
128 PN->setIncomingBlock(Idx, NewBB);
129 break;
130 }
131 }
132
133 // Skip the updated incoming block so that it will not be removed.
134 if (NewBB)
135 ++Idx;
136
137 // Remove additional occurrences coming from condensed cases and keep the
138 // number of incoming values equal to the number of branches to SuccBB.
140 for (; LocalNumMergedCases.ugt(0) && Idx < E; ++Idx)
141 if (PN->getIncomingBlock(Idx) == OrigBB) {
142 Indices.push_back(Idx);
143 LocalNumMergedCases -= 1;
144 }
145 // Remove incoming values in the reverse order to prevent invalidating
146 // *successive* index.
147 for (unsigned III : llvm::reverse(Indices))
148 PN->removeIncomingValue(III);
149 }
150}
151
152/// Create a new leaf block for the binary lookup tree. It checks if the
153/// switch's value == the case's value. If not, then it jumps to the default
154/// branch. At this point in the tree, the value can't be another valid case
155/// value, so the jump to the "default" branch is warranted.
156BasicBlock *NewLeafBlock(CaseRange &Leaf, Value *Val, ConstantInt *LowerBound,
157 ConstantInt *UpperBound, BasicBlock *OrigBlock,
159 Function *F = OrigBlock->getParent();
160 BasicBlock *NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
161 F->insert(++OrigBlock->getIterator(), NewLeaf);
162
163 // Emit comparison
164 ICmpInst *Comp = nullptr;
165 if (Leaf.Low == Leaf.High) {
166 // Make the seteq instruction...
167 Comp =
168 new ICmpInst(NewLeaf, ICmpInst::ICMP_EQ, Val, Leaf.Low, "SwitchLeaf");
169 } else {
170 // Make range comparison
171 if (Leaf.Low == LowerBound) {
172 // Val >= Min && Val <= Hi --> Val <= Hi
173 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
174 "SwitchLeaf");
175 } else if (Leaf.High == UpperBound) {
176 // Val <= Max && Val >= Lo --> Val >= Lo
177 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,
178 "SwitchLeaf");
179 } else if (Leaf.Low->isZero()) {
180 // Val >= 0 && Val <= Hi --> Val <=u Hi
181 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
182 "SwitchLeaf");
183 } else {
184 // Emit V-Lo <=u Hi-Lo
185 Constant *NegLo = ConstantExpr::getNeg(Leaf.Low);
186 Instruction *Add = BinaryOperator::CreateAdd(
187 Val, NegLo, Val->getName() + ".off", NewLeaf);
188 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
189 Comp = new ICmpInst(NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
190 "SwitchLeaf");
191 }
192 }
193
194 // Make the conditional branch...
195 BasicBlock *Succ = Leaf.BB;
196 BranchInst::Create(Succ, Default, Comp, NewLeaf);
197
198 // Update the PHI incoming value/block for the default.
199 for (auto &I : Default->phis()) {
200 PHINode *PN = cast<PHINode>(&I);
201 auto *V = PN->getIncomingValueForBlock(OrigBlock);
202 PN->addIncoming(V, NewLeaf);
203 }
204
205 // If there were any PHI nodes in this successor, rewrite one entry
206 // from OrigBlock to come from NewLeaf.
207 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
208 PHINode *PN = cast<PHINode>(I);
209 // Remove all but one incoming entries from the cluster
210 APInt Range = Leaf.High->getValue() - Leaf.Low->getValue();
211 for (APInt j(Range.getBitWidth(), 0, true); j.slt(Range); ++j) {
212 PN->removeIncomingValue(OrigBlock);
213 }
214
215 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
216 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
217 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
218 }
219
220 return NewLeaf;
221}
222
223/// Convert the switch statement into a binary lookup of the case values.
224/// The function recursively builds this tree. LowerBound and UpperBound are
225/// used to keep track of the bounds for Val that have already been checked by
226/// a block emitted by one of the previous calls to switchConvert in the call
227/// stack.
228BasicBlock *SwitchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
229 ConstantInt *UpperBound, Value *Val,
230 BasicBlock *Predecessor, BasicBlock *OrigBlock,
232 const std::vector<IntRange> &UnreachableRanges) {
233 assert(LowerBound && UpperBound && "Bounds must be initialized");
234 unsigned Size = End - Begin;
235
236 if (Size == 1) {
237 // Check if the Case Range is perfectly squeezed in between
238 // already checked Upper and Lower bounds. If it is then we can avoid
239 // emitting the code that checks if the value actually falls in the range
240 // because the bounds already tell us so.
241 if (Begin->Low == LowerBound && Begin->High == UpperBound) {
242 APInt NumMergedCases = UpperBound->getValue() - LowerBound->getValue();
243 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
244 return Begin->BB;
245 }
246 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
247 Default);
248 }
249
250 unsigned Mid = Size / 2;
251 std::vector<CaseRange> LHS(Begin, Begin + Mid);
252 LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
253 std::vector<CaseRange> RHS(Begin + Mid, End);
254 LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
255
256 CaseRange &Pivot = *(Begin + Mid);
257 LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "
258 << Pivot.High->getValue() << "]\n");
259
260 // NewLowerBound here should never be the integer minimal value.
261 // This is because it is computed from a case range that is never
262 // the smallest, so there is always a case range that has at least
263 // a smaller value.
264 ConstantInt *NewLowerBound = Pivot.Low;
265
266 // Because NewLowerBound is never the smallest representable integer
267 // it is safe here to subtract one.
268 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
269 NewLowerBound->getValue() - 1);
270
271 if (!UnreachableRanges.empty()) {
272 // Check if the gap between LHS's highest and NewLowerBound is unreachable.
273 APInt GapLow = LHS.back().High->getValue() + 1;
274 APInt GapHigh = NewLowerBound->getValue() - 1;
275 IntRange Gap = {GapLow, GapHigh};
276 if (GapHigh.sge(GapLow) && IsInRanges(Gap, UnreachableRanges))
277 NewUpperBound = LHS.back().High;
278 }
279
280 LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getValue() << ", "
281 << NewUpperBound->getValue() << "]\n"
282 << "RHS Bounds ==> [" << NewLowerBound->getValue() << ", "
283 << UpperBound->getValue() << "]\n");
284
285 // Create a new node that checks if the value is < pivot. Go to the
286 // left branch if it is and right branch if not.
287 Function *F = OrigBlock->getParent();
288 BasicBlock *NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
289
290 ICmpInst *Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot");
291
292 BasicBlock *LBranch =
293 SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,
294 NewNode, OrigBlock, Default, UnreachableRanges);
295 BasicBlock *RBranch =
296 SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,
297 NewNode, OrigBlock, Default, UnreachableRanges);
298
299 F->insert(++OrigBlock->getIterator(), NewNode);
300 Comp->insertInto(NewNode, NewNode->end());
301
302 BranchInst::Create(LBranch, RBranch, Comp, NewNode);
303 return NewNode;
304}
305
306/// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.
307/// \post \p Cases wouldn't contain references to \p SI's default BB.
308/// \returns Number of \p SI's cases that do not reference \p SI's default BB.
309unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {
310 unsigned NumSimpleCases = 0;
311
312 // Start with "simple" cases
313 for (auto Case : SI->cases()) {
314 if (Case.getCaseSuccessor() == SI->getDefaultDest())
315 continue;
316 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
317 Case.getCaseSuccessor()));
318 ++NumSimpleCases;
319 }
320
321 llvm::sort(Cases, CaseCmp());
322
323 // Merge case into clusters
324 if (Cases.size() >= 2) {
325 CaseItr I = Cases.begin();
326 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
327 const APInt &nextValue = J->Low->getValue();
328 const APInt &currentValue = I->High->getValue();
329 BasicBlock *nextBB = J->BB;
330 BasicBlock *currentBB = I->BB;
331
332 // If the two neighboring cases go to the same destination, merge them
333 // into a single case.
334 assert(nextValue.sgt(currentValue) &&
335 "Cases should be strictly ascending");
336 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
337 I->High = J->High;
338 // FIXME: Combine branch weights.
339 } else if (++I != J) {
340 *I = *J;
341 }
342 }
343 Cases.erase(std::next(I), Cases.end());
344 }
345
346 return NumSimpleCases;
347}
348
349/// Replace the specified switch instruction with a sequence of chained if-then
350/// insts in a balanced binary search.
351void ProcessSwitchInst(SwitchInst *SI,
353 AssumptionCache *AC, LazyValueInfo *LVI) {
354 BasicBlock *OrigBlock = SI->getParent();
355 Function *F = OrigBlock->getParent();
356 Value *Val = SI->getCondition(); // The value we are switching on...
357 BasicBlock *Default = SI->getDefaultDest();
358
359 // Don't handle unreachable blocks. If there are successors with phis, this
360 // would leave them behind with missing predecessors.
361 if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||
362 OrigBlock->getSinglePredecessor() == OrigBlock) {
363 DeleteList.insert(OrigBlock);
364 return;
365 }
366
367 // Prepare cases vector.
368 CaseVector Cases;
369 const unsigned NumSimpleCases = Clusterify(Cases, SI);
370 IntegerType *IT = cast<IntegerType>(SI->getCondition()->getType());
371 const unsigned BitWidth = IT->getBitWidth();
372 // Explictly use higher precision to prevent unsigned overflow where
373 // `UnsignedMax - 0 + 1 == 0`
374 APInt UnsignedZero(BitWidth + 1, 0);
375 APInt UnsignedMax = APInt::getMaxValue(BitWidth);
376 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
377 << ". Total non-default cases: " << NumSimpleCases
378 << "\nCase clusters: " << Cases << "\n");
379
380 // If there is only the default destination, just branch.
381 if (Cases.empty()) {
382 BranchInst::Create(Default, OrigBlock);
383 // Remove all the references from Default's PHIs to OrigBlock, but one.
384 FixPhis(Default, OrigBlock, OrigBlock, UnsignedMax);
385 SI->eraseFromParent();
386 return;
387 }
388
389 ConstantInt *LowerBound = nullptr;
390 ConstantInt *UpperBound = nullptr;
391 bool DefaultIsUnreachableFromSwitch = false;
392
393 if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
394 // Make the bounds tightly fitted around the case value range, because we
395 // know that the value passed to the switch must be exactly one of the case
396 // values.
397 LowerBound = Cases.front().Low;
398 UpperBound = Cases.back().High;
399 DefaultIsUnreachableFromSwitch = true;
400 } else {
401 // Constraining the range of the value being switched over helps eliminating
402 // unreachable BBs and minimizing the number of `add` instructions
403 // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after
404 // LowerSwitch isn't as good, and also much more expensive in terms of
405 // compile time for the following reasons:
406 // 1. it processes many kinds of instructions, not just switches;
407 // 2. even if limited to icmp instructions only, it will have to process
408 // roughly C icmp's per switch, where C is the number of cases in the
409 // switch, while LowerSwitch only needs to call LVI once per switch.
410 const DataLayout &DL = F->getParent()->getDataLayout();
411 KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);
412 // TODO Shouldn't this create a signed range?
413 ConstantRange KnownBitsRange =
414 ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);
415 const ConstantRange LVIRange =
416 LVI->getConstantRange(Val, SI, /*UndefAllowed*/ false);
417 ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);
418 // We delegate removal of unreachable non-default cases to other passes. In
419 // the unlikely event that some of them survived, we just conservatively
420 // maintain the invariant that all the cases lie between the bounds. This
421 // may, however, still render the default case effectively unreachable.
422 const APInt &Low = Cases.front().Low->getValue();
423 const APInt &High = Cases.back().High->getValue();
424 APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);
426
427 LowerBound = ConstantInt::get(SI->getContext(), Min);
428 UpperBound = ConstantInt::get(SI->getContext(), Max);
429 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
430 }
431
432 std::vector<IntRange> UnreachableRanges;
433
434 if (DefaultIsUnreachableFromSwitch) {
436 APInt MaxPop(UnsignedZero);
437 BasicBlock *PopSucc = nullptr;
438
441 IntRange R = {SignedMin, SignedMax};
442 UnreachableRanges.push_back(R);
443 for (const auto &I : Cases) {
444 const APInt &Low = I.Low->getValue();
445 const APInt &High = I.High->getValue();
446
447 IntRange &LastRange = UnreachableRanges.back();
448 if (LastRange.Low.eq(Low)) {
449 // There is nothing left of the previous range.
450 UnreachableRanges.pop_back();
451 } else {
452 // Terminate the previous range.
453 assert(Low.sgt(LastRange.Low));
454 LastRange.High = Low - 1;
455 }
456 if (High.ne(SignedMax)) {
457 IntRange R = {High + 1, SignedMax};
458 UnreachableRanges.push_back(R);
459 }
460
461 // Count popularity.
462 assert(High.sge(Low) && "Popularity shouldn't be negative.");
463 APInt N = High.sext(BitWidth + 1) - Low.sext(BitWidth + 1) + 1;
464 // Explict insert to make sure the bitwidth of APInts match
465 APInt &Pop = Popularity.insert({I.BB, APInt(UnsignedZero)}).first->second;
466 if ((Pop += N).ugt(MaxPop)) {
467 MaxPop = Pop;
468 PopSucc = I.BB;
469 }
470 }
471#ifndef NDEBUG
472 /* UnreachableRanges should be sorted and the ranges non-adjacent. */
473 for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
474 I != E; ++I) {
475 assert(I->Low.sle(I->High));
476 auto Next = I + 1;
477 if (Next != E) {
478 assert(Next->Low.sgt(I->High));
479 }
480 }
481#endif
482
483 // As the default block in the switch is unreachable, update the PHI nodes
484 // (remove all of the references to the default block) to reflect this.
485 const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;
486 for (unsigned I = 0; I < NumDefaultEdges; ++I)
487 Default->removePredecessor(OrigBlock);
488
489 // Use the most popular block as the new default, reducing the number of
490 // cases.
491 Default = PopSucc;
492 llvm::erase_if(Cases,
493 [PopSucc](const CaseRange &R) { return R.BB == PopSucc; });
494
495 // If there are no cases left, just branch.
496 if (Cases.empty()) {
497 BranchInst::Create(Default, OrigBlock);
498 SI->eraseFromParent();
499 // As all the cases have been replaced with a single branch, only keep
500 // one entry in the PHI nodes.
501 if (!MaxPop.isZero())
502 for (APInt I(UnsignedZero); I.ult(MaxPop - 1); ++I)
503 PopSucc->removePredecessor(OrigBlock);
504 return;
505 }
506
507 // If the condition was a PHI node with the switch block as a predecessor
508 // removing predecessors may have caused the condition to be erased.
509 // Getting the condition value again here protects against that.
510 Val = SI->getCondition();
511 }
512
513 BasicBlock *SwitchBlock =
514 SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
515 OrigBlock, OrigBlock, Default, UnreachableRanges);
516
517 // We have added incoming values for newly-created predecessors in
518 // NewLeafBlock(). The only meaningful work we offload to FixPhis() is to
519 // remove the incoming values from OrigBlock. There might be a special case
520 // that SwitchBlock is the same as Default, under which the PHIs in Default
521 // are fixed inside SwitchConvert().
522 if (SwitchBlock != Default)
523 FixPhis(Default, OrigBlock, nullptr, UnsignedMax);
524
525 // Branch to our shiny new if-then stuff...
526 BranchInst::Create(SwitchBlock, OrigBlock);
527
528 // We are now done with the switch instruction, delete it.
529 BasicBlock *OldDefault = SI->getDefaultDest();
530 SI->eraseFromParent();
531
532 // If the Default block has no more predecessors just add it to DeleteList.
533 if (pred_empty(OldDefault))
534 DeleteList.insert(OldDefault);
535}
536
537bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC) {
538 bool Changed = false;
540
541 // We use make_early_inc_range here so that we don't traverse new blocks.
543 // If the block is a dead Default block that will be deleted later, don't
544 // waste time processing it.
545 if (DeleteList.count(&Cur))
546 continue;
547
548 if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur.getTerminator())) {
549 Changed = true;
550 ProcessSwitchInst(SI, DeleteList, AC, LVI);
551 }
552 }
553
554 for (BasicBlock *BB : DeleteList) {
555 LVI->eraseBlock(BB);
556 DeleteDeadBlock(BB);
557 }
558
559 return Changed;
560}
561
562/// Replace all SwitchInst instructions with chained branch instructions.
563class LowerSwitchLegacyPass : public FunctionPass {
564public:
565 // Pass identification, replacement for typeid
566 static char ID;
567
568 LowerSwitchLegacyPass() : FunctionPass(ID) {
570 }
571
572 bool runOnFunction(Function &F) override;
573
574 void getAnalysisUsage(AnalysisUsage &AU) const override {
576 }
577};
578
579} // end anonymous namespace
580
581char LowerSwitchLegacyPass::ID = 0;
582
583// Publicly exposed interface to pass...
584char &llvm::LowerSwitchID = LowerSwitchLegacyPass::ID;
585
586INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch",
587 "Lower SwitchInst's to branches", false, false)
590INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch",
592
593// createLowerSwitchPass - Interface to this file...
595 return new LowerSwitchLegacyPass();
596}
597
598bool LowerSwitchLegacyPass::runOnFunction(Function &F) {
599 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
600 auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
601 AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;
602 return LowerSwitch(F, LVI, AC);
603}
604
609 return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none()
611}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ATTRIBUTE_USED
Definition: Compiler.h:151
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
@ Default
Definition: DwarfDebug.cpp:87
uint64_t Size
bool End
Definition: ELF_riscv.cpp:480
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
lowerswitch
Lower SwitchInst s to branches
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t High
if(VerifyEach)
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:184
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:187
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:197
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1215
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:442
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:498
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:439
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:496
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2537
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2525
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
This class represents a range of values.
Definition: ConstantRange.h:47
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
This instruction compares its operands according to the predicate given to the constructor.
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Class to represent integer types.
Definition: DerivedTypes.h:40
Analysis to compute lazy value information.
Wrapper around LazyValueInfo.
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:31
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
ConstantRange getConstantRange(Value *V, Instruction *CxtI, bool UndefAllowed)
Return the ConstantRange constraint that is known to hold for the specified value at the specified in...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingBlock(unsigned i, BasicBlock *BB)
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.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Multiway switch.
LLVM Value Representation.
Definition: Value.h:74
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2178
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2183
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
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:665
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
char & LowerSwitchID
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1963
@ Add
Sum of integers.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2060
FunctionPass * createLowerSwitchPass()
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)