LLVM  9.0.0svn
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"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/IRBuilder.h"
36 #include "llvm/IR/InstIterator.h"
37 #include "llvm/IR/Instruction.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/Debug.h"
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  bool runOnFunction(Function &F) override;
62 };
63 
64 } // end anonymous namespace
65 
67 
68 INITIALIZE_PASS(IndirectBrExpandPass, DEBUG_TYPE,
69  "Expand indirectbr instructions", false, false)
70 
72  return new IndirectBrExpandPass();
73 }
74 
76  auto &DL = F.getParent()->getDataLayout();
77  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
78  if (!TPC)
79  return false;
80 
81  auto &TM = TPC->getTM<TargetMachine>();
82  auto &STI = *TM.getSubtargetImpl(F);
83  if (!STI.enableIndirectBrExpand())
84  return false;
85  TLI = STI.getTargetLowering();
86 
88 
89  // Set of all potential successors for indirectbr instructions.
90  SmallPtrSet<BasicBlock *, 4> IndirectBrSuccs;
91 
92  // Build a list of indirectbrs that we want to rewrite.
93  for (BasicBlock &BB : F)
94  if (auto *IBr = dyn_cast<IndirectBrInst>(BB.getTerminator())) {
95  // Handle the degenerate case of no successors by replacing the indirectbr
96  // with unreachable as there is no successor available.
97  if (IBr->getNumSuccessors() == 0) {
98  (void)new UnreachableInst(F.getContext(), IBr);
99  IBr->eraseFromParent();
100  continue;
101  }
102 
103  IndirectBrs.push_back(IBr);
104  for (BasicBlock *SuccBB : IBr->successors())
105  IndirectBrSuccs.insert(SuccBB);
106  }
107 
108  if (IndirectBrs.empty())
109  return false;
110 
111  // If we need to replace any indirectbrs we need to establish integer
112  // constants that will correspond to each of the basic blocks in the function
113  // whose address escapes. We do that here and rewrite all the blockaddress
114  // constants to just be those integer constants cast to a pointer type.
116 
117  for (BasicBlock &BB : F) {
118  // Skip blocks that aren't successors to an indirectbr we're going to
119  // rewrite.
120  if (!IndirectBrSuccs.count(&BB))
121  continue;
122 
123  auto IsBlockAddressUse = [&](const Use &U) {
124  return isa<BlockAddress>(U.getUser());
125  };
126  auto BlockAddressUseIt = llvm::find_if(BB.uses(), IsBlockAddressUse);
127  if (BlockAddressUseIt == BB.use_end())
128  continue;
129 
130  assert(std::find_if(std::next(BlockAddressUseIt), BB.use_end(),
131  IsBlockAddressUse) == BB.use_end() &&
132  "There should only ever be a single blockaddress use because it is "
133  "a constant and should be uniqued.");
134 
135  auto *BA = cast<BlockAddress>(BlockAddressUseIt->getUser());
136 
137  // Skip if the constant was formed but ended up not being used (due to DCE
138  // or whatever).
139  if (!BA->isConstantUsed())
140  continue;
141 
142  // Compute the index we want to use for this basic block. We can't use zero
143  // because null can be compared with block addresses.
144  int BBIndex = BBs.size() + 1;
145  BBs.push_back(&BB);
146 
147  auto *ITy = cast<IntegerType>(DL.getIntPtrType(BA->getType()));
148  ConstantInt *BBIndexC = ConstantInt::get(ITy, BBIndex);
149 
150  // Now rewrite the blockaddress to an integer constant based on the index.
151  // FIXME: This part doesn't properly recognize other uses of blockaddress
152  // expressions, for instance, where they are used to pass labels to
153  // asm-goto. This part of the pass needs a rework.
154  BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(BBIndexC, BA->getType()));
155  }
156 
157  if (BBs.empty()) {
158  // There are no blocks whose address is taken, so any indirectbr instruction
159  // cannot get a valid input and we can replace all of them with unreachable.
160  for (auto *IBr : IndirectBrs) {
161  (void)new UnreachableInst(F.getContext(), IBr);
162  IBr->eraseFromParent();
163  }
164  return true;
165  }
166 
167  BasicBlock *SwitchBB;
168  Value *SwitchValue;
169 
170  // Compute a common integer type across all the indirectbr instructions.
171  IntegerType *CommonITy = nullptr;
172  for (auto *IBr : IndirectBrs) {
173  auto *ITy =
174  cast<IntegerType>(DL.getIntPtrType(IBr->getAddress()->getType()));
175  if (!CommonITy || ITy->getBitWidth() > CommonITy->getBitWidth())
176  CommonITy = ITy;
177  }
178 
179  auto GetSwitchValue = [DL, CommonITy](IndirectBrInst *IBr) {
181  IBr->getAddress(), CommonITy,
182  Twine(IBr->getAddress()->getName()) + ".switch_cast", IBr);
183  };
184 
185  if (IndirectBrs.size() == 1) {
186  // If we only have one indirectbr, we can just directly replace it within
187  // its block.
188  SwitchBB = IndirectBrs[0]->getParent();
189  SwitchValue = GetSwitchValue(IndirectBrs[0]);
190  IndirectBrs[0]->eraseFromParent();
191  } else {
192  // Otherwise we need to create a new block to hold the switch across BBs,
193  // jump to that block instead of each indirectbr, and phi together the
194  // values for the switch.
195  SwitchBB = BasicBlock::Create(F.getContext(), "switch_bb", &F);
196  auto *SwitchPN = PHINode::Create(CommonITy, IndirectBrs.size(),
197  "switch_value_phi", SwitchBB);
198  SwitchValue = SwitchPN;
199 
200  // Now replace the indirectbr instructions with direct branches to the
201  // switch block and fill out the PHI operands.
202  for (auto *IBr : IndirectBrs) {
203  SwitchPN->addIncoming(GetSwitchValue(IBr), IBr->getParent());
204  BranchInst::Create(SwitchBB, IBr);
205  IBr->eraseFromParent();
206  }
207  }
208 
209  // Now build the switch in the block. The block will have no terminator
210  // already.
211  auto *SI = SwitchInst::Create(SwitchValue, BBs[0], BBs.size(), SwitchBB);
212 
213  // Add a case for each block.
214  for (int i : llvm::seq<int>(1, BBs.size()))
215  SI->addCase(ConstantInt::get(CommonITy, i + 1), BBs[i]);
216 
217  return true;
218 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:171
This routine provides some synthesis utilities to produce sequences of values.
void initializeIndirectBrExpandPassPass(PassRegistry &)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1769
F(f)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:66
static bool runOnFunction(Function &F, bool PostInlining)
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This function has undefined behavior.
Indirect Branch Instruction.
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:370
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
Class to represent integer types.
Definition: DerivedTypes.h:40
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1220
size_t size() const
Definition: SmallVector.h:52
FunctionPass * createIndirectBrExpandPass()
#define DEBUG_TYPE
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, Instruction *InsertBefore=nullptr)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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:631
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
INITIALIZE_PASS(IndirectBrExpandPass, DEBUG_TYPE, "Expand indirectbr instructions", false, false) FunctionPass *llvm
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:72
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65