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"
30 #include "llvm/ADT/SmallVector.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"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
43 #include <optional>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "indirectbr-expand"
48 
49 namespace {
50 
51 class IndirectBrExpandPass : public FunctionPass {
52  const TargetLowering *TLI = nullptr;
53 
54 public:
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 
71 
72 INITIALIZE_PASS_BEGIN(IndirectBrExpandPass, DEBUG_TYPE,
73  "Expand indirectbr instructions", false, false)
75 INITIALIZE_PASS_END(IndirectBrExpandPass, DEBUG_TYPE,
76  "Expand indirectbr instructions", false, false)
77 
79  return new IndirectBrExpandPass();
80 }
81 
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 }
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
llvm::Function
Definition: Function.h:59
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::SwitchInst::Create
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3472
ErrorHandling.h
DomTreeUpdater.h
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:258
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
Sequence.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
TargetMachine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
llvm::ConstantExpr::getIntToPtr
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2215
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3510
llvm::initializeIndirectBrExpandPassPass
void initializeIndirectBrExpandPassPass(PassRegistry &)
SI
@ SI
Definition: SIInstrInfo.cpp:7993
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
llvm::ConstantInt::get
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:887
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
BasicBlock.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3195
TargetPassConfig.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TargetMachine
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:78
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(IndirectBrExpandPass, DEBUG_TYPE, "Expand indirectbr instructions", false, false) INITIALIZE_PASS_END(IndirectBrExpandPass
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::IndirectBrInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3782
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::createIndirectBrExpandPass
FunctionPass * createIndirectBrExpandPass()
Definition: IndirectBrExpandPass.cpp:78
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::find_if
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:1762
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::PHINode::Create
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...
Definition: Instructions.h:2750
Function.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: IndirectBrExpandPass.cpp:47
llvm::IndirectBrInst
Indirect Branch Instruction.
Definition: Instructions.h:3679
Instructions.h
SmallVector.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:90
llvm::IntegerType::getBitWidth
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
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
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4773
llvm::CastInst::CreatePointerCast
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
Definition: Instructions.cpp:3446
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:259
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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