Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Coroutines/CoroFrame.cpp
Line
Count
Source (jump to first uncovered line)
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
// TODO: pack values tightly using liveness info.
17
//===----------------------------------------------------------------------===//
18
19
#include "CoroInternal.h"
20
#include "llvm/ADT/BitVector.h"
21
#include "llvm/Transforms/Utils/Local.h"
22
#include "llvm/Config/llvm-config.h"
23
#include "llvm/IR/CFG.h"
24
#include "llvm/IR/Dominators.h"
25
#include "llvm/IR/IRBuilder.h"
26
#include "llvm/IR/InstIterator.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/MathExtras.h"
29
#include "llvm/Support/circular_raw_ostream.h"
30
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
31
32
using namespace llvm;
33
34
// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
35
// "coro-frame", which results in leaner debug spew.
36
#define DEBUG_TYPE "coro-suspend-crossing"
37
38
enum { SmallVectorThreshold = 32 };
39
40
// Provides two way mapping between the blocks and numbers.
41
namespace {
42
class BlockToIndexMapping {
43
  SmallVector<BasicBlock *, SmallVectorThreshold> V;
44
45
public:
46
37
  size_t size() const { return V.size(); }
47
48
37
  BlockToIndexMapping(Function &F) {
49
37
    for (BasicBlock &BB : F)
50
499
      V.push_back(&BB);
51
37
    llvm::sort(V);
52
37
  }
53
54
3.59k
  size_t blockToIndex(BasicBlock *BB) const {
55
3.59k
    auto *I = llvm::lower_bound(V, BB);
56
3.59k
    assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
57
3.59k
    return I - V.begin();
58
3.59k
  }
59
60
2.26k
  BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
61
};
62
} // end anonymous namespace
63
64
// The SuspendCrossingInfo maintains data that allows to answer a question
65
// whether given two BasicBlocks A and B there is a path from A to B that
66
// passes through a suspend point.
67
//
68
// For every basic block 'i' it maintains a BlockData that consists of:
69
//   Consumes:  a bit vector which contains a set of indices of blocks that can
70
//              reach block 'i'
71
//   Kills: a bit vector which contains a set of indices of blocks that can
72
//          reach block 'i', but one of the path will cross a suspend point
73
//   Suspend: a boolean indicating whether block 'i' contains a suspend point.
74
//   End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
75
//
76
namespace {
77
struct SuspendCrossingInfo {
78
  BlockToIndexMapping Mapping;
79
80
  struct BlockData {
81
    BitVector Consumes;
82
    BitVector Kills;
83
    bool Suspend = false;
84
    bool End = false;
85
  };
86
  SmallVector<BlockData, SmallVectorThreshold> Block;
87
88
2.26k
  iterator_range<succ_iterator> successors(BlockData const &BD) const {
89
2.26k
    BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
90
2.26k
    return llvm::successors(BB);
91
2.26k
  }
92
93
117
  BlockData &getBlockData(BasicBlock *BB) {
94
117
    return Block[Mapping.blockToIndex(BB)];
95
117
  }
96
97
  void dump() const;
98
  void dump(StringRef Label, BitVector const &BV) const;
99
100
  SuspendCrossingInfo(Function &F, coro::Shape &Shape);
101
102
417
  bool hasPathCrossingSuspendPoint(BasicBlock *DefBB, BasicBlock *UseBB) const {
103
417
    size_t const DefIndex = Mapping.blockToIndex(DefBB);
104
417
    size_t const UseIndex = Mapping.blockToIndex(UseBB);
105
417
106
417
    assert(Block[UseIndex].Consumes[DefIndex] && "use must consume def");
107
417
    bool const Result = Block[UseIndex].Kills[DefIndex];
108
417
    LLVM_DEBUG(dbgs() << UseBB->getName() << " => " << DefBB->getName()
109
417
                      << " answer is " << Result << "\n");
110
417
    return Result;
111
417
  }
112
113
487
  bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
114
487
    auto *I = cast<Instruction>(U);
115
487
116
487
    // We rewrote PHINodes, so that only the ones with exactly one incoming
117
487
    // value need to be analyzed.
118
487
    if (auto *PN = dyn_cast<PHINode>(I))
119
105
      if (PN->getNumIncomingValues() > 1)
120
70
        return false;
121
417
122
417
    BasicBlock *UseBB = I->getParent();
123
417
    return hasPathCrossingSuspendPoint(DefBB, UseBB);
124
417
  }
125
126
39
  bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
127
39
    return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
128
39
  }
129
130
448
  bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
131
448
    return isDefinitionAcrossSuspend(I.getParent(), U);
132
448
  }
