Go to the documentation of this file.
50 #define DEBUG_TYPE "lower-switch"
62 bool IsInRanges(
const IntRange &R,
const std::vector<IntRange> &Ranges) {
69 Ranges, R, [](IntRange A, IntRange
B) {
return A.High <
B.High; });
70 return I != Ranges.end() &&
I->Low <=
R.Low;
82 using CaseVector = std::vector<CaseRange>;
83 using CaseItr = std::vector<CaseRange>::iterator;
88 bool operator()(
const CaseRange &
C1,
const CaseRange &C2) {
90 const ConstantInt *CI2 = cast<const ConstantInt>(C2.High);
100 for (CaseVector::const_iterator
B =
C.begin(),
E =
C.end();
B !=
E;) {
101 O <<
"[" <<
B->Low->getValue() <<
", " <<
B->High->getValue() <<
"]";
122 for (
auto &
I : SuccBB->
phis()) {
127 unsigned LocalNumMergedCases = NumMergedCases;
128 for (; Idx !=
E && NewBB; ++Idx) {
142 for (; LocalNumMergedCases > 0 && Idx <
E; ++Idx)
144 Indices.push_back(Idx);
145 LocalNumMergedCases--;
163 F->getBasicBlockList().insert(++OrigBlock->
getIterator(), NewLeaf);
167 if (Leaf.Low == Leaf.High) {
173 if (Leaf.Low == LowerBound) {
177 }
else if (Leaf.High == UpperBound) {
181 }
else if (Leaf.Low->isZero()) {
189 Val, NegLo, Val->
getName() +
".off", NewLeaf);
212 uint64_t Range = Leaf.High->getSExtValue() - Leaf.Low->getSExtValue();
218 assert(BlockIdx != -1 &&
"Switch didn't go to this successor??");
234 const std::vector<IntRange> &UnreachableRanges) {
235 assert(LowerBound && UpperBound &&
"Bounds must be initialized");
236 unsigned Size = End - Begin;
243 if (Begin->Low == LowerBound && Begin->High == UpperBound) {
244 unsigned NumMergedCases = 0;
246 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
249 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
253 unsigned Mid =
Size / 2;
254 std::vector<CaseRange>
LHS(Begin, Begin + Mid);
256 std::vector<CaseRange>
RHS(Begin + Mid, End);
259 CaseRange &Pivot = *(Begin + Mid);
260 LLVM_DEBUG(
dbgs() <<
"Pivot ==> [" << Pivot.Low->getValue() <<
", "
261 << Pivot.High->getValue() <<
"]\n");
274 if (!UnreachableRanges.empty()) {
276 int64_t GapLow =
LHS.back().High->getSExtValue() + 1;
278 IntRange Gap = { GapLow, GapHigh };
279 if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
280 NewUpperBound =
LHS.back().High;
294 Val, Pivot.Low,
"Pivot");
297 SwitchConvert(
LHS.begin(),
LHS.end(), LowerBound, NewUpperBound, Val,
298 NewNode, OrigBlock, Default, UnreachableRanges);
300 SwitchConvert(
RHS.begin(),
RHS.end(), NewLowerBound, UpperBound, Val,
301 NewNode, OrigBlock, Default, UnreachableRanges);
303 F->getBasicBlockList().insert(++OrigBlock->
getIterator(), NewNode);
313 unsigned Clusterify(CaseVector &Cases,
SwitchInst *
SI) {
314 unsigned NumSimpleCases = 0;
317 for (
auto Case :
SI->cases()) {
318 if (Case.getCaseSuccessor() ==
SI->getDefaultDest())
320 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
321 Case.getCaseSuccessor()));
328 if (Cases.size() >= 2) {
329 CaseItr
I = Cases.begin();
330 for (CaseItr J = std::next(
I),
E = Cases.end(); J !=
E; ++J) {
331 int64_t nextValue = J->Low->getSExtValue();
332 int64_t currentValue =
I->High->getSExtValue();
338 assert(nextValue > currentValue &&
"Cases should be strictly ascending");
339 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
342 }
else if (++
I != J) {
346 Cases.erase(std::next(
I), Cases.end());
349 return NumSimpleCases;
359 Value *Val =
SI->getCondition();
364 if ((OrigBlock != &
F->getEntryBlock() &&
pred_empty(OrigBlock)) ||
366 DeleteList.
insert(OrigBlock);
372 const unsigned NumSimpleCases = Clusterify(Cases,
SI);
373 LLVM_DEBUG(
dbgs() <<
"Clusterify finished. Total clusters: " << Cases.size()
374 <<
". Total non-default cases: " << NumSimpleCases
375 <<
"\nCase clusters: " << Cases <<
"\n");
381 FixPhis(Default, OrigBlock, OrigBlock);
382 SI->eraseFromParent();
388 bool DefaultIsUnreachableFromSwitch =
false;
390 if (isa<UnreachableInst>(
Default->getFirstNonPHIOrDbg())) {
394 LowerBound = Cases.front().Low;
395 UpperBound = Cases.back().High;
396 DefaultIsUnreachableFromSwitch =
true;
418 APInt Low = Cases.front().Low->getValue();
419 APInt High = Cases.back().High->getValue();
425 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
428 std::vector<IntRange> UnreachableRanges;
430 if (DefaultIsUnreachableFromSwitch) {
437 UnreachableRanges.push_back(R);
438 for (
const auto &
I : Cases) {
439 int64_t
Low =
I.Low->getSExtValue();
440 int64_t
High =
I.High->getSExtValue();
442 IntRange &LastRange = UnreachableRanges.back();
443 if (LastRange.Low == Low) {
445 UnreachableRanges.pop_back();
448 assert(Low > LastRange.Low);
449 LastRange.High =
Low - 1;
453 UnreachableRanges.push_back(R);
458 unsigned &Pop = Popularity[
I.BB];
459 if ((Pop +=
N) > MaxPop) {
466 for (
auto I = UnreachableRanges.begin(),
E = UnreachableRanges.end();
478 const unsigned NumDefaultEdges =
SI->getNumCases() + 1 - NumSimpleCases;
479 for (
unsigned I = 0;
I < NumDefaultEdges; ++
I)
480 Default->removePredecessor(OrigBlock);
484 assert(MaxPop > 0 && PopSucc);
487 [PopSucc](
const CaseRange &R) {
return R.BB == PopSucc; });
492 SI->eraseFromParent();
495 for (
unsigned I = 0 ;
I < (MaxPop - 1) ; ++
I)
503 Val =
SI->getCondition();
507 SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
508 OrigBlock, OrigBlock, Default, UnreachableRanges);
515 if (SwitchBlock != Default)
516 FixPhis(Default, OrigBlock,
nullptr);
527 DeleteList.
insert(OldDefault);
531 bool Changed =
false;
538 if (DeleteList.
count(&Cur))
541 if (
SwitchInst *
SI = dyn_cast<SwitchInst>(Cur.getTerminator())) {
543 ProcessSwitchInst(
SI, DeleteList, AC, LVI);
580 "Lower SwitchInst's to branches",
false,
false)
588 return new LowerSwitchLegacyPass();
592 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
593 auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
595 return LowerSwitch(
F, LVI, AC);
A set of analyses that are preserved following a run of a transformation pass.
#define LLVM_ATTRIBUTE_USED
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This is an optimization pass for GlobalISel generic memory operations.
A parsed version of the target data layout string in and methods for querying it.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
void initializeLowerSwitchLegacyPassPass(PassRegistry &)
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
instcombine should handle this C2 when C1
const APInt & getValue() const
Return the constant as an APInt value reference.
Analysis to compute lazy value information.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
@ ICMP_SLE
signed less or equal
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
This is the shared class of boolean and integer constants.
< i1 > br i1 label label bb bb
INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) INITIALIZE_PASS_END(LowerSwitchLegacyPass
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
(vector float) vec_cmpeq(*A, *B) C
@ ICMP_ULE
unsigned less or equal
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Value * getIncomingValueForBlock(const BasicBlock *BB) const
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
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.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
FunctionPass * createLowerSwitchPass()
bool slt(const APInt &RHS) const
Signed less than comparison.
This is an important base class in LLVM.
This instruction compares its operands according to the predicate given to the constructor.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
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...
A function analysis which provides an AssumptionCache.
void setIncomingBlock(unsigned i, BasicBlock *BB)
Wrapper around LazyValueInfo.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
multiplies can be turned into SHL s
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
This pass computes, caches, and vends lazy value constraint information.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Class for arbitrary precision integers.
Lower SwitchInst s to branches
@ ICMP_SLT
signed less than
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
An immutable pass that tracks lazily created AssumptionCache objects.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
A cache of @llvm.assume calls within a function.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool pred_empty(const BasicBlock *BB)
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
StringRef getName() const
Return a constant reference to the value's name.
static bool runOnFunction(Function &F, bool PostInlining)
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
void sort(IteratorTy Start, IteratorTy End)
@ ICMP_SGE
signed greater or equal
This class represents a range of values.
const InstListType & getInstList() const
Return the underlying instruction list container.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
LLVM Value Representation.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.