LLVM  9.0.0svn
CoroSplit.cpp
Go to the documentation of this file.
1 //===- CoroSplit.cpp - Converts a coroutine into a state machine ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // This pass builds the coroutine frame and outlines resume and destroy parts
9 // of the coroutine into separate functions.
10 //
11 // We present a coroutine to an LLVM as an ordinary function with suspension
12 // points marked up with intrinsics. We let the optimizer party on the coroutine
13 // as a single function for as long as possible. Shortly before the coroutine is
14 // eligible to be inlined into its callers, we split up the coroutine into parts
15 // corresponding to an initial, resume and destroy invocations of the coroutine,
16 // add them to the current SCC and restart the IPO pipeline to optimize the
17 // coroutine subfunctions we extracted before proceeding to the caller of the
18 // coroutine.
19 //===----------------------------------------------------------------------===//
20 
21 #include "CoroInstr.h"
22 #include "CoroInternal.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/ADT/Twine.h"
31 #include "llvm/IR/Argument.h"
32 #include "llvm/IR/Attributes.h"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/CFG.h"
35 #include "llvm/IR/CallSite.h"
36 #include "llvm/IR/CallingConv.h"
37 #include "llvm/IR/Constants.h"
38 #include "llvm/IR/DataLayout.h"
39 #include "llvm/IR/DerivedTypes.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/GlobalValue.h"
42 #include "llvm/IR/GlobalVariable.h"
43 #include "llvm/IR/IRBuilder.h"
44 #include "llvm/IR/InstIterator.h"
45 #include "llvm/IR/InstrTypes.h"
46 #include "llvm/IR/Instruction.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/IntrinsicInst.h"
49 #include "llvm/IR/LLVMContext.h"
51 #include "llvm/IR/Module.h"
52 #include "llvm/IR/Type.h"
53 #include "llvm/IR/Value.h"
54 #include "llvm/IR/Verifier.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/Debug.h"
59 #include "llvm/Transforms/Scalar.h"
63 #include <cassert>
64 #include <cstddef>
65 #include <cstdint>
66 #include <initializer_list>
67 #include <iterator>
68 
69 using namespace llvm;
70 
71 #define DEBUG_TYPE "coro-split"
72 
73 // Create an entry block for a resume function with a switch that will jump to
74 // suspend points.
76  LLVMContext &C = F.getContext();
77 
78  // resume.entry:
79  // %index.addr = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr, i32 0,
80  // i32 2
81  // % index = load i32, i32* %index.addr
82  // switch i32 %index, label %unreachable [
83  // i32 0, label %resume.0
84  // i32 1, label %resume.1
85  // ...
86  // ]
87 
88  auto *NewEntry = BasicBlock::Create(C, "resume.entry", &F);
89  auto *UnreachBB = BasicBlock::Create(C, "unreachable", &F);
90 
91  IRBuilder<> Builder(NewEntry);
92  auto *FramePtr = Shape.FramePtr;
93  auto *FrameTy = Shape.FrameTy;
94  auto *GepIndex = Builder.CreateConstInBoundsGEP2_32(
95  FrameTy, FramePtr, 0, coro::Shape::IndexField, "index.addr");
96  auto *Index = Builder.CreateLoad(Shape.getIndexType(), GepIndex, "index");
97  auto *Switch =
98  Builder.CreateSwitch(Index, UnreachBB, Shape.CoroSuspends.size());
99  Shape.ResumeSwitch = Switch;
100 
101  size_t SuspendIndex = 0;
102  for (CoroSuspendInst *S : Shape.CoroSuspends) {
103  ConstantInt *IndexVal = Shape.getIndex(SuspendIndex);
104 
105  // Replace CoroSave with a store to Index:
106  // %index.addr = getelementptr %f.frame... (index field number)
107  // store i32 0, i32* %index.addr1
108  auto *Save = S->getCoroSave();
109  Builder.SetInsertPoint(Save);
110  if (S->isFinal()) {
111  // Final suspend point is represented by storing zero in ResumeFnAddr.
112  auto *GepIndex = Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0,
113  0, "ResumeFn.addr");
114  auto *NullPtr = ConstantPointerNull::get(cast<PointerType>(
115  cast<PointerType>(GepIndex->getType())->getElementType()));
116  Builder.CreateStore(NullPtr, GepIndex);
117  } else {
118  auto *GepIndex = Builder.CreateConstInBoundsGEP2_32(
119  FrameTy, FramePtr, 0, coro::Shape::IndexField, "index.addr");
120  Builder.CreateStore(IndexVal, GepIndex);
121  }
123  Save->eraseFromParent();
124 
125  // Split block before and after coro.suspend and add a jump from an entry
126  // switch:
127  //
128  // whateverBB:
129  // whatever
130  // %0 = call i8 @llvm.coro.suspend(token none, i1 false)
131  // switch i8 %0, label %suspend[i8 0, label %resume
132  // i8 1, label %cleanup]
133  // becomes:
134  //
135  // whateverBB:
136  // whatever
137  // br label %resume.0.landing
138  //
139  // resume.0: ; <--- jump from the switch in the resume.entry
140  // %0 = tail call i8 @llvm.coro.suspend(token none, i1 false)
141  // br label %resume.0.landing
142  //
143  // resume.0.landing:
144  // %1 = phi i8[-1, %whateverBB], [%0, %resume.0]
145  // switch i8 % 1, label %suspend [i8 0, label %resume
146  // i8 1, label %cleanup]
147 
148  auto *SuspendBB = S->getParent();
149  auto *ResumeBB =
150  SuspendBB->splitBasicBlock(S, "resume." + Twine(SuspendIndex));
151  auto *LandingBB = ResumeBB->splitBasicBlock(
152  S->getNextNode(), ResumeBB->getName() + Twine(".landing"));
153  Switch->addCase(IndexVal, ResumeBB);
154 
155  cast<BranchInst>(SuspendBB->getTerminator())->setSuccessor(0, LandingBB);
156  auto *PN = PHINode::Create(Builder.getInt8Ty(), 2, "", &LandingBB->front());
157  S->replaceAllUsesWith(PN);
158  PN->addIncoming(Builder.getInt8(-1), SuspendBB);
159  PN->addIncoming(S, ResumeBB);
160 
161  ++SuspendIndex;
162  }
163 
164  Builder.SetInsertPoint(UnreachBB);
165  Builder.CreateUnreachable();
166 
167  return NewEntry;
168 }
169 
170 // In Resumers, we replace fallthrough coro.end with ret void and delete the
171 // rest of the block.
173  ValueToValueMapTy &VMap) {
174  auto *NewE = cast<IntrinsicInst>(VMap[End]);
175  ReturnInst::Create(NewE->getContext(), nullptr, NewE);
176 
177  // Remove the rest of the block, by splitting it into an unreachable block.
178  auto *BB = NewE->getParent();
179  BB->splitBasicBlock(NewE);
181 }
182 
183 // In Resumers, we replace unwind coro.end with True to force the immediate
184 // unwind to caller.
186  if (Shape.CoroEnds.empty())
187  return;
188 
189  LLVMContext &Context = Shape.CoroEnds.front()->getContext();
190  auto *True = ConstantInt::getTrue(Context);
191  for (CoroEndInst *CE : Shape.CoroEnds) {
192  if (!CE->isUnwind())
193  continue;
194 
195  auto *NewCE = cast<IntrinsicInst>(VMap[CE]);
196 
197  // If coro.end has an associated bundle, add cleanupret instruction.
198  if (auto Bundle = NewCE->getOperandBundle(LLVMContext::OB_funclet)) {
199  Value *FromPad = Bundle->Inputs[0];
200  auto *CleanupRet = CleanupReturnInst::Create(FromPad, nullptr, NewCE);
201  NewCE->getParent()->splitBasicBlock(NewCE);
202  CleanupRet->getParent()->getTerminator()->eraseFromParent();
203  }
204 
205  NewCE->replaceAllUsesWith(True);
206  NewCE->eraseFromParent();
207  }
208 }
209 
210 // Rewrite final suspend point handling. We do not use suspend index to
211 // represent the final suspend point. Instead we zero-out ResumeFnAddr in the
212 // coroutine frame, since it is undefined behavior to resume a coroutine
213 // suspended at the final suspend point. Thus, in the resume function, we can
214 // simply remove the last case (when coro::Shape is built, the final suspend
215 // point (if present) is always the last element of CoroSuspends array).
216 // In the destroy function, we add a code sequence to check if ResumeFnAddress
217 // is Null, and if so, jump to the appropriate label to handle cleanup from the
218 // final suspend point.
219 static void handleFinalSuspend(IRBuilder<> &Builder, Value *FramePtr,
220  coro::Shape &Shape, SwitchInst *Switch,
221  bool IsDestroy) {
222  assert(Shape.HasFinalSuspend);
223  auto FinalCaseIt = std::prev(Switch->case_end());
224  BasicBlock *ResumeBB = FinalCaseIt->getCaseSuccessor();
225  Switch->removeCase(FinalCaseIt);
226  if (IsDestroy) {
227  BasicBlock *OldSwitchBB = Switch->getParent();
228  auto *NewSwitchBB = OldSwitchBB->splitBasicBlock(Switch, "Switch");
229  Builder.SetInsertPoint(OldSwitchBB->getTerminator());
230  auto *GepIndex = Builder.CreateConstInBoundsGEP2_32(Shape.FrameTy, FramePtr,
231  0, 0, "ResumeFn.addr");
232  auto *Load = Builder.CreateLoad(
234  auto *NullPtr =
235  ConstantPointerNull::get(cast<PointerType>(Load->getType()));
236  auto *Cond = Builder.CreateICmpEQ(Load, NullPtr);
237  Builder.CreateCondBr(Cond, ResumeBB, NewSwitchBB);
238  OldSwitchBB->getTerminator()->eraseFromParent();
239  }
240 }
241 
242 // Create a resume clone by cloning the body of the original function, setting
243 // new entry block and replacing coro.suspend an appropriate value to force
244 // resume or cleanup pass for every suspend point.
245 static Function *createClone(Function &F, Twine Suffix, coro::Shape &Shape,
246  BasicBlock *ResumeEntry, int8_t FnIndex) {
247  Module *M = F.getParent();
248  auto *FrameTy = Shape.FrameTy;
249  auto *FnPtrTy = cast<PointerType>(FrameTy->getElementType(0));
250  auto *FnTy = cast<FunctionType>(FnPtrTy->getElementType());
251 
252  Function *NewF =
253  Function::Create(FnTy, GlobalValue::LinkageTypes::ExternalLinkage,
254  F.getName() + Suffix, M);
255  NewF->addParamAttr(0, Attribute::NonNull);
256  NewF->addParamAttr(0, Attribute::NoAlias);
257 
258  ValueToValueMapTy VMap;
259  // Replace all args with undefs. The buildCoroutineFrame algorithm already
260  // rewritten access to the args that occurs after suspend points with loads
261  // and stores to/from the coroutine frame.
262  for (Argument &A : F.args())
263  VMap[&A] = UndefValue::get(A.getType());
264 
266 
267  CloneFunctionInto(NewF, &F, VMap, /*ModuleLevelChanges=*/true, Returns);
268  NewF->setLinkage(GlobalValue::LinkageTypes::InternalLinkage);
269 
270  // Remove old returns.
271  for (ReturnInst *Return : Returns)
272  changeToUnreachable(Return, /*UseLLVMTrap=*/false);
273 
274  // Remove old return attributes.
275  NewF->removeAttributes(
277  AttributeFuncs::typeIncompatible(NewF->getReturnType()));
278 
279  // Make AllocaSpillBlock the new entry block.
280  auto *SwitchBB = cast<BasicBlock>(VMap[ResumeEntry]);
281  auto *Entry = cast<BasicBlock>(VMap[Shape.AllocaSpillBlock]);
282  Entry->moveBefore(&NewF->getEntryBlock());
283  Entry->getTerminator()->eraseFromParent();
284  BranchInst::Create(SwitchBB, Entry);
285  Entry->setName("entry" + Suffix);
286 
287  // Clear all predecessors of the new entry block.
288  auto *Switch = cast<SwitchInst>(VMap[Shape.ResumeSwitch]);
289  Entry->replaceAllUsesWith(Switch->getDefaultDest());
290 
291  IRBuilder<> Builder(&NewF->getEntryBlock().front());
292 
293  // Remap frame pointer.
294  Argument *NewFramePtr = &*NewF->arg_begin();
295  Value *OldFramePtr = cast<Value>(VMap[Shape.FramePtr]);
296  NewFramePtr->takeName(OldFramePtr);
297  OldFramePtr->replaceAllUsesWith(NewFramePtr);
298 
299  // Remap vFrame pointer.
300  auto *NewVFrame = Builder.CreateBitCast(
301  NewFramePtr, Type::getInt8PtrTy(Builder.getContext()), "vFrame");
302  Value *OldVFrame = cast<Value>(VMap[Shape.CoroBegin]);
303  OldVFrame->replaceAllUsesWith(NewVFrame);
304 
305  // Rewrite final suspend handling as it is not done via switch (allows to
306  // remove final case from the switch, since it is undefined behavior to resume
307  // the coroutine suspended at the final suspend point.
308  if (Shape.HasFinalSuspend) {
309  auto *Switch = cast<SwitchInst>(VMap[Shape.ResumeSwitch]);
310  bool IsDestroy = FnIndex != 0;
311  handleFinalSuspend(Builder, NewFramePtr, Shape, Switch, IsDestroy);
312  }
313 
314  // Replace coro suspend with the appropriate resume index.
315  // Replacing coro.suspend with (0) will result in control flow proceeding to
316  // a resume label associated with a suspend point, replacing it with (1) will
317  // result in control flow proceeding to a cleanup label associated with this
318  // suspend point.
319  auto *NewValue = Builder.getInt8(FnIndex ? 1 : 0);
320  for (CoroSuspendInst *CS : Shape.CoroSuspends) {
321  auto *MappedCS = cast<CoroSuspendInst>(VMap[CS]);
322  MappedCS->replaceAllUsesWith(NewValue);
323  MappedCS->eraseFromParent();
324  }
325 
326  // Remove coro.end intrinsics.
327  replaceFallthroughCoroEnd(Shape.CoroEnds.front(), VMap);
328  replaceUnwindCoroEnds(Shape, VMap);
329  // Eliminate coro.free from the clones, replacing it with 'null' in cleanup,
330  // to suppress deallocation code.
331  coro::replaceCoroFree(cast<CoroIdInst>(VMap[Shape.CoroBegin->getId()]),
332  /*Elide=*/FnIndex == 2);
333 
334  NewF->setCallingConv(CallingConv::Fast);
335 
336  return NewF;
337 }
338 
339 static void removeCoroEnds(coro::Shape &Shape) {
340  if (Shape.CoroEnds.empty())
341  return;
342 
343  LLVMContext &Context = Shape.CoroEnds.front()->getContext();
344  auto *False = ConstantInt::getFalse(Context);
345 
346  for (CoroEndInst *CE : Shape.CoroEnds) {
347  CE->replaceAllUsesWith(False);
348  CE->eraseFromParent();
349  }
350 }
351 
352 static void replaceFrameSize(coro::Shape &Shape) {
353  if (Shape.CoroSizes.empty())
354  return;
355 
356  // In the same function all coro.sizes should have the same result type.
357  auto *SizeIntrin = Shape.CoroSizes.back();
358  Module *M = SizeIntrin->getModule();
359  const DataLayout &DL = M->getDataLayout();
360  auto Size = DL.getTypeAllocSize(Shape.FrameTy);
361  auto *SizeConstant = ConstantInt::get(SizeIntrin->getType(), Size);
362 
363  for (CoroSizeInst *CS : Shape.CoroSizes) {
364  CS->replaceAllUsesWith(SizeConstant);
365  CS->eraseFromParent();
366  }
367 }
368 
369 // Create a global constant array containing pointers to functions provided and
370 // set Info parameter of CoroBegin to point at this constant. Example:
371 //
372 // @f.resumers = internal constant [2 x void(%f.frame*)*]
373 // [void(%f.frame*)* @f.resume, void(%f.frame*)* @f.destroy]
374 // define void @f() {
375 // ...
376 // call i8* @llvm.coro.begin(i8* null, i32 0, i8* null,
377 // i8* bitcast([2 x void(%f.frame*)*] * @f.resumers to i8*))
378 //
379 // Assumes that all the functions have the same signature.
380 static void setCoroInfo(Function &F, CoroBeginInst *CoroBegin,
381  std::initializer_list<Function *> Fns) {
382  SmallVector<Constant *, 4> Args(Fns.begin(), Fns.end());
383  assert(!Args.empty());
384  Function *Part = *Fns.begin();
385  Module *M = Part->getParent();
386  auto *ArrTy = ArrayType::get(Part->getType(), Args.size());
387 
388  auto *ConstVal = ConstantArray::get(ArrTy, Args);
389  auto *GV = new GlobalVariable(*M, ConstVal->getType(), /*isConstant=*/true,
391  F.getName() + Twine(".resumers"));
392 
393  // Update coro.begin instruction to refer to this constant.
394  LLVMContext &C = F.getContext();
396  CoroBegin->getId()->setInfo(BC);
397 }
398 
399 // Store addresses of Resume/Destroy/Cleanup functions in the coroutine frame.
400 static void updateCoroFrame(coro::Shape &Shape, Function *ResumeFn,
401  Function *DestroyFn, Function *CleanupFn) {
402  IRBuilder<> Builder(Shape.FramePtr->getNextNode());
403  auto *ResumeAddr = Builder.CreateConstInBoundsGEP2_32(
404  Shape.FrameTy, Shape.FramePtr, 0, coro::Shape::ResumeField,
405  "resume.addr");
406  Builder.CreateStore(ResumeFn, ResumeAddr);
407 
408  Value *DestroyOrCleanupFn = DestroyFn;
409 
410  CoroIdInst *CoroId = Shape.CoroBegin->getId();
411  if (CoroAllocInst *CA = CoroId->getCoroAlloc()) {
412  // If there is a CoroAlloc and it returns false (meaning we elide the
413  // allocation, use CleanupFn instead of DestroyFn).
414  DestroyOrCleanupFn = Builder.CreateSelect(CA, DestroyFn, CleanupFn);
415  }
416 
417  auto *DestroyAddr = Builder.CreateConstInBoundsGEP2_32(
418  Shape.FrameTy, Shape.FramePtr, 0, coro::Shape::DestroyField,
419  "destroy.addr");
420  Builder.CreateStore(DestroyOrCleanupFn, DestroyAddr);
421 }
422 
423 static void postSplitCleanup(Function &F) {
426 
427  FPM.add(createVerifierPass());
428  FPM.add(createSCCPPass());
429  FPM.add(createCFGSimplificationPass());
430  FPM.add(createEarlyCSEPass());
431  FPM.add(createCFGSimplificationPass());
432 
433  FPM.doInitialization();
434  FPM.run(F);
435  FPM.doFinalization();
436 }
437 
438 // Assuming we arrived at the block NewBlock from Prev instruction, store
439 // PHI's incoming values in the ResolvedValues map.
440 static void
442  DenseMap<Value *, Value *> &ResolvedValues) {
443  auto *PrevBB = Prev->getParent();
444  for (PHINode &PN : NewBlock->phis()) {
445  auto V = PN.getIncomingValueForBlock(PrevBB);
446  // See if we already resolved it.
447  auto VI = ResolvedValues.find(V);
448  if (VI != ResolvedValues.end())
449  V = VI->second;
450  // Remember the value.
451  ResolvedValues[&PN] = V;
452  }
453 }
454 
455 // Replace a sequence of branches leading to a ret, with a clone of a ret
456 // instruction. Suspend instruction represented by a switch, track the PHI
457 // values and select the correct case successor when possible.
458 static bool simplifyTerminatorLeadingToRet(Instruction *InitialInst) {
459  DenseMap<Value *, Value *> ResolvedValues;
460 
461  Instruction *I = InitialInst;
462  while (I->isTerminator()) {
463  if (isa<ReturnInst>(I)) {
464  if (I != InitialInst)
465  ReplaceInstWithInst(InitialInst, I->clone());
466  return true;
467  }
468  if (auto *BR = dyn_cast<BranchInst>(I)) {
469  if (BR->isUnconditional()) {
470  BasicBlock *BB = BR->getSuccessor(0);
471  scanPHIsAndUpdateValueMap(I, BB, ResolvedValues);
473  continue;
474  }
475  } else if (auto *SI = dyn_cast<SwitchInst>(I)) {
476  Value *V = SI->getCondition();
477  auto it = ResolvedValues.find(V);
478  if (it != ResolvedValues.end())
479  V = it->second;
480  if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
481  BasicBlock *BB = SI->findCaseValue(Cond)->getCaseSuccessor();
482  scanPHIsAndUpdateValueMap(I, BB, ResolvedValues);
484  continue;
485  }
486  }
487  return false;
488  }
489  return false;
490 }
491 
492 // Add musttail to any resume instructions that is immediately followed by a
493 // suspend (i.e. ret). We do this even in -O0 to support guaranteed tail call
494 // for symmetrical coroutine control transfer (C++ Coroutines TS extension).
495 // This transformation is done only in the resume part of the coroutine that has
496 // identical signature and calling convention as the coro.resume call.
498  bool changed = false;
499 
500  // Collect potential resume instructions.
502  for (auto &I : instructions(F))
503  if (auto *Call = dyn_cast<CallInst>(&I))
504  if (auto *CalledValue = Call->getCalledValue())
505  // CoroEarly pass replaced coro resumes with indirect calls to an
506  // address return by CoroSubFnInst intrinsic. See if it is one of those.
507  if (isa<CoroSubFnInst>(CalledValue->stripPointerCasts()))
508  Resumes.push_back(Call);
509 
510  // Set musttail on those that are followed by a ret instruction.
511  for (CallInst *Call : Resumes)
512  if (simplifyTerminatorLeadingToRet(Call->getNextNode())) {
513  Call->setTailCallKind(CallInst::TCK_MustTail);
514  changed = true;
515  }
516 
517  if (changed)
519 }
520 
521 // Coroutine has no suspend points. Remove heap allocation for the coroutine
522 // frame if possible.
523 static void handleNoSuspendCoroutine(CoroBeginInst *CoroBegin, Type *FrameTy) {
524  auto *CoroId = CoroBegin->getId();
525  auto *AllocInst = CoroId->getCoroAlloc();
526  coro::replaceCoroFree(CoroId, /*Elide=*/AllocInst != nullptr);
527  if (AllocInst) {
528  IRBuilder<> Builder(AllocInst);
529  // FIXME: Need to handle overaligned members.
530  auto *Frame = Builder.CreateAlloca(FrameTy);
531  auto *VFrame = Builder.CreateBitCast(Frame, Builder.getInt8PtrTy());
532  AllocInst->replaceAllUsesWith(Builder.getFalse());
533  AllocInst->eraseFromParent();
534  CoroBegin->replaceAllUsesWith(VFrame);
535  } else {
536  CoroBegin->replaceAllUsesWith(CoroBegin->getMem());
537  }
538  CoroBegin->eraseFromParent();
539 }
540 
541 // SimplifySuspendPoint needs to check that there is no calls between
542 // coro_save and coro_suspend, since any of the calls may potentially resume
543 // the coroutine and if that is the case we cannot eliminate the suspend point.
545  for (Instruction *I = From; I != To; I = I->getNextNode()) {
546  // Assume that no intrinsic can resume the coroutine.
547  if (isa<IntrinsicInst>(I))
548  continue;
549 
550  if (CallSite(I))
551  return true;
552  }
553  return false;
554 }
555 
556 static bool hasCallsInBlocksBetween(BasicBlock *SaveBB, BasicBlock *ResDesBB) {
559 
560  Set.insert(SaveBB);
561  Worklist.push_back(ResDesBB);
562 
563  // Accumulate all blocks between SaveBB and ResDesBB. Because CoroSaveIntr
564  // returns a token consumed by suspend instruction, all blocks in between
565  // will have to eventually hit SaveBB when going backwards from ResDesBB.
566  while (!Worklist.empty()) {
567  auto *BB = Worklist.pop_back_val();
568  Set.insert(BB);
569  for (auto *Pred : predecessors(BB))
570  if (Set.count(Pred) == 0)
571  Worklist.push_back(Pred);
572  }
573 
574  // SaveBB and ResDesBB are checked separately in hasCallsBetween.
575  Set.erase(SaveBB);
576  Set.erase(ResDesBB);
577 
578  for (auto *BB : Set)
579  if (hasCallsInBlockBetween(BB->getFirstNonPHI(), nullptr))
580  return true;
581 
582  return false;
583 }
584 
585 static bool hasCallsBetween(Instruction *Save, Instruction *ResumeOrDestroy) {
586  auto *SaveBB = Save->getParent();
587  auto *ResumeOrDestroyBB = ResumeOrDestroy->getParent();
588 
589  if (SaveBB == ResumeOrDestroyBB)
590  return hasCallsInBlockBetween(Save->getNextNode(), ResumeOrDestroy);
591 
592  // Any calls from Save to the end of the block?
593  if (hasCallsInBlockBetween(Save->getNextNode(), nullptr))
594  return true;
595 
596  // Any calls from begging of the block up to ResumeOrDestroy?
597  if (hasCallsInBlockBetween(ResumeOrDestroyBB->getFirstNonPHI(),
598  ResumeOrDestroy))
599  return true;
600 
601  // Any calls in all of the blocks between SaveBB and ResumeOrDestroyBB?
602  if (hasCallsInBlocksBetween(SaveBB, ResumeOrDestroyBB))
603  return true;
604 
605  return false;
606 }
607 
608 // If a SuspendIntrin is preceded by Resume or Destroy, we can eliminate the
609 // suspend point and replace it with nornal control flow.
611  CoroBeginInst *CoroBegin) {
612  Instruction *Prev = Suspend->getPrevNode();
613  if (!Prev) {
614  auto *Pred = Suspend->getParent()->getSinglePredecessor();
615  if (!Pred)
616  return false;
617  Prev = Pred->getTerminator();
618  }
619 
620  CallSite CS{Prev};
621  if (!CS)
622  return false;
623 
624  auto *CallInstr = CS.getInstruction();
625 
626  auto *Callee = CS.getCalledValue()->stripPointerCasts();
627 
628  // See if the callsite is for resumption or destruction of the coroutine.
629  auto *SubFn = dyn_cast<CoroSubFnInst>(Callee);
630  if (!SubFn)
631  return false;
632 
633  // Does not refer to the current coroutine, we cannot do anything with it.
634  if (SubFn->getFrame() != CoroBegin)
635  return false;
636 
637  // See if the transformation is safe. Specifically, see if there are any
638  // calls in between Save and CallInstr. They can potenitally resume the
639  // coroutine rendering this optimization unsafe.
640  auto *Save = Suspend->getCoroSave();
641  if (hasCallsBetween(Save, CallInstr))
642  return false;
643 
644  // Replace llvm.coro.suspend with the value that results in resumption over
645  // the resume or cleanup path.
646  Suspend->replaceAllUsesWith(SubFn->getRawIndex());
647  Suspend->eraseFromParent();
648  Save->eraseFromParent();
649 
650  // No longer need a call to coro.resume or coro.destroy.
651  if (auto *Invoke = dyn_cast<InvokeInst>(CallInstr)) {
652  BranchInst::Create(Invoke->getNormalDest(), Invoke);
653  }
654 
655  // Grab the CalledValue from CS before erasing the CallInstr.
656  auto *CalledValue = CS.getCalledValue();
657  CallInstr->eraseFromParent();
658 
659  // If no more users remove it. Usually it is a bitcast of SubFn.
660  if (CalledValue != SubFn && CalledValue->user_empty())
661  if (auto *I = dyn_cast<Instruction>(CalledValue))
662  I->eraseFromParent();
663 
664  // Now we are good to remove SubFn.
665  if (SubFn->user_empty())
666  SubFn->eraseFromParent();
667 
668  return true;
669 }
670 
671 // Remove suspend points that are simplified.
672 static void simplifySuspendPoints(coro::Shape &Shape) {
673  auto &S = Shape.CoroSuspends;
674  size_t I = 0, N = S.size();
675  if (N == 0)
676  return;
677  while (true) {
678  if (simplifySuspendPoint(S[I], Shape.CoroBegin)) {
679  if (--N == I)
680  break;
681  std::swap(S[I], S[N]);
682  continue;
683  }
684  if (++I == N)
685  break;
686  }
687  S.resize(N);
688 }
689 
691  // Collect all blocks that we need to look for instructions to relocate.
692  SmallPtrSet<BasicBlock *, 4> RelocBlocks;
694  Work.push_back(CB->getParent());
695 
696  do {
697  BasicBlock *Current = Work.pop_back_val();
698  for (BasicBlock *BB : predecessors(Current))
699  if (RelocBlocks.count(BB) == 0) {
700  RelocBlocks.insert(BB);
701  Work.push_back(BB);
702  }
703  } while (!Work.empty());
704  return RelocBlocks;
705 }
706 
709  SmallPtrSetImpl<BasicBlock *> &RelocBlocks) {
710  SmallPtrSet<Instruction *, 8> DoNotRelocate;
711  // Collect all instructions that we should not relocate
713 
714  // Start with CoroBegin and terminators of all preceding blocks.
715  Work.push_back(CoroBegin);
716  BasicBlock *CoroBeginBB = CoroBegin->getParent();
717  for (BasicBlock *BB : RelocBlocks)
718  if (BB != CoroBeginBB)
719  Work.push_back(BB->getTerminator());
720 
721  // For every instruction in the Work list, place its operands in DoNotRelocate
722  // set.
723  do {
724  Instruction *Current = Work.pop_back_val();
725  LLVM_DEBUG(dbgs() << "CoroSplit: Will not relocate: " << *Current << "\n");
726  DoNotRelocate.insert(Current);
727  for (Value *U : Current->operands()) {
728  auto *I = dyn_cast<Instruction>(U);
729  if (!I)
730  continue;
731 
732  if (auto *A = dyn_cast<AllocaInst>(I)) {
733  // Stores to alloca instructions that occur before the coroutine frame
734  // is allocated should not be moved; the stored values may be used by
735  // the coroutine frame allocator. The operands to those stores must also
736  // remain in place.
737  for (const auto &User : A->users())
738  if (auto *SI = dyn_cast<llvm::StoreInst>(User))
739  if (RelocBlocks.count(SI->getParent()) != 0 &&
740  DoNotRelocate.count(SI) == 0) {
741  Work.push_back(SI);
742  DoNotRelocate.insert(SI);
743  }
744  continue;
745  }
746 
747  if (DoNotRelocate.count(I) == 0) {
748  Work.push_back(I);
749  DoNotRelocate.insert(I);
750  }
751  }
752  } while (!Work.empty());
753  return DoNotRelocate;
754 }
755 
757  // Analyze which non-alloca instructions are needed for allocation and
758  // relocate the rest to after coro.begin. We need to do it, since some of the
759  // targets of those instructions may be placed into coroutine frame memory
760  // for which becomes available after coro.begin intrinsic.
761 
762  auto BlockSet = getCoroBeginPredBlocks(CoroBegin);
763  auto DoNotRelocateSet = getNotRelocatableInstructions(CoroBegin, BlockSet);
764 
765  Instruction *InsertPt = CoroBegin->getNextNode();
766  BasicBlock &BB = F.getEntryBlock(); // TODO: Look at other blocks as well.
767  for (auto B = BB.begin(), E = BB.end(); B != E;) {
768  Instruction &I = *B++;
769  if (isa<AllocaInst>(&I))
770  continue;
771  if (&I == CoroBegin)
772  break;
773  if (DoNotRelocateSet.count(&I))
774  continue;
775  I.moveBefore(InsertPt);
776  }
777 }
778 
779 static void splitCoroutine(Function &F, CallGraph &CG, CallGraphSCC &SCC) {
781 
782  coro::Shape Shape(F);
783  if (!Shape.CoroBegin)
784  return;
785 
786  simplifySuspendPoints(Shape);
788  buildCoroutineFrame(F, Shape);
789  replaceFrameSize(Shape);
790 
791  // If there are no suspend points, no split required, just remove
792  // the allocation and deallocation blocks, they are not needed.
793  if (Shape.CoroSuspends.empty()) {
795  removeCoroEnds(Shape);
796  postSplitCleanup(F);
797  coro::updateCallGraph(F, {}, CG, SCC);
798  return;
799  }
800 
801  auto *ResumeEntry = createResumeEntryBlock(F, Shape);
802  auto ResumeClone = createClone(F, ".resume", Shape, ResumeEntry, 0);
803  auto DestroyClone = createClone(F, ".destroy", Shape, ResumeEntry, 1);
804  auto CleanupClone = createClone(F, ".cleanup", Shape, ResumeEntry, 2);
805 
806  // We no longer need coro.end in F.
807  removeCoroEnds(Shape);
808 
809  postSplitCleanup(F);
810  postSplitCleanup(*ResumeClone);
811  postSplitCleanup(*DestroyClone);
812  postSplitCleanup(*CleanupClone);
813 
814  addMustTailToCoroResumes(*ResumeClone);
815 
816  // Store addresses resume/destroy/cleanup functions in the coroutine frame.
817  updateCoroFrame(Shape, ResumeClone, DestroyClone, CleanupClone);
818 
819  // Create a constant array referring to resume/destroy/clone functions pointed
820  // by the last argument of @llvm.coro.info, so that CoroElide pass can
821  // determined correct function to call.
822  setCoroInfo(F, Shape.CoroBegin, {ResumeClone, DestroyClone, CleanupClone});
823 
824  // Update call graph and add the functions we created to the SCC.
825  coro::updateCallGraph(F, {ResumeClone, DestroyClone, CleanupClone}, CG, SCC);
826 }
827 
828 // When we see the coroutine the first time, we insert an indirect call to a
829 // devirt trigger function and mark the coroutine that it is now ready for
830 // split.
831 static void prepareForSplit(Function &F, CallGraph &CG) {
832  Module &M = *F.getParent();
834 #ifndef NDEBUG
836  assert(DevirtFn && "coro.devirt.trigger function not found");
837 #endif
838 
840 
841  // Insert an indirect call sequence that will be devirtualized by CoroElide
842  // pass:
843  // %0 = call i8* @llvm.coro.subfn.addr(i8* null, i8 -1)
844  // %1 = bitcast i8* %0 to void(i8*)*
845  // call void %1(i8* null)
846  coro::LowererBase Lowerer(M);
847  Instruction *InsertPt = F.getEntryBlock().getTerminator();
848  auto *Null = ConstantPointerNull::get(Type::getInt8PtrTy(Context));
849  auto *DevirtFnAddr =
850  Lowerer.makeSubFnCall(Null, CoroSubFnInst::RestartTrigger, InsertPt);
852  {Type::getInt8PtrTy(Context)}, false);
853  auto *IndirectCall = CallInst::Create(FnTy, DevirtFnAddr, Null, "", InsertPt);
854 
855  // Update CG graph with an indirect call we just added.
856  CG[&F]->addCalledFunction(IndirectCall, CG.getCallsExternalNode());
857 }
858 
859 // Make sure that there is a devirtualization trigger function that CoroSplit
860 // pass uses the force restart CGSCC pipeline. If devirt trigger function is not
861 // found, we will create one and add it to the current SCC.
863  Module &M = CG.getModule();
865  return;
866 
867  LLVMContext &C = M.getContext();
869  /*IsVarArgs=*/false);
870  Function *DevirtFn =
871  Function::Create(FnTy, GlobalValue::LinkageTypes::PrivateLinkage,
873  DevirtFn->addFnAttr(Attribute::AlwaysInline);
874  auto *Entry = BasicBlock::Create(C, "entry", DevirtFn);
876 
877  auto *Node = CG.getOrInsertFunction(DevirtFn);
878 
879  SmallVector<CallGraphNode *, 8> Nodes(SCC.begin(), SCC.end());
880  Nodes.push_back(Node);
881  SCC.initialize(Nodes);
882 }
883 
884 //===----------------------------------------------------------------------===//
885 // Top Level Driver
886 //===----------------------------------------------------------------------===//
887 
888 namespace {
889 
890 struct CoroSplit : public CallGraphSCCPass {
891  static char ID; // Pass identification, replacement for typeid
892 
893  CoroSplit() : CallGraphSCCPass(ID) {
895  }
896 
897  bool Run = false;
898 
899  // A coroutine is identified by the presence of coro.begin intrinsic, if
900  // we don't have any, this pass has nothing to do.
901  bool doInitialization(CallGraph &CG) override {
902  Run = coro::declaresIntrinsics(CG.getModule(), {"llvm.coro.begin"});
904  }
905 
906  bool runOnSCC(CallGraphSCC &SCC) override {
907  if (!Run)
908  return false;
909 
910  // Find coroutines for processing.
911  SmallVector<Function *, 4> Coroutines;
912  for (CallGraphNode *CGN : SCC)
913  if (auto *F = CGN->getFunction())
914  if (F->hasFnAttribute(CORO_PRESPLIT_ATTR))
915  Coroutines.push_back(F);
916 
917  if (Coroutines.empty())
918  return false;
919 
920  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
921  createDevirtTriggerFunc(CG, SCC);
922 
923  for (Function *F : Coroutines) {
924  Attribute Attr = F->getFnAttribute(CORO_PRESPLIT_ATTR);
926  LLVM_DEBUG(dbgs() << "CoroSplit: Processing coroutine '" << F->getName()
927  << "' state: " << Value << "\n");
928  if (Value == UNPREPARED_FOR_SPLIT) {
929  prepareForSplit(*F, CG);
930  continue;
931  }
932  F->removeFnAttr(CORO_PRESPLIT_ATTR);
933  splitCoroutine(*F, CG, SCC);
934  }
935  return true;
936  }
937 
938  void getAnalysisUsage(AnalysisUsage &AU) const override {
940  }
941 
942  StringRef getPassName() const override { return "Coroutine Splitting"; }
943 };
944 
945 } // end anonymous namespace
946 
947 char CoroSplit::ID = 0;
948 
950  CoroSplit, "coro-split",
951  "Split coroutine into a set of functions driving its state machine", false,
952  false)
953 
954 Pass *llvm::createCoroSplitPass() { return new CoroSplit(); }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:594
static void createDevirtTriggerFunc(CallGraph &CG, CallGraphSCC &SCC)
Definition: CoroSplit.cpp:862
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:853
CaseIt case_end()
Returns a read/write iterator that points one past the last in the SwitchInst.
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Instruction * FramePtr
Definition: CoroInternal.h:81
static void setCoroInfo(Function &F, CoroBeginInst *CoroBegin, std::initializer_list< Function *> Fns)
Definition: CoroSplit.cpp:380
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
LLVMContext & Context
AllocaInst * CreateAlloca(Type *Ty, unsigned AddrSpace, Value *ArraySize=nullptr, const Twine &Name="")
Definition: IRBuilder.h:1379
CoroBeginInst * CoroBegin
Definition: CoroInternal.h:67
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This represents the llvm.coro.alloc instruction.
Definition: CoroInstr.h:81
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:345
static void addMustTailToCoroResumes(Function &F)
Definition: CoroSplit.cpp:497
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Definition: Function.cpp:389
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve &#39;CreateLoad(Ty, Ptr, "...")&#39; correctly, instead of converting the string to &#39;bool...
Definition: IRBuilder.h:1392
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static void splitCoroutine(Function &F, CallGraph &CG, CallGraphSCC &SCC)
Definition: CoroSplit.cpp:779
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
IntegerType * getIndexType() const
Definition: CoroInternal.h:87
iterator end() const
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:2247
Pass * createCoroSplitPass()
Split up coroutines into multiple functions driving their state machines.
static void relocateInstructionBefore(CoroBeginInst *CoroBegin, Function &F)
Definition: CoroSplit.cpp:756
This class represents a function call, abstracting a target machine&#39;s calling convention.
virtual bool doInitialization(CallGraph &CG)
doInitialization - This method is called before the SCC&#39;s of the program has been processed...
FunctionPass * createVerifierPass(bool FatalErrors=true)
Definition: Verifier.cpp:5375
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
bool isTerminator() const
Definition: Instruction.h:128
F(f)
static void replaceFrameSize(coro::Shape &Shape)
Definition: CoroSplit.cpp:352
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
A node in the call graph for a module.
Definition: CallGraph.h:164
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:113
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:992
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
FunctionPass * createCFGSimplificationPass(unsigned Threshold=1, bool ForwardSwitchCond=false, bool ConvertSwitch=false, bool KeepLoops=true, bool SinkCommon=false, std::function< bool(const Function &)> Ftor=nullptr)
static bool simplifySuspendPoint(CoroSuspendInst *Suspend, CoroBeginInst *CoroBegin)
Definition: CoroSplit.cpp:610
void CloneFunctionInto(Function *NewFunc, const Function *OldFunc, ValueToValueMapTy &VMap, bool ModuleLevelChanges, SmallVectorImpl< ReturnInst *> &Returns, const char *NameSuffix="", ClonedCodeInfo *CodeInfo=nullptr, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Clone OldFunc into NewFunc, transforming the old arguments into references to VMap values...
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
static void handleNoSuspendCoroutine(CoroBeginInst *CoroBegin, Type *FrameTy)
Definition: CoroSplit.cpp:523
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
This represents the llvm.coro.suspend instruction.
Definition: CoroInstr.h:265
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:742
This file contains the simple types necessary to represent the attributes associated with functions a...
static void scanPHIsAndUpdateValueMap(Instruction *Prev, BasicBlock *NewBlock, DenseMap< Value *, Value *> &ResolvedValues)
Definition: CoroSplit.cpp:441
FunctionPass * createSCCPPass()
Definition: SCCP.cpp:1883
This class represents the llvm.coro.subfn.addr instruction.
Definition: CoroInstr.h:34
#define PREPARED_FOR_SPLIT
Definition: CoroInternal.h:39
StoreInst * CreateStore(Value *Val, Value *Ptr, bool isVolatile=false)
Definition: IRBuilder.h:1421
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
const Instruction * getFirstNonPHIOrDbgOrLifetime() const
Returns a pointer to the first instruction in this block that is not a PHINode, a debug intrinsic...
Definition: BasicBlock.cpp:203
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
ConstantInt * getIndex(uint64_t Value) const
Definition: CoroInternal.h:91
Class to represent function types.
Definition: DerivedTypes.h:102
void initializeCoroSplitPass(PassRegistry &)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1767
static void replaceFallthroughCoroEnd(IntrinsicInst *End, ValueToValueMapTy &VMap)
Definition: CoroSplit.cpp:172
This represents the llvm.coro.alloc instruction.
Definition: CoroInstr.h:69
SmallVector< CoroSizeInst *, 2 > CoroSizes
Definition: CoroInternal.h:69
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
void add(Pass *P) override
Add a pass to the queue of passes to run.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
static void simplifySuspendPoints(coro::Shape &Shape)
Definition: CoroSplit.cpp:672
SmallVector< CoroSuspendInst *, 4 > CoroSuspends
Definition: CoroInternal.h:70
iterator begin()
Definition: Function.h:661
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:126
const BasicBlock & getEntryBlock() const
Definition: Function.h:645
iterator begin() const
This represents the llvm.coro.size instruction.
Definition: CoroInstr.h:290
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:135
static void postSplitCleanup(Function &F)
Definition: CoroSplit.cpp:423
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:652
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1410
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:138
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
#define CORO_PRESPLIT_ATTR
Definition: CoroInternal.h:37
bool isFinal() const
Definition: CoroInstr.h:276
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1013
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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:370
Value * getMem() const
Definition: CoroInstr.h:220
static void prepareForSplit(Function &F, CallGraph &CG)
Definition: CoroSplit.cpp:831
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:160
This represents the llvm.coro.end instruction.
Definition: CoroInstr.h:302
static bool hasCallsBetween(Instruction *Save, Instruction *ResumeOrDestroy)
Definition: CoroSplit.cpp:585
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:296
op_range operands()
Definition: User.h:237
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1874
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
void initialize(ArrayRef< CallGraphNode *> NewNodes)
static bool hasCallsInBlocksBetween(BasicBlock *SaveBB, BasicBlock *ResDesBB)
Definition: CoroSplit.cpp:556
CaseIt removeCase(CaseIt I)
This method removes the specified case and its successor from the switch instruction.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:196
static void replaceUnwindCoroEnds(coro::Shape &Shape, ValueToValueMapTy &VMap)
Definition: CoroSplit.cpp:185
FunctionPassManager manages FunctionPasses and BasicBlockPassManagers.
static Function * createClone(Function &F, Twine Suffix, coro::Shape &Shape, BasicBlock *ResumeEntry, int8_t FnIndex)
Definition: CoroSplit.cpp:245
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
PointerType * getInt8PtrTy(unsigned AddrSpace=0)
Fetch the type representing a pointer to an 8-bit integer value.
Definition: IRBuilder.h:384
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:219
static SmallPtrSet< BasicBlock *, 4 > getCoroBeginPredBlocks(CoroBeginInst *CB)
Definition: CoroSplit.cpp:690
static bool hasCallsInBlockBetween(Instruction *From, Instruction *To)
Definition: CoroSplit.cpp:544
static Constant * getPointerCast(Constant *C, Type *Ty)
Create a BitCast, AddrSpaceCast, or a PtrToInt cast constant expression.
Definition: Constants.cpp:1596
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
StructType * FrameTy
Definition: CoroInternal.h:80
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
BlockVerifier::State From
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:377
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
bool EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete all basic blocks from F that are not reachable from its entry node.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void buildCoroutineFrame(Function &F, Shape &Shape)
Definition: CoroFrame.cpp:898
#define UNPREPARED_FOR_SPLIT
Definition: CoroInternal.h:38
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:631
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:587
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:214
Value * makeSubFnCall(Value *Arg, int Index, Instruction *InsertPt)
Definition: Coroutines.cpp:107
amdgpu Simplify well known AMD library false FunctionCallee Callee
bool isUnwind() const
Definition: CoroInstr.h:307
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
Definition: IRBuilder.h:336
static void updateCoroFrame(coro::Shape &Shape, Function *ResumeFn, Function *DestroyFn, Function *CleanupFn)
Definition: CoroSplit.cpp:400
static BasicBlock * createResumeEntryBlock(Function &F, coro::Shape &Shape)
Definition: CoroSplit.cpp:75
ConstantInt * getFalse()
Get the constant value for i1 false.
Definition: IRBuilder.h:291
SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a switch instruction with the specified value, default dest, and with a hint for the number of...
Definition: IRBuilder.h:876
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:461
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
INITIALIZE_PASS(CoroSplit, "coro-split", "Split coroutine into a set of functions driving its state machine", false, false) Pass *llvm
Definition: CoroSplit.cpp:949
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:194
SwitchInst * ResumeSwitch
Definition: CoroInternal.h:83
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
static void handleFinalSuspend(IRBuilder<> &Builder, Value *FramePtr, coro::Shape &Shape, SwitchInst *Switch, bool IsDestroy)
Definition: CoroSplit.cpp:219
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
Value * CreateConstInBoundsGEP2_32(Type *Ty, Value *Ptr, unsigned Idx0, unsigned Idx1, const Twine &Name="")
Definition: IRBuilder.h:1588
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:580
#define CORO_DEVIRT_TRIGGER_FN
Definition: CoroInternal.h:41
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
static ConstantTokenNone * get(LLVMContext &Context)
Return the ConstantTokenNone.
Definition: Constants.cpp:1139
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:407
CoroIdInst * getId() const
Definition: CoroInstr.h:218
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:152
static SmallPtrSet< Instruction *, 8 > getNotRelocatableInstructions(CoroBeginInst *CoroBegin, SmallPtrSetImpl< BasicBlock *> &RelocBlocks)
Definition: CoroSplit.cpp:708
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallVector< CoroEndInst *, 4 > CoroEnds
Definition: CoroInternal.h:68
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
void setInfo(Constant *C)
Definition: CoroInstr.h:163
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:147
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
AttrBuilder typeIncompatible(Type *Ty)
Which attributes cannot be applied to a type.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
static bool simplifyTerminatorLeadingToRet(Instruction *InitialInst)
Definition: CoroSplit.cpp:458
bool declaresIntrinsics(Module &M, std::initializer_list< StringRef >)
Definition: Coroutines.cpp:139
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:229
FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
Definition: EarlyCSE.cpp:1358
ConstantInt * getInt8(uint8_t C)
Get a constant 8-bit value.
Definition: IRBuilder.h:296
static void removeCoroEnds(coro::Shape &Shape)
Definition: CoroSplit.cpp:339
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
inst_range instructions(Function *F)
Definition: InstIterator.h:133
CoroAllocInst * getCoroAlloc()
Definition: CoroInstr.h:85
BasicBlock * AllocaSpillBlock
Definition: CoroInternal.h:82
#define LLVM_DEBUG(X)
Definition: Debug.h:122
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1936
CoroSaveInst * getCoroSave() const
Definition: CoroInstr.h:269
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
void updateCallGraph(Function &Caller, ArrayRef< Function *> Funcs, CallGraph &CG, CallGraphSCC &SCC)
Definition: Coroutines.cpp:193
iterator_range< arg_iterator > args()
Definition: Function.h:694
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66