133
};
134
} // end anonymous namespace
135
136
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
137
LLVM_DUMP_METHOD void SuspendCrossingInfo::dump(StringRef Label,
138
                                                BitVector const &BV) const {
139
  dbgs() << Label << ":";
140
  for (size_t I = 0, N = BV.size(); I < N; ++I)
141
    if (BV[I])
142
      dbgs() << " " << Mapping.indexToBlock(I)->getName();
143
  dbgs() << "\n";
144
}
145
146
LLVM_DUMP_METHOD void SuspendCrossingInfo::dump() const {
147
  for (size_t I = 0, N = Block.size(); I < N; ++I) {
148
    BasicBlock *const B = Mapping.indexToBlock(I);
149
    dbgs() << B->getName() << ":\n";
150
    dump("   Consumes", Block[I].Consumes);
151
    dump("      Kills", Block[I].Kills);
152
  }
153
  dbgs() << "\n";
154
}
155
#endif
156
157
SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
158
37
    : Mapping(F) {
159
37
  const size_t N = Mapping.size();
160
37
  Block.resize(N);
161
37
162
37
  // Initialize every block so that it consumes itself
163
536
  for (size_t I = 0; I < N; 
++I499
) {
164
499
    auto &B = Block[I];
165
499
    B.Consumes.resize(N);
166
499
    B.Kills.resize(N);
167
499
    B.Consumes.set(I);
168
499
  }
169
37
170
37
  // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
171
37
  // the code beyond coro.end is reachable during initial invocation of the
172
37
  // coroutine.
173
37
  for (auto *CE : Shape.CoroEnds)
174
39
    getBlockData(CE->getParent()).End = true;
175
37
176
37
  // Mark all suspend blocks and indicate that they kill everything they
177
37
  // consume. Note, that crossing coro.save also requires a spill, as any code
178
37
  // between coro.save and coro.suspend may resume the coroutine and all of the
179
37
  // state needs to be saved by that time.
180
78
  auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
181
78
    BasicBlock *SuspendBlock = BarrierInst->getParent();
182
78
    auto &B = getBlockData(SuspendBlock);
183
78
    B.Suspend = true;
184
78
    B.Kills |= B.Consumes;
185
78
  };
186
39
  for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
187
39
    markSuspendBlock(CSI);
188
39
    markSuspendBlock(CSI->getCoroSave());
189
39
  }
190
37
191
37
  // Iterate propagating consumes and kills until they stop changing.
192
37
  int Iteration = 0;
193
37
  (void)Iteration;
194
37
195
37
  bool Changed;
196
159
  do {
197
159
    LLVM_DEBUG(dbgs() << "iteration " << ++Iteration);
198
159
    LLVM_DEBUG(dbgs() << "==============\n");
199
159
200
159
    Changed = false;
201
2.42k
    for (size_t I = 0; I < N; 
++I2.26k
) {
202
2.26k
      auto &B = Block[I];
203
2.64k
      for (BasicBlock *SI : successors(B)) {
204
2.64k
205
2.64k
        auto SuccNo = Mapping.blockToIndex(SI);
206
2.64k
207
2.64k
        // Saved Consumes and Kills bitsets so that it is easy to see
208
2.64k
        // if anything changed after propagation.
209
2.64k
        auto &S = Block[SuccNo];
210
2.64k
        auto SavedConsumes = S.Consumes;
211
2.64k
        auto SavedKills = S.Kills;
212
2.64k
213
2.64k
        // Propagate Kills and Consumes from block B into its successor S.
214
2.64k
        S.Consumes |= B.Consumes;
215
2.64k
        S.Kills |= B.Kills;
216
2.64k
217
2.64k
        // If block B is a suspend block, it should propagate kills into the
218
2.64k
        // its successor for every block B consumes.
219
2.64k
        if (B.Suspend) {
220
352
          S.Kills |= B.Consumes;
221
352
        }
222
2.64k
        if (S.Suspend) {
223
352
          // If block S is a suspend block, it should kill all of the blocks it
224
352
          // consumes.
225
352
          S.Kills |= S.Consumes;
226
2.29k
        } else if (S.End) {
227
165
          // If block S is an end block, it should not propagate kills as the
228
165
          // blocks following coro.end() are reached during initial invocation
229
165
          // of the coroutine while all the data are still available on the
230
165
          // stack or in the registers.
231
165
          S.Kills.reset();
232
2.12k
        } else {
233
2.12k
          // This is reached when S block it not Suspend nor coro.end and it
234
2.12k
          // need to make sure that it is not in the kill set.
235
2.12k
          S.Kills.reset(SuccNo);
236
2.12k
        }
237
2.64k
238
2.64k
        // See if anything changed.
239
2.64k
        Changed |= (S.Kills != SavedKills) || 
(S.Consumes != SavedConsumes)1.97k
;
240
2.64k
241
2.64k
        if (S.Kills != SavedKills) {
242
672
          LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()
243
672
                            << "\n");
244
672
          LLVM_DEBUG(dump("S.Kills", S.Kills));
245
672
          LLVM_DEBUG(dump("SavedKills", SavedKills));
246
672
        }
247
2.64k
        if (S.Consumes != SavedConsumes) {
248
1.18k
          LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n");
249
1.18k
          LLVM_DEBUG(dump("S.Consume", S.Consumes));
250
1.18k
          LLVM_DEBUG(dump("SavedCons", SavedConsumes));
251
1.18k
        }
252
2.64k
      }
253
2.26k
    }
254
159
  } while (Changed);
255
37
  LLVM_DEBUG(dump());
