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
9#include "llvm/Transforms/Scalar/JumpTableToSwitch.h"
10#include "ScalarOptions.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/ADT/SmallVector.h"
13#include "llvm/ADT/Statistic.h"
14#include "llvm/Analysis/ConstantFolding.h"
15#include "llvm/Analysis/DomTreeUpdater.h"
16#include "llvm/Analysis/OptimizationRemarkEmitter.h"
17#include "llvm/Analysis/PostDominators.h"
18#include "llvm/IR/IRBuilder.h"
19#include "llvm/IR/LLVMContext.h"
20#include "llvm/IR/ProfDataUtils.h"
21#include "llvm/ProfileData/InstrProf.h"
22#include "llvm/Transforms/Utils/BasicBlockUtils.h"
23#include <limits>
24
25using namespace llvm;
26
27#define DEBUG_TYPE "jump-table-to-switch"
28
29STATISTIC(NumEligibleJumpTables, "The number of jump tables seen by the pass "
30 "that can be converted if deemed profitable.");
31STATISTIC(NumJumpTablesConverted,
32 "The number of jump tables converted into switches.");
33
34namespace {
35struct JumpTable {
36 Value *Index;
37 SmallVector<std::pair<uint64_t, Function *>, 10> Funcs;
38};
39} // anonymous namespace
40
41static Function *getExpandableCallee(const ScalarOptions &Opts, Value *V,
42 FunctionType *CallFTy) {
43 auto *Func = dyn_cast<Function>(Val: V);
44 if (!Func || Func->isDeclaration() || Func->getFunctionType() != CallFTy ||
45 Func->getInstructionCount() >
46 Opts.jump_table_to_switch_function_size_threshold)
47 return nullptr;
48 return Func;
49}
50
51static std::optional<JumpTable> parseJumpTable(const ScalarOptions &Opts,
52 GetElementPtrInst *GEP,
53 PointerType *PtrTy,
54 FunctionType *CallFTy) {
55 Constant *Ptr = dyn_cast<Constant>(Val: GEP->getPointerOperand());
56 if (!Ptr)
57 return std::nullopt;
58
59 GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Ptr);
60 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
61 return std::nullopt;
62
63 Function &F = *GEP->getParent()->getParent();
64 const DataLayout &DL = F.getDataLayout();
65 const unsigned BitWidth =
66 DL.getIndexSizeInBits(AS: GEP->getPointerAddressSpace());
67 SmallMapVector<Value *, APInt, 4> VariableOffsets;
68 APInt ConstantOffset(BitWidth, 0);
69 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
70 return std::nullopt;
71 if (VariableOffsets.size() != 1)
72 return std::nullopt;
73 // TODO: consider supporting more general patterns
74 if (!ConstantOffset.isZero())
75 return std::nullopt;
76 APInt StrideBytes = VariableOffsets.front().second;
77 const uint64_t JumpTableSizeBytes = GV->getGlobalSize(DL);
78 if (JumpTableSizeBytes % StrideBytes.getZExtValue() != 0)
79 return std::nullopt;
80 ++NumEligibleJumpTables;
81 const uint64_t N = JumpTableSizeBytes / StrideBytes.getZExtValue();
82 if (N > Opts.jump_table_to_switch_size_threshold)
83 return std::nullopt;
84
85 JumpTable JT;
86 JT.Index = VariableOffsets.front().first;
87 JT.Funcs.reserve(N);
88 for (uint64_t Index = 0; Index < N; ++Index) {
89 // ConstantOffset is zero.
90 APInt Offset = Index * StrideBytes;
91 Constant *C =
92 ConstantFoldLoadFromConst(C: GV->getInitializer(), Ty: PtrTy, Offset, DL);
93 if (!C)
94 return std::nullopt;
95 if ((isa<ConstantPointerNull>(Val: C) &&
96 !NullPointerIsDefined(F: &F, AS: PtrTy->getAddressSpace())) ||
97 isa<UndefValue>(Val: C))
98 continue;
99 Function *Func = getExpandableCallee(Opts, V: C, CallFTy);
100 if (!Func)
101 return std::nullopt;
102 JT.Funcs.push_back(Elt: {Index, Func});
103 }
104 // Empty table, or only values that are UB when called
105 if (JT.Funcs.empty())
106 return std::nullopt;
107 return JT;
108}
109
110static BasicBlock *
111expandToSwitch(CallBase *CB, const JumpTable &JT, DomTreeUpdater &DTU,
112 OptimizationRemarkEmitter &ORE,
113 llvm::function_ref<GlobalValue::GUID(const Function &)>
114 GetGuidForFunction) {
115 ++NumJumpTablesConverted;
116 const bool IsVoid = CB->getType() == Type::getVoidTy(C&: CB->getContext());
117
118 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
119 BasicBlock *BB = CB->getParent();
120 BasicBlock *Tail = SplitBlock(Old: BB, SplitPt: CB, DTU: &DTU, LI: nullptr, MSSAU: nullptr,
121 BBName: BB->getName() + Twine(".tail"));
122 DTUpdates.push_back(Elt: {DominatorTree::Delete, BB, Tail});
123 BB->getTerminator()->eraseFromParent();
124
125 Function &F = *BB->getParent();
126 BasicBlock *BBUnreachable = BasicBlock::Create(
127 Context&: F.getContext(), Name: "default.switch.case.unreachable", Parent: &F, InsertBefore: Tail);
128 IRBuilder<> BuilderUnreachable(BBUnreachable);
129 BuilderUnreachable.CreateUnreachable();
130
131 IRBuilder<> Builder(BB);
132 SwitchInst *Switch = Builder.CreateSwitch(V: JT.Index, Dest: BBUnreachable);
133 DTUpdates.push_back(Elt: {DominatorTree::Insert, BB, BBUnreachable});
134
135 IRBuilder<> BuilderTail(CB);
136 PHINode *PHI =
137 IsVoid ? nullptr : BuilderTail.CreatePHI(Ty: CB->getType(), NumReservedValues: JT.Funcs.size());
138 const auto *ProfMD = CB->getMetadata(KindID: LLVMContext::MD_prof);
139
140 SmallVector<uint64_t> BranchWeights;
141 DenseMap<GlobalValue::GUID, uint64_t> GuidToCounter;
142 const bool HadProfile = isValueProfileMD(ProfileData: ProfMD);
143 if (HadProfile) {
144 // The assumptions, coming in, are that the functions in JT.Funcs are
145 // defined in this module (from parseJumpTable).
146 assert(llvm::all_of(JT.Funcs, [](auto &F) {
147 return F.second && !F.second->isDeclaration();
148 }));
149 BranchWeights.reserve(N: JT.Funcs.size() + 1);
150 // The first is the default target, which is the unreachable block created
151 // above.
152 BranchWeights.push_back(Elt: 0U);
153 uint64_t TotalCount = 0;
154 auto Targets = getValueProfDataFromInst(
155 Inst: *CB, ValueKind: InstrProfValueKind::IPVK_IndirectCallTarget,
156 MaxNumValueData: std::numeric_limits<uint32_t>::max(), TotalC&: TotalCount);
157
158 for (const auto &[G, C] : Targets) {
159 [[maybe_unused]] auto It = GuidToCounter.insert(KV: {G, C});
160 // We should always be inserting as it is verifier-enforced IR invariant
161 // that VP metadata does not have duplicate values.
162 assert(It.second);
163 }
164 }
165 for (auto [Index, Func] : JT.Funcs) {
166 BasicBlock *B = BasicBlock::Create(Context&: Func->getContext(),
167 Name: "call." + Twine(Index), Parent: &F, InsertBefore: Tail);
168 DTUpdates.push_back(Elt: {DominatorTree::Insert, BB, B});
169 DTUpdates.push_back(Elt: {DominatorTree::Insert, B, Tail});
170
171 CallBase *Call = cast<CallBase>(Val: CB->clone());
172 // The MD_prof metadata (VP kind), if it existed, can be dropped, it doesn't
173 // make sense on a direct call. Note that the values are used for the branch
174 // weights of the switch.
175 Call->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
176 Call->setCalledFunction(Func);
177 Call->insertInto(ParentBB: B, It: B->end());
178 Switch->addCase(
179 OnVal: cast<ConstantInt>(Val: ConstantInt::get(Ty: JT.Index->getType(), V: Index)), Dest: B);
180 GlobalValue::GUID FctID = GetGuidForFunction(*Func);
181 // It'd be OK to _not_ find target functions in GuidToCounter, e.g. suppose
182 // just some of the jump targets are taken (for the given profile).
183 BranchWeights.push_back(Elt: FctID == 0U ? 0U
184 : GuidToCounter.lookup_or(Val: FctID, Default: 0U));
185 UncondBrInst::Create(Target: Tail, InsertBefore: B);
186 if (PHI)
187 PHI->addIncoming(V: Call, BB: B);
188 }
189 DTU.applyUpdates(Updates: DTUpdates);
190 ORE.emit(RemarkBuilder: [&]() {
191 return OptimizationRemark(DEBUG_TYPE, "ReplacedJumpTableWithSwitch", CB)
192 << "expanded indirect call into switch";
193 });
194 auto *Select = dyn_cast<SelectInst>(Val: CB->getCalledOperand());
195 SmallVector<uint32_t, 2> SelectWeights;
196 // Only set branch weights on the switch if we have non-zero branch weights.
197 // We can have no non-zero branch weights while having VP metadata if for
198 // example, all of the functions are external and not instrumented.
199 if (HadProfile && llvm::any_of(Range&: BranchWeights, P: not_equal_to(Arg: 0))) {
200 setBranchWeights(I&: *Switch, Weights: downscaleWeights(Weights: BranchWeights),
201 /*IsExpected=*/false);
202 } else if (Select && extractBranchWeights(I: *Select, Weights&: SelectWeights) &&
203 llvm::any_of(Range&: SelectWeights, P: not_equal_to(Arg: 0))) {
204 // Switch branches:
205 // - default (never taken)
206 // - 0: false case (branch 1) of select
207 // - 1: true case (branch 0) of select
208 setBranchWeights(I&: *Switch, Weights: {0, SelectWeights[1], SelectWeights[0]},
209 /*IsExpected=*/false);
210 } else
211 setExplicitlyUnknownBranchWeights(I&: *Switch, DEBUG_TYPE);
212 if (PHI)
213 CB->replaceAllUsesWith(V: PHI);
214 CB->eraseFromParent();
215 return Tail;
216}
217
218PreservedAnalyses JumpTableToSwitchPass::run(Function &F,
219 FunctionAnalysisManager &AM) {
220 OptimizationRemarkEmitter &ORE =
221 AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
222 DominatorTree *DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
223 PostDominatorTree *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(IR&: F);
224 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
225 const ScalarOptions &Opts = getScalarOptions(F);
226 bool Changed = false;
227 auto FuncToGuid = [&](const Function &Fct) {
228 if (const auto MaybeGUID = Fct.getGUIDIfAssigned(); MaybeGUID)
229 return *MaybeGUID;
230
231 return Function::getGUIDAssumingExternalLinkage(
232 GlobalName: getIRPGOObjectName(GO: Fct, InLTO));
233 };
234
235 for (BasicBlock &BB : make_early_inc_range(Range&: F)) {
236 BasicBlock *CurrentBB = &BB;
237 while (CurrentBB) {
238 BasicBlock *SplittedOutTail = nullptr;
239 for (Instruction &I : make_early_inc_range(Range&: *CurrentBB)) {
240 auto *Call = dyn_cast<CallInst>(Val: &I);
241 if (!Call || Call->getCalledFunction() || Call->isMustTailCall())
242 continue;
243 std::optional<JumpTable> JT;
244 if (auto *S = dyn_cast<SelectInst>(Val: Call->getCalledOperand())) {
245 Function *F0 = getExpandableCallee(Opts, V: S->getFalseValue(),
246 CallFTy: Call->getFunctionType());
247 if (!F0)
248 continue;
249 Function *F1 = getExpandableCallee(Opts, V: S->getTrueValue(),
250 CallFTy: Call->getFunctionType());
251 if (!F1)
252 continue;
253 JT = JumpTable();
254 JT->Index = S->getCondition();
255 JT->Funcs.push_back(Elt: {0, F0});
256 JT->Funcs.push_back(Elt: {1, F1});
257 } else if (auto *L = dyn_cast<LoadInst>(Val: Call->getCalledOperand())) {
258 // Skip atomic or volatile loads.
259 if (!L || !L->isSimple())
260 continue;
261 auto *GEP = dyn_cast<GetElementPtrInst>(Val: L->getPointerOperand());
262 if (!GEP ||
263 (!GEP->hasNoUnsignedWrap() && !GEP->hasNoUnsignedSignedWrap()))
264 continue;
265 auto *PtrTy = dyn_cast<PointerType>(Val: L->getType());
266 assert(PtrTy && "call operand must be a pointer");
267 JT = parseJumpTable(Opts, GEP, PtrTy, CallFTy: Call->getFunctionType());
268 }
269 if (!JT)
270 continue;
271 SplittedOutTail = expandToSwitch(CB: Call, JT: *JT, DTU, ORE, GetGuidForFunction: FuncToGuid);
272 Changed = true;
273 break;
274 }
275 CurrentBB = SplittedOutTail ? SplittedOutTail : nullptr;
276 }
277 }
278
279 if (!Changed)
280 return PreservedAnalyses::all();
281
282 PreservedAnalyses PA;
283 if (DT)
284 PA.preserve<DominatorTreeAnalysis>();
285 if (PDT)
286 PA.preserve<PostDominatorTreeAnalysis>();
287 return PA;
288}
289