LLVM 19.0.0git
JumpTableToSwitch.cpp
Go to the documentation of this file.
1//===- JumpTableToSwitch.cpp ----------------------------------------------===//
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
15#include "llvm/IR/IRBuilder.h"
18
19using namespace llvm;
20
22 JumpTableSizeThreshold("jump-table-to-switch-size-threshold", cl::Hidden,
23 cl::desc("Only split jump tables with size less or "
24 "equal than JumpTableSizeThreshold."),
25 cl::init(10));
26
27// TODO: Consider adding a cost model for profitability analysis of this
28// transformation. Currently we replace a jump table with a switch if all the
29// functions in the jump table are smaller than the provided threshold.
31 "jump-table-to-switch-function-size-threshold", cl::Hidden,
32 cl::desc("Only split jump tables containing functions whose sizes are less "
33 "or equal than this threshold."),
34 cl::init(50));
35
36#define DEBUG_TYPE "jump-table-to-switch"
37
38namespace {
39struct JumpTableTy {
40 Value *Index;
42};
43} // anonymous namespace
44
45static std::optional<JumpTableTy> parseJumpTable(GetElementPtrInst *GEP,
46 PointerType *PtrTy) {
47 Constant *Ptr = dyn_cast<Constant>(GEP->getPointerOperand());
48 if (!Ptr)
49 return std::nullopt;
50
51 GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr);
52 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
53 return std::nullopt;
54
55 Function &F = *GEP->getParent()->getParent();
56 const DataLayout &DL = F.getParent()->getDataLayout();
57 const unsigned BitWidth =
58 DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
59 MapVector<Value *, APInt> VariableOffsets;
60 APInt ConstantOffset(BitWidth, 0);
61 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
62 return std::nullopt;
63 if (VariableOffsets.size() != 1)
64 return std::nullopt;
65 // TODO: consider supporting more general patterns
66 if (!ConstantOffset.isZero())
67 return std::nullopt;
68 APInt StrideBytes = VariableOffsets.front().second;
69 const uint64_t JumpTableSizeBytes = DL.getTypeAllocSize(GV->getValueType());
70 if (JumpTableSizeBytes % StrideBytes.getZExtValue() != 0)
71 return std::nullopt;
72 const uint64_t N = JumpTableSizeBytes / StrideBytes.getZExtValue();
74 return std::nullopt;
75
76 JumpTableTy JumpTable;
77 JumpTable.Index = VariableOffsets.front().first;
78 JumpTable.Funcs.reserve(N);
79 for (uint64_t Index = 0; Index < N; ++Index) {
80 // ConstantOffset is zero.
81 APInt Offset = Index * StrideBytes;
82 Constant *C =
84 auto *Func = dyn_cast_or_null<Function>(C);
85 if (!Func || Func->isDeclaration() ||
86 Func->getInstructionCount() > FunctionSizeThreshold)
87 return std::nullopt;
88 JumpTable.Funcs.push_back(Func);
89 }
90 return JumpTable;
91}
92
93static BasicBlock *expandToSwitch(CallBase *CB, const JumpTableTy &JT,
94 DomTreeUpdater &DTU,
96 const bool IsVoid = CB->getType() == Type::getVoidTy(CB->getContext());
97
99 BasicBlock *BB = CB->getParent();
100 BasicBlock *Tail = SplitBlock(BB, CB, &DTU, nullptr, nullptr,
101 BB->getName() + Twine(".tail"));
102 DTUpdates.push_back({DominatorTree::Delete, BB, Tail});
104
105 Function &F = *BB->getParent();
106 BasicBlock *BBUnreachable = BasicBlock::Create(
107 F.getContext(), "default.switch.case.unreachable", &F, Tail);
108 IRBuilder<> BuilderUnreachable(BBUnreachable);
109 BuilderUnreachable.CreateUnreachable();
110
111 IRBuilder<> Builder(BB);
112 SwitchInst *Switch = Builder.CreateSwitch(JT.Index, BBUnreachable);
113 DTUpdates.push_back({DominatorTree::Insert, BB, BBUnreachable});
114
115 IRBuilder<> BuilderTail(CB);
116 PHINode *PHI =
117 IsVoid ? nullptr : BuilderTail.CreatePHI(CB->getType(), JT.Funcs.size());
118
119 for (auto [Index, Func] : llvm::enumerate(JT.Funcs)) {
120 BasicBlock *B = BasicBlock::Create(Func->getContext(),
121 "call." + Twine(Index), &F, Tail);
122 DTUpdates.push_back({DominatorTree::Insert, BB, B});
123 DTUpdates.push_back({DominatorTree::Insert, B, Tail});
124
125 CallBase *Call = cast<CallBase>(CB->clone());
126 Call->setCalledFunction(Func);
127 Call->insertInto(B, B->end());
128 Switch->addCase(
129 cast<ConstantInt>(ConstantInt::get(JT.Index->getType(), Index)), B);
131 if (PHI)
132 PHI->addIncoming(Call, B);
133 }
134 DTU.applyUpdates(DTUpdates);
135 ORE.emit([&]() {
136 return OptimizationRemark(DEBUG_TYPE, "ReplacedJumpTableWithSwitch", CB)
137 << "expanded indirect call into switch";
138 });
139 if (PHI)
141 CB->eraseFromParent();
142 return Tail;
143}
144
152 bool Changed = false;
153 for (BasicBlock &BB : make_early_inc_range(F)) {
154 BasicBlock *CurrentBB = &BB;
155 while (CurrentBB) {
156 BasicBlock *SplittedOutTail = nullptr;
157 for (Instruction &I : make_early_inc_range(*CurrentBB)) {
158 auto *Call = dyn_cast<CallInst>(&I);
159 if (!Call || Call->getCalledFunction() || Call->isMustTailCall())
160 continue;
161 auto *L = dyn_cast<LoadInst>(Call->getCalledOperand());
162 // Skip atomic or volatile loads.
163 if (!L || !L->isSimple())
164 continue;
165 auto *GEP = dyn_cast<GetElementPtrInst>(L->getPointerOperand());
166 if (!GEP)
167 continue;
168 auto *PtrTy = dyn_cast<PointerType>(L->getType());
169 assert(PtrTy && "call operand must be a pointer");
170 std::optional<JumpTableTy> JumpTable = parseJumpTable(GEP, PtrTy);
171 if (!JumpTable)
172 continue;
173 SplittedOutTail = expandToSwitch(Call, *JumpTable, DTU, ORE);
174 Changed = true;
175 break;
176 }
177 CurrentBB = SplittedOutTail ? SplittedOutTail : nullptr;
178 }
179 }
180
181 if (!Changed)
182 return PreservedAnalyses::all();
183
185 if (DT)
187 if (PDT)
189 return PA;
190}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Hexagon Common GEP
static cl::opt< unsigned > FunctionSizeThreshold("jump-table-to-switch-function-size-threshold", cl::Hidden, cl::desc("Only split jump tables containing functions whose sizes are less " "or equal than this threshold."), cl::init(50))
static cl::opt< unsigned > JumpTableSizeThreshold("jump-table-to-switch-size-threshold", cl::Hidden, cl::desc("Only split jump tables with size less or " "equal than JumpTableSizeThreshold."), cl::init(10))
static BasicBlock * expandToSwitch(CallBase *CB, const JumpTableTy &JT, DomTreeUpdater &DTU, OptimizationRemarkEmitter &ORE)
static std::optional< JumpTableTy > parseJumpTable(GetElementPtrInst *GEP, PointerType *PtrTy)
#define DEBUG_TYPE
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Class for arbitrary precision integers.
Definition: APInt.h:76
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1491
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:358
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:492
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1467
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
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:973
Type * getValueType() const
Definition: GlobalValue.h:296
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1263
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2387
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Definition: IRBuilder.h:1143
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2656
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
size_type size() const
Definition: MapVector.h:60
std::pair< KeyT, ValueT > & front()
Definition: MapVector.h:83
The optimization diagnostic interface.
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for applied optimization remarks.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
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.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
static Type * getVoidTy(LLVMContext &C)
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2406
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
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
#define N
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.