256
37
}
257
258
#undef DEBUG_TYPE // "coro-suspend-crossing"
259
#define DEBUG_TYPE "coro-frame"
260
261
// We build up the list of spills for every case where a use is separated
262
// from the definition by a suspend point.
263
264
namespace {
265
class Spill {
266
  Value *Def = nullptr;
267
  Instruction *User = nullptr;
268
  unsigned FieldNo = 0;
269
270
public:
271
77
  Spill(Value *Def, llvm::User *U) : Def(Def), User(cast<Instruction>(U)) {}
272
273
349
  Value *def() const { return Def; }
274
143
  Instruction *user() const { return User; }
275
147
  BasicBlock *userBlock() const { return User->getParent(); }
276
277
  // Note that field index is stored in the first SpillEntry for a particular
278
  // definition. Subsequent mentions of a defintion do not have fieldNo
279
  // assigned. This works out fine as the users of Spills capture the info about
280
  // the definition the first time they encounter it. Consider refactoring
281
  // SpillInfo into two arrays to normalize the spill representation.
282
41
  unsigned fieldIndex() const {
283
41
    assert(FieldNo && "Accessing unassigned field");
284
41
    return FieldNo;
285
41
  }
286
41
  void setFieldIndex(unsigned FieldNumber) {
287
41
    assert(!FieldNo && "Reassigning field number");
288
41
    FieldNo = FieldNumber;
289
41
  }
290
};
291
} // namespace
292
293
// Note that there may be more than one record with the same value of Def in
294
// the SpillInfo vector.
295
using SpillInfo = SmallVector<Spill, 8>;
296
297
#ifndef NDEBUG
298
static void dump(StringRef Title, SpillInfo const &Spills) {
299
  dbgs() << "------------- " << Title << "--------------\n";
300
  Value *CurrentValue = nullptr;
301
  for (auto const &E : Spills) {
302
    if (CurrentValue != E.def()) {
303
      CurrentValue = E.def();
304
      CurrentValue->dump();
305
    }
306
    dbgs() << "   user: ";
307
    E.user()->dump();
308
  }
309
}
310
#endif
311
312
namespace {
313
// We cannot rely solely on natural alignment of a type when building a
314
// coroutine frame and if the alignment specified on the Alloca instruction
315
// differs from the natural alignment of the alloca type we will need to insert
316
// padding.
317
struct PaddingCalculator {
318
  const DataLayout &DL;
319
  LLVMContext &Context;
320
  unsigned StructSize = 0;
321
322
  PaddingCalculator(LLVMContext &Context, DataLayout const &DL)
323
37
      : DL(DL), Context(Context) {}
324
325
  // Replicate the logic from IR/DataLayout.cpp to match field offset
326
  // computation for LLVM structs.
327
190
  void addType(Type *Ty) {
328
190
    unsigned TyAlign = DL.getABITypeAlignment(Ty);
329
190
    if ((StructSize & (TyAlign - 1)) != 0)
330
28
      StructSize = alignTo(StructSize, TyAlign);
331
190
332
190
    StructSize += DL.getTypeAllocSize(Ty); // Consume space for this data item.
333
190
  }
334
335
37
  void addTypes(SmallVectorImpl<Type *> const &Types) {
336
37
    for (auto *Ty : Types)
337
148
      addType(Ty);
338
37
  }
339
340
14
  unsigned computePadding(Type *Ty, unsigned ForcedAlignment) {
341
14
    unsigned TyAlign = DL.getABITypeAlignment(Ty);
342
14
    auto Natural = alignTo(StructSize, TyAlign);
343
14
    auto Forced = alignTo(StructSize, ForcedAlignment);
344
14
345
14
    // Return how many bytes of padding we need to insert.
346
14
    if (Natural != Forced)
347
1
      return std::max(Natural, Forced) - StructSize;
348
13
349
13
    // Rely on natural alignment.
350
13
    return 0;
351
13
  }
352
353
  // If padding required, return the padding field type to insert.
354
14
  ArrayType *getPaddingType(Type *Ty, unsigned ForcedAlignment) {
355
14
    if (auto Padding = computePadding(Ty, ForcedAlignment))
356
1
      return ArrayType::get(Type::getInt8Ty(Context), Padding);
357
13
358
13
    return nullptr;
359
13
  }
360
};
361
} // namespace
362
363
// Build a struct that will keep state for an active coroutine.
364
//   struct f.frame {
365
//     ResumeFnTy ResumeFnAddr;
366
//     ResumeFnTy DestroyFnAddr;
367
//     int ResumeIndex;
368
//     ... promise (if present) ...
369
//     ... spills ...
370
//   };
371
static StructType *buildFrameType(Function &F, coro::Shape &Shape,
372
37
                                  SpillInfo &Spills) {
373
37
  LLVMContext &C = F.getContext();
374
37
  const DataLayout &DL = F.getParent()->getDataLayout();
375
37
  PaddingCalculator Padder(C, DL);
376
37
  SmallString<32> Name(F.getName());
377
37
  Name.append(".Frame");
378
37
  StructType *FrameTy = StructType::create(C, Name);
379
37
  auto *FramePtrTy = FrameTy->getPointerTo();
380
37
  auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
381
37
                                 /*isVarArg=*/false);
382
37
  auto *FnPtrTy = FnTy->getPointerTo();
383
37
384
37
  // Figure out how wide should be an integer type storing the suspend index.
385
37
  unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
386
37
  Type *PromiseType = Shape.PromiseAlloca
387
37
                          ? 
Shape.PromiseAlloca->getType()->getElementType()2
388
37
                          : 
Type::getInt1Ty(C)35
;
389
37
  SmallVector<Type *, 8> Types{FnPtrTy, FnPtrTy, PromiseType,
390
37
                               Type::getIntNTy(C, IndexBits)};
391
37
  Value *CurrentDef = nullptr;
