LLVM 17.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 <limits>
46#include <vector>
47
48using namespace llvm;
49
50#define DEBUG_TYPE "lower-switch"
51
52namespace {
53
54struct IntRange {
55 APInt Low, High;
56};
57
58} // end anonymous namespace
59
60namespace {
61// Return true iff R is covered by Ranges.
62bool IsInRanges(const IntRange &R, const std::vector<IntRange> &Ranges) {
63 // Note: Ranges must be sorted, non-overlapping and non-adjacent.
64
65 // Find the first range whose High field is >= R.High,
66 // then check if the Low field is <= R.Low. If so, we
67 // have a Range that covers R.
68 auto I = llvm::lower_bound(
69 Ranges, R, [](IntRange A, IntRange B) { return A.High.slt(B.High); });
70 return I != Ranges.end() && I->Low.sle(R.Low);
71}
72
73struct CaseRange {
76 BasicBlock *BB;
77
78 CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
79 : Low(low), High(high), BB(bb) {}
80};
81
82using CaseVector = std::vector<CaseRange>;
83using CaseItr = std::vector<CaseRange>::iterator;
84
85/// The comparison function for sorting the switch case values in the vector.
86/// WARNING: Case ranges should be disjoint!
87struct CaseCmp {
88 bool operator()(const CaseRange &C1, const CaseRange &C2) {
89 const ConstantInt *CI1 = cast<const ConstantInt>(C1.Low);
90 const ConstantInt *CI2 = cast<const ConstantInt>(C2.High);
91 return CI1->getValue().slt(CI2->getValue());
92 }
93};
94
95/// Used for debugging purposes.
97raw_ostream &operator<<(raw_ostream &O, const CaseVector &C) {
98 O << "[";
99
100 for (CaseVector::const_iterator B = C.begin(), E = C.end(); B != E;) {
101 O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";
102 if (++B != E)
103 O << ", ";
104 }
105
106 return O << "]";
107}
108
109/// Update the first occurrence of the "switch statement" BB in the PHI
110/// node with the "new" BB. The other occurrences will:
111///
112/// 1) Be updated by subsequent calls to this function. Switch statements may
113/// have more than one outcoming edge into the same BB if they all have the same
114/// value. When the switch statement is converted these incoming edges are now
115/// coming from multiple BBs.
116/// 2) Removed if subsequent incoming values now share the same case, i.e.,
117/// multiple outcome edges are condensed into one. This is necessary to keep the
118/// number of phi values equal to the number of branches to SuccBB.
119void FixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
120 const APInt &NumMergedCases) {
121 for (auto &I : SuccBB->phis()) {
122 PHINode *PN = cast<PHINode>(&I);
123
124 // Only update the first occurrence if NewBB exists.
125 unsigned Idx = 0, E = PN->getNumIncomingValues();
126 APInt LocalNumMergedCases = NumMergedCases;
127 for (; Idx != E && NewBB; ++Idx) {
128 if (PN->getIncomingBlock(Idx) == OrigBB) {
129 PN->setIncomingBlock(Idx, NewBB);
130 break;
131 }
132 }
133
134 // Skip the updated incoming block so that it will not be removed.
135 if (NewBB)
136 ++Idx;
137
138 // Remove additional occurrences coming from condensed cases and keep the
139 // number of incoming values equal to the number of branches to SuccBB.
141 for (; LocalNumMergedCases.ugt(0) && Idx < E; ++Idx)
142 if (PN->getIncomingBlock(Idx) == OrigBB) {
143 Indices.push_back(Idx);
144 LocalNumMergedCases -= 1;
145 }
146 // Remove incoming values in the reverse order to prevent invalidating
147 // *successive* index.
148 for (unsigned III : llvm::reverse(Indices))
149 PN->removeIncomingValue(III);
150 }
151}
152
153/// Create a new leaf block for the binary lookup tree. It checks if the
154/// switch's value == the case's value. If not, then it jumps to the default
155/// branch. At this point in the tree, the value can't be another valid case
156/// value, so the jump to the "default" branch is warranted.
157BasicBlock *NewLeafBlock(CaseRange &Leaf, Value *Val, ConstantInt *LowerBound,
158 ConstantInt *UpperBound, BasicBlock *OrigBlock,
160 Function *F = OrigBlock->getParent();
161 BasicBlock *NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
162 F->insert(++OrigBlock->getIterator(), NewLeaf);
163
164 // Emit comparison
165 ICmpInst *Comp = nullptr;
166 if (Leaf.Low == Leaf.High) {
167 // Make the seteq instruction...
168 Comp =
169 new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, Leaf.Low, "SwitchLeaf");
170 } else {
171 // Make range comparison
172 if (Leaf.Low == LowerBound) {
173 // Val >= Min && Val <= Hi --> Val <= Hi
174 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
175 "SwitchLeaf");
176 } else if (Leaf.High == UpperBound) {
177 // Val <= Max && Val >= Lo --> Val >= Lo
178 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,
179 "SwitchLeaf");
180 } else if (Leaf.Low->isZero()) {
181 // Val >= 0 && Val <= Hi --> Val <=u Hi
182 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
183 "SwitchLeaf");
184 } else {
185 // Emit V-Lo <=u Hi-Lo
186 Constant *NegLo = ConstantExpr::getNeg(Leaf.Low);
187 Instruction *Add = BinaryOperator::CreateAdd(
188 Val, NegLo, Val->getName() + ".off", NewLeaf);
189 Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
190 Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
191 "SwitchLeaf");
192 }
193 }
194
195 // Make the conditional branch...
196 BasicBlock *Succ = Leaf.BB;
197 BranchInst::Create(Succ, Default, Comp, NewLeaf);
198
199 // Update the PHI incoming value/block for the default.
200 for (auto &I : Default->phis()) {
201 PHINode *PN = cast<PHINode>(&I);
202 auto *V = PN->getIncomingValueForBlock(OrigBlock);
203 PN->addIncoming(V, NewLeaf);
204 }
205
206 // If there were any PHI nodes in this successor, rewrite one entry
207 // from OrigBlock to come from NewLeaf.
208 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
209 PHINode *PN = cast<PHINode>(I);
210 // Remove all but one incoming entries from the cluster
211 APInt Range = Leaf.High->getValue() - Leaf.Low->getValue();
212 for (APInt j(Range.getBitWidth(), 0, true); j.slt(Range); ++j) {
213 PN->removeIncomingValue(OrigBlock);
214 }
215
216 int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
217 assert(BlockIdx != -1 && "Switch didn't go to this successor??");
218 PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
219 }
220
221 return NewLeaf;
222}
223
224/// Convert the switch statement into a binary lookup of the case values.
225/// The function recursively builds this tree. LowerBound and UpperBound are
226/// used to keep track of the bounds for Val that have already been checked by
227/// a block emitted by one of the previous calls to switchConvert in the call
228/// stack.
229BasicBlock *SwitchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
230 ConstantInt *UpperBound, Value *Val,
231 BasicBlock *Predecessor, BasicBlock *OrigBlock,
233 const std::vector<IntRange> &UnreachableRanges) {
234 assert(LowerBound && UpperBound && "Bounds must be initialized");
235 unsigned Size = End - Begin;
236
237 if (Size == 1) {
238 // Check if the Case Range is perfectly squeezed in between
239 // already checked Upper and Lower bounds. If it is then we can avoid
240 // emitting the code that checks if the value actually falls in the range
241 // because the bounds already tell us so.
242 if (Begin->Low == LowerBound && Begin->High == UpperBound) {
243 APInt NumMergedCases = UpperBound->getValue() - LowerBound->getValue();
244 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
245 return Begin->BB;
246 }
247 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
248 Default);
249 }
250
251 unsigned Mid = Size / 2;
252 std::vector<CaseRange> LHS(Begin, Begin + Mid);
253 LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
254 std::vector<CaseRange> RHS(Begin + Mid, End);
255 LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
256
257 CaseRange &Pivot = *(Begin + Mid);
258 LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "
259 << Pivot.High->getValue() << "]\n");
260
261 // NewLowerBound here should never be the integer minimal value.
262 // This is because it is computed from a case range that is never
263 // the smallest, so there is always a case range that has at least
264 // a smaller value.
265 ConstantInt *NewLowerBound = Pivot.Low;
266
267 // Because NewLowerBound is never the smallest representable integer
268 // it is safe here to subtract one.
269 ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
270 NewLowerBound->getValue() - 1);
271
272 if (!UnreachableRanges.empty()) {
273 // Check if the gap between LHS's highest and NewLowerBound is unreachable.
274 APInt GapLow = LHS.back().High->getValue() + 1;
275 APInt GapHigh = NewLowerBound->getValue() - 1;
276 IntRange Gap = {GapLow, GapHigh};
277 if (GapHigh.sge(GapLow) && IsInRanges(Gap, UnreachableRanges))
278 NewUpperBound = LHS.back().High;
279 }
280
281 LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getValue() << ", "
282 << NewUpperBound->getValue() << "]\n"
283 << "RHS Bounds ==> [" << NewLowerBound->getValue() << ", "
284 << UpperBound->getValue() << "]\n");
285
286 // Create a new node that checks if the value is < pivot. Go to the
287 // left branch if it is and right branch if not.
288 Function *F = OrigBlock->getParent();
289 BasicBlock *NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
290
291 ICmpInst *Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot");
292
293 BasicBlock *LBranch =
294 SwitchConvert(LHS.begin(), LHS.end(), LowerBound, NewUpperBound, Val,
295 NewNode, OrigBlock, Default, UnreachableRanges);
296 BasicBlock *RBranch =
297 SwitchConvert(RHS.begin(), RHS.end(), NewLowerBound, UpperBound, Val,
298 NewNode, OrigBlock, Default, UnreachableRanges);
299
300 F->insert(++OrigBlock->getIterator(), NewNode);
301 Comp->insertInto(NewNode, NewNode->end());
302
303 BranchInst::Create(LBranch, RBranch, Comp, NewNode);
304 return NewNode;
305}
306
307/// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.
308/// \post \p Cases wouldn't contain references to \p SI's default BB.
309/// \returns Number of \p SI's cases that do not reference \p SI's default BB.
310unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {
311 unsigned NumSimpleCases = 0;
312
313 // Start with "simple" cases
314 for (auto Case : SI->cases()) {
315 if (Case.getCaseSuccessor() == SI->getDefaultDest())
316 continue;
317 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
318 Case.getCaseSuccessor()));
319 ++NumSimpleCases;
320 }
321
322 llvm::sort(Cases, CaseCmp());
323
324 // Merge case into clusters
325 if (Cases.size() >= 2) {
326 CaseItr I = Cases.begin();
327 for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
328 const APInt &nextValue = J->Low->getValue();
329 const APInt &currentValue = I->High->getValue();
330 BasicBlock *nextBB = J->BB;
331 BasicBlock *currentBB = I->BB;
332
333 // If the two neighboring cases go to the same destination, merge them
334 // into a single case.
335 assert(nextValue.sgt(currentValue) &&
336 "Cases should be strictly ascending");
337 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
338 I->High = J->High;
339 // FIXME: Combine branch weights.
340 } else if (++I != J) {
341 *I = *J;
342 }
343 }
344 Cases.erase(std::next(I), Cases.end());
345 }
346
347 return NumSimpleCases;
348}
349
350/// Replace the specified switch instruction with a sequence of chained if-then
351/// insts in a balanced binary search.
352void ProcessSwitchInst(SwitchInst *SI,
354 AssumptionCache *AC, LazyValueInfo *LVI) {
355 BasicBlock *OrigBlock = SI->getParent();
356 Function *F = OrigBlock->getParent();
357 Value *Val = SI->getCondition(); // The value we are switching on...
358 BasicBlock *Default = SI->getDefaultDest();
359
360 // Don't handle unreachable blocks. If there are successors with phis, this
361 // would leave them behind with missing predecessors.
362 if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||
363 OrigBlock->getSinglePredecessor() == OrigBlock) {
364 DeleteList.insert(OrigBlock);
365 return;
366 }
367
368 // Prepare cases vector.
369 CaseVector Cases;
370 const unsigned NumSimpleCases = Clusterify(Cases, SI);
371 IntegerType *IT = cast<IntegerType>(SI->getCondition()->getType());
372 const unsigned BitWidth = IT->getBitWidth();
373 // Explictly use higher precision to prevent unsigned overflow where
374 // `UnsignedMax - 0 + 1 == 0`
375 APInt UnsignedZero(BitWidth + 1, 0);
376 APInt UnsignedMax = APInt::getMaxValue(BitWidth);
377 LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
378 << ". Total non-default cases: " << NumSimpleCases
379 << "\nCase clusters: " << Cases << "\n");
380
381 // If there is only the default destination, just branch.
382 if (Cases.empty()) {
383 BranchInst::Create(Default, OrigBlock);
384 // Remove all the references from Default's PHIs to OrigBlock, but one.
385 FixPhis(Default, OrigBlock, OrigBlock, UnsignedMax);
386 SI->eraseFromParent();
387 return;
388 }
389
390 ConstantInt *LowerBound = nullptr;
391 ConstantInt *UpperBound = nullptr;
392 bool DefaultIsUnreachableFromSwitch = false;
393
394 if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
395 // Make the bounds tightly fitted around the case value range, because we
396 // know that the value passed to the switch must be exactly one of the case
397 // values.
398 LowerBound = Cases.front().Low;
399 UpperBound = Cases.back().High;
400 DefaultIsUnreachableFromSwitch = true;
401 } else {
402 // Constraining the range of the value being switched over helps eliminating
403 // unreachable BBs and minimizing the number of `add` instructions
404 // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after
405 // LowerSwitch isn't as good, and also much more expensive in terms of
406 // compile time for the following reasons:
407 // 1. it processes many kinds of instructions, not just switches;
408 // 2. even if limited to icmp instructions only, it will have to process
409 // roughly C icmp's per switch, where C is the number of cases in the
410 // switch, while LowerSwitch only needs to call LVI once per switch.
411 const DataLayout &DL = F->getParent()->getDataLayout();
412 KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);
413 // TODO Shouldn't this create a signed range?
414 ConstantRange KnownBitsRange =
415 ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);
416 const ConstantRange LVIRange = LVI->getConstantRange(Val, SI);
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:139
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:86
uint64_t Size
bool End
Definition: ELF_riscv.cpp:464
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
@ SI
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:75
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:1183
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1164
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:1112
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1219
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:56
iterator end()
Definition: BasicBlock.h:328
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:326
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:384
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:292
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:349
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2593
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2581
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
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.
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
Definition: Instruction.cpp:98
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=true)
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: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Multiway switch.
LLVM Value Representation.
Definition: Value.h:74
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1069
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:82
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:2187
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2192
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:748
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:511
char & LowerSwitchID
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
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:2038
@ 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:292
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
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:2113
FunctionPass * createLowerSwitchPass()
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)