LLVM 19.0.0git
IndirectBrExpandPass.cpp
Go to the documentation of this file.
1//===- IndirectBrExpandPass.cpp - Expand indirectbr to switch -------------===//
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/// \file
9///
10/// Implements an expansion pass to turn `indirectbr` instructions in the IR
11/// into `switch` instructions. This works by enumerating the basic blocks in
12/// a dense range of integers, replacing each `blockaddr` constant with the
13/// corresponding integer constant, and then building a switch that maps from
14/// the integers to the actual blocks. All of the indirectbr instructions in the
15/// function are redirected to this common switch.
16///
17/// While this is generically useful if a target is unable to codegen
18/// `indirectbr` natively, it is primarily useful when there is some desire to
19/// get the builtin non-jump-table lowering of a switch even when the input
20/// source contained an explicit indirect branch construct.
21///
22/// Note that it doesn't make any sense to enable this pass unless a target also
23/// disables jump-table lowering of switches. Doing that is likely to pessimize
24/// the code.
25///
26//===----------------------------------------------------------------------===//
27
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Sequence.h"
35#include "llvm/IR/BasicBlock.h"
36#include "llvm/IR/Constants.h"
37#include "llvm/IR/Dominators.h"
38#include "llvm/IR/Function.h"
41#include "llvm/Pass.h"
44#include <optional>
45
46using namespace llvm;
47
48#define DEBUG_TYPE "indirectbr-expand"
49
50namespace {
51
52class IndirectBrExpandLegacyPass : public FunctionPass {
53public:
54 static char ID; // Pass identification, replacement for typeid
55
56 IndirectBrExpandLegacyPass() : FunctionPass(ID) {
58 }
59
60 void getAnalysisUsage(AnalysisUsage &AU) const override {
62 }
63
64 bool runOnFunction(Function &F) override;
65};
66
67} // end anonymous namespace
68
69static bool runImpl(Function &F, const TargetLowering *TLI,
70 DomTreeUpdater *DTU);
71
74 auto *STI = TM->getSubtargetImpl(F);
75 if (!STI->enableIndirectBrExpand())
77
78 auto *TLI = STI->getTargetLowering();
81
82 bool Changed = runImpl(F, TLI, DT ? &DTU : nullptr);
83 if (!Changed)
87 return PA;
88}
89
90char IndirectBrExpandLegacyPass::ID = 0;
91
92INITIALIZE_PASS_BEGIN(IndirectBrExpandLegacyPass, DEBUG_TYPE,
93 "Expand indirectbr instructions", false, false)
95INITIALIZE_PASS_END(IndirectBrExpandLegacyPass, DEBUG_TYPE,
96 "Expand indirectbr instructions", false, false)
97
99 return new IndirectBrExpandLegacyPass();
100}
101
103 auto &DL = F.getParent()->getDataLayout();
104
106
107 // Set of all potential successors for indirectbr instructions.
108 SmallPtrSet<BasicBlock *, 4> IndirectBrSuccs;
109
110 // Build a list of indirectbrs that we want to rewrite.
111 for (BasicBlock &BB : F)
112 if (auto *IBr = dyn_cast<IndirectBrInst>(BB.getTerminator())) {
113 // Handle the degenerate case of no successors by replacing the indirectbr
114 // with unreachable as there is no successor available.
115 if (IBr->getNumSuccessors() == 0) {
116 (void)new UnreachableInst(F.getContext(), IBr->getIterator());
117 IBr->eraseFromParent();
118 continue;
119 }
120
121 IndirectBrs.push_back(IBr);
122 for (BasicBlock *SuccBB : IBr->successors())
123 IndirectBrSuccs.insert(SuccBB);
124 }
125
126 if (IndirectBrs.empty())
127 return false;
128
129 // If we need to replace any indirectbrs we need to establish integer
130 // constants that will correspond to each of the basic blocks in the function
131 // whose address escapes. We do that here and rewrite all the blockaddress
132 // constants to just be those integer constants cast to a pointer type.
134
135 for (BasicBlock &BB : F) {
136 // Skip blocks that aren't successors to an indirectbr we're going to
137 // rewrite.
138 if (!IndirectBrSuccs.count(&BB))
139 continue;
140
141 auto IsBlockAddressUse = [&](const Use &U) {
142 return isa<BlockAddress>(U.getUser());
143 };
144 auto BlockAddressUseIt = llvm::find_if(BB.uses(), IsBlockAddressUse);
145 if (BlockAddressUseIt == BB.use_end())
146 continue;
147
148 assert(std::find_if(std::next(BlockAddressUseIt), BB.use_end(),
149 IsBlockAddressUse) == BB.use_end() &&
150 "There should only ever be a single blockaddress use because it is "
151 "a constant and should be uniqued.");
152
153 auto *BA = cast<BlockAddress>(BlockAddressUseIt->getUser());
154
155 // Skip if the constant was formed but ended up not being used (due to DCE
156 // or whatever).
157 if (!BA->isConstantUsed())
158 continue;
159
160 // Compute the index we want to use for this basic block. We can't use zero
161 // because null can be compared with block addresses.
162 int BBIndex = BBs.size() + 1;
163 BBs.push_back(&BB);
164
165 auto *ITy = cast<IntegerType>(DL.getIntPtrType(BA->getType()));
166 ConstantInt *BBIndexC = ConstantInt::get(ITy, BBIndex);
167
168 // Now rewrite the blockaddress to an integer constant based on the index.
169 // FIXME: This part doesn't properly recognize other uses of blockaddress
170 // expressions, for instance, where they are used to pass labels to
171 // asm-goto. This part of the pass needs a rework.
172 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(BBIndexC, BA->getType()));
173 }
174
175 if (BBs.empty()) {
176 // There are no blocks whose address is taken, so any indirectbr instruction
177 // cannot get a valid input and we can replace all of them with unreachable.
179 if (DTU)
180 Updates.reserve(IndirectBrSuccs.size());
181 for (auto *IBr : IndirectBrs) {
182 if (DTU) {
183 for (BasicBlock *SuccBB : IBr->successors())
184 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
185 }
186 (void)new UnreachableInst(F.getContext(), IBr->getIterator());
187 IBr->eraseFromParent();
188 }
189 if (DTU) {
190 assert(Updates.size() == IndirectBrSuccs.size() &&
191 "Got unexpected update count.");
192 DTU->applyUpdates(Updates);
193 }
194 return true;
195 }
196
197 BasicBlock *SwitchBB;
198 Value *SwitchValue;
199
200 // Compute a common integer type across all the indirectbr instructions.
201 IntegerType *CommonITy = nullptr;
202 for (auto *IBr : IndirectBrs) {
203 auto *ITy =
204 cast<IntegerType>(DL.getIntPtrType(IBr->getAddress()->getType()));
205 if (!CommonITy || ITy->getBitWidth() > CommonITy->getBitWidth())
206 CommonITy = ITy;
207 }
208
209 auto GetSwitchValue = [CommonITy](IndirectBrInst *IBr) {
210 return CastInst::CreatePointerCast(IBr->getAddress(), CommonITy,
211 Twine(IBr->getAddress()->getName()) +
212 ".switch_cast",
213 IBr->getIterator());
214 };
215
217
218 if (IndirectBrs.size() == 1) {
219 // If we only have one indirectbr, we can just directly replace it within
220 // its block.
221 IndirectBrInst *IBr = IndirectBrs[0];
222 SwitchBB = IBr->getParent();
223 SwitchValue = GetSwitchValue(IBr);
224 if (DTU) {
225 Updates.reserve(IndirectBrSuccs.size());
226 for (BasicBlock *SuccBB : IBr->successors())
227 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
228 assert(Updates.size() == IndirectBrSuccs.size() &&
229 "Got unexpected update count.");
230 }
231 IBr->eraseFromParent();
232 } else {
233 // Otherwise we need to create a new block to hold the switch across BBs,
234 // jump to that block instead of each indirectbr, and phi together the
235 // values for the switch.
236 SwitchBB = BasicBlock::Create(F.getContext(), "switch_bb", &F);
237 auto *SwitchPN = PHINode::Create(CommonITy, IndirectBrs.size(),
238 "switch_value_phi", SwitchBB);
239 SwitchValue = SwitchPN;
240
241 // Now replace the indirectbr instructions with direct branches to the
242 // switch block and fill out the PHI operands.
243 if (DTU)
244 Updates.reserve(IndirectBrs.size() + 2 * IndirectBrSuccs.size());
245 for (auto *IBr : IndirectBrs) {
246 SwitchPN->addIncoming(GetSwitchValue(IBr), IBr->getParent());
247 BranchInst::Create(SwitchBB, IBr->getIterator());
248 if (DTU) {
249 Updates.push_back({DominatorTree::Insert, IBr->getParent(), SwitchBB});
250 for (BasicBlock *SuccBB : IBr->successors())
251 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
252 }
253 IBr->eraseFromParent();
254 }
255 }
256
257 // Now build the switch in the block. The block will have no terminator
258 // already.
259 auto *SI = SwitchInst::Create(SwitchValue, BBs[0], BBs.size(), SwitchBB);
260
261 // Add a case for each block.
262 for (int i : llvm::seq<int>(1, BBs.size()))
263 SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
264
265 if (DTU) {
266 // If there were multiple indirectbr's, they may have common successors,
267 // but in the dominator tree, we only track unique edges.
268 SmallPtrSet<BasicBlock *, 8> UniqueSuccessors;
269 Updates.reserve(Updates.size() + BBs.size());
270 for (BasicBlock *BB : BBs) {
271 if (UniqueSuccessors.insert(BB).second)
272 Updates.push_back({DominatorTree::Insert, SwitchBB, BB});
273 }
274 DTU->applyUpdates(Updates);
275 }
276
277 return true;
278}
279
280bool IndirectBrExpandLegacyPass::runOnFunction(Function &F) {
281 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
282 if (!TPC)
283 return false;
284
285 auto &TM = TPC->getTM<TargetMachine>();
286 auto &STI = *TM.getSubtargetImpl(F);
287 if (!STI.enableIndirectBrExpand())
288 return false;
289 auto *TLI = STI.getTargetLowering();
290
291 std::optional<DomTreeUpdater> DTU;
292 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
293 DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
294
295 return runImpl(F, TLI, DTU ? &*DTU : nullptr);
296}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool runImpl(Function &F, const TargetLowering &TLI)
#define DEBUG_TYPE
static bool runImpl(Function &F, const TargetLowering *TLI, DomTreeUpdater *DTU)
#define F(x, y, z)
Definition: MD5.cpp:55
FunctionAnalysisManager FAM
const char LLVMTargetMachineRef TM
#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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallVector class.
Target-Independent Code Generator Pass Configuration Options pass.
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
Represent the analysis usage information of a pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
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
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2231
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
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.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Indirect Branch Instruction.
iterator_range< succ_op_iterator > successors()
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Class to represent integer types.
Definition: DerivedTypes.h:40
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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: 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
size_type size() const
Definition: SmallPtrSet.h:94
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:676
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
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, BasicBlock::iterator InsertBefore)
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:76
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
self_iterator getIterator()
Definition: ilist_node.h:109
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createIndirectBrExpandPass()
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
void initializeIndirectBrExpandLegacyPassPass(PassRegistry &)