392
37
393
37
  Padder.addTypes(Types);
394
37
395
37
  // Create an entry for every spilled value.
396
63
  for (auto &S : Spills) {
397
63
    if (CurrentDef == S.def())
398
22
      continue;
399
41
400
41
    CurrentDef = S.def();
401
41
    // PromiseAlloca was already added to Types array earlier.
402
41
    if (CurrentDef == Shape.PromiseAlloca)
403
0
      continue;
404
41
405
41
    uint64_t Count = 1;
406
41
    Type *Ty = nullptr;
407
41
    if (auto *AI = dyn_cast<AllocaInst>(CurrentDef)) {
408
17
      Ty = AI->getAllocatedType();
409
17
      if (unsigned AllocaAlignment = AI->getAlignment()) {
410
14
        // If alignment is specified in alloca, see if we need to insert extra
411
14
        // padding.
412
14
        if (auto PaddingTy = Padder.getPaddingType(Ty, AllocaAlignment)) {
413
1
          Types.push_back(PaddingTy);
414
1
          Padder.addType(PaddingTy);
415
1
        }
416
14
      }
417
17
      if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize()))
418
17
        Count = CI->getValue().getZExtValue();
419
0
      else
420
0
        report_fatal_error("Coroutines cannot handle non static allocas yet");
421
24
    } else {
422
24
      Ty = CurrentDef->getType();
423
24
    }
424
41
    S.setFieldIndex(Types.size());
425
41
    if (Count == 1)
426
40
      Types.push_back(Ty);
427
1
    else
428
1
      Types.push_back(ArrayType::get(Ty, Count));
429
41
    Padder.addType(Ty);
430
41
  }
431
37
  FrameTy->setBody(Types);
432
37
433
37
  return FrameTy;
434
37
}
435
436
// We need to make room to insert a spill after initial PHIs, but before
437
// catchswitch instruction. Placing it before violates the requirement that
438
// catchswitch, like all other EHPads must be the first nonPHI in a block.
439
//
440
// Split away catchswitch into a separate block and insert in its place:
441
//
442
//   cleanuppad <InsertPt> cleanupret.
443
//
444
// cleanupret instruction will act as an insert point for the spill.
445
1
static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
446
1
  BasicBlock *CurrentBlock = CatchSwitch->getParent();
447
1
  BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
448
1
  CurrentBlock->getTerminator()->eraseFromParent();
449
1
450
1
  auto *CleanupPad =
451
1
      CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
452
1
  auto *CleanupRet =
453
1
      CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
454
1
  return CleanupRet;
455
1
}
456
457
// Replace all alloca and SSA values that are accessed across suspend points
458
// with GetElementPointer from coroutine frame + loads and stores. Create an
459
// AllocaSpillBB that will become the new entry block for the resume parts of
460
// the coroutine:
461
//
462
//    %hdl = coro.begin(...)
463
//    whatever
464
//
465
// becomes:
466
//
467
//    %hdl = coro.begin(...)
468
//    %FramePtr = bitcast i8* hdl to %f.frame*
469
//    br label %AllocaSpillBB
470
//
471
//  AllocaSpillBB:
472
//    ; geps corresponding to allocas that were moved to coroutine frame
473
//    br label PostSpill
474
//
475
//  PostSpill:
476
//    whatever
477
//
478
//
479
37
static Instruction *insertSpills(SpillInfo &Spills, coro::Shape &Shape) {
480
37
  auto *CB = Shape.CoroBegin;
481
37
  LLVMContext &C = CB->getContext();
482
37
  IRBuilder<> Builder(CB->getNextNode());
483
37
  StructType *FrameTy = Shape.FrameTy;
484
37
  PointerType *FramePtrTy = FrameTy->getPointerTo();
485
37
  auto *FramePtr =
486
37
      cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
487
37
488
37
  Value *CurrentValue = nullptr;
489
37
  BasicBlock *CurrentBlock = nullptr;
490
37
  Value *CurrentReload = nullptr;
491
37
  unsigned Index = 0; // Proper field number will be read from field definition.
492
37
493
37
  // We need to keep track of any allocas that need "spilling"
494
37
  // since they will live in the coroutine frame now, all access to them
495
37
  // need to be changed, not just the access across suspend points
496
37
  // we remember allocas and their indices to be handled once we processed
497
37
  // all the spills.
498
37
  SmallVector<std::pair<AllocaInst *, unsigned>, 4> Allocas;
499
37
  // Promise alloca (if present) has a fixed field number (Shape::PromiseField)
500
37
  if (Shape.PromiseAlloca)
501
2
    Allocas.emplace_back(Shape.PromiseAlloca, coro::Shape::PromiseField);
502
37
503
37
  // Create a GEP with the given index into the coroutine frame for the original
504
37
  // value Orig. Appends an extra 0 index for array-allocas, preserving the
505
37
  // original type.
506
75
  auto GetFramePointer = [&](uint32_t Index, Value *Orig) -> Value * {
507
75
    SmallVector<Value *, 3> Indices = {
508
75
        ConstantInt::get(Type::getInt32Ty(C), 0),
509
75
        ConstantInt::get(Type::getInt32Ty(C), Index),
510
75
    };
511
75
512
75
    if (auto *AI = dyn_cast<AllocaInst>(Orig)) {
513
46
      if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize())) {
514
46
        auto Count = CI->getValue().getZExtValue();
515
46
        if (Count > 1) {
516
2
          Indices.push_back(ConstantInt::get(Type::getInt32Ty(C), 0));
517
2
        }
518
46
      } else {
519
0
        report_fatal_error("Coroutines cannot handle non static allocas yet");
520
0
      }
521
75
    }
