LLVM  15.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 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "indirectbr-expand"
47 
48 namespace {
49 
50 class IndirectBrExpandPass : public FunctionPass {
51  const TargetLowering *TLI = nullptr;
52 
53 public:
54  static char ID; // Pass identification, replacement for typeid
55 
56  IndirectBrExpandPass() : 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 
70 
71 INITIALIZE_PASS_BEGIN(IndirectBrExpandPass, DEBUG_TYPE,
72  "Expand indirectbr instructions", false, false)
74 INITIALIZE_PASS_END(IndirectBrExpandPass, DEBUG_TYPE,
75  "Expand indirectbr instructions", false, false)
76 
78  return new IndirectBrExpandPass();
79 }
80 
82  auto &DL = F.getParent()->getDataLayout();
83  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
84  if (!TPC)
85  return false;
86 
87  auto &TM = TPC->getTM<TargetMachine>();
88  auto &STI = *TM.getSubtargetImpl(F);
89  if (!STI.enableIndirectBrExpand())
90  return false;
91  TLI = STI.getTargetLowering();
92 
94  if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
95  DTU.emplace(DTWP->getDomTree(), DomTreeUpdater::UpdateStrategy::Lazy);
96 
98 
99  // Set of all potential successors for indirectbr instructions.
100  SmallPtrSet<BasicBlock *, 4> IndirectBrSuccs;
101 
102  // Build a list of indirectbrs that we want to rewrite.
103  for (BasicBlock &BB : F)
104  if (auto *IBr = dyn_cast<IndirectBrInst>(BB.getTerminator())) {
105  // Handle the degenerate case of no successors by replacing the indirectbr
106  // with unreachable as there is no successor available.
107  if (IBr->getNumSuccessors() == 0) {
108  (void)new UnreachableInst(F.getContext(), IBr);
109  IBr->eraseFromParent();
110  continue;
111  }
112 
113  IndirectBrs.push_back(IBr);
114  for (BasicBlock *SuccBB : IBr->successors())
115  IndirectBrSuccs.insert(SuccBB);
116  }
117 
118  if (IndirectBrs.empty())
119  return false;
120 
121  // If we need to replace any indirectbrs we need to establish integer
122  // constants that will correspond to each of the basic blocks in the function
123  // whose address escapes. We do that here and rewrite all the blockaddress
124  // constants to just be those integer constants cast to a pointer type.
126 
127  for (BasicBlock &BB : F) {
128  // Skip blocks that aren't successors to an indirectbr we're going to
129  // rewrite.
130  if (!IndirectBrSuccs.count(&BB))
131  continue;
132 
133  auto IsBlockAddressUse = [&](const Use &U) {
134  return isa<BlockAddress>(U.getUser());
135  };
136  auto BlockAddressUseIt = llvm::find_if(BB.uses(), IsBlockAddressUse);
137  if (BlockAddressUseIt == BB.use_end())
138  continue;
139 
140  assert(std::find_if(std::next(BlockAddressUseIt), BB.use_end(),
141  IsBlockAddressUse) == BB.use_end() &&
142  "There should only ever be a single blockaddress use because it is "
143  "a constant and should be uniqued.");
144 
145  auto *BA = cast<BlockAddress>(BlockAddressUseIt->getUser());
146 
147  // Skip if the constant was formed but ended up not being used (due to DCE
148  // or whatever).
149  if (!BA->isConstantUsed())
150  continue;
151 
152  // Compute the index we want to use for this basic block. We can't use zero
153  // because null can be compared with block addresses.
154  int BBIndex = BBs.size() + 1;
155  BBs.push_back(&BB);
156 
157  auto *ITy = cast<IntegerType>(DL.getIntPtrType(BA->getType()));
158  ConstantInt *BBIndexC = ConstantInt::get(ITy, BBIndex);
159 
160  // Now rewrite the blockaddress to an integer constant based on the index.
161  // FIXME: This part doesn't properly recognize other uses of blockaddress
162  // expressions, for instance, where they are used to pass labels to
163  // asm-goto. This part of the pass needs a rework.
164  BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(BBIndexC, BA->getType()));
165  }
166 
167  if (BBs.empty()) {
168  // There are no blocks whose address is taken, so any indirectbr instruction
169  // cannot get a valid input and we can replace all of them with unreachable.
171  if (DTU)
172  Updates.reserve(IndirectBrSuccs.size());
173  for (auto *IBr : IndirectBrs) {
174  if (DTU) {
175  for (BasicBlock *SuccBB : IBr->successors())
176  Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
177  }
178  (void)new UnreachableInst(F.getContext(), IBr);
179  IBr->eraseFromParent();
180  }
181  if (DTU) {
182  assert(Updates.size() == IndirectBrSuccs.size() &&
183  "Got unexpected update count.");
184  DTU->applyUpdates(Updates);
185  }
186  return true;
187  }
188 
189  BasicBlock *SwitchBB;
190  Value *SwitchValue;
191 
192  // Compute a common integer type across all the indirectbr instructions.
193  IntegerType *CommonITy = nullptr;
194  for (auto *IBr : IndirectBrs) {
195  auto *ITy =
196  cast<IntegerType>(DL.getIntPtrType(IBr->getAddress()->getType()));
197  if (!CommonITy || ITy->getBitWidth() > CommonITy->getBitWidth())
198  CommonITy = ITy;
199  }
200 
201  auto GetSwitchValue = [DL, CommonITy](IndirectBrInst *IBr) {
203  IBr->getAddress(), CommonITy,
204  Twine(IBr->getAddress()->getName()) + ".switch_cast", IBr);
205  };
206 
208 
209  if (IndirectBrs.size() == 1) {
210  // If we only have one indirectbr, we can just directly replace it within
211  // its block.
212  IndirectBrInst *IBr = IndirectBrs[0];
213  SwitchBB = IBr->getParent();
214  SwitchValue = GetSwitchValue(IBr);
215  if (DTU) {
216  Updates.reserve(IndirectBrSuccs.size());
217  for (BasicBlock *SuccBB : IBr->successors())
218  Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
219  assert(Updates.size() == IndirectBrSuccs.size() &&
220  "Got unexpected update count.");
221  }
222  IBr->eraseFromParent();
223  } else {
224  // Otherwise we need to create a new block to hold the switch across BBs,
225  // jump to that block instead of each indirectbr, and phi together the
226  // values for the switch.
227  SwitchBB = BasicBlock::Create(F.getContext(), "switch_bb", &F);
228  auto *SwitchPN = PHINode::Create(CommonITy, IndirectBrs.size(),
229  "switch_value_phi", SwitchBB);
230  SwitchValue = SwitchPN;
231 
232  // Now replace the indirectbr instructions with direct branches to the
233  // switch block and fill out the PHI operands.
234  if (DTU)
235  Updates.reserve(IndirectBrs.size() + 2 * IndirectBrSuccs.size());
236  for (auto *IBr : IndirectBrs) {
237  SwitchPN->addIncoming(GetSwitchValue(IBr), IBr->getParent());
238  BranchInst::Create(SwitchBB, IBr);
239  if (DTU) {
240  Updates.push_back({DominatorTree::Insert, IBr->getParent(), SwitchBB});
241  for (BasicBlock *SuccBB : IBr->successors())
242  Updates.push_back({DominatorTree::Delete, IBr->getParent(), SuccBB});
243  }
244  IBr->eraseFromParent();
245  }
246  }
247 
248  // Now build the switch in the block. The block will have no terminator
249  // already.
250  auto *SI = SwitchInst::Create(SwitchValue, BBs[0], BBs.size(), SwitchBB);
251 
252  // Add a case for each block.
253  for (int i : llvm::seq<int>(1, BBs.size()))
254  SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
255 
256  if (DTU) {
257  // If there were multiple indirectbr's, they may have common successors,
258  // but in the dominator tree, we only track unique edges.
259  SmallPtrSet<BasicBlock *, 8> UniqueSuccessors;
260  Updates.reserve(Updates.size() + BBs.size());
261  for (BasicBlock *BB : BBs) {
262  if (UniqueSuccessors.insert(BB).second)
263  Updates.push_back({DominatorTree::Insert, SwitchBB, BB});
264  }
265  DTU->applyUpdates(Updates);
266  }
267 
268  return true;
269 }
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::Function
Definition: Function.h:60
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:1185
llvm::SwitchInst::Create
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3419
ErrorHandling.h
DomTreeUpdater.h
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::Optional
Definition: APInt.h:33
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:79
TargetMachine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::ConstantExpr::getIntToPtr
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2243
llvm::TargetLowering
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Definition: TargetLowering.h:3412
llvm::initializeIndirectBrExpandPassPass
void initializeIndirectBrExpandPassPass(PassRegistry &)
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:302
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:926
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:58
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:77
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:287
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3142
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:77
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:3731
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:97
TargetSubtargetInfo.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::createIndirectBrExpandPass
FunctionPass * createIndirectBrExpandPass()
Definition: IndirectBrExpandPass.cpp:77
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:1644
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
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:2693
Function.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: IndirectBrExpandPass.cpp:46
llvm::IndirectBrInst
Indirect Branch Instruction.
Definition: Instructions.h:3628
Instructions.h
SmallVector.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
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:4727
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:3274
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38