LLVM  8.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/Dominators.h"
18 #include "llvm/IR/InstIterator.h"
19 #include "llvm/Pass.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "coro-elide"
25 
26 namespace {
27 // Created on demand if CoroElide pass has work to do.
28 struct Lowerer : coro::LowererBase {
35 
36  Lowerer(Module &M) : LowererBase(M) {}
37 
38  void elideHeapAllocations(Function *F, Type *FrameTy, AAResults &AA);
39  bool shouldElide(Function *F, DominatorTree &DT) const;
40  bool processCoroId(CoroIdInst *, AAResults &AA, DominatorTree &DT);
41 };
42 } // end anonymous namespace
43 
44 // Go through the list of coro.subfn.addr intrinsics and replace them with the
45 // provided constant.
48  if (Users.empty())
49  return;
50 
51  // See if we need to bitcast the constant to match the type of the intrinsic
52  // being replaced. Note: All coro.subfn.addr intrinsics return the same type,
53  // so we only need to examine the type of the first one in the list.
54  Type *IntrTy = Users.front()->getType();
55  Type *ValueTy = Value->getType();
56  if (ValueTy != IntrTy) {
57  // May need to tweak the function type to match the type expected at the
58  // use site.
59  assert(ValueTy->isPointerTy() && IntrTy->isPointerTy());
60  Value = ConstantExpr::getBitCast(Value, IntrTy);
61  }
62 
63  // Now the value type matches the type of the intrinsic. Replace them all!
64  for (CoroSubFnInst *I : Users)
66 }
67 
68 // See if any operand of the call instruction references the coroutine frame.
69 static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA) {
70  for (Value *Op : CI->operand_values())
71  if (AA.alias(Op, Frame) != NoAlias)
72  return true;
73  return false;
74 }
75 
76 // Look for any tail calls referencing the coroutine frame and remove tail
77 // attribute from them, since now coroutine frame resides on the stack and tail
78 // call implies that the function does not references anything on the stack.
79 static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA) {
80  Function &F = *Frame->getFunction();
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(Function *F, DominatorTree &DT) 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 along a non-exceptional path.
153  // If the value escaped, then coro.destroy would have been referencing a
154  // memory location storing that value and not the virtual register.
155 
156  // First gather all of the non-exceptional terminators for the function.
157  SmallPtrSet<Instruction *, 8> Terminators;
158  for (BasicBlock &B : *F) {
159  auto *TI = B.getTerminator();
160  if (TI->getNumSuccessors() == 0 && !TI->isExceptionalTerminator() &&
161  !isa<UnreachableInst>(TI))
162  Terminators.insert(TI);
163  }
164 
165  // Filter out the coro.destroy that lie along exceptional paths.
167  for (CoroSubFnInst *DA : DestroyAddr) {
168  for (Instruction *TI : Terminators) {
169  if (DT.dominates(DA, TI)) {
170  DAs.insert(DA);
171  break;
172  }
173  }
174  }
175 
176  // Find all the coro.begin referenced by coro.destroy along happy paths.
177  SmallPtrSet<CoroBeginInst *, 8> ReferencedCoroBegins;
178  for (CoroSubFnInst *DA : DAs) {
179  if (auto *CB = dyn_cast<CoroBeginInst>(DA->getFrame()))
180  ReferencedCoroBegins.insert(CB);
181  else
182  return false;
183  }
184 
185  // If size of the set is the same as total number of coro.begin, that means we
186  // found a coro.free or coro.destroy referencing each coro.begin, so we can
187  // perform heap elision.
188  return ReferencedCoroBegins.size() == CoroBegins.size();
189 }
190 
191 bool Lowerer::processCoroId(CoroIdInst *CoroId, AAResults &AA,
192  DominatorTree &DT) {
193  CoroBegins.clear();
194  CoroAllocs.clear();
195  CoroFrees.clear();
196  ResumeAddr.clear();
197  DestroyAddr.clear();
198 
199  // Collect all coro.begin and coro.allocs associated with this coro.id.
200  for (User *U : CoroId->users()) {
201  if (auto *CB = dyn_cast<CoroBeginInst>(U))
202  CoroBegins.push_back(CB);
203  else if (auto *CA = dyn_cast<CoroAllocInst>(U))
204  CoroAllocs.push_back(CA);
205  else if (auto *CF = dyn_cast<CoroFreeInst>(U))
206  CoroFrees.push_back(CF);
207  }
208 
209  // Collect all coro.subfn.addrs associated with coro.begin.
210  // Note, we only devirtualize the calls if their coro.subfn.addr refers to
211  // coro.begin directly. If we run into cases where this check is too
212  // conservative, we can consider relaxing the check.
213  for (CoroBeginInst *CB : CoroBegins) {
214  for (User *U : CB->users())
215  if (auto *II = dyn_cast<CoroSubFnInst>(U))
216  switch (II->getIndex()) {
218  ResumeAddr.push_back(II);
219  break;
221  DestroyAddr.push_back(II);
222  break;
223  default:
224  llvm_unreachable("unexpected coro.subfn.addr constant");
225  }
226  }
227 
228  // PostSplit coro.id refers to an array of subfunctions in its Info
229  // argument.
230  ConstantArray *Resumers = CoroId->getInfo().Resumers;
231  assert(Resumers && "PostSplit coro.id Info argument must refer to an array"
232  "of coroutine subfunctions");
233  auto *ResumeAddrConstant =
235 
236  replaceWithConstant(ResumeAddrConstant, ResumeAddr);
237 
238  bool ShouldElide = shouldElide(CoroId->getFunction(), DT);
239 
240  auto *DestroyAddrConstant = ConstantExpr::getExtractValue(
241  Resumers,
243 
244  replaceWithConstant(DestroyAddrConstant, DestroyAddr);
245 
246  if (ShouldElide) {
247  auto *FrameTy = getFrameType(cast<Function>(ResumeAddrConstant));
248  elideHeapAllocations(CoroId->getFunction(), FrameTy, AA);
249  coro::replaceCoroFree(CoroId, /*Elide=*/true);
250  }
251 
252  return true;
253 }
254 
255 // See if there are any coro.subfn.addr instructions referring to coro.devirt
256 // trigger, if so, replace them with a direct call to devirt trigger function.
259  for (auto &I : instructions(F))
260  if (auto *SubFn = dyn_cast<CoroSubFnInst>(&I))
261  if (SubFn->getIndex() == CoroSubFnInst::RestartTrigger)
262  DevirtAddr.push_back(SubFn);
263 
264  if (DevirtAddr.empty())
265  return false;
266 
267  Module &M = *F.getParent();
269  assert(DevirtFn && "coro.devirt.fn not found");
270  replaceWithConstant(DevirtFn, DevirtAddr);
271 
272  return true;
273 }
274 
275 //===----------------------------------------------------------------------===//
276 // Top Level Driver
277 //===----------------------------------------------------------------------===//
278 
279 namespace {
280 struct CoroElide : FunctionPass {
281  static char ID;
282  CoroElide() : FunctionPass(ID) {
284  }
285 
286  std::unique_ptr<Lowerer> L;
287 
288  bool doInitialization(Module &M) override {
289  if (coro::declaresIntrinsics(M, {"llvm.coro.id"}))
290  L = llvm::make_unique<Lowerer>(M);
291  return false;
292  }
293 
294  bool runOnFunction(Function &F) override {
295  if (!L)
296  return false;
297 
298  bool Changed = false;
299 
301  Changed = replaceDevirtTrigger(F);
302 
303  L->CoroIds.clear();
304 
305  // Collect all PostSplit coro.ids.
306  for (auto &I : instructions(F))
307  if (auto *CII = dyn_cast<CoroIdInst>(&I))
308  if (CII->getInfo().isPostSplit())
309  // If it is the coroutine itself, don't touch it.
310  if (CII->getCoroutine() != CII->getFunction())
311  L->CoroIds.push_back(CII);
312 
313  // If we did not find any coro.id, there is nothing to do.
314  if (L->CoroIds.empty())
315  return Changed;
316 
317  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
318  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
319 
320  for (auto *CII : L->CoroIds)
321  Changed |= L->processCoroId(CII, AA, DT);
322 
323  return Changed;
324  }
325  void getAnalysisUsage(AnalysisUsage &AU) const override {
328  }
329  StringRef getPassName() const override { return "Coroutine Elision"; }
330 };
331 }
332 
333 char CoroElide::ID = 0;
335  CoroElide, "coro-elide",
336  "Coroutine frame allocation elision and indirect calls replacement", false,
337  false)
340  CoroElide, "coro-elide",
341  "Coroutine frame allocation elision and indirect calls replacement", false,
342  false)
343 
344 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:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:585
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:139
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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:85
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:321
F(f)
iv Induction Variable Users
Definition: IVUsers.cpp:52
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:258
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:365
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:257
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:145
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1773
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
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:58
#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:224
Pass * createCoroElidePass()
Analyze coroutines use sites, devirtualize resume/destroy calls and elide heap allocation for corouti...
Definition: CoroElide.cpp:344
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:46
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:79
arg_iterator arg_begin()
Definition: Function.h:671
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:60
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
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:847
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:249
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:176
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:215
ConstantArray - Constant Array Declarations.
Definition: Constants.h:414
ConstantArray * Resumers
Definition: CoroInstr.h:140
iterator_range< user_iterator > users()
Definition: Value.h:400
static Instruction * getFirstNonAllocaInTheEntryBlock(Function *F)
Definition: CoroElide.cpp:100
static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:69
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
#define I(x, y, z)
Definition: MD5.cpp:58
iterator_range< value_op_iterator > operand_values()
Definition: User.h:262
#define CORO_DEVIRT_TRIGGER_FN
Definition: CoroInternal.h:42
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:153
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:140
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
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