522
75
523
75
    return Builder.CreateInBoundsGEP(FrameTy, FramePtr, Indices);
524
75
  };
525
37
526
37
  // Create a load instruction to reload the spilled value from the coroutine
527
37
  // frame.
528
56
  auto CreateReload = [&](Instruction *InsertBefore) {
529
56
    assert(Index && "accessing unassigned field number");
530
56
    Builder.SetInsertPoint(InsertBefore);
531
56
532
56
    auto *G = GetFramePointer(Index, CurrentValue);
533
56
    G->setName(CurrentValue->getName() + Twine(".reload.addr"));
534
56
535
56
    return isa<AllocaInst>(CurrentValue)
536
56
               ? 
G27
537
56
               : Builder.CreateLoad(FrameTy->getElementType(Index), G,
538
29
                                    CurrentValue->getName() + Twine(".reload"));
539
56
  };
540
37
541
63
  for (auto const &E : Spills) {
542
63
    // If we have not seen the value, generate a spill.
543
63
    if (CurrentValue != E.def()) {
544
41
      CurrentValue = E.def();
545
41
      CurrentBlock = nullptr;
546
41
      CurrentReload = nullptr;
547
41
548
41
      Index = E.fieldIndex();
549
41
550
41
      if (auto *AI = dyn_cast<AllocaInst>(CurrentValue)) {
551
17
        // Spilled AllocaInst will be replaced with GEP from the coroutine frame
552
17
        // there is no spill required.
553
17
        Allocas.emplace_back(AI, Index);
554
17
        if (!AI->isStaticAlloca())
555
0
          report_fatal_error("Coroutines cannot handle non static allocas yet");
556
24
      } else {
557
24
        // Otherwise, create a store instruction storing the value into the
558
24
        // coroutine frame.
559
24
560
24
        Instruction *InsertPt = nullptr;
561
24
        if (isa<Argument>(CurrentValue)) {
562
11
          // For arguments, we will place the store instruction right after
563
11
          // the coroutine frame pointer instruction, i.e. bitcast of
564
11
          // coro.begin from i8* to %f.frame*.
565
11
          InsertPt = FramePtr->getNextNode();
566
13
        } else if (auto *II = dyn_cast<InvokeInst>(CurrentValue)) {
567
1
          // If we are spilling the result of the invoke instruction, split the
568
1
          // normal edge and insert the spill in the new block.
569
1
          auto NewBB = SplitEdge(II->getParent(), II->getNormalDest());
570
1
          InsertPt = NewBB->getTerminator();
571
12
        } else if (dyn_cast<PHINode>(CurrentValue)) {
572
10
          // Skip the PHINodes and EH pads instructions.
573
10
          BasicBlock *DefBlock = cast<Instruction>(E.def())->getParent();
574
10
          if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
575
1
            InsertPt = splitBeforeCatchSwitch(CSI);
576
9
          else
577
9
            InsertPt = &*DefBlock->getFirstInsertionPt();
578
10
        } else {
579
2
          // For all other values, the spill is placed immediately after
580
2
          // the definition.
581
2
          assert(!cast<Instruction>(E.def())->isTerminator() &&
582
2
                 "unexpected terminator");
583
2
          InsertPt = cast<Instruction>(E.def())->getNextNode();
584
2
        }
585
24
586
24
        Builder.SetInsertPoint(InsertPt);
587
24
        auto *G = Builder.CreateConstInBoundsGEP2_32(
588
24
            FrameTy, FramePtr, 0, Index,
589
24
            CurrentValue->getName() + Twine(".spill.addr"));
590
24
        Builder.CreateStore(CurrentValue, G);
591
24
      }
592
41
    }
593
63
594
63
    // If we have not seen the use block, generate a reload in it.
595
63
    if (CurrentBlock != E.userBlock()) {
596
56
      CurrentBlock = E.userBlock();
597
56
      CurrentReload = CreateReload(&*CurrentBlock->getFirstInsertionPt());
598
56
    }
599
63
600
63
    // If we have a single edge PHINode, remove it and replace it with a reload
601
63
    // from the coroutine frame. (We already took care of multi edge PHINodes
602
63
    // by rewriting them in the rewritePHIs function).
603
63
    if (auto *PN = dyn_cast<PHINode>(E.user())) {
604
5
      assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
605
5
                                                "values in the PHINode");
606
5
      PN->replaceAllUsesWith(CurrentReload);
607
5
      PN->eraseFromParent();
608
5
      continue;
609
5
    }
610
58
611
58
    // Replace all uses of CurrentValue in the current instruction with reload.
612
58
    E.user()->replaceUsesOfWith(CurrentValue, CurrentReload);
613
58
  }
614
37
615
37
  BasicBlock *FramePtrBB = FramePtr->getParent();
616
37
  Shape.AllocaSpillBlock =
617
37
      FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
618
37
  Shape.AllocaSpillBlock->splitBasicBlock(&Shape.AllocaSpillBlock->front(),
619
37
                                          "PostSpill");
620
37
621
37
  Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
