LLVM  6.0.0svn
CoroElide.cpp
Go to the documentation of this file.
1 //===- CoroElide.cpp - Coroutine Frame Allocation Elision Pass ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This pass replaces dynamic allocation of coroutine frame with alloca and
10 // replaces calls to llvm.coro.resume and llvm.coro.destroy with direct calls
11 // to coroutine sub-functions.
12 //===----------------------------------------------------------------------===//
13 
14 #include "CoroInternal.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() const;
39  bool processCoroId(CoroIdInst *, AAResults &AA);
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  MemoryLocation Mem(Frame);
81  for (Instruction &I : instructions(F))
82  if (auto *Call = dyn_cast<CallInst>(&I))
83  if (Call->isTailCall() && operandReferences(Call, Frame, AA)) {
84  // FIXME: If we ever hit this check. Evaluate whether it is more
85  // appropriate to retain musttail and allow the code to compile.
86  if (Call->isMustTailCall())
87  report_fatal_error("Call referring to the coroutine frame cannot be "
88  "marked as musttail");
89  Call->setTailCall(false);
90  }
91 }
92 
93 // Given a resume function @f.resume(%f.frame* %frame), returns %f.frame type.
94 static Type *getFrameType(Function *Resume) {
95  auto *ArgType = Resume->arg_begin()->getType();
96  return cast<PointerType>(ArgType)->getElementType();
97 }
98 
99 // Finds first non alloca instruction in the entry block of a function.
101  for (Instruction &I : F->getEntryBlock())
102  if (!isa<AllocaInst>(&I))
103  return &I;
104  llvm_unreachable("no terminator in the entry block");
105 }
106 
107 // To elide heap allocations we need to suppress code blocks guarded by
108 // llvm.coro.alloc and llvm.coro.free instructions.
109 void Lowerer::elideHeapAllocations(Function *F, Type *FrameTy, AAResults &AA) {
110  LLVMContext &C = FrameTy->getContext();
111  auto *InsertPt =
112  getFirstNonAllocaInTheEntryBlock(CoroIds.front()->getFunction());
113 
114  // Replacing llvm.coro.alloc with false will suppress dynamic
115  // allocation as it is expected for the frontend to generate the code that
116  // looks like:
117  // id = coro.id(...)
118  // mem = coro.alloc(id) ? malloc(coro.size()) : 0;
119  // coro.begin(id, mem)
120  auto *False = ConstantInt::getFalse(C);
121  for (auto *CA : CoroAllocs) {
122  CA->replaceAllUsesWith(False);
123  CA->eraseFromParent();
124  }
125 
126  // FIXME: Design how to transmit alignment information for every alloca that
127  // is spilled into the coroutine frame and recreate the alignment information
128  // here. Possibly we will need to do a mini SROA here and break the coroutine
129  // frame into individual AllocaInst recreating the original alignment.
130  const DataLayout &DL = F->getParent()->getDataLayout();
131  auto *Frame = new AllocaInst(FrameTy, DL.getAllocaAddrSpace(), "", InsertPt);
132  auto *FrameVoidPtr =
133  new BitCastInst(Frame, Type::getInt8PtrTy(C), "vFrame", InsertPt);
134 
135  for (auto *CB : CoroBegins) {
136  CB->replaceAllUsesWith(FrameVoidPtr);
137  CB->eraseFromParent();
138  }
139 
140  // Since now coroutine frame lives on the stack we need to make sure that
141  // any tail call referencing it, must be made non-tail call.
142  removeTailCallAttribute(Frame, AA);
143 }
144 
145 bool Lowerer::shouldElide() const {
146  // If no CoroAllocs, we cannot suppress allocation, so elision is not
147  // possible.
148  if (CoroAllocs.empty())
149  return false;
150 
151  // Check that for every coro.begin there is a coro.destroy directly
152  // referencing the SSA value of that coro.begin. If the value escaped, then
153  // coro.destroy would have been referencing a memory location storing that
154  // value and not the virtual register.
155 
156  SmallPtrSet<CoroBeginInst *, 8> ReferencedCoroBegins;
157 
158  for (CoroSubFnInst *DA : DestroyAddr) {
159  if (auto *CB = dyn_cast<CoroBeginInst>(DA->getFrame()))
160  ReferencedCoroBegins.insert(CB);
161  else
162  return false;
163  }
164 
165  // If size of the set is the same as total number of CoroBegins, means we
166  // found a coro.free or coro.destroy mentioning a coro.begin and we can
167  // perform heap elision.
168  return ReferencedCoroBegins.size() == CoroBegins.size();
169 }
170 
171 bool Lowerer::processCoroId(CoroIdInst *CoroId, AAResults &AA) {
172  CoroBegins.clear();
173  CoroAllocs.clear();
174  CoroFrees.clear();
175  ResumeAddr.clear();
176  DestroyAddr.clear();
177 
178  // Collect all coro.begin and coro.allocs associated with this coro.id.
179  for (User *U : CoroId->users()) {
180  if (auto *CB = dyn_cast<CoroBeginInst>(U))
181  CoroBegins.push_back(CB);
182  else if (auto *CA = dyn_cast<CoroAllocInst>(U))
183  CoroAllocs.push_back(CA);
184  else if (auto *CF = dyn_cast<CoroFreeInst>(U))
185  CoroFrees.push_back(CF);
186  }
187 
188  // Collect all coro.subfn.addrs associated with coro.begin.
189  // Note, we only devirtualize the calls if their coro.subfn.addr refers to
190  // coro.begin directly. If we run into cases where this check is too
191  // conservative, we can consider relaxing the check.
192  for (CoroBeginInst *CB : CoroBegins) {
193  for (User *U : CB->users())
194  if (auto *II = dyn_cast<CoroSubFnInst>(U))
195  switch (II->getIndex()) {
197  ResumeAddr.push_back(II);
198  break;
200  DestroyAddr.push_back(II);
201  break;
202  default:
203  llvm_unreachable("unexpected coro.subfn.addr constant");
204  }
205  }
206 
207  // PostSplit coro.id refers to an array of subfunctions in its Info
208  // argument.
209  ConstantArray *Resumers = CoroId->getInfo().Resumers;
210  assert(Resumers && "PostSplit coro.id Info argument must refer to an array"
211  "of coroutine subfunctions");
212  auto *ResumeAddrConstant =
214 
215  replaceWithConstant(ResumeAddrConstant, ResumeAddr);
216 
217  bool ShouldElide = shouldElide();
218 
219  auto *DestroyAddrConstant = ConstantExpr::getExtractValue(
220  Resumers,
222 
223  replaceWithConstant(DestroyAddrConstant, DestroyAddr);
224 
225  if (ShouldElide) {
226  auto *FrameTy = getFrameType(cast<Function>(ResumeAddrConstant));
227  elideHeapAllocations(CoroId->getFunction(), FrameTy, AA);
228  coro::replaceCoroFree(CoroId, /*Elide=*/true);
229  }
230 
231  return true;
232 }
233 
234 // See if there are any coro.subfn.addr instructions referring to coro.devirt
235 // trigger, if so, replace them with a direct call to devirt trigger function.
238  for (auto &I : instructions(F))
239  if (auto *SubFn = dyn_cast<CoroSubFnInst>(&I))
240  if (SubFn->getIndex() == CoroSubFnInst::RestartTrigger)
241  DevirtAddr.push_back(SubFn);
242 
243  if (DevirtAddr.empty())
244  return false;
245 
246  Module &M = *F.getParent();
248  assert(DevirtFn && "coro.devirt.fn not found");
249  replaceWithConstant(DevirtFn, DevirtAddr);
250 
251  return true;
252 }
253 
254 //===----------------------------------------------------------------------===//
255 // Top Level Driver
256 //===----------------------------------------------------------------------===//
257 
258 namespace {
259 struct CoroElide : FunctionPass {
260  static char ID;
261  CoroElide() : FunctionPass(ID) {
263  }
264 
265  std::unique_ptr<Lowerer> L;
266 
267  bool doInitialization(Module &M) override {
268  if (coro::declaresIntrinsics(M, {"llvm.coro.id"}))
269  L = llvm::make_unique<Lowerer>(M);
270  return false;
271  }
272 
273  bool runOnFunction(Function &F) override {
274  if (!L)
275  return false;
276 
277  bool Changed = false;
278 
280  Changed = replaceDevirtTrigger(F);
281 
282  L->CoroIds.clear();
283 
284  // Collect all PostSplit coro.ids.
285  for (auto &I : instructions(F))
286  if (auto *CII = dyn_cast<CoroIdInst>(&I))
287  if (CII->getInfo().isPostSplit())
288  // If it is the coroutine itself, don't touch it.
289  if (CII->getCoroutine() != CII->getFunction())
290  L->CoroIds.push_back(CII);
291 
292  // If we did not find any coro.id, there is nothing to do.
293  if (L->CoroIds.empty())
294  return Changed;
295 
296  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
297 
298  for (auto *CII : L->CoroIds)
299  Changed |= L->processCoroId(CII, AA);
300 
301  return Changed;
302  }
303  void getAnalysisUsage(AnalysisUsage &AU) const override {
305  }
306  StringRef getPassName() const override { return "Coroutine Elision"; }
307 };
308 }
309 
310 char CoroElide::ID = 0;
312  CoroElide, "coro-elide",
313  "Coroutine frame allocation elision and indirect calls replacement", false,
314  false)
317  CoroElide, "coro-elide",
318  "Coroutine frame allocation elision and indirect calls replacement", false,
319  false)
320 
321 Pass *llvm::createCoroElidePass() { return new CoroElide(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:523
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This represents the llvm.coro.alloc instruction.
Definition: CoroInstr.h:82
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:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void initializeCoroElidePass(PassRegistry &)
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:262
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
iv Induction Variable Users
Definition: IVUsers.cpp:51
Info getInfo() const
Definition: CoroInstr.h:146
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:253
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
static bool replaceDevirtTrigger(Function &F)
Definition: CoroElide.cpp:236
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.
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1678
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
static bool runOnFunction(Function &F, bool PostInlining)
#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:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
This is an important base class in LLVM.
Definition: Constant.h:42
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
Pass * createCoroElidePass()
Analyze coroutines use sites, devirtualize resume/destroy calls and elide heap allocation for corouti...
Definition: CoroElide.cpp:321
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:371
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:285
static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:78
arg_iterator arg_begin()
Definition: Function.h:603
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:61
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
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:94
Representation for a specific memory location.
size_type size() const
Definition: SmallPtrSet.h:93
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:172
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:215
ConstantArray - Constant Array Declarations.
Definition: Constants.h:405
ConstantArray * Resumers
Definition: CoroInstr.h:140
iterator_range< user_iterator > users()
Definition: Value.h:401
static Instruction * getFirstNonAllocaInTheEntryBlock(Function *F)
Definition: CoroElide.cpp:100
static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:68
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
iterator_range< value_op_iterator > operand_values()
Definition: User.h:246
#define CORO_DEVIRT_TRIGGER_FN
Definition: CoroInternal.h:42
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:151
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:556
LLVM Value Representation.
Definition: Value.h:73
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:138
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2072
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr)
Replace all uses of &#39;I&#39; with &#39;SimpleV&#39; and simplify the uses recursively.
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:60