LLVM  6.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 
14 #include "CoroInstr.h"
15 #include "CoroInternal.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/StringRef.h"
20 #include "llvm/IR/Attributes.h"
21 #include "llvm/IR/CallSite.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/Intrinsics.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/Type.h"
32 #include "llvm/Support/Casting.h"
35 #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.param",
129  "llvm.coro.promise", "llvm.coro.resume", "llvm.coro.save",
130  "llvm.coro.size", "llvm.coro.subfn.addr", "llvm.coro.suspend",
131  };
132  return Intrinsic::lookupLLVMIntrinsicByName(CoroIntrinsics, Name) != -1;
133 }
134 #endif
135 
136 // Verifies if a module has named values listed. Also, in debug mode verifies
137 // that names are intrinsic names.
139  std::initializer_list<StringRef> List) {
140  for (StringRef Name : List) {
141  assert(isCoroutineIntrinsicName(Name) && "not a coroutine intrinsic");
142  if (M.getNamedValue(Name))
143  return true;
144  }
145 
146  return false;
147 }
148 
149 // Replace all coro.frees associated with the provided CoroId either with 'null'
150 // if Elide is true and with its frame parameter otherwise.
151 void coro::replaceCoroFree(CoroIdInst *CoroId, bool Elide) {
153  for (User *U : CoroId->users())
154  if (auto CF = dyn_cast<CoroFreeInst>(U))
155  CoroFrees.push_back(CF);
156 
157  if (CoroFrees.empty())
158  return;
159 
160  Value *Replacement =
162  : CoroFrees.front()->getFrame();
163 
164  for (CoroFreeInst *CF : CoroFrees) {
165  CF->replaceAllUsesWith(Replacement);
166  CF->eraseFromParent();
167  }
168 }
169 
170 // FIXME: This code is stolen from CallGraph::addToCallGraph(Function *F), which
171 // happens to be private. It is better for this functionality exposed by the
172 // CallGraph.
173 static void buildCGN(CallGraph &CG, CallGraphNode *Node) {
174  Function *F = Node->getFunction();
175 
176  // Look for calls by this function.
177  for (Instruction &I : instructions(F))
178  if (CallSite CS = CallSite(cast<Value>(&I))) {
179  const Function *Callee = CS.getCalledFunction();
180  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
181  // Indirect calls of intrinsics are not allowed so no need to check.
182  // We can be more precise here by using TargetArg returned by
183  // Intrinsic::isLeaf.
184  Node->addCalledFunction(CS, CG.getCallsExternalNode());
185  else if (!Callee->isIntrinsic())
186  Node->addCalledFunction(CS, CG.getOrInsertFunction(Callee));
187  }
188 }
189 
190 // Rebuild CGN after we extracted parts of the code from ParentFunc into
191 // NewFuncs. Builds CGNs for the NewFuncs and adds them to the current SCC.
193  CallGraph &CG, CallGraphSCC &SCC) {
194  // Rebuild CGN from scratch for the ParentFunc
195  auto *ParentNode = CG[&ParentFunc];
196  ParentNode->removeAllCalledFunctions();
197  buildCGN(CG, ParentNode);
198 
199  SmallVector<CallGraphNode *, 8> Nodes(SCC.begin(), SCC.end());
200 
201  for (Function *F : NewFuncs) {
203  Nodes.push_back(Callee);
204  buildCGN(CG, Callee);
205  }
206 
207  SCC.initialize(Nodes);
208 }
209 
210 static void clear(coro::Shape &Shape) {
211  Shape.CoroBegin = nullptr;
212  Shape.CoroEnds.clear();
213  Shape.CoroSizes.clear();
214  Shape.CoroSuspends.clear();
215 
216  Shape.FrameTy = nullptr;
217  Shape.FramePtr = nullptr;
218  Shape.AllocaSpillBlock = nullptr;
219  Shape.ResumeSwitch = nullptr;
220  Shape.PromiseAlloca = nullptr;
221  Shape.HasFinalSuspend = false;
222 }
223 
225  CoroSuspendInst *SuspendInst) {
226  Module *M = SuspendInst->getModule();
227  auto *Fn = Intrinsic::getDeclaration(M, Intrinsic::coro_save);
228  auto *SaveInst =
229  cast<CoroSaveInst>(CallInst::Create(Fn, CoroBegin, "", SuspendInst));
230  assert(!SuspendInst->getCoroSave());
231  SuspendInst->setArgOperand(0, SaveInst);
232  return SaveInst;
233 }
234 
235 // Collect "interesting" coroutine intrinsics.
237  size_t FinalSuspendIndex = 0;
238  clear(*this);
240  SmallVector<CoroSaveInst *, 2> UnusedCoroSaves;
241 
242  for (Instruction &I : instructions(F)) {
243  if (auto II = dyn_cast<IntrinsicInst>(&I)) {
244  switch (II->getIntrinsicID()) {
245  default:
246  continue;
247  case Intrinsic::coro_size:
248  CoroSizes.push_back(cast<CoroSizeInst>(II));
249  break;
250  case Intrinsic::coro_frame:
251  CoroFrames.push_back(cast<CoroFrameInst>(II));
252  break;
253  case Intrinsic::coro_save:
254  // After optimizations, coro_suspends using this coro_save might have
255  // been removed, remember orphaned coro_saves to remove them later.
256  if (II->use_empty())
257  UnusedCoroSaves.push_back(cast<CoroSaveInst>(II));
258  break;
259  case Intrinsic::coro_suspend:
260  CoroSuspends.push_back(cast<CoroSuspendInst>(II));
261  if (CoroSuspends.back()->isFinal()) {
262  if (HasFinalSuspend)
264  "Only one suspend point can be marked as final");
265  HasFinalSuspend = true;
266  FinalSuspendIndex = CoroSuspends.size() - 1;
267  }
268  break;
269  case Intrinsic::coro_begin: {
270  auto CB = cast<CoroBeginInst>(II);
271  if (CB->getId()->getInfo().isPreSplit()) {
272  if (CoroBegin)
274  "coroutine should have exactly one defining @llvm.coro.begin");
275  CB->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
277  CB->removeAttribute(AttributeList::FunctionIndex,
278  Attribute::NoDuplicate);
279  CoroBegin = CB;
280  }
281  break;
282  }
283  case Intrinsic::coro_end:
284  CoroEnds.push_back(cast<CoroEndInst>(II));
285  if (CoroEnds.back()->isFallthrough()) {
286  // Make sure that the fallthrough coro.end is the first element in the
287  // CoroEnds vector.
288  if (CoroEnds.size() > 1) {
289  if (CoroEnds.front()->isFallthrough())
291  "Only one coro.end can be marked as fallthrough");
292  std::swap(CoroEnds.front(), CoroEnds.back());
293  }
294  }
295  break;
296  }
297  }
298  }
299 
300  // If for some reason, we were not able to find coro.begin, bailout.
301  if (!CoroBegin) {
302  // Replace coro.frame which are supposed to be lowered to the result of
303  // coro.begin with undef.
305  for (CoroFrameInst *CF : CoroFrames) {
306  CF->replaceAllUsesWith(Undef);
307  CF->eraseFromParent();
308  }
309 
310  // Replace all coro.suspend with undef and remove related coro.saves if
311  // present.
312  for (CoroSuspendInst *CS : CoroSuspends) {
313  CS->replaceAllUsesWith(UndefValue::get(CS->getType()));
314  CS->eraseFromParent();
315  if (auto *CoroSave = CS->getCoroSave())
316  CoroSave->eraseFromParent();
317  }
318 
319  // Replace all coro.ends with unreachable instruction.
320  for (CoroEndInst *CE : CoroEnds)
321  changeToUnreachable(CE, /*UseLLVMTrap=*/false);
322 
323  return;
324  }
325 
326  // The coro.free intrinsic is always lowered to the result of coro.begin.
327  for (CoroFrameInst *CF : CoroFrames) {
328  CF->replaceAllUsesWith(CoroBegin);
329  CF->eraseFromParent();
330  }
331 
332  // Canonicalize coro.suspend by inserting a coro.save if needed.
333  for (CoroSuspendInst *CS : CoroSuspends)
334  if (!CS->getCoroSave())
335  createCoroSave(CoroBegin, CS);
336 
337  // Move final suspend to be the last element in the CoroSuspends vector.
338  if (HasFinalSuspend &&
339  FinalSuspendIndex != CoroSuspends.size() - 1)
340  std::swap(CoroSuspends[FinalSuspendIndex], CoroSuspends.back());
341 
342  // Remove orphaned coro.saves.
343  for (CoroSaveInst *CoroSave : UnusedCoroSaves)
344  CoroSave->eraseFromParent();
345 }
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:180
Instruction * FramePtr
Definition: CoroInternal.h:83
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:173
EP_ScalarOptimizerLate - This extension point allows adding optimization passes after most of the mai...
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:728
virtual void add(Pass *P)=0
Add a pass to the queue of passes to run.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
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)
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1452
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:236
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: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:980
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:1306
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:963
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:321
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:1320
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:82
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:224
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
A constant pointer value that points to null.
Definition: Constants.h:530
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:560
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:175
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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:57
Value * makeSubFnCall(Value *Arg, int Index, Instruction *InsertPt)
Definition: Coroutines.cpp:107
iterator_range< user_iterator > users()
Definition: Value.h:401
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:210
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:61
SwitchInst * ResumeSwitch
Definition: CoroInternal.h:85
const NodeList & List
Definition: RDFGraph.cpp:210
#define I(x, y, z)
Definition: MD5.cpp:58
void setArgOperand(unsigned i, Value *v)
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:151
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallVector< CoroEndInst *, 4 > CoroEnds
Definition: CoroInternal.h:69
AllocaInst * PromiseAlloca
Definition: CoroInternal.h:86
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:80
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:138
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:84
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:192