622
37
  // If we found any allocas, replace all of their remaining uses with Geps.
623
37
  for (auto &P : Allocas) {
624
19
    auto *G = GetFramePointer(P.second, P.first);
625
19
626
19
    // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G)) here,
627
19
    // as we are changing location of the instruction.
628
19
    G->takeName(P.first);
629
19
    P.first->replaceAllUsesWith(G);
630
19
    P.first->eraseFromParent();
631
19
  }
632
37
  return FramePtr;
633
37
}
634
635
// Sets the unwind edge of an instruction to a particular successor.
636
8
static void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) {
637
8
  if (auto *II = dyn_cast<InvokeInst>(TI))
638
8
    II->setUnwindDest(Succ);
639
0
  else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
640
0
    CS->setUnwindDest(Succ);
641
0
  else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
642
0
    CR->setUnwindDest(Succ);
643
0
  else
644
0
    llvm_unreachable("unexpected terminator instruction");
645
8
}
646
647
// Replaces all uses of OldPred with the NewPred block in all PHINodes in a
648
// block.
649
static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
650
                           BasicBlock *NewPred,
651
8
                           PHINode *LandingPadReplacement) {
652
8
  unsigned BBIdx = 0;
653
16
  for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); 
++I8
) {
654
10
    PHINode *PN = cast<PHINode>(I);
655
10
656
10
    // We manually update the LandingPadReplacement PHINode and it is the last
657
10
    // PHI Node. So, if we find it, we are done.
658
10
    if (LandingPadReplacement == PN)
659
2
      break;
660
8
661
8
    // Reuse the previous value of BBIdx if it lines up.  In cases where we
662
8
    // have multiple phi nodes with *lots* of predecessors, this is a speed
663
8
    // win because we don't have to scan the PHI looking for TIBB.  This
664
8
    // happens because the BB list of PHI nodes are usually in the same
665
8
    // order.
666
8
    if (PN->getIncomingBlock(BBIdx) != OldPred)
667
4
      BBIdx = PN->getBasicBlockIndex(OldPred);
668
8
669
8
    assert(BBIdx != (unsigned)-1 && "Invalid PHI Index!");
670
8
    PN->setIncomingBlock(BBIdx, NewPred);
671
8
  }
672
8
}
673
674
// Uses SplitEdge unless the successor block is an EHPad, in which case do EH
675
// specific handling.
676
static BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
677
                                    LandingPadInst *OriginalPad,
678
60
                                    PHINode *LandingPadReplacement) {
679
60
  auto *PadInst = Succ->getFirstNonPHI();
680
60
  if (!LandingPadReplacement && 
!PadInst->isEHPad()58
)
681
52
    return SplitEdge(BB, Succ);
682
8
683
8
  auto *NewBB = BasicBlock::Create(BB->getContext(), "", BB->getParent(), Succ);
684
8
  setUnwindEdgeTo(BB->getTerminator(), NewBB);
685
8
  updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
686
8
687
8
  if (LandingPadReplacement) {
688
2
    auto *NewLP = OriginalPad->clone();
689
2
    auto *Terminator = BranchInst::Create(Succ, NewBB);
690
2
    NewLP->insertBefore(Terminator);
691
2
    LandingPadReplacement->addIncoming(NewLP, NewBB);
692
2
    return NewBB;
693
2
  }
694
6
  Value *ParentPad = nullptr;
695
6
  if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
696
2
    ParentPad = FuncletPad->getParentPad();
697
4
  else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
698
4
    ParentPad = CatchSwitch->getParentPad();
699
4
  else
700
4
    
llvm_unreachable0
("handling for other EHPads not implemented yet");
701
6
702
6
  auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, "", NewBB);
703
6
  CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
704
6
  return NewBB;
705
6
}
706
707
29
static void rewritePHIs(BasicBlock &BB) {
708
29
  // For every incoming edge we will create a block holding all
709
29
  // incoming values in a single PHI nodes.
710
29
  //
711
29
  // loop:
712
29
  //    %n.val = phi i32[%n, %entry], [%inc, %loop]
713
29
  //
714
29
  // It will create:
715
29
  //
716
29
  // loop.from.entry:
717
29
  //    %n.loop.pre = phi i32 [%n, %entry]
718
29
  //    br %label loop
719
29
  // loop.from.loop:
720
29
  //    %inc.loop.pre = phi i32 [%inc, %loop]
721
29
  //    br %label loop
722
29
  //
723
29
  // After this rewrite, further analysis will ignore any phi nodes with more
724
29
  // than one incoming edge.
725
29
726
29
  // TODO: Simplify PHINodes in the basic block to remove duplicate
727
29
  // predecessors.
728
29
729
29
  LandingPadInst *LandingPad = nullptr;
730
29
  PHINode *ReplPHI = nullptr;
731
29
  if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
732
1
    // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
733
1
    // We replace the original landing pad with a PHINode that will collect the
734
1
    // results from all of them.
735
1
    ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
736
1
    ReplPHI->takeName(LandingPad);
737
1
    LandingPad->replaceAllUsesWith(ReplPHI);
738
1
    // We will erase the original landing pad at the end of this function after
739
1
    // ehAwareSplitEdge cloned it in the transition blocks.
740
1
  }
741
29
742
29
  SmallVector<BasicBlock *, 8> Preds(pred_begin(&BB), pred_end(&BB));
