LLVM 17.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"
34#include "llvm/IR/BasicBlock.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/Function.h"
40#include "llvm/Pass.h"
43#include <optional>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "indirectbr-expand"
48
49namespace {
50
51class IndirectBrExpandPass : public FunctionPass {
52 const TargetLowering *TLI = nullptr;
53
54public:
55 static char ID; // Pass identification, replacement for typeid
56
57 IndirectBrExpandPass() : FunctionPass(ID) {
59 }
60
61 void getAnalysisUsage(AnalysisUsage &AU) const override {
63 }
64
65 bool runOnFunction(Function &F) override;
66};
67
68} // end anonymous namespace
69
70char IndirectBrExpandPass::ID = 0;
71
72INITIALIZE_PASS_BEGIN(IndirectBrExpandPass, DEBUG_TYPE,
73 "Expand indirectbr instructions", false, false)
75INITIALIZE_PASS_END(IndirectBrExpandPass, DEBUG_TYPE,
76 "Expand indirectbr instructions", false, false)
77
79 return new IndirectBrExpandPass();
80}
81
82bool IndirectBrExpandPass::runOnFunction(Function &F) {
83 auto &DL = F.getParent()->getDataLayout();
84 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
85 if (!TPC)
86 return false;
87
88 auto &TM = TPC->getTM<TargetMachine>();
89 auto &STI = *TM.getSubtargetImpl(F);
90 if (!STI.enableIndirectBrExpand())
91 return false;
92 TLI = STI.getTargetLowering();
93
94 std::optional<DomTreeUpdater> DTU;
95 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
96 DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
97
99
100 // Set of all potential successors for indirectbr instructions.
101 SmallPtrSet<BasicBlock *, 4> IndirectBrSuccs;
102
103 // Build a list of indirectbrs that we want to rewrite.
104 for (BasicBlock &BB : F)
105 if (auto *IBr = dyn_cast<IndirectBrInst>(BB.getTerminator())) {
106 // Handle the degenerate case of no successors by replacing the indirectbr
107 // with unreachable as there is no successor available.
108 if (IBr->getNumSuccessors() == 0) {
109 (void)new UnreachableInst(F.getContext(), IBr);
110 IBr->eraseFromParent();
111 continue;
112 }
113
114 IndirectBrs.push_back(IBr);
115 for (BasicBlock *SuccBB : IBr->successors())
116 IndirectBrSuccs.insert(SuccBB);
117 }
118
119 if (IndirectBrs.empty())
120 return false;
121
122 // If we need to replace any indirectbrs we need to establish integer
123 // constants that will correspond to each of the basic blocks in the function
124 // whose address escapes. We do that here and rewrite all the blockaddress
125 // constants to just be those integer constants cast to a pointer type.
127
128 for (BasicBlock &BB : F) {
129 // Skip blocks that aren't successors to an indirectbr we're going to
130 // rewrite.
131 if (!IndirectBrSuccs.count(&BB))
132 continue;
133
134 auto IsBlockAddressUse = [&](const Use &U) {
135 return isa<BlockAddress>(U.getUser());
136 };
137 auto BlockAddressUseIt = llvm::find_if(BB.uses(), IsBlockAddressUse);
138 if (BlockAddressUseIt == BB.use_end())
139 continue;
140
141 assert(std::find_if(std::next(BlockAddressUseIt), BB.use_end(),
142 IsBlockAddressUse) == BB.use_end() &&
143 "There should only ever be a single blockaddress use because it is "
144 "a constant and should be uniqued.");
145
146 auto *BA = cast<BlockAddress>(BlockAddressUseIt->getUser());
147
148 // Skip if the constant was formed but ended up not being used (due to DCE
149 // or whatever).
150 if (!BA->isConstantUsed())
151 continue;
152
153 // Compute the index we want to use for this basic block. We can't use zero
154 // because null can be compared with block addresses.
155 int BBIndex = BBs.size() + 1;
156 BBs.push_back(&BB);
157
158 auto *ITy = cast<IntegerType>(DL.getIntPtrType(BA->getType()));
159 ConstantInt *BBIndexC = ConstantInt::get(ITy, BBIndex);
160
161 // Now rewrite the blockaddress to an integer constant based on the index.
162 // FIXME: This part doesn't properly recognize other uses of blockaddress
163 // expressions, for instance, where they are used to pass labels to
164 // asm-goto. This part of the pass needs a rework.
165 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(BBIndexC, BA->getType()));
166 }
167
168 if (BBs.empty()) {
169 // There are no blocks whose address is taken, so any indirectbr instruction
170 // cannot get a valid input and we can replace all of them with unreachable.
172 if (DTU)
173 Updates.reserve(IndirectBrSuccs.size());
174 for (auto *IBr : IndirectBrs) {
175 if (DTU) {
176 for (BasicBlock *SuccBB : IBr->successors())
177 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
178 }
179 (void)new UnreachableInst(F.getContext(), IBr);
180 IBr->eraseFromParent();
181 }
182 if (DTU) {
183 assert(Updates.size() == IndirectBrSuccs.size() &&
184 "Got unexpected update count.");
185 DTU->applyUpdates(Updates);
186 }
187 return true;
188 }
189
190 BasicBlock *SwitchBB;
191 Value *SwitchValue;
192
193 // Compute a common integer type across all the indirectbr instructions.
194 IntegerType *CommonITy = nullptr;
195 for (auto *IBr : IndirectBrs) {
196 auto *ITy =
197 cast<IntegerType>(DL.getIntPtrType(IBr->getAddress()->getType()));
198 if (!CommonITy || ITy->getBitWidth() > CommonITy->getBitWidth())
199 CommonITy = ITy;
200 }
201
202 auto GetSwitchValue = [CommonITy](IndirectBrInst *IBr) {
204 IBr->getAddress(), CommonITy,
205 Twine(IBr->getAddress()->getName()) + ".switch_cast", IBr);
206 };
207
209
210 if (IndirectBrs.size() == 1) {
211 // If we only have one indirectbr, we can just directly replace it within
212 // its block.
213 IndirectBrInst *IBr = IndirectBrs[0];
214 SwitchBB = IBr->getParent();
215 SwitchValue = GetSwitchValue(IBr);
216 if (DTU) {
217 Updates.reserve(IndirectBrSuccs.size());
218 for (BasicBlock *SuccBB : IBr->successors())
219 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
220 assert(Updates.size() == IndirectBrSuccs.size() &&
221 "Got unexpected update count.");
222 }
223 IBr->eraseFromParent();
224 } else {
225 // Otherwise we need to create a new block to hold the switch across BBs,
226 // jump to that block instead of each indirectbr, and phi together the
227 // values for the switch.
228 SwitchBB = BasicBlock::Create(F.getContext(), "switch_bb", &F);
229 auto *SwitchPN = PHINode::Create(CommonITy, IndirectBrs.size(),
230 "switch_value_phi", SwitchBB);
231 SwitchValue = SwitchPN;
232
233 // Now replace the indirectbr instructions with direct branches to the
234 // switch block and fill out the PHI operands.
235 if (DTU)
236 Updates.reserve(IndirectBrs.size() + 2 * IndirectBrSuccs.size());
237 for (auto *IBr : IndirectBrs) {
238 SwitchPN->addIncoming(GetSwitchValue(IBr), IBr->getParent());
239 BranchInst::Create(SwitchBB, IBr);
240 if (DTU) {
241 Updates.push_back({DominatorTree::Insert, IBr->getParent(), SwitchBB});
242 for (BasicBlock *SuccBB : IBr->successors())
243 Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
244 }
245 IBr->eraseFromParent();
246 }
247 }
248
249 // Now build the switch in the block. The block will have no terminator
250 // already.
251 auto *SI = SwitchInst::Create(SwitchValue, BBs[0], BBs.size(), SwitchBB);
252
253 // Add a case for each block.
254 for (int i : llvm::seq<int>(1, BBs.size()))
255 SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
256
257 if (DTU) {
258 // If there were multiple indirectbr's, they may have common successors,
259 // but in the dominator tree, we only track unique edges.
260 SmallPtrSet<BasicBlock *, 8> UniqueSuccessors;
261 Updates.reserve(Updates.size() + BBs.size());
262 for (BasicBlock *BB : BBs) {
263 if (UniqueSuccessors.insert(BB).second)
264 Updates.push_back({DominatorTree::Insert, SwitchBB, BB});
265 }
266 DTU->applyUpdates(Updates);
267 }
268
269 return true;
270}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Expand indirectbr instructions
#define DEBUG_TYPE
#define F(x, y, z)
Definition: MD5.cpp:55
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
@ SI
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.
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:56
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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:2199
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
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.
Definition: Constants.cpp:888
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
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.
Indirect Branch Instruction.
iterator_range< succ_op_iterator > successors()
const BasicBlock * getParent() const
Definition: Instruction.h:90
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
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="", Instruction *InsertBefore=nullptr)
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
size_type size() const
Definition: SmallPtrSet.h:93
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
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:78
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
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()
void initializeIndirectBrExpandPassPass(PassRegistry &)
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:1846