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, DataLayout const &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  DIScope *Scope, unsigned LineNum,
845  DenseMap<Type *, DIType *> &DITypeCache) {
846  if (DIType *DT = DITypeCache.lookup(Ty))
847  return DT;
848 
850 
851  DIType *RetType = nullptr;
852 
853  if (Ty->isIntegerTy()) {
854  auto BitWidth = cast<IntegerType>(Ty)->getBitWidth();
855  RetType = Builder.createBasicType(Name, BitWidth, dwarf::DW_ATE_signed,
856  llvm::DINode::FlagArtificial);
857  } else if (Ty->isFloatingPointTy()) {
858  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
859  dwarf::DW_ATE_float,
860  llvm::DINode::FlagArtificial);
861  } else if (Ty->isPointerTy()) {
862  // Construct BasicType instead of PointerType to avoid infinite
863  // search problem.
864  // For example, we would be in trouble if we traverse recursively:
865  //
866  // struct Node {
867  // Node* ptr;
868  // };
869  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
870  dwarf::DW_ATE_address,
871  llvm::DINode::FlagArtificial);
872  } else if (Ty->isStructTy()) {
873  auto *DIStruct = Builder.createStructType(
874  Scope, Name, Scope->getFile(), LineNum, Layout.getTypeSizeInBits(Ty),
875  Layout.getPrefTypeAlignment(Ty), llvm::DINode::FlagArtificial, nullptr,
876  llvm::DINodeArray());
877 
878  auto *StructTy = cast<StructType>(Ty);
880  for (unsigned I = 0; I < StructTy->getNumElements(); I++) {
881  DIType *DITy = solveDIType(Builder, StructTy->getElementType(I), Layout,
882  Scope, LineNum, DITypeCache);
883  assert(DITy);
884  Elements.push_back(Builder.createMemberType(
885  Scope, DITy->getName(), Scope->getFile(), LineNum,
886  DITy->getSizeInBits(), DITy->getAlignInBits(),
887  Layout.getStructLayout(StructTy)->getElementOffsetInBits(I),
888  llvm::DINode::FlagArtificial, DITy));
889  }
890 
891  Builder.replaceArrays(DIStruct, Builder.getOrCreateArray(Elements));
892 
893  RetType = DIStruct;
894  } else {
895  LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n";);
896  SmallString<32> Buffer;
897  raw_svector_ostream OS(Buffer);
898  OS << Name.str() << "_" << Layout.getTypeSizeInBits(Ty);
899  RetType = Builder.createBasicType(OS.str(), Layout.getTypeSizeInBits(Ty),
900  dwarf::DW_ATE_address,
901  llvm::DINode::FlagArtificial);
902  }
903 
904  DITypeCache.insert({Ty, RetType});
905  return RetType;
906 }
907 
908 /// Build artificial debug info for C++ coroutine frames to allow users to
909 /// inspect the contents of the frame directly
910 ///
911 /// Create Debug information for coroutine frame with debug name "__coro_frame".
912 /// The debug information for the fields of coroutine frame is constructed from
913 /// the following way:
914 /// 1. For all the value in the Frame, we search the use of dbg.declare to find
915 /// the corresponding debug variables for the value. If we can find the
916 /// debug variable, we can get full and accurate debug information.
917 /// 2. If we can't get debug information in step 1 and 2, we could only try to
918 /// build the DIType by Type. We did this in solveDIType. We only handle
919 /// integer, float, double, integer type and struct type for now.
921  FrameDataInfo &FrameData) {
922  DISubprogram *DIS = F.getSubprogram();
923  // If there is no DISubprogram for F, it implies the Function are not compiled
924  // with debug info. So we also don't need to generate debug info for the frame
925  // neither.
926  if (!DIS || !DIS->getUnit() ||
928  (dwarf::SourceLanguage)DIS->getUnit()->getSourceLanguage()))
929  return;
930 
931  assert(Shape.ABI == coro::ABI::Switch &&
932  "We could only build debug infomation for C++ coroutine now.\n");
933 
934  DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);
935 
936  AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
937  assert(PromiseAlloca &&
938  "Coroutine with switch ABI should own Promise alloca");
939 
941  if (DIs.empty())
942  return;
943 
944  DbgDeclareInst *PromiseDDI = DIs.front();
945  DILocalVariable *PromiseDIVariable = PromiseDDI->getVariable();
946  DILocalScope *PromiseDIScope = PromiseDIVariable->getScope();
947  DIFile *DFile = PromiseDIScope->getFile();
948  DILocation *DILoc = PromiseDDI->getDebugLoc().get();
949  unsigned LineNum = PromiseDIVariable->getLine();
950 
951  DICompositeType *FrameDITy = DBuilder.createStructType(
952  DIS, "__coro_frame_ty", DFile, LineNum, Shape.FrameSize * 8,
953  Shape.FrameAlign.value() * 8, llvm::DINode::FlagArtificial, nullptr,
954  llvm::DINodeArray());
955  StructType *FrameTy = Shape.FrameTy;
957  DataLayout Layout = F.getParent()->getDataLayout();
958 
960  cacheDIVar(FrameData, DIVarCache);
961 
962  unsigned ResumeIndex = coro::Shape::SwitchFieldIndex::Resume;
963  unsigned DestroyIndex = coro::Shape::SwitchFieldIndex::Destroy;
964  unsigned IndexIndex = Shape.SwitchLowering.IndexField;
965 
967  NameCache.insert({ResumeIndex, "__resume_fn"});
968  NameCache.insert({DestroyIndex, "__destroy_fn"});
969  NameCache.insert({IndexIndex, "__coro_index"});
970 
971  Type *ResumeFnTy = FrameTy->getElementType(ResumeIndex),
972  *DestroyFnTy = FrameTy->getElementType(DestroyIndex),
973  *IndexTy = FrameTy->getElementType(IndexIndex);
974 
976  TyCache.insert({ResumeIndex,
977  DBuilder.createBasicType("__resume_fn",
978  Layout.getTypeSizeInBits(ResumeFnTy),
979  dwarf::DW_ATE_address)});
980  TyCache.insert(
981  {DestroyIndex, DBuilder.createBasicType(
982  "__destroy_fn", Layout.getTypeSizeInBits(DestroyFnTy),
983  dwarf::DW_ATE_address)});
984 
985  /// FIXME: If we fill the field `SizeInBits` with the actual size of
986  /// __coro_index in bits, then __coro_index wouldn't show in the debugger.
987  TyCache.insert({IndexIndex, DBuilder.createBasicType(
988  "__coro_index",
989  (Layout.getTypeSizeInBits(IndexTy) < 8)
990  ? 8
991  : Layout.getTypeSizeInBits(IndexTy),
992  dwarf::DW_ATE_unsigned_char)});
993 
994  for (auto *V : FrameData.getAllDefs()) {
995  if (DIVarCache.find(V) == DIVarCache.end())
996  continue;
997 
998  auto Index = FrameData.getFieldIndex(V);
999 
1000  NameCache.insert({Index, DIVarCache[V]->getName()});
1001  TyCache.insert({Index, DIVarCache[V]->getType()});
1002  }
1003 
1004  // Cache from index to (Align, Offset Pair)
1006  // The Align and Offset of Resume function and Destroy function are fixed.
1007  OffsetCache.insert({ResumeIndex, {8, 0}});
1008  OffsetCache.insert({DestroyIndex, {8, 8}});
1009  OffsetCache.insert(
1010  {IndexIndex,
1012 
1013  for (auto *V : FrameData.getAllDefs()) {
1014  auto Index = FrameData.getFieldIndex(V);
1015 
1016  OffsetCache.insert(
1017  {Index, {FrameData.getAlign(V), FrameData.getOffset(V)}});
1018  }
1019 
1020  DenseMap<Type *, DIType *> DITypeCache;
1021  // This counter is used to avoid same type names. e.g., there would be
1022  // many i32 and i64 types in one coroutine. And we would use i32_0 and
1023  // i32_1 to avoid the same type. Since it makes no sense the name of the
1024  // fields confilicts with each other.
1025  unsigned UnknownTypeNum = 0;
1026  for (unsigned Index = 0; Index < FrameTy->getNumElements(); Index++) {
1027  if (OffsetCache.find(Index) == OffsetCache.end())
1028  continue;
1029 
1030  std::string Name;
1031  uint64_t SizeInBits;
1032  uint32_t AlignInBits;
1033  uint64_t OffsetInBits;
1034  DIType *DITy = nullptr;
1035 
1036  Type *Ty = FrameTy->getElementType(Index);
1037  assert(Ty->isSized() && "We can't handle type which is not sized.\n");
1038  SizeInBits = Layout.getTypeSizeInBits(Ty).getFixedSize();
1039  AlignInBits = OffsetCache[Index].first * 8;
1040  OffsetInBits = OffsetCache[Index].second * 8;
1041 
1042  if (NameCache.find(Index) != NameCache.end()) {
1043  Name = NameCache[Index].str();
1044  DITy = TyCache[Index];
1045  } else {
1046  DITy = solveDIType(DBuilder, Ty, Layout, FrameDITy, LineNum, DITypeCache);
1047  assert(DITy && "SolveDIType shouldn't return nullptr.\n");
1048  Name = DITy->getName().str();
1049  Name += "_" + std::to_string(UnknownTypeNum);
1050  UnknownTypeNum++;
1051  }
1052 
1053  Elements.push_back(DBuilder.createMemberType(
1054  FrameDITy, Name, DFile, LineNum, SizeInBits, AlignInBits, OffsetInBits,
1055  llvm::DINode::FlagArtificial, DITy));
1056  }
1057 
1058  DBuilder.replaceArrays(FrameDITy, DBuilder.getOrCreateArray(Elements));
1059 
1060  auto *FrameDIVar = DBuilder.createAutoVariable(PromiseDIScope, "__coro_frame",
1061  DFile, LineNum, FrameDITy,
1062  true, DINode::FlagArtificial);
1063  assert(FrameDIVar->isValidLocationForIntrinsic(PromiseDDI->getDebugLoc()));
1064 
1065  // Subprogram would have ContainedNodes field which records the debug
1066  // variables it contained. So we need to add __coro_frame to the
1067  // ContainedNodes of it.
1068  //
1069  // If we don't add __coro_frame to the RetainedNodes, user may get
1070  // `no symbol __coro_frame in context` rather than `__coro_frame`
1071  // is optimized out, which is more precise.
1072  if (auto *SubProgram = dyn_cast<DISubprogram>(PromiseDIScope)) {
1073  auto RetainedNodes = SubProgram->getRetainedNodes();
1074  SmallVector<Metadata *, 32> RetainedNodesVec(RetainedNodes.begin(),
1075  RetainedNodes.end());
1076  RetainedNodesVec.push_back(FrameDIVar);
1077  SubProgram->replaceOperandWith(
1078  7, (MDTuple::get(F.getContext(), RetainedNodesVec)));
1079  }
1080 
1081  DBuilder.insertDeclare(Shape.FramePtr, FrameDIVar,
1082  DBuilder.createExpression(), DILoc,
1083  Shape.FramePtr->getNextNode());
1084 }
1085 
1086 // Build a struct that will keep state for an active coroutine.
1087 // struct f.frame {
1088 // ResumeFnTy ResumeFnAddr;
1089 // ResumeFnTy DestroyFnAddr;
1090 // int ResumeIndex;
1091 // ... promise (if present) ...
1092 // ... spills ...
1093 // };
1095  FrameDataInfo &FrameData) {
1096  LLVMContext &C = F.getContext();
1097  const DataLayout &DL = F.getParent()->getDataLayout();
1098  StructType *FrameTy = [&] {
1099  SmallString<32> Name(F.getName());
1100  Name.append(".Frame");
1101  return StructType::create(C, Name);
1102  }();
1103 
1104  // We will use this value to cap the alignment of spilled values.
1105  Optional<Align> MaxFrameAlignment;
1106  if (Shape.ABI == coro::ABI::Async)
1107  MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();
1108  FrameTypeBuilder B(C, DL, MaxFrameAlignment);
1109 
1110  AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
1111  Optional<FieldIDType> SwitchIndexFieldId;
1112 
1113  if (Shape.ABI == coro::ABI::Switch) {
1114  auto *FramePtrTy = FrameTy->getPointerTo();
1115  auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
1116  /*IsVarArg=*/false);
1117  auto *FnPtrTy = FnTy->getPointerTo();
1118 
1119  // Add header fields for the resume and destroy functions.
1120  // We can rely on these being perfectly packed.
1121  (void)B.addField(FnPtrTy, None, /*header*/ true);
1122  (void)B.addField(FnPtrTy, None, /*header*/ true);
1123 
1124  // PromiseAlloca field needs to be explicitly added here because it's
1125  // a header field with a fixed offset based on its alignment. Hence it
1126  // needs special handling and cannot be added to FrameData.Allocas.
1127  if (PromiseAlloca)
1128  FrameData.setFieldIndex(
1129  PromiseAlloca, B.addFieldForAlloca(PromiseAlloca, /*header*/ true));
1130 
1131  // Add a field to store the suspend index. This doesn't need to
1132  // be in the header.
1133  unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
1134  Type *IndexType = Type::getIntNTy(C, IndexBits);
1135 
1136  SwitchIndexFieldId = B.addField(IndexType, None);
1137  } else {
1138  assert(PromiseAlloca == nullptr && "lowering doesn't support promises");
1139  }
1140 
1141  // Because multiple allocas may own the same field slot,
1142  // we add allocas to field here.
1143  B.addFieldForAllocas(F, FrameData, Shape);
1144  // Add PromiseAlloca to Allocas list so that
1145  // 1. updateLayoutIndex could update its index after
1146  // `performOptimizedStructLayout`
1147  // 2. it is processed in insertSpills.
1148  if (Shape.ABI == coro::ABI::Switch && PromiseAlloca)
1149  // We assume that the promise alloca won't be modified before
1150  // CoroBegin and no alias will be create before CoroBegin.
1151  FrameData.Allocas.emplace_back(
1152  PromiseAlloca, DenseMap<Instruction *, llvm::Optional<APInt>>{}, false);
1153  // Create an entry for every spilled value.
1154  for (auto &S : FrameData.Spills) {
1155  Type *FieldType = S.first->getType();
1156  // For byval arguments, we need to store the pointed value in the frame,
1157  // instead of the pointer itself.
1158  if (const Argument *A = dyn_cast<Argument>(S.first))
1159  if (A->hasByValAttr())
1160  FieldType = A->getParamByValType();
1161  FieldIDType Id =
1162  B.addField(FieldType, None, false /*header*/, true /*IsSpillOfValue*/);
1163  FrameData.setFieldIndex(S.first, Id);
1164  }
1165 
1166  B.finish(FrameTy);
1167  FrameData.updateLayoutIndex(B);
1168  Shape.FrameAlign = B.getStructAlign();
1169  Shape.FrameSize = B.getStructSize();
1170 
1171  switch (Shape.ABI) {
1172  case coro::ABI::Switch: {
1173  // In the switch ABI, remember the switch-index field.
1174  auto IndexField = B.getLayoutField(*SwitchIndexFieldId);
1175  Shape.SwitchLowering.IndexField = IndexField.LayoutFieldIndex;
1176  Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();
1177  Shape.SwitchLowering.IndexOffset = IndexField.Offset;
1178 
1179  // Also round the frame size up to a multiple of its alignment, as is
1180  // generally expected in C/C++.
1181  Shape.FrameSize = alignTo(Shape.FrameSize, Shape.FrameAlign);
1182  break;
1183  }
1184 
1185  // In the retcon ABI, remember whether the frame is inline in the storage.
1186  case coro::ABI::Retcon:
1187  case coro::ABI::RetconOnce: {
1188  auto Id = Shape.getRetconCoroId();
1190  = (B.getStructSize() <= Id->getStorageSize() &&
1191  B.getStructAlign() <= Id->getStorageAlignment());
1192  break;
1193  }
1194  case coro::ABI::Async: {
1195  Shape.AsyncLowering.FrameOffset =
1197  // Also make the final context size a multiple of the context alignment to
1198  // make allocation easier for allocators.
1199  Shape.AsyncLowering.ContextSize =
1202  if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
1204  "The alignment requirment of frame variables cannot be higher than "
1205  "the alignment of the async function context");
1206  }
1207  break;
1208  }
1209  }
1210 
1211  return FrameTy;
1212 }
1213 
1214 // We use a pointer use visitor to track how an alloca is being used.
1215 // The goal is to be able to answer the following three questions:
1216 // 1. Should this alloca be allocated on the frame instead.
1217 // 2. Could the content of the alloca be modified prior to CoroBegn, which would
1218 // require copying the data from alloca to the frame after CoroBegin.
1219 // 3. Is there any alias created for this alloca prior to CoroBegin, but used
1220 // after CoroBegin. In that case, we will need to recreate the alias after
1221 // CoroBegin based off the frame. To answer question 1, we track two things:
1222 // a. List of all BasicBlocks that use this alloca or any of the aliases of
1223 // the alloca. In the end, we check if there exists any two basic blocks that
1224 // cross suspension points. If so, this alloca must be put on the frame. b.
1225 // Whether the alloca or any alias of the alloca is escaped at some point,
1226 // either by storing the address somewhere, or the address is used in a
1227 // function call that might capture. If it's ever escaped, this alloca must be
1228 // put on the frame conservatively.
1229 // To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.
1230 // Whenever a potential write happens, either through a store instruction, a
1231 // function call or any of the memory intrinsics, we check whether this
1232 // instruction is prior to CoroBegin. To answer question 3, we track the offsets
1233 // of all aliases created for the alloca prior to CoroBegin but used after
1234 // CoroBegin. llvm::Optional is used to be able to represent the case when the
1235 // offset is unknown (e.g. when you have a PHINode that takes in different
1236 // offset values). We cannot handle unknown offsets and will assert. This is the
1237 // potential issue left out. An ideal solution would likely require a
1238 // significant redesign.
1239 namespace {
1240 struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
1242  AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,
1243  const CoroBeginInst &CB, const SuspendCrossingInfo &Checker)
1244  : PtrUseVisitor(DL), DT(DT), CoroBegin(CB), Checker(Checker) {}
1245 
1246  void visit(Instruction &I) {
1247  Users.insert(&I);
1248  Base::visit(I);
1249  // If the pointer is escaped prior to CoroBegin, we have to assume it would
1250  // be written into before CoroBegin as well.
1251  if (PI.isEscaped() && !DT.dominates(&CoroBegin, PI.getEscapingInst())) {
1252  MayWriteBeforeCoroBegin = true;
1253  }
1254  }
1255  // We need to provide this overload as PtrUseVisitor uses a pointer based
1256  // visiting function.
1257  void visit(Instruction *I) { return visit(*I); }
1258 
1259  void visitPHINode(PHINode &I) {
1260  enqueueUsers(I);
1261  handleAlias(I);
1262  }
1263 
1264  void visitSelectInst(SelectInst &I) {
1265  enqueueUsers(I);
1266  handleAlias(I);
1267  }
1268 
1269  void visitStoreInst(StoreInst &SI) {
1270  // Regardless whether the alias of the alloca is the value operand or the
1271  // pointer operand, we need to assume the alloca is been written.
1272  handleMayWrite(SI);
1273 
1274  if (SI.getValueOperand() != U->get())
1275  return;
1276 
1277  // We are storing the pointer into a memory location, potentially escaping.
1278  // As an optimization, we try to detect simple cases where it doesn't
1279  // actually escape, for example:
1280  // %ptr = alloca ..
1281  // %addr = alloca ..
1282  // store %ptr, %addr
1283  // %x = load %addr
1284  // ..
1285  // If %addr is only used by loading from it, we could simply treat %x as
1286  // another alias of %ptr, and not considering %ptr being escaped.
1287  auto IsSimpleStoreThenLoad = [&]() {
1288  auto *AI = dyn_cast<AllocaInst>(SI.getPointerOperand());
1289  // If the memory location we are storing to is not an alloca, it
1290  // could be an alias of some other memory locations, which is difficult
1291  // to analyze.
1292  if (!AI)
1293  return false;
1294  // StoreAliases contains aliases of the memory location stored into.
1295  SmallVector<Instruction *, 4> StoreAliases = {AI};
1296  while (!StoreAliases.empty()) {
1297  Instruction *I = StoreAliases.pop_back_val();
1298  for (User *U : I->users()) {
1299  // If we are loading from the memory location, we are creating an
1300  // alias of the original pointer.
1301  if (auto *LI = dyn_cast<LoadInst>(U)) {
1302  enqueueUsers(*LI);
1303  handleAlias(*LI);
1304  continue;
1305  }
1306  // If we are overriding the memory location, the pointer certainly
1307  // won't escape.
1308  if (auto *S = dyn_cast<StoreInst>(U))
1309  if (S->getPointerOperand() == I)
1310  continue;
1311  if (auto *II = dyn_cast<IntrinsicInst>(U))
1312  if (II->isLifetimeStartOrEnd())
1313  continue;
1314  // BitCastInst creats aliases of the memory location being stored
1315  // into.
1316  if (auto *BI = dyn_cast<BitCastInst>(U)) {
1317  StoreAliases.push_back(BI);
1318  continue;
1319  }
1320  return false;
1321  }
1322  }
1323 
1324  return true;
1325  };
1326 
1327  if (!IsSimpleStoreThenLoad())
1328  PI.setEscaped(&SI);
1329  }
1330 
1331  // All mem intrinsics modify the data.
1332  void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(MI); }
1333 
1334  void visitBitCastInst(BitCastInst &BC) {
1336  handleAlias(BC);
1337  }
1338 
1341  handleAlias(ASC);
1342  }
1343 
1345  // The base visitor will adjust Offset accordingly.
1347  handleAlias(GEPI);
1348  }
1349 
1350  void visitIntrinsicInst(IntrinsicInst &II) {
1351  if (II.getIntrinsicID() != Intrinsic::lifetime_start)
1352  return Base::visitIntrinsicInst(II);
1353  LifetimeStarts.insert(&II);
1354  }
1355 
1356  void visitCallBase(CallBase &CB) {
1357  for (unsigned Op = 0, OpCount = CB.getNumArgOperands(); Op < OpCount; ++Op)
1358  if (U->get() == CB.getArgOperand(Op) && !CB.doesNotCapture(Op))
1359  PI.setEscaped(&CB);
1360  handleMayWrite(CB);
1361  }
1362 
1363  bool getShouldLiveOnFrame() const {
1364  if (!ShouldLiveOnFrame)
1365  ShouldLiveOnFrame = computeShouldLiveOnFrame();
1366  return ShouldLiveOnFrame.getValue();
1367  }
1368 
1369  bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }
1370 
1371  DenseMap<Instruction *, llvm::Optional<APInt>> getAliasesCopy() const {
1372  assert(getShouldLiveOnFrame() && "This method should only be called if the "
1373  "alloca needs to live on the frame.");
1374  for (const auto &P : AliasOffetMap)
1375  if (!P.second)
1376  report_fatal_error("Unable to handle an alias with unknown offset "
1377  "created before CoroBegin.");
1378  return AliasOffetMap;
1379  }
1380 
1381 private:
1382  const DominatorTree &DT;
1383  const CoroBeginInst &CoroBegin;
1384  const SuspendCrossingInfo &Checker;
1385  // All alias to the original AllocaInst, created before CoroBegin and used
1386  // after CoroBegin. Each entry contains the instruction and the offset in the
1387  // original Alloca. They need to be recreated after CoroBegin off the frame.
1390  SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};
1391  bool MayWriteBeforeCoroBegin{false};
1392 
1393  mutable llvm::Optional<bool> ShouldLiveOnFrame{};
1394 
1395  bool computeShouldLiveOnFrame() const {
1396  // If lifetime information is available, we check it first since it's
1397  // more precise. We look at every pair of lifetime.start intrinsic and
1398  // every basic block that uses the pointer to see if they cross suspension
1399  // points. The uses cover both direct uses as well as indirect uses.
1400  if (!LifetimeStarts.empty()) {
1401  for (auto *I : Users)
1402  for (auto *S : LifetimeStarts)
1403  if (Checker.isDefinitionAcrossSuspend(*S, I))
1404  return true;
1405  return false;
1406  }
1407  // FIXME: Ideally the isEscaped check should come at the beginning.
1408  // However there are a few loose ends that need to be fixed first before
1409  // we can do that. We need to make sure we are not over-conservative, so
1410  // that the data accessed in-between await_suspend and symmetric transfer
1411  // is always put on the stack, and also data accessed after coro.end is
1412  // always put on the stack (esp the return object). To fix that, we need
1413  // to:
1414  // 1) Potentially treat sret as nocapture in calls
1415  // 2) Special handle the return object and put it on the stack
1416  // 3) Utilize lifetime.end intrinsic
1417  if (PI.isEscaped())
1418  return true;
1419 
1420  for (auto *U1 : Users)
1421  for (auto *U2 : Users)
1422  if (Checker.isDefinitionAcrossSuspend(*U1, U2))
1423  return true;
1424 
1425  return false;
1426  }
1427 
1428  void handleMayWrite(const Instruction &I) {
1429  if (!DT.dominates(&CoroBegin, &I))
1430  MayWriteBeforeCoroBegin = true;
1431  }
1432 
1433  bool usedAfterCoroBegin(Instruction &I) {
1434  for (auto &U : I.uses())
1435  if (DT.dominates(&CoroBegin, U))
1436  return true;
1437  return false;
1438  }
1439 
1440  void handleAlias(Instruction &I) {
1441  // We track all aliases created prior to CoroBegin but used after.
1442  // These aliases may need to be recreated after CoroBegin if the alloca
1443  // need to live on the frame.
1444  if (DT.dominates(&CoroBegin, &I) || !usedAfterCoroBegin(I))
1445  return;
1446 
1447  if (!IsOffsetKnown) {
1448  AliasOffetMap[&I].reset();
1449  } else {
1450  auto Itr = AliasOffetMap.find(&I);
1451  if (Itr == AliasOffetMap.end()) {
1452  AliasOffetMap[&I] = Offset;
1453  } else if (Itr->second.hasValue() && Itr->second.getValue() != Offset) {
1454  // If we have seen two different possible values for this alias, we set
1455  // it to empty.
1456  AliasOffetMap[&I].reset();
1457  }
1458  }
1459  }
1460 };
1461 } // namespace
1462 
1463 // We need to make room to insert a spill after initial PHIs, but before
1464 // catchswitch instruction. Placing it before violates the requirement that
1465 // catchswitch, like all other EHPads must be the first nonPHI in a block.
1466 //
1467 // Split away catchswitch into a separate block and insert in its place:
1468 //
1469 // cleanuppad <InsertPt> cleanupret.
1470 //
1471 // cleanupret instruction will act as an insert point for the spill.
1473  BasicBlock *CurrentBlock = CatchSwitch->getParent();
1474  BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
1475  CurrentBlock->getTerminator()->eraseFromParent();
1476 
1477  auto *CleanupPad =
1478  CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
1479  auto *CleanupRet =
1480  CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
1481  return CleanupRet;
1482 }
1483 
1484 static void createFramePtr(coro::Shape &Shape) {
1485  auto *CB = Shape.CoroBegin;
1487  StructType *FrameTy = Shape.FrameTy;
1488  PointerType *FramePtrTy = FrameTy->getPointerTo();
1489  Shape.FramePtr =
1490  cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
1491 }
1492 
1493 // Replace all alloca and SSA values that are accessed across suspend points
1494 // with GetElementPointer from coroutine frame + loads and stores. Create an
1495 // AllocaSpillBB that will become the new entry block for the resume parts of
1496 // the coroutine:
1497 //
1498 // %hdl = coro.begin(...)
1499 // whatever
1500 //
1501 // becomes:
1502 //
1503 // %hdl = coro.begin(...)
1504 // %FramePtr = bitcast i8* hdl to %f.frame*
1505 // br label %AllocaSpillBB
1506 //
1507 // AllocaSpillBB:
1508 // ; geps corresponding to allocas that were moved to coroutine frame
1509 // br label PostSpill
1510 //
1511 // PostSpill:
1512 // whatever
1513 //
1514 //
1515 static Instruction *insertSpills(const FrameDataInfo &FrameData,
1516  coro::Shape &Shape) {
1517  auto *CB = Shape.CoroBegin;
1518  LLVMContext &C = CB->getContext();
1520  StructType *FrameTy = Shape.FrameTy;
1521  Instruction *FramePtr = Shape.FramePtr;
1522  DominatorTree DT(*CB->getFunction());
1524 
1525  // Create a GEP with the given index into the coroutine frame for the original
1526  // value Orig. Appends an extra 0 index for array-allocas, preserving the
1527  // original type.
1528  auto GetFramePointer = [&](Value *Orig) -> Value * {
1529  FieldIDType Index = FrameData.getFieldIndex(Orig);
1530  SmallVector<Value *, 3> Indices = {
1531  ConstantInt::get(Type::getInt32Ty(C), 0),
1532  ConstantInt::get(Type::getInt32Ty(C), Index),
1533  };
1534 
1535  if (auto *AI = dyn_cast<AllocaInst>(Orig)) {
1536  if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize())) {
1537  auto Count = CI->getValue().getZExtValue();
1538  if (Count > 1) {
1539  Indices.push_back(ConstantInt::get(Type::getInt32Ty(C), 0));
1540  }
1541  } else {
1542  report_fatal_error("Coroutines cannot handle non static allocas yet");
1543  }
1544  }
1545 
1546  auto GEP = cast<GetElementPtrInst>(
1547  Builder.CreateInBoundsGEP(FrameTy, FramePtr, Indices));
1548  if (isa<AllocaInst>(Orig)) {
1549  // If the type of GEP is not equal to the type of AllocaInst, it implies
1550  // that the AllocaInst may be reused in the Frame slot of other
1551  // AllocaInst. So We cast GEP to the AllocaInst here to re-use
1552  // the Frame storage.
1553  //
1554  // Note: If we change the strategy dealing with alignment, we need to refine
1555  // this casting.
1556  if (GEP->getResultElementType() != Orig->getType())
1557  return Builder.CreateBitCast(GEP, Orig->getType(),
1558  Orig->getName() + Twine(".cast"));
1559  }
1560  return GEP;
1561  };
1562 
1563  for (auto const &E : FrameData.Spills) {
1564  Value *Def = E.first;
1565  auto SpillAlignment = Align(FrameData.getAlign(Def));
1566  // Create a store instruction storing the value into the
1567  // coroutine frame.
1568  Instruction *InsertPt = nullptr;
1569  bool NeedToCopyArgPtrValue = false;
1570  if (auto *Arg = dyn_cast<Argument>(Def)) {
1571  // For arguments, we will place the store instruction right after
1572  // the coroutine frame pointer instruction, i.e. bitcast of
1573  // coro.begin from i8* to %f.frame*.
1574  InsertPt = FramePtr->getNextNode();
1575 
1576  // If we're spilling an Argument, make sure we clear 'nocapture'
1577  // from the coroutine function.
1578  Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::NoCapture);
1579 
1580  if (Arg->hasByValAttr())
1581  NeedToCopyArgPtrValue = true;
1582 
1583  } else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Def)) {
1584  // Don't spill immediately after a suspend; splitting assumes
1585  // that the suspend will be followed by a branch.
1586  InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHI();
1587  } else {
1588  auto *I = cast<Instruction>(Def);
1589  if (!DT.dominates(CB, I)) {
1590  // If it is not dominated by CoroBegin, then spill should be
1591  // inserted immediately after CoroFrame is computed.
1592  InsertPt = FramePtr->getNextNode();
1593  } else if (auto *II = dyn_cast<InvokeInst>(I)) {
1594  // If we are spilling the result of the invoke instruction, split
1595  // the normal edge and insert the spill in the new block.
1596  auto *NewBB = SplitEdge(II->getParent(), II->getNormalDest());
1597  InsertPt = NewBB->getTerminator();
1598  } else if (isa<PHINode>(I)) {
1599  // Skip the PHINodes and EH pads instructions.
1600  BasicBlock *DefBlock = I->getParent();
1601  if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
1602  InsertPt = splitBeforeCatchSwitch(CSI);
1603  else
1604  InsertPt = &*DefBlock->getFirstInsertionPt();
1605  } else {
1606  assert(!I->isTerminator() && "unexpected terminator");
1607  // For all other values, the spill is placed immediately after
1608  // the definition.
1609  InsertPt = I->getNextNode();
1610  }
1611  }
1612 
1613  auto Index = FrameData.getFieldIndex(Def);
1614  Builder.SetInsertPoint(InsertPt);
1615  auto *G = Builder.CreateConstInBoundsGEP2_32(
1616  FrameTy, FramePtr, 0, Index, Def->getName() + Twine(".spill.addr"));
1617  if (NeedToCopyArgPtrValue) {
1618  // For byval arguments, we need to store the pointed value in the frame,
1619  // instead of the pointer itself.
1620  auto *Value =
1621  Builder.CreateLoad(Def->getType()->getPointerElementType(), Def);
1622  Builder.CreateAlignedStore(Value, G, SpillAlignment);
1623  } else {
1624  Builder.CreateAlignedStore(Def, G, SpillAlignment);
1625  }
1626 
1627  BasicBlock *CurrentBlock = nullptr;
1628  Value *CurrentReload = nullptr;
1629  for (auto *U : E.second) {
1630  // If we have not seen the use block, create a load instruction to reload
1631  // the spilled value from the coroutine frame. Populates the Value pointer
1632  // reference provided with the frame GEP.
1633  if (CurrentBlock != U->getParent()) {
1634  CurrentBlock = U->getParent();
1635  Builder.SetInsertPoint(&*CurrentBlock->getFirstInsertionPt());
1636 
1637  auto *GEP = GetFramePointer(E.first);
1638  GEP->setName(E.first->getName() + Twine(".reload.addr"));
1639  if (NeedToCopyArgPtrValue)
1640  CurrentReload = GEP;
1641  else
1642  CurrentReload = Builder.CreateAlignedLoad(
1643  FrameTy->getElementType(FrameData.getFieldIndex(E.first)), GEP,
1644  SpillAlignment, E.first->getName() + Twine(".reload"));
1645 
1647  for (DbgDeclareInst *DDI : DIs) {
1648  bool AllowUnresolved = false;
1649  // This dbg.declare is preserved for all coro-split function
1650  // fragments. It will be unreachable in the main function, and
1651  // processed by coro::salvageDebugInfo() by CoroCloner.
1652  DIBuilder(*CurrentBlock->getParent()->getParent(), AllowUnresolved)
1653  .insertDeclare(CurrentReload, DDI->getVariable(),
1654  DDI->getExpression(), DDI->getDebugLoc(),
1655  &*Builder.GetInsertPoint());
1656  // This dbg.declare is for the main function entry point. It
1657  // will be deleted in all coro-split functions.
1658  coro::salvageDebugInfo(DbgPtrAllocaCache, DDI, Shape.ReuseFrameSlot);
1659  }
1660  }
1661 
1662  // If we have a single edge PHINode, remove it and replace it with a
1663  // reload from the coroutine frame. (We already took care of multi edge
1664  // PHINodes by rewriting them in the rewritePHIs function).
1665  if (auto *PN = dyn_cast<PHINode>(U)) {
1666  assert(PN->getNumIncomingValues() == 1 &&
1667  "unexpected number of incoming "
1668  "values in the PHINode");
1669  PN->replaceAllUsesWith(CurrentReload);
1670  PN->eraseFromParent();
1671  continue;
1672  }
1673 
1674  // Replace all uses of CurrentValue in the current instruction with
1675  // reload.
1676  U->replaceUsesOfWith(Def, CurrentReload);
1677  }
1678  }
1679 
1680  BasicBlock *FramePtrBB = FramePtr->getParent();
1681 
1682  auto SpillBlock =
1683  FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
1684  SpillBlock->splitBasicBlock(&SpillBlock->front(), "PostSpill");
1685  Shape.AllocaSpillBlock = SpillBlock;
1686 
1687  // retcon and retcon.once lowering assumes all uses have been sunk.
1688  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
1689  Shape.ABI == coro::ABI::Async) {
1690  // If we found any allocas, replace all of their remaining uses with Geps.
1691  Builder.SetInsertPoint(&SpillBlock->front());
1692  for (const auto &P : FrameData.Allocas) {
1693  AllocaInst *Alloca = P.Alloca;
1694  auto *G = GetFramePointer(Alloca);
1695 
1696  // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))
1697  // here, as we are changing location of the instruction.
1698  G->takeName(Alloca);
1699  Alloca->replaceAllUsesWith(G);
1700  Alloca->eraseFromParent();
1701  }
1702  return FramePtr;
1703  }
1704 
1705  // If we found any alloca, replace all of their remaining uses with GEP
1706  // instructions. To remain debugbility, we replace the uses of allocas for
1707  // dbg.declares and dbg.values with the reload from the frame.
1708  // Note: We cannot replace the alloca with GEP instructions indiscriminately,
1709  // as some of the uses may not be dominated by CoroBegin.
1710  Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
1711  SmallVector<Instruction *, 4> UsersToUpdate;
1712  for (const auto &A : FrameData.Allocas) {
1713  AllocaInst *Alloca = A.Alloca;
1714  UsersToUpdate.clear();
1715  for (User *U : Alloca->users()) {
1716  auto *I = cast<Instruction>(U);
1717  if (DT.dominates(CB, I))
1718  UsersToUpdate.push_back(I);
1719  }
1720  if (UsersToUpdate.empty())
1721  continue;
1722  auto *G = GetFramePointer(Alloca);
1723  G->setName(Alloca->getName() + Twine(".reload.addr"));
1724 
1726  findDbgUsers(DIs, Alloca);
1727  for (auto *DVI : DIs)
1728  DVI->replaceUsesOfWith(Alloca, G);
1729 
1730  for (Instruction *I : UsersToUpdate)
1731  I->replaceUsesOfWith(Alloca, G);
1732  }
1733  Builder.SetInsertPoint(FramePtr->getNextNode());
1734  for (const auto &A : FrameData.Allocas) {
1735  AllocaInst *Alloca = A.Alloca;
1736  if (A.MayWriteBeforeCoroBegin) {
1737  // isEscaped really means potentially modified before CoroBegin.
1738  if (Alloca->isArrayAllocation())
1740  "Coroutines cannot handle copying of array allocas yet");
1741 
1742  auto *G = GetFramePointer(Alloca);
1743  auto *Value = Builder.CreateLoad(Alloca->getAllocatedType(), Alloca);
1744  Builder.CreateStore(Value, G);
1745  }
1746  // For each alias to Alloca created before CoroBegin but used after
1747  // CoroBegin, we recreate them after CoroBegin by appplying the offset
1748  // to the pointer in the frame.
1749  for (const auto &Alias : A.Aliases) {
1750  auto *FramePtr = GetFramePointer(Alloca);
1751  auto *FramePtrRaw =
1752  Builder.CreateBitCast(FramePtr, Type::getInt8PtrTy(C));
1753  auto *AliasPtr = Builder.CreateGEP(
1754  Type::getInt8Ty(C), FramePtrRaw,
1755  ConstantInt::get(Type::getInt64Ty(C), Alias.second.getValue()));
1756  auto *AliasPtrTyped =
1757  Builder.CreateBitCast(AliasPtr, Alias.first->getType());
1758  Alias.first->replaceUsesWithIf(
1759  AliasPtrTyped, [&](Use &U) { return DT.dominates(CB, U); });
1760  }
1761  }
1762  return FramePtr;
1763 }
1764 
1765 // Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
1766 // PHI in InsertedBB.
1768  BasicBlock *InsertedBB,
1769  BasicBlock *PredBB,
1770  PHINode *UntilPHI = nullptr) {
1771  auto *PN = cast<PHINode>(&SuccBB->front());
1772  do {
1773  int Index = PN->getBasicBlockIndex(InsertedBB);
1774  Value *V = PN->getIncomingValue(Index);
1775  PHINode *InputV = PHINode::Create(
1776  V->getType(), 1, V->getName() + Twine(".") + SuccBB->getName(),
1777  &InsertedBB->front());
1778  InputV->addIncoming(V, PredBB);
1779  PN->setIncomingValue(Index, InputV);
1780  PN = dyn_cast<PHINode>(PN->getNextNode());
1781  } while (PN != UntilPHI);
1782 }
1783 
1784 // Rewrites the PHI Nodes in a cleanuppad.
1785 static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,
1786  CleanupPadInst *CleanupPad) {
1787  // For every incoming edge to a CleanupPad we will create a new block holding
1788  // all incoming values in single-value PHI nodes. We will then create another
1789  // block to act as a dispather (as all unwind edges for related EH blocks
1790  // must be the same).
1791  //
1792  // cleanuppad:
1793  // %2 = phi i32[%0, %catchswitch], [%1, %catch.1]
1794  // %3 = cleanuppad within none []
1795  //
1796  // It will create:
1797  //
1798  // cleanuppad.corodispatch
1799  // %2 = phi i8[0, %catchswitch], [1, %catch.1]
1800  // %3 = cleanuppad within none []
1801  // switch i8 % 2, label %unreachable
1802  // [i8 0, label %cleanuppad.from.catchswitch
1803  // i8 1, label %cleanuppad.from.catch.1]
1804  // cleanuppad.from.catchswitch:
1805  // %4 = phi i32 [%0, %catchswitch]
1806  // br %label cleanuppad
1807  // cleanuppad.from.catch.1:
1808  // %6 = phi i32 [%1, %catch.1]
1809  // br %label cleanuppad
1810  // cleanuppad:
1811  // %8 = phi i32 [%4, %cleanuppad.from.catchswitch],
1812  // [%6, %cleanuppad.from.catch.1]
1813 
1814  // Unreachable BB, in case switching on an invalid value in the dispatcher.
1815  auto *UnreachBB = BasicBlock::Create(
1816  CleanupPadBB->getContext(), "unreachable", CleanupPadBB->getParent());
1817  IRBuilder<> Builder(UnreachBB);
1818  Builder.CreateUnreachable();
1819 
1820  // Create a new cleanuppad which will be the dispatcher.
1821  auto *NewCleanupPadBB =
1822  BasicBlock::Create(CleanupPadBB->getContext(),
1823  CleanupPadBB->getName() + Twine(".corodispatch"),
1824  CleanupPadBB->getParent(), CleanupPadBB);
1825  Builder.SetInsertPoint(NewCleanupPadBB);
1826  auto *SwitchType = Builder.getInt8Ty();
1827  auto *SetDispatchValuePN =
1828  Builder.CreatePHI(SwitchType, pred_size(CleanupPadBB));
1829  CleanupPad->removeFromParent();
1830  CleanupPad->insertAfter(SetDispatchValuePN);
1831  auto *SwitchOnDispatch = Builder.CreateSwitch(SetDispatchValuePN, UnreachBB,
1832  pred_size(CleanupPadBB));
1833 
1834  int SwitchIndex = 0;
1835  SmallVector<BasicBlock *, 8> Preds(predecessors(CleanupPadBB));
1836  for (BasicBlock *Pred : Preds) {
1837  // Create a new cleanuppad and move the PHI values to there.
1838  auto *CaseBB = BasicBlock::Create(CleanupPadBB->getContext(),
1839  CleanupPadBB->getName() +
1840  Twine(".from.") + Pred->getName(),
1841  CleanupPadBB->getParent(), CleanupPadBB);
1842  updatePhiNodes(CleanupPadBB, Pred, CaseBB);
1843  CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +
1844  Pred->getName());
1845  Builder.SetInsertPoint(CaseBB);
1846  Builder.CreateBr(CleanupPadBB);
1847  movePHIValuesToInsertedBlock(CleanupPadBB, CaseBB, NewCleanupPadBB);
1848 
1849  // Update this Pred to the new unwind point.
1850  setUnwindEdgeTo(Pred->getTerminator(), NewCleanupPadBB);
1851 
1852  // Setup the switch in the dispatcher.
1853  auto *SwitchConstant = ConstantInt::get(SwitchType, SwitchIndex);
1854  SetDispatchValuePN->addIncoming(SwitchConstant, Pred);
1855  SwitchOnDispatch->addCase(SwitchConstant, CaseBB);
1856  SwitchIndex++;
1857  }
1858 }
1859 
1861  SmallVector<PHINode *, 32> Worklist;
1862  for (auto &BB : F) {
1863  for (auto &Phi : BB.phis()) {
1864  if (Phi.getNumIncomingValues() == 1) {
1865  Worklist.push_back(&Phi);
1866  } else
1867  break;
1868  }
1869  }
1870  while (!Worklist.empty()) {
1871  auto *Phi = Worklist.back();
1872  Worklist.pop_back();
1873  auto *OriginalValue = Phi->getIncomingValue(0);
1874  Phi->replaceAllUsesWith(OriginalValue);
1875  }
1876 }
1877 
1878 static void rewritePHIs(BasicBlock &BB) {
1879  // For every incoming edge we will create a block holding all
1880  // incoming values in a single PHI nodes.
1881  //
1882  // loop:
1883  // %n.val = phi i32[%n, %entry], [%inc, %loop]
1884  //
1885  // It will create:
1886  //
1887  // loop.from.entry:
1888  // %n.loop.pre = phi i32 [%n, %entry]
1889  // br %label loop
1890  // loop.from.loop:
1891  // %inc.loop.pre = phi i32 [%inc, %loop]
1892  // br %label loop
1893  //
1894  // After this rewrite, further analysis will ignore any phi nodes with more
1895  // than one incoming edge.
1896 
1897  // TODO: Simplify PHINodes in the basic block to remove duplicate
1898  // predecessors.
1899 
1900  // Special case for CleanupPad: all EH blocks must have the same unwind edge
1901  // so we need to create an additional "dispatcher" block.
1902  if (auto *CleanupPad =
1903  dyn_cast_or_null<CleanupPadInst>(BB.getFirstNonPHI())) {
1905  for (BasicBlock *Pred : Preds) {
1906  if (CatchSwitchInst *CS =
1907  dyn_cast<CatchSwitchInst>(Pred->getTerminator())) {
1908  // CleanupPad with a CatchSwitch predecessor: therefore this is an
1909  // unwind destination that needs to be handle specially.
1910  assert(CS->getUnwindDest() == &BB);
1911  (void)CS;
1912  rewritePHIsForCleanupPad(&BB, CleanupPad);
1913  return;
1914  }
1915  }
1916  }
1917 
1918  LandingPadInst *LandingPad = nullptr;
1919  PHINode *ReplPHI = nullptr;
1920  if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
1921  // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
1922  // We replace the original landing pad with a PHINode that will collect the
1923  // results from all of them.
1924  ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
1925  ReplPHI->takeName(LandingPad);
1926  LandingPad->replaceAllUsesWith(ReplPHI);
1927  // We will erase the original landing pad at the end of this function after
1928  // ehAwareSplitEdge cloned it in the transition blocks.
1929  }
1930 
1932  for (BasicBlock *Pred : Preds) {
1933  auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
1934  IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
1935 
1936  // Stop the moving of values at ReplPHI, as this is either null or the PHI
1937  // that replaced the landing pad.
1938  movePHIValuesToInsertedBlock(&BB, IncomingBB, Pred, ReplPHI);
1939  }
1940 
1941  if (LandingPad) {
1942  // Calls to ehAwareSplitEdge function cloned the original lading pad.
1943  // No longer need it.
1944  LandingPad->eraseFromParent();
1945  }
1946 }
1947 
1948 static void rewritePHIs(Function &F) {
1950 
1951  for (BasicBlock &BB : F)
1952  if (auto *PN = dyn_cast<PHINode>(&BB.front()))
1953  if (PN->getNumIncomingValues() > 1)
1954  WorkList.push_back(&BB);
1955 
1956  for (BasicBlock *BB : WorkList)
1957  rewritePHIs(*BB);
1958 }
1959 
1960 // Check for instructions that we can recreate on resume as opposed to spill
1961 // the result into a coroutine frame.
1962 static bool materializable(Instruction &V) {
1963  return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
1964  isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
1965 }
1966 
1967 // Check for structural coroutine intrinsics that should not be spilled into
1968 // the coroutine frame.
1970  return isa<CoroIdInst>(&I) || isa<CoroSaveInst>(&I) ||
1971  isa<CoroSuspendInst>(&I);
1972 }
1973 
1974 // For every use of the value that is across suspend point, recreate that value
1975 // after a suspend point.
1977  const SpillInfo &Spills) {
1978  for (const auto &E : Spills) {
1979  Value *Def = E.first;
1980  BasicBlock *CurrentBlock = nullptr;
1981  Instruction *CurrentMaterialization = nullptr;
1982  for (Instruction *U : E.second) {
1983  // If we have not seen this block, materialize the value.
1984  if (CurrentBlock != U->getParent()) {
1985 
1986  bool IsInCoroSuspendBlock = isa<AnyCoroSuspendInst>(U);
1987  CurrentBlock = IsInCoroSuspendBlock
1989  : U->getParent();
1990  CurrentMaterialization = cast<Instruction>(Def)->clone();
1991  CurrentMaterialization->setName(Def->getName());
1992  CurrentMaterialization->insertBefore(
1993  IsInCoroSuspendBlock ? CurrentBlock->getTerminator()
1994  : &*CurrentBlock->getFirstInsertionPt());
1995  }
1996  if (auto *PN = dyn_cast<PHINode>(U)) {
1997  assert(PN->getNumIncomingValues() == 1 &&
1998  "unexpected number of incoming "
1999  "values in the PHINode");
2000  PN->replaceAllUsesWith(CurrentMaterialization);
2001  PN->eraseFromParent();
2002  continue;
2003  }
2004  // Replace all uses of Def in the current instruction with the
2005  // CurrentMaterialization for the block.
2006  U->replaceUsesOfWith(Def, CurrentMaterialization);
2007  }
2008  }
2009 }
2010 
2011 // Splits the block at a particular instruction unless it is the first
2012 // instruction in the block with a single predecessor.
2014  auto *BB = I->getParent();
2015  if (&BB->front() == I) {
2016  if (BB->getSinglePredecessor()) {
2017  BB->setName(Name);
2018  return BB;
2019  }
2020  }
2021  return BB->splitBasicBlock(I, Name);
2022 }
2023 
2024 // Split above and below a particular instruction so that it
2025 // will be all alone by itself in a block.
2026 static void splitAround(Instruction *I, const Twine &Name) {
2028  splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
2029 }
2030 
2032  return isa<AnyCoroSuspendInst>(BB->front());
2033 }
2034 
2036 
2037 /// Does control flow starting at the given block ever reach a suspend
2038 /// instruction before reaching a block in VisitedOrFreeBBs?
2040  VisitedBlocksSet &VisitedOrFreeBBs) {
2041  // Eagerly try to add this block to the visited set. If it's already
2042  // there, stop recursing; this path doesn't reach a suspend before
2043  // either looping or reaching a freeing block.
2044  if (!VisitedOrFreeBBs.insert(From).second)
2045  return false;
2046 
2047  // We assume that we'll already have split suspends into their own blocks.
2048  if (isSuspendBlock(From))
2049  return true;
2050 
2051  // Recurse on the successors.
2052  for (auto Succ : successors(From)) {
2053  if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))
2054  return true;
2055  }
2056 
2057  return false;
2058 }
2059 
2060 /// Is the given alloca "local", i.e. bounded in lifetime to not cross a
2061 /// suspend point?
2063  // Seed the visited set with all the basic blocks containing a free
2064  // so that we won't pass them up.
2065  VisitedBlocksSet VisitedOrFreeBBs;
2066  for (auto User : AI->users()) {
2067  if (auto FI = dyn_cast<CoroAllocaFreeInst>(User))
2068  VisitedOrFreeBBs.insert(FI->getParent());
2069  }
2070 
2071  return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);
2072 }
2073 
2074 /// After we split the coroutine, will the given basic block be along
2075 /// an obvious exit path for the resumption function?
2077  unsigned depth = 3) {
2078  // If we've bottomed out our depth count, stop searching and assume
2079  // that the path might loop back.
2080  if (depth == 0) return false;
2081 
2082  // If this is a suspend block, we're about to exit the resumption function.
2083  if (isSuspendBlock(BB)) return true;
2084 
2085  // Recurse into the successors.
2086  for (auto Succ : successors(BB)) {
2087  if (!willLeaveFunctionImmediatelyAfter(Succ, depth - 1))
2088  return false;
2089  }
2090 
2091  // If none of the successors leads back in a loop, we're on an exit/abort.
2092  return true;
2093 }
2094 
2096  // Look for a free that isn't sufficiently obviously followed by
2097  // either a suspend or a termination, i.e. something that will leave
2098  // the coro resumption frame.
2099  for (auto U : AI->users()) {
2100  auto FI = dyn_cast<CoroAllocaFreeInst>(U);
2101  if (!FI) continue;
2102 
2103  if (!willLeaveFunctionImmediatelyAfter(FI->getParent()))
2104  return true;
2105  }
2106 
2107  // If we never found one, we don't need a stack save.
2108  return false;
2109 }
2110 
2111 /// Turn each of the given local allocas into a normal (dynamic) alloca
2112 /// instruction.
2114  SmallVectorImpl<Instruction*> &DeadInsts) {
2115  for (auto AI : LocalAllocas) {
2116  auto M = AI->getModule();
2117  IRBuilder<> Builder(AI);
2118 
2119  // Save the stack depth. Try to avoid doing this if the stackrestore
2120  // is going to immediately precede a return or something.
2121  Value *StackSave = nullptr;
2122  if (localAllocaNeedsStackSave(AI))
2123  StackSave = Builder.CreateCall(
2124  Intrinsic::getDeclaration(M, Intrinsic::stacksave));
2125 
2126  // Allocate memory.
2127  auto Alloca = Builder.CreateAlloca(Builder.getInt8Ty(), AI->getSize());
2128  Alloca->setAlignment(Align(AI->getAlignment()));
2129 
2130  for (auto U : AI->users()) {
2131  // Replace gets with the allocation.
2132  if (isa<CoroAllocaGetInst>(U)) {
2133  U->replaceAllUsesWith(Alloca);
2134 
2135  // Replace frees with stackrestores. This is safe because
2136  // alloca.alloc is required to obey a stack discipline, although we
2137  // don't enforce that structurally.
2138  } else {
2139  auto FI = cast<CoroAllocaFreeInst>(U);
2140  if (StackSave) {
2141  Builder.SetInsertPoint(FI);
2142  Builder.CreateCall(
2143  Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
2144  StackSave);
2145  }
2146  }
2147  DeadInsts.push_back(cast<Instruction>(U));
2148  }
2149 
2150  DeadInsts.push_back(AI);
2151  }
2152 }
2153 
2154 /// Turn the given coro.alloca.alloc call into a dynamic allocation.
2155 /// This happens during the all-instructions iteration, so it must not
2156 /// delete the call.
2158  coro::Shape &Shape,
2159  SmallVectorImpl<Instruction*> &DeadInsts) {
2160  IRBuilder<> Builder(AI);
2161  auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);
2162 
2163  for (User *U : AI->users()) {
2164  if (isa<CoroAllocaGetInst>(U)) {
2165  U->replaceAllUsesWith(Alloc);
2166  } else {
2167  auto FI = cast<CoroAllocaFreeInst>(U);
2168  Builder.SetInsertPoint(FI);
2169  Shape.emitDealloc(Builder, Alloc, nullptr);
2170  }
2171  DeadInsts.push_back(cast<Instruction>(U));
2172  }
2173 
2174  // Push this on last so that it gets deleted after all the others.
2175  DeadInsts.push_back(AI);
2176 
2177  // Return the new allocation value so that we can check for needed spills.
2178  return cast<Instruction>(Alloc);
2179 }
2180 
2181 /// Get the current swifterror value.
2183  coro::Shape &Shape) {
2184  // Make a fake function pointer as a sort of intrinsic.
2185  auto FnTy = FunctionType::get(ValueTy, {}, false);
2186  auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2187 
2188  auto Call = Builder.CreateCall(FnTy, Fn, {});
2189  Shape.SwiftErrorOps.push_back(Call);
2190 
2191  return Call;
2192 }
2193 
2194 /// Set the given value as the current swifterror value.
2195 ///
2196 /// Returns a slot that can be used as a swifterror slot.
2198  coro::Shape &Shape) {
2199  // Make a fake function pointer as a sort of intrinsic.
2200  auto FnTy = FunctionType::get(V->getType()->getPointerTo(),
2201  {V->getType()}, false);
2202  auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2203 
2204  auto Call = Builder.CreateCall(FnTy, Fn, { V });
2205  Shape.SwiftErrorOps.push_back(Call);
2206 
2207  return Call;
2208 }
2209 
2210 /// Set the swifterror value from the given alloca before a call,
2211 /// then put in back in the alloca afterwards.
2212 ///
2213 /// Returns an address that will stand in for the swifterror slot
2214 /// until splitting.
2216  AllocaInst *Alloca,
2217  coro::Shape &Shape) {
2218  auto ValueTy = Alloca->getAllocatedType();
2220 
2221  // Load the current value from the alloca and set it as the
2222  // swifterror value.
2223  auto ValueBeforeCall = Builder.CreateLoad(ValueTy, Alloca);
2224  auto Addr = emitSetSwiftErrorValue(Builder, ValueBeforeCall, Shape);
2225 
2226  // Move to after the call. Since swifterror only has a guaranteed
2227  // value on normal exits, we can ignore implicit and explicit unwind
2228  // edges.
2229  if (isa<CallInst>(Call)) {
2230  Builder.SetInsertPoint(Call->getNextNode());
2231  } else {
2232  auto Invoke = cast<InvokeInst>(Call);
2233  Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
2234  }
2235 
2236  // Get the current swifterror value and store it to the alloca.
2237  auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
2238  Builder.CreateStore(ValueAfterCall, Alloca);
2239 
2240  return Addr;
2241 }
2242 
2243 /// Eliminate a formerly-swifterror alloca by inserting the get/set
2244 /// intrinsics and attempting to MemToReg the alloca away.
2246  coro::Shape &Shape) {
2247  for (auto UI = Alloca->use_begin(), UE = Alloca->use_end(); UI != UE; ) {
2248  // We're likely changing the use list, so use a mutation-safe
2249  // iteration pattern.
2250  auto &Use = *UI;
2251  ++UI;
2252 
2253  // swifterror values can only be used in very specific ways.
2254  // We take advantage of that here.
2255  auto User = Use.getUser();
2256  if (isa<LoadInst>(User) || isa<StoreInst>(User))
2257  continue;
2258 
2259  assert(isa<CallInst>(User) || isa<InvokeInst>(User));
2260  auto Call = cast<Instruction>(User);
2261 
2262  auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);
2263 
2264  // Use the returned slot address as the call argument.
2265  Use.set(Addr);
2266  }
2267 
2268  // All the uses should be loads and stores now.
2269  assert(isAllocaPromotable(Alloca));
2270 }
2271 
2272 /// "Eliminate" a swifterror argument by reducing it to the alloca case
2273 /// and then loading and storing in the prologue and epilog.
2274 ///
2275 /// The argument keeps the swifterror flag.
2277  coro::Shape &Shape,
2278  SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
2279  IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrDbg());
2280 
2281  auto ArgTy = cast<PointerType>(Arg.getType());
2282  auto ValueTy = ArgTy->getElementType();
2283 
2284  // Reduce to the alloca case:
2285 
2286  // Create an alloca and replace all uses of the arg with it.
2287  auto Alloca = Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());
2288  Arg.replaceAllUsesWith(Alloca);
2289 
2290  // Set an initial value in the alloca. swifterror is always null on entry.
2291  auto InitialValue = Constant::getNullValue(ValueTy);
2292  Builder.CreateStore(InitialValue, Alloca);
2293 
2294  // Find all the suspends in the function and save and restore around them.
2295  for (auto Suspend : Shape.CoroSuspends) {
2296  (void) emitSetAndGetSwiftErrorValueAround(Suspend, Alloca, Shape);
2297  }
2298 
2299  // Find all the coro.ends in the function and restore the error value.
2300  for (auto End : Shape.CoroEnds) {
2301  Builder.SetInsertPoint(End);
2302  auto FinalValue = Builder.CreateLoad(ValueTy, Alloca);
2303  (void) emitSetSwiftErrorValue(Builder, FinalValue, Shape);
2304  }
2305 
2306  // Now we can use the alloca logic.
2307  AllocasToPromote.push_back(Alloca);
2308  eliminateSwiftErrorAlloca(F, Alloca, Shape);
2309 }
2310 
2311 /// Eliminate all problematic uses of swifterror arguments and allocas
2312 /// from the function. We'll fix them up later when splitting the function.
2314  SmallVector<AllocaInst*, 4> AllocasToPromote;
2315 
2316  // Look for a swifterror argument.
2317  for (auto &Arg : F.args()) {
2318  if (!Arg.hasSwiftErrorAttr()) continue;
2319 
2320  eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
2321  break;
2322  }
2323 
2324  // Look for swifterror allocas.
2325  for (auto &Inst : F.getEntryBlock()) {
2326  auto Alloca = dyn_cast<AllocaInst>(&Inst);
2327  if (!Alloca || !Alloca->isSwiftError()) continue;
2328 
2329  // Clear the swifterror flag.
2330  Alloca->setSwiftError(false);
2331 
2332  AllocasToPromote.push_back(Alloca);
2333  eliminateSwiftErrorAlloca(F, Alloca, Shape);
2334  }
2335 
2336  // If we have any allocas to promote, compute a dominator tree and
2337  // promote them en masse.
2338  if (!AllocasToPromote.empty()) {
2339  DominatorTree DT(F);
2340  PromoteMemToReg(AllocasToPromote, DT);
2341  }
2342 }
2343 
2344 /// retcon and retcon.once conventions assume that all spill uses can be sunk
2345 /// after the coro.begin intrinsic.
2347  const FrameDataInfo &FrameData,
2348  CoroBeginInst *CoroBegin) {
2349  DominatorTree Dom(F);
2350 
2353 
2354  // Collect all users that precede coro.begin.
2355  for (auto *Def : FrameData.getAllDefs()) {
2356  for (User *U : Def->users()) {
2357  auto Inst = cast<Instruction>(U);
2358  if (Inst->getParent() != CoroBegin->getParent() ||
2359  Dom.dominates(CoroBegin, Inst))
2360  continue;
2361  if (ToMove.insert(Inst))
2362  Worklist.push_back(Inst);
2363  }
2364  }
2365  // Recursively collect users before coro.begin.
2366  while (!Worklist.empty()) {
2367  auto *Def = Worklist.pop_back_val();
2368  for (User *U : Def->users()) {
2369  auto Inst = cast<Instruction>(U);
2370  if (Dom.dominates(CoroBegin, Inst))
2371  continue;
2372  if (ToMove.insert(Inst))
2373  Worklist.push_back(Inst);
2374  }
2375  }
2376 
2377  // Sort by dominance.
2378  SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
2379  llvm::sort(InsertionList, [&Dom](Instruction *A, Instruction *B) -> bool {
2380  // If a dominates b it should preceed (<) b.
2381  return Dom.dominates(A, B);
2382  });
2383 
2384  Instruction *InsertPt = CoroBegin->getNextNode();
2385  for (Instruction *Inst : InsertionList)
2386  Inst->moveBefore(InsertPt);
2387 }
2388 
2389 /// For each local variable that all of its user are only used inside one of
2390 /// suspended region, we sink their lifetime.start markers to the place where
2391 /// after the suspend block. Doing so minimizes the lifetime of each variable,
2392 /// hence minimizing the amount of data we end up putting on the frame.
2394  SuspendCrossingInfo &Checker) {
2395  DominatorTree DT(F);
2396 
2397  // Collect all possible basic blocks which may dominate all uses of allocas.
2399  DomSet.insert(&F.getEntryBlock());
2400  for (auto *CSI : Shape.CoroSuspends) {
2401  BasicBlock *SuspendBlock = CSI->getParent();
2402  assert(isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() &&
2403  "should have split coro.suspend into its own block");
2404  DomSet.insert(SuspendBlock->getSingleSuccessor());
2405  }
2406 
2407  for (Instruction &I : instructions(F)) {
2408  AllocaInst* AI = dyn_cast<AllocaInst>(&I);
2409  if (!AI)
2410  continue;
2411 
2412  for (BasicBlock *DomBB : DomSet) {
2413  bool Valid = true;
2415 
2416  auto isLifetimeStart = [](Instruction* I) {
2417  if (auto* II = dyn_cast<IntrinsicInst>(I))
2418  return II->getIntrinsicID() == Intrinsic::lifetime_start;
2419  return false;
2420  };
2421 
2422  auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
2423  if (isLifetimeStart(U)) {
2424  Lifetimes.push_back(U);
2425  return true;
2426  }
2427  if (!U->hasOneUse() || U->stripPointerCasts() != AI)
2428  return false;
2429  if (isLifetimeStart(U->user_back())) {
2430  Lifetimes.push_back(U->user_back());
2431  return true;
2432  }
2433  return false;
2434  };
2435 
2436  for (User *U : AI->users()) {
2437  Instruction *UI = cast<Instruction>(U);
2438  // For all users except lifetime.start markers, if they are all
2439  // dominated by one of the basic blocks and do not cross
2440  // suspend points as well, then there is no need to spill the
2441  // instruction.
2442  if (!DT.dominates(DomBB, UI->getParent()) ||
2443  Checker.isDefinitionAcrossSuspend(DomBB, UI)) {
2444  // Skip lifetime.start, GEP and bitcast used by lifetime.start
2445  // markers.
2446  if (collectLifetimeStart(UI, AI))
2447  continue;
2448  Valid = false;
2449  break;
2450  }
2451  }
2452  // Sink lifetime.start markers to dominate block when they are
2453  // only used outside the region.
2454  if (Valid && Lifetimes.size() != 0) {
2455  // May be AI itself, when the type of AI is i8*
2456  auto *NewBitCast = [&](AllocaInst *AI) -> Value* {
2457  if (isa<AllocaInst>(Lifetimes[0]->getOperand(1)))
2458  return AI;
2459  auto *Int8PtrTy = Type::getInt8PtrTy(F.getContext());
2460  return CastInst::Create(Instruction::BitCast, AI, Int8PtrTy, "",
2461  DomBB->getTerminator());
2462  }(AI);
2463 
2464  auto *NewLifetime = Lifetimes[0]->clone();
2465  NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(1), NewBitCast);
2466  NewLifetime->insertBefore(DomBB->getTerminator());
2467 
2468  // All the outsided lifetime.start markers are no longer necessary.
2469  for (Instruction *S : Lifetimes)
2470  S->eraseFromParent();
2471 
2472  break;
2473  }
2474  }
2475  }
2476 }
2477 
2479  const SuspendCrossingInfo &Checker,
2480  SmallVectorImpl<AllocaInfo> &Allocas) {
2481  for (Instruction &I : instructions(F)) {
2482  auto *AI = dyn_cast<AllocaInst>(&I);
2483  if (!AI)
2484  continue;
2485  // The PromiseAlloca will be specially handled since it needs to be in a
2486  // fixed position in the frame.
2487  if (AI == Shape.SwitchLowering.PromiseAlloca) {
2488  continue;
2489  }
2490  DominatorTree DT(F);
2491  AllocaUseVisitor Visitor{F.getParent()->getDataLayout(), DT,
2492  *Shape.CoroBegin, Checker};
2493  Visitor.visitPtr(*AI);
2494  if (!Visitor.getShouldLiveOnFrame())
2495  continue;
2496  Allocas.emplace_back(AI, Visitor.getAliasesCopy(),
2497  Visitor.getMayWriteBeforeCoroBegin());
2498  }
2499 }
2500 
2503  DbgVariableIntrinsic *DVI, bool ReuseFrameSlot) {
2504  Function *F = DVI->getFunction();
2505  IRBuilder<> Builder(F->getContext());
2506  auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
2507  while (isa<IntrinsicInst>(InsertPt))
2508  ++InsertPt;
2509  Builder.SetInsertPoint(&F->getEntryBlock(), InsertPt);
2510  DIExpression *Expr = DVI->getExpression();
2511  // Follow the pointer arithmetic all the way to the incoming
2512  // function argument and convert into a DIExpression.
2513  bool OutermostLoad = true;
2514  Value *Storage = DVI->getVariableLocationOp(0);
2515  Value *OriginalStorage = Storage;
2516  while (Storage) {
2517  if (auto *LdInst = dyn_cast<LoadInst>(Storage)) {
2518  Storage = LdInst->getOperand(0);
2519  // FIXME: This is a heuristic that works around the fact that
2520  // LLVM IR debug intrinsics cannot yet distinguish between
2521  // memory and value locations: Because a dbg.declare(alloca) is
2522  // implicitly a memory location no DW_OP_deref operation for the
2523  // last direct load from an alloca is necessary. This condition
2524  // effectively drops the *last* DW_OP_deref in the expression.
2525  if (!OutermostLoad)
2526  Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2527  OutermostLoad = false;
2528  } else if (auto *StInst = dyn_cast<StoreInst>(Storage)) {
2529  Storage = StInst->getOperand(0);
2530  } else if (auto *GEPInst = dyn_cast<GetElementPtrInst>(Storage)) {
2531  SmallVector<Value *> AdditionalValues;
2532  DIExpression *SalvagedExpr = llvm::salvageDebugInfoImpl(
2533  *GEPInst, Expr,
2534  /*WithStackValue=*/false, 0, AdditionalValues);
2535  // Debug declares cannot currently handle additional location
2536  // operands.
2537  if (!SalvagedExpr || !AdditionalValues.empty())
2538  break;
2539  Expr = SalvagedExpr;
2540  Storage = GEPInst->getOperand(0);
2541  } else if (auto *BCInst = dyn_cast<llvm::BitCastInst>(Storage))
2542  Storage = BCInst->getOperand(0);
2543  else
2544  break;
2545  }
2546  if (!Storage)
2547  return;
2548 
2549  // Store a pointer to the coroutine frame object in an alloca so it
2550  // is available throughout the function when producing unoptimized
2551  // code. Extending the lifetime this way is correct because the
2552  // variable has been declared by a dbg.declare intrinsic.
2553  //
2554  // Avoid to create the alloca would be eliminated by optimization
2555  // passes and the corresponding dbg.declares would be invalid.
2556  if (!ReuseFrameSlot && !EnableReuseStorageInFrame)
2557  if (auto *Arg = dyn_cast<llvm::Argument>(Storage)) {
2558  auto &Cached = DbgPtrAllocaCache[Storage];
2559  if (!Cached) {
2560  Cached = Builder.CreateAlloca(Storage->getType(), 0, nullptr,
2561  Arg->getName() + ".debug");
2562  Builder.CreateStore(Storage, Cached);
2563  }
2564  Storage = Cached;
2565  // FIXME: LLVM lacks nuanced semantics to differentiate between
2566  // memory and direct locations at the IR level. The backend will
2567  // turn a dbg.declare(alloca, ..., DIExpression()) into a memory
2568  // location. Thus, if there are deref and offset operations in the
2569  // expression, we need to add a DW_OP_deref at the *start* of the
2570  // expression to first load the contents of the alloca before
2571  // adjusting it with the expression.
2572  if (Expr && Expr->isComplex())
2573  Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2574  }
2575 
2576  DVI->replaceVariableLocationOp(OriginalStorage, Storage);
2577  DVI->setExpression(Expr);
2578  /// It makes no sense to move the dbg.value intrinsic.
2579  if (!isa<DbgValueInst>(DVI)) {
2580  if (auto *InsertPt = dyn_cast<Instruction>(Storage))
2581  DVI->moveAfter(InsertPt);
2582  else if (isa<Argument>(Storage))
2583  DVI->moveAfter(F->getEntryBlock().getFirstNonPHI());
2584  }
2585 }
2586 
2588  // Don't eliminate swifterror in async functions that won't be split.
2589  if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2591 
2592  if (Shape.ABI == coro::ABI::Switch &&
2595  }
2596 
2597  // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
2598  // intrinsics are in their own blocks to simplify the logic of building up
2599  // SuspendCrossing data.
2600  for (auto *CSI : Shape.CoroSuspends) {
2601  if (auto *Save = CSI->getCoroSave())
2602  splitAround(Save, "CoroSave");
2603  splitAround(CSI, "CoroSuspend");
2604  }
2605 
2606  // Put CoroEnds into their own blocks.
2607  for (AnyCoroEndInst *CE : Shape.CoroEnds) {
2608  splitAround(CE, "CoroEnd");
2609 
2610  // Emit the musttail call function in a new block before the CoroEnd.
2611  // We do this here so that the right suspend crossing info is computed for
2612  // the uses of the musttail call function call. (Arguments to the coro.end
2613  // instructions would be ignored)
2614  if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(CE)) {
2615  auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
2616  if (!MustTailCallFn)
2617  continue;
2618  IRBuilder<> Builder(AsyncEnd);
2619  SmallVector<Value *, 8> Args(AsyncEnd->args());
2621  auto *Call = createMustTailCall(AsyncEnd->getDebugLoc(), MustTailCallFn,
2622  Arguments, Builder);
2623  splitAround(Call, "MustTailCall.Before.CoroEnd");
2624  }
2625  }
2626 
2627  // Later code makes structural assumptions about single predecessors phis e.g
2628  // that they are not live accross a suspend point.
2630 
2631  // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
2632  // never has its definition separated from the PHI by the suspend point.
2633  rewritePHIs(F);
2634 
2635  // Build suspend crossing info.
2636  SuspendCrossingInfo Checker(F, Shape);
2637 
2638  IRBuilder<> Builder(F.getContext());
2639  FrameDataInfo FrameData;
2641  SmallVector<Instruction*, 4> DeadInstructions;
2642 
2643  {
2644  SpillInfo Spills;
2645  for (int Repeat = 0; Repeat < 4; ++Repeat) {
2646  // See if there are materializable instructions across suspend points.
2647  for (Instruction &I : instructions(F))
2648  if (materializable(I)) {
2649  for (User *U : I.users())
2650  if (Checker.isDefinitionAcrossSuspend(I, U))
2651  Spills[&I].push_back(cast<Instruction>(U));
2652 
2653  // Manually add dbg.value metadata uses of I.
2655  findDbgValues(DVIs, &I);
2656  for (auto *DVI : DVIs)
2657  if (Checker.isDefinitionAcrossSuspend(I, DVI))
2658  Spills[&I].push_back(DVI);
2659  }
2660 
2661  if (Spills.empty())
2662  break;
2663 
2664  // Rewrite materializable instructions to be materialized at the use
2665  // point.
2666  LLVM_DEBUG(dumpSpills("Materializations", Spills));
2668  Spills.clear();
2669  }
2670  }
2671 
2672  sinkLifetimeStartMarkers(F, Shape, Checker);
2673  if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2674  collectFrameAllocas(F, Shape, Checker, FrameData.Allocas);
2675  LLVM_DEBUG(dumpAllocas(FrameData.Allocas));
2676 
2677  // Collect the spills for arguments and other not-materializable values.
2678  for (Argument &A : F.args())
2679  for (User *U : A.users())
2680  if (Checker.isDefinitionAcrossSuspend(A, U))
2681  FrameData.Spills[&A].push_back(cast<Instruction>(U));
2682 
2683  for (Instruction &I : instructions(F)) {
2684  // Values returned from coroutine structure intrinsics should not be part
2685  // of the Coroutine Frame.
2687  continue;
2688 
2689  // The Coroutine Promise always included into coroutine frame, no need to
2690  // check for suspend crossing.
2691  if (Shape.ABI == coro::ABI::Switch &&
2693  continue;
2694 
2695  // Handle alloca.alloc specially here.
2696  if (auto AI = dyn_cast<CoroAllocaAllocInst>(&I)) {
2697  // Check whether the alloca's lifetime is bounded by suspend points.
2698  if (isLocalAlloca(AI)) {
2699  LocalAllocas.push_back(AI);
2700  continue;
2701  }
2702 
2703  // If not, do a quick rewrite of the alloca and then add spills of
2704  // the rewritten value. The rewrite doesn't invalidate anything in
2705  // Spills because the other alloca intrinsics have no other operands
2706  // besides AI, and it doesn't invalidate the iteration because we delay
2707  // erasing AI.
2708  auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInstructions);
2709 
2710  for (User *U : Alloc->users()) {
2711  if (Checker.isDefinitionAcrossSuspend(*Alloc, U))
2712  FrameData.Spills[Alloc].push_back(cast<Instruction>(U));
2713  }
2714  continue;
2715  }
2716 
2717  // Ignore alloca.get; we process this as part of coro.alloca.alloc.
2718  if (isa<CoroAllocaGetInst>(I))
2719  continue;
2720 
2721  if (isa<AllocaInst>(I))
2722  continue;
2723 
2724  for (User *U : I.users())
2725  if (Checker.isDefinitionAcrossSuspend(I, U)) {
2726  // We cannot spill a token.
2727  if (I.getType()->isTokenTy())
2729  "token definition is separated from the use by a suspend point");
2730  FrameData.Spills[&I].push_back(cast<Instruction>(U));
2731  }
2732  }
2733 
2734  // We don't want the layout of coroutine frame to be affected
2735  // by debug information. So we only choose to salvage DbgValueInst for
2736  // whose value is already in the frame.
2737  // We would handle the dbg.values for allocas specially
2738  for (auto &Iter : FrameData.Spills) {
2739  auto *V = Iter.first;
2741  findDbgValues(DVIs, V);
2742  llvm::for_each(DVIs, [&](DbgValueInst *DVI) {
2743  if (Checker.isDefinitionAcrossSuspend(*V, DVI))
2744  FrameData.Spills[V].push_back(DVI);
2745  });
2746  }
2747 
2748  LLVM_DEBUG(dumpSpills("Spills", FrameData.Spills));
2749  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
2750  Shape.ABI == coro::ABI::Async)
2752  Shape.FrameTy = buildFrameType(F, Shape, FrameData);
2754  // For now, this works for C++ programs only.
2755  buildFrameDebugInfo(F, Shape, FrameData);
2756  insertSpills(FrameData, Shape);
2757  lowerLocalAllocas(LocalAllocas, DeadInstructions);
2758 
2759  for (auto I : DeadInstructions)
2760  I->eraseFromParent();
2761 }
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:2013
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:1547
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:274
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:102
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:491
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
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::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:1561
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
solveDIType
static DIType * solveDIType(DIBuilder &Builder, Type *Ty, DataLayout &Layout, DIScope *Scope, unsigned LineNum, DenseMap< Type *, DIType * > &DITypeCache)
Definition: CoroFrame.cpp:843
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:1336
eliminateSwiftError
static void eliminateSwiftError(Function &F, coro::Shape &Shape)
Eliminate all problematic uses of swifterror arguments and allocas from the function.
Definition: CoroFrame.cpp:2313
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:228
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:2026
llvm::Function
Definition: Function.h:61
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:1657
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:2197
llvm::DataLayout::getTypeSizeInBits
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:655
llvm::StructType::setBody
void setBody(ArrayRef< Type * > Elements, bool isPacked=false)
Specify a body for an opaque identified type.
Definition: Type.cpp:411
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5194
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:2879
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:1785
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:671
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
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
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:2276
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:294
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:381
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:852
collectFrameAllocas
static void collectFrameAllocas(Function &F, coro::Shape &Shape, const SuspendCrossingInfo &Checker, SmallVectorImpl< AllocaInfo > &Allocas)
Definition: CoroFrame.cpp:2478
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:1013
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::CallBase::getNumArgOperands
unsigned getNumArgOperands() const
Definition: InstrTypes.h:1336
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2557
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:2076
llvm::coro::buildCoroutineFrame
void buildCoroutineFrame(Function &F, Shape &Shape)
Definition: CoroFrame.cpp:2587
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:122
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:759
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:1860
llvm::coro::Shape::RetconLoweringStorage::IsFrameInlineInStorage
bool IsFrameInlineInStorage
Definition: CoroInternal.h:146
rewriteMaterializableInstructions
static void rewriteMaterializableInstructions(IRBuilder<> &IRB, const SpillInfo &Spills)
Definition: CoroFrame.cpp:1976
StackLifetime.h
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5234
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:2182
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:3053
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:2095
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:343
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:2157
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:639
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:249
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:2245
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::DataLayout::getPrefTypeAlignment
unsigned getPrefTypeAlignment(Type *Ty) const
Returns the preferred stack/global alignment for the specified type.
Definition: DataLayout.cpp:826
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:364
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:2346
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:212
SmallVectorThreshold
@ SmallVectorThreshold
Definition: CoroFrame.cpp:52
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:1065
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:2393
llvm::None
const NoneType None
Definition: None.h:23
llvm::coro::Shape::FrameAlign
Align FrameAlign
Definition: CoroInternal.h:123
llvm::salvageDebugInfoImpl
DIExpression * salvageDebugInfoImpl(Instruction &I, DIExpression *DIExpr, bool StackVal, unsigned LocNo, SmallVectorImpl< Value * > &AdditionalValues)
Given an instruction I and DIExpression DIExpr operating on it, write the effects of I into the retur...
Definition: Local.cpp:1893
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:3106
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:201
llvm::PtrUseVisitor::visitMemIntrinsic
void visitMemIntrinsic(MemIntrinsic &I)
Definition: PtrUseVisitor.h:283
isCoroutineStructureIntrinsic
static bool isCoroutineStructureIntrinsic(Instruction &I)
Definition: CoroFrame.cpp:1969
createFramePtr
static void createFramePtr(coro::Shape &Shape)
Definition: CoroFrame.cpp:1484
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:860
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:4428
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:1094
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::SwitchInst::setDefaultDest
void setDefaultDest(BasicBlock *DefaultCase)
Definition: Instructions.h:3418
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:1540
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
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:2777
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:798
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:920
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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:631
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:1646
llvm::coro::Shape::FramePtr
Instruction * FramePtr
Definition: CoroInternal.h:125
materializable
static bool materializable(Instruction &V)
Definition: CoroFrame.cpp:1962
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:2039
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1740
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
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:2215
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:1528
llvm::dwarf::SourceLanguage
SourceLanguage
Definition: Dwarf.h:200
llvm::DICompositeType
Composite types.
Definition: DebugInfoMetadata.h:1051
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:212
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:681
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:2501
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:520
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::AllocaInst::getAlignment
unsigned getAlignment() const
Definition: Instructions.h:129
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:979
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:1378
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:369
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:1767
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:1515
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:297
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:148
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:326
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:675
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:1574
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:32
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:476
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:1472
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:314
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
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:1186
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)
Create debugging information entry for a member.
Definition: DIBuilder.cpp:348
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:1488
Arguments
AMDGPU Lower Kernel Arguments
Definition: AMDGPULowerKernelArguments.cpp:244
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:1728
llvm::DIBuilder::getOrCreateArray
DINodeArray getOrCreateArray(ArrayRef< Metadata * > Elements)
Get a DINodeArray, create one if required.
Definition: DIBuilder.cpp:642
llvm::Type::getPointerTo
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
Definition: Type.cpp:738
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:1878
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:4312
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:926
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:2113
isSuspendBlock
static bool isSuspendBlock(BasicBlock *BB)
Definition: CoroFrame.cpp:2031
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:222
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:372
isLocalAlloca
static bool isLocalAlloca(CoroAllocaAllocInst *AI)
Is the given alloca "local", i.e.
Definition: CoroFrame.cpp:2062
Dominators.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1338
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:656
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:2627
llvm::CoroBeginInst
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:420
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1802
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:327
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:1532
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:267
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:3206
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:370
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:2035
llvm::cl::desc
Definition: CommandLine.h:414
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:221
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:4250
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
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