743
60
  for (BasicBlock *Pred : Preds) {
744
60
    auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
745
60
    IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
746
60
    auto *PN = cast<PHINode>(&BB.front());
747
62
    do {
748
62
      int Index = PN->getBasicBlockIndex(IncomingBB);
749
62
      Value *V = PN->getIncomingValue(Index);
750
62
      PHINode *InputV = PHINode::Create(
751
62
          V->getType(), 1, V->getName() + Twine(".") + BB.getName(),
752
62
          &IncomingBB->front());
753
62
      InputV->addIncoming(V, Pred);
754
62
      PN->setIncomingValue(Index, InputV);
755
62
      PN = dyn_cast<PHINode>(PN->getNextNode());
756
62
    } while (PN != ReplPHI); // ReplPHI is either null or the PHI that replaced
757
60
                             // the landing pad.
758
60
  }
759
29
760
29
  if (LandingPad) {
761
1
    // Calls to ehAwareSplitEdge function cloned the original lading pad.
762
1
    // No longer need it.
763
1
    LandingPad->eraseFromParent();
764
1
  }
765
29
}
766
767
37
static void rewritePHIs(Function &F) {
768
37
  SmallVector<BasicBlock *, 8> WorkList;
769
37
770
37
  for (BasicBlock &BB : F)
771
439
    if (auto *PN = dyn_cast<PHINode>(&BB.front()))
772
29
      if (PN->getNumIncomingValues() > 1)
773
29
        WorkList.push_back(&BB);
774
37
775
37
  for (BasicBlock *BB : WorkList)
776
29
    rewritePHIs(*BB);
777
37
}
778
779
// Check for instructions that we can recreate on resume as opposed to spill
780
// the result into a coroutine frame.
781
1.46k
static bool materializable(Instruction &V) {
782
1.46k
  return isa<CastInst>(&V) || 
isa<GetElementPtrInst>(&V)1.44k
||
783
1.46k
         
isa<BinaryOperator>(&V)1.43k
||
isa<CmpInst>(&V)1.39k
||
isa<SelectInst>(&V)1.38k
;
784
1.46k
}
785
786
// Check for structural coroutine intrinsics that should not be spilled into
787
// the coroutine frame.
788
1.17k
static bool isCoroutineStructureIntrinsic(Instruction &I) {
789
1.17k
  return isa<CoroIdInst>(&I) || 
isa<CoroSaveInst>(&I)1.13k
||
790
1.17k
         
isa<CoroSuspendInst>(&I)1.09k
;
791
1.17k
}
792
793
// For every use of the value that is across suspend point, recreate that value
794
// after a suspend point.
795
static void rewriteMaterializableInstructions(IRBuilder<> &IRB,
796
10
                                              SpillInfo const &Spills) {
797
10
  BasicBlock *CurrentBlock = nullptr;
798
10
  Instruction *CurrentMaterialization = nullptr;
799
10
  Instruction *CurrentDef = nullptr;
800
10
801
14
  for (auto const &E : Spills) {
802
14
    // If it is a new definition, update CurrentXXX variables.
803
14
    if (CurrentDef != E.def()) {
804
11
      CurrentDef = cast<Instruction>(E.def());
805
11
      CurrentBlock = nullptr;
806
11
      CurrentMaterialization = nullptr;
807
11
    }
808
14
809
14
    // If we have not seen this block, materialize the value.
810
14
    if (CurrentBlock != E.userBlock()) {
811
14
      CurrentBlock = E.userBlock();
812
14
      CurrentMaterialization = cast<Instruction>(CurrentDef)->clone();
813
14
      CurrentMaterialization->setName(CurrentDef->getName());
814
14
      CurrentMaterialization->insertBefore(
815
14
          &*CurrentBlock->getFirstInsertionPt());
816
14
    }
817
14
818
14
    if (auto *PN = dyn_cast<PHINode>(E.user())) {
819
6
      assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
820
6
                                                "values in the PHINode");
821
6
      PN->replaceAllUsesWith(CurrentMaterialization);
822
6
      PN->eraseFromParent();
823
6
      continue;
824
6
    }
825
8
826
8
    // Replace all uses of CurrentDef in the current instruction with the
827
8
    // CurrentMaterialization for the block.
828
8
    E.user()->replaceUsesOfWith(CurrentDef, CurrentMaterialization);
829
8
  }
