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.slt(
B.High); });
70 return I !=
Ranges.end() &&
I->Low.sle(
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() <<
"]";
120 const APInt &NumMergedCases) {
121 for (
auto &
I : SuccBB->
phis()) {
126 APInt LocalNumMergedCases = NumMergedCases;
127 for (; Idx !=
E && NewBB; ++Idx) {
141 for (; LocalNumMergedCases.
ugt(0) && Idx <
E; ++Idx)
143 Indices.push_back(Idx);
144 LocalNumMergedCases -= 1;
166 if (Leaf.Low == Leaf.High) {
172 if (Leaf.Low == LowerBound) {
176 }
else if (Leaf.High == UpperBound) {
180 }
else if (Leaf.Low->isZero()) {
188 Val, NegLo, Val->
getName() +
".off", NewLeaf);
211 APInt Range = Leaf.High->getValue() - Leaf.Low->getValue();
212 for (
APInt j(
Range.getBitWidth(), 0,
true);
j.slt(Range); ++
j) {
217 assert(BlockIdx != -1 &&
"Switch didn't go to this successor??");
233 const std::vector<IntRange> &UnreachableRanges) {
234 assert(LowerBound && UpperBound &&
"Bounds must be initialized");
235 unsigned Size = End - Begin;
242 if (Begin->Low == LowerBound && Begin->High == UpperBound) {
244 FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
247 return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
251 unsigned Mid =
Size / 2;
252 std::vector<CaseRange>
LHS(Begin, Begin + Mid);
254 std::vector<CaseRange>
RHS(Begin + Mid, End);
257 CaseRange &Pivot = *(Begin + Mid);
258 LLVM_DEBUG(
dbgs() <<
"Pivot ==> [" << Pivot.Low->getValue() <<
", "
259 << Pivot.High->getValue() <<
"]\n");
272 if (!UnreachableRanges.empty()) {
274 APInt GapLow =
LHS.back().High->getValue() + 1;
276 IntRange Gap = {GapLow, GapHigh};
277 if (GapHigh.
sge(GapLow) && IsInRanges(Gap, UnreachableRanges))
278 NewUpperBound =
LHS.back().High;
282 << NewUpperBound->
getValue() <<
"]\n"
283 <<
"RHS Bounds ==> [" << NewLowerBound->
getValue() <<
", "
284 << UpperBound->
getValue() <<
"]\n");
294 SwitchConvert(
LHS.begin(),
LHS.end(), LowerBound, NewUpperBound, Val,
295 NewNode, OrigBlock, Default, UnreachableRanges);
297 SwitchConvert(
RHS.begin(),
RHS.end(), NewLowerBound, UpperBound, Val,
298 NewNode, OrigBlock, Default, UnreachableRanges);
310 unsigned Clusterify(CaseVector &Cases,
SwitchInst *
SI) {
311 unsigned NumSimpleCases = 0;
314 for (
auto Case :
SI->cases()) {
315 if (Case.getCaseSuccessor() ==
SI->getDefaultDest())
317 Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
318 Case.getCaseSuccessor()));
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 ¤tValue =
I->High->getValue();
336 "Cases should be strictly ascending");
337 if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {
340 }
else if (++
I != J) {
344 Cases.erase(std::next(
I), Cases.end());
347 return NumSimpleCases;
357 Value *Val =
SI->getCondition();
362 if ((OrigBlock != &
F->getEntryBlock() &&
pred_empty(OrigBlock)) ||
364 DeleteList.
insert(OrigBlock);
370 const unsigned NumSimpleCases = Clusterify(Cases,
SI);
377 LLVM_DEBUG(
dbgs() <<
"Clusterify finished. Total clusters: " << Cases.size()
378 <<
". Total non-default cases: " << NumSimpleCases
379 <<
"\nCase clusters: " << Cases <<
"\n");
385 FixPhis(Default, OrigBlock, OrigBlock, UnsignedMax);
386 SI->eraseFromParent();
392 bool DefaultIsUnreachableFromSwitch =
false;
394 if (isa<UnreachableInst>(
Default->getFirstNonPHIOrDbg())) {
398 LowerBound = Cases.front().Low;
399 UpperBound = Cases.back().High;
400 DefaultIsUnreachableFromSwitch =
true;
422 const APInt &
Low = Cases.front().Low->getValue();
423 const APInt &
High = Cases.back().High->getValue();
429 DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
432 std::vector<IntRange> UnreachableRanges;
434 if (DefaultIsUnreachableFromSwitch) {
436 APInt MaxPop(UnsignedZero);
441 IntRange
R = {SignedMin, SignedMax};
442 UnreachableRanges.push_back(R);
443 for (
const auto &
I : Cases) {
447 IntRange &LastRange = UnreachableRanges.back();
448 if (LastRange.Low.eq(Low)) {
450 UnreachableRanges.pop_back();
454 LastRange.High =
Low - 1;
456 if (
High.ne(SignedMax)) {
457 IntRange
R = {
High + 1, SignedMax};
458 UnreachableRanges.push_back(R);
462 assert(
High.sge(Low) &&
"Popularity shouldn't be negative.");
466 if ((Pop +=
N).ugt(MaxPop)) {
473 for (
auto I = UnreachableRanges.begin(),
E = UnreachableRanges.end();
478 assert(Next->Low.sgt(
I->High));
485 const unsigned NumDefaultEdges =
SI->getNumCases() + 1 - NumSimpleCases;
486 for (
unsigned I = 0;
I < NumDefaultEdges; ++
I)
487 Default->removePredecessor(OrigBlock);
493 [PopSucc](
const CaseRange &R) {
return R.BB == PopSucc; });
498 SI->eraseFromParent();
501 if (!MaxPop.isZero())
502 for (
APInt I(UnsignedZero);
I.ult(MaxPop - 1); ++
I)
510 Val =
SI->getCondition();
514 SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
515 OrigBlock, OrigBlock, Default, UnreachableRanges);
522 if (SwitchBlock != Default)
523 FixPhis(Default, OrigBlock,
nullptr, UnsignedMax);
530 SI->eraseFromParent();
534 DeleteList.
insert(OldDefault);
538 bool Changed =
false;
545 if (DeleteList.
count(&Cur))
548 if (
SwitchInst *
SI = dyn_cast<SwitchInst>(Cur.getTerminator())) {
550 ProcessSwitchInst(
SI, DeleteList, AC, LVI);
587 "Lower SwitchInst's to branches",
false,
false)
595 return new LowerSwitchLegacyPass();
599 LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
600 auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
602 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.
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...
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
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 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 PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
@ ICMP_SLE
signed less or equal
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
Class to represent integer types.
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()
void sort(IteratorTy Start, IteratorTy End)
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())
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
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.
A cache of @llvm.assume calls within a function.
if(llvm_vc STREQUAL "") set(fake_version_inc "$
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)
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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.
constexpr unsigned BitWidth
@ ICMP_SGE
signed greater or equal
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
This class represents a range of values.
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.
auto reverse(ContainerTy &&C)
bool sgt(const APInt &RHS) const
Signed greater than comparison.
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.