LLVM  14.0.0git
CoroFrame.cpp
Go to the documentation of this file.
1 //===- CoroFrame.cpp - Builds and manipulates coroutine frame -------------===//
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 file contains classes used to discover if for a particular value
9 // there from sue to definition that crosses a suspend block.
10 //
11 // Using the information discovered we form a Coroutine Frame structure to
12 // contain those values. All uses of those values are replaced with appropriate
13 // GEP + load from the coroutine frame. At the point of the definition we spill
14 // the value into the coroutine frame.
15 //===----------------------------------------------------------------------===//
16 
17 #include "CoroInternal.h"
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/SmallString.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/DIBuilder.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InstIterator.h"
29 #include "llvm/Support/Debug.h"
37 #include <algorithm>
38 
39 using namespace llvm;
40 
41 // The "coro-suspend-crossing" flag is very noisy. There is another debug type,
42 // "coro-frame", which results in leaner debug spew.
43 #define DEBUG_TYPE "coro-suspend-crossing"
44 
46  "reuse-storage-in-coroutine-frame", cl::Hidden,
47  cl::desc(
48  "Enable the optimization which would reuse the storage in the coroutine \
49  frame for allocas whose liferanges are not overlapped, for testing purposes"),
50  llvm::cl::init(false));
51 
52 enum { SmallVectorThreshold = 32 };
53 
54 // Provides two way mapping between the blocks and numbers.
55 namespace {
56 class BlockToIndexMapping {
58 
59 public:
60  size_t size() const { return V.size(); }
61 
62  BlockToIndexMapping(Function &F) {
63  for (BasicBlock &BB : F)
64  V.push_back(&BB);
65  llvm::sort(V);
66  }
67 
68  size_t blockToIndex(BasicBlock *BB) const {
69  auto *I = llvm::lower_bound(V, BB);
70  assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
71  return I - V.begin();
72  }
73 
74  BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
75 };
76 } // end anonymous namespace
77 
78 // The SuspendCrossingInfo maintains data that allows to answer a question
79 // whether given two BasicBlocks A and B there is a path from A to B that
80 // passes through a suspend point.
81 //
82 // For every basic block 'i' it maintains a BlockData that consists of:
83 // Consumes: a bit vector which contains a set of indices of blocks that can
84 // reach block 'i'
85 // Kills: a bit vector which contains a set of indices of blocks that can
86 // reach block 'i', but one of the path will cross a suspend point
87 // Suspend: a boolean indicating whether block 'i' contains a suspend point.
88 // End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
89 //
90 namespace {
91 struct SuspendCrossingInfo {
92  BlockToIndexMapping Mapping;
93 
94  struct BlockData {
95  BitVector Consumes;
96  BitVector Kills;
97  bool Suspend = false;
98  bool End = false;
99  };
101 
102  iterator_range<succ_iterator> successors(BlockData const &BD) const {
103  BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
104  return llvm::successors(BB);
105  }
106 
107  BlockData &getBlockData(BasicBlock *BB) {
108  return Block[Mapping.blockToIndex(BB)];
109  }
110 
111  void dump() const;
112  void dump(StringRef Label, BitVector const &BV) const;
113 
114  SuspendCrossingInfo(Function &F, coro::Shape &Shape);
115 
116  bool hasPathCrossingSuspendPoint(BasicBlock *DefBB, BasicBlock *UseBB) const {
117  size_t const DefIndex = Mapping.blockToIndex(DefBB);
118  size_t const UseIndex = Mapping.blockToIndex(UseBB);
119 
120  bool const Result = Block[UseIndex].Kills[DefIndex];
121  LLVM_DEBUG(dbgs() << UseBB->getName() << " => " << DefBB->getName()
122  << " answer is " << Result << "\n");
123  return Result;
124  }
125 
126  bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
127  auto *I = cast<Instruction>(U);
128 
129  // We rewrote PHINodes, so that only the ones with exactly one incoming
130  // value need to be analyzed.
131  if (auto *PN = dyn_cast<PHINode>(I))
132  if (PN->getNumIncomingValues() > 1)
133  return false;
134 
135  BasicBlock *UseBB = I->getParent();
136 
137  // As a special case, treat uses by an llvm.coro.suspend.retcon or an
138  // llvm.coro.suspend.async as if they were uses in the suspend's single
139  // predecessor: the uses conceptually occur before the suspend.
140  if (isa<CoroSuspendRetconInst>(I) || isa<CoroSuspendAsyncInst>(I)) {
141  UseBB = UseBB->getSinglePredecessor();
142  assert(UseBB && "should have split coro.suspend into its own block");
143  }
144 
145  return hasPathCrossingSuspendPoint(DefBB, UseBB);
146  }
147 
148  bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
149  return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
150  }
151 
152  bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
153  auto *DefBB = I.getParent();
154 
155  // As a special case, treat values produced by an llvm.coro.suspend.*
156  // as if they were defined in the single successor: the uses
157  // conceptually occur after the suspend.
158  if (isa<AnyCoroSuspendInst>(I)) {
159  DefBB = DefBB->getSingleSuccessor();
160  assert(DefBB && "should have split coro.suspend into its own block");
161  }
162 
163  return isDefinitionAcrossSuspend(DefBB, U);
164  }
165 
166  bool isDefinitionAcrossSuspend(Value &V, User *U) const {
167  if (auto *Arg = dyn_cast<Argument>(&V))
168  return isDefinitionAcrossSuspend(*Arg, U);
169  if (auto *Inst = dyn_cast<Instruction>(&V))
170  return isDefinitionAcrossSuspend(*Inst, U);
171 
173  "Coroutine could only collect Argument and Instruction now.");
174  }
175 };
176 } // end anonymous namespace
177 
178 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
180  BitVector const &BV) const {
181  dbgs() << Label << ":";
182  for (size_t I = 0, N = BV.size(); I < N; ++I)
183  if (BV[I])
184  dbgs() << " " << Mapping.indexToBlock(I)->getName();
185  dbgs() << "\n";
186 }
187 
189  for (size_t I = 0, N = Block.size(); I < N; ++I) {
190  BasicBlock *const B = Mapping.indexToBlock(I);
191  dbgs() << B->getName() << ":\n";
192  dump(" Consumes", Block[I].Consumes);
193  dump(" Kills", Block[I].Kills);
194  }
195  dbgs() << "\n";
196 }
197 #endif
198 
199 SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
200  : Mapping(F) {
201  const size_t N = Mapping.size();
202  Block.resize(N);
203 
204  // Initialize every block so that it consumes itself
205  for (size_t I = 0; I < N; ++I) {
206  auto &B = Block[I];
207  B.Consumes.resize(N);
208  B.Kills.resize(N);
209  B.Consumes.set(I);
210  }
211 
212  // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
213  // the code beyond coro.end is reachable during initial invocation of the
214  // coroutine.
215  for (auto *CE : Shape.CoroEnds)
216  getBlockData(CE->getParent()).End = true;
217 
218  // Mark all suspend blocks and indicate that they kill everything they
219  // consume. Note, that crossing coro.save also requires a spill, as any code
220  // between coro.save and coro.suspend may resume the coroutine and all of the
221  // state needs to be saved by that time.
222  auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
223  BasicBlock *SuspendBlock = BarrierInst->getParent();
224  auto &B = getBlockData(SuspendBlock);
225  B.Suspend = true;
226  B.Kills |= B.Consumes;
227  };
228  for (auto *CSI : Shape.CoroSuspends) {
229  markSuspendBlock(CSI);
230  if (auto *Save = CSI->getCoroSave())
231  markSuspendBlock(Save);
232  }
233 
234  // Iterate propagating consumes and kills until they stop changing.
235  int Iteration = 0;
236  (void)Iteration;
237 
238  bool Changed;
239  do {
240  LLVM_DEBUG(dbgs() << "iteration " << ++Iteration);
241  LLVM_DEBUG(dbgs() << "==============\n");
242 
243  Changed = false;
244  for (size_t I = 0; I < N; ++I) {
245  auto &B = Block[I];
246  for (BasicBlock *SI : successors(B)) {
247 
248  auto SuccNo = Mapping.blockToIndex(SI);
249 
250  // Saved Consumes and Kills bitsets so that it is easy to see
251  // if anything changed after propagation.
252  auto &S = Block[SuccNo];
253  auto SavedConsumes = S.Consumes;
254  auto SavedKills = S.Kills;
255 
256  // Propagate Kills and Consumes from block B into its successor S.
257  S.Consumes |= B.Consumes;
258  S.Kills |= B.Kills;
259 
260  // If block B is a suspend block, it should propagate kills into the
261  // its successor for every block B consumes.
262  if (B.Suspend) {
263  S.Kills |= B.Consumes;
264  }
265  if (S.Suspend) {
266  // If block S is a suspend block, it should kill all of the blocks it
267  // consumes.
268  S.Kills |= S.Consumes;
269  } else if (S.End) {
270  // If block S is an end block, it should not propagate kills as the
271  // blocks following coro.end() are reached during initial invocation
272  // of the coroutine while all the data are still available on the
273  // stack or in the registers.
274  S.Kills.reset();
275  } else {
276  // This is reached when S block it not Suspend nor coro.end and it
277  // need to make sure that it is not in the kill set.
278  S.Kills.reset(SuccNo);
279  }
280 
281  // See if anything changed.
282  Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);
283 
284  if (S.Kills != SavedKills) {
285  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()
286  << "\n");
287  LLVM_DEBUG(dump("S.Kills", S.Kills));
288  LLVM_DEBUG(dump("SavedKills", SavedKills));
289  }
290  if (S.Consumes != SavedConsumes) {
291  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n");
292  LLVM_DEBUG(dump("S.Consume", S.Consumes));
293  LLVM_DEBUG(dump("SavedCons", SavedConsumes));
294  }
295  }
296  }
297  } while (Changed);
298  LLVM_DEBUG(dump());
299 }
300 
301 #undef DEBUG_TYPE // "coro-suspend-crossing"
302 #define DEBUG_TYPE "coro-frame"
303 
304 namespace {
305 class FrameTypeBuilder;
306 // Mapping from the to-be-spilled value to all the users that need reload.
308 struct AllocaInfo {
309  AllocaInst *Alloca;
311  bool MayWriteBeforeCoroBegin;
312  AllocaInfo(AllocaInst *Alloca,
314  bool MayWriteBeforeCoroBegin)
315  : Alloca(Alloca), Aliases(std::move(Aliases)),
316  MayWriteBeforeCoroBegin(MayWriteBeforeCoroBegin) {}
317 };
318 struct FrameDataInfo {
319  // All the values (that are not allocas) that needs to be spilled to the
320  // frame.
321  SpillInfo Spills;
322  // Allocas contains all values defined as allocas that need to live in the
323  // frame.
325 
326  SmallVector<Value *, 8> getAllDefs() const {
328  for (const auto &P : Spills)
329  Defs.push_back(P.first);
330  for (const auto &A : Allocas)
331  Defs.push_back(A.Alloca);
332  return Defs;
333  }
334 
335  uint32_t getFieldIndex(Value *V) const {
336  auto Itr = FieldIndexMap.find(V);
337  assert(Itr != FieldIndexMap.end() &&
338  "Value does not have a frame field index");
339  return Itr->second;
340  }
341 
342  void setFieldIndex(Value *V, uint32_t Index) {
343  assert((LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) &&
344  "Cannot set the index for the same field twice.");
345  FieldIndexMap[V] = Index;
346  }
347 
348  uint64_t getAlign(Value *V) const {
349  auto Iter = FieldAlignMap.find(V);
350  assert(Iter != FieldAlignMap.end());
351  return Iter->second;
352  }
353 
354  void setAlign(Value *V, uint64_t Align) {
355  assert(FieldAlignMap.count(V) == 0);
356  FieldAlignMap.insert({V, Align});
357  }
358 
359  uint64_t getOffset(Value *V) const {
360  auto Iter = FieldOffsetMap.find(V);
361  assert(Iter != FieldOffsetMap.end());
362  return Iter->second;
363  }
364 
365  void setOffset(Value *V, uint64_t Offset) {
366  assert(FieldOffsetMap.count(V) == 0);
367  FieldOffsetMap.insert({V, Offset});
368  }
369 
370  // Remap the index of every field in the frame, using the final layout index.
371  void updateLayoutIndex(FrameTypeBuilder &B);
372 
373 private:
374  // LayoutIndexUpdateStarted is used to avoid updating the index of any field
375  // twice by mistake.
376  bool LayoutIndexUpdateStarted = false;
377  // Map from values to their slot indexes on the frame. They will be first set
378  // with their original insertion field index. After the frame is built, their
379  // indexes will be updated into the final layout index.
380  DenseMap<Value *, uint32_t> FieldIndexMap;
381  // Map from values to their alignment on the frame. They would be set after
382  // the frame is built.
383  DenseMap<Value *, uint64_t> FieldAlignMap;
384  // Map from values to their offset on the frame. They would be set after
385  // the frame is built.
386  DenseMap<Value *, uint64_t> FieldOffsetMap;
387 };
388 } // namespace
389 
390 #ifndef NDEBUG
391 static void dumpSpills(StringRef Title, const SpillInfo &Spills) {
392  dbgs() << "------------- " << Title << "--------------\n";
393  for (const auto &E : Spills) {
394  E.first->dump();
395  dbgs() << " user: ";
396  for (auto *I : E.second)
397  I->dump();
398  }
399 }
400 
401 static void dumpAllocas(const SmallVectorImpl<AllocaInfo> &Allocas) {
402  dbgs() << "------------- Allocas --------------\n";
403  for (const auto &A : Allocas) {
404  A.Alloca->dump();
405  }
406 }
407 #endif
408 
409 namespace {
410 using FieldIDType = size_t;
411 // We cannot rely solely on natural alignment of a type when building a
412 // coroutine frame and if the alignment specified on the Alloca instruction
413 // differs from the natural alignment of the alloca type we will need to insert
414 // padding.
415 class FrameTypeBuilder {
416 private:
417  struct Field {
418  uint64_t Size;
420  Type *Ty;
421  FieldIDType LayoutFieldIndex;
422  Align Alignment;
423  Align TyAlignment;
424  };
425 
426  const DataLayout &DL;
428  uint64_t StructSize = 0;
429  Align StructAlign;
430  bool IsFinished = false;
431 
432  Optional<Align> MaxFrameAlignment;
433 
434  SmallVector<Field, 8> Fields;
435  DenseMap<Value*, unsigned> FieldIndexByKey;
436 
437 public:
438  FrameTypeBuilder(LLVMContext &Context, const DataLayout &DL,
439  Optional<Align> MaxFrameAlignment)
440  : DL(DL), Context(Context), MaxFrameAlignment(MaxFrameAlignment) {}
441 
442  /// Add a field to this structure for the storage of an `alloca`
443  /// instruction.
444  LLVM_NODISCARD FieldIDType addFieldForAlloca(AllocaInst *AI,
445  bool IsHeader = false) {
446  Type *Ty = AI->getAllocatedType();
447 
448  // Make an array type if this is a static array allocation.
449  if (AI->isArrayAllocation()) {
450  if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize()))
451  Ty = ArrayType::get(Ty, CI->getValue().getZExtValue());
452  else
453  report_fatal_error("Coroutines cannot handle non static allocas yet");
454  }
455 
456  return addField(Ty, AI->getAlign(), IsHeader);
457  }
458 
459  /// We want to put the allocas whose lifetime-ranges are not overlapped
460  /// into one slot of coroutine frame.
461  /// Consider the example at:https://bugs.llvm.org/show_bug.cgi?id=45566
462  ///
463  /// cppcoro::task<void> alternative_paths(bool cond) {
464  /// if (cond) {
465  /// big_structure a;
466  /// process(a);
467  /// co_await something();
468  /// } else {
469  /// big_structure b;
470  /// process2(b);
471  /// co_await something();
472  /// }
473  /// }
474  ///
475  /// We want to put variable a and variable b in the same slot to
476  /// reduce the size of coroutine frame.
477  ///
478  /// This function use StackLifetime algorithm to partition the AllocaInsts in
479  /// Spills to non-overlapped sets in order to put Alloca in the same
480  /// non-overlapped set into the same slot in the Coroutine Frame. Then add
481  /// field for the allocas in the same non-overlapped set by using the largest
482  /// type as the field type.
483  ///
484  /// Side Effects: Because We sort the allocas, the order of allocas in the
485  /// frame may be different with the order in the source code.
486  void addFieldForAllocas(const Function &F, FrameDataInfo &FrameData,
487  coro::Shape &Shape);
488 
489  /// Add a field to this structure.
490  LLVM_NODISCARD FieldIDType addField(Type *Ty, MaybeAlign FieldAlignment,
491  bool IsHeader = false,
492  bool IsSpillOfValue = false) {
493  assert(!IsFinished && "adding fields to a finished builder");
494  assert(Ty && "must provide a type for a field");
495 
496  // The field size is always the alloc size of the type.
497  uint64_t FieldSize = DL.getTypeAllocSize(Ty);
498 
499  // For an alloca with size=0, we don't need to add a field and they
500  // can just point to any index in the frame. Use index 0.
501  if (FieldSize == 0) {
502  return 0;
503  }
504 
505  // The field alignment might not be the type alignment, but we need
506  // to remember the type alignment anyway to build the type.
507  // If we are spilling values we don't need to worry about ABI alignment
508  // concerns.
509  auto ABIAlign = DL.getABITypeAlign(Ty);
510  Align TyAlignment =
511  (IsSpillOfValue && MaxFrameAlignment)
512  ? (*MaxFrameAlignment < ABIAlign ? *MaxFrameAlignment : ABIAlign)
513  : ABIAlign;
514  if (!FieldAlignment) {
515  FieldAlignment = TyAlignment;
516  }
517 
518  // Lay out header fields immediately.
520  if (IsHeader) {
521  Offset = alignTo(StructSize, FieldAlignment);
522  StructSize = Offset + FieldSize;
523 
524  // Everything else has a flexible offset.
525  } else {
526  Offset = OptimizedStructLayoutField::FlexibleOffset;
527  }
528 
529  Fields.push_back({FieldSize, Offset, Ty, 0, *FieldAlignment, TyAlignment});
530  return Fields.size() - 1;
531  }
532 
533  /// Finish the layout and set the body on the given type.
534  void finish(StructType *Ty);
535 
536  uint64_t getStructSize() const {
537  assert(IsFinished && "not yet finished!");
538  return StructSize;
539  }
540 
541  Align getStructAlign() const {
542  assert(IsFinished && "not yet finished!");
543  return StructAlign;
544  }
545 
546  FieldIDType getLayoutFieldIndex(FieldIDType Id) const {
547  assert(IsFinished && "not yet finished!");
548  return Fields[Id].LayoutFieldIndex;
549  }
550 
551  Field getLayoutField(FieldIDType Id) const {
552  assert(IsFinished && "not yet finished!");
553  return Fields[Id];
554  }
555 };
556 } // namespace
557 
558 void FrameDataInfo::updateLayoutIndex(FrameTypeBuilder &B) {
559  auto Updater = [&](Value *I) {
560  auto Field = B.getLayoutField(getFieldIndex(I));
561  setFieldIndex(I, Field.LayoutFieldIndex);
562  setAlign(I, Field.Alignment.value());
563  setOffset(I, Field.Offset);
564  };
565  LayoutIndexUpdateStarted = true;
566  for (auto &S : Spills)
567  Updater(S.first);
568  for (const auto &A : Allocas)
569  Updater(A.Alloca);
570  LayoutIndexUpdateStarted = false;
571 }
572 
573 void FrameTypeBuilder::addFieldForAllocas(const Function &F,
574  FrameDataInfo &FrameData,
575  coro::Shape &Shape) {
576  using AllocaSetType = SmallVector<AllocaInst *, 4>;
577  SmallVector<AllocaSetType, 4> NonOverlapedAllocas;
578 
579  // We need to add field for allocas at the end of this function. However, this
580  // function has multiple exits, so we use this helper to avoid redundant code.
581  struct RTTIHelper {
582  std::function<void()> func;
583  RTTIHelper(std::function<void()> &&func) : func(func) {}
584  ~RTTIHelper() { func(); }
585  } Helper([&]() {
586  for (auto AllocaList : NonOverlapedAllocas) {
587  auto *LargestAI = *AllocaList.begin();
588  FieldIDType Id = addFieldForAlloca(LargestAI);
589  for (auto *Alloca : AllocaList)
590  FrameData.setFieldIndex(Alloca, Id);
591  }
592  });
593 
594  if (!Shape.ReuseFrameSlot && !EnableReuseStorageInFrame) {
595  for (const auto &A : FrameData.Allocas) {
596  AllocaInst *Alloca = A.Alloca;
597  NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
598  }
599  return;
600  }
601 
602  // Because there are pathes from the lifetime.start to coro.end
603  // for each alloca, the liferanges for every alloca is overlaped
604  // in the blocks who contain coro.end and the successor blocks.
605  // So we choose to skip there blocks when we calculates the liferange
606  // for each alloca. It should be reasonable since there shouldn't be uses
607  // in these blocks and the coroutine frame shouldn't be used outside the
608  // coroutine body.
609  //
610  // Note that the user of coro.suspend may not be SwitchInst. However, this
611  // case seems too complex to handle. And it is harmless to skip these
612  // patterns since it just prevend putting the allocas to live in the same
613  // slot.
614  DenseMap<SwitchInst *, BasicBlock *> DefaultSuspendDest;
615  for (auto CoroSuspendInst : Shape.CoroSuspends) {
616  for (auto U : CoroSuspendInst->users()) {
617  if (auto *ConstSWI = dyn_cast<SwitchInst>(U)) {
618  auto *SWI = const_cast<SwitchInst *>(ConstSWI);
619  DefaultSuspendDest[SWI] = SWI->getDefaultDest();
620  SWI->setDefaultDest(SWI->getSuccessor(1));
621  }
622  }
623  }
624 
625  auto ExtractAllocas = [&]() {
626  AllocaSetType Allocas;
627  Allocas.reserve(FrameData.Allocas.size());
628  for (const auto &A : FrameData.Allocas)
629  Allocas.push_back(A.Alloca);
630  return Allocas;
631  };
632  StackLifetime StackLifetimeAnalyzer(F, ExtractAllocas(),
633  StackLifetime::LivenessType::May);
634  StackLifetimeAnalyzer.run();
635  auto IsAllocaInferenre = [&](const AllocaInst *AI1, const AllocaInst *AI2) {
636  return StackLifetimeAnalyzer.getLiveRange(AI1).overlaps(
637  StackLifetimeAnalyzer.getLiveRange(AI2));
638  };
639  auto GetAllocaSize = [&](const AllocaInfo &A) {
640  Optional<TypeSize> RetSize = A.Alloca->getAllocationSizeInBits(DL);
641  assert(RetSize && "Variable Length Arrays (VLA) are not supported.\n");
642  assert(!RetSize->isScalable() && "Scalable vectors are not yet supported");
643  return RetSize->getFixedSize();
644  };
645  // Put larger allocas in the front. So the larger allocas have higher
646  // priority to merge, which can save more space potentially. Also each
647  // AllocaSet would be ordered. So we can get the largest Alloca in one
648  // AllocaSet easily.
649  sort(FrameData.Allocas, [&](const auto &Iter1, const auto &Iter2) {
650  return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);
651  });
652  for (const auto &A : FrameData.Allocas) {
653  AllocaInst *Alloca = A.Alloca;
654  bool Merged = false;
655  // Try to find if the Alloca is not inferenced with any existing
656  // NonOverlappedAllocaSet. If it is true, insert the alloca to that
657  // NonOverlappedAllocaSet.
658  for (auto &AllocaSet : NonOverlapedAllocas) {
659  assert(!AllocaSet.empty() && "Processing Alloca Set is not empty.\n");
660  bool NoInference = none_of(AllocaSet, [&](auto Iter) {
661  return IsAllocaInferenre(Alloca, Iter);
662  });
663  // If the alignment of A is multiple of the alignment of B, the address
664  // of A should satisfy the requirement for aligning for B.
665  //
666  // There may be other more fine-grained strategies to handle the alignment
667  // infomation during the merging process. But it seems hard to handle
668  // these strategies and benefit little.
669  bool Alignable = [&]() -> bool {
670  auto *LargestAlloca = *AllocaSet.begin();
671  return LargestAlloca->getAlign().value() % Alloca->getAlign().value() ==
672  0;
673  }();
674  bool CouldMerge = NoInference && Alignable;
675  if (!CouldMerge)
676  continue;
677  AllocaSet.push_back(Alloca);
678  Merged = true;
679  break;
680  }
681  if (!Merged) {
682  NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
683  }
684  }
685  // Recover the default target destination for each Switch statement
686  // reserved.
687  for (auto SwitchAndDefaultDest : DefaultSuspendDest) {
688  SwitchInst *SWI = SwitchAndDefaultDest.first;
689  BasicBlock *DestBB = SwitchAndDefaultDest.second;
690  SWI->setDefaultDest(DestBB);
691  }
692  // This Debug Info could tell us which allocas are merged into one slot.
693  LLVM_DEBUG(for (auto &AllocaSet
694  : NonOverlapedAllocas) {
695  if (AllocaSet.size() > 1) {
696  dbgs() << "In Function:" << F.getName() << "\n";
697  dbgs() << "Find Union Set "
698  << "\n";
699  dbgs() << "\tAllocas are \n";
700  for (auto Alloca : AllocaSet)
701  dbgs() << "\t\t" << *Alloca << "\n";
702  }
703  });
704 }
705 
706 void FrameTypeBuilder::finish(StructType *Ty) {
707  assert(!IsFinished && "already finished!");
708 
709  // Prepare the optimal-layout field array.
710  // The Id in the layout field is a pointer to our Field for it.
712  LayoutFields.reserve(Fields.size());
713  for (auto &Field : Fields) {
714  LayoutFields.emplace_back(&Field, Field.Size, Field.Alignment,
715  Field.Offset);
716  }
717 
718  // Perform layout.
719  auto SizeAndAlign = performOptimizedStructLayout(LayoutFields);
720  StructSize = SizeAndAlign.first;
721  StructAlign = SizeAndAlign.second;
722 
723  auto getField = [](const OptimizedStructLayoutField &LayoutField) -> Field & {
724  return *static_cast<Field *>(const_cast<void*>(LayoutField.Id));
725  };
726 
727  // We need to produce a packed struct type if there's a field whose
728  // assigned offset isn't a multiple of its natural type alignment.
729  bool Packed = [&] {
730  for (auto &LayoutField : LayoutFields) {
731  auto &F = getField(LayoutField);
732  if (!isAligned(F.TyAlignment, LayoutField.Offset))
733  return true;
734  }
735  return false;
736  }();
737 
738  // Build the struct body.
739  SmallVector<Type*, 16> FieldTypes;
740  FieldTypes.reserve(LayoutFields.size() * 3 / 2);
741  uint64_t LastOffset = 0;
742  for (auto &LayoutField : LayoutFields) {
743  auto &F = getField(LayoutField);
744 
745  auto Offset = LayoutField.Offset;
746 
747  // Add a padding field if there's a padding gap and we're either
748  // building a packed struct or the padding gap is more than we'd
749  // get from aligning to the field type's natural alignment.
750  assert(Offset >= LastOffset);
751  if (Offset != LastOffset) {
752  if (Packed || alignTo(LastOffset, F.TyAlignment) != Offset)
753  FieldTypes.push_back(ArrayType::get(Type::getInt8Ty(Context),
754  Offset - LastOffset));
755  }
756 
757  F.Offset = Offset;
758  F.LayoutFieldIndex = FieldTypes.size();
759 
760  FieldTypes.push_back(F.Ty);
761  LastOffset = Offset + F.Size;
762  }
763 
764  Ty->setBody(FieldTypes, Packed);
765 
766 #ifndef NDEBUG
767  // Check that the IR layout matches the offsets we expect.
768  auto Layout = DL.getStructLayout(Ty);
769  for (auto &F : Fields) {
770  assert(Ty->getElementType(F.LayoutFieldIndex) == F.Ty);
771  assert(Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset);
772  }
773 #endif
774 
775  IsFinished = true;
776 }
777 
778 static void cacheDIVar(FrameDataInfo &FrameData,
780  for (auto *V : FrameData.getAllDefs()) {
781  if (DIVarCache.find(V) != DIVarCache.end())
782  continue;
783 
784  auto DDIs = FindDbgDeclareUses(V);
785  auto *I = llvm::find_if(DDIs, [](DbgDeclareInst *DDI) {
786  return DDI->getExpression()->getNumElements() == 0;
787  });
788  if (I != DDIs.end())
789  DIVarCache.insert({V, (*I)->getVariable()});
790  }
791 }
792 
793 /// Create name for Type. It uses MDString to store new created string to
794 /// avoid memory leak.
796  if (Ty->isIntegerTy()) {
797  // The longest name in common may be '__int_128', which has 9 bits.
798  SmallString<16> Buffer;
799  raw_svector_ostream OS(Buffer);
800  OS << "__int_" << cast<IntegerType>(Ty)->getBitWidth();
801  auto *MDName = MDString::get(Ty->getContext(), OS.str());
802  return MDName->getString();
803  }
804 
805  if (Ty->isFloatingPointTy()) {
806  if (Ty->isFloatTy())
807  return "__float_";
808  if (Ty->isDoubleTy())
809  return "__double_";
810  return "__floating_type_";
811  }
812 
813  if (Ty->isPointerTy()) {
814  auto *PtrTy = cast<PointerType>(Ty);
815  Type *PointeeTy = PtrTy->getElementType();
816  auto Name = solveTypeName(PointeeTy);
817  if (Name == "UnknownType")
818  return "PointerType";
819  SmallString<16> Buffer;
820  Twine(Name + "_Ptr").toStringRef(Buffer);
821  auto *MDName = MDString::get(Ty->getContext(), Buffer.str());
822  return MDName->getString();
823  }
824 
825  if (Ty->isStructTy()) {
826  if (!cast<StructType>(Ty)->hasName())
827  return "__LiteralStructType_";
828 
829  auto Name = Ty->getStructName();
830 
831  SmallString<16> Buffer(Name);
832  for_each(Buffer, [](auto &Iter) {
833  if (Iter == '.' || Iter == ':')
834  Iter = '_';
835  });
836  auto *MDName = MDString::get(Ty->getContext(), Buffer.str());
837  return MDName->getString();
838  }
839 
840  return "UnknownType";
841 }
842 
844  const DataLayout &Layout, DIScope *Scope,
845  unsigned LineNum,
846  DenseMap<Type *, DIType *> &DITypeCache) {
847  if (DIType *DT = DITypeCache.lookup(Ty))
848  return DT;
849 
851 
852  DIType *RetType = nullptr;
853 
854  if (Ty->isIntegerTy()) {
855  auto BitWidth = cast<IntegerType>(Ty)->getBitWidth();
856  RetType = Builder.createBasicType(Name, BitWidth, dwarf::DW_ATE_signed,
857  llvm::DINode::FlagArtificial);
858  } else if (Ty->isFloatingPointTy()) {
859  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
860  dwarf::DW_ATE_float,
861  llvm::DINode::FlagArtificial);
862  } else if (Ty->isPointerTy()) {
863  // Construct BasicType instead of PointerType to avoid infinite
864  // search problem.
865  // For example, we would be in trouble if we traverse recursively:
866  //
867  // struct Node {
868  // Node* ptr;
869  // };
870  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
871  dwarf::DW_ATE_address,
872  llvm::DINode::FlagArtificial);
873  } else if (Ty->isStructTy()) {
874  auto *DIStruct = Builder.createStructType(
875  Scope, Name, Scope->getFile(), LineNum, Layout.getTypeSizeInBits(Ty),
876  Layout.getPrefTypeAlignment(Ty), llvm::DINode::FlagArtificial, nullptr,
877  llvm::DINodeArray());
878 
879  auto *StructTy = cast<StructType>(Ty);
881  for (unsigned I = 0; I < StructTy->getNumElements(); I++) {
882  DIType *DITy = solveDIType(Builder, StructTy->getElementType(I), Layout,
883  Scope, LineNum, DITypeCache);
884  assert(DITy);
885  Elements.push_back(Builder.createMemberType(
886  Scope, DITy->getName(), Scope->getFile(), LineNum,
887  DITy->getSizeInBits(), DITy->getAlignInBits(),
888  Layout.getStructLayout(StructTy)->getElementOffsetInBits(I),
889  llvm::DINode::FlagArtificial, DITy));
890  }
891 
892  Builder.replaceArrays(DIStruct, Builder.getOrCreateArray(Elements));
893 
894  RetType = DIStruct;
895  } else {
896  LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n";);
897  SmallString<32> Buffer;
898  raw_svector_ostream OS(Buffer);
899  OS << Name.str() << "_" << Layout.getTypeSizeInBits(Ty);
900  RetType = Builder.createBasicType(OS.str(), Layout.getTypeSizeInBits(Ty),
901  dwarf::DW_ATE_address,
902  llvm::DINode::FlagArtificial);
903  }
904 
905  DITypeCache.insert({Ty, RetType});
906  return RetType;
907 }
908 
909 /// Build artificial debug info for C++ coroutine frames to allow users to
910 /// inspect the contents of the frame directly
911 ///
912 /// Create Debug information for coroutine frame with debug name "__coro_frame".
913 /// The debug information for the fields of coroutine frame is constructed from
914 /// the following way:
915 /// 1. For all the value in the Frame, we search the use of dbg.declare to find
916 /// the corresponding debug variables for the value. If we can find the
917 /// debug variable, we can get full and accurate debug information.
918 /// 2. If we can't get debug information in step 1 and 2, we could only try to
919 /// build the DIType by Type. We did this in solveDIType. We only handle
920 /// integer, float, double, integer type and struct type for now.
922  FrameDataInfo &FrameData) {
923  DISubprogram *DIS = F.getSubprogram();
924  // If there is no DISubprogram for F, it implies the Function are not compiled
925  // with debug info. So we also don't need to generate debug info for the frame
926  // neither.
927  if (!DIS || !DIS->getUnit() ||
929  (dwarf::SourceLanguage)DIS->getUnit()->getSourceLanguage()))
930  return;
931 
932  assert(Shape.ABI == coro::ABI::Switch &&
933  "We could only build debug infomation for C++ coroutine now.\n");
934 
935  DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);
936 
937  AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
938  assert(PromiseAlloca &&
939  "Coroutine with switch ABI should own Promise alloca");
940 
942  if (DIs.empty())
943  return;
944 
945  DbgDeclareInst *PromiseDDI = DIs.front();
946  DILocalVariable *PromiseDIVariable = PromiseDDI->getVariable();
947  DILocalScope *PromiseDIScope = PromiseDIVariable->getScope();
948  DIFile *DFile = PromiseDIScope->getFile();
949  DILocation *DILoc = PromiseDDI->getDebugLoc().get();
950  unsigned LineNum = PromiseDIVariable->getLine();
951 
952  DICompositeType *FrameDITy = DBuilder.createStructType(
953  DIS, "__coro_frame_ty", DFile, LineNum, Shape.FrameSize * 8,
954  Shape.FrameAlign.value() * 8, llvm::DINode::FlagArtificial, nullptr,
955  llvm::DINodeArray());
956  StructType *FrameTy = Shape.FrameTy;
958  DataLayout Layout = F.getParent()->getDataLayout();
959 
961  cacheDIVar(FrameData, DIVarCache);
962 
963  unsigned ResumeIndex = coro::Shape::SwitchFieldIndex::Resume;
964  unsigned DestroyIndex = coro::Shape::SwitchFieldIndex::Destroy;
965  unsigned IndexIndex = Shape.SwitchLowering.IndexField;
966 
968  NameCache.insert({ResumeIndex, "__resume_fn"});
969  NameCache.insert({DestroyIndex, "__destroy_fn"});
970  NameCache.insert({IndexIndex, "__coro_index"});
971 
972  Type *ResumeFnTy = FrameTy->getElementType(ResumeIndex),
973  *DestroyFnTy = FrameTy->getElementType(DestroyIndex),
974  *IndexTy = FrameTy->getElementType(IndexIndex);
975 
977  TyCache.insert({ResumeIndex,
978  DBuilder.createBasicType("__resume_fn",
979  Layout.getTypeSizeInBits(ResumeFnTy),
980  dwarf::DW_ATE_address)});
981  TyCache.insert(
982  {DestroyIndex, DBuilder.createBasicType(
983  "__destroy_fn", Layout.getTypeSizeInBits(DestroyFnTy),
984  dwarf::DW_ATE_address)});
985 
986  /// FIXME: If we fill the field `SizeInBits` with the actual size of
987  /// __coro_index in bits, then __coro_index wouldn't show in the debugger.
988  TyCache.insert({IndexIndex, DBuilder.createBasicType(
989  "__coro_index",
990  (Layout.getTypeSizeInBits(IndexTy) < 8)
991  ? 8
992  : Layout.getTypeSizeInBits(IndexTy),
993  dwarf::DW_ATE_unsigned_char)});
994 
995  for (auto *V : FrameData.getAllDefs()) {
996  if (DIVarCache.find(V) == DIVarCache.end())
997  continue;
998 
999  auto Index = FrameData.getFieldIndex(V);
1000 
1001  NameCache.insert({Index, DIVarCache[V]->getName()});
1002  TyCache.insert({Index, DIVarCache[V]->getType()});
1003  }
1004 
1005  // Cache from index to (Align, Offset Pair)
1007  // The Align and Offset of Resume function and Destroy function are fixed.
1008  OffsetCache.insert({ResumeIndex, {8, 0}});
1009  OffsetCache.insert({DestroyIndex, {8, 8}});
1010  OffsetCache.insert(
1011  {IndexIndex,
1013 
1014  for (auto *V : FrameData.getAllDefs()) {
1015  auto Index = FrameData.getFieldIndex(V);
1016 
1017  OffsetCache.insert(
1018  {Index, {FrameData.getAlign(V), FrameData.getOffset(V)}});
1019  }
1020 
1021  DenseMap<Type *, DIType *> DITypeCache;
1022  // This counter is used to avoid same type names. e.g., there would be
1023  // many i32 and i64 types in one coroutine. And we would use i32_0 and
1024  // i32_1 to avoid the same type. Since it makes no sense the name of the
1025  // fields confilicts with each other.
1026  unsigned UnknownTypeNum = 0;
1027  for (unsigned Index = 0; Index < FrameTy->getNumElements(); Index++) {
1028  if (OffsetCache.find(Index) == OffsetCache.end())
1029  continue;
1030 
1031  std::string Name;
1032  uint64_t SizeInBits;
1033  uint32_t AlignInBits;
1034  uint64_t OffsetInBits;
1035  DIType *DITy = nullptr;
1036 
1037  Type *Ty = FrameTy->getElementType(Index);
1038  assert(Ty->isSized() && "We can't handle type which is not sized.\n");
1039  SizeInBits = Layout.getTypeSizeInBits(Ty).getFixedSize();
1040  AlignInBits = OffsetCache[Index].first * 8;
1041  OffsetInBits = OffsetCache[Index].second * 8;
1042 
1043  if (NameCache.find(Index) != NameCache.end()) {
1044  Name = NameCache[Index].str();
1045  DITy = TyCache[Index];
1046  } else {
1047  DITy = solveDIType(DBuilder, Ty, Layout, FrameDITy, LineNum, DITypeCache);
1048  assert(DITy && "SolveDIType shouldn't return nullptr.\n");
1049  Name = DITy->getName().str();
1050  Name += "_" + std::to_string(UnknownTypeNum);
1051  UnknownTypeNum++;
1052  }
1053 
1054  Elements.push_back(DBuilder.createMemberType(
1055  FrameDITy, Name, DFile, LineNum, SizeInBits, AlignInBits, OffsetInBits,
1056  llvm::DINode::FlagArtificial, DITy));
1057  }
1058 
1059  DBuilder.replaceArrays(FrameDITy, DBuilder.getOrCreateArray(Elements));
1060 
1061  auto *FrameDIVar = DBuilder.createAutoVariable(PromiseDIScope, "__coro_frame",
1062  DFile, LineNum, FrameDITy,
1063  true, DINode::FlagArtificial);
1064  assert(FrameDIVar->isValidLocationForIntrinsic(PromiseDDI->getDebugLoc()));
1065 
1066  // Subprogram would have ContainedNodes field which records the debug
1067  // variables it contained. So we need to add __coro_frame to the
1068  // ContainedNodes of it.
1069  //
1070  // If we don't add __coro_frame to the RetainedNodes, user may get
1071  // `no symbol __coro_frame in context` rather than `__coro_frame`
1072  // is optimized out, which is more precise.
1073  if (auto *SubProgram = dyn_cast<DISubprogram>(PromiseDIScope)) {
1074  auto RetainedNodes = SubProgram->getRetainedNodes();
1075  SmallVector<Metadata *, 32> RetainedNodesVec(RetainedNodes.begin(),
1076  RetainedNodes.end());
1077  RetainedNodesVec.push_back(FrameDIVar);
1078  SubProgram->replaceOperandWith(
1079  7, (MDTuple::get(F.getContext(), RetainedNodesVec)));
1080  }
1081 
1082  DBuilder.insertDeclare(Shape.FramePtr, FrameDIVar,
1083  DBuilder.createExpression(), DILoc,
1084  Shape.FramePtr->getNextNode());
1085 }
1086 
1087 // Build a struct that will keep state for an active coroutine.
1088 // struct f.frame {
1089 // ResumeFnTy ResumeFnAddr;
1090 // ResumeFnTy DestroyFnAddr;
1091 // int ResumeIndex;
1092 // ... promise (if present) ...
1093 // ... spills ...
1094 // };
1096  FrameDataInfo &FrameData) {
1097  LLVMContext &C = F.getContext();
1098  const DataLayout &DL = F.getParent()->getDataLayout();
1099  StructType *FrameTy = [&] {
1100  SmallString<32> Name(F.getName());
1101  Name.append(".Frame");
1102  return StructType::create(C, Name);
1103  }();
1104 
1105  // We will use this value to cap the alignment of spilled values.
1106  Optional<Align> MaxFrameAlignment;
1107  if (Shape.ABI == coro::ABI::Async)
1108  MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();
1109  FrameTypeBuilder B(C, DL, MaxFrameAlignment);
1110 
1111  AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
1112  Optional<FieldIDType> SwitchIndexFieldId;
1113 
1114  if (Shape.ABI == coro::ABI::Switch) {
1115  auto *FramePtrTy = FrameTy->getPointerTo();
1116  auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
1117  /*IsVarArg=*/false);
1118  auto *FnPtrTy = FnTy->getPointerTo();
1119 
1120  // Add header fields for the resume and destroy functions.
1121  // We can rely on these being perfectly packed.
1122  (void)B.addField(FnPtrTy, None, /*header*/ true);
1123  (void)B.addField(FnPtrTy, None, /*header*/ true);
1124 
1125  // PromiseAlloca field needs to be explicitly added here because it's
1126  // a header field with a fixed offset based on its alignment. Hence it
1127  // needs special handling and cannot be added to FrameData.Allocas.
1128  if (PromiseAlloca)
1129  FrameData.setFieldIndex(
1130  PromiseAlloca, B.addFieldForAlloca(PromiseAlloca, /*header*/ true));
1131 
1132  // Add a field to store the suspend index. This doesn't need to
1133  // be in the header.
1134  unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
1135  Type *IndexType = Type::getIntNTy(C, IndexBits);
1136 
1137  SwitchIndexFieldId = B.addField(IndexType, None);
1138  } else {
1139  assert(PromiseAlloca == nullptr && "lowering doesn't support promises");
1140  }
1141 
1142  // Because multiple allocas may own the same field slot,
1143  // we add allocas to field here.
1144  B.addFieldForAllocas(F, FrameData, Shape);
1145  // Add PromiseAlloca to Allocas list so that
1146  // 1. updateLayoutIndex could update its index after
1147  // `performOptimizedStructLayout`
1148  // 2. it is processed in insertSpills.
1149  if (Shape.ABI == coro::ABI::Switch && PromiseAlloca)
1150  // We assume that the promise alloca won't be modified before
1151  // CoroBegin and no alias will be create before CoroBegin.
1152  FrameData.Allocas.emplace_back(
1153  PromiseAlloca, DenseMap<Instruction *, llvm::Optional<APInt>>{}, false);
1154  // Create an entry for every spilled value.
1155  for (auto &S : FrameData.Spills) {
1156  Type *FieldType = S.first->getType();
1157  // For byval arguments, we need to store the pointed value in the frame,
1158  // instead of the pointer itself.
1159  if (const Argument *A = dyn_cast<Argument>(S.first))
1160  if (A->hasByValAttr())
1161  FieldType = A->getParamByValType();
1162  FieldIDType Id =
1163  B.addField(FieldType, None, false /*header*/, true /*IsSpillOfValue*/);
1164  FrameData.setFieldIndex(S.first, Id);
1165  }
1166 
1167  B.finish(FrameTy);
1168  FrameData.updateLayoutIndex(B);
1169  Shape.FrameAlign = B.getStructAlign();
1170  Shape.FrameSize = B.getStructSize();
1171 
1172  switch (Shape.ABI) {
1173  case coro::ABI::Switch: {
1174  // In the switch ABI, remember the switch-index field.
1175  auto IndexField = B.getLayoutField(*SwitchIndexFieldId);
1176  Shape.SwitchLowering.IndexField = IndexField.LayoutFieldIndex;
1177  Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();
1178  Shape.SwitchLowering.IndexOffset = IndexField.Offset;
1179 
1180  // Also round the frame size up to a multiple of its alignment, as is
1181  // generally expected in C/C++.
1182  Shape.FrameSize = alignTo(Shape.FrameSize, Shape.FrameAlign);
1183  break;
1184  }
1185 
1186  // In the retcon ABI, remember whether the frame is inline in the storage.
1187  case coro::ABI::Retcon:
1188  case coro::ABI::RetconOnce: {
1189  auto Id = Shape.getRetconCoroId();
1191  = (B.getStructSize() <= Id->getStorageSize() &&
1192  B.getStructAlign() <= Id->getStorageAlignment());
1193  break;
1194  }
1195  case coro::ABI::Async: {
1196  Shape.AsyncLowering.FrameOffset =
1198  // Also make the final context size a multiple of the context alignment to
1199  // make allocation easier for allocators.
1200  Shape.AsyncLowering.ContextSize =
1203  if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
1205  "The alignment requirment of frame variables cannot be higher than "
1206  "the alignment of the async function context");
1207  }
1208  break;
1209  }
1210  }
1211 
1212  return FrameTy;
1213 }
1214 
1215 // We use a pointer use visitor to track how an alloca is being used.
1216 // The goal is to be able to answer the following three questions:
1217 // 1. Should this alloca be allocated on the frame instead.
1218 // 2. Could the content of the alloca be modified prior to CoroBegn, which would
1219 // require copying the data from alloca to the frame after CoroBegin.
1220 // 3. Is there any alias created for this alloca prior to CoroBegin, but used
1221 // after CoroBegin. In that case, we will need to recreate the alias after
1222 // CoroBegin based off the frame. To answer question 1, we track two things:
1223 // a. List of all BasicBlocks that use this alloca or any of the aliases of
1224 // the alloca. In the end, we check if there exists any two basic blocks that
1225 // cross suspension points. If so, this alloca must be put on the frame. b.
1226 // Whether the alloca or any alias of the alloca is escaped at some point,
1227 // either by storing the address somewhere, or the address is used in a
1228 // function call that might capture. If it's ever escaped, this alloca must be
1229 // put on the frame conservatively.
1230 // To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.
1231 // Whenever a potential write happens, either through a store instruction, a
1232 // function call or any of the memory intrinsics, we check whether this
1233 // instruction is prior to CoroBegin. To answer question 3, we track the offsets
1234 // of all aliases created for the alloca prior to CoroBegin but used after
1235 // CoroBegin. llvm::Optional is used to be able to represent the case when the
1236 // offset is unknown (e.g. when you have a PHINode that takes in different
1237 // offset values). We cannot handle unknown offsets and will assert. This is the
1238 // potential issue left out. An ideal solution would likely require a
1239 // significant redesign.
1240 namespace {
1241 struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
1243  AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,
1244  const CoroBeginInst &CB, const SuspendCrossingInfo &Checker)
1245  : PtrUseVisitor(DL), DT(DT), CoroBegin(CB), Checker(Checker) {}
1246 
1247  void visit(Instruction &I) {
1248  Users.insert(&I);
1249  Base::visit(I);
1250  // If the pointer is escaped prior to CoroBegin, we have to assume it would
1251  // be written into before CoroBegin as well.
1252  if (PI.isEscaped() && !DT.dominates(&CoroBegin, PI.getEscapingInst())) {
1253  MayWriteBeforeCoroBegin = true;
1254  }
1255  }
1256  // We need to provide this overload as PtrUseVisitor uses a pointer based
1257  // visiting function.
1258  void visit(Instruction *I) { return visit(*I); }
1259 
1260  void visitPHINode(PHINode &I) {
1261  enqueueUsers(I);
1262  handleAlias(I);
1263  }
1264 
1265  void visitSelectInst(SelectInst &I) {
1266  enqueueUsers(I);
1267  handleAlias(I);
1268  }
1269 
1270  void visitStoreInst(StoreInst &SI) {
1271  // Regardless whether the alias of the alloca is the value operand or the
1272  // pointer operand, we need to assume the alloca is been written.
1273  handleMayWrite(SI);
1274 
1275  if (SI.getValueOperand() != U->get())
1276  return;
1277 
1278  // We are storing the pointer into a memory location, potentially escaping.
1279  // As an optimization, we try to detect simple cases where it doesn't
1280  // actually escape, for example:
1281  // %ptr = alloca ..
1282  // %addr = alloca ..
1283  // store %ptr, %addr
1284  // %x = load %addr
1285  // ..
1286  // If %addr is only used by loading from it, we could simply treat %x as
1287  // another alias of %ptr, and not considering %ptr being escaped.
1288  auto IsSimpleStoreThenLoad = [&]() {
1289  auto *AI = dyn_cast<AllocaInst>(SI.getPointerOperand());
1290  // If the memory location we are storing to is not an alloca, it
1291  // could be an alias of some other memory locations, which is difficult
1292  // to analyze.
1293  if (!AI)
1294  return false;
1295  // StoreAliases contains aliases of the memory location stored into.
1296  SmallVector<Instruction *, 4> StoreAliases = {AI};
1297  while (!StoreAliases.empty()) {
1298  Instruction *I = StoreAliases.pop_back_val();
1299  for (User *U : I->users()) {
1300  // If we are loading from the memory location, we are creating an
1301  // alias of the original pointer.
1302  if (auto *LI = dyn_cast<LoadInst>(U)) {
1303  enqueueUsers(*LI);
1304  handleAlias(*LI);
1305  continue;
1306  }
1307  // If we are overriding the memory location, the pointer certainly
1308  // won't escape.
1309  if (auto *S = dyn_cast<StoreInst>(U))
1310  if (S->getPointerOperand() == I)
1311  continue;
1312  if (auto *II = dyn_cast<IntrinsicInst>(U))
1313  if (II->isLifetimeStartOrEnd())
1314  continue;
1315  // BitCastInst creats aliases of the memory location being stored
1316  // into.
1317  if (auto *BI = dyn_cast<BitCastInst>(U)) {
1318  StoreAliases.push_back(BI);
1319  continue;
1320  }
1321  return false;
1322  }
1323  }
1324 
1325  return true;
1326  };
1327 
1328  if (!IsSimpleStoreThenLoad())
1329  PI.setEscaped(&SI);
1330  }
1331 
1332  // All mem intrinsics modify the data.
1333  void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(MI); }
1334 
1335  void visitBitCastInst(BitCastInst &BC) {
1337  handleAlias(BC);
1338  }
1339 
1342  handleAlias(ASC);
1343  }
1344 
1346  // The base visitor will adjust Offset accordingly.
1348  handleAlias(GEPI);
1349  }
1350 
1351  void visitIntrinsicInst(IntrinsicInst &II) {
1352  // When we found the lifetime markers refers to a
1353  // subrange of the original alloca, ignore the lifetime
1354  // markers to avoid misleading the analysis.
1355  if (II.getIntrinsicID() != Intrinsic::lifetime_start || !IsOffsetKnown ||
1356  !Offset.isZero())
1357  return Base::visitIntrinsicInst(II);
1358  LifetimeStarts.insert(&II);
1359  }
1360 
1361  void visitCallBase(CallBase &CB) {
1362  for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)
1363  if (U->get() == CB.getArgOperand(Op) && !CB.doesNotCapture(Op))
1364  PI.setEscaped(&CB);
1365  handleMayWrite(CB);
1366  }
1367 
1368  bool getShouldLiveOnFrame() const {
1369  if (!ShouldLiveOnFrame)
1370  ShouldLiveOnFrame = computeShouldLiveOnFrame();
1371  return ShouldLiveOnFrame.getValue();
1372  }
1373 
1374  bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }
1375 
1376  DenseMap<Instruction *, llvm::Optional<APInt>> getAliasesCopy() const {
1377  assert(getShouldLiveOnFrame() && "This method should only be called if the "
1378  "alloca needs to live on the frame.");
1379  for (const auto &P : AliasOffetMap)
1380  if (!P.second)
1381  report_fatal_error("Unable to handle an alias with unknown offset "
1382  "created before CoroBegin.");
1383  return AliasOffetMap;
1384  }
1385 
1386 private:
1387  const DominatorTree &DT;
1388  const CoroBeginInst &CoroBegin;
1389  const SuspendCrossingInfo &Checker;
1390  // All alias to the original AllocaInst, created before CoroBegin and used
1391  // after CoroBegin. Each entry contains the instruction and the offset in the
1392  // original Alloca. They need to be recreated after CoroBegin off the frame.
1395  SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};
1396  bool MayWriteBeforeCoroBegin{false};
1397 
1398  mutable llvm::Optional<bool> ShouldLiveOnFrame{};
1399 
1400  bool computeShouldLiveOnFrame() const {
1401  // If lifetime information is available, we check it first since it's
1402  // more precise. We look at every pair of lifetime.start intrinsic and
1403  // every basic block that uses the pointer to see if they cross suspension
1404  // points. The uses cover both direct uses as well as indirect uses.
1405  if (!LifetimeStarts.empty()) {
1406  for (auto *I : Users)
1407  for (auto *S : LifetimeStarts)
1408  if (Checker.isDefinitionAcrossSuspend(*S, I))
1409  return true;
1410  return false;
1411  }
1412  // FIXME: Ideally the isEscaped check should come at the beginning.
1413  // However there are a few loose ends that need to be fixed first before
1414  // we can do that. We need to make sure we are not over-conservative, so
1415  // that the data accessed in-between await_suspend and symmetric transfer
1416  // is always put on the stack, and also data accessed after coro.end is
1417  // always put on the stack (esp the return object). To fix that, we need
1418  // to:
1419  // 1) Potentially treat sret as nocapture in calls
1420  // 2) Special handle the return object and put it on the stack
1421  // 3) Utilize lifetime.end intrinsic
1422  if (PI.isEscaped())
1423  return true;
1424 
1425  for (auto *U1 : Users)
1426  for (auto *U2 : Users)
1427  if (Checker.isDefinitionAcrossSuspend(*U1, U2))
1428  return true;
1429 
1430  return false;
1431  }
1432 
1433  void handleMayWrite(const Instruction &I) {
1434  if (!DT.dominates(&CoroBegin, &I))
1435  MayWriteBeforeCoroBegin = true;
1436  }
1437 
1438  bool usedAfterCoroBegin(Instruction &I) {
1439  for (auto &U : I.uses())
1440  if (DT.dominates(&CoroBegin, U))
1441  return true;
1442  return false;
1443  }
1444 
1445  void handleAlias(Instruction &I) {
1446  // We track all aliases created prior to CoroBegin but used after.
1447  // These aliases may need to be recreated after CoroBegin if the alloca
1448  // need to live on the frame.
1449  if (DT.dominates(&CoroBegin, &I) || !usedAfterCoroBegin(I))
1450  return;
1451 
1452  if (!IsOffsetKnown) {
1453  AliasOffetMap[&I].reset();
1454  } else {
1455  auto Itr = AliasOffetMap.find(&I);
1456  if (Itr == AliasOffetMap.end()) {
1457  AliasOffetMap[&I] = Offset;
1458  } else if (Itr->second.hasValue() && Itr->second.getValue() != Offset) {
1459  // If we have seen two different possible values for this alias, we set
1460  // it to empty.
1461  AliasOffetMap[&I].reset();
1462  }
1463  }
1464  }
1465 };
1466 } // namespace
1467 
1468 // We need to make room to insert a spill after initial PHIs, but before
1469 // catchswitch instruction. Placing it before violates the requirement that
1470 // catchswitch, like all other EHPads must be the first nonPHI in a block.
1471 //
1472 // Split away catchswitch into a separate block and insert in its place:
1473 //
1474 // cleanuppad <InsertPt> cleanupret.
1475 //
1476 // cleanupret instruction will act as an insert point for the spill.
1478  BasicBlock *CurrentBlock = CatchSwitch->getParent();
1479  BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
1480  CurrentBlock->getTerminator()->eraseFromParent();
1481 
1482  auto *CleanupPad =
1483  CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
1484  auto *CleanupRet =
1485  CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
1486  return CleanupRet;
1487 }
1488 
1489 static void createFramePtr(coro::Shape &Shape) {
1490  auto *CB = Shape.CoroBegin;
1492  StructType *FrameTy = Shape.FrameTy;
1493  PointerType *FramePtrTy = FrameTy->getPointerTo();
1494  Shape.FramePtr =
1495  cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
1496 }
1497 
1498 // Replace all alloca and SSA values that are accessed across suspend points
1499 // with GetElementPointer from coroutine frame + loads and stores. Create an
1500 // AllocaSpillBB that will become the new entry block for the resume parts of
1501 // the coroutine:
1502 //
1503 // %hdl = coro.begin(...)
1504 // whatever
1505 //
1506 // becomes:
1507 //
1508 // %hdl = coro.begin(...)
1509 // %FramePtr = bitcast i8* hdl to %f.frame*
1510 // br label %AllocaSpillBB
1511 //
1512 // AllocaSpillBB:
1513 // ; geps corresponding to allocas that were moved to coroutine frame
1514 // br label PostSpill
1515 //
1516 // PostSpill:
1517 // whatever
1518 //
1519 //
1520 static Instruction *insertSpills(const FrameDataInfo &FrameData,
1521  coro::Shape &Shape) {
1522  auto *CB = Shape.CoroBegin;
1523  LLVMContext &C = CB->getContext();
1525  StructType *FrameTy = Shape.FrameTy;
1526  Instruction *FramePtr = Shape.FramePtr;
1527  DominatorTree DT(*CB->getFunction());
1529 
1530  // Create a GEP with the given index into the coroutine frame for the original
1531  // value Orig. Appends an extra 0 index for array-allocas, preserving the
1532  // original type.
1533  auto GetFramePointer = [&](Value *Orig) -> Value * {
1534  FieldIDType Index = FrameData.getFieldIndex(Orig);
1535  SmallVector<Value *, 3> Indices = {
1536  ConstantInt::get(Type::getInt32Ty(C), 0),
1537  ConstantInt::get(Type::getInt32Ty(C), Index),
1538  };
1539 
1540  if (auto *AI = dyn_cast<AllocaInst>(Orig)) {
1541  if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize())) {
1542  auto Count = CI->getValue().getZExtValue();
1543  if (Count > 1) {
1544  Indices.push_back(ConstantInt::get(Type::getInt32Ty(C), 0));
1545  }
1546  } else {
1547  report_fatal_error("Coroutines cannot handle non static allocas yet");
1548  }
1549  }
1550 
1551  auto GEP = cast<GetElementPtrInst>(
1552  Builder.CreateInBoundsGEP(FrameTy, FramePtr, Indices));
1553  if (isa<AllocaInst>(Orig)) {
1554  // If the type of GEP is not equal to the type of AllocaInst, it implies
1555  // that the AllocaInst may be reused in the Frame slot of other
1556  // AllocaInst. So We cast GEP to the AllocaInst here to re-use
1557  // the Frame storage.
1558  //
1559  // Note: If we change the strategy dealing with alignment, we need to refine
1560  // this casting.
1561  if (GEP->getResultElementType() != Orig->getType())
1562  return Builder.CreateBitCast(GEP, Orig->getType(),
1563  Orig->getName() + Twine(".cast"));
1564  }
1565  return GEP;
1566  };
1567 
1568  for (auto const &E : FrameData.Spills) {
1569  Value *Def = E.first;
1570  auto SpillAlignment = Align(FrameData.getAlign(Def));
1571  // Create a store instruction storing the value into the
1572  // coroutine frame.
1573  Instruction *InsertPt = nullptr;
1574  bool NeedToCopyArgPtrValue = false;
1575  if (auto *Arg = dyn_cast<Argument>(Def)) {
1576  // For arguments, we will place the store instruction right after
1577  // the coroutine frame pointer instruction, i.e. bitcast of
1578  // coro.begin from i8* to %f.frame*.
1579  InsertPt = FramePtr->getNextNode();
1580 
1581  // If we're spilling an Argument, make sure we clear 'nocapture'
1582  // from the coroutine function.
1583  Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::NoCapture);
1584 
1585  if (Arg->hasByValAttr())
1586  NeedToCopyArgPtrValue = true;
1587 
1588  } else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Def)) {
1589  // Don't spill immediately after a suspend; splitting assumes
1590  // that the suspend will be followed by a branch.
1591  InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHI();
1592  } else {
1593  auto *I = cast<Instruction>(Def);
1594  if (!DT.dominates(CB, I)) {
1595  // If it is not dominated by CoroBegin, then spill should be
1596  // inserted immediately after CoroFrame is computed.
1597  InsertPt = FramePtr->getNextNode();
1598  } else if (auto *II = dyn_cast<InvokeInst>(I)) {
1599  // If we are spilling the result of the invoke instruction, split
1600  // the normal edge and insert the spill in the new block.
1601  auto *NewBB = SplitEdge(II->getParent(), II->getNormalDest());
1602  InsertPt = NewBB->getTerminator();
1603  } else if (isa<PHINode>(I)) {
1604  // Skip the PHINodes and EH pads instructions.
1605  BasicBlock *DefBlock = I->getParent();
1606  if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
1607  InsertPt = splitBeforeCatchSwitch(CSI);
1608  else
1609  InsertPt = &*DefBlock->getFirstInsertionPt();
1610  } else {
1611  assert(!I->isTerminator() && "unexpected terminator");
1612  // For all other values, the spill is placed immediately after
1613  // the definition.
1614  InsertPt = I->getNextNode();
1615  }
1616  }
1617 
1618  auto Index = FrameData.getFieldIndex(Def);
1619  Builder.SetInsertPoint(InsertPt);
1620  auto *G = Builder.CreateConstInBoundsGEP2_32(
1621  FrameTy, FramePtr, 0, Index, Def->getName() + Twine(".spill.addr"));
1622  if (NeedToCopyArgPtrValue) {
1623  // For byval arguments, we need to store the pointed value in the frame,
1624  // instead of the pointer itself.
1625  auto *Value =
1626  Builder.CreateLoad(Def->getType()->getPointerElementType(), Def);
1627  Builder.CreateAlignedStore(Value, G, SpillAlignment);
1628  } else {
1629  Builder.CreateAlignedStore(Def, G, SpillAlignment);
1630  }
1631 
1632  BasicBlock *CurrentBlock = nullptr;
1633  Value *CurrentReload = nullptr;
1634  for (auto *U : E.second) {
1635  // If we have not seen the use block, create a load instruction to reload
1636  // the spilled value from the coroutine frame. Populates the Value pointer
1637  // reference provided with the frame GEP.
1638  if (CurrentBlock != U->getParent()) {
1639  CurrentBlock = U->getParent();
1640  Builder.SetInsertPoint(&*CurrentBlock->getFirstInsertionPt());
1641 
1642  auto *GEP = GetFramePointer(E.first);
1643  GEP->setName(E.first->getName() + Twine(".reload.addr"));
1644  if (NeedToCopyArgPtrValue)
1645  CurrentReload = GEP;
1646  else
1647  CurrentReload = Builder.CreateAlignedLoad(
1648  FrameTy->getElementType(FrameData.getFieldIndex(E.first)), GEP,
1649  SpillAlignment, E.first->getName() + Twine(".reload"));
1650 
1652  for (DbgDeclareInst *DDI : DIs) {
1653  bool AllowUnresolved = false;
1654  // This dbg.declare is preserved for all coro-split function
1655  // fragments. It will be unreachable in the main function, and
1656  // processed by coro::salvageDebugInfo() by CoroCloner.
1657  DIBuilder(*CurrentBlock->getParent()->getParent(), AllowUnresolved)
1658  .insertDeclare(CurrentReload, DDI->getVariable(),
1659  DDI->getExpression(), DDI->getDebugLoc(),
1660  &*Builder.GetInsertPoint());
1661  // This dbg.declare is for the main function entry point. It
1662  // will be deleted in all coro-split functions.
1663  coro::salvageDebugInfo(DbgPtrAllocaCache, DDI, Shape.ReuseFrameSlot);
1664  }
1665  }
1666 
1667  // If we have a single edge PHINode, remove it and replace it with a
1668  // reload from the coroutine frame. (We already took care of multi edge
1669  // PHINodes by rewriting them in the rewritePHIs function).
1670  if (auto *PN = dyn_cast<PHINode>(U)) {
1671  assert(PN->getNumIncomingValues() == 1 &&
1672  "unexpected number of incoming "
1673  "values in the PHINode");
1674  PN->replaceAllUsesWith(CurrentReload);
1675  PN->eraseFromParent();
1676  continue;
1677  }
1678 
1679  // Replace all uses of CurrentValue in the current instruction with
1680  // reload.
1681  U->replaceUsesOfWith(Def, CurrentReload);
1682  }
1683  }
1684 
1685  BasicBlock *FramePtrBB = FramePtr->getParent();
1686 
1687  auto SpillBlock =
1688  FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
1689  SpillBlock->splitBasicBlock(&SpillBlock->front(), "PostSpill");
1690  Shape.AllocaSpillBlock = SpillBlock;
1691 
1692  // retcon and retcon.once lowering assumes all uses have been sunk.
1693  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
1694  Shape.ABI == coro::ABI::Async) {
1695  // If we found any allocas, replace all of their remaining uses with Geps.
1696  Builder.SetInsertPoint(&SpillBlock->front());
1697  for (const auto &P : FrameData.Allocas) {
1698  AllocaInst *Alloca = P.Alloca;
1699  auto *G = GetFramePointer(Alloca);
1700 
1701  // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))
1702  // here, as we are changing location of the instruction.
1703  G->takeName(Alloca);
1704  Alloca->replaceAllUsesWith(G);
1705  Alloca->eraseFromParent();
1706  }
1707  return FramePtr;
1708  }
1709 
1710  // If we found any alloca, replace all of their remaining uses with GEP
1711  // instructions. To remain debugbility, we replace the uses of allocas for
1712  // dbg.declares and dbg.values with the reload from the frame.
1713  // Note: We cannot replace the alloca with GEP instructions indiscriminately,
1714  // as some of the uses may not be dominated by CoroBegin.
1715  Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
1716  SmallVector<Instruction *, 4> UsersToUpdate;
1717  for (const auto &A : FrameData.Allocas) {
1718  AllocaInst *Alloca = A.Alloca;
1719  UsersToUpdate.clear();
1720  for (User *U : Alloca->users()) {
1721  auto *I = cast<Instruction>(U);
1722  if (DT.dominates(CB, I))
1723  UsersToUpdate.push_back(I);
1724  }
1725  if (UsersToUpdate.empty())
1726  continue;
1727  auto *G = GetFramePointer(Alloca);
1728  G->setName(Alloca->getName() + Twine(".reload.addr"));
1729 
1731  findDbgUsers(DIs, Alloca);
1732  for (auto *DVI : DIs)
1733  DVI->replaceUsesOfWith(Alloca, G);
1734 
1735  for (Instruction *I : UsersToUpdate)
1736  I->replaceUsesOfWith(Alloca, G);
1737  }
1738  Builder.SetInsertPoint(FramePtr->getNextNode());
1739  for (const auto &A : FrameData.Allocas) {
1740  AllocaInst *Alloca = A.Alloca;
1741  if (A.MayWriteBeforeCoroBegin) {
1742  // isEscaped really means potentially modified before CoroBegin.
1743  if (Alloca->isArrayAllocation())
1745  "Coroutines cannot handle copying of array allocas yet");
1746 
1747  auto *G = GetFramePointer(Alloca);
1748  auto *Value = Builder.CreateLoad(Alloca->getAllocatedType(), Alloca);
1749  Builder.CreateStore(Value, G);
1750  }
1751  // For each alias to Alloca created before CoroBegin but used after
1752  // CoroBegin, we recreate them after CoroBegin by appplying the offset
1753  // to the pointer in the frame.
1754  for (const auto &Alias : A.Aliases) {
1755  auto *FramePtr = GetFramePointer(Alloca);
1756  auto *FramePtrRaw =
1757  Builder.CreateBitCast(FramePtr, Type::getInt8PtrTy(C));
1758  auto *AliasPtr = Builder.CreateGEP(
1759  Type::getInt8Ty(C), FramePtrRaw,
1760  ConstantInt::get(Type::getInt64Ty(C), Alias.second.getValue()));
1761  auto *AliasPtrTyped =
1762  Builder.CreateBitCast(AliasPtr, Alias.first->getType());
1763  Alias.first->replaceUsesWithIf(
1764  AliasPtrTyped, [&](Use &U) { return DT.dominates(CB, U); });
1765  }
1766  }
1767  return FramePtr;
1768 }
1769 
1770 // Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
1771 // PHI in InsertedBB.
1773  BasicBlock *InsertedBB,
1774  BasicBlock *PredBB,
1775  PHINode *UntilPHI = nullptr) {
1776  auto *PN = cast<PHINode>(&SuccBB->front());
1777  do {
1778  int Index = PN->getBasicBlockIndex(InsertedBB);
1779  Value *V = PN->getIncomingValue(Index);
1780  PHINode *InputV = PHINode::Create(
1781  V->getType(), 1, V->getName() + Twine(".") + SuccBB->getName(),
1782  &InsertedBB->front());
1783  InputV->addIncoming(V, PredBB);
1784  PN->setIncomingValue(Index, InputV);
1785  PN = dyn_cast<PHINode>(PN->getNextNode());
1786  } while (PN != UntilPHI);
1787 }
1788 
1789 // Rewrites the PHI Nodes in a cleanuppad.
1790 static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,
1791  CleanupPadInst *CleanupPad) {
1792  // For every incoming edge to a CleanupPad we will create a new block holding
1793  // all incoming values in single-value PHI nodes. We will then create another
1794  // block to act as a dispather (as all unwind edges for related EH blocks
1795  // must be the same).
1796  //
1797  // cleanuppad:
1798  // %2 = phi i32[%0, %catchswitch], [%1, %catch.1]
1799  // %3 = cleanuppad within none []
1800  //
1801  // It will create:
1802  //
1803  // cleanuppad.corodispatch
1804  // %2 = phi i8[0, %catchswitch], [1, %catch.1]
1805  // %3 = cleanuppad within none []
1806  // switch i8 % 2, label %unreachable
1807  // [i8 0, label %cleanuppad.from.catchswitch
1808  // i8 1, label %cleanuppad.from.catch.1]
1809  // cleanuppad.from.catchswitch:
1810  // %4 = phi i32 [%0, %catchswitch]
1811  // br %label cleanuppad
1812  // cleanuppad.from.catch.1:
1813  // %6 = phi i32 [%1, %catch.1]
1814  // br %label cleanuppad
1815  // cleanuppad:
1816  // %8 = phi i32 [%4, %cleanuppad.from.catchswitch],
1817  // [%6, %cleanuppad.from.catch.1]
1818 
1819  // Unreachable BB, in case switching on an invalid value in the dispatcher.
1820  auto *UnreachBB = BasicBlock::Create(
1821  CleanupPadBB->getContext(), "unreachable", CleanupPadBB->getParent());
1822  IRBuilder<> Builder(UnreachBB);
1823  Builder.CreateUnreachable();
1824 
1825  // Create a new cleanuppad which will be the dispatcher.
1826  auto *NewCleanupPadBB =
1827  BasicBlock::Create(CleanupPadBB->getContext(),
1828  CleanupPadBB->getName() + Twine(".corodispatch"),
1829  CleanupPadBB->getParent(), CleanupPadBB);
1830  Builder.SetInsertPoint(NewCleanupPadBB);
1831  auto *SwitchType = Builder.getInt8Ty();
1832  auto *SetDispatchValuePN =
1833  Builder.CreatePHI(SwitchType, pred_size(CleanupPadBB));
1834  CleanupPad->removeFromParent();
1835  CleanupPad->insertAfter(SetDispatchValuePN);
1836  auto *SwitchOnDispatch = Builder.CreateSwitch(SetDispatchValuePN, UnreachBB,
1837  pred_size(CleanupPadBB));
1838 
1839  int SwitchIndex = 0;
1840  SmallVector<BasicBlock *, 8> Preds(predecessors(CleanupPadBB));
1841  for (BasicBlock *Pred : Preds) {
1842  // Create a new cleanuppad and move the PHI values to there.
1843  auto *CaseBB = BasicBlock::Create(CleanupPadBB->getContext(),
1844  CleanupPadBB->getName() +
1845  Twine(".from.") + Pred->getName(),
1846  CleanupPadBB->getParent(), CleanupPadBB);
1847  updatePhiNodes(CleanupPadBB, Pred, CaseBB);
1848  CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +
1849  Pred->getName());
1850  Builder.SetInsertPoint(CaseBB);
1851  Builder.CreateBr(CleanupPadBB);
1852  movePHIValuesToInsertedBlock(CleanupPadBB, CaseBB, NewCleanupPadBB);
1853 
1854  // Update this Pred to the new unwind point.
1855  setUnwindEdgeTo(Pred->getTerminator(), NewCleanupPadBB);
1856 
1857  // Setup the switch in the dispatcher.
1858  auto *SwitchConstant = ConstantInt::get(SwitchType, SwitchIndex);
1859  SetDispatchValuePN->addIncoming(SwitchConstant, Pred);
1860  SwitchOnDispatch->addCase(SwitchConstant, CaseBB);
1861  SwitchIndex++;
1862  }
1863 }
1864 
1866  SmallVector<PHINode *, 32> Worklist;
1867  for (auto &BB : F) {
1868  for (auto &Phi : BB.phis()) {
1869  if (Phi.getNumIncomingValues() == 1) {
1870  Worklist.push_back(&Phi);
1871  } else
1872  break;
1873  }
1874  }
1875  while (!Worklist.empty()) {
1876  auto *Phi = Worklist.pop_back_val();
1877  auto *OriginalValue = Phi->getIncomingValue(0);
1878  Phi->replaceAllUsesWith(OriginalValue);
1879  }
1880 }
1881 
1882 static void rewritePHIs(BasicBlock &BB) {
1883  // For every incoming edge we will create a block holding all
1884  // incoming values in a single PHI nodes.
1885  //
1886  // loop:
1887  // %n.val = phi i32[%n, %entry], [%inc, %loop]
1888  //
1889  // It will create:
1890  //
1891  // loop.from.entry:
1892  // %n.loop.pre = phi i32 [%n, %entry]
1893  // br %label loop
1894  // loop.from.loop:
1895  // %inc.loop.pre = phi i32 [%inc, %loop]
1896  // br %label loop
1897  //
1898  // After this rewrite, further analysis will ignore any phi nodes with more
1899  // than one incoming edge.
1900 
1901  // TODO: Simplify PHINodes in the basic block to remove duplicate
1902  // predecessors.
1903 
1904  // Special case for CleanupPad: all EH blocks must have the same unwind edge
1905  // so we need to create an additional "dispatcher" block.
1906  if (auto *CleanupPad =
1907  dyn_cast_or_null<CleanupPadInst>(BB.getFirstNonPHI())) {
1909  for (BasicBlock *Pred : Preds) {
1910  if (CatchSwitchInst *CS =
1911  dyn_cast<CatchSwitchInst>(Pred->getTerminator())) {
1912  // CleanupPad with a CatchSwitch predecessor: therefore this is an
1913  // unwind destination that needs to be handle specially.
1914  assert(CS->getUnwindDest() == &BB);
1915  (void)CS;
1916  rewritePHIsForCleanupPad(&BB, CleanupPad);
1917  return;
1918  }
1919  }
1920  }
1921 
1922  LandingPadInst *LandingPad = nullptr;
1923  PHINode *ReplPHI = nullptr;
1924  if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
1925  // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
1926  // We replace the original landing pad with a PHINode that will collect the
1927  // results from all of them.
1928  ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
1929  ReplPHI->takeName(LandingPad);
1930  LandingPad->replaceAllUsesWith(ReplPHI);
1931  // We will erase the original landing pad at the end of this function after
1932  // ehAwareSplitEdge cloned it in the transition blocks.
1933  }
1934 
1936  for (BasicBlock *Pred : Preds) {
1937  auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
1938  IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
1939 
1940  // Stop the moving of values at ReplPHI, as this is either null or the PHI
1941  // that replaced the landing pad.
1942  movePHIValuesToInsertedBlock(&BB, IncomingBB, Pred, ReplPHI);
1943  }
1944 
1945  if (LandingPad) {
1946  // Calls to ehAwareSplitEdge function cloned the original lading pad.
1947  // No longer need it.
1948  LandingPad->eraseFromParent();
1949  }
1950 }
1951 
1952 static void rewritePHIs(Function &F) {
1954 
1955  for (BasicBlock &BB : F)
1956  if (auto *PN = dyn_cast<PHINode>(&BB.front()))
1957  if (PN->getNumIncomingValues() > 1)
1958  WorkList.push_back(&BB);
1959 
1960  for (BasicBlock *BB : WorkList)
1961  rewritePHIs(*BB);
1962 }
1963 
1964 // Check for instructions that we can recreate on resume as opposed to spill
1965 // the result into a coroutine frame.
1966 static bool materializable(Instruction &V) {
1967  return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
1968  isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
1969 }
1970 
1971 // Check for structural coroutine intrinsics that should not be spilled into
1972 // the coroutine frame.
1974  return isa<CoroIdInst>(&I) || isa<CoroSaveInst>(&I) ||
1975  isa<CoroSuspendInst>(&I);
1976 }
1977 
1978 // For every use of the value that is across suspend point, recreate that value
1979 // after a suspend point.
1981  const SpillInfo &Spills) {
1982  for (const auto &E : Spills) {
1983  Value *Def = E.first;
1984  BasicBlock *CurrentBlock = nullptr;
1985  Instruction *CurrentMaterialization = nullptr;
1986  for (Instruction *U : E.second) {
1987  // If we have not seen this block, materialize the value.
1988  if (CurrentBlock != U->getParent()) {
1989 
1990  bool IsInCoroSuspendBlock = isa<AnyCoroSuspendInst>(U);
1991  CurrentBlock = U->getParent();
1992  auto *InsertBlock = IsInCoroSuspendBlock
1993  ? CurrentBlock->getSinglePredecessor()
1994  : CurrentBlock;
1995  CurrentMaterialization = cast<Instruction>(Def)->clone();
1996  CurrentMaterialization->setName(Def->getName());
1997  CurrentMaterialization->insertBefore(
1998  IsInCoroSuspendBlock ? InsertBlock->getTerminator()
1999  : &*InsertBlock->getFirstInsertionPt());
2000  }
2001  if (auto *PN = dyn_cast<PHINode>(U)) {
2002  assert(PN->getNumIncomingValues() == 1 &&
2003  "unexpected number of incoming "
2004  "values in the PHINode");
2005  PN->replaceAllUsesWith(CurrentMaterialization);
2006  PN->eraseFromParent();
2007  continue;
2008  }
2009  // Replace all uses of Def in the current instruction with the
2010  // CurrentMaterialization for the block.
2011  U->replaceUsesOfWith(Def, CurrentMaterialization);
2012  }
2013  }
2014 }
2015 
2016 // Splits the block at a particular instruction unless it is the first
2017 // instruction in the block with a single predecessor.
2019  auto *BB = I->getParent();
2020  if (&BB->front() == I) {
2021  if (BB->getSinglePredecessor()) {
2022  BB->setName(Name);
2023  return BB;
2024  }
2025  }
2026  return BB->splitBasicBlock(I, Name);
2027 }
2028 
2029 // Split above and below a particular instruction so that it
2030 // will be all alone by itself in a block.
2031 static void splitAround(Instruction *I, const Twine &Name) {
2033  splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
2034 }
2035 
2037  return isa<AnyCoroSuspendInst>(BB->front());
2038 }
2039 
2041 
2042 /// Does control flow starting at the given block ever reach a suspend
2043 /// instruction before reaching a block in VisitedOrFreeBBs?
2045  VisitedBlocksSet &VisitedOrFreeBBs) {
2046  // Eagerly try to add this block to the visited set. If it's already
2047  // there, stop recursing; this path doesn't reach a suspend before
2048  // either looping or reaching a freeing block.
2049  if (!VisitedOrFreeBBs.insert(From).second)
2050  return false;
2051 
2052  // We assume that we'll already have split suspends into their own blocks.
2053  if (isSuspendBlock(From))
2054  return true;
2055 
2056  // Recurse on the successors.
2057  for (auto Succ : successors(From)) {
2058  if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))
2059  return true;
2060  }
2061 
2062  return false;
2063 }
2064 
2065 /// Is the given alloca "local", i.e. bounded in lifetime to not cross a
2066 /// suspend point?
2068  // Seed the visited set with all the basic blocks containing a free
2069  // so that we won't pass them up.
2070  VisitedBlocksSet VisitedOrFreeBBs;
2071  for (auto User : AI->users()) {
2072  if (auto FI = dyn_cast<CoroAllocaFreeInst>(User))
2073  VisitedOrFreeBBs.insert(FI->getParent());
2074  }
2075 
2076  return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);
2077 }
2078 
2079 /// After we split the coroutine, will the given basic block be along
2080 /// an obvious exit path for the resumption function?
2082  unsigned depth = 3) {
2083  // If we've bottomed out our depth count, stop searching and assume
2084  // that the path might loop back.
2085  if (depth == 0) return false;
2086 
2087  // If this is a suspend block, we're about to exit the resumption function.
2088  if (isSuspendBlock(BB)) return true;
2089 
2090  // Recurse into the successors.
2091  for (auto Succ : successors(BB)) {
2092  if (!willLeaveFunctionImmediatelyAfter(Succ, depth - 1))
2093  return false;
2094  }
2095 
2096  // If none of the successors leads back in a loop, we're on an exit/abort.
2097  return true;
2098 }
2099 
2101  // Look for a free that isn't sufficiently obviously followed by
2102  // either a suspend or a termination, i.e. something that will leave
2103  // the coro resumption frame.
2104  for (auto U : AI->users()) {
2105  auto FI = dyn_cast<CoroAllocaFreeInst>(U);
2106  if (!FI) continue;
2107 
2108  if (!willLeaveFunctionImmediatelyAfter(FI->getParent()))
2109  return true;
2110  }
2111 
2112  // If we never found one, we don't need a stack save.
2113  return false;
2114 }
2115 
2116 /// Turn each of the given local allocas into a normal (dynamic) alloca
2117 /// instruction.
2119  SmallVectorImpl<Instruction*> &DeadInsts) {
2120  for (auto AI : LocalAllocas) {
2121  auto M = AI->getModule();
2122  IRBuilder<> Builder(AI);
2123 
2124  // Save the stack depth. Try to avoid doing this if the stackrestore
2125  // is going to immediately precede a return or something.
2126  Value *StackSave = nullptr;
2127  if (localAllocaNeedsStackSave(AI))
2128  StackSave = Builder.CreateCall(
2129  Intrinsic::getDeclaration(M, Intrinsic::stacksave));
2130 
2131  // Allocate memory.
2132  auto Alloca = Builder.CreateAlloca(Builder.getInt8Ty(), AI->getSize());
2133  Alloca->setAlignment(Align(AI->getAlignment()));
2134 
2135  for (auto U : AI->users()) {
2136  // Replace gets with the allocation.
2137  if (isa<CoroAllocaGetInst>(U)) {
2138  U->replaceAllUsesWith(Alloca);
2139 
2140  // Replace frees with stackrestores. This is safe because
2141  // alloca.alloc is required to obey a stack discipline, although we
2142  // don't enforce that structurally.
2143  } else {
2144  auto FI = cast<CoroAllocaFreeInst>(U);
2145  if (StackSave) {
2146  Builder.SetInsertPoint(FI);
2147  Builder.CreateCall(
2148  Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
2149  StackSave);
2150  }
2151  }
2152  DeadInsts.push_back(cast<Instruction>(U));
2153  }
2154 
2155  DeadInsts.push_back(AI);
2156  }
2157 }
2158 
2159 /// Turn the given coro.alloca.alloc call into a dynamic allocation.
2160 /// This happens during the all-instructions iteration, so it must not
2161 /// delete the call.
2163  coro::Shape &Shape,
2164  SmallVectorImpl<Instruction*> &DeadInsts) {
2165  IRBuilder<> Builder(AI);
2166  auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);
2167 
2168  for (User *U : AI->users()) {
2169  if (isa<CoroAllocaGetInst>(U)) {
2170  U->replaceAllUsesWith(Alloc);
2171  } else {
2172  auto FI = cast<CoroAllocaFreeInst>(U);
2173  Builder.SetInsertPoint(FI);
2174  Shape.emitDealloc(Builder, Alloc, nullptr);
2175  }
2176  DeadInsts.push_back(cast<Instruction>(U));
2177  }
2178 
2179  // Push this on last so that it gets deleted after all the others.
2180  DeadInsts.push_back(AI);
2181 
2182  // Return the new allocation value so that we can check for needed spills.
2183  return cast<Instruction>(Alloc);
2184 }
2185 
2186 /// Get the current swifterror value.
2188  coro::Shape &Shape) {
2189  // Make a fake function pointer as a sort of intrinsic.
2190  auto FnTy = FunctionType::get(ValueTy, {}, false);
2191  auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2192 
2193  auto Call = Builder.CreateCall(FnTy, Fn, {});
2194  Shape.SwiftErrorOps.push_back(Call);
2195 
2196  return Call;
2197 }
2198 
2199 /// Set the given value as the current swifterror value.
2200 ///
2201 /// Returns a slot that can be used as a swifterror slot.
2203  coro::Shape &Shape) {
2204  // Make a fake function pointer as a sort of intrinsic.
2205  auto FnTy = FunctionType::get(V->getType()->getPointerTo(),
2206  {V->getType()}, false);
2207  auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2208 
2209  auto Call = Builder.CreateCall(FnTy, Fn, { V });
2210  Shape.SwiftErrorOps.push_back(Call);
2211 
2212  return Call;
2213 }
2214 
2215 /// Set the swifterror value from the given alloca before a call,
2216 /// then put in back in the alloca afterwards.
2217 ///
2218 /// Returns an address that will stand in for the swifterror slot
2219 /// until splitting.
2221  AllocaInst *Alloca,
2222  coro::Shape &Shape) {
2223  auto ValueTy = Alloca->getAllocatedType();
2225 
2226  // Load the current value from the alloca and set it as the
2227  // swifterror value.
2228  auto ValueBeforeCall = Builder.CreateLoad(ValueTy, Alloca);
2229  auto Addr = emitSetSwiftErrorValue(Builder, ValueBeforeCall, Shape);
2230 
2231  // Move to after the call. Since swifterror only has a guaranteed
2232  // value on normal exits, we can ignore implicit and explicit unwind
2233  // edges.
2234  if (isa<CallInst>(Call)) {
2235  Builder.SetInsertPoint(Call->getNextNode());
2236  } else {
2237  auto Invoke = cast<InvokeInst>(Call);
2238  Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
2239  }
2240 
2241  // Get the current swifterror value and store it to the alloca.
2242  auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
2243  Builder.CreateStore(ValueAfterCall, Alloca);
2244 
2245  return Addr;
2246 }
2247 
2248 /// Eliminate a formerly-swifterror alloca by inserting the get/set
2249 /// intrinsics and attempting to MemToReg the alloca away.
2251  coro::Shape &Shape) {
2252  for (auto UI = Alloca->use_begin(), UE = Alloca->use_end(); UI != UE; ) {
2253  // We're likely changing the use list, so use a mutation-safe
2254  // iteration pattern.
2255  auto &Use = *UI;
2256  ++UI;
2257 
2258  // swifterror values can only be used in very specific ways.
2259  // We take advantage of that here.
2260  auto User = Use.getUser();
2261  if (isa<LoadInst>(User) || isa<StoreInst>(User))
2262  continue;
2263 
2264  assert(isa<CallInst>(User) || isa<InvokeInst>(User));
2265  auto Call = cast<Instruction>(User);
2266 
2267  auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);
2268 
2269  // Use the returned slot address as the call argument.
2270  Use.set(Addr);
2271  }
2272 
2273  // All the uses should be loads and stores now.
2274  assert(isAllocaPromotable(Alloca));
2275 }
2276 
2277 /// "Eliminate" a swifterror argument by reducing it to the alloca case
2278 /// and then loading and storing in the prologue and epilog.
2279 ///
2280 /// The argument keeps the swifterror flag.
2282  coro::Shape &Shape,
2283  SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
2284  IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrDbg());
2285 
2286  auto ArgTy = cast<PointerType>(Arg.getType());
2287  auto ValueTy = ArgTy->getElementType();
2288 
2289  // Reduce to the alloca case:
2290 
2291  // Create an alloca and replace all uses of the arg with it.
2292  auto Alloca = Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());
2293  Arg.replaceAllUsesWith(Alloca);
2294 
2295  // Set an initial value in the alloca. swifterror is always null on entry.
2296  auto InitialValue = Constant::getNullValue(ValueTy);
2297  Builder.CreateStore(InitialValue, Alloca);
2298 
2299  // Find all the suspends in the function and save and restore around them.
2300  for (auto Suspend : Shape.CoroSuspends) {
2301  (void) emitSetAndGetSwiftErrorValueAround(Suspend, Alloca, Shape);
2302  }
2303 
2304  // Find all the coro.ends in the function and restore the error value.
2305  for (auto End : Shape.CoroEnds) {
2306  Builder.SetInsertPoint(End);
2307  auto FinalValue = Builder.CreateLoad(ValueTy, Alloca);
2308  (void) emitSetSwiftErrorValue(Builder, FinalValue, Shape);
2309  }
2310 
2311  // Now we can use the alloca logic.
2312  AllocasToPromote.push_back(Alloca);
2313  eliminateSwiftErrorAlloca(F, Alloca, Shape);
2314 }
2315 
2316 /// Eliminate all problematic uses of swifterror arguments and allocas
2317 /// from the function. We'll fix them up later when splitting the function.
2319  SmallVector<AllocaInst*, 4> AllocasToPromote;
2320 
2321  // Look for a swifterror argument.
2322  for (auto &Arg : F.args()) {
2323  if (!Arg.hasSwiftErrorAttr()) continue;
2324 
2325  eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
2326  break;
2327  }
2328 
2329  // Look for swifterror allocas.
2330  for (auto &Inst : F.getEntryBlock()) {
2331  auto Alloca = dyn_cast<AllocaInst>(&Inst);
2332  if (!Alloca || !Alloca->isSwiftError()) continue;
2333 
2334  // Clear the swifterror flag.
2335  Alloca->setSwiftError(false);
2336 
2337  AllocasToPromote.push_back(Alloca);
2338  eliminateSwiftErrorAlloca(F, Alloca, Shape);
2339  }
2340 
2341  // If we have any allocas to promote, compute a dominator tree and
2342  // promote them en masse.
2343  if (!AllocasToPromote.empty()) {
2344  DominatorTree DT(F);
2345  PromoteMemToReg(AllocasToPromote, DT);
2346  }
2347 }
2348 
2349 /// retcon and retcon.once conventions assume that all spill uses can be sunk
2350 /// after the coro.begin intrinsic.
2352  const FrameDataInfo &FrameData,
2353  CoroBeginInst *CoroBegin) {
2354  DominatorTree Dom(F);
2355 
2358 
2359  // Collect all users that precede coro.begin.
2360  for (auto *Def : FrameData.getAllDefs()) {
2361  for (User *U : Def->users()) {
2362  auto Inst = cast<Instruction>(U);
2363  if (Inst->getParent() != CoroBegin->getParent() ||
2364  Dom.dominates(CoroBegin, Inst))
2365  continue;
2366  if (ToMove.insert(Inst))
2367  Worklist.push_back(Inst);
2368  }
2369  }
2370  // Recursively collect users before coro.begin.
2371  while (!Worklist.empty()) {
2372  auto *Def = Worklist.pop_back_val();
2373  for (User *U : Def->users()) {
2374  auto Inst = cast<Instruction>(U);
2375  if (Dom.dominates(CoroBegin, Inst))
2376  continue;
2377  if (ToMove.insert(Inst))
2378  Worklist.push_back(Inst);
2379  }
2380  }
2381 
2382  // Sort by dominance.
2383  SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
2384  llvm::sort(InsertionList, [&Dom](Instruction *A, Instruction *B) -> bool {
2385  // If a dominates b it should preceed (<) b.
2386  return Dom.dominates(A, B);
2387  });
2388 
2389  Instruction *InsertPt = CoroBegin->getNextNode();
2390  for (Instruction *Inst : InsertionList)
2391  Inst->moveBefore(InsertPt);
2392 }
2393 
2394 /// For each local variable that all of its user are only used inside one of
2395 /// suspended region, we sink their lifetime.start markers to the place where
2396 /// after the suspend block. Doing so minimizes the lifetime of each variable,
2397 /// hence minimizing the amount of data we end up putting on the frame.
2399  SuspendCrossingInfo &Checker) {
2400  DominatorTree DT(F);
2401 
2402  // Collect all possible basic blocks which may dominate all uses of allocas.
2404  DomSet.insert(&F.getEntryBlock());
2405  for (auto *CSI : Shape.CoroSuspends) {
2406  BasicBlock *SuspendBlock = CSI->getParent();
2407  assert(isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() &&
2408  "should have split coro.suspend into its own block");
2409  DomSet.insert(SuspendBlock->getSingleSuccessor());
2410  }
2411 
2412  for (Instruction &I : instructions(F)) {
2413  AllocaInst* AI = dyn_cast<AllocaInst>(&I);
2414  if (!AI)
2415  continue;
2416 
2417  for (BasicBlock *DomBB : DomSet) {
2418  bool Valid = true;
2420 
2421  auto isLifetimeStart = [](Instruction* I) {
2422  if (auto* II = dyn_cast<IntrinsicInst>(I))
2423  return II->getIntrinsicID() == Intrinsic::lifetime_start;
2424  return false;
2425  };
2426 
2427  auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
2428  if (isLifetimeStart(U)) {
2429  Lifetimes.push_back(U);
2430  return true;
2431  }
2432  if (!U->hasOneUse() || U->stripPointerCasts() != AI)
2433  return false;
2434  if (isLifetimeStart(U->user_back())) {
2435  Lifetimes.push_back(U->user_back());
2436  return true;
2437  }
2438  return false;
2439  };
2440 
2441  for (User *U : AI->users()) {
2442  Instruction *UI = cast<Instruction>(U);
2443  // For all users except lifetime.start markers, if they are all
2444  // dominated by one of the basic blocks and do not cross
2445  // suspend points as well, then there is no need to spill the
2446  // instruction.
2447  if (!DT.dominates(DomBB, UI->getParent()) ||
2448  Checker.isDefinitionAcrossSuspend(DomBB, UI)) {
2449  // Skip lifetime.start, GEP and bitcast used by lifetime.start
2450  // markers.
2451  if (collectLifetimeStart(UI, AI))
2452  continue;
2453  Valid = false;
2454  break;
2455  }
2456  }
2457  // Sink lifetime.start markers to dominate block when they are
2458  // only used outside the region.
2459  if (Valid && Lifetimes.size() != 0) {
2460  // May be AI itself, when the type of AI is i8*
2461  auto *NewBitCast = [&](AllocaInst *AI) -> Value* {
2462  if (isa<AllocaInst>(Lifetimes[0]->getOperand(1)))
2463  return AI;
2464  auto *Int8PtrTy = Type::getInt8PtrTy(F.getContext());
2465  return CastInst::Create(Instruction::BitCast, AI, Int8PtrTy, "",
2466  DomBB->getTerminator());
2467  }(AI);
2468 
2469  auto *NewLifetime = Lifetimes[0]->clone();
2470  NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(1), NewBitCast);
2471  NewLifetime->insertBefore(DomBB->getTerminator());
2472 
2473  // All the outsided lifetime.start markers are no longer necessary.
2474  for (Instruction *S : Lifetimes)
2475  S->eraseFromParent();
2476 
2477  break;
2478  }
2479  }
2480  }
2481 }
2482 
2484  const SuspendCrossingInfo &Checker,
2485  SmallVectorImpl<AllocaInfo> &Allocas) {
2486  for (Instruction &I : instructions(F)) {
2487  auto *AI = dyn_cast<AllocaInst>(&I);
2488  if (!AI)
2489  continue;
2490  // The PromiseAlloca will be specially handled since it needs to be in a
2491  // fixed position in the frame.
2492  if (AI == Shape.SwitchLowering.PromiseAlloca) {
2493  continue;
2494  }
2495  DominatorTree DT(F);
2496  AllocaUseVisitor Visitor{F.getParent()->getDataLayout(), DT,
2497  *Shape.CoroBegin, Checker};
2498  Visitor.visitPtr(*AI);
2499  if (!Visitor.getShouldLiveOnFrame())
2500  continue;
2501  Allocas.emplace_back(AI, Visitor.getAliasesCopy(),
2502  Visitor.getMayWriteBeforeCoroBegin());
2503  }
2504 }
2505 
2508  DbgVariableIntrinsic *DVI, bool ReuseFrameSlot) {
2509  Function *F = DVI->getFunction();
2510  IRBuilder<> Builder(F->getContext());
2511  auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
2512  while (isa<IntrinsicInst>(InsertPt))
2513  ++InsertPt;
2514  Builder.SetInsertPoint(&F->getEntryBlock(), InsertPt);
2515  DIExpression *Expr = DVI->getExpression();
2516  // Follow the pointer arithmetic all the way to the incoming
2517  // function argument and convert into a DIExpression.
2518  bool SkipOutermostLoad = !isa<DbgValueInst>(DVI);
2519  Value *Storage = DVI->getVariableLocationOp(0);
2520  Value *OriginalStorage = Storage;
2521  while (auto *Inst = dyn_cast_or_null<Instruction>(Storage)) {
2522  if (auto *LdInst = dyn_cast<LoadInst>(Inst)) {
2523  Storage = LdInst->getOperand(0);
2524  // FIXME: This is a heuristic that works around the fact that
2525  // LLVM IR debug intrinsics cannot yet distinguish between
2526  // memory and value locations: Because a dbg.declare(alloca) is
2527  // implicitly a memory location no DW_OP_deref operation for the
2528  // last direct load from an alloca is necessary. This condition
2529  // effectively drops the *last* DW_OP_deref in the expression.
2530  if (!SkipOutermostLoad)
2531  Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2532  } else if (auto *StInst = dyn_cast<StoreInst>(Inst)) {
2533  Storage = StInst->getOperand(0);
2534  } else {
2536  SmallVector<Value *, 0> AdditionalValues;
2538  *Inst, Expr ? Expr->getNumLocationOperands() : 0, Ops,
2539  AdditionalValues);
2540  if (!Op || !AdditionalValues.empty()) {
2541  // If salvaging failed or salvaging produced more than one location
2542  // operand, give up.
2543  break;
2544  }
2545  Storage = Op;
2546  Expr = DIExpression::appendOpsToArg(Expr, Ops, 0, /*StackValue*/ false);
2547  }
2548  SkipOutermostLoad = false;
2549  }
2550  if (!Storage)
2551  return;
2552 
2553  // Store a pointer to the coroutine frame object in an alloca so it
2554  // is available throughout the function when producing unoptimized
2555  // code. Extending the lifetime this way is correct because the
2556  // variable has been declared by a dbg.declare intrinsic.
2557  //
2558  // Avoid to create the alloca would be eliminated by optimization
2559  // passes and the corresponding dbg.declares would be invalid.
2560  if (!ReuseFrameSlot && !EnableReuseStorageInFrame)
2561  if (auto *Arg = dyn_cast<llvm::Argument>(Storage)) {
2562  auto &Cached = DbgPtrAllocaCache[Storage];
2563  if (!Cached) {
2564  Cached = Builder.CreateAlloca(Storage->getType(), 0, nullptr,
2565  Arg->getName() + ".debug");
2566  Builder.CreateStore(Storage, Cached);
2567  }
2568  Storage = Cached;
2569  // FIXME: LLVM lacks nuanced semantics to differentiate between
2570  // memory and direct locations at the IR level. The backend will
2571  // turn a dbg.declare(alloca, ..., DIExpression()) into a memory
2572  // location. Thus, if there are deref and offset operations in the
2573  // expression, we need to add a DW_OP_deref at the *start* of the
2574  // expression to first load the contents of the alloca before
2575  // adjusting it with the expression.
2576  if (Expr && Expr->isComplex())
2577  Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2578  }
2579 
2580  DVI->replaceVariableLocationOp(OriginalStorage, Storage);
2581  DVI->setExpression(Expr);
2582  /// It makes no sense to move the dbg.value intrinsic.
2583  if (!isa<DbgValueInst>(DVI)) {
2584  if (auto *InsertPt = dyn_cast<Instruction>(Storage))
2585  DVI->moveAfter(InsertPt);
2586  else if (isa<Argument>(Storage))
2587  DVI->moveAfter(F->getEntryBlock().getFirstNonPHI());
2588  }
2589 }
2590 
2592  // Don't eliminate swifterror in async functions that won't be split.
2593  if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2595 
2596  if (Shape.ABI == coro::ABI::Switch &&
2599  }
2600 
2601  // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
2602  // intrinsics are in their own blocks to simplify the logic of building up
2603  // SuspendCrossing data.
2604  for (auto *CSI : Shape.CoroSuspends) {
2605  if (auto *Save = CSI->getCoroSave())
2606  splitAround(Save, "CoroSave");
2607  splitAround(CSI, "CoroSuspend");
2608  }
2609 
2610  // Put CoroEnds into their own blocks.
2611  for (AnyCoroEndInst *CE : Shape.CoroEnds) {
2612  splitAround(CE, "CoroEnd");
2613 
2614  // Emit the musttail call function in a new block before the CoroEnd.
2615  // We do this here so that the right suspend crossing info is computed for
2616  // the uses of the musttail call function call. (Arguments to the coro.end
2617  // instructions would be ignored)
2618  if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(CE)) {
2619  auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
2620  if (!MustTailCallFn)
2621  continue;
2622  IRBuilder<> Builder(AsyncEnd);
2623  SmallVector<Value *, 8> Args(AsyncEnd->args());
2625  auto *Call = createMustTailCall(AsyncEnd->getDebugLoc(), MustTailCallFn,
2626  Arguments, Builder);
2627  splitAround(Call, "MustTailCall.Before.CoroEnd");
2628  }
2629  }
2630 
2631  // Later code makes structural assumptions about single predecessors phis e.g
2632  // that they are not live accross a suspend point.
2634 
2635  // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
2636  // never has its definition separated from the PHI by the suspend point.
2637  rewritePHIs(F);
2638 
2639  // Build suspend crossing info.
2640  SuspendCrossingInfo Checker(F, Shape);
2641 
2642  IRBuilder<> Builder(F.getContext());
2643  FrameDataInfo FrameData;
2645  SmallVector<Instruction*, 4> DeadInstructions;
2646 
2647  {
2648  SpillInfo Spills;
2649  for (int Repeat = 0; Repeat < 4; ++Repeat) {
2650  // See if there are materializable instructions across suspend points.
2651  for (Instruction &I : instructions(F))
2652  if (materializable(I)) {
2653  for (User *U : I.users())
2654  if (Checker.isDefinitionAcrossSuspend(I, U))
2655  Spills[&I].push_back(cast<Instruction>(U));
2656 
2657  // Manually add dbg.value metadata uses of I.
2659  findDbgValues(DVIs, &I);
2660  for (auto *DVI : DVIs)
2661  if (Checker.isDefinitionAcrossSuspend(I, DVI))
2662  Spills[&I].push_back(DVI);
2663  }
2664 
2665  if (Spills.empty())
2666  break;
2667 
2668  // Rewrite materializable instructions to be materialized at the use
2669  // point.
2670  LLVM_DEBUG(dumpSpills("Materializations", Spills));
2672  Spills.clear();
2673  }
2674  }
2675 
2676  sinkLifetimeStartMarkers(F, Shape, Checker);
2677  if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2678  collectFrameAllocas(F, Shape, Checker, FrameData.Allocas);
2679  LLVM_DEBUG(dumpAllocas(FrameData.Allocas));
2680 
2681  // Collect the spills for arguments and other not-materializable values.
2682  for (Argument &A : F.args())
2683  for (User *U : A.users())
2684  if (Checker.isDefinitionAcrossSuspend(A, U))
2685  FrameData.Spills[&A].push_back(cast<Instruction>(U));
2686 
2687  for (Instruction &I : instructions(F)) {
2688  // Values returned from coroutine structure intrinsics should not be part
2689  // of the Coroutine Frame.
2691  continue;
2692 
2693  // The Coroutine Promise always included into coroutine frame, no need to
2694  // check for suspend crossing.
2695  if (Shape.ABI == coro::ABI::Switch &&
2697  continue;
2698 
2699  // Handle alloca.alloc specially here.
2700  if (auto AI = dyn_cast<CoroAllocaAllocInst>(&I)) {
2701  // Check whether the alloca's lifetime is bounded by suspend points.
2702  if (isLocalAlloca(AI)) {
2703  LocalAllocas.push_back(AI);
2704  continue;
2705  }
2706 
2707  // If not, do a quick rewrite of the alloca and then add spills of
2708  // the rewritten value. The rewrite doesn't invalidate anything in
2709  // Spills because the other alloca intrinsics have no other operands
2710  // besides AI, and it doesn't invalidate the iteration because we delay
2711  // erasing AI.
2712  auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInstructions);
2713 
2714  for (User *U : Alloc->users()) {
2715  if (Checker.isDefinitionAcrossSuspend(*Alloc, U))
2716  FrameData.Spills[Alloc].push_back(cast<Instruction>(U));
2717  }
2718  continue;
2719  }
2720 
2721  // Ignore alloca.get; we process this as part of coro.alloca.alloc.
2722  if (isa<CoroAllocaGetInst>(I))
2723  continue;
2724 
2725  if (isa<AllocaInst>(I))
2726  continue;
2727 
2728  for (User *U : I.users())
2729  if (Checker.isDefinitionAcrossSuspend(I, U)) {
2730  // We cannot spill a token.
2731  if (I.getType()->isTokenTy())
2733  "token definition is separated from the use by a suspend point");
2734  FrameData.Spills[&I].push_back(cast<Instruction>(U));
2735  }
2736  }
2737 
2738  // We don't want the layout of coroutine frame to be affected
2739  // by debug information. So we only choose to salvage DbgValueInst for
2740  // whose value is already in the frame.
2741  // We would handle the dbg.values for allocas specially
2742  for (auto &Iter : FrameData.Spills) {
2743  auto *V = Iter.first;
2745  findDbgValues(DVIs, V);
2746  llvm::for_each(DVIs, [&](DbgValueInst *DVI) {
2747  if (Checker.isDefinitionAcrossSuspend(*V, DVI))
2748  FrameData.Spills[V].push_back(DVI);
2749  });
2750  }
2751 
2752  LLVM_DEBUG(dumpSpills("Spills", FrameData.Spills));
2753  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
2754  Shape.ABI == coro::ABI::Async)
2756  Shape.FrameTy = buildFrameType(F, Shape, FrameData);
2758  // For now, this works for C++ programs only.
2759  buildFrameDebugInfo(F, Shape, FrameData);
2760  insertSpills(FrameData, Shape);
2761  lowerLocalAllocas(LocalAllocas, DeadInstructions);
2762 
2763  for (auto I : DeadInstructions)
2764  I->eraseFromParent();
2765 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
PtrUseVisitor.h
alignTo
static int alignTo(int Num, int PowOf2)
Definition: AArch64LoadStoreOptimizer.cpp:1218
llvm::detail::PtrUseVisitorBase::enqueueUsers
void enqueueUsers(Instruction &I)
Enqueue the users of this instruction in the visit worklist.
Definition: PtrUseVisitor.cpp:21
splitBlockIfNotFirst
static BasicBlock * splitBlockIfNotFirst(Instruction *I, const Twine &Name)
Definition: CoroFrame.cpp:2018
llvm::DbgVariableIntrinsic::getExpression
DIExpression * getExpression() const
Definition: IntrinsicInst.h:257
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::coro::createMustTailCall
CallInst * createMustTailCall(DebugLoc Loc, Function *MustTailCallFn, ArrayRef< Value * > Arguments, IRBuilder<> &)
Definition: CoroSplit.cpp:1545
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:263
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm::coro::Shape::AsyncLoweringStorage::FrameOffset
uint64_t FrameOffset
Definition: CoroInternal.h:156
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
MathExtras.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::DIType
Base class for types.
Definition: DebugInfoMetadata.h:662
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DIExpression::getNumLocationOperands
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
Definition: DebugInfoMetadata.cpp:1529
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1565
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
llvm::OptimizedStructLayoutField::Offset
uint64_t Offset
The offset of this field in the final layout.
Definition: OptimizedStructLayout.h:59
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1379
eliminateSwiftError
static void eliminateSwiftError(Function &F, coro::Shape &Shape)
Eliminate all problematic uses of swifterror arguments and allocas from the function.
Definition: CoroFrame.cpp:2318
llvm::coro::Shape::SwitchLowering
SwitchLoweringStorage SwitchLowering
Definition: CoroInternal.h:164
llvm::DIType::getSizeInBits
uint64_t getSizeInBits() const
Definition: DebugInfoMetadata.h:701
llvm::AllocaInst::getAlign
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
Definition: Instructions.h:120
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:217
llvm::DIBuilder
Definition: DIBuilder.h:41
dumpAllocas
static void dumpAllocas(const SmallVectorImpl< AllocaInfo > &Allocas)
Definition: CoroFrame.cpp:401
llvm::coro::Shape::FrameTy
StructType * FrameTy
Definition: CoroInternal.h:122
InstIterator.h
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:426
splitAround
static void splitAround(Instruction *I, const Twine &Name)
Definition: CoroFrame.cpp:2031
llvm::Function
Definition: Function.h:62
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1661
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:52
emitSetSwiftErrorValue
static Value * emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V, coro::Shape &Shape)
Set the given value as the current swifterror value.
Definition: CoroFrame.cpp:2202
llvm::DataLayout::getTypeSizeInBits
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:664
llvm::StructType::setBody
void setBody(ArrayRef< Type * > Elements, bool isPacked=false)
Specify a body for an opaque identified type.
Definition: Type.cpp:447
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5198
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2885
llvm::InstVisitor< DerivedT >::visitIntrinsicInst
void visitIntrinsicInst(IntrinsicInst &I)
Definition: InstVisitor.h:221
llvm::IRBuilder<>
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:102
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::DbgVariableIntrinsic::replaceVariableLocationOp
void replaceVariableLocationOp(Value *OldValue, Value *NewValue)
Definition: IntrinsicInst.cpp:82
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
rewritePHIsForCleanupPad
static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB, CleanupPadInst *CleanupPad)
Definition: CoroFrame.cpp:1790
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::DataLayout::getStructLayout
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:676
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
llvm::CoroAllocaAllocInst
This represents the llvm.coro.alloca.alloc instruction.
Definition: CoroInstr.h:658
llvm::DIType::getAlignInBits
uint32_t getAlignInBits() const
Definition: DebugInfoMetadata.h:702
llvm::InstVisitor< DerivedT >::visitBitCastInst
void visitBitCastInst(BitCastInst &I)
Definition: InstVisitor.h:188
SmallVectorThreshold
@ SmallVectorThreshold
Definition: CoroFrame.cpp:52
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
eliminateSwiftErrorArgument
static void eliminateSwiftErrorArgument(Function &F, Argument &Arg, coro::Shape &Shape, SmallVectorImpl< AllocaInst * > &AllocasToPromote)
"Eliminate" a swifterror argument by reducing it to the alloca case and then loading and storing in t...
Definition: CoroFrame.cpp:2281
llvm::coro::Shape::ABI
coro::ABI ABI
Definition: CoroInternal.h:120
BlockData::BlockData
BlockData()
Definition: SIModeRegister.cpp:104
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:298
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:385
llvm::TinyPtrVector::front
EltTy front() const
Definition: TinyPtrVector.h:230
llvm::DbgVariableIntrinsic::getVariable
DILocalVariable * getVariable() const
Definition: IntrinsicInst.h:253
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:874
collectFrameAllocas
static void collectFrameAllocas(Function &F, coro::Shape &Shape, const SuspendCrossingInfo &Checker, SmallVectorImpl< AllocaInfo > &Allocas)
Definition: CoroFrame.cpp:2483
llvm::Optional
Definition: APInt.h:33
llvm::coro::Shape::getPromiseAlloca
AllocaInst * getPromiseAlloca() const
Definition: CoroInternal.h:258
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet< Instruction *, 4 >
solveTypeName
static StringRef solveTypeName(Type *Ty)
Create name for Type.
Definition: CoroFrame.cpp:795
llvm::PromoteMemToReg
void PromoteMemToReg(ArrayRef< AllocaInst * > Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)
Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...
Definition: PromoteMemoryToRegister.cpp:1014
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::DIBuilder::createMemberType
DIDerivedType * createMemberType(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNo, uint64_t SizeInBits, uint32_t AlignInBits, uint64_t OffsetInBits, DINode::DIFlags Flags, DIType *Ty, DINodeArray Annotations=nullptr)
Create debugging information entry for a member.
Definition: DIBuilder.cpp:354
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2586
willLeaveFunctionImmediatelyAfter
static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB, unsigned depth=3)
After we split the coroutine, will the given basic block be along an obvious exit path for the resump...
Definition: CoroFrame.cpp:2081
llvm::coro::buildCoroutineFrame
void buildCoroutineFrame(Function &F, Shape &Shape)
Definition: CoroFrame.cpp:2591
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::Type::isFloatingPointTy
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
llvm::coro::Shape::SwitchLoweringStorage::PromiseAlloca
AllocaInst * PromiseAlloca
Definition: CoroInternal.h:133
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:299
llvm::getOffset
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
Definition: RuntimeDyld.cpp:170
llvm::DbgVariableIntrinsic::getVariableLocationOp
Value * getVariableLocationOp(unsigned OpIdx) const
Definition: IntrinsicInst.cpp:60
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::coro::Shape::AsyncLoweringStorage::ContextHeaderSize
uint64_t ContextHeaderSize
Definition: CoroInternal.h:154
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
instructions
print must be executed print the must be executed context for all instructions
Definition: MustExecute.cpp:355
llvm::coro::Shape::emitDealloc
void emitDealloc(IRBuilder<> &Builder, Value *Ptr, CallGraph *CG) const
Deallocate memory according to the rules of the active lowering.
Definition: Coroutines.cpp:552
llvm::DIBuilder::createAutoVariable
DILocalVariable * createAutoVariable(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNo, DIType *Ty, bool AlwaysPreserve=false, DINode::DIFlags Flags=DINode::FlagZero, uint32_t AlignInBits=0)
Create a new descriptor for an auto variable.
Definition: DIBuilder.cpp:770
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
CommandLine.h
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:90
llvm::coro::Shape::AllocaSpillBlock
BasicBlock * AllocaSpillBlock
Definition: CoroInternal.h:126
cleanupSinglePredPHIs
static void cleanupSinglePredPHIs(Function &F)
Definition: CoroFrame.cpp:1865
llvm::coro::Shape::RetconLoweringStorage::IsFrameInlineInStorage
bool IsFrameInlineInStorage
Definition: CoroInternal.h:146
rewriteMaterializableInstructions
static void rewriteMaterializableInstructions(IRBuilder<> &IRB, const SpillInfo &Spills)
Definition: CoroFrame.cpp:1980
StackLifetime.h
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5238
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
emitGetSwiftErrorValue
static Value * emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy, coro::Shape &Shape)
Get the current swifterror value.
Definition: CoroFrame.cpp:2187
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
llvm::DbgValueInst
This represents the llvm.dbg.value instruction.
Definition: IntrinsicInst.h:347
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:113
SmallString.h
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3097
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PtrUseVisitor::visitGetElementPtrInst
void visitGetElementPtrInst(GetElementPtrInst &GEPI)
Definition: PtrUseVisitor.h:266
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
localAllocaNeedsStackSave
static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI)
Definition: CoroFrame.cpp:2100
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::BitVector::size
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:151
llvm::Type::getStructName
StringRef getStructName() const
Definition: DerivedTypes.h:344
lowerNonLocalAlloca
static Instruction * lowerNonLocalAlloca(CoroAllocaAllocInst *AI, coro::Shape &Shape, SmallVectorImpl< Instruction * > &DeadInsts)
Turn the given coro.alloca.alloc call into a dynamic allocation.
Definition: CoroFrame.cpp:2162
llvm::InstVisitor< DerivedT >::visitGetElementPtrInst
void visitGetElementPtrInst(GetElementPtrInst &I)
Definition: InstVisitor.h:175
llvm::CoroSuspendInst
This represents the llvm.coro.suspend instruction.
Definition: CoroInstr.h:493
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::StructLayout::getElementOffsetInBits
uint64_t getElementOffsetInBits(unsigned Idx) const
Definition: DataLayout.h:648
llvm::DIType::getName
StringRef getName() const
Definition: DebugInfoMetadata.h:708
llvm::BasicBlock::getFirstInsertionPt
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:253
llvm::coro::Shape::CoroSuspends
SmallVector< AnyCoroSuspendInst *, 4 > CoroSuspends
Definition: CoroInternal.h:102
FramePtr
static const unsigned FramePtr
Definition: XCoreFrameLowering.cpp:34
eliminateSwiftErrorAlloca
static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca, coro::Shape &Shape)
Eliminate a formerly-swifterror alloca by inserting the get/set intrinsics and attempting to MemToReg...
Definition: CoroFrame.cpp:2250
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::DbgVariableIntrinsic::setExpression
void setExpression(DIExpression *NewExpr)
Definition: IntrinsicInst.h:217
llvm::coro::Shape::CoroEnds
SmallVector< AnyCoroEndInst *, 4 > CoroEnds
Definition: CoroInternal.h:100
llvm::Instruction
Definition: Instruction.h:45
llvm::FindDbgDeclareUses
TinyPtrVector< DbgDeclareInst * > FindDbgDeclareUses(Value *V)
Like FindDbgAddrUses, but only returns dbg.declare intrinsics, not dbg.addr.
Definition: DebugInfo.cpp:68
llvm::AllocaInst::getArraySize
const Value * getArraySize() const
Get the number of elements allocated.
Definition: Instructions.h:100
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
BitVector.h
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
sinkSpillUsesAfterCoroBegin
static void sinkSpillUsesAfterCoroBegin(Function &F, const FrameDataInfo &FrameData, CoroBeginInst *CoroBegin)
retcon and retcon.once conventions assume that all spill uses can be sunk after the coro....
Definition: CoroFrame.cpp:2351
llvm::InstVisitor< DerivedT >::visitPHINode
void visitPHINode(PHINode &I)
Definition: InstVisitor.h:176
llvm::BitVector
Definition: BitVector.h:74
llvm::Instruction::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: Instruction.cpp:74
llvm::CoroIdInst::clearPromise
void clearPromise()
Definition: CoroInstr.h:124
Align
uint64_t Align
Definition: ELFObjHandler.cpp:83
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::ehAwareSplitEdge
BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad=nullptr, PHINode *LandingPadReplacement=nullptr, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
Split the edge connect the specficed blocks in the case that Succ is an Exception Handling Block.
Definition: BasicBlockUtils.cpp:564
llvm::DIBuilder::replaceArrays
void replaceArrays(DICompositeType *&T, DINodeArray Elements, DINodeArray TParams=DINodeArray())
Replace arrays on a composite type.
Definition: DIBuilder.cpp:1078
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:245
sinkLifetimeStartMarkers
static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape, SuspendCrossingInfo &Checker)
For each local variable that all of its user are only used inside one of suspended region,...
Definition: CoroFrame.cpp:2398
llvm::None
const NoneType None
Definition: None.h:23
llvm::coro::Shape::FrameAlign
Align FrameAlign
Definition: CoroInternal.h:123
llvm::SmallString< 16 >
CFG.h
llvm::AllocaInst::isSwiftError
bool isSwiftError() const
Return true if this alloca is used as a swifterror argument to a call.
Definition: Instructions.h:148
llvm::DILocalVariable::getScope
DILocalScope * getScope() const
Get the local scope for this variable.
Definition: DebugInfoMetadata.h:3153
llvm::coro::Shape
Definition: CoroInternal.h:98
llvm::coro::Shape::AsyncLowering
AsyncLoweringStorage AsyncLowering
Definition: CoroInternal.h:166
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
llvm::PtrUseVisitor::visitMemIntrinsic
void visitMemIntrinsic(MemIntrinsic &I)
Definition: PtrUseVisitor.h:283
isCoroutineStructureIntrinsic
static bool isCoroutineStructureIntrinsic(Instruction &I)
Definition: CoroFrame.cpp:1973
createFramePtr
static void createFramePtr(coro::Shape &Shape)
Definition: CoroFrame.cpp:1489
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
CoroInternal.h
llvm::OptimizedStructLayoutField::Alignment
Align Alignment
The required alignment of this field.
Definition: OptimizedStructLayout.h:73
llvm::Use::set
void set(Value *Val)
Definition: Value.h:863
llvm::cl::opt< bool >
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:148
llvm::coro::Shape::SwiftErrorOps
SmallVector< CallInst *, 2 > SwiftErrorOps
Definition: CoroInternal.h:103
llvm::CleanupPadInst
Definition: Instructions.h:4432
llvm::InstVisitor< DerivedT >::visitSelectInst
void visitSelectInst(SelectInst &I)
Definition: InstVisitor.h:190
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::ArrayRef::drop_front
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:204
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
dumpSpills
static void dumpSpills(StringRef Title, const SpillInfo &Spills)
Definition: CoroFrame.cpp:391
buildFrameType
static StructType * buildFrameType(Function &F, coro::Shape &Shape, FrameDataInfo &FrameData)
Definition: CoroFrame.cpp:1095
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::SwitchInst::setDefaultDest
void setDefaultDest(BasicBlock *DefaultCase)
Definition: Instructions.h:3424
uint64_t
llvm::Optional::reset
void reset()
Definition: Optional.h:278
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1544
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:578
llvm::DbgDeclareInst
This represents the llvm.dbg.declare instruction.
Definition: IntrinsicInst.h:308
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::Instruction::user_back
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:91
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::DIBuilder::createExpression
DIExpression * createExpression(ArrayRef< uint64_t > Addr=None)
Create a new descriptor for the specified variable which has a complex address expression for its add...
Definition: DIBuilder.cpp:810
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::coro::Shape::SwitchLoweringStorage::IndexOffset
unsigned IndexOffset
Definition: CoroInternal.h:137
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::coro::Shape::SwitchLoweringStorage::IndexAlign
unsigned IndexAlign
Definition: CoroInternal.h:136
llvm::Instruction::moveAfter
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:101
PromoteMemToReg.h
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DebugLoc::get
DILocation * get() const
Get the underlying DILocation.
Definition: DebugLoc.cpp:21
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
buildFrameDebugInfo
static void buildFrameDebugInfo(Function &F, coro::Shape &Shape, FrameDataInfo &FrameData)
Build artificial debug info for C++ coroutine frames to allow users to inspect the contents of the fr...
Definition: CoroFrame.cpp:921
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
DIBuilder.h
llvm::coro::Shape::ReuseFrameSlot
bool ReuseFrameSlot
This would only be true if optimization are enabled.
Definition: CoroInternal.h:129
llvm::StackLifetime
Compute live ranges of allocas.
Definition: StackLifetime.h:38
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
getAlign
static Align getAlign(GlobalVariable *GV)
Definition: ConstantMerge.cpp:87
llvm::findDbgValues
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:76
llvm::updatePhiNodes
void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
Definition: BasicBlockUtils.cpp:542
llvm::InstVisitor< DerivedT >::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:88
llvm::Log2_64_Ceil
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:615
llvm::CallBase::doesNotCapture
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: InstrTypes.h:1651
llvm::coro::Shape::FramePtr
Instruction * FramePtr
Definition: CoroInternal.h:125
materializable
static bool materializable(Instruction &V)
Definition: CoroFrame.cpp:1966
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
OptimizedStructLayout.h
IRBuilder.h
isSuspendReachableFrom
static bool isSuspendReachableFrom(BasicBlock *From, VisitedBlocksSet &VisitedOrFreeBBs)
Does control flow starting at the given block ever reach a suspend instruction before reaching a bloc...
Definition: CoroFrame.cpp:2044
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
solveDIType
static DIType * solveDIType(DIBuilder &Builder, Type *Ty, const DataLayout &Layout, DIScope *Scope, unsigned LineNum, DenseMap< Type *, DIType * > &DITypeCache)
Definition: CoroFrame.cpp:843
llvm::DataLayout::getPrefTypeAlignment
uint64_t getPrefTypeAlignment(Type *Ty) const
Returns the preferred stack/global alignment for the specified type.
Definition: DataLayout.cpp:831
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::InstVisitor< DerivedT >::visitAddrSpaceCastInst
void visitAddrSpaceCastInst(AddrSpaceCastInst &I)
Definition: InstVisitor.h:189
llvm::AllocaInst::getAlignment
uint64_t getAlignment() const
Definition: Instructions.h:129
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:360
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
emitSetAndGetSwiftErrorValueAround
static Value * emitSetAndGetSwiftErrorValueAround(Instruction *Call, AllocaInst *Alloca, coro::Shape &Shape)
Set the swifterror value from the given alloca before a call, then put in back in the alloca afterwar...
Definition: CoroFrame.cpp:2220
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::coro::Shape::AsyncLoweringStorage::ContextSize
uint64_t ContextSize
Definition: CoroInternal.h:157
isAligned
static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment, const DataLayout &DL)
Definition: Loads.cpp:34
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1532
llvm::dwarf::SourceLanguage
SourceLanguage
Definition: Dwarf.h:200
llvm::DICompositeType
Composite types.
Definition: DebugInfoMetadata.h:1060
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:850
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::raw_svector_ostream::str
StringRef str() const
Return a StringRef for the vector contents.
Definition: raw_ostream.h:683
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::pred_size
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:124
llvm::DIVariable::getLine
unsigned getLine() const
Definition: DebugInfoMetadata.h:2530
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
A
* A
Definition: README_ALTIVEC.txt:89
llvm::PtrUseVisitor
A base class for visitors over the uses of a pointer value.
Definition: PtrUseVisitor.h:205
uint32_t
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:990
llvm::AllocaInst::isArrayAllocation
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
Definition: Instructions.cpp:1388
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:368
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
movePHIValuesToInsertedBlock
static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB, BasicBlock *InsertedBB, BasicBlock *PredBB, PHINode *UntilPHI=nullptr)
Definition: CoroFrame.cpp:1772
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::PtrUseVisitor::visitCallBase
void visitCallBase(CallBase &CB)
Definition: PtrUseVisitor.h:297
llvm::coro::Shape::CoroBegin
CoroBeginInst * CoroBegin
Definition: CoroInternal.h:99
insertSpills
static Instruction * insertSpills(const FrameDataInfo &FrameData, coro::Shape &Shape)
Definition: CoroFrame.cpp:1520
llvm::OptimizedStructLayoutField::Size
uint64_t Size
The required size of this field in bytes.
Definition: OptimizedStructLayout.h:63
llvm::AnyCoroEndInst
Definition: CoroInstr.h:602
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::Type::getContext
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:127
llvm::detail::PtrUseVisitorBase::Offset
APInt Offset
The constant offset of the use if that is known.
Definition: PtrUseVisitor.h:156
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::BasicBlock::getTerminator
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:152
llvm::coro::Shape::RetconLowering
RetconLoweringStorage RetconLowering
Definition: CoroInternal.h:165
llvm::performOptimizedStructLayout
std::pair< uint64_t, Align > performOptimizedStructLayout(MutableArrayRef< OptimizedStructLayoutField > Fields)
Compute a layout for a struct containing the given fields, making a best-effort attempt to minimize t...
Definition: OptimizedStructLayout.cpp:42
llvm::StructType::getNumElements
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:327
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:687
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1578
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
llvm::codeview::ClassOptions::Packed
@ Packed
llvm::DIBuilder::createStructType
DICompositeType * createStructType(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNumber, uint64_t SizeInBits, uint32_t AlignInBits, DINode::DIFlags Flags, DIType *DerivedFrom, DINodeArray Elements, unsigned RunTimeLang=0, DIType *VTableHolder=nullptr, StringRef UniqueIdentifier="")
Create debugging information entry for a struct.
Definition: DIBuilder.cpp:482
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:493
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::pdb::PDB_SymType::Label
@ Label
splitBeforeCatchSwitch
static Instruction * splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch)
Definition: CoroFrame.cpp:1477
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::setUnwindEdgeTo
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
Definition: BasicBlockUtils.cpp:531
llvm::Type::isFloatTy
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
Definition: Type.h:147
llvm::DIScope
Base class for scope-like contexts.
Definition: DebugInfoMetadata.h:476
llvm::PtrUseVisitor::visitAddrSpaceCastInst
void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)
Definition: PtrUseVisitor.h:258
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1326
llvm::salvageDebugInfoImpl
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1898
circular_raw_ostream.h
llvm::DIExpression::isComplex
bool isComplex() const
Return whether the location is computed on the expression stack, meaning it cannot be a simple regist...
Definition: DebugInfoMetadata.cpp:1197
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
Arguments
AMDGPU Lower Kernel Arguments
Definition: AMDGPULowerKernelArguments.cpp:243
llvm::salvageDebugInfo
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1726
llvm::DIBuilder::getOrCreateArray
DINodeArray getOrCreateArray(ArrayRef< Metadata * > Elements)
Get a DINodeArray, create one if required.
Definition: DIBuilder.cpp:650
llvm::Type::getPointerTo
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:776
llvm::Type::isDoubleTy
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
Definition: Type.h:150
llvm::coro::Shape::emitAlloc
Value * emitAlloc(IRBuilder<> &Builder, Value *Size, CallGraph *CG) const
Allocate memory according to the rules of the active lowering.
Definition: Coroutines.cpp:529
llvm::coro::Shape::getSwitchCoroId
CoroIdInst * getSwitchCoroId() const
Definition: CoroInternal.h:169
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
rewritePHIs
static void rewritePHIs(BasicBlock &BB)
Definition: CoroFrame.cpp:1882
llvm::dwarf::isCPlusPlus
bool isCPlusPlus(SourceLanguage S)
Definition: Dwarf.h:208
llvm::CoroAllocaAllocInst::getSize
Value * getSize() const
Definition: CoroInstr.h:661
llvm::SmallString::str
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:259
llvm::CatchSwitchInst::getParentPad
Value * getParentPad() const
Definition: Instructions.h:4316
EnableReuseStorageInFrame
static cl::opt< bool > EnableReuseStorageInFrame("reuse-storage-in-coroutine-frame", cl::Hidden, cl::desc("Enable the optimization which would reuse the storage in the coroutine \ frame for allocas whose liferanges are not overlapped, for testing purposes"), llvm::cl::init(false))
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
isLifetimeStart
static bool isLifetimeStart(const Instruction *Inst)
Definition: GVN.cpp:943
lowerLocalAllocas
static void lowerLocalAllocas(ArrayRef< CoroAllocaAllocInst * > LocalAllocas, SmallVectorImpl< Instruction * > &DeadInsts)
Turn each of the given local allocas into a normal (dynamic) alloca instruction.
Definition: CoroFrame.cpp:2118
isSuspendBlock
static bool isSuspendBlock(BasicBlock *BB)
Definition: CoroFrame.cpp:2036
llvm::AllocaInst::setAlignment
void setAlignment(Align Align)
Definition: Instructions.h:124
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::end
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
llvm::TinyPtrVector::empty
bool empty() const
Definition: TinyPtrVector.h:163
llvm::coro::Shape::getRetconCoroId
AnyCoroIdRetconInst * getRetconCoroId() const
Definition: CoroInternal.h:174
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:211
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
isLocalAlloca
static bool isLocalAlloca(CoroAllocaAllocInst *AI)
Is the given alloca "local", i.e.
Definition: CoroFrame.cpp:2067
Dominators.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1328
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::coro::Shape::FrameSize
uint64_t FrameSize
Definition: CoroInternal.h:124
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:63
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::raw_svector_ostream
A raw_ostream that writes to an SmallVector or SmallString.
Definition: raw_ostream.h:658
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:104
llvm::PHINode
Definition: Instructions.h:2633
llvm::CoroBeginInst
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:420
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1820
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::StructType::getElementType
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:328
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::PtrUseVisitor::visitStoreInst
void visitStoreInst(StoreInst &SI)
Definition: PtrUseVisitor.h:249
llvm::Twine::toStringRef
StringRef toStringRef(SmallVectorImpl< char > &Out) const
This returns the twine as a single StringRef if it can be represented as such.
Definition: Twine.h:477
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::DILocalScope
A scope for locals.
Definition: DebugInfoMetadata.h:1550
llvm::DIBuilder::createBasicType
DIBasicType * createBasicType(StringRef Name, uint64_t SizeInBits, unsigned Encoding, DINode::DIFlags Flags=DINode::FlagZero)
Create debugging information entry for a basic type.
Definition: DIBuilder.cpp:271
llvm::PtrUseVisitor::visitIntrinsicInst
void visitIntrinsicInst(IntrinsicInst &II)
Definition: PtrUseVisitor.h:284
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::OptimizedStructLayoutField
A field in a structure.
Definition: OptimizedStructLayout.h:45
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:382
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
VisitedBlocksSet
SmallPtrSet< BasicBlock *, 8 > VisitedBlocksSet
Definition: CoroFrame.cpp:2040
llvm::cl::desc
Definition: CommandLine.h:412
cacheDIVar
static void cacheDIVar(FrameDataInfo &FrameData, DenseMap< Value *, DILocalVariable * > &DIVarCache)
Definition: CoroFrame.cpp:778
llvm::coro::Shape::AsyncLoweringStorage::getContextAlignment
Align getContextAlignment() const
Definition: CoroInternal.h:160
raw_ostream.h
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:231
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
BasicBlockUtils.h
llvm::PtrUseVisitor::visitBitCastInst
void visitBitCastInst(BitCastInst &BC)
Definition: PtrUseVisitor.h:254
llvm::pdb::PDB_SymType::Block
@ Block
llvm::CatchSwitchInst
Definition: Instructions.h:4254
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::coro::Shape::SwitchLoweringStorage::IndexField
unsigned IndexField
Definition: CoroInternal.h:135
llvm::AllocaInst::setSwiftError
void setSwiftError(bool V)
Specify whether this alloca is used to represent a swifterror.
Definition: Instructions.h:150
llvm::codeview::DebugSubsectionKind::FrameData
@ FrameData
llvm::isAllocaPromotable
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
Definition: PromoteMemoryToRegister.cpp:64
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
llvm::DIScope::getFile
DIFile * getFile() const
Definition: DebugInfoMetadata.h:484
llvm::DIFile
File.
Definition: DebugInfoMetadata.h:530
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::SmallPtrSetImpl::insert
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:364