LLVM  8.0.0svn
Coroutines.cpp
Go to the documentation of this file.
1 //===- Coroutines.cpp -----------------------------------------------------===//
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 //
10 // This file implements the common infrastructure for Coroutine Passes.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 #include "CoroInstr.h"
17 #include "CoroInternal.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringRef.h"
23 #include "llvm/IR/Attributes.h"
24 #include "llvm/IR/CallSite.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/InstIterator.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/Intrinsics.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/Support/Casting.h"
37 #include "llvm/Transforms/IPO.h"
39 #include <cassert>
40 #include <cstddef>
41 #include <utility>
42 
43 using namespace llvm;
44 
46  initializeCoroEarlyPass(Registry);
47  initializeCoroSplitPass(Registry);
48  initializeCoroElidePass(Registry);
49  initializeCoroCleanupPass(Registry);
50 }
51 
52 static void addCoroutineOpt0Passes(const PassManagerBuilder &Builder,
56 
59 }
60 
61 static void addCoroutineEarlyPasses(const PassManagerBuilder &Builder,
64 }
65 
69 }
70 
71 static void addCoroutineSCCPasses(const PassManagerBuilder &Builder,
74 }
75 
79 }
80 
92 }
93 
94 // Construct the lowerer base class and initialize its members.
96  : TheModule(M), Context(M.getContext()),
97  Int8Ptr(Type::getInt8PtrTy(Context)),
98  ResumeFnType(FunctionType::get(Type::getVoidTy(Context), Int8Ptr,
99  /*isVarArg=*/false)),
100  NullPtr(ConstantPointerNull::get(Int8Ptr)) {}
101 
102 // Creates a sequence of instructions to obtain a resume function address using
103 // llvm.coro.subfn.addr. It generates the following sequence:
104 //
105 // call i8* @llvm.coro.subfn.addr(i8* %Arg, i8 %index)
106 // bitcast i8* %2 to void(i8*)*
107 
109  Instruction *InsertPt) {
110  auto *IndexVal = ConstantInt::get(Type::getInt8Ty(Context), Index);
111  auto *Fn = Intrinsic::getDeclaration(&TheModule, Intrinsic::coro_subfn_addr);
112 
114  Index < CoroSubFnInst::IndexLast &&
115  "makeSubFnCall: Index value out of range");
116  auto *Call = CallInst::Create(Fn, {Arg, IndexVal}, "", InsertPt);
117 
118  auto *Bitcast =
119  new BitCastInst(Call, ResumeFnType->getPointerTo(), "", InsertPt);
120  return Bitcast;
121 }
122 
123 #ifndef NDEBUG
125  // NOTE: Must be sorted!
126  static const char *const CoroIntrinsics[] = {
127  "llvm.coro.alloc", "llvm.coro.begin", "llvm.coro.destroy",
128  "llvm.coro.done", "llvm.coro.end", "llvm.coro.frame",
129  "llvm.coro.free", "llvm.coro.id", "llvm.coro.noop",
130  "llvm.coro.param", "llvm.coro.promise", "llvm.coro.resume",
131  "llvm.coro.save", "llvm.coro.size", "llvm.coro.subfn.addr",
132  "llvm.coro.suspend",
133  };
134  return Intrinsic::lookupLLVMIntrinsicByName(CoroIntrinsics, Name) != -1;
135 }
136 #endif
137 
138 // Verifies if a module has named values listed. Also, in debug mode verifies
139 // that names are intrinsic names.
141  std::initializer_list<StringRef> List) {
142  for (StringRef Name : List) {
143  assert(isCoroutineIntrinsicName(Name) && "not a coroutine intrinsic");
144  if (M.getNamedValue(Name))
145  return true;
146  }
147 
148  return false;
149 }
150 
151 // Replace all coro.frees associated with the provided CoroId either with 'null'
152 // if Elide is true and with its frame parameter otherwise.
153 void coro::replaceCoroFree(CoroIdInst *CoroId, bool Elide) {
155  for (User *U : CoroId->users())
156  if (auto CF = dyn_cast<CoroFreeInst>(U))
157  CoroFrees.push_back(CF);
158 
159  if (CoroFrees.empty())
160  return;
161 
162  Value *Replacement =
164  : CoroFrees.front()->getFrame();
165 
166  for (CoroFreeInst *CF : CoroFrees) {
167  CF->replaceAllUsesWith(Replacement);
168  CF->eraseFromParent();
169  }
170 }
171 
172 // FIXME: This code is stolen from CallGraph::addToCallGraph(Function *F), which
173 // happens to be private. It is better for this functionality exposed by the
174 // CallGraph.
175 static void buildCGN(CallGraph &CG, CallGraphNode *Node) {
176  Function *F = Node->getFunction();
177 
178  // Look for calls by this function.
179  for (Instruction &I : instructions(F))
180  if (CallSite CS = CallSite(cast<Value>(&I))) {
181  const Function *Callee = CS.getCalledFunction();
182  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
183  // Indirect calls of intrinsics are not allowed so no need to check.
184  // We can be more precise here by using TargetArg returned by
185  // Intrinsic::isLeaf.
186  Node->addCalledFunction(CS, CG.getCallsExternalNode());
187  else if (!Callee->isIntrinsic())
188  Node->addCalledFunction(CS, CG.getOrInsertFunction(Callee));
189  }
190 }
191 
192 // Rebuild CGN after we extracted parts of the code from ParentFunc into
193 // NewFuncs. Builds CGNs for the NewFuncs and adds them to the current SCC.
195  CallGraph &CG, CallGraphSCC &SCC) {
196  // Rebuild CGN from scratch for the ParentFunc
197  auto *ParentNode = CG[&ParentFunc];
198  ParentNode->removeAllCalledFunctions();
199  buildCGN(CG, ParentNode);
200 
201  SmallVector<CallGraphNode *, 8> Nodes(SCC.begin(), SCC.end());
202 
203  for (Function *F : NewFuncs) {
205  Nodes.push_back(Callee);
206  buildCGN(CG, Callee);
207  }
208 
209  SCC.initialize(Nodes);
210 }
211 
212 static void clear(coro::Shape &Shape) {
213  Shape.CoroBegin = nullptr;
214  Shape.CoroEnds.clear();
215  Shape.CoroSizes.clear();
216  Shape.CoroSuspends.clear();
217 
218  Shape.FrameTy = nullptr;
219  Shape.FramePtr = nullptr;
220  Shape.AllocaSpillBlock = nullptr;
221  Shape.ResumeSwitch = nullptr;
222  Shape.PromiseAlloca = nullptr;
223  Shape.HasFinalSuspend = false;
224 }
225 
227  CoroSuspendInst *SuspendInst) {
228  Module *M = SuspendInst->getModule();
229  auto *Fn = Intrinsic::getDeclaration(M, Intrinsic::coro_save);
230  auto *SaveInst =
231  cast<CoroSaveInst>(CallInst::Create(Fn, CoroBegin, "", SuspendInst));
232  assert(!SuspendInst->getCoroSave());
233  SuspendInst->setArgOperand(0, SaveInst);
234  return SaveInst;
235 }
236 
237 // Collect "interesting" coroutine intrinsics.
239  size_t FinalSuspendIndex = 0;
240  clear(*this);
242  SmallVector<CoroSaveInst *, 2> UnusedCoroSaves;
243 
244  for (Instruction &I : instructions(F)) {
245  if (auto II = dyn_cast<IntrinsicInst>(&I)) {
246  switch (II->getIntrinsicID()) {
247  default:
248  continue;
249  case Intrinsic::coro_size:
250  CoroSizes.push_back(cast<CoroSizeInst>(II));
251  break;
252  case Intrinsic::coro_frame:
253  CoroFrames.push_back(cast<CoroFrameInst>(II));
254  break;
255  case Intrinsic::coro_save:
256  // After optimizations, coro_suspends using this coro_save might have
257  // been removed, remember orphaned coro_saves to remove them later.
258  if (II->use_empty())
259  UnusedCoroSaves.push_back(cast<CoroSaveInst>(II));
260  break;
261  case Intrinsic::coro_suspend:
262  CoroSuspends.push_back(cast<CoroSuspendInst>(II));
263  if (CoroSuspends.back()->isFinal()) {
264  if (HasFinalSuspend)
266  "Only one suspend point can be marked as final");
267  HasFinalSuspend = true;
268  FinalSuspendIndex = CoroSuspends.size() - 1;
269  }
270  break;
271  case Intrinsic::coro_begin: {
272  auto CB = cast<CoroBeginInst>(II);
273  if (CB->getId()->getInfo().isPreSplit()) {
274  if (CoroBegin)
276  "coroutine should have exactly one defining @llvm.coro.begin");
277  CB->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
279  CB->removeAttribute(AttributeList::FunctionIndex,
280  Attribute::NoDuplicate);
281  CoroBegin = CB;
282  }
283  break;
284  }
285  case Intrinsic::coro_end:
286  CoroEnds.push_back(cast<CoroEndInst>(II));
287  if (CoroEnds.back()->isFallthrough()) {
288  // Make sure that the fallthrough coro.end is the first element in the
289  // CoroEnds vector.
290  if (CoroEnds.size() > 1) {
291  if (CoroEnds.front()->isFallthrough())
293  "Only one coro.end can be marked as fallthrough");
294  std::swap(CoroEnds.front(), CoroEnds.back());
295  }
296  }
297  break;
298  }
299  }
300  }
301 
302  // If for some reason, we were not able to find coro.begin, bailout.
303  if (!CoroBegin) {
304  // Replace coro.frame which are supposed to be lowered to the result of
305  // coro.begin with undef.
307  for (CoroFrameInst *CF : CoroFrames) {
308  CF->replaceAllUsesWith(Undef);
309  CF->eraseFromParent();
310  }
311 
312  // Replace all coro.suspend with undef and remove related coro.saves if
313  // present.
314  for (CoroSuspendInst *CS : CoroSuspends) {
315  CS->replaceAllUsesWith(UndefValue::get(CS->getType()));
316  CS->eraseFromParent();
317  if (auto *CoroSave = CS->getCoroSave())
318  CoroSave->eraseFromParent();
319  }
320 
321  // Replace all coro.ends with unreachable instruction.
322  for (CoroEndInst *CE : CoroEnds)
323  changeToUnreachable(CE, /*UseLLVMTrap=*/false);
324 
325  return;
326  }
327 
328  // The coro.free intrinsic is always lowered to the result of coro.begin.
329  for (CoroFrameInst *CF : CoroFrames) {
330  CF->replaceAllUsesWith(CoroBegin);
331  CF->eraseFromParent();
332  }
333 
334  // Canonicalize coro.suspend by inserting a coro.save if needed.
335  for (CoroSuspendInst *CS : CoroSuspends)
336  if (!CS->getCoroSave())
337  createCoroSave(CoroBegin, CS);
338 
339  // Move final suspend to be the last element in the CoroSuspends vector.
340  if (HasFinalSuspend &&
341  FinalSuspendIndex != CoroSuspends.size() - 1)
342  std::swap(CoroSuspends[FinalSuspendIndex], CoroSuspends.back());
343 
344  // Remove orphaned coro.saves.
345  for (CoroSaveInst *CoroSave : UnusedCoroSaves)
346  CoroSave->eraseFromParent();
347 }
348 
350  unwrap(PM)->add(createCoroEarlyPass());
351 }
352 
354  unwrap(PM)->add(createCoroSplitPass());
355 }
356 
358  unwrap(PM)->add(createCoroElidePass());
359 }
360 
362  unwrap(PM)->add(createCoroCleanupPass());
363 }
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:199
Instruction * FramePtr
Definition: CoroInternal.h:82
LLVMContext & Context
PassManagerBuilder - This class is used to set up a standard optimization sequence for languages like...
CoroBeginInst * CoroBegin
Definition: CoroInternal.h:68
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
void initializeCoroEarlyPass(PassRegistry &)
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
void initializeCoroElidePass(PassRegistry &)
void LLVMAddCoroElidePass(LLVMPassManagerRef PM)
See llvm::createCoroElidePass function.
Definition: Coroutines.cpp:357
iterator end() const
Pass * createCoroSplitPass()
Split up coroutines into multiple functions driving their state machines.
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:45
static void buildCGN(CallGraph &CG, CallGraphNode *Node)
Definition: Coroutines.cpp:175
EP_ScalarOptimizerLate - This extension point allows adding optimization passes after most of the mai...
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
static void addCoroutineSCCPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:71
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:705
virtual void add(Pass *P)=0
Add a pass to the queue of passes to run.
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1084
Pass * createCoroEarlyPass()
Lower coroutine intrinsics that are not needed by later passes.
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
A node in the call graph for a module.
Definition: CallGraph.h:165
static bool isCoroutineIntrinsicName(StringRef Name)
Definition: Coroutines.cpp:124
void addCalledFunction(CallSite CS, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:233
amdgpu Simplify well known AMD library false Value Value const Twine & Name
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1923
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:195
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:652
This represents the llvm.coro.suspend instruction.
Definition: CoroInstr.h:266
This file contains the simple types necessary to represent the attributes associated with functions a...
void buildFrom(Function &F)
Definition: Coroutines.cpp:238
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
Class to represent function types.
Definition: DerivedTypes.h:103
void initializeCoroSplitPass(PassRegistry &)
EP_EnabledOnOptLevel0 - This extension point allows adding passes that should not be disabled by O0 o...
FunctionType *const ResumeFnType
Definition: CoroInternal.h:58
SmallVector< CoroSizeInst *, 2 > CoroSizes
Definition: CoroInternal.h:70
static void addCoroutineOptimizerLastPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:76
This class represents a no-op cast from one type to another.
GlobalValue * getNamedValue(StringRef Name) const
Return the global value in the module with the specified name, of arbitrary type. ...
Definition: Module.cpp:113
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
SmallVector< CoroSuspendInst *, 4 > CoroSuspends
Definition: CoroInternal.h:71
amdgpu Simplify well known AMD library false Value * Callee
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1021
static void addCoroutineScalarOptimizerPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:66
iterator begin() const
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1401
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1004
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:139
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
void LLVMAddCoroEarlyPass(LLVMPassManagerRef PM)
See llvm::createCoroEarlyPass function.
Definition: Coroutines.cpp:349
Pass * createCoroCleanupPass()
Lower all remaining coroutine intrinsics.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Pass * createCoroElidePass()
Analyze coroutines use sites, devirtualize resume/destroy calls and elide heap allocation for corouti...
Definition: CoroElide.cpp:344
This represents the llvm.coro.end instruction.
Definition: CoroInstr.h:303
ModulePass * createBarrierNoopPass()
createBarrierNoopPass - This pass is purely a module pass barrier in a pass manager.
This represents the llvm.coro.save instruction.
Definition: CoroInstr.h:233
void initialize(ArrayRef< CallGraphNode *> NewNodes)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
EP_OptimizerLast – This extension point allows adding passes that run after everything else...
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
LLVMContext & Context
Definition: CoroInternal.h:56
EP_EarlyAsPossible - This extension point allows adding passes before any other transformations, allowing them to see the code as it is coming out of the frontend.
This represents the llvm.coro.free instruction.
Definition: CoroInstr.h:199
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:188
EP_CGSCCOptimizerLate - This extension point allows adding CallGraphSCC passes at the end of the main...
StructType * FrameTy
Definition: CoroInternal.h:81
static void addCoroutineOpt0Passes(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:52
PassManagerBase - An abstract interface to allow code to add passes to a pass manager without having ...
void initializeCoroutines(PassRegistry &)
Initialize all passes linked into the Coroutines library.
Definition: Coroutines.cpp:45
static CoroSaveInst * createCoroSave(CoroBeginInst *CoroBegin, CoroSuspendInst *SuspendInst)
Definition: Coroutines.cpp:226
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
A constant pointer value that points to null.
Definition: Constants.h:539
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:622
static void addCoroutineEarlyPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:61
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:194
void LLVMAddCoroSplitPass(LLVMPassManagerRef PM)
See llvm::createCoroSplitPass function.
Definition: Coroutines.cpp:353
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:128
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:215
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:56
Value * makeSubFnCall(Value *Arg, int Index, Instruction *InsertPt)
Definition: Coroutines.cpp:108
iterator_range< user_iterator > users()
Definition: Value.h:400
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:212
amdgpu Simplify well known AMD library false Value Value * Arg
void initializeCoroCleanupPass(PassRegistry &)
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:74
Value * getFrame() const
Definition: CoroInstr.h:203
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
SwitchInst * ResumeSwitch
Definition: CoroInternal.h:84
const NodeList & List
Definition: RDFGraph.cpp:210
#define I(x, y, z)
Definition: MD5.cpp:58
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:153
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallVector< CoroEndInst *, 4 > CoroEnds
Definition: CoroInternal.h:69
AllocaInst * PromiseAlloca
Definition: CoroInternal.h:85
This represents the llvm.coro.frame instruction.
Definition: CoroInstr.h:187
LLVM Value Representation.
Definition: Value.h:73
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist...
Definition: CallGraph.cpp:149
void addCoroutinePassesToExtensionPoints(PassManagerBuilder &Builder)
Add all coroutine passes to appropriate extension points.
Definition: Coroutines.cpp:81
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:140
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:39
int lookupLLVMIntrinsicByName(ArrayRef< const char *> NameTable, StringRef Name)
Looks up Name in NameTable via binary search.
void LLVMAddCoroCleanupPass(LLVMPassManagerRef PM)
See llvm::createCoroCleanupPass function.
Definition: Coroutines.cpp:361
BasicBlock * AllocaSpillBlock
Definition: CoroInternal.h:83
void addExtension(ExtensionPointTy Ty, ExtensionFn Fn)
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
CoroSaveInst * getCoroSave() const
Definition: CoroInstr.h:270
void updateCallGraph(Function &Caller, ArrayRef< Function *> Funcs, CallGraph &CG, CallGraphSCC &SCC)
Definition: Coroutines.cpp:194