830
10
}
831
832
// Move early uses of spilled variable after CoroBegin.
833
// For example, if a parameter had address taken, we may end up with the code
834
// like:
835
//        define @f(i32 %n) {
836
//          %n.addr = alloca i32
837
//          store %n, %n.addr
838
//          ...
839
//          call @coro.begin
840
//    we need to move the store after coro.begin
841
static void moveSpillUsesAfterCoroBegin(Function &F, SpillInfo const &Spills,
842
37
                                        CoroBeginInst *CoroBegin) {
843
37
  DominatorTree DT(F);
844
37
  SmallVector<Instruction *, 8> NeedsMoving;
845
37
846
37
  Value *CurrentValue = nullptr;
847
37
848
63
  for (auto const &E : Spills) {
849
63
    if (CurrentValue == E.def())
850
22
      continue;
851
41
852
41
    CurrentValue = E.def();
853
41
854
88
    for (User *U : CurrentValue->users()) {
855
88
      Instruction *I = cast<Instruction>(U);
856
88
      if (!DT.dominates(CoroBegin, I)) {
857
0
        LLVM_DEBUG(dbgs() << "will move: " << *I << "\n");
858
0
859
0
        // TODO: Make this more robust. Currently if we run into a situation
860
0
        // where simple instruction move won't work we panic and
861
0
        // report_fatal_error.
862
0
        for (User *UI : I->users()) {
863
0
          if (!DT.dominates(CoroBegin, cast<Instruction>(UI)))
864
0
            report_fatal_error("cannot move instruction since its users are not"
865
0
                               " dominated by CoroBegin");
866
0
        }
867
0
868
0
        NeedsMoving.push_back(I);
869
0
      }
870
88
    }
871
41
  }
872
37
873
37
  Instruction *InsertPt = CoroBegin->getNextNode();
874
37
  for (Instruction *I : NeedsMoving)
875
0
    I->moveBefore(InsertPt);
876
37
}
877
878
// Splits the block at a particular instruction unless it is the first
879
// instruction in the block with a single predecessor.
880
234
static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
881
234
  auto *BB = I->getParent();
882
234
  if (&BB->front() == I) {
883
79
    if (BB->getSinglePredecessor()) {
884
43
      BB->setName(Name);
885
43
      return BB;
886
43
    }
887
191
  }
888
191
  return BB->splitBasicBlock(I, Name);
889
191
}
890
891
// Split above and below a particular instruction so that it
892
// will be all alone by itself in a block.
893
117
static void splitAround(Instruction *I, const Twine &Name) {
894
117
  splitBlockIfNotFirst(I, Name);
895
117
  splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
896
117
}
897
898
37
void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
899
37
  // Lower coro.dbg.declare to coro.dbg.value, since we are going to rewrite
900
37
  // access to local variables.
901
37
  LowerDbgDeclare(F);
902
37
903
37
  Shape.PromiseAlloca = Shape.CoroBegin->getId()->getPromise();
904
37
  if (Shape.PromiseAlloca) {
905
2
    Shape.CoroBegin->getId()->clearPromise();
906
2
  }
907
37
908
37
  // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
909
37
  // intrinsics are in their own blocks to simplify the logic of building up
910
37
  // SuspendCrossing data.
911
39
  for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
912
39
    splitAround(CSI->getCoroSave(), "CoroSave");
913
39
    splitAround(CSI, "CoroSuspend");
914
39
  }
915
37
916
37
  // Put CoroEnds into their own blocks.
917
37
  for (CoroEndInst *CE : Shape.CoroEnds)
918
39
    splitAround(CE, "CoroEnd");
919
37
920
37
  // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
921
37
  // never has its definition separated from the PHI by the suspend point.
922
37
  rewritePHIs(F);
923
37
924
37
  // Build suspend crossing info.
925
37
  SuspendCrossingInfo Checker(F, Shape);
926
37
927
37
  IRBuilder<> Builder(F.getContext());
928
37
  SpillInfo Spills;
929
37
930
47
  for (int Repeat = 0; Repeat < 4; 
++Repeat10
) {
931
47
    // See if there are materializable instructions across suspend points.
932
47
    for (Instruction &I : instructions(F))
933
1.46k
      if (materializable(I))
934
80
        for (User *U : I.users())
935
72
          if (Checker.isDefinitionAcrossSuspend(I, U))
936
14
            Spills.emplace_back(&I, U);
937
47
938
47
    if (Spills.empty())
939
37
      break;
940
10
941
10
    // Rewrite materializable instructions to be materialized at the use point.
942
10
    LLVM_DEBUG(dump("Materializations", Spills));
943
10
    rewriteMaterializableInstructions(Builder, Spills);
944
10
    Spills.clear();
945
10
  }
946
37
947
37
  // Collect the spills for arguments and other not-materializable values.
948
37
  for (Argument &A : F.args())
949
33
    for (User *U : A.users())
950
39
      if (Checker.isDefinitionAcrossSuspend(A, U))
951
13
        Spills.emplace_back(&A, U);
952
37
953
1.17k
  for (Instruction &I : instructions(F)) {
954
1.17k
    // Values returned from coroutine structure intrinsics should not be part
955
1.17k
    // of the Coroutine Frame.
956
1.17k
    if (isCoroutineStructureIntrinsic(I) || 
&I == Shape.CoroBegin1.05k
)
957
153
      continue;
958
1.02k
    // The Coroutine Promise always included into coroutine frame, no need to
959
1.02k
    // check for suspend crossing.
960
1.02k
    if (Shape.PromiseAlloca == &I)
961
2
      continue;
962
1.01k
963
1.01k
    for (User *U : I.users())
964
376
      if (Checker.isDefinitionAcrossSuspend(I, U)) {
965
50
        // We cannot spill a token.
966
50
        if (I.getType()->isTokenTy())
967
0
          report_fatal_error(
968
0
              "token definition is separated from the use by a suspend point");
969
50
        Spills.emplace_back(&I, U);
970
50
      }
971
1.01k
  }
972
37
  LLVM_DEBUG(dump("Spills", Spills));
973
37
  moveSpillUsesAfterCoroBegin(F, Spills, Shape.CoroBegin);
974
37
  Shape.FrameTy = buildFrameType(F, Shape, Spills);
975
37
  Shape.FramePtr = insertSpills(Spills, Shape);
976
37
}