LLVM  7.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 
15 #include "CoroInstr.h"
16 #include "CoroInternal.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/StringRef.h"
22 #include "llvm/IR/Attributes.h"
23 #include "llvm/IR/CallSite.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/IR/Intrinsics.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/Support/Casting.h"
36 #include "llvm/Transforms/IPO.h"
38 #include <cassert>
39 #include <cstddef>
40 #include <utility>
41 
42 using namespace llvm;
43 
45  initializeCoroEarlyPass(Registry);
46  initializeCoroSplitPass(Registry);
47  initializeCoroElidePass(Registry);
48  initializeCoroCleanupPass(Registry);
49 }
50 
51 static void addCoroutineOpt0Passes(const PassManagerBuilder &Builder,
55 
58 }
59 
60 static void addCoroutineEarlyPasses(const PassManagerBuilder &Builder,
63 }
64 
68 }
69 
70 static void addCoroutineSCCPasses(const PassManagerBuilder &Builder,
73 }
74 
78 }
79 
91 }
92 
93 // Construct the lowerer base class and initialize its members.
95  : TheModule(M), Context(M.getContext()),
96  Int8Ptr(Type::getInt8PtrTy(Context)),
97  ResumeFnType(FunctionType::get(Type::getVoidTy(Context), Int8Ptr,
98  /*isVarArg=*/false)),
99  NullPtr(ConstantPointerNull::get(Int8Ptr)) {}
100 
101 // Creates a sequence of instructions to obtain a resume function address using
102 // llvm.coro.subfn.addr. It generates the following sequence:
103 //
104 // call i8* @llvm.coro.subfn.addr(i8* %Arg, i8 %index)
105 // bitcast i8* %2 to void(i8*)*
106 
108  Instruction *InsertPt) {
109  auto *IndexVal = ConstantInt::get(Type::getInt8Ty(Context), Index);
110  auto *Fn = Intrinsic::getDeclaration(&TheModule, Intrinsic::coro_subfn_addr);
111 
113  Index < CoroSubFnInst::IndexLast &&
114  "makeSubFnCall: Index value out of range");
115  auto *Call = CallInst::Create(Fn, {Arg, IndexVal}, "", InsertPt);
116 
117  auto *Bitcast =
118  new BitCastInst(Call, ResumeFnType->getPointerTo(), "", InsertPt);
119  return Bitcast;
120 }
121 
122 #ifndef NDEBUG
124  // NOTE: Must be sorted!
125  static const char *const CoroIntrinsics[] = {
126  "llvm.coro.alloc", "llvm.coro.begin", "llvm.coro.destroy",
127  "llvm.coro.done", "llvm.coro.end", "llvm.coro.frame",
128  "llvm.coro.free", "llvm.coro.id", "llvm.coro.noop",
129  "llvm.coro.param", "llvm.coro.promise", "llvm.coro.resume",
130  "llvm.coro.save", "llvm.coro.size", "llvm.coro.subfn.addr",
131  "llvm.coro.suspend",
132  };
133  return Intrinsic::lookupLLVMIntrinsicByName(CoroIntrinsics, Name) != -1;
134 }
135 #endif
136 
137 // Verifies if a module has named values listed. Also, in debug mode verifies
138 // that names are intrinsic names.
140  std::initializer_list<StringRef> List) {
141  for (StringRef Name : List) {
142  assert(isCoroutineIntrinsicName(Name) && "not a coroutine intrinsic");
143  if (M.getNamedValue(Name))
144  return true;
145  }
146 
147  return false;
148 }
149 
150 // Replace all coro.frees associated with the provided CoroId either with 'null'
151 // if Elide is true and with its frame parameter otherwise.
152 void coro::replaceCoroFree(CoroIdInst *CoroId, bool Elide) {
154  for (User *U : CoroId->users())
155  if (auto CF = dyn_cast<CoroFreeInst>(U))
156  CoroFrees.push_back(CF);
157 
158  if (CoroFrees.empty())
159  return;
160 
161  Value *Replacement =
163  : CoroFrees.front()->getFrame();
164 
165  for (CoroFreeInst *CF : CoroFrees) {
166  CF->replaceAllUsesWith(Replacement);
167  CF->eraseFromParent();
168  }
169 }
170 
171 // FIXME: This code is stolen from CallGraph::addToCallGraph(Function *F), which
172 // happens to be private. It is better for this functionality exposed by the
173 // CallGraph.
174 static void buildCGN(CallGraph &CG, CallGraphNode *Node) {
175  Function *F = Node->getFunction();
176 
177  // Look for calls by this function.
178  for (Instruction &I : instructions(F))
179  if (CallSite CS = CallSite(cast<Value>(&I))) {
180  const Function *Callee = CS.getCalledFunction();
181  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
182  // Indirect calls of intrinsics are not allowed so no need to check.
183  // We can be more precise here by using TargetArg returned by
184  // Intrinsic::isLeaf.
185  Node->addCalledFunction(CS, CG.getCallsExternalNode());
186  else if (!Callee->isIntrinsic())
187  Node->addCalledFunction(CS, CG.getOrInsertFunction(Callee));
188  }
189 }
190 
191 // Rebuild CGN after we extracted parts of the code from ParentFunc into
192 // NewFuncs. Builds CGNs for the NewFuncs and adds them to the current SCC.
194  CallGraph &CG, CallGraphSCC &SCC) {
195  // Rebuild CGN from scratch for the ParentFunc
196  auto *ParentNode = CG[&ParentFunc];
197  ParentNode->removeAllCalledFunctions();
198  buildCGN(CG, ParentNode);
199 
200  SmallVector<CallGraphNode *, 8> Nodes(SCC.begin(), SCC.end());
201 
202  for (Function *F : NewFuncs) {
204  Nodes.push_back(Callee);
205  buildCGN(CG, Callee);
206  }
207 
208  SCC.initialize(Nodes);
209 }
210 
211 static void clear(coro::Shape &Shape) {
212  Shape.CoroBegin = nullptr;
213  Shape.CoroEnds.clear();
214  Shape.CoroSizes.clear();
215  Shape.CoroSuspends.clear();
216 
217  Shape.FrameTy = nullptr;
218  Shape.FramePtr = nullptr;
219  Shape.AllocaSpillBlock = nullptr;
220  Shape.ResumeSwitch = nullptr;
221  Shape.PromiseAlloca = nullptr;
222  Shape.HasFinalSuspend = false;
223 }
224 
226  CoroSuspendInst *SuspendInst) {
227  Module *M = SuspendInst->getModule();
228  auto *Fn = Intrinsic::getDeclaration(M, Intrinsic::coro_save);
229  auto *SaveInst =
230  cast<CoroSaveInst>(CallInst::Create(Fn, CoroBegin, "", SuspendInst));
231  assert(!SuspendInst->getCoroSave());
232  SuspendInst->setArgOperand(0, SaveInst);
233  return SaveInst;
234 }
235 
236 // Collect "interesting" coroutine intrinsics.
238  size_t FinalSuspendIndex = 0;
239  clear(*this);
241  SmallVector<CoroSaveInst *, 2> UnusedCoroSaves;
242 
243  for (Instruction &I : instructions(F)) {
244  if (auto II = dyn_cast<IntrinsicInst>(&I)) {
245  switch (II->getIntrinsicID()) {
246  default:
247  continue;
248  case Intrinsic::coro_size:
249  CoroSizes.push_back(cast<CoroSizeInst>(II));
250  break;
251  case Intrinsic::coro_frame:
252  CoroFrames.push_back(cast<CoroFrameInst>(II));
253  break;
254  case Intrinsic::coro_save:
255  // After optimizations, coro_suspends using this coro_save might have
256  // been removed, remember orphaned coro_saves to remove them later.
257  if (II->use_empty())
258  UnusedCoroSaves.push_back(cast<CoroSaveInst>(II));
259  break;
260  case Intrinsic::coro_suspend:
261  CoroSuspends.push_back(cast<CoroSuspendInst>(II));
262  if (CoroSuspends.back()->isFinal()) {
263  if (HasFinalSuspend)
265  "Only one suspend point can be marked as final");
266  HasFinalSuspend = true;
267  FinalSuspendIndex = CoroSuspends.size() - 1;
268  }
269  break;
270  case Intrinsic::coro_begin: {
271  auto CB = cast<CoroBeginInst>(II);
272  if (CB->getId()->getInfo().isPreSplit()) {
273  if (CoroBegin)
275  "coroutine should have exactly one defining @llvm.coro.begin");
276  CB->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
278  CB->removeAttribute(AttributeList::FunctionIndex,
279  Attribute::NoDuplicate);
280  CoroBegin = CB;
281  }
282  break;
283  }
284  case Intrinsic::coro_end:
285  CoroEnds.push_back(cast<CoroEndInst>(II));
286  if (CoroEnds.back()->isFallthrough()) {
287  // Make sure that the fallthrough coro.end is the first element in the
288  // CoroEnds vector.
289  if (CoroEnds.size() > 1) {
290  if (CoroEnds.front()->isFallthrough())
292  "Only one coro.end can be marked as fallthrough");
293  std::swap(CoroEnds.front(), CoroEnds.back());
294  }
295  }
296  break;
297  }
298  }
299  }
300 
301  // If for some reason, we were not able to find coro.begin, bailout.
302  if (!CoroBegin) {
303  // Replace coro.frame which are supposed to be lowered to the result of
304  // coro.begin with undef.
306  for (CoroFrameInst *CF : CoroFrames) {
307  CF->replaceAllUsesWith(Undef);
308  CF->eraseFromParent();
309  }
310 
311  // Replace all coro.suspend with undef and remove related coro.saves if
312  // present.
313  for (CoroSuspendInst *CS : CoroSuspends) {
314  CS->replaceAllUsesWith(UndefValue::get(CS->getType()));
315  CS->eraseFromParent();
316  if (auto *CoroSave = CS->getCoroSave())
317  CoroSave->eraseFromParent();
318  }
319 
320  // Replace all coro.ends with unreachable instruction.
321  for (CoroEndInst *CE : CoroEnds)
322  changeToUnreachable(CE, /*UseLLVMTrap=*/false);
323 
324  return;
325  }
326 
327  // The coro.free intrinsic is always lowered to the result of coro.begin.
328  for (CoroFrameInst *CF : CoroFrames) {
329  CF->replaceAllUsesWith(CoroBegin);
330  CF->eraseFromParent();
331  }
332 
333  // Canonicalize coro.suspend by inserting a coro.save if needed.
334  for (CoroSuspendInst *CS : CoroSuspends)
335  if (!CS->getCoroSave())
336  createCoroSave(CoroBegin, CS);
337 
338  // Move final suspend to be the last element in the CoroSuspends vector.
339  if (HasFinalSuspend &&
340  FinalSuspendIndex != CoroSuspends.size() - 1)
341  std::swap(CoroSuspends[FinalSuspendIndex], CoroSuspends.back());
342 
343  // Remove orphaned coro.saves.
344  for (CoroSaveInst *CoroSave : UnusedCoroSaves)
345  CoroSave->eraseFromParent();
346 }
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:185
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:115
Compute iterated dominance frontiers using a linear time algorithm.
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:63
void initializeCoroElidePass(PassRegistry &)
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:174
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:70
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:713
virtual void add(Pass *P)=0
Add a pass to the queue of passes to run.
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:123
void addCalledFunction(CallSite CS, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:233
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:639
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:237
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:75
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:112
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:439
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:1001
static void addCoroutineScalarOptimizerPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:65
iterator begin() const
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1368
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:984
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
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 setArgOperand(unsigned i, Value *v)
void initialize(ArrayRef< CallGraphNode *> NewNodes)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1382
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:51
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:44
static CoroSaveInst * createCoroSave(CoroBeginInst *CoroBegin, CoroSuspendInst *SuspendInst)
Definition: Coroutines.cpp:225
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
Module.h This file contains the declarations for the Module class.
A constant pointer value that points to null.
Definition: Constants.h:535
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:611
static void addCoroutineEarlyPasses(const PassManagerBuilder &Builder, legacy::PassManagerBase &PM)
Definition: Coroutines.cpp:60
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:180
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
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:107
iterator_range< user_iterator > users()
Definition: Value.h:399
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
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:62
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:152
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DeferredDominance *DDT=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1713
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:150
void addCoroutinePassesToExtensionPoints(PassManagerBuilder &Builder)
Add all coroutine passes to appropriate extension points.
Definition: Coroutines.cpp:80
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:139
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.
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:193