LLVM  6.0.0svn
CoroFrame.cpp
Go to the documentation of this file.
1 //===- CoroFrame.cpp - Builds and manipulates coroutine frame -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This file contains classes used to discover if for a particular value
10 // there from sue to definition that crosses a suspend block.
11 //
12 // Using the information discovered we form a Coroutine Frame structure to
13 // contain those values. All uses of those values are replaced with appropriate
14 // GEP + load from the coroutine frame. At the point of the definition we spill
15 // the value into the coroutine frame.
16 //
17 // TODO: pack values tightly using liveness info.
18 //===----------------------------------------------------------------------===//
19 
20 #include "CoroInternal.h"
21 #include "llvm/ADT/BitVector.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/Support/Debug.h"
31 
32 using namespace llvm;
33 
34 // The "coro-suspend-crossing" flag is very noisy. There is another debug type,
35 // "coro-frame", which results in leaner debug spew.
36 #define DEBUG_TYPE "coro-suspend-crossing"
37 
38 enum { SmallVectorThreshold = 32 };
39 
40 // Provides two way mapping between the blocks and numbers.
41 namespace {
42 class BlockToIndexMapping {
44 
45 public:
46  size_t size() const { return V.size(); }
47 
48  BlockToIndexMapping(Function &F) {
49  for (BasicBlock &BB : F)
50  V.push_back(&BB);
51  std::sort(V.begin(), V.end());
52  }
53 
54  size_t blockToIndex(BasicBlock *BB) const {
55  auto *I = std::lower_bound(V.begin(), V.end(), BB);
56  assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
57  return I - V.begin();
58  }
59 
60  BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
61 };
62 } // end anonymous namespace
63 
64 // The SuspendCrossingInfo maintains data that allows to answer a question
65 // whether given two BasicBlocks A and B there is a path from A to B that
66 // passes through a suspend point.
67 //
68 // For every basic block 'i' it maintains a BlockData that consists of:
69 // Consumes: a bit vector which contains a set of indices of blocks that can
70 // reach block 'i'
71 // Kills: a bit vector which contains a set of indices of blocks that can
72 // reach block 'i', but one of the path will cross a suspend point
73 // Suspend: a boolean indicating whether block 'i' contains a suspend point.
74 // End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
75 //
76 namespace {
77 struct SuspendCrossingInfo {
78  BlockToIndexMapping Mapping;
79 
80  struct BlockData {
81  BitVector Consumes;
82  BitVector Kills;
83  bool Suspend = false;
84  bool End = false;
85  };
87 
88  iterator_range<succ_iterator> successors(BlockData const &BD) const {
89  BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
90  return llvm::successors(BB);
91  }
92 
93  BlockData &getBlockData(BasicBlock *BB) {
94  return Block[Mapping.blockToIndex(BB)];
95  }
96 
97  void dump() const;
98  void dump(StringRef Label, BitVector const &BV) const;
99 
100  SuspendCrossingInfo(Function &F, coro::Shape &Shape);
101 
102  bool hasPathCrossingSuspendPoint(BasicBlock *DefBB, BasicBlock *UseBB) const {
103  size_t const DefIndex = Mapping.blockToIndex(DefBB);
104  size_t const UseIndex = Mapping.blockToIndex(UseBB);
105 
106  assert(Block[UseIndex].Consumes[DefIndex] && "use must consume def");
107  bool const Result = Block[UseIndex].Kills[DefIndex];
108  DEBUG(dbgs() << UseBB->getName() << " => " << DefBB->getName()
109  << " answer is " << Result << "\n");
110  return Result;
111  }
112 
113  bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
114  auto *I = cast<Instruction>(U);
115 
116  // We rewrote PHINodes, so that only the ones with exactly one incoming
117  // value need to be analyzed.
118  if (auto *PN = dyn_cast<PHINode>(I))
119  if (PN->getNumIncomingValues() > 1)
120  return false;
121 
122  BasicBlock *UseBB = I->getParent();
123  return hasPathCrossingSuspendPoint(DefBB, UseBB);
124  }
125 
126  bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
127  return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
128  }
129 
130  bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
131  return isDefinitionAcrossSuspend(I.getParent(), U);
132  }
133 };
134 } // end anonymous namespace
135 
136 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
138  BitVector const &BV) const {
139  dbgs() << Label << ":";
140  for (size_t I = 0, N = BV.size(); I < N; ++I)
141  if (BV[I])
142  dbgs() << " " << Mapping.indexToBlock(I)->getName();
143  dbgs() << "\n";
144 }
145 
147  for (size_t I = 0, N = Block.size(); I < N; ++I) {
148  BasicBlock *const B = Mapping.indexToBlock(I);
149  dbgs() << B->getName() << ":\n";
150  dump(" Consumes", Block[I].Consumes);
151  dump(" Kills", Block[I].Kills);
152  }
153  dbgs() << "\n";
154 }
155 #endif
156 
157 SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
158  : Mapping(F) {
159  const size_t N = Mapping.size();
160  Block.resize(N);
161 
162  // Initialize every block so that it consumes itself
163  for (size_t I = 0; I < N; ++I) {
164  auto &B = Block[I];
165  B.Consumes.resize(N);
166  B.Kills.resize(N);
167  B.Consumes.set(I);
168  }
169 
170  // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
171  // the code beyond coro.end is reachable during initial invocation of the
172  // coroutine.
173  for (auto *CE : Shape.CoroEnds)
174  getBlockData(CE->getParent()).End = true;
175 
176  // Mark all suspend blocks and indicate that they kill everything they
177  // consume. Note, that crossing coro.save also requires a spill, as any code
178  // between coro.save and coro.suspend may resume the coroutine and all of the
179  // state needs to be saved by that time.
180  auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
181  BasicBlock *SuspendBlock = BarrierInst->getParent();
182  auto &B = getBlockData(SuspendBlock);
183  B.Suspend = true;
184  B.Kills |= B.Consumes;
185  };
186  for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
187  markSuspendBlock(CSI);
188  markSuspendBlock(CSI->getCoroSave());
189  }
190 
191  // Iterate propagating consumes and kills until they stop changing.
192  int Iteration = 0;
193  (void)Iteration;
194 
195  bool Changed;
196  do {
197  DEBUG(dbgs() << "iteration " << ++Iteration);
198  DEBUG(dbgs() << "==============\n");
199 
200  Changed = false;
201  for (size_t I = 0; I < N; ++I) {
202  auto &B = Block[I];
203  for (BasicBlock *SI : successors(B)) {
204 
205  auto SuccNo = Mapping.blockToIndex(SI);
206 
207  // Saved Consumes and Kills bitsets so that it is easy to see
208  // if anything changed after propagation.
209  auto &S = Block[SuccNo];
210  auto SavedConsumes = S.Consumes;
211  auto SavedKills = S.Kills;
212 
213  // Propagate Kills and Consumes from block B into its successor S.
214  S.Consumes |= B.Consumes;
215  S.Kills |= B.Kills;
216 
217  // If block B is a suspend block, it should propagate kills into the
218  // its successor for every block B consumes.
219  if (B.Suspend) {
220  S.Kills |= B.Consumes;
221  }
222  if (S.Suspend) {
223  // If block S is a suspend block, it should kill all of the blocks it
224  // consumes.
225  S.Kills |= S.Consumes;
226  } else if (S.End) {
227  // If block S is an end block, it should not propagate kills as the
228  // blocks following coro.end() are reached during initial invocation
229  // of the coroutine while all the data are still available on the
230  // stack or in the registers.
231  S.Kills.reset();
232  } else {
233  // This is reached when S block it not Suspend nor coro.end and it
234  // need to make sure that it is not in the kill set.
235  S.Kills.reset(SuccNo);
236  }
237 
238  // See if anything changed.
239  Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);
240 
241  if (S.Kills != SavedKills) {
242  DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()
243  << "\n");
244  DEBUG(dump("S.Kills", S.Kills));
245  DEBUG(dump("SavedKills", SavedKills));
246  }
247  if (S.Consumes != SavedConsumes) {
248  DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n");
249  DEBUG(dump("S.Consume", S.Consumes));
250  DEBUG(dump("SavedCons", SavedConsumes));
251  }
252  }
253  }
254  } while (Changed);
255  DEBUG(dump());
256 }
257 
258 #undef DEBUG_TYPE // "coro-suspend-crossing"
259 #define DEBUG_TYPE "coro-frame"
260 
261 // We build up the list of spills for every case where a use is separated
262 // from the definition by a suspend point.
263 
264 struct Spill : std::pair<Value *, Instruction *> {
265  using base = std::pair<Value *, Instruction *>;
266 
267  Spill(Value *Def, User *U) : base(Def, cast<Instruction>(U)) {}
268 
269  Value *def() const { return first; }
270  Instruction *user() const { return second; }
271  BasicBlock *userBlock() const { return second->getParent(); }
272 
273  std::pair<Value *, BasicBlock *> getKey() const {
274  return {def(), userBlock()};
275  }
276 
277  bool operator<(Spill const &rhs) const { return getKey() < rhs.getKey(); }
278 };
279 
280 // Note that there may be more than one record with the same value of Def in
281 // the SpillInfo vector.
283 
284 #ifndef NDEBUG
285 static void dump(StringRef Title, SpillInfo const &Spills) {
286  dbgs() << "------------- " << Title << "--------------\n";
287  Value *CurrentValue = nullptr;
288  for (auto const &E : Spills) {
289  if (CurrentValue != E.def()) {
290  CurrentValue = E.def();
291  CurrentValue->dump();
292  }
293  dbgs() << " user: ";
294  E.user()->dump();
295  }
296 }
297 #endif
298 
299 // Build a struct that will keep state for an active coroutine.
300 // struct f.frame {
301 // ResumeFnTy ResumeFnAddr;
302 // ResumeFnTy DestroyFnAddr;
303 // int ResumeIndex;
304 // ... promise (if present) ...
305 // ... spills ...
306 // };
308  SpillInfo &Spills) {
309  LLVMContext &C = F.getContext();
311  Name.append(".Frame");
312  StructType *FrameTy = StructType::create(C, Name);
313  auto *FramePtrTy = FrameTy->getPointerTo();
314  auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
315  /*IsVarArgs=*/false);
316  auto *FnPtrTy = FnTy->getPointerTo();
317 
318  // Figure out how wide should be an integer type storing the suspend index.
319  unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
320  Type *PromiseType = Shape.PromiseAlloca
321  ? Shape.PromiseAlloca->getType()->getElementType()
322  : Type::getInt1Ty(C);
323  SmallVector<Type *, 8> Types{FnPtrTy, FnPtrTy, PromiseType,
324  Type::getIntNTy(C, IndexBits)};
325  Value *CurrentDef = nullptr;
326 
327  // Create an entry for every spilled value.
328  for (auto const &S : Spills) {
329  if (CurrentDef == S.def())
330  continue;
331 
332  CurrentDef = S.def();
333  // PromiseAlloca was already added to Types array earlier.
334  if (CurrentDef == Shape.PromiseAlloca)
335  continue;
336 
337  Type *Ty = nullptr;
338  if (auto *AI = dyn_cast<AllocaInst>(CurrentDef))
339  Ty = AI->getAllocatedType();
340  else
341  Ty = CurrentDef->getType();
342 
343  Types.push_back(Ty);
344  }
345  FrameTy->setBody(Types);
346 
347  return FrameTy;
348 }
349 
350 // We need to make room to insert a spill after initial PHIs, but before
351 // catchswitch instruction. Placing it before violates the requirement that
352 // catchswitch, like all other EHPads must be the first nonPHI in a block.
353 //
354 // Split away catchswitch into a separate block and insert in its place:
355 //
356 // cleanuppad <InsertPt> cleanupret.
357 //
358 // cleanupret instruction will act as an insert point for the spill.
360  BasicBlock *CurrentBlock = CatchSwitch->getParent();
361  BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
362  CurrentBlock->getTerminator()->eraseFromParent();
363 
364  auto *CleanupPad =
365  CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
366  auto *CleanupRet =
367  CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
368  return CleanupRet;
369 }
370 
371 // Replace all alloca and SSA values that are accessed across suspend points
372 // with GetElementPointer from coroutine frame + loads and stores. Create an
373 // AllocaSpillBB that will become the new entry block for the resume parts of
374 // the coroutine:
375 //
376 // %hdl = coro.begin(...)
377 // whatever
378 //
379 // becomes:
380 //
381 // %hdl = coro.begin(...)
382 // %FramePtr = bitcast i8* hdl to %f.frame*
383 // br label %AllocaSpillBB
384 //
385 // AllocaSpillBB:
386 // ; geps corresponding to allocas that were moved to coroutine frame
387 // br label PostSpill
388 //
389 // PostSpill:
390 // whatever
391 //
392 //
393 static Instruction *insertSpills(SpillInfo &Spills, coro::Shape &Shape) {
394  auto *CB = Shape.CoroBegin;
395  IRBuilder<> Builder(CB->getNextNode());
396  PointerType *FramePtrTy = Shape.FrameTy->getPointerTo();
397  auto *FramePtr =
398  cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
399  Type *FrameTy = FramePtrTy->getElementType();
400 
401  Value *CurrentValue = nullptr;
402  BasicBlock *CurrentBlock = nullptr;
403  Value *CurrentReload = nullptr;
404  unsigned Index = coro::Shape::LastKnownField;
405 
406  // We need to keep track of any allocas that need "spilling"
407  // since they will live in the coroutine frame now, all access to them
408  // need to be changed, not just the access across suspend points
409  // we remember allocas and their indices to be handled once we processed
410  // all the spills.
412  // Promise alloca (if present) has a fixed field number (Shape::PromiseField)
413  if (Shape.PromiseAlloca)
415 
416  // Create a load instruction to reload the spilled value from the coroutine
417  // frame.
418  auto CreateReload = [&](Instruction *InsertBefore) {
419  Builder.SetInsertPoint(InsertBefore);
420  auto *G = Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, Index,
421  CurrentValue->getName() +
422  Twine(".reload.addr"));
423  return isa<AllocaInst>(CurrentValue)
424  ? G
425  : Builder.CreateLoad(G,
426  CurrentValue->getName() + Twine(".reload"));
427  };
428 
429  for (auto const &E : Spills) {
430  // If we have not seen the value, generate a spill.
431  if (CurrentValue != E.def()) {
432  CurrentValue = E.def();
433  CurrentBlock = nullptr;
434  CurrentReload = nullptr;
435 
436  ++Index;
437 
438  if (auto *AI = dyn_cast<AllocaInst>(CurrentValue)) {
439  // Spilled AllocaInst will be replaced with GEP from the coroutine frame
440  // there is no spill required.
441  Allocas.emplace_back(AI, Index);
442  if (!AI->isStaticAlloca())
443  report_fatal_error("Coroutines cannot handle non static allocas yet");
444  } else {
445  // Otherwise, create a store instruction storing the value into the
446  // coroutine frame.
447 
448  Instruction *InsertPt = nullptr;
449  if (isa<Argument>(CurrentValue)) {
450  // For arguments, we will place the store instruction right after
451  // the coroutine frame pointer instruction, i.e. bitcast of
452  // coro.begin from i8* to %f.frame*.
453  InsertPt = FramePtr->getNextNode();
454  } else if (auto *II = dyn_cast<InvokeInst>(CurrentValue)) {
455  // If we are spilling the result of the invoke instruction, split the
456  // normal edge and insert the spill in the new block.
457  auto NewBB = SplitEdge(II->getParent(), II->getNormalDest());
458  InsertPt = NewBB->getTerminator();
459  } else if (dyn_cast<PHINode>(CurrentValue)) {
460  // Skip the PHINodes and EH pads instructions.
461  BasicBlock *DefBlock = cast<Instruction>(E.def())->getParent();
462  if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
463  InsertPt = splitBeforeCatchSwitch(CSI);
464  else
465  InsertPt = &*DefBlock->getFirstInsertionPt();
466  } else {
467  // For all other values, the spill is placed immediately after
468  // the definition.
469  assert(!isa<TerminatorInst>(E.def()) && "unexpected terminator");
470  InsertPt = cast<Instruction>(E.def())->getNextNode();
471  }
472 
473  Builder.SetInsertPoint(InsertPt);
474  auto *G = Builder.CreateConstInBoundsGEP2_32(
475  FrameTy, FramePtr, 0, Index,
476  CurrentValue->getName() + Twine(".spill.addr"));
477  Builder.CreateStore(CurrentValue, G);
478  }
479  }
480 
481  // If we have not seen the use block, generate a reload in it.
482  if (CurrentBlock != E.userBlock()) {
483  CurrentBlock = E.userBlock();
484  CurrentReload = CreateReload(&*CurrentBlock->getFirstInsertionPt());
485  }
486 
487  // If we have a single edge PHINode, remove it and replace it with a reload
488  // from the coroutine frame. (We already took care of multi edge PHINodes
489  // by rewriting them in the rewritePHIs function).
490  if (auto *PN = dyn_cast<PHINode>(E.user())) {
491  assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
492  "values in the PHINode");
493  PN->replaceAllUsesWith(CurrentReload);
494  PN->eraseFromParent();
495  continue;
496  }
497 
498  // Replace all uses of CurrentValue in the current instruction with reload.
499  E.user()->replaceUsesOfWith(CurrentValue, CurrentReload);
500  }
501 
502  BasicBlock *FramePtrBB = FramePtr->getParent();
503  Shape.AllocaSpillBlock =
504  FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
506  "PostSpill");
507 
508  Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
509  // If we found any allocas, replace all of their remaining uses with Geps.
510  for (auto &P : Allocas) {
511  auto *G =
512  Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, P.second);
513  // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G)) here,
514  // as we are changing location of the instruction.
515  G->takeName(P.first);
516  P.first->replaceAllUsesWith(G);
517  P.first->eraseFromParent();
518  }
519  return FramePtr;
520 }
521 
522 // Sets the unwind edge of an instruction to a particular successor.
523 static void setUnwindEdgeTo(TerminatorInst *TI, BasicBlock *Succ) {
524  if (auto *II = dyn_cast<InvokeInst>(TI))
525  II->setUnwindDest(Succ);
526  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
527  CS->setUnwindDest(Succ);
528  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
529  CR->setUnwindDest(Succ);
530  else
531  llvm_unreachable("unexpected terminator instruction");
532 }
533 
534 // Replaces all uses of OldPred with the NewPred block in all PHINodes in a
535 // block.
536 static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
537  BasicBlock *NewPred,
538  PHINode *LandingPadReplacement) {
539  unsigned BBIdx = 0;
540  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
541  PHINode *PN = cast<PHINode>(I);
542 
543  // We manually update the LandingPadReplacement PHINode and it is the last
544  // PHI Node. So, if we find it, we are done.
545  if (LandingPadReplacement == PN)
546  break;
547 
548  // Reuse the previous value of BBIdx if it lines up. In cases where we
549  // have multiple phi nodes with *lots* of predecessors, this is a speed
550  // win because we don't have to scan the PHI looking for TIBB. This
551  // happens because the BB list of PHI nodes are usually in the same
552  // order.
553  if (PN->getIncomingBlock(BBIdx) != OldPred)
554  BBIdx = PN->getBasicBlockIndex(OldPred);
555 
556  assert(BBIdx != (unsigned)-1 && "Invalid PHI Index!");
557  PN->setIncomingBlock(BBIdx, NewPred);
558  }
559 }
560 
561 // Uses SplitEdge unless the successor block is an EHPad, in which case do EH
562 // specific handling.
564  LandingPadInst *OriginalPad,
565  PHINode *LandingPadReplacement) {
566  auto *PadInst = Succ->getFirstNonPHI();
567  if (!LandingPadReplacement && !PadInst->isEHPad())
568  return SplitEdge(BB, Succ);
569 
570  auto *NewBB = BasicBlock::Create(BB->getContext(), "", BB->getParent(), Succ);
571  setUnwindEdgeTo(BB->getTerminator(), NewBB);
572  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
573 
574  if (LandingPadReplacement) {
575  auto *NewLP = OriginalPad->clone();
576  auto *Terminator = BranchInst::Create(Succ, NewBB);
577  NewLP->insertBefore(Terminator);
578  LandingPadReplacement->addIncoming(NewLP, NewBB);
579  return NewBB;
580  }
581  Value *ParentPad = nullptr;
582  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
583  ParentPad = FuncletPad->getParentPad();
584  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
585  ParentPad = CatchSwitch->getParentPad();
586  else
587  llvm_unreachable("handling for other EHPads not implemented yet");
588 
589  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, "", NewBB);
590  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
591  return NewBB;
592 }
593 
594 static void rewritePHIs(BasicBlock &BB) {
595  // For every incoming edge we will create a block holding all
596  // incoming values in a single PHI nodes.
597  //
598  // loop:
599  // %n.val = phi i32[%n, %entry], [%inc, %loop]
600  //
601  // It will create:
602  //
603  // loop.from.entry:
604  // %n.loop.pre = phi i32 [%n, %entry]
605  // br %label loop
606  // loop.from.loop:
607  // %inc.loop.pre = phi i32 [%inc, %loop]
608  // br %label loop
609  //
610  // After this rewrite, further analysis will ignore any phi nodes with more
611  // than one incoming edge.
612 
613  // TODO: Simplify PHINodes in the basic block to remove duplicate
614  // predecessors.
615 
616  LandingPadInst *LandingPad = nullptr;
617  PHINode *ReplPHI = nullptr;
618  if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
619  // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
620  // We replace the original landing pad with a PHINode that will collect the
621  // results from all of them.
622  ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
623  ReplPHI->takeName(LandingPad);
624  LandingPad->replaceAllUsesWith(ReplPHI);
625  // We will erase the original landing pad at the end of this function after
626  // ehAwareSplitEdge cloned it in the transition blocks.
627  }
628 
630  for (BasicBlock *Pred : Preds) {
631  auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
632  IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
633  auto *PN = cast<PHINode>(&BB.front());
634  do {
635  int Index = PN->getBasicBlockIndex(IncomingBB);
636  Value *V = PN->getIncomingValue(Index);
637  PHINode *InputV = PHINode::Create(
638  V->getType(), 1, V->getName() + Twine(".") + BB.getName(),
639  &IncomingBB->front());
640  InputV->addIncoming(V, Pred);
641  PN->setIncomingValue(Index, InputV);
642  PN = dyn_cast<PHINode>(PN->getNextNode());
643  } while (PN != ReplPHI); // ReplPHI is either null or the PHI that replaced
644  // the landing pad.
645  }
646 
647  if (LandingPad) {
648  // Calls to ehAwareSplitEdge function cloned the original lading pad.
649  // No longer need it.
650  LandingPad->eraseFromParent();
651  }
652 }
653 
654 static void rewritePHIs(Function &F) {
656 
657  for (BasicBlock &BB : F)
658  if (auto *PN = dyn_cast<PHINode>(&BB.front()))
659  if (PN->getNumIncomingValues() > 1)
660  WorkList.push_back(&BB);
661 
662  for (BasicBlock *BB : WorkList)
663  rewritePHIs(*BB);
664 }
665 
666 // Check for instructions that we can recreate on resume as opposed to spill
667 // the result into a coroutine frame.
668 static bool materializable(Instruction &V) {
669  return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
670  isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
671 }
672 
673 // Check for structural coroutine intrinsics that should not be spilled into
674 // the coroutine frame.
676  return isa<CoroIdInst>(&I) || isa<CoroSaveInst>(&I) ||
677  isa<CoroSuspendInst>(&I);
678 }
679 
680 // For every use of the value that is across suspend point, recreate that value
681 // after a suspend point.
683  SpillInfo const &Spills) {
684  BasicBlock *CurrentBlock = nullptr;
685  Instruction *CurrentMaterialization = nullptr;
686  Instruction *CurrentDef = nullptr;
687 
688  for (auto const &E : Spills) {
689  // If it is a new definition, update CurrentXXX variables.
690  if (CurrentDef != E.def()) {
691  CurrentDef = cast<Instruction>(E.def());
692  CurrentBlock = nullptr;
693  CurrentMaterialization = nullptr;
694  }
695 
696  // If we have not seen this block, materialize the value.
697  if (CurrentBlock != E.userBlock()) {
698  CurrentBlock = E.userBlock();
699  CurrentMaterialization = cast<Instruction>(CurrentDef)->clone();
700  CurrentMaterialization->setName(CurrentDef->getName());
701  CurrentMaterialization->insertBefore(
702  &*CurrentBlock->getFirstInsertionPt());
703  }
704 
705  if (auto *PN = dyn_cast<PHINode>(E.user())) {
706  assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
707  "values in the PHINode");
708  PN->replaceAllUsesWith(CurrentMaterialization);
709  PN->eraseFromParent();
710  continue;
711  }
712 
713  // Replace all uses of CurrentDef in the current instruction with the
714  // CurrentMaterialization for the block.
715  E.user()->replaceUsesOfWith(CurrentDef, CurrentMaterialization);
716  }
717 }
718 
719 // Move early uses of spilled variable after CoroBegin.
720 // For example, if a parameter had address taken, we may end up with the code
721 // like:
722 // define @f(i32 %n) {
723 // %n.addr = alloca i32
724 // store %n, %n.addr
725 // ...
726 // call @coro.begin
727 // we need to move the store after coro.begin
728 static void moveSpillUsesAfterCoroBegin(Function &F, SpillInfo const &Spills,
729  CoroBeginInst *CoroBegin) {
730  DominatorTree DT(F);
731  SmallVector<Instruction *, 8> NeedsMoving;
732 
733  Value *CurrentValue = nullptr;
734 
735  for (auto const &E : Spills) {
736  if (CurrentValue == E.def())
737  continue;
738 
739  CurrentValue = E.def();
740 
741  for (User *U : CurrentValue->users()) {
742  Instruction *I = cast<Instruction>(U);
743  if (!DT.dominates(CoroBegin, I)) {
744  // TODO: Make this more robust. Currently if we run into a situation
745  // where simple instruction move won't work we panic and
746  // report_fatal_error.
747  for (User *UI : I->users()) {
748  if (!DT.dominates(CoroBegin, cast<Instruction>(UI)))
749  report_fatal_error("cannot move instruction since its users are not"
750  " dominated by CoroBegin");
751  }
752 
753  DEBUG(dbgs() << "will move: " << *I << "\n");
754  NeedsMoving.push_back(I);
755  }
756  }
757  }
758 
759  Instruction *InsertPt = CoroBegin->getNextNode();
760  for (Instruction *I : NeedsMoving)
761  I->moveBefore(InsertPt);
762 }
763 
764 // Splits the block at a particular instruction unless it is the first
765 // instruction in the block with a single predecessor.
767  auto *BB = I->getParent();
768  if (&BB->front() == I) {
769  if (BB->getSinglePredecessor()) {
770  BB->setName(Name);
771  return BB;
772  }
773  }
774  return BB->splitBasicBlock(I, Name);
775 }
776 
777 // Split above and below a particular instruction so that it
778 // will be all alone by itself in a block.
779 static void splitAround(Instruction *I, const Twine &Name) {
780  splitBlockIfNotFirst(I, Name);
781  splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
782 }
783 
784 void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
785  // Lower coro.dbg.declare to coro.dbg.value, since we are going to rewrite
786  // access to local variables.
787  LowerDbgDeclare(F);
788 
789  Shape.PromiseAlloca = Shape.CoroBegin->getId()->getPromise();
790  if (Shape.PromiseAlloca) {
791  Shape.CoroBegin->getId()->clearPromise();
792  }
793 
794  // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
795  // intrinsics are in their own blocks to simplify the logic of building up
796  // SuspendCrossing data.
797  for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
798  splitAround(CSI->getCoroSave(), "CoroSave");
799  splitAround(CSI, "CoroSuspend");
800  }
801 
802  // Put CoroEnds into their own blocks.
803  for (CoroEndInst *CE : Shape.CoroEnds)
804  splitAround(CE, "CoroEnd");
805 
806  // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
807  // never has its definition separated from the PHI by the suspend point.
808  rewritePHIs(F);
809 
810  // Build suspend crossing info.
811  SuspendCrossingInfo Checker(F, Shape);
812 
813  IRBuilder<> Builder(F.getContext());
814  SpillInfo Spills;
815 
816  for (int Repeat = 0; Repeat < 4; ++Repeat) {
817  // See if there are materializable instructions across suspend points.
818  for (Instruction &I : instructions(F))
819  if (materializable(I))
820  for (User *U : I.users())
821  if (Checker.isDefinitionAcrossSuspend(I, U))
822  Spills.emplace_back(&I, U);
823 
824  if (Spills.empty())
825  break;
826 
827  // Rewrite materializable instructions to be materialized at the use point.
828  DEBUG(dump("Materializations", Spills));
829  rewriteMaterializableInstructions(Builder, Spills);
830  Spills.clear();
831  }
832 
833  // Collect the spills for arguments and other not-materializable values.
834  for (Argument &A : F.args())
835  for (User *U : A.users())
836  if (Checker.isDefinitionAcrossSuspend(A, U))
837  Spills.emplace_back(&A, U);
838 
839  for (Instruction &I : instructions(F)) {
840  // Values returned from coroutine structure intrinsics should not be part
841  // of the Coroutine Frame.
842  if (isCoroutineStructureIntrinsic(I) || &I == Shape.CoroBegin)
843  continue;
844  // The Coroutine Promise always included into coroutine frame, no need to
845  // check for suspend crossing.
846  if (Shape.PromiseAlloca == &I)
847  continue;
848 
849  for (User *U : I.users())
850  if (Checker.isDefinitionAcrossSuspend(I, U)) {
851  // We cannot spill a token.
852  if (I.getType()->isTokenTy())
854  "token definition is separated from the use by a suspend point");
855  Spills.emplace_back(&I, U);
856  }
857  }
858  DEBUG(dump("Spills", Spills));
859  moveSpillUsesAfterCoroBegin(F, Spills, Shape.CoroBegin);
860  Shape.FrameTy = buildFrameType(F, Shape, Spills);
861  Shape.FramePtr = insertSpills(Spills, Shape);
862 }
uint64_t CallInst * C
static Instruction * splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch)
Definition: CoroFrame.cpp:359
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
Instruction * FramePtr
Definition: CoroInternal.h:83
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
CoroBeginInst * CoroBegin
Definition: CoroInternal.h:68
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
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:103
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
Value * def() const
Definition: CoroFrame.cpp:269
static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *LandingPadReplacement)
Definition: CoroFrame.cpp:536
static void rewritePHIs(BasicBlock &BB)
Definition: CoroFrame.cpp:594
unsigned second
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:285
bool operator<(Spill const &rhs) const
Definition: CoroFrame.cpp:277
F(f)
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:3629
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
PointerType * getType() const
Overload to return most specific pointer type.
Definition: Instructions.h:97
Class to represent struct types.
Definition: DerivedTypes.h:201
static bool materializable(Instruction &V)
Definition: CoroFrame.cpp:668
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 provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
std::pair< Value *, BasicBlock * > getKey() const
Definition: CoroFrame.cpp:273
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:284
AllocaInst * getPromise() const
Definition: CoroInstr.h:101
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
Value * getParentPad() const
SmallVector< CoroSuspendInst *, 4 > CoroSuspends
Definition: CoroInternal.h:71
void setBody(ArrayRef< Type *> Elements, bool isPacked=false)
Specify a body for an opaque identified type.
Definition: Type.cpp:356
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Spill(Value *Def, User *U)
Definition: CoroFrame.cpp:267
std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type cast(const Y &Val)
Definition: Casting.h:240
Class to represent pointers.
Definition: DerivedTypes.h:467
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
#define P(N)
The landingpad instruction holds all of the information necessary to generate correct exception handl...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:171
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
static void moveSpillUsesAfterCoroBegin(Function &F, SpillInfo const &Spills, CoroBeginInst *CoroBegin)
Definition: CoroFrame.cpp:728
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:75
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
const Instruction & front() const
Definition: BasicBlock.h:264
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
This represents the llvm.coro.end instruction.
Definition: CoroInstr.h:303
static const unsigned End
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:297
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1220
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned first
static bool isCoroutineStructureIntrinsic(Instruction &I)
Definition: CoroFrame.cpp:675
Iterator for intrusive lists based on ilist_node.
StructType * FrameTy
Definition: CoroInternal.h:82
void setIncomingBlock(unsigned i, BasicBlock *BB)
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value *> Args=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:180
void buildCoroutineFrame(Function &F, Shape &Shape)
Definition: CoroFrame.cpp:784
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...
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
Definition: MathExtras.h:550
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:215
A range adaptor for a pair of iterators.
iterator_range< user_iterator > users()
Definition: Value.h:395
auto lower_bound(R &&Range, ForwardIt I) -> decltype(std::begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:908
static BasicBlock * splitBlockIfNotFirst(Instruction *I, const Twine &Name)
Definition: CoroFrame.cpp:766
BasicBlock * userBlock() const
Definition: CoroFrame.cpp:271
void clearPromise()
Definition: CoroInstr.h:108
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static void rewriteMaterializableInstructions(IRBuilder<> &IRB, SpillInfo const &Spills)
Definition: CoroFrame.cpp:682
const Function * getParent() const
Definition: Argument.h:42
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:656
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
static Instruction * insertSpills(SpillInfo &Spills, coro::Shape &Shape)
Definition: CoroFrame.cpp:393
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
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:323
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:170
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:382
CoroIdInst * getId() const
Definition: CoroInstr.h:219
Instruction * user() const
Definition: CoroFrame.cpp:270
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallVector< CoroEndInst *, 4 > CoroEnds
Definition: CoroInternal.h:69
LLVM_NODISCARD char front() const
front - Get the first character in the string.
Definition: StringRef.h:142
AllocaInst * PromiseAlloca
Definition: CoroInternal.h:86
static BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad, PHINode *LandingPadReplacement)
Definition: CoroFrame.cpp:563
static StructType * buildFrameType(Function &F, coro::Shape &Shape, SpillInfo &Spills)
Definition: CoroFrame.cpp:307
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
static StructType * create(LLVMContext &Context, StringRef Name)
This creates an identified struct.
Definition: Type.cpp:424
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
static const Function * getParent(const Value *V)
static const unsigned FramePtr
#define DEBUG(X)
Definition: Debug.h:118
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the edge connecting specified block.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:522
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
inst_range instructions(Function *F)
Definition: InstIterator.h:134
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
BasicBlock * AllocaSpillBlock
Definition: CoroInternal.h:84
const TerminatorInst * 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:120
static void setUnwindEdgeTo(TerminatorInst *TI, BasicBlock *Succ)
Definition: CoroFrame.cpp:523
std::pair< Value *, Instruction * > base
Definition: CoroFrame.cpp:265
static void splitAround(Instruction *I, const Twine &Name)
Definition: CoroFrame.cpp:779
CoroSaveInst * getCoroSave() const
Definition: CoroInstr.h:270
Type * getElementType() const
Definition: DerivedTypes.h:486
iterator_range< arg_iterator > args()
Definition: Function.h:621
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:66