LLVM  10.0.0svn
CoroElide.cpp
Go to the documentation of this file.
1 //===- CoroElide.cpp - Coroutine Frame Allocation Elision Pass ------------===//
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 // This pass replaces dynamic allocation of coroutine frame with alloca and
9 // replaces calls to llvm.coro.resume and llvm.coro.destroy with direct calls
10 // to coroutine sub-functions.
11 //===----------------------------------------------------------------------===//
12 
13 #include "CoroInternal.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/Pass.h"
20 
21 using namespace llvm;
22 
23 #define DEBUG_TYPE "coro-elide"
24 
25 namespace {
26 // Created on demand if CoroElide pass has work to do.
27 struct Lowerer : coro::LowererBase {
34 
35  Lowerer(Module &M) : LowererBase(M) {}
36 
37  void elideHeapAllocations(Function *F, Type *FrameTy, AAResults &AA);
38  bool shouldElide(Function *F, DominatorTree &DT) const;
39  bool processCoroId(CoroIdInst *, AAResults &AA, DominatorTree &DT);
40 };
41 } // end anonymous namespace
42 
43 // Go through the list of coro.subfn.addr intrinsics and replace them with the
44 // provided constant.
47  if (Users.empty())
48  return;
49 
50  // See if we need to bitcast the constant to match the type of the intrinsic
51  // being replaced. Note: All coro.subfn.addr intrinsics return the same type,
52  // so we only need to examine the type of the first one in the list.
53  Type *IntrTy = Users.front()->getType();
54  Type *ValueTy = Value->getType();
55  if (ValueTy != IntrTy) {
56  // May need to tweak the function type to match the type expected at the
57  // use site.
58  assert(ValueTy->isPointerTy() && IntrTy->isPointerTy());
59  Value = ConstantExpr::getBitCast(Value, IntrTy);
60  }
61 
62  // Now the value type matches the type of the intrinsic. Replace them all!
63  for (CoroSubFnInst *I : Users)
65 }
66 
67 // See if any operand of the call instruction references the coroutine frame.
68 static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA) {
69  for (Value *Op : CI->operand_values())
70  if (AA.alias(Op, Frame) != NoAlias)
71  return true;
72  return false;
73 }
74 
75 // Look for any tail calls referencing the coroutine frame and remove tail
76 // attribute from them, since now coroutine frame resides on the stack and tail
77 // call implies that the function does not references anything on the stack.
78 static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA) {
79  Function &F = *Frame->getFunction();
80  for (Instruction &I : instructions(F))
81  if (auto *Call = dyn_cast<CallInst>(&I))
82  if (Call->isTailCall() && operandReferences(Call, Frame, AA)) {
83  // FIXME: If we ever hit this check. Evaluate whether it is more
84  // appropriate to retain musttail and allow the code to compile.
85  if (Call->isMustTailCall())
86  report_fatal_error("Call referring to the coroutine frame cannot be "
87  "marked as musttail");
88  Call->setTailCall(false);
89  }
90 }
91 
92 // Given a resume function @f.resume(%f.frame* %frame), returns %f.frame type.
93 static Type *getFrameType(Function *Resume) {
94  auto *ArgType = Resume->arg_begin()->getType();
95  return cast<PointerType>(ArgType)->getElementType();
96 }
97 
98 // Finds first non alloca instruction in the entry block of a function.
100  for (Instruction &I : F->getEntryBlock())
101  if (!isa<AllocaInst>(&I))
102  return &I;
103  llvm_unreachable("no terminator in the entry block");
104 }
105 
106 // To elide heap allocations we need to suppress code blocks guarded by
107 // llvm.coro.alloc and llvm.coro.free instructions.
108 void Lowerer::elideHeapAllocations(Function *F, Type *FrameTy, AAResults &AA) {
109  LLVMContext &C = FrameTy->getContext();
110  auto *InsertPt =
111  getFirstNonAllocaInTheEntryBlock(CoroIds.front()->getFunction());
112 
113  // Replacing llvm.coro.alloc with false will suppress dynamic
114  // allocation as it is expected for the frontend to generate the code that
115  // looks like:
116  // id = coro.id(...)
117  // mem = coro.alloc(id) ? malloc(coro.size()) : 0;
118  // coro.begin(id, mem)
119  auto *False = ConstantInt::getFalse(C);
120  for (auto *CA : CoroAllocs) {
121  CA->replaceAllUsesWith(False);
122  CA->eraseFromParent();
123  }
124 
125  // FIXME: Design how to transmit alignment information for every alloca that
126  // is spilled into the coroutine frame and recreate the alignment information
127  // here. Possibly we will need to do a mini SROA here and break the coroutine
128  // frame into individual AllocaInst recreating the original alignment.
129  const DataLayout &DL = F->getParent()->getDataLayout();
130  auto *Frame = new AllocaInst(FrameTy, DL.getAllocaAddrSpace(), "", InsertPt);
131  auto *FrameVoidPtr =
132  new BitCastInst(Frame, Type::getInt8PtrTy(C), "vFrame", InsertPt);
133 
134  for (auto *CB : CoroBegins) {
135  CB->replaceAllUsesWith(FrameVoidPtr);
136  CB->eraseFromParent();
137  }
138 
139  // Since now coroutine frame lives on the stack we need to make sure that
140  // any tail call referencing it, must be made non-tail call.
141  removeTailCallAttribute(Frame, AA);
142 }
143 
144 bool Lowerer::shouldElide(Function *F, DominatorTree &DT) const {
145  // If no CoroAllocs, we cannot suppress allocation, so elision is not
146  // possible.
147  if (CoroAllocs.empty())
148  return false;
149 
150  // Check that for every coro.begin there is a coro.destroy directly
151  // referencing the SSA value of that coro.begin along a non-exceptional path.
152  // If the value escaped, then coro.destroy would have been referencing a
153  // memory location storing that value and not the virtual register.
154 
155  // First gather all of the non-exceptional terminators for the function.
156  SmallPtrSet<Instruction *, 8> Terminators;
157  for (BasicBlock &B : *F) {
158  auto *TI = B.getTerminator();
159  if (TI->getNumSuccessors() == 0 && !TI->isExceptionalTerminator() &&
160  !isa<UnreachableInst>(TI))
161  Terminators.insert(TI);
162  }
163 
164  // Filter out the coro.destroy that lie along exceptional paths.
166  for (CoroSubFnInst *DA : DestroyAddr) {
167  for (Instruction *TI : Terminators) {
168  if (DT.dominates(DA, TI)) {
169  DAs.insert(DA);
170  break;
171  }
172  }
173  }
174 
175  // Find all the coro.begin referenced by coro.destroy along happy paths.
176  SmallPtrSet<CoroBeginInst *, 8> ReferencedCoroBegins;
177  for (CoroSubFnInst *DA : DAs) {
178  if (auto *CB = dyn_cast<CoroBeginInst>(DA->getFrame()))
179  ReferencedCoroBegins.insert(CB);
180  else
181  return false;
182  }
183 
184  // If size of the set is the same as total number of coro.begin, that means we
185  // found a coro.free or coro.destroy referencing each coro.begin, so we can
186  // perform heap elision.
187  return ReferencedCoroBegins.size() == CoroBegins.size();
188 }
189 
190 bool Lowerer::processCoroId(CoroIdInst *CoroId, AAResults &AA,
191  DominatorTree &DT) {
192  CoroBegins.clear();
193  CoroAllocs.clear();
194  CoroFrees.clear();
195  ResumeAddr.clear();
196  DestroyAddr.clear();
197 
198  // Collect all coro.begin and coro.allocs associated with this coro.id.
199  for (User *U : CoroId->users()) {
200  if (auto *CB = dyn_cast<CoroBeginInst>(U))
201  CoroBegins.push_back(CB);
202  else if (auto *CA = dyn_cast<CoroAllocInst>(U))
203  CoroAllocs.push_back(CA);
204  else if (auto *CF = dyn_cast<CoroFreeInst>(U))
205  CoroFrees.push_back(CF);
206  }
207 
208  // Collect all coro.subfn.addrs associated with coro.begin.
209  // Note, we only devirtualize the calls if their coro.subfn.addr refers to
210  // coro.begin directly. If we run into cases where this check is too
211  // conservative, we can consider relaxing the check.
212  for (CoroBeginInst *CB : CoroBegins) {
213  for (User *U : CB->users())
214  if (auto *II = dyn_cast<CoroSubFnInst>(U))
215  switch (II->getIndex()) {
217  ResumeAddr.push_back(II);
218  break;
220  DestroyAddr.push_back(II);
221  break;
222  default:
223  llvm_unreachable("unexpected coro.subfn.addr constant");
224  }
225  }
226 
227  // PostSplit coro.id refers to an array of subfunctions in its Info
228  // argument.
229  ConstantArray *Resumers = CoroId->getInfo().Resumers;
230  assert(Resumers && "PostSplit coro.id Info argument must refer to an array"
231  "of coroutine subfunctions");
232  auto *ResumeAddrConstant =
234 
235  replaceWithConstant(ResumeAddrConstant, ResumeAddr);
236 
237  bool ShouldElide = shouldElide(CoroId->getFunction(), DT);
238 
239  auto *DestroyAddrConstant = ConstantExpr::getExtractValue(
240  Resumers,
242 
243  replaceWithConstant(DestroyAddrConstant, DestroyAddr);
244 
245  if (ShouldElide) {
246  auto *FrameTy = getFrameType(cast<Function>(ResumeAddrConstant));
247  elideHeapAllocations(CoroId->getFunction(), FrameTy, AA);
248  coro::replaceCoroFree(CoroId, /*Elide=*/true);
249  }
250 
251  return true;
252 }
253 
254 // See if there are any coro.subfn.addr instructions referring to coro.devirt
255 // trigger, if so, replace them with a direct call to devirt trigger function.
258  for (auto &I : instructions(F))
259  if (auto *SubFn = dyn_cast<CoroSubFnInst>(&I))
260  if (SubFn->getIndex() == CoroSubFnInst::RestartTrigger)
261  DevirtAddr.push_back(SubFn);
262 
263  if (DevirtAddr.empty())
264  return false;
265 
266  Module &M = *F.getParent();
268  assert(DevirtFn && "coro.devirt.fn not found");
269  replaceWithConstant(DevirtFn, DevirtAddr);
270 
271  return true;
272 }
273 
274 //===----------------------------------------------------------------------===//
275 // Top Level Driver
276 //===----------------------------------------------------------------------===//
277 
278 namespace {
279 struct CoroElide : FunctionPass {
280  static char ID;
281  CoroElide() : FunctionPass(ID) {
283  }
284 
285  std::unique_ptr<Lowerer> L;
286 
287  bool doInitialization(Module &M) override {
288  if (coro::declaresIntrinsics(M, {"llvm.coro.id"}))
289  L = std::make_unique<Lowerer>(M);
290  return false;
291  }
292 
293  bool runOnFunction(Function &F) override {
294  if (!L)
295  return false;
296 
297  bool Changed = false;
298 
300  Changed = replaceDevirtTrigger(F);
301 
302  L->CoroIds.clear();
303 
304  // Collect all PostSplit coro.ids.
305  for (auto &I : instructions(F))
306  if (auto *CII = dyn_cast<CoroIdInst>(&I))
307  if (CII->getInfo().isPostSplit())
308  // If it is the coroutine itself, don't touch it.
309  if (CII->getCoroutine() != CII->getFunction())
310  L->CoroIds.push_back(CII);
311 
312  // If we did not find any coro.id, there is nothing to do.
313  if (L->CoroIds.empty())
314  return Changed;
315 
316  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
317  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
318 
319  for (auto *CII : L->CoroIds)
320  Changed |= L->processCoroId(CII, AA, DT);
321 
322  return Changed;
323  }
324  void getAnalysisUsage(AnalysisUsage &AU) const override {
327  }
328  StringRef getPassName() const override { return "Coroutine Elision"; }
329 };
330 }
331 
332 char CoroElide::ID = 0;
334  CoroElide, "coro-elide",
335  "Coroutine frame allocation elision and indirect calls replacement", false,
336  false)
339  CoroElide, "coro-elide",
340  "Coroutine frame allocation elision and indirect calls replacement", false,
341  false)
342 
343 Pass *llvm::createCoroElidePass() { return new CoroElide(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:616
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This represents the llvm.coro.id instruction.
Definition: CoroInstr.h:113
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void initializeCoroElidePass(PassRegistry &)
This class represents a function call, abstracting a target machine&#39;s calling convention.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
F(f)
iv Induction Variable Users
Definition: IVUsers.cpp:51
Info getInfo() const
Definition: CoroInstr.h:162
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:270
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of &#39;I&#39; with &#39;SimpleV&#39; and simplify the uses recursively.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
static bool replaceDevirtTrigger(Function &F)
Definition: CoroElide.cpp:256
This class represents the llvm.coro.subfn.addr instruction.
Definition: CoroInstr.h:35
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
This class represents a no-op cast from one type to another.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1804
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
#define CORO_PRESPLIT_ATTR
Definition: CoroInternal.h:38
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
This is an important base class in LLVM.
Definition: Constant.h:41
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
Pass * createCoroElidePass()
Analyze coroutines use sites, devirtualize resume/destroy calls and elide heap allocation for corouti...
Definition: CoroElide.cpp:343
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
Represent the analysis usage information of a pass.
static void replaceWithConstant(Constant *Value, SmallVectorImpl< CoroSubFnInst *> &Users)
Definition: CoroElide.cpp:45
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:78
arg_iterator arg_begin()
Definition: Function.h:695
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:219
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static Type * getFrameType(Function *Resume)
Definition: CoroElide.cpp:93
size_type size() const
Definition: SmallPtrSet.h:92
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:305
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
ConstantArray * Resumers
Definition: CoroInstr.h:156
iterator_range< user_iterator > users()
Definition: Value.h:419
static Instruction * getFirstNonAllocaInTheEntryBlock(Function *F)
Definition: CoroElide.cpp:99
static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:68
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
iterator_range< value_op_iterator > operand_values()
Definition: User.h:261
#define CORO_DEVIRT_TRIGGER_FN
Definition: CoroInternal.h:42
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:166
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:73
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:153
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2207
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
INITIALIZE_PASS_BEGIN(CoroElide, "coro-elide", "Coroutine frame allocation elision and indirect calls replacement", false, false) INITIALIZE_PASS_END(CoroElide
an instruction to allocate memory on the stack
Definition: Instructions.h:59