LLVM 18.0.0git
Go to the documentation of this file.
1//===-- CallBrPrepare - Prepare callbr for code generation ----------------===//
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
9// This pass lowers callbrs in LLVM IR in order to to assist SelectionDAG's
10// codegen.
12// In particular, this pass assists in inserting register copies for the output
13// values of a callbr along the edges leading to the indirect target blocks.
14// Though the output SSA value is defined by the callbr instruction itself in
15// the IR representation, the value cannot be copied to the appropriate virtual
16// registers prior to jumping to an indirect label, since the jump occurs
17// within the user-provided assembly blob.
19// Instead, those copies must occur separately at the beginning of each
20// indirect target. That requires that we create a separate SSA definition in
21// each of them (via llvm.callbr.landingpad), and may require splitting
22// critical edges so we have a location to place the intrinsic. Finally, we
23// remap users of the original callbr output SSA value to instead point to the
24// appropriate llvm.callbr.landingpad value.
26// Ideally, this could be done inside SelectionDAG, or in the
27// MachineInstruction representation, without the use of an IR-level intrinsic.
28// But, within the current framework, it’s simpler to implement as an IR pass.
29// (If support for callbr in GlobalISel is implemented, it’s worth considering
30// whether this is still required.)
35#include "llvm/ADT/ArrayRef.h"
38#include "llvm/ADT/iterator.h"
39#include "llvm/Analysis/CFG.h"
40#include "llvm/CodeGen/Passes.h"
41#include "llvm/IR/BasicBlock.h"
42#include "llvm/IR/Dominators.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/IRBuilder.h"
47#include "llvm/IR/Intrinsics.h"
49#include "llvm/Pass.h"
53using namespace llvm;
55#define DEBUG_TYPE "callbrprepare"
59 DominatorTree &DT);
60static void UpdateSSA(DominatorTree &DT, CallBrInst *CBR, CallInst *Intrinsic,
61 SSAUpdater &SSAUpdate);
64namespace {
66class CallBrPrepare : public FunctionPass {
68 CallBrPrepare() : FunctionPass(ID) {}
69 void getAnalysisUsage(AnalysisUsage &AU) const override;
70 bool runOnFunction(Function &Fn) override;
71 static char ID;
74} // end anonymous namespace
78 bool Changed = false;
81 if (CBRs.empty())
84 auto &DT = FAM.getResult<DominatorTreeAnalysis>(Fn);
86 Changed |= SplitCriticalEdges(CBRs, DT);
87 Changed |= InsertIntrinsicCalls(CBRs, DT);
89 if (!Changed)
93 return PA;
96char CallBrPrepare::ID = 0;
97INITIALIZE_PASS_BEGIN(CallBrPrepare, DEBUG_TYPE, "Prepare callbr", false, false)
99INITIALIZE_PASS_END(CallBrPrepare, DEBUG_TYPE, "Prepare callbr", false, false)
101FunctionPass *llvm::createCallBrPass() { return new CallBrPrepare(); }
103void CallBrPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
109 for (BasicBlock &BB : Fn)
110 if (auto *CBR = dyn_cast<CallBrInst>(BB.getTerminator()))
111 if (!CBR->getType()->isVoidTy() && !CBR->use_empty())
112 CBRs.push_back(CBR);
113 return CBRs;
117 bool Changed = false;
119 Options.setMergeIdenticalEdges();
121 // The indirect destination might be duplicated between another parameter...
122 // %0 = callbr ... [label %x, label %x]
123 // ...hence MergeIdenticalEdges and AllowIndentical edges, but we don't need
124 // to split the default destination if it's duplicated between an indirect
125 // destination...
126 // %1 = callbr ... to label %x [label %x]
127 // ...hence starting at 1 and checking against successor 0 (aka the default
128 // destination).
129 for (CallBrInst *CBR : CBRs)
130 for (unsigned i = 1, e = CBR->getNumSuccessors(); i != e; ++i)
131 if (CBR->getSuccessor(i) == CBR->getSuccessor(0) ||
132 isCriticalEdge(CBR, i, /*AllowIdenticalEdges*/ true))
133 if (SplitKnownCriticalEdge(CBR, i, Options))
134 Changed = true;
135 return Changed;
139 bool Changed = false;
141 IRBuilder<> Builder(CBRs[0]->getContext());
142 for (CallBrInst *CBR : CBRs) {
143 if (!CBR->getNumIndirectDests())
144 continue;
146 SSAUpdater SSAUpdate;
147 SSAUpdate.Initialize(CBR->getType(), CBR->getName());
148 SSAUpdate.AddAvailableValue(CBR->getParent(), CBR);
149 SSAUpdate.AddAvailableValue(CBR->getDefaultDest(), CBR);
151 for (BasicBlock *IndDest : CBR->getIndirectDests()) {
152 if (!Visited.insert(IndDest).second)
153 continue;
154 Builder.SetInsertPoint(&*IndDest->begin());
155 CallInst *Intrinsic = Builder.CreateIntrinsic(
156 CBR->getType(), Intrinsic::callbr_landingpad, {CBR});
157 SSAUpdate.AddAvailableValue(IndDest, Intrinsic);
158 UpdateSSA(DT, CBR, Intrinsic, SSAUpdate);
159 Changed = true;
160 }
161 }
162 return Changed;
165static bool IsInSameBasicBlock(const Use &U, const BasicBlock *BB) {
166 const auto *I = dyn_cast<Instruction>(U.getUser());
167 return I && I->getParent() == BB;
170#ifndef NDEBUG
171static void PrintDebugDomInfo(const DominatorTree &DT, const Use &U,
172 const BasicBlock *BB, bool IsDefaultDest) {
173 if (!isa<Instruction>(U.getUser()))
174 return;
175 LLVM_DEBUG(dbgs() << "Use: " << *U.getUser() << ", in block "
176 << cast<Instruction>(U.getUser())->getParent()->getName()
177 << ", is " << (DT.dominates(BB, U) ? "" : "NOT ")
178 << "dominated by " << BB->getName() << " ("
179 << (IsDefaultDest ? "in" : "") << "direct)\n");
183void UpdateSSA(DominatorTree &DT, CallBrInst *CBR, CallInst *Intrinsic,
184 SSAUpdater &SSAUpdate) {
186 SmallPtrSet<Use *, 4> Visited;
187 BasicBlock *DefaultDest = CBR->getDefaultDest();
188 BasicBlock *LandingPad = Intrinsic->getParent();
191 for (Use *U : Uses) {
192 if (!Visited.insert(U).second)
193 continue;
195#ifndef NDEBUG
196 PrintDebugDomInfo(DT, *U, LandingPad, /*IsDefaultDest*/ false);
197 PrintDebugDomInfo(DT, *U, DefaultDest, /*IsDefaultDest*/ true);
200 // Don't rewrite the use in the newly inserted intrinsic.
201 if (const auto *II = dyn_cast<IntrinsicInst>(U->getUser()))
202 if (II->getIntrinsicID() == Intrinsic::callbr_landingpad)
203 continue;
205 // If the Use is in the same BasicBlock as the Intrinsic call, replace
206 // the Use with the value of the Intrinsic call.
207 if (IsInSameBasicBlock(*U, LandingPad)) {
208 U->set(Intrinsic);
209 continue;
210 }
212 // If the Use is dominated by the default dest, do not touch it.
213 if (DT.dominates(DefaultDest, *U))
214 continue;
216 SSAUpdate.RewriteUse(*U);
217 }
220bool CallBrPrepare::runOnFunction(Function &Fn) {
221 bool Changed = false;
224 if (CBRs.empty())
225 return Changed;
227 // It's highly likely that most programs do not contain CallBrInsts. Follow a
228 // similar pattern from SafeStackLegacyPass::runOnFunction to reuse previous
229 // domtree analysis if available, otherwise compute it lazily. This avoids
230 // forcing Dominator Tree Construction at -O0 for programs that likely do not
231 // contain CallBrInsts. It does pessimize programs with callbr at higher
232 // optimization levels, as the DominatorTree created here is not reused by
233 // subsequent passes.
234 DominatorTree *DT;
235 std::optional<DominatorTree> LazilyComputedDomTree;
236 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>())
237 DT = &DTWP->getDomTree();
238 else {
239 LazilyComputedDomTree.emplace(Fn);
240 DT = &*LazilyComputedDomTree;
241 }
243 if (SplitCriticalEdges(CBRs, *DT))
244 Changed = true;
246 if (InsertIntrinsicCalls(CBRs, *DT))
247 Changed = true;
249 return Changed;
static bool InsertIntrinsicCalls(ArrayRef< CallBrInst * > CBRs, DominatorTree &DT)
static bool SplitCriticalEdges(ArrayRef< CallBrInst * > CBRs, DominatorTree &DT)
static bool IsInSameBasicBlock(const Use &U, const BasicBlock *BB)
static void UpdateSSA(DominatorTree &DT, CallBrInst *CBR, CallInst *Intrinsic, SSAUpdater &SSAUpdate)
static void PrintDebugDomInfo(const DominatorTree &DT, const Use &U, const BasicBlock *BB, bool IsDefaultDest)
static SmallVector< CallBrInst *, 2 > FindCallBrs(Function &Fn)
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Rewrite Partial Register Uses
#define DEBUG_TYPE
static LVOptions Options
Definition: LVOptions.cpp:25
#define I(x, y, z)
Definition: MD5.cpp:58
FunctionAnalysisManager FAM
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
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
Represent the analysis usage information of a pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
BasicBlock * getDefaultDest() const
PreservedAnalyses run(Function &Fn, FunctionAnalysisManager &FAM)
This class represents a function call, abstracting a target machine's calling convention.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:277
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:312
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:164
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:123
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.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Definition: IRBuilder.cpp:930
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2639
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: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:193
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:188
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
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
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
iterator_range< use_iterator > uses()
Definition: Value.h:376
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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
BasicBlock * SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If it is known that an edge is critical, SplitKnownCriticalEdge can be called directly,...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:363
FunctionPass * createCallBrPass()
Option class for critical edge splitting.