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, false); j.ult(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 // Explicitly 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->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")
#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
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
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:78
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1181
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1162
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1110
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1217
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
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:61
iterator end()
Definition: BasicBlock.h:451
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:438
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:507
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:202
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:457
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:209
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:167
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:514
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2599
static Constant * getNeg(Constant *C, bool HasNSW=false)
Definition: Constants.cpp:2587
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
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.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
This is an important base class in LLVM.
Definition: Constant.h:42
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:34
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:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:323
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:412
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
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:1075
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:132
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:2197
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2202
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:656
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:419
char & LowerSwitchID
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
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:1954
@ 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:2051
FunctionPass * createLowerSwitchPass()
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)