Bug Summary

File:llvm/include/llvm/IR/IntrinsicInst.h
Warning:line 218, column 43
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CoroFrame.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Coroutines -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Coroutines -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Coroutines -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Coroutines -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Coroutines/CoroFrame.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Coroutines/CoroFrame.cpp

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"
20#include "llvm/Analysis/PtrUseVisitor.h"
21#include "llvm/Analysis/StackLifetime.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"
28#include "llvm/Support/CommandLine.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/MathExtras.h"
31#include "llvm/Support/OptimizedStructLayout.h"
32#include "llvm/Support/circular_raw_ostream.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/Transforms/Utils/BasicBlockUtils.h"
35#include "llvm/Transforms/Utils/Local.h"
36#include "llvm/Transforms/Utils/PromoteMemToReg.h"
37#include <algorithm>
38
39using 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-frame" "coro-suspend-crossing"
44
45static cl::opt<bool> EnableReuseStorageInFrame(
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
52enum { SmallVectorThreshold = 32 };
53
54// Provides two way mapping between the blocks and numbers.
55namespace {
56class BlockToIndexMapping {
57 SmallVector<BasicBlock *, SmallVectorThreshold> V;
58
59public:
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")(static_cast<void> (0));
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//
90namespace {
91struct SuspendCrossingInfo {
92 BlockToIndexMapping Mapping;
93
94 struct BlockData {
95 BitVector Consumes;
96 BitVector Kills;
97 bool Suspend = false;
98 bool End = false;
99 };
100 SmallVector<BlockData, SmallVectorThreshold> Block;
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()do { } while (false)
122 << " answer is " << Result << "\n")do { } while (false);
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")(static_cast<void> (0));
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")(static_cast<void> (0));
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
172 llvm_unreachable(__builtin_unreachable()
173 "Coroutine could only collect Argument and Instruction now.")__builtin_unreachable();
174 }
175};
176} // end anonymous namespace
177
178#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
179LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump(StringRef Label,
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
188LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump() const {
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
199SuspendCrossingInfo::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)do { } while (false);
241 LLVM_DEBUG(dbgs() << "==============\n")do { } while (false);
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()do { } while (false)
286 << "\n")do { } while (false);
287 LLVM_DEBUG(dump("S.Kills", S.Kills))do { } while (false);
288 LLVM_DEBUG(dump("SavedKills", SavedKills))do { } while (false);
289 }
290 if (S.Consumes != SavedConsumes) {
291 LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n")do { } while (false);
292 LLVM_DEBUG(dump("S.Consume", S.Consumes))do { } while (false);
293 LLVM_DEBUG(dump("SavedCons", SavedConsumes))do { } while (false);
294 }
295 }
296 }
297 } while (Changed);
298 LLVM_DEBUG(dump())do { } while (false);
299}
300
301#undef DEBUG_TYPE"coro-frame" // "coro-suspend-crossing"
302#define DEBUG_TYPE"coro-frame" "coro-frame"
303
304namespace {
305class FrameTypeBuilder;
306// Mapping from the to-be-spilled value to all the users that need reload.
307using SpillInfo = SmallMapVector<Value *, SmallVector<Instruction *, 2>, 8>;
308struct AllocaInfo {
309 AllocaInst *Alloca;
310 DenseMap<Instruction *, llvm::Optional<APInt>> Aliases;
311 bool MayWriteBeforeCoroBegin;
312 AllocaInfo(AllocaInst *Alloca,
313 DenseMap<Instruction *, llvm::Optional<APInt>> Aliases,
314 bool MayWriteBeforeCoroBegin)
315 : Alloca(Alloca), Aliases(std::move(Aliases)),
316 MayWriteBeforeCoroBegin(MayWriteBeforeCoroBegin) {}
317};
318struct 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.
324 SmallVector<AllocaInfo, 8> Allocas;
325
326 SmallVector<Value *, 8> getAllDefs() const {
327 SmallVector<Value *, 8> Defs;
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() &&(static_cast<void> (0))
338 "Value does not have a frame field index")(static_cast<void> (0));
339 return Itr->second;
340 }
341
342 void setFieldIndex(Value *V, uint32_t Index) {
343 assert((LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) &&(static_cast<void> (0))
344 "Cannot set the index for the same field twice.")(static_cast<void> (0));
345 FieldIndexMap[V] = Index;
346 }
347
348 uint64_t getAlign(Value *V) const {
349 auto Iter = FieldAlignMap.find(V);
350 assert(Iter != FieldAlignMap.end())(static_cast<void> (0));
351 return Iter->second;
352 }
353
354 void setAlign(Value *V, uint64_t Align) {
355 assert(FieldAlignMap.count(V) == 0)(static_cast<void> (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())(static_cast<void> (0));
362 return Iter->second;
363 }
364
365 void setOffset(Value *V, uint64_t Offset) {
366 assert(FieldOffsetMap.count(V) == 0)(static_cast<void> (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
373private:
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 NDEBUG1
391static 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
401static 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
409namespace {
410using 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.
415class FrameTypeBuilder {
416private:
417 struct Field {
418 uint64_t Size;
419 uint64_t Offset;
420 Type *Ty;
421 FieldIDType LayoutFieldIndex;
422 Align Alignment;
423 Align TyAlignment;
424 };
425
426 const DataLayout &DL;
427 LLVMContext &Context;
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
437public:
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[[clang::warn_unused_result]] 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[[clang::warn_unused_result]] FieldIDType addField(Type *Ty, MaybeAlign FieldAlignment,
491 bool IsHeader = false,
492 bool IsSpillOfValue = false) {
493 assert(!IsFinished && "adding fields to a finished builder")(static_cast<void> (0));
494 assert(Ty && "must provide a type for a field")(static_cast<void> (0));
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.
519 uint64_t Offset;
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!")(static_cast<void> (0));
538 return StructSize;
539 }
540
541 Align getStructAlign() const {
542 assert(IsFinished && "not yet finished!")(static_cast<void> (0));
543 return StructAlign;
544 }
545
546 FieldIDType getLayoutFieldIndex(FieldIDType Id) const {
547 assert(IsFinished && "not yet finished!")(static_cast<void> (0));
548 return Fields[Id].LayoutFieldIndex;
549 }
550
551 Field getLayoutField(FieldIDType Id) const {
552 assert(IsFinished && "not yet finished!")(static_cast<void> (0));
553 return Fields[Id];
554 }
555};
556} // namespace
557
558void 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
573void 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")(static_cast<void> (0));
642 assert(!RetSize->isScalable() && "Scalable vectors are not yet supported")(static_cast<void> (0));
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")(static_cast<void> (0));
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 &AllocaSetdo { } while (false)
694 : NonOverlapedAllocas) {do { } while (false)
695 if (AllocaSet.size() > 1) {do { } while (false)
696 dbgs() << "In Function:" << F.getName() << "\n";do { } while (false)
697 dbgs() << "Find Union Set "do { } while (false)
698 << "\n";do { } while (false)
699 dbgs() << "\tAllocas are \n";do { } while (false)
700 for (auto Alloca : AllocaSet)do { } while (false)
701 dbgs() << "\t\t" << *Alloca << "\n";do { } while (false)
702 }do { } while (false)
703 })do { } while (false);
704}
705
706void FrameTypeBuilder::finish(StructType *Ty) {
707 assert(!IsFinished && "already finished!")(static_cast<void> (0));
708
709 // Prepare the optimal-layout field array.
710 // The Id in the layout field is a pointer to our Field for it.
711 SmallVector<OptimizedStructLayoutField, 8> LayoutFields;
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)(static_cast<void> (0));
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 NDEBUG1
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)(static_cast<void> (0));
771 assert(Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset)(static_cast<void> (0));
772 }
773#endif
774
775 IsFinished = true;
776}
777
778static void cacheDIVar(FrameDataInfo &FrameData,
779 DenseMap<Value *, DILocalVariable *> &DIVarCache) {
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.
795static StringRef solveTypeName(Type *Ty) {
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
843static DIType *solveDIType(DIBuilder &Builder, Type *Ty, DataLayout &Layout,
844 DIScope *Scope, unsigned LineNum,
845 DenseMap<Type *, DIType *> &DITypeCache) {
846 if (DIType *DT = DITypeCache.lookup(Ty))
847 return DT;
848
849 StringRef Name = solveTypeName(Ty);
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);
879 SmallVector<Metadata *, 16> Elements;
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)(static_cast<void> (0));
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";)do { } while (false);
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.
920static void buildFrameDebugInfo(Function &F, coro::Shape &Shape,
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() ||
927 !dwarf::isCPlusPlus(
928 (dwarf::SourceLanguage)DIS->getUnit()->getSourceLanguage()))
929 return;
930
931 assert(Shape.ABI == coro::ABI::Switch &&(static_cast<void> (0))
932 "We could only build debug infomation for C++ coroutine now.\n")(static_cast<void> (0));
933
934 DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);
935
936 AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
937 assert(PromiseAlloca &&(static_cast<void> (0))
938 "Coroutine with switch ABI should own Promise alloca")(static_cast<void> (0));
939
940 TinyPtrVector<DbgDeclareInst *> DIs = FindDbgDeclareUses(PromiseAlloca);
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;
956 SmallVector<Metadata *, 16> Elements;
957 DataLayout Layout = F.getParent()->getDataLayout();
958
959 DenseMap<Value *, DILocalVariable *> DIVarCache;
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
966 DenseMap<unsigned, StringRef> NameCache;
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
975 DenseMap<unsigned, DIType *> TyCache;
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)
1005 DenseMap<unsigned, std::pair<unsigned, unsigned>> OffsetCache;
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,
1011 {Shape.SwitchLowering.IndexAlign, Shape.SwitchLowering.IndexOffset}});
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")(static_cast<void> (0));
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")(static_cast<void> (0));
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()))(static_cast<void> (0));
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// };
1094static StructType *buildFrameType(Function &F, coro::Shape &Shape,
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")(static_cast<void> (0));
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();
1189 Shape.RetconLowering.IsFrameInlineInStorage
1190 = (B.getStructSize() <= Id->getStorageSize() &&
1191 B.getStructAlign() <= Id->getStorageAlignment());
1192 break;
1193 }
1194 case coro::ABI::Async: {
1195 Shape.AsyncLowering.FrameOffset =
1196 alignTo(Shape.AsyncLowering.ContextHeaderSize, Shape.FrameAlign);
1197 // Also make the final context size a multiple of the context alignment to
1198 // make allocation easier for allocators.
1199 Shape.AsyncLowering.ContextSize =
1200 alignTo(Shape.AsyncLowering.FrameOffset + Shape.FrameSize,
1201 Shape.AsyncLowering.getContextAlignment());
1202 if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
1203 report_fatal_error(
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.
1239namespace {
1240struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
1241 using Base = 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) {
1335 Base::visitBitCastInst(BC);
1336 handleAlias(BC);
1337 }
1338
1339 void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
1340 Base::visitAddrSpaceCastInst(ASC);
1341 handleAlias(ASC);
1342 }
1343
1344 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
1345 // The base visitor will adjust Offset accordingly.
1346 Base::visitGetElementPtrInst(GEPI);
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 "(static_cast<void> (0))
1373 "alloca needs to live on the frame.")(static_cast<void> (0));
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
1381private:
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.
1388 DenseMap<Instruction *, llvm::Optional<APInt>> AliasOffetMap{};
1389 SmallPtrSet<Instruction *, 4> Users{};
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.
1472static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
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
1484static void createFramePtr(coro::Shape &Shape) {
1485 auto *CB = Shape.CoroBegin;
1486 IRBuilder<> Builder(CB->getNextNode());
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//
1515static Instruction *insertSpills(const FrameDataInfo &FrameData,
1516 coro::Shape &Shape) {
1517 auto *CB = Shape.CoroBegin;
1518 LLVMContext &C = CB->getContext();
1519 IRBuilder<> Builder(C);
1520 StructType *FrameTy = Shape.FrameTy;
1521 Instruction *FramePtr = Shape.FramePtr;
1522 DominatorTree DT(*CB->getFunction());
1523 SmallDenseMap<llvm::Value *, llvm::AllocaInst *, 4> DbgPtrAllocaCache;
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")(static_cast<void> (0));
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
1646 TinyPtrVector<DbgDeclareInst *> DIs = FindDbgDeclareUses(Def);
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 &&(static_cast<void> (0))
1667 "unexpected number of incoming "(static_cast<void> (0))
1668 "values in the PHINode")(static_cast<void> (0));
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
1725 SmallVector<DbgVariableIntrinsic *, 4> DIs;
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())
1739 report_fatal_error(
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.
1767static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,
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.
1785static 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
1860static void cleanupSinglePredPHIs(Function &F) {
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
1878static 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())) {
1904 SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));
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)(static_cast<void> (0));
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
1931 SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));
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
1948static void rewritePHIs(Function &F) {
1949 SmallVector<BasicBlock *, 8> WorkList;
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.
1962static 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.
1969static bool isCoroutineStructureIntrinsic(Instruction &I) {
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.
1976static void rewriteMaterializableInstructions(IRBuilder<> &IRB,
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 = U->getParent();
1988 auto *InsertBlock = IsInCoroSuspendBlock
1989 ? CurrentBlock->getSinglePredecessor()
1990 : CurrentBlock;
1991 CurrentMaterialization = cast<Instruction>(Def)->clone();
1992 CurrentMaterialization->setName(Def->getName());
1993 CurrentMaterialization->insertBefore(
1994 IsInCoroSuspendBlock ? InsertBlock->getTerminator()
1995 : &*InsertBlock->getFirstInsertionPt());
1996 }
1997 if (auto *PN = dyn_cast<PHINode>(U)) {
1998 assert(PN->getNumIncomingValues() == 1 &&(static_cast<void> (0))
1999 "unexpected number of incoming "(static_cast<void> (0))
2000 "values in the PHINode")(static_cast<void> (0));
2001 PN->replaceAllUsesWith(CurrentMaterialization);
2002 PN->eraseFromParent();
2003 continue;
2004 }
2005 // Replace all uses of Def in the current instruction with the
2006 // CurrentMaterialization for the block.
2007 U->replaceUsesOfWith(Def, CurrentMaterialization);
2008 }
2009 }
2010}
2011
2012// Splits the block at a particular instruction unless it is the first
2013// instruction in the block with a single predecessor.
2014static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
2015 auto *BB = I->getParent();
2016 if (&BB->front() == I) {
2017 if (BB->getSinglePredecessor()) {
2018 BB->setName(Name);
2019 return BB;
2020 }
2021 }
2022 return BB->splitBasicBlock(I, Name);
2023}
2024
2025// Split above and below a particular instruction so that it
2026// will be all alone by itself in a block.
2027static void splitAround(Instruction *I, const Twine &Name) {
2028 splitBlockIfNotFirst(I, Name);
2029 splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
2030}
2031
2032static bool isSuspendBlock(BasicBlock *BB) {
2033 return isa<AnyCoroSuspendInst>(BB->front());
2034}
2035
2036typedef SmallPtrSet<BasicBlock*, 8> VisitedBlocksSet;
2037
2038/// Does control flow starting at the given block ever reach a suspend
2039/// instruction before reaching a block in VisitedOrFreeBBs?
2040static bool isSuspendReachableFrom(BasicBlock *From,
2041 VisitedBlocksSet &VisitedOrFreeBBs) {
2042 // Eagerly try to add this block to the visited set. If it's already
2043 // there, stop recursing; this path doesn't reach a suspend before
2044 // either looping or reaching a freeing block.
2045 if (!VisitedOrFreeBBs.insert(From).second)
2046 return false;
2047
2048 // We assume that we'll already have split suspends into their own blocks.
2049 if (isSuspendBlock(From))
2050 return true;
2051
2052 // Recurse on the successors.
2053 for (auto Succ : successors(From)) {
2054 if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))
2055 return true;
2056 }
2057
2058 return false;
2059}
2060
2061/// Is the given alloca "local", i.e. bounded in lifetime to not cross a
2062/// suspend point?
2063static bool isLocalAlloca(CoroAllocaAllocInst *AI) {
2064 // Seed the visited set with all the basic blocks containing a free
2065 // so that we won't pass them up.
2066 VisitedBlocksSet VisitedOrFreeBBs;
2067 for (auto User : AI->users()) {
2068 if (auto FI = dyn_cast<CoroAllocaFreeInst>(User))
2069 VisitedOrFreeBBs.insert(FI->getParent());
2070 }
2071
2072 return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);
2073}
2074
2075/// After we split the coroutine, will the given basic block be along
2076/// an obvious exit path for the resumption function?
2077static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB,
2078 unsigned depth = 3) {
2079 // If we've bottomed out our depth count, stop searching and assume
2080 // that the path might loop back.
2081 if (depth == 0) return false;
2082
2083 // If this is a suspend block, we're about to exit the resumption function.
2084 if (isSuspendBlock(BB)) return true;
2085
2086 // Recurse into the successors.
2087 for (auto Succ : successors(BB)) {
2088 if (!willLeaveFunctionImmediatelyAfter(Succ, depth - 1))
2089 return false;
2090 }
2091
2092 // If none of the successors leads back in a loop, we're on an exit/abort.
2093 return true;
2094}
2095
2096static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI) {
2097 // Look for a free that isn't sufficiently obviously followed by
2098 // either a suspend or a termination, i.e. something that will leave
2099 // the coro resumption frame.
2100 for (auto U : AI->users()) {
2101 auto FI = dyn_cast<CoroAllocaFreeInst>(U);
2102 if (!FI) continue;
2103
2104 if (!willLeaveFunctionImmediatelyAfter(FI->getParent()))
2105 return true;
2106 }
2107
2108 // If we never found one, we don't need a stack save.
2109 return false;
2110}
2111
2112/// Turn each of the given local allocas into a normal (dynamic) alloca
2113/// instruction.
2114static void lowerLocalAllocas(ArrayRef<CoroAllocaAllocInst*> LocalAllocas,
2115 SmallVectorImpl<Instruction*> &DeadInsts) {
2116 for (auto AI : LocalAllocas) {
2117 auto M = AI->getModule();
2118 IRBuilder<> Builder(AI);
2119
2120 // Save the stack depth. Try to avoid doing this if the stackrestore
2121 // is going to immediately precede a return or something.
2122 Value *StackSave = nullptr;
2123 if (localAllocaNeedsStackSave(AI))
2124 StackSave = Builder.CreateCall(
2125 Intrinsic::getDeclaration(M, Intrinsic::stacksave));
2126
2127 // Allocate memory.
2128 auto Alloca = Builder.CreateAlloca(Builder.getInt8Ty(), AI->getSize());
2129 Alloca->setAlignment(Align(AI->getAlignment()));
2130
2131 for (auto U : AI->users()) {
2132 // Replace gets with the allocation.
2133 if (isa<CoroAllocaGetInst>(U)) {
2134 U->replaceAllUsesWith(Alloca);
2135
2136 // Replace frees with stackrestores. This is safe because
2137 // alloca.alloc is required to obey a stack discipline, although we
2138 // don't enforce that structurally.
2139 } else {
2140 auto FI = cast<CoroAllocaFreeInst>(U);
2141 if (StackSave) {
2142 Builder.SetInsertPoint(FI);
2143 Builder.CreateCall(
2144 Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
2145 StackSave);
2146 }
2147 }
2148 DeadInsts.push_back(cast<Instruction>(U));
2149 }
2150
2151 DeadInsts.push_back(AI);
2152 }
2153}
2154
2155/// Turn the given coro.alloca.alloc call into a dynamic allocation.
2156/// This happens during the all-instructions iteration, so it must not
2157/// delete the call.
2158static Instruction *lowerNonLocalAlloca(CoroAllocaAllocInst *AI,
2159 coro::Shape &Shape,
2160 SmallVectorImpl<Instruction*> &DeadInsts) {
2161 IRBuilder<> Builder(AI);
2162 auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);
2163
2164 for (User *U : AI->users()) {
2165 if (isa<CoroAllocaGetInst>(U)) {
2166 U->replaceAllUsesWith(Alloc);
2167 } else {
2168 auto FI = cast<CoroAllocaFreeInst>(U);
2169 Builder.SetInsertPoint(FI);
2170 Shape.emitDealloc(Builder, Alloc, nullptr);
2171 }
2172 DeadInsts.push_back(cast<Instruction>(U));
2173 }
2174
2175 // Push this on last so that it gets deleted after all the others.
2176 DeadInsts.push_back(AI);
2177
2178 // Return the new allocation value so that we can check for needed spills.
2179 return cast<Instruction>(Alloc);
2180}
2181
2182/// Get the current swifterror value.
2183static Value *emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy,
2184 coro::Shape &Shape) {
2185 // Make a fake function pointer as a sort of intrinsic.
2186 auto FnTy = FunctionType::get(ValueTy, {}, false);
2187 auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2188
2189 auto Call = Builder.CreateCall(FnTy, Fn, {});
2190 Shape.SwiftErrorOps.push_back(Call);
2191
2192 return Call;
2193}
2194
2195/// Set the given value as the current swifterror value.
2196///
2197/// Returns a slot that can be used as a swifterror slot.
2198static Value *emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V,
2199 coro::Shape &Shape) {
2200 // Make a fake function pointer as a sort of intrinsic.
2201 auto FnTy = FunctionType::get(V->getType()->getPointerTo(),
2202 {V->getType()}, false);
2203 auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());
2204
2205 auto Call = Builder.CreateCall(FnTy, Fn, { V });
2206 Shape.SwiftErrorOps.push_back(Call);
2207
2208 return Call;
2209}
2210
2211/// Set the swifterror value from the given alloca before a call,
2212/// then put in back in the alloca afterwards.
2213///
2214/// Returns an address that will stand in for the swifterror slot
2215/// until splitting.
2216static Value *emitSetAndGetSwiftErrorValueAround(Instruction *Call,
2217 AllocaInst *Alloca,
2218 coro::Shape &Shape) {
2219 auto ValueTy = Alloca->getAllocatedType();
2220 IRBuilder<> Builder(Call);
2221
2222 // Load the current value from the alloca and set it as the
2223 // swifterror value.
2224 auto ValueBeforeCall = Builder.CreateLoad(ValueTy, Alloca);
2225 auto Addr = emitSetSwiftErrorValue(Builder, ValueBeforeCall, Shape);
2226
2227 // Move to after the call. Since swifterror only has a guaranteed
2228 // value on normal exits, we can ignore implicit and explicit unwind
2229 // edges.
2230 if (isa<CallInst>(Call)) {
2231 Builder.SetInsertPoint(Call->getNextNode());
2232 } else {
2233 auto Invoke = cast<InvokeInst>(Call);
2234 Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
2235 }
2236
2237 // Get the current swifterror value and store it to the alloca.
2238 auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
2239 Builder.CreateStore(ValueAfterCall, Alloca);
2240
2241 return Addr;
2242}
2243
2244/// Eliminate a formerly-swifterror alloca by inserting the get/set
2245/// intrinsics and attempting to MemToReg the alloca away.
2246static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca,
2247 coro::Shape &Shape) {
2248 for (auto UI = Alloca->use_begin(), UE = Alloca->use_end(); UI != UE; ) {
2249 // We're likely changing the use list, so use a mutation-safe
2250 // iteration pattern.
2251 auto &Use = *UI;
2252 ++UI;
2253
2254 // swifterror values can only be used in very specific ways.
2255 // We take advantage of that here.
2256 auto User = Use.getUser();
2257 if (isa<LoadInst>(User) || isa<StoreInst>(User))
2258 continue;
2259
2260 assert(isa<CallInst>(User) || isa<InvokeInst>(User))(static_cast<void> (0));
2261 auto Call = cast<Instruction>(User);
2262
2263 auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);
2264
2265 // Use the returned slot address as the call argument.
2266 Use.set(Addr);
2267 }
2268
2269 // All the uses should be loads and stores now.
2270 assert(isAllocaPromotable(Alloca))(static_cast<void> (0));
2271}
2272
2273/// "Eliminate" a swifterror argument by reducing it to the alloca case
2274/// and then loading and storing in the prologue and epilog.
2275///
2276/// The argument keeps the swifterror flag.
2277static void eliminateSwiftErrorArgument(Function &F, Argument &Arg,
2278 coro::Shape &Shape,
2279 SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
2280 IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrDbg());
2281
2282 auto ArgTy = cast<PointerType>(Arg.getType());
2283 auto ValueTy = ArgTy->getElementType();
2284
2285 // Reduce to the alloca case:
2286
2287 // Create an alloca and replace all uses of the arg with it.
2288 auto Alloca = Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());
2289 Arg.replaceAllUsesWith(Alloca);
2290
2291 // Set an initial value in the alloca. swifterror is always null on entry.
2292 auto InitialValue = Constant::getNullValue(ValueTy);
2293 Builder.CreateStore(InitialValue, Alloca);
2294
2295 // Find all the suspends in the function and save and restore around them.
2296 for (auto Suspend : Shape.CoroSuspends) {
2297 (void) emitSetAndGetSwiftErrorValueAround(Suspend, Alloca, Shape);
2298 }
2299
2300 // Find all the coro.ends in the function and restore the error value.
2301 for (auto End : Shape.CoroEnds) {
2302 Builder.SetInsertPoint(End);
2303 auto FinalValue = Builder.CreateLoad(ValueTy, Alloca);
2304 (void) emitSetSwiftErrorValue(Builder, FinalValue, Shape);
2305 }
2306
2307 // Now we can use the alloca logic.
2308 AllocasToPromote.push_back(Alloca);
2309 eliminateSwiftErrorAlloca(F, Alloca, Shape);
2310}
2311
2312/// Eliminate all problematic uses of swifterror arguments and allocas
2313/// from the function. We'll fix them up later when splitting the function.
2314static void eliminateSwiftError(Function &F, coro::Shape &Shape) {
2315 SmallVector<AllocaInst*, 4> AllocasToPromote;
2316
2317 // Look for a swifterror argument.
2318 for (auto &Arg : F.args()) {
2319 if (!Arg.hasSwiftErrorAttr()) continue;
2320
2321 eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
2322 break;
2323 }
2324
2325 // Look for swifterror allocas.
2326 for (auto &Inst : F.getEntryBlock()) {
2327 auto Alloca = dyn_cast<AllocaInst>(&Inst);
2328 if (!Alloca || !Alloca->isSwiftError()) continue;
2329
2330 // Clear the swifterror flag.
2331 Alloca->setSwiftError(false);
2332
2333 AllocasToPromote.push_back(Alloca);
2334 eliminateSwiftErrorAlloca(F, Alloca, Shape);
2335 }
2336
2337 // If we have any allocas to promote, compute a dominator tree and
2338 // promote them en masse.
2339 if (!AllocasToPromote.empty()) {
2340 DominatorTree DT(F);
2341 PromoteMemToReg(AllocasToPromote, DT);
2342 }
2343}
2344
2345/// retcon and retcon.once conventions assume that all spill uses can be sunk
2346/// after the coro.begin intrinsic.
2347static void sinkSpillUsesAfterCoroBegin(Function &F,
2348 const FrameDataInfo &FrameData,
2349 CoroBeginInst *CoroBegin) {
2350 DominatorTree Dom(F);
2351
2352 SmallSetVector<Instruction *, 32> ToMove;
2353 SmallVector<Instruction *, 32> Worklist;
2354
2355 // Collect all users that precede coro.begin.
2356 for (auto *Def : FrameData.getAllDefs()) {
2357 for (User *U : Def->users()) {
2358 auto Inst = cast<Instruction>(U);
2359 if (Inst->getParent() != CoroBegin->getParent() ||
2360 Dom.dominates(CoroBegin, Inst))
2361 continue;
2362 if (ToMove.insert(Inst))
2363 Worklist.push_back(Inst);
2364 }
2365 }
2366 // Recursively collect users before coro.begin.
2367 while (!Worklist.empty()) {
2368 auto *Def = Worklist.pop_back_val();
2369 for (User *U : Def->users()) {
2370 auto Inst = cast<Instruction>(U);
2371 if (Dom.dominates(CoroBegin, Inst))
2372 continue;
2373 if (ToMove.insert(Inst))
2374 Worklist.push_back(Inst);
2375 }
2376 }
2377
2378 // Sort by dominance.
2379 SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
2380 llvm::sort(InsertionList, [&Dom](Instruction *A, Instruction *B) -> bool {
2381 // If a dominates b it should preceed (<) b.
2382 return Dom.dominates(A, B);
2383 });
2384
2385 Instruction *InsertPt = CoroBegin->getNextNode();
2386 for (Instruction *Inst : InsertionList)
2387 Inst->moveBefore(InsertPt);
2388}
2389
2390/// For each local variable that all of its user are only used inside one of
2391/// suspended region, we sink their lifetime.start markers to the place where
2392/// after the suspend block. Doing so minimizes the lifetime of each variable,
2393/// hence minimizing the amount of data we end up putting on the frame.
2394static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape,
2395 SuspendCrossingInfo &Checker) {
2396 DominatorTree DT(F);
2397
2398 // Collect all possible basic blocks which may dominate all uses of allocas.
2399 SmallPtrSet<BasicBlock *, 4> DomSet;
2400 DomSet.insert(&F.getEntryBlock());
2401 for (auto *CSI : Shape.CoroSuspends) {
2402 BasicBlock *SuspendBlock = CSI->getParent();
2403 assert(isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() &&(static_cast<void> (0))
2404 "should have split coro.suspend into its own block")(static_cast<void> (0));
2405 DomSet.insert(SuspendBlock->getSingleSuccessor());
2406 }
2407
2408 for (Instruction &I : instructions(F)) {
2409 AllocaInst* AI = dyn_cast<AllocaInst>(&I);
2410 if (!AI)
2411 continue;
2412
2413 for (BasicBlock *DomBB : DomSet) {
2414 bool Valid = true;
2415 SmallVector<Instruction *, 1> Lifetimes;
2416
2417 auto isLifetimeStart = [](Instruction* I) {
2418 if (auto* II = dyn_cast<IntrinsicInst>(I))
2419 return II->getIntrinsicID() == Intrinsic::lifetime_start;
2420 return false;
2421 };
2422
2423 auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
2424 if (isLifetimeStart(U)) {
2425 Lifetimes.push_back(U);
2426 return true;
2427 }
2428 if (!U->hasOneUse() || U->stripPointerCasts() != AI)
2429 return false;
2430 if (isLifetimeStart(U->user_back())) {
2431 Lifetimes.push_back(U->user_back());
2432 return true;
2433 }
2434 return false;
2435 };
2436
2437 for (User *U : AI->users()) {
2438 Instruction *UI = cast<Instruction>(U);
2439 // For all users except lifetime.start markers, if they are all
2440 // dominated by one of the basic blocks and do not cross
2441 // suspend points as well, then there is no need to spill the
2442 // instruction.
2443 if (!DT.dominates(DomBB, UI->getParent()) ||
2444 Checker.isDefinitionAcrossSuspend(DomBB, UI)) {
2445 // Skip lifetime.start, GEP and bitcast used by lifetime.start
2446 // markers.
2447 if (collectLifetimeStart(UI, AI))
2448 continue;
2449 Valid = false;
2450 break;
2451 }
2452 }
2453 // Sink lifetime.start markers to dominate block when they are
2454 // only used outside the region.
2455 if (Valid && Lifetimes.size() != 0) {
2456 // May be AI itself, when the type of AI is i8*
2457 auto *NewBitCast = [&](AllocaInst *AI) -> Value* {
2458 if (isa<AllocaInst>(Lifetimes[0]->getOperand(1)))
2459 return AI;
2460 auto *Int8PtrTy = Type::getInt8PtrTy(F.getContext());
2461 return CastInst::Create(Instruction::BitCast, AI, Int8PtrTy, "",
2462 DomBB->getTerminator());
2463 }(AI);
2464
2465 auto *NewLifetime = Lifetimes[0]->clone();
2466 NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(1), NewBitCast);
2467 NewLifetime->insertBefore(DomBB->getTerminator());
2468
2469 // All the outsided lifetime.start markers are no longer necessary.
2470 for (Instruction *S : Lifetimes)
2471 S->eraseFromParent();
2472
2473 break;
2474 }
2475 }
2476 }
2477}
2478
2479static void collectFrameAllocas(Function &F, coro::Shape &Shape,
2480 const SuspendCrossingInfo &Checker,
2481 SmallVectorImpl<AllocaInfo> &Allocas) {
2482 for (Instruction &I : instructions(F)) {
2483 auto *AI = dyn_cast<AllocaInst>(&I);
2484 if (!AI)
2485 continue;
2486 // The PromiseAlloca will be specially handled since it needs to be in a
2487 // fixed position in the frame.
2488 if (AI == Shape.SwitchLowering.PromiseAlloca) {
2489 continue;
2490 }
2491 DominatorTree DT(F);
2492 AllocaUseVisitor Visitor{F.getParent()->getDataLayout(), DT,
2493 *Shape.CoroBegin, Checker};
2494 Visitor.visitPtr(*AI);
2495 if (!Visitor.getShouldLiveOnFrame())
2496 continue;
2497 Allocas.emplace_back(AI, Visitor.getAliasesCopy(),
2498 Visitor.getMayWriteBeforeCoroBegin());
2499 }
2500}
2501
2502void coro::salvageDebugInfo(
2503 SmallDenseMap<llvm::Value *, llvm::AllocaInst *, 4> &DbgPtrAllocaCache,
2504 DbgVariableIntrinsic *DVI, bool ReuseFrameSlot) {
2505 Function *F = DVI->getFunction();
2506 IRBuilder<> Builder(F->getContext());
2507 auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
2508 while (isa<IntrinsicInst>(InsertPt))
1
Assuming 'InsertPt' is not a 'IntrinsicInst'
2
Loop condition is false. Execution continues on line 2510
2509 ++InsertPt;
2510 Builder.SetInsertPoint(&F->getEntryBlock(), InsertPt);
2511 DIExpression *Expr = DVI->getExpression();
2512 // Follow the pointer arithmetic all the way to the incoming
2513 // function argument and convert into a DIExpression.
2514 bool SkipOutermostLoad = !isa<DbgValueInst>(DVI);
3
Assuming 'DVI' is not a 'DbgValueInst'
2515 Value *Storage = DVI->getVariableLocationOp(0);
2516 Value *OriginalStorage = Storage;
2517 while (auto *Inst = dyn_cast_or_null<Instruction>(Storage)) {
4
Assuming 'Storage' is a 'Instruction'
5
Loop condition is true. Entering loop body
18
Assuming 'Storage' is a 'Instruction'
19
Loop condition is true. Entering loop body
2518 if (auto *LdInst
6.1
'LdInst' is null
20.1
'LdInst' is null
6.1
'LdInst' is null
20.1
'LdInst' is null
6.1
'LdInst' is null
20.1
'LdInst' is null
= dyn_cast<LoadInst>(Inst)) {
6
Assuming 'Inst' is not a 'LoadInst'
7
Taking false branch
20
Assuming 'Inst' is not a 'LoadInst'
21
Taking false branch
2519 Storage = LdInst->getOperand(0);
2520 // FIXME: This is a heuristic that works around the fact that
2521 // LLVM IR debug intrinsics cannot yet distinguish between
2522 // memory and value locations: Because a dbg.declare(alloca) is
2523 // implicitly a memory location no DW_OP_deref operation for the
2524 // last direct load from an alloca is necessary. This condition
2525 // effectively drops the *last* DW_OP_deref in the expression.
2526 if (!SkipOutermostLoad)
2527 Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2528 } else if (auto *StInst
8.1
'StInst' is null
22.1
'StInst' is null
8.1
'StInst' is null
22.1
'StInst' is null
8.1
'StInst' is null
22.1
'StInst' is null
= dyn_cast<StoreInst>(Inst)) {
8
Assuming 'Inst' is not a 'StoreInst'
9
Taking false branch
22
Assuming 'Inst' is not a 'StoreInst'
23
Taking false branch
2529 Storage = StInst->getOperand(0);
2530 } else {
2531 SmallVector<uint64_t, 16> Ops;
2532 SmallVector<Value *, 0> AdditionalValues;
2533 Value *Op = llvm::salvageDebugInfoImpl(
2534 *Inst, Expr
9.1
'Expr' is non-null
9.1
'Expr' is non-null
9.1
'Expr' is non-null
? Expr->getNumLocationOperands() : 0, Ops,
10
'?' condition is true
24
Assuming 'Expr' is null
25
'?' condition is false
2535 AdditionalValues);
2536 if (!Op || !AdditionalValues.empty()) {
11
Assuming 'Op' is non-null
12
Calling 'SmallVectorBase::empty'
15
Returning from 'SmallVectorBase::empty'
16
Taking false branch
26
Assuming 'Op' is null
2537 // If salvaging failed or salvaging produced more than one location
2538 // operand, give up.
2539 break;
2540 }
2541 Storage = Op;
2542 Expr = DIExpression::appendOpsToArg(Expr, Ops, 0, /*StackValue*/ false);
17
Value assigned to 'Expr'
2543 }
2544 SkipOutermostLoad = false;
2545 }
2546 if (!Storage
27.1
'Storage' is non-null
27.1
'Storage' is non-null
27.1
'Storage' is non-null
)
27
Execution continues on line 2546
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)
28
Assuming 'ReuseFrameSlot' is true
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);
29
Passing null pointer value via 1st parameter 'NewExpr'
30
Calling 'DbgVariableIntrinsic::setExpression'
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
2587void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
2588 // Don't eliminate swifterror in async functions that won't be split.
2589 if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2590 eliminateSwiftError(F, Shape);
2591
2592 if (Shape.ABI == coro::ABI::Switch &&
2593 Shape.SwitchLowering.PromiseAlloca) {
2594 Shape.getSwitchCoroId()->clearPromise();
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());
2620 auto Arguments = ArrayRef<Value *>(Args).drop_front(3);
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.
2629 cleanupSinglePredPHIs(F);
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;
2640 SmallVector<CoroAllocaAllocInst*, 4> LocalAllocas;
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.
2654 SmallVector<DbgValueInst *, 16> DVIs;
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))do { } while (false);
2667 rewriteMaterializableInstructions(Builder, 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))do { } while (false);
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.
2686 if (isCoroutineStructureIntrinsic(I) || &I == Shape.CoroBegin)
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 &&
2692 Shape.SwitchLowering.PromiseAlloca == &I)
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())
2728 report_fatal_error(
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;
2740 SmallVector<DbgValueInst *, 16> DVIs;
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))do { } while (false);
2749 if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
2750 Shape.ABI == coro::ABI::Async)
2751 sinkSpillUsesAfterCoroBegin(F, FrameData, Shape.CoroBegin);
2752 Shape.FrameTy = buildFrameType(F, Shape, FrameData);
2753 createFramePtr(Shape);
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}

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
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//
9// This file defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/MemAlloc.h"
20#include "llvm/Support/type_traits.h"
21#include <algorithm>
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25#include <cstring>
26#include <functional>
27#include <initializer_list>
28#include <iterator>
29#include <limits>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
47 void *BeginX;
48 Size_T Size = 0, Capacity;
49
50 /// The maximum value of the Size_T used.
51 static constexpr size_t SizeTypeMax() {
52 return std::numeric_limits<Size_T>::max();
53 }
54
55 SmallVectorBase() = delete;
56 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57 : BeginX(FirstEl), Capacity(TotalCapacity) {}
58
59 /// This is a helper for \a grow() that's out of line to reduce code
60 /// duplication. This function will report a fatal error if it can't grow at
61 /// least to \p MinSize.
62 void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
63
64 /// This is an implementation of the grow() method which only works
65 /// on POD-like data types and is out of line to reduce code duplication.
66 /// This function will report a fatal error if it cannot increase capacity.
67 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
68
69public:
70 size_t size() const { return Size; }
71 size_t capacity() const { return Capacity; }
72
73 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
13
Assuming field 'Size' is 0
14
Returning the value 1, which participates in a condition later
74
75 /// Set the array size to \p N, which the current array must have enough
76 /// capacity for.
77 ///
78 /// This does not construct or destroy any elements in the vector.
79 ///
80 /// Clients can use this in conjunction with capacity() to write past the end
81 /// of the buffer when they know that more elements are available, and only
82 /// update the size later. This avoids the cost of value initializing elements
83 /// which will only be overwritten.
84 void set_size(size_t N) {
85 assert(N <= capacity())(static_cast<void> (0));
86 Size = N;
87 }
88};
89
90template <class T>
91using SmallVectorSizeType =
92 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
93 uint32_t>::type;
94
95/// Figure out the offset of the first element.
96template <class T, typename = void> struct SmallVectorAlignmentAndSize {
97 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
98 SmallVectorBase<SmallVectorSizeType<T>>)];
99 alignas(T) char FirstEl[sizeof(T)];
100};
101
102/// This is the part of SmallVectorTemplateBase which does not depend on whether
103/// the type T is a POD. The extra dummy template argument is used by ArrayRef
104/// to avoid unnecessarily requiring T to be complete.
105template <typename T, typename = void>
106class SmallVectorTemplateCommon
107 : public SmallVectorBase<SmallVectorSizeType<T>> {
108 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
109
110 /// Find the address of the first element. For this pointer math to be valid
111 /// with small-size of 0 for T with lots of alignment, it's important that
112 /// SmallVectorStorage is properly-aligned even for small-size of 0.
113 void *getFirstEl() const {
114 return const_cast<void *>(reinterpret_cast<const void *>(
115 reinterpret_cast<const char *>(this) +
116 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
117 }
118 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
119
120protected:
121 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
122
123 void grow_pod(size_t MinSize, size_t TSize) {
124 Base::grow_pod(getFirstEl(), MinSize, TSize);
125 }
126
127 /// Return true if this is a smallvector which has not had dynamic
128 /// memory allocated for it.
129 bool isSmall() const { return this->BeginX == getFirstEl(); }
130
131 /// Put this vector in a state of being small.
132 void resetToSmall() {
133 this->BeginX = getFirstEl();
134 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
135 }
136
137 /// Return true if V is an internal reference to the given range.
138 bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
139 // Use std::less to avoid UB.
140 std::less<> LessThan;
141 return !LessThan(V, First) && LessThan(V, Last);
142 }
143
144 /// Return true if V is an internal reference to this vector.
145 bool isReferenceToStorage(const void *V) const {
146 return isReferenceToRange(V, this->begin(), this->end());
147 }
148
149 /// Return true if First and Last form a valid (possibly empty) range in this
150 /// vector's storage.
151 bool isRangeInStorage(const void *First, const void *Last) const {
152 // Use std::less to avoid UB.
153 std::less<> LessThan;
154 return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
155 !LessThan(this->end(), Last);
156 }
157
158 /// Return true unless Elt will be invalidated by resizing the vector to
159 /// NewSize.
160 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
161 // Past the end.
162 if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
163 return true;
164
165 // Return false if Elt will be destroyed by shrinking.
166 if (NewSize <= this->size())
167 return Elt < this->begin() + NewSize;
168
169 // Return false if we need to grow.
170 return NewSize <= this->capacity();
171 }
172
173 /// Check whether Elt will be invalidated by resizing the vector to NewSize.
174 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
175 assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast<void> (0))
176 "Attempting to reference an element of the vector in an operation "(static_cast<void> (0))
177 "that invalidates it")(static_cast<void> (0));
178 }
179
180 /// Check whether Elt will be invalidated by increasing the size of the
181 /// vector by N.
182 void assertSafeToAdd(const void *Elt, size_t N = 1) {
183 this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
184 }
185
186 /// Check whether any part of the range will be invalidated by clearing.
187 void assertSafeToReferenceAfterClear(const T *From, const T *To) {
188 if (From == To)
189 return;
190 this->assertSafeToReferenceAfterResize(From, 0);
191 this->assertSafeToReferenceAfterResize(To - 1, 0);
192 }
193 template <
194 class ItTy,
195 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
196 bool> = false>
197 void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
198
199 /// Check whether any part of the range will be invalidated by growing.
200 void assertSafeToAddRange(const T *From, const T *To) {
201 if (From == To)
202 return;
203 this->assertSafeToAdd(From, To - From);
204 this->assertSafeToAdd(To - 1, To - From);
205 }
206 template <
207 class ItTy,
208 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
209 bool> = false>
210 void assertSafeToAddRange(ItTy, ItTy) {}
211
212 /// Reserve enough space to add one element, and return the updated element
213 /// pointer in case it was a reference to the storage.
214 template <class U>
215 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
216 size_t N) {
217 size_t NewSize = This->size() + N;
218 if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
)
)
219 return &Elt;
220
221 bool ReferencesStorage = false;
222 int64_t Index = -1;
223 if (!U::TakesParamByValue) {
224 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)
) {
225 ReferencesStorage = true;
226 Index = &Elt - This->begin();
227 }
228 }
229 This->grow(NewSize);
230 return ReferencesStorage ? This->begin() + Index : &Elt;
231 }
232
233public:
234 using size_type = size_t;
235 using difference_type = ptrdiff_t;
236 using value_type = T;
237 using iterator = T *;
238 using const_iterator = const T *;
239
240 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
241 using reverse_iterator = std::reverse_iterator<iterator>;
242
243 using reference = T &;
244 using const_reference = const T &;
245 using pointer = T *;
246 using const_pointer = const T *;
247
248 using Base::capacity;
249 using Base::empty;
250 using Base::size;
251
252 // forward iterator creation methods.
253 iterator begin() { return (iterator)this->BeginX; }
254 const_iterator begin() const { return (const_iterator)this->BeginX; }
255 iterator end() { return begin() + size(); }
256 const_iterator end() const { return begin() + size(); }
257
258 // reverse iterator creation methods.
259 reverse_iterator rbegin() { return reverse_iterator(end()); }
260 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
261 reverse_iterator rend() { return reverse_iterator(begin()); }
262 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
263
264 size_type size_in_bytes() const { return size() * sizeof(T); }
265 size_type max_size() const {
266 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
267 }
268
269 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
270
271 /// Return a pointer to the vector's buffer, even if empty().
272 pointer data() { return pointer(begin()); }
273 /// Return a pointer to the vector's buffer, even if empty().
274 const_pointer data() const { return const_pointer(begin()); }
275
276 reference operator[](size_type idx) {
277 assert(idx < size())(static_cast<void> (0));
278 return begin()[idx];
279 }
280 const_reference operator[](size_type idx) const {
281 assert(idx < size())(static_cast<void> (0));
282 return begin()[idx];
283 }
284
285 reference front() {
286 assert(!empty())(static_cast<void> (0));
287 return begin()[0];
288 }
289 const_reference front() const {
290 assert(!empty())(static_cast<void> (0));
291 return begin()[0];
292 }
293
294 reference back() {
295 assert(!empty())(static_cast<void> (0));
296 return end()[-1];
297 }
298 const_reference back() const {
299 assert(!empty())(static_cast<void> (0));
300 return end()[-1];
301 }
302};
303
304/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
305/// method implementations that are designed to work with non-trivial T's.
306///
307/// We approximate is_trivially_copyable with trivial move/copy construction and
308/// trivial destruction. While the standard doesn't specify that you're allowed
309/// copy these types with memcpy, there is no way for the type to observe this.
310/// This catches the important case of std::pair<POD, POD>, which is not
311/// trivially assignable.
312template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
313 (is_trivially_move_constructible<T>::value) &&
314 std::is_trivially_destructible<T>::value>
315class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
316 friend class SmallVectorTemplateCommon<T>;
317
318protected:
319 static constexpr bool TakesParamByValue = false;
320 using ValueParamT = const T &;
321
322 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
323
324 static void destroy_range(T *S, T *E) {
325 while (S != E) {
326 --E;
327 E->~T();
328 }
329 }
330
331 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
332 /// constructing elements as needed.
333 template<typename It1, typename It2>
334 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
335 std::uninitialized_copy(std::make_move_iterator(I),
336 std::make_move_iterator(E), Dest);
337 }
338
339 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
340 /// constructing elements as needed.
341 template<typename It1, typename It2>
342 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
343 std::uninitialized_copy(I, E, Dest);
344 }
345
346 /// Grow the allocated memory (without initializing new elements), doubling
347 /// the size of the allocated memory. Guarantees space for at least one more
348 /// element, or MinSize more elements if specified.
349 void grow(size_t MinSize = 0);
350
351 /// Create a new allocation big enough for \p MinSize and pass back its size
352 /// in \p NewCapacity. This is the first section of \a grow().
353 T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
354 return static_cast<T *>(
355 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
356 MinSize, sizeof(T), NewCapacity));
357 }
358
359 /// Move existing elements over to the new allocation \p NewElts, the middle
360 /// section of \a grow().
361 void moveElementsForGrow(T *NewElts);
362
363 /// Transfer ownership of the allocation, finishing up \a grow().
364 void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
365
366 /// Reserve enough space to add one element, and return the updated element
367 /// pointer in case it was a reference to the storage.
368 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
369 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
370 }
371
372 /// Reserve enough space to add one element, and return the updated element
373 /// pointer in case it was a reference to the storage.
374 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
375 return const_cast<T *>(
376 this->reserveForParamAndGetAddressImpl(this, Elt, N));
377 }
378
379 static T &&forward_value_param(T &&V) { return std::move(V); }
380 static const T &forward_value_param(const T &V) { return V; }
381
382 void growAndAssign(size_t NumElts, const T &Elt) {
383 // Grow manually in case Elt is an internal reference.
384 size_t NewCapacity;
385 T *NewElts = mallocForGrow(NumElts, NewCapacity);
386 std::uninitialized_fill_n(NewElts, NumElts, Elt);
387 this->destroy_range(this->begin(), this->end());
388 takeAllocationForGrow(NewElts, NewCapacity);
389 this->set_size(NumElts);
390 }
391
392 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
393 // Grow manually in case one of Args is an internal reference.
394 size_t NewCapacity;
395 T *NewElts = mallocForGrow(0, NewCapacity);
396 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
397 moveElementsForGrow(NewElts);
398 takeAllocationForGrow(NewElts, NewCapacity);
399 this->set_size(this->size() + 1);
400 return this->back();
401 }
402
403public:
404 void push_back(const T &Elt) {
405 const T *EltPtr = reserveForParamAndGetAddress(Elt);
406 ::new ((void *)this->end()) T(*EltPtr);
407 this->set_size(this->size() + 1);
408 }
409
410 void push_back(T &&Elt) {
411 T *EltPtr = reserveForParamAndGetAddress(Elt);
412 ::new ((void *)this->end()) T(::std::move(*EltPtr));
413 this->set_size(this->size() + 1);
414 }
415
416 void pop_back() {
417 this->set_size(this->size() - 1);
418 this->end()->~T();
419 }
420};
421
422// Define this out-of-line to dissuade the C++ compiler from inlining it.
423template <typename T, bool TriviallyCopyable>
424void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
425 size_t NewCapacity;
426 T *NewElts = mallocForGrow(MinSize, NewCapacity);
427 moveElementsForGrow(NewElts);
428 takeAllocationForGrow(NewElts, NewCapacity);
429}
430
431// Define this out-of-line to dissuade the C++ compiler from inlining it.
432template <typename T, bool TriviallyCopyable>
433void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
434 T *NewElts) {
435 // Move the elements over.
436 this->uninitialized_move(this->begin(), this->end(), NewElts);
437
438 // Destroy the original elements.
439 destroy_range(this->begin(), this->end());
440}
441
442// Define this out-of-line to dissuade the C++ compiler from inlining it.
443template <typename T, bool TriviallyCopyable>
444void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
445 T *NewElts, size_t NewCapacity) {
446 // If this wasn't grown from the inline copy, deallocate the old space.
447 if (!this->isSmall())
448 free(this->begin());
449
450 this->BeginX = NewElts;
451 this->Capacity = NewCapacity;
452}
453
454/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
455/// method implementations that are designed to work with trivially copyable
456/// T's. This allows using memcpy in place of copy/move construction and
457/// skipping destruction.
458template <typename T>
459class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
460 friend class SmallVectorTemplateCommon<T>;
461
462protected:
463 /// True if it's cheap enough to take parameters by value. Doing so avoids
464 /// overhead related to mitigations for reference invalidation.
465 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
466
467 /// Either const T& or T, depending on whether it's cheap enough to take
468 /// parameters by value.
469 using ValueParamT =
470 typename std::conditional<TakesParamByValue, T, const T &>::type;
471
472 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
473
474 // No need to do a destroy loop for POD's.
475 static void destroy_range(T *, T *) {}
476
477 /// Move the range [I, E) onto the uninitialized memory
478 /// starting with "Dest", constructing elements into it as needed.
479 template<typename It1, typename It2>
480 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
481 // Just do a copy.
482 uninitialized_copy(I, E, Dest);
483 }
484
485 /// Copy the range [I, E) onto the uninitialized memory
486 /// starting with "Dest", constructing elements into it as needed.
487 template<typename It1, typename It2>
488 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
489 // Arbitrary iterator types; just use the basic implementation.
490 std::uninitialized_copy(I, E, Dest);
491 }
492
493 /// Copy the range [I, E) onto the uninitialized memory
494 /// starting with "Dest", constructing elements into it as needed.
495 template <typename T1, typename T2>
496 static void uninitialized_copy(
497 T1 *I, T1 *E, T2 *Dest,
498 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
499 T2>::value> * = nullptr) {
500 // Use memcpy for PODs iterated by pointers (which includes SmallVector
501 // iterators): std::uninitialized_copy optimizes to memmove, but we can
502 // use memcpy here. Note that I and E are iterators and thus might be
503 // invalid for memcpy if they are equal.
504 if (I != E)
505 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
506 }
507
508 /// Double the size of the allocated memory, guaranteeing space for at
509 /// least one more element or MinSize if specified.
510 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
511
512 /// Reserve enough space to add one element, and return the updated element
513 /// pointer in case it was a reference to the storage.
514 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
515 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
516 }
517
518 /// Reserve enough space to add one element, and return the updated element
519 /// pointer in case it was a reference to the storage.
520 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
521 return const_cast<T *>(
522 this->reserveForParamAndGetAddressImpl(this, Elt, N));
523 }
524
525 /// Copy \p V or return a reference, depending on \a ValueParamT.
526 static ValueParamT forward_value_param(ValueParamT V) { return V; }
527
528 void growAndAssign(size_t NumElts, T Elt) {
529 // Elt has been copied in case it's an internal reference, side-stepping
530 // reference invalidation problems without losing the realloc optimization.
531 this->set_size(0);
532 this->grow(NumElts);
533 std::uninitialized_fill_n(this->begin(), NumElts, Elt);
534 this->set_size(NumElts);
535 }
536
537 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
538 // Use push_back with a copy in case Args has an internal reference,
539 // side-stepping reference invalidation problems without losing the realloc
540 // optimization.
541 push_back(T(std::forward<ArgTypes>(Args)...));
542 return this->back();
543 }
544
545public:
546 void push_back(ValueParamT Elt) {
547 const T *EltPtr = reserveForParamAndGetAddress(Elt);
548 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
549 this->set_size(this->size() + 1);
550 }
551
552 void pop_back() { this->set_size(this->size() - 1); }
553};
554
555/// This class consists of common code factored out of the SmallVector class to
556/// reduce code duplication based on the SmallVector 'N' template parameter.
557template <typename T>
558class SmallVectorImpl : public SmallVectorTemplateBase<T> {
559 using SuperClass = SmallVectorTemplateBase<T>;
560
561public:
562 using iterator = typename SuperClass::iterator;
563 using const_iterator = typename SuperClass::const_iterator;
564 using reference = typename SuperClass::reference;
565 using size_type = typename SuperClass::size_type;
566
567protected:
568 using SmallVectorTemplateBase<T>::TakesParamByValue;
569 using ValueParamT = typename SuperClass::ValueParamT;
570
571 // Default ctor - Initialize to empty.
572 explicit SmallVectorImpl(unsigned N)
573 : SmallVectorTemplateBase<T>(N) {}
574
575public:
576 SmallVectorImpl(const SmallVectorImpl &) = delete;
577
578 ~SmallVectorImpl() {
579 // Subclass has already destructed this vector's elements.
580 // If this wasn't grown from the inline copy, deallocate the old space.
581 if (!this->isSmall())
582 free(this->begin());
583 }
584
585 void clear() {
586 this->destroy_range(this->begin(), this->end());
587 this->Size = 0;
588 }
589
590private:
591 template <bool ForOverwrite> void resizeImpl(size_type N) {
592 if (N < this->size()) {
593 this->pop_back_n(this->size() - N);
594 } else if (N > this->size()) {
595 this->reserve(N);
596 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
597 if (ForOverwrite)
598 new (&*I) T;
599 else
600 new (&*I) T();
601 this->set_size(N);
602 }
603 }
604
605public:
606 void resize(size_type N) { resizeImpl<false>(N); }
607
608 /// Like resize, but \ref T is POD, the new values won't be initialized.
609 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
610
611 void resize(size_type N, ValueParamT NV) {
612 if (N == this->size())
613 return;
614
615 if (N < this->size()) {
616 this->pop_back_n(this->size() - N);
617 return;
618 }
619
620 // N > this->size(). Defer to append.
621 this->append(N - this->size(), NV);
622 }
623
624 void reserve(size_type N) {
625 if (this->capacity() < N)
626 this->grow(N);
627 }
628
629 void pop_back_n(size_type NumItems) {
630 assert(this->size() >= NumItems)(static_cast<void> (0));
631 this->destroy_range(this->end() - NumItems, this->end());
632 this->set_size(this->size() - NumItems);
633 }
634
635 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
636 T Result = ::std::move(this->back());
637 this->pop_back();
638 return Result;
639 }
640
641 void swap(SmallVectorImpl &RHS);
642
643 /// Add the specified range to the end of the SmallVector.
644 template <typename in_iter,
645 typename = std::enable_if_t<std::is_convertible<
646 typename std::iterator_traits<in_iter>::iterator_category,
647 std::input_iterator_tag>::value>>
648 void append(in_iter in_start, in_iter in_end) {
649 this->assertSafeToAddRange(in_start, in_end);
650 size_type NumInputs = std::distance(in_start, in_end);
651 this->reserve(this->size() + NumInputs);
652 this->uninitialized_copy(in_start, in_end, this->end());
653 this->set_size(this->size() + NumInputs);
654 }
655
656 /// Append \p NumInputs copies of \p Elt to the end.
657 void append(size_type NumInputs, ValueParamT Elt) {
658 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
659 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
660 this->set_size(this->size() + NumInputs);
661 }
662
663 void append(std::initializer_list<T> IL) {
664 append(IL.begin(), IL.end());
665 }
666
667 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
668
669 void assign(size_type NumElts, ValueParamT Elt) {
670 // Note that Elt could be an internal reference.
671 if (NumElts > this->capacity()) {
672 this->growAndAssign(NumElts, Elt);
673 return;
674 }
675
676 // Assign over existing elements.
677 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
678 if (NumElts > this->size())
679 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
680 else if (NumElts < this->size())
681 this->destroy_range(this->begin() + NumElts, this->end());
682 this->set_size(NumElts);
683 }
684
685 // FIXME: Consider assigning over existing elements, rather than clearing &
686 // re-initializing them - for all assign(...) variants.
687
688 template <typename in_iter,
689 typename = std::enable_if_t<std::is_convertible<
690 typename std::iterator_traits<in_iter>::iterator_category,
691 std::input_iterator_tag>::value>>
692 void assign(in_iter in_start, in_iter in_end) {
693 this->assertSafeToReferenceAfterClear(in_start, in_end);
694 clear();
695 append(in_start, in_end);
696 }
697
698 void assign(std::initializer_list<T> IL) {
699 clear();
700 append(IL);
701 }
702
703 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
704
705 iterator erase(const_iterator CI) {
706 // Just cast away constness because this is a non-const member function.
707 iterator I = const_cast<iterator>(CI);
708
709 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast<void> (0));
710
711 iterator N = I;
712 // Shift all elts down one.
713 std::move(I+1, this->end(), I);
714 // Drop the last elt.
715 this->pop_back();
716 return(N);
717 }
718
719 iterator erase(const_iterator CS, const_iterator CE) {
720 // Just cast away constness because this is a non-const member function.
721 iterator S = const_cast<iterator>(CS);
722 iterator E = const_cast<iterator>(CE);
723
724 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast<void> (0));
725
726 iterator N = S;
727 // Shift all elts down.
728 iterator I = std::move(E, this->end(), S);
729 // Drop the last elts.
730 this->destroy_range(I, this->end());
731 this->set_size(I - this->begin());
732 return(N);
733 }
734
735private:
736 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
737 // Callers ensure that ArgType is derived from T.
738 static_assert(
739 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
740 T>::value,
741 "ArgType must be derived from T!");
742
743 if (I == this->end()) { // Important special case for empty vector.
744 this->push_back(::std::forward<ArgType>(Elt));
745 return this->end()-1;
746 }
747
748 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
749
750 // Grow if necessary.
751 size_t Index = I - this->begin();
752 std::remove_reference_t<ArgType> *EltPtr =
753 this->reserveForParamAndGetAddress(Elt);
754 I = this->begin() + Index;
755
756 ::new ((void*) this->end()) T(::std::move(this->back()));
757 // Push everything else over.
758 std::move_backward(I, this->end()-1, this->end());
759 this->set_size(this->size() + 1);
760
761 // If we just moved the element we're inserting, be sure to update
762 // the reference (never happens if TakesParamByValue).
763 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
764 "ArgType must be 'T' when taking by value!");
765 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
766 ++EltPtr;
767
768 *I = ::std::forward<ArgType>(*EltPtr);
769 return I;
770 }
771
772public:
773 iterator insert(iterator I, T &&Elt) {
774 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
775 }
776
777 iterator insert(iterator I, const T &Elt) {
778 return insert_one_impl(I, this->forward_value_param(Elt));
779 }
780
781 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
782 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
783 size_t InsertElt = I - this->begin();
784
785 if (I == this->end()) { // Important special case for empty vector.
786 append(NumToInsert, Elt);
787 return this->begin()+InsertElt;
788 }
789
790 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
791
792 // Ensure there is enough space, and get the (maybe updated) address of
793 // Elt.
794 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
795
796 // Uninvalidate the iterator.
797 I = this->begin()+InsertElt;
798
799 // If there are more elements between the insertion point and the end of the
800 // range than there are being inserted, we can use a simple approach to
801 // insertion. Since we already reserved space, we know that this won't
802 // reallocate the vector.
803 if (size_t(this->end()-I) >= NumToInsert) {
804 T *OldEnd = this->end();
805 append(std::move_iterator<iterator>(this->end() - NumToInsert),
806 std::move_iterator<iterator>(this->end()));
807
808 // Copy the existing elements that get replaced.
809 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
810
811 // If we just moved the element we're inserting, be sure to update
812 // the reference (never happens if TakesParamByValue).
813 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
814 EltPtr += NumToInsert;
815
816 std::fill_n(I, NumToInsert, *EltPtr);
817 return I;
818 }
819
820 // Otherwise, we're inserting more elements than exist already, and we're
821 // not inserting at the end.
822
823 // Move over the elements that we're about to overwrite.
824 T *OldEnd = this->end();
825 this->set_size(this->size() + NumToInsert);
826 size_t NumOverwritten = OldEnd-I;
827 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
828
829 // If we just moved the element we're inserting, be sure to update
830 // the reference (never happens if TakesParamByValue).
831 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
832 EltPtr += NumToInsert;
833
834 // Replace the overwritten part.
835 std::fill_n(I, NumOverwritten, *EltPtr);
836
837 // Insert the non-overwritten middle part.
838 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
839 return I;
840 }
841
842 template <typename ItTy,
843 typename = std::enable_if_t<std::is_convertible<
844 typename std::iterator_traits<ItTy>::iterator_category,
845 std::input_iterator_tag>::value>>
846 iterator insert(iterator I, ItTy From, ItTy To) {
847 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
848 size_t InsertElt = I - this->begin();
849
850 if (I == this->end()) { // Important special case for empty vector.
851 append(From, To);
852 return this->begin()+InsertElt;
853 }
854
855 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
856
857 // Check that the reserve that follows doesn't invalidate the iterators.
858 this->assertSafeToAddRange(From, To);
859
860 size_t NumToInsert = std::distance(From, To);
861
862 // Ensure there is enough space.
863 reserve(this->size() + NumToInsert);
864
865 // Uninvalidate the iterator.
866 I = this->begin()+InsertElt;
867
868 // If there are more elements between the insertion point and the end of the
869 // range than there are being inserted, we can use a simple approach to
870 // insertion. Since we already reserved space, we know that this won't
871 // reallocate the vector.
872 if (size_t(this->end()-I) >= NumToInsert) {
873 T *OldEnd = this->end();
874 append(std::move_iterator<iterator>(this->end() - NumToInsert),
875 std::move_iterator<iterator>(this->end()));
876
877 // Copy the existing elements that get replaced.
878 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
879
880 std::copy(From, To, I);
881 return I;
882 }
883
884 // Otherwise, we're inserting more elements than exist already, and we're
885 // not inserting at the end.
886
887 // Move over the elements that we're about to overwrite.
888 T *OldEnd = this->end();
889 this->set_size(this->size() + NumToInsert);
890 size_t NumOverwritten = OldEnd-I;
891 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
892
893 // Replace the overwritten part.
894 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
895 *J = *From;
896 ++J; ++From;
897 }
898
899 // Insert the non-overwritten middle part.
900 this->uninitialized_copy(From, To, OldEnd);
901 return I;
902 }
903
904 void insert(iterator I, std::initializer_list<T> IL) {
905 insert(I, IL.begin(), IL.end());
906 }
907
908 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
909 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
910 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
911
912 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
913 this->set_size(this->size() + 1);
914 return this->back();
915 }
916
917 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
918
919 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
920
921 bool operator==(const SmallVectorImpl &RHS) const {
922 if (this->size() != RHS.size()) return false;
923 return std::equal(this->begin(), this->end(), RHS.begin());
924 }
925 bool operator!=(const SmallVectorImpl &RHS) const {
926 return !(*this == RHS);
927 }
928
929 bool operator<(const SmallVectorImpl &RHS) const {
930 return std::lexicographical_compare(this->begin(), this->end(),
931 RHS.begin(), RHS.end());
932 }
933};
934
935template <typename T>
936void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
937 if (this == &RHS) return;
938
939 // We can only avoid copying elements if neither vector is small.
940 if (!this->isSmall() && !RHS.isSmall()) {
941 std::swap(this->BeginX, RHS.BeginX);
942 std::swap(this->Size, RHS.Size);
943 std::swap(this->Capacity, RHS.Capacity);
944 return;
945 }
946 this->reserve(RHS.size());
947 RHS.reserve(this->size());
948
949 // Swap the shared elements.
950 size_t NumShared = this->size();
951 if (NumShared > RHS.size()) NumShared = RHS.size();
952 for (size_type i = 0; i != NumShared; ++i)
953 std::swap((*this)[i], RHS[i]);
954
955 // Copy over the extra elts.
956 if (this->size() > RHS.size()) {
957 size_t EltDiff = this->size() - RHS.size();
958 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
959 RHS.set_size(RHS.size() + EltDiff);
960 this->destroy_range(this->begin()+NumShared, this->end());
961 this->set_size(NumShared);
962 } else if (RHS.size() > this->size()) {
963 size_t EltDiff = RHS.size() - this->size();
964 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
965 this->set_size(this->size() + EltDiff);
966 this->destroy_range(RHS.begin()+NumShared, RHS.end());
967 RHS.set_size(NumShared);
968 }
969}
970
971template <typename T>
972SmallVectorImpl<T> &SmallVectorImpl<T>::
973 operator=(const SmallVectorImpl<T> &RHS) {
974 // Avoid self-assignment.
975 if (this == &RHS) return *this;
976
977 // If we already have sufficient space, assign the common elements, then
978 // destroy any excess.
979 size_t RHSSize = RHS.size();
980 size_t CurSize = this->size();
981 if (CurSize >= RHSSize) {
982 // Assign common elements.
983 iterator NewEnd;
984 if (RHSSize)
985 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
986 else
987 NewEnd = this->begin();
988
989 // Destroy excess elements.
990 this->destroy_range(NewEnd, this->end());
991
992 // Trim.
993 this->set_size(RHSSize);
994 return *this;
995 }
996
997 // If we have to grow to have enough elements, destroy the current elements.
998 // This allows us to avoid copying them during the grow.
999 // FIXME: don't do this if they're efficiently moveable.
1000 if (this->capacity() < RHSSize) {
1001 // Destroy current elements.
1002 this->clear();
1003 CurSize = 0;
1004 this->grow(RHSSize);
1005 } else if (CurSize) {
1006 // Otherwise, use assignment for the already-constructed elements.
1007 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1008 }
1009
1010 // Copy construct the new elements in place.
1011 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1012 this->begin()+CurSize);
1013
1014 // Set end.
1015 this->set_size(RHSSize);
1016 return *this;
1017}
1018
1019template <typename T>
1020SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1021 // Avoid self-assignment.
1022 if (this == &RHS) return *this;
1023
1024 // If the RHS isn't small, clear this vector and then steal its buffer.
1025 if (!RHS.isSmall()) {
1026 this->destroy_range(this->begin(), this->end());
1027 if (!this->isSmall()) free(this->begin());
1028 this->BeginX = RHS.BeginX;
1029 this->Size = RHS.Size;
1030 this->Capacity = RHS.Capacity;
1031 RHS.resetToSmall();
1032 return *this;
1033 }
1034
1035 // If we already have sufficient space, assign the common elements, then
1036 // destroy any excess.
1037 size_t RHSSize = RHS.size();
1038 size_t CurSize = this->size();
1039 if (CurSize >= RHSSize) {
1040 // Assign common elements.
1041 iterator NewEnd = this->begin();
1042 if (RHSSize)
1043 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1044
1045 // Destroy excess elements and trim the bounds.
1046 this->destroy_range(NewEnd, this->end());
1047 this->set_size(RHSSize);
1048
1049 // Clear the RHS.
1050 RHS.clear();
1051
1052 return *this;
1053 }
1054
1055 // If we have to grow to have enough elements, destroy the current elements.
1056 // This allows us to avoid copying them during the grow.
1057 // FIXME: this may not actually make any sense if we can efficiently move
1058 // elements.
1059 if (this->capacity() < RHSSize) {
1060 // Destroy current elements.
1061 this->clear();
1062 CurSize = 0;
1063 this->grow(RHSSize);
1064 } else if (CurSize) {
1065 // Otherwise, use assignment for the already-constructed elements.
1066 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1067 }
1068
1069 // Move-construct the new elements in place.
1070 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1071 this->begin()+CurSize);
1072
1073 // Set end.
1074 this->set_size(RHSSize);
1075
1076 RHS.clear();
1077 return *this;
1078}
1079
1080/// Storage for the SmallVector elements. This is specialized for the N=0 case
1081/// to avoid allocating unnecessary storage.
1082template <typename T, unsigned N>
1083struct SmallVectorStorage {
1084 alignas(T) char InlineElts[N * sizeof(T)];
1085};
1086
1087/// We need the storage to be properly aligned even for small-size of 0 so that
1088/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1089/// well-defined.
1090template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1091
1092/// Forward declaration of SmallVector so that
1093/// calculateSmallVectorDefaultInlinedElements can reference
1094/// `sizeof(SmallVector<T, 0>)`.
1095template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1096
1097/// Helper class for calculating the default number of inline elements for
1098/// `SmallVector<T>`.
1099///
1100/// This should be migrated to a constexpr function when our minimum
1101/// compiler support is enough for multi-statement constexpr functions.
1102template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1103 // Parameter controlling the default number of inlined elements
1104 // for `SmallVector<T>`.
1105 //
1106 // The default number of inlined elements ensures that
1107 // 1. There is at least one inlined element.
1108 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1109 // it contradicts 1.
1110 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1111
1112 // static_assert that sizeof(T) is not "too big".
1113 //
1114 // Because our policy guarantees at least one inlined element, it is possible
1115 // for an arbitrarily large inlined element to allocate an arbitrarily large
1116 // amount of inline storage. We generally consider it an antipattern for a
1117 // SmallVector to allocate an excessive amount of inline storage, so we want
1118 // to call attention to these cases and make sure that users are making an
1119 // intentional decision if they request a lot of inline storage.
1120 //
1121 // We want this assertion to trigger in pathological cases, but otherwise
1122 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1123 // larger than kPreferredSmallVectorSizeof (otherwise,
1124 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1125 // pattern seems useful in practice).
1126 //
1127 // One wrinkle is that this assertion is in theory non-portable, since
1128 // sizeof(T) is in general platform-dependent. However, we don't expect this
1129 // to be much of an issue, because most LLVM development happens on 64-bit
1130 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1131 // 32-bit hosts, dodging the issue. The reverse situation, where development
1132 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1133 // 64-bit host, is expected to be very rare.
1134 static_assert(
1135 sizeof(T) <= 256,
1136 "You are trying to use a default number of inlined elements for "
1137 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1138 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1139 "sure you really want that much inline storage.");
1140
1141 // Discount the size of the header itself when calculating the maximum inline
1142 // bytes.
1143 static constexpr size_t PreferredInlineBytes =
1144 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1145 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1146 static constexpr size_t value =
1147 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1148};
1149
1150/// This is a 'vector' (really, a variable-sized array), optimized
1151/// for the case when the array is small. It contains some number of elements
1152/// in-place, which allows it to avoid heap allocation when the actual number of
1153/// elements is below that threshold. This allows normal "small" cases to be
1154/// fast without losing generality for large inputs.
1155///
1156/// \note
1157/// In the absence of a well-motivated choice for the number of inlined
1158/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1159/// omitting the \p N). This will choose a default number of inlined elements
1160/// reasonable for allocation on the stack (for example, trying to keep \c
1161/// sizeof(SmallVector<T>) around 64 bytes).
1162///
1163/// \warning This does not attempt to be exception safe.
1164///
1165/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1166template <typename T,
1167 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1169 SmallVectorStorage<T, N> {
1170public:
1171 SmallVector() : SmallVectorImpl<T>(N) {}
1172
1173 ~SmallVector() {
1174 // Destroy the constructed elements in the vector.
1175 this->destroy_range(this->begin(), this->end());
1176 }
1177
1178 explicit SmallVector(size_t Size, const T &Value = T())
1179 : SmallVectorImpl<T>(N) {
1180 this->assign(Size, Value);
1181 }
1182
1183 template <typename ItTy,
1184 typename = std::enable_if_t<std::is_convertible<
1185 typename std::iterator_traits<ItTy>::iterator_category,
1186 std::input_iterator_tag>::value>>
1187 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1188 this->append(S, E);
1189 }
1190
1191 template <typename RangeTy>
1192 explicit SmallVector(const iterator_range<RangeTy> &R)
1193 : SmallVectorImpl<T>(N) {
1194 this->append(R.begin(), R.end());
1195 }
1196
1197 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1198 this->assign(IL);
1199 }
1200
1201 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1202 if (!RHS.empty())
1203 SmallVectorImpl<T>::operator=(RHS);
1204 }
1205
1206 SmallVector &operator=(const SmallVector &RHS) {
1207 SmallVectorImpl<T>::operator=(RHS);
1208 return *this;
1209 }
1210
1211 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1212 if (!RHS.empty())
1213 SmallVectorImpl<T>::operator=(::std::move(RHS));
1214 }
1215
1216 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1217 if (!RHS.empty())
1218 SmallVectorImpl<T>::operator=(::std::move(RHS));
1219 }
1220
1221 SmallVector &operator=(SmallVector &&RHS) {
1222 SmallVectorImpl<T>::operator=(::std::move(RHS));
1223 return *this;
1224 }
1225
1226 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1227 SmallVectorImpl<T>::operator=(::std::move(RHS));
1228 return *this;
1229 }
1230
1231 SmallVector &operator=(std::initializer_list<T> IL) {
1232 this->assign(IL);
1233 return *this;
1234 }
1235};
1236
1237template <typename T, unsigned N>
1238inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1239 return X.capacity_in_bytes();
1240}
1241
1242/// Given a range of type R, iterate the entire range and return a
1243/// SmallVector with elements of the vector. This is useful, for example,
1244/// when you want to iterate a range and then sort the results.
1245template <unsigned Size, typename R>
1246SmallVector<typename std::remove_const<typename std::remove_reference<
1247 decltype(*std::begin(std::declval<R &>()))>::type>::type,
1248 Size>
1249to_vector(R &&Range) {
1250 return {std::begin(Range), std::end(Range)};
1251}
1252
1253} // end namespace llvm
1254
1255namespace std {
1256
1257 /// Implement std::swap in terms of SmallVector swap.
1258 template<typename T>
1259 inline void
1260 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1261 LHS.swap(RHS);
1262 }
1263
1264 /// Implement std::swap in terms of SmallVector swap.
1265 template<typename T, unsigned N>
1266 inline void
1267 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1268 LHS.swap(RHS);
1269 }
1270
1271} // end namespace std
1272
1273#endif // LLVM_ADT_SMALLVECTOR_H

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/IR/IntrinsicInst.h

1//===-- llvm/IntrinsicInst.h - Intrinsic Instruction Wrappers ---*- C++ -*-===//
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//
9// This file defines classes that make it really easy to deal with intrinsic
10// functions with the isa/dyncast family of functions. In particular, this
11// allows you to do things like:
12//
13// if (MemCpyInst *MCI = dyn_cast<MemCpyInst>(Inst))
14// ... MCI->getDest() ... MCI->getSource() ...
15//
16// All intrinsic function calls are instances of the call instruction, so these
17// are all subclasses of the CallInst class. Note that none of these classes
18// has state or virtual methods, which is an important part of this gross/neat
19// hack working.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_IR_INTRINSICINST_H
24#define LLVM_IR_INTRINSICINST_H
25
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DebugInfoMetadata.h"
28#include "llvm/IR/DerivedTypes.h"
29#include "llvm/IR/FPEnv.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/GlobalVariable.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Intrinsics.h"
34#include "llvm/IR/Metadata.h"
35#include "llvm/IR/Value.h"
36#include "llvm/Support/Casting.h"
37#include <cassert>
38#include <cstdint>
39
40namespace llvm {
41
42/// A wrapper class for inspecting calls to intrinsic functions.
43/// This allows the standard isa/dyncast/cast functionality to work with calls
44/// to intrinsic functions.
45class IntrinsicInst : public CallInst {
46public:
47 IntrinsicInst() = delete;
48 IntrinsicInst(const IntrinsicInst &) = delete;
49 IntrinsicInst &operator=(const IntrinsicInst &) = delete;
50
51 /// Return the intrinsic ID of this intrinsic.
52 Intrinsic::ID getIntrinsicID() const {
53 return getCalledFunction()->getIntrinsicID();
54 }
55
56 /// Return true if swapping the first two arguments to the intrinsic produces
57 /// the same result.
58 bool isCommutative() const {
59 switch (getIntrinsicID()) {
60 case Intrinsic::maxnum:
61 case Intrinsic::minnum:
62 case Intrinsic::maximum:
63 case Intrinsic::minimum:
64 case Intrinsic::smax:
65 case Intrinsic::smin:
66 case Intrinsic::umax:
67 case Intrinsic::umin:
68 case Intrinsic::sadd_sat:
69 case Intrinsic::uadd_sat:
70 case Intrinsic::sadd_with_overflow:
71 case Intrinsic::uadd_with_overflow:
72 case Intrinsic::smul_with_overflow:
73 case Intrinsic::umul_with_overflow:
74 case Intrinsic::smul_fix:
75 case Intrinsic::umul_fix:
76 case Intrinsic::smul_fix_sat:
77 case Intrinsic::umul_fix_sat:
78 case Intrinsic::fma:
79 case Intrinsic::fmuladd:
80 return true;
81 default:
82 return false;
83 }
84 }
85
86 // Checks if the intrinsic is an annotation.
87 bool isAssumeLikeIntrinsic() const {
88 switch (getIntrinsicID()) {
89 default: break;
90 case Intrinsic::assume:
91 case Intrinsic::sideeffect:
92 case Intrinsic::pseudoprobe:
93 case Intrinsic::dbg_declare:
94 case Intrinsic::dbg_value:
95 case Intrinsic::dbg_label:
96 case Intrinsic::invariant_start:
97 case Intrinsic::invariant_end:
98 case Intrinsic::lifetime_start:
99 case Intrinsic::lifetime_end:
100 case Intrinsic::experimental_noalias_scope_decl:
101 case Intrinsic::objectsize:
102 case Intrinsic::ptr_annotation:
103 case Intrinsic::var_annotation:
104 return true;
105 }
106 return false;
107 }
108
109 // Methods for support type inquiry through isa, cast, and dyn_cast:
110 static bool classof(const CallInst *I) {
111 if (const Function *CF = I->getCalledFunction())
112 return CF->isIntrinsic();
113 return false;
114 }
115 static bool classof(const Value *V) {
116 return isa<CallInst>(V) && classof(cast<CallInst>(V));
117 }
118};
119
120/// Check if \p ID corresponds to a debug info intrinsic.
121static inline bool isDbgInfoIntrinsic(Intrinsic::ID ID) {
122 switch (ID) {
123 case Intrinsic::dbg_declare:
124 case Intrinsic::dbg_value:
125 case Intrinsic::dbg_addr:
126 case Intrinsic::dbg_label:
127 return true;
128 default:
129 return false;
130 }
131}
132
133/// This is the common base class for debug info intrinsics.
134class DbgInfoIntrinsic : public IntrinsicInst {
135public:
136 /// \name Casting methods
137 /// @{
138 static bool classof(const IntrinsicInst *I) {
139 return isDbgInfoIntrinsic(I->getIntrinsicID());
140 }
141 static bool classof(const Value *V) {
142 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
143 }
144 /// @}
145};
146
147/// This is the common base class for debug info intrinsics for variables.
148class DbgVariableIntrinsic : public DbgInfoIntrinsic {
149public:
150 // Iterator for ValueAsMetadata that internally uses direct pointer iteration
151 // over either a ValueAsMetadata* or a ValueAsMetadata**, dereferencing to the
152 // ValueAsMetadata .
153 class location_op_iterator
154 : public iterator_facade_base<location_op_iterator,
155 std::bidirectional_iterator_tag, Value *> {
156 PointerUnion<ValueAsMetadata *, ValueAsMetadata **> I;
157
158 public:
159 location_op_iterator(ValueAsMetadata *SingleIter) : I(SingleIter) {}
160 location_op_iterator(ValueAsMetadata **MultiIter) : I(MultiIter) {}
161
162 location_op_iterator(const location_op_iterator &R) : I(R.I) {}
163 location_op_iterator &operator=(const location_op_iterator &R) {
164 I = R.I;
165 return *this;
166 }
167 bool operator==(const location_op_iterator &RHS) const {
168 return I == RHS.I;
169 }
170 const Value *operator*() const {
171 ValueAsMetadata *VAM = I.is<ValueAsMetadata *>()
172 ? I.get<ValueAsMetadata *>()
173 : *I.get<ValueAsMetadata **>();
174 return VAM->getValue();
175 };
176 Value *operator*() {
177 ValueAsMetadata *VAM = I.is<ValueAsMetadata *>()
178 ? I.get<ValueAsMetadata *>()
179 : *I.get<ValueAsMetadata **>();
180 return VAM->getValue();
181 }
182 location_op_iterator &operator++() {
183 if (I.is<ValueAsMetadata *>())
184 I = I.get<ValueAsMetadata *>() + 1;
185 else
186 I = I.get<ValueAsMetadata **>() + 1;
187 return *this;
188 }
189 location_op_iterator &operator--() {
190 if (I.is<ValueAsMetadata *>())
191 I = I.get<ValueAsMetadata *>() - 1;
192 else
193 I = I.get<ValueAsMetadata **>() - 1;
194 return *this;
195 }
196 };
197
198 /// Get the locations corresponding to the variable referenced by the debug
199 /// info intrinsic. Depending on the intrinsic, this could be the
200 /// variable's value or its address.
201 iterator_range<location_op_iterator> location_ops() const;
202
203 Value *getVariableLocationOp(unsigned OpIdx) const;
204
205 void replaceVariableLocationOp(Value *OldValue, Value *NewValue);
206 void replaceVariableLocationOp(unsigned OpIdx, Value *NewValue);
207 /// Adding a new location operand will always result in this intrinsic using
208 /// an ArgList, and must always be accompanied by a new expression that uses
209 /// the new operand.
210 void addVariableLocationOps(ArrayRef<Value *> NewValues,
211 DIExpression *NewExpr);
212
213 void setVariable(DILocalVariable *NewVar) {
214 setArgOperand(1, MetadataAsValue::get(NewVar->getContext(), NewVar));
215 }
216
217 void setExpression(DIExpression *NewExpr) {
218 setArgOperand(2, MetadataAsValue::get(NewExpr->getContext(), NewExpr));
31
Called C++ object pointer is null
219 }
220
221 unsigned getNumVariableLocationOps() const {
222 if (hasArgList())
223 return cast<DIArgList>(getRawLocation())->getArgs().size();
224 return 1;
225 }
226
227 bool hasArgList() const { return isa<DIArgList>(getRawLocation()); }
228
229 /// Does this describe the address of a local variable. True for dbg.addr
230 /// and dbg.declare, but not dbg.value, which describes its value.
231 bool isAddressOfVariable() const {
232 return getIntrinsicID() != Intrinsic::dbg_value;
233 }
234
235 void setUndef() {
236 // TODO: When/if we remove duplicate values from DIArgLists, we don't need
237 // this set anymore.
238 SmallPtrSet<Value *, 4> RemovedValues;
239 for (Value *OldValue : location_ops()) {
240 if (!RemovedValues.insert(OldValue).second)
241 continue;
242 Value *Undef = UndefValue::get(OldValue->getType());
243 replaceVariableLocationOp(OldValue, Undef);
244 }
245 }
246
247 bool isUndef() const {
248 return (getNumVariableLocationOps() == 0 &&
249 !getExpression()->isComplex()) ||
250 any_of(location_ops(), [](Value *V) { return isa<UndefValue>(V); });
251 }
252
253 DILocalVariable *getVariable() const {
254 return cast<DILocalVariable>(getRawVariable());
255 }
256
257 DIExpression *getExpression() const {
258 return cast<DIExpression>(getRawExpression());
259 }
260
261 Metadata *getRawLocation() const {
262 return cast<MetadataAsValue>(getArgOperand(0))->getMetadata();
263 }
264
265 Metadata *getRawVariable() const {
266 return cast<MetadataAsValue>(getArgOperand(1))->getMetadata();
267 }
268
269 Metadata *getRawExpression() const {
270 return cast<MetadataAsValue>(getArgOperand(2))->getMetadata();
271 }
272
273 /// Use of this should generally be avoided; instead,
274 /// replaceVariableLocationOp and addVariableLocationOps should be used where
275 /// possible to avoid creating invalid state.
276 void setRawLocation(Metadata *Location) {
277 return setArgOperand(0, MetadataAsValue::get(getContext(), Location));
278 }
279
280 /// Get the size (in bits) of the variable, or fragment of the variable that
281 /// is described.
282 Optional<uint64_t> getFragmentSizeInBits() const;
283
284 /// \name Casting methods
285 /// @{
286 static bool classof(const IntrinsicInst *I) {
287 switch (I->getIntrinsicID()) {
288 case Intrinsic::dbg_declare:
289 case Intrinsic::dbg_value:
290 case Intrinsic::dbg_addr:
291 return true;
292 default:
293 return false;
294 }
295 }
296 static bool classof(const Value *V) {
297 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
298 }
299 /// @}
300private:
301 void setArgOperand(unsigned i, Value *v) {
302 DbgInfoIntrinsic::setArgOperand(i, v);
303 }
304 void setOperand(unsigned i, Value *v) { DbgInfoIntrinsic::setOperand(i, v); }
305};
306
307/// This represents the llvm.dbg.declare instruction.
308class DbgDeclareInst : public DbgVariableIntrinsic {
309public:
310 Value *getAddress() const {
311 assert(getNumVariableLocationOps() == 1 &&(static_cast<void> (0))
312 "dbg.declare must have exactly 1 location operand.")(static_cast<void> (0));
313 return getVariableLocationOp(0);
314 }
315
316 /// \name Casting methods
317 /// @{
318 static bool classof(const IntrinsicInst *I) {
319 return I->getIntrinsicID() == Intrinsic::dbg_declare;
320 }
321 static bool classof(const Value *V) {
322 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
323 }
324 /// @}
325};
326
327/// This represents the llvm.dbg.addr instruction.
328class DbgAddrIntrinsic : public DbgVariableIntrinsic {
329public:
330 Value *getAddress() const {
331 assert(getNumVariableLocationOps() == 1 &&(static_cast<void> (0))
332 "dbg.addr must have exactly 1 location operand.")(static_cast<void> (0));
333 return getVariableLocationOp(0);
334 }
335
336 /// \name Casting methods
337 /// @{
338 static bool classof(const IntrinsicInst *I) {
339 return I->getIntrinsicID() == Intrinsic::dbg_addr;
340 }
341 static bool classof(const Value *V) {
342 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
343 }
344};
345
346/// This represents the llvm.dbg.value instruction.
347class DbgValueInst : public DbgVariableIntrinsic {
348public:
349 // The default argument should only be used in ISel, and the default option
350 // should be removed once ISel support for multiple location ops is complete.
351 Value *getValue(unsigned OpIdx = 0) const {
352 return getVariableLocationOp(OpIdx);
353 }
354 iterator_range<location_op_iterator> getValues() const {
355 return location_ops();
356 }
357
358 /// \name Casting methods
359 /// @{
360 static bool classof(const IntrinsicInst *I) {
361 return I->getIntrinsicID() == Intrinsic::dbg_value;
362 }
363 static bool classof(const Value *V) {
364 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
365 }
366 /// @}
367};
368
369/// This represents the llvm.dbg.label instruction.
370class DbgLabelInst : public DbgInfoIntrinsic {
371public:
372 DILabel *getLabel() const { return cast<DILabel>(getRawLabel()); }
373
374 Metadata *getRawLabel() const {
375 return cast<MetadataAsValue>(getArgOperand(0))->getMetadata();
376 }
377
378 /// Methods for support type inquiry through isa, cast, and dyn_cast:
379 /// @{
380 static bool classof(const IntrinsicInst *I) {
381 return I->getIntrinsicID() == Intrinsic::dbg_label;
382 }
383 static bool classof(const Value *V) {
384 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
385 }
386 /// @}
387};
388
389/// This is the common base class for vector predication intrinsics.
390class VPIntrinsic : public IntrinsicInst {
391public:
392 /// \brief Declares a llvm.vp.* intrinsic in \p M that matches the parameters
393 /// \p Params.
394 static Function *getDeclarationForParams(Module *M, Intrinsic::ID,
395 ArrayRef<Value *> Params);
396
397 static Optional<unsigned> getMaskParamPos(Intrinsic::ID IntrinsicID);
398 static Optional<unsigned> getVectorLengthParamPos(Intrinsic::ID IntrinsicID);
399
400 /// The llvm.vp.* intrinsics for this instruction Opcode
401 static Intrinsic::ID getForOpcode(unsigned OC);
402
403 // Whether \p ID is a VP intrinsic ID.
404 static bool isVPIntrinsic(Intrinsic::ID);
405
406 /// \return The mask parameter or nullptr.
407 Value *getMaskParam() const;
408 void setMaskParam(Value *);
409
410 /// \return The vector length parameter or nullptr.
411 Value *getVectorLengthParam() const;
412 void setVectorLengthParam(Value *);
413
414 /// \return Whether the vector length param can be ignored.
415 bool canIgnoreVectorLengthParam() const;
416
417 /// \return The static element count (vector number of elements) the vector
418 /// length parameter applies to.
419 ElementCount getStaticVectorLength() const;
420
421 /// \return The alignment of the pointer used by this load/store/gather or
422 /// scatter.
423 MaybeAlign getPointerAlignment() const;
424 // MaybeAlign setPointerAlignment(Align NewAlign); // TODO
425
426 /// \return The pointer operand of this load,store, gather or scatter.
427 Value *getMemoryPointerParam() const;
428 static Optional<unsigned> getMemoryPointerParamPos(Intrinsic::ID);
429
430 /// \return The data (payload) operand of this store or scatter.
431 Value *getMemoryDataParam() const;
432 static Optional<unsigned> getMemoryDataParamPos(Intrinsic::ID);
433
434 // Methods for support type inquiry through isa, cast, and dyn_cast:
435 static bool classof(const IntrinsicInst *I) {
436 return isVPIntrinsic(I->getIntrinsicID());
437 }
438 static bool classof(const Value *V) {
439 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
440 }
441
442 // Equivalent non-predicated opcode
443 Optional<unsigned> getFunctionalOpcode() const {
444 return getFunctionalOpcodeForVP(getIntrinsicID());
445 }
446
447 // Equivalent non-predicated opcode
448 static Optional<unsigned> getFunctionalOpcodeForVP(Intrinsic::ID ID);
449};
450
451/// This represents vector predication reduction intrinsics.
452class VPReductionIntrinsic : public VPIntrinsic {
453public:
454 static bool isVPReduction(Intrinsic::ID ID);
455
456 unsigned getStartParamPos() const;
457 unsigned getVectorParamPos() const;
458
459 static Optional<unsigned> getStartParamPos(Intrinsic::ID ID);
460 static Optional<unsigned> getVectorParamPos(Intrinsic::ID ID);
461
462 /// Methods for support type inquiry through isa, cast, and dyn_cast:
463 /// @{
464 static bool classof(const IntrinsicInst *I) {
465 return VPReductionIntrinsic::isVPReduction(I->getIntrinsicID());
466 }
467 static bool classof(const Value *V) {
468 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
469 }
470 /// @}
471};
472
473/// This is the common base class for constrained floating point intrinsics.
474class ConstrainedFPIntrinsic : public IntrinsicInst {
475public:
476 bool isUnaryOp() const;
477 bool isTernaryOp() const;
478 Optional<RoundingMode> getRoundingMode() const;
479 Optional<fp::ExceptionBehavior> getExceptionBehavior() const;
480 bool isDefaultFPEnvironment() const;
481
482 // Methods for support type inquiry through isa, cast, and dyn_cast:
483 static bool classof(const IntrinsicInst *I);
484 static bool classof(const Value *V) {
485 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
486 }
487};
488
489/// Constrained floating point compare intrinsics.
490class ConstrainedFPCmpIntrinsic : public ConstrainedFPIntrinsic {
491public:
492 FCmpInst::Predicate getPredicate() const;
493
494 // Methods for support type inquiry through isa, cast, and dyn_cast:
495 static bool classof(const IntrinsicInst *I) {
496 switch (I->getIntrinsicID()) {
497 case Intrinsic::experimental_constrained_fcmp:
498 case Intrinsic::experimental_constrained_fcmps:
499 return true;
500 default:
501 return false;
502 }
503 }
504 static bool classof(const Value *V) {
505 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
506 }
507};
508
509/// This class represents min/max intrinsics.
510class MinMaxIntrinsic : public IntrinsicInst {
511public:
512 static bool classof(const IntrinsicInst *I) {
513 switch (I->getIntrinsicID()) {
514 case Intrinsic::umin:
515 case Intrinsic::umax:
516 case Intrinsic::smin:
517 case Intrinsic::smax:
518 return true;
519 default:
520 return false;
521 }
522 }
523 static bool classof(const Value *V) {
524 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
525 }
526
527 Value *getLHS() const { return const_cast<Value *>(getArgOperand(0)); }
528 Value *getRHS() const { return const_cast<Value *>(getArgOperand(1)); }
529
530 /// Returns the comparison predicate underlying the intrinsic.
531 ICmpInst::Predicate getPredicate() const {
532 switch (getIntrinsicID()) {
533 case Intrinsic::umin:
534 return ICmpInst::Predicate::ICMP_ULT;
535 case Intrinsic::umax:
536 return ICmpInst::Predicate::ICMP_UGT;
537 case Intrinsic::smin:
538 return ICmpInst::Predicate::ICMP_SLT;
539 case Intrinsic::smax:
540 return ICmpInst::Predicate::ICMP_SGT;
541 default:
542 llvm_unreachable("Invalid intrinsic")__builtin_unreachable();
543 }
544 }
545
546 /// Whether the intrinsic is signed or unsigned.
547 bool isSigned() const { return ICmpInst::isSigned(getPredicate()); };
548};
549
550/// This class represents an intrinsic that is based on a binary operation.
551/// This includes op.with.overflow and saturating add/sub intrinsics.
552class BinaryOpIntrinsic : public IntrinsicInst {
553public:
554 static bool classof(const IntrinsicInst *I) {
555 switch (I->getIntrinsicID()) {
556 case Intrinsic::uadd_with_overflow:
557 case Intrinsic::sadd_with_overflow:
558 case Intrinsic::usub_with_overflow:
559 case Intrinsic::ssub_with_overflow:
560 case Intrinsic::umul_with_overflow:
561 case Intrinsic::smul_with_overflow:
562 case Intrinsic::uadd_sat:
563 case Intrinsic::sadd_sat:
564 case Intrinsic::usub_sat:
565 case Intrinsic::ssub_sat:
566 return true;
567 default:
568 return false;
569 }
570 }
571 static bool classof(const Value *V) {
572 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
573 }
574
575 Value *getLHS() const { return const_cast<Value *>(getArgOperand(0)); }
576 Value *getRHS() const { return const_cast<Value *>(getArgOperand(1)); }
577
578 /// Returns the binary operation underlying the intrinsic.
579 Instruction::BinaryOps getBinaryOp() const;
580
581 /// Whether the intrinsic is signed or unsigned.
582 bool isSigned() const;
583
584 /// Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
585 unsigned getNoWrapKind() const;
586};
587
588/// Represents an op.with.overflow intrinsic.
589class WithOverflowInst : public BinaryOpIntrinsic {
590public:
591 static bool classof(const IntrinsicInst *I) {
592 switch (I->getIntrinsicID()) {
593 case Intrinsic::uadd_with_overflow:
594 case Intrinsic::sadd_with_overflow:
595 case Intrinsic::usub_with_overflow:
596 case Intrinsic::ssub_with_overflow:
597 case Intrinsic::umul_with_overflow:
598 case Intrinsic::smul_with_overflow:
599 return true;
600 default:
601 return false;
602 }
603 }
604 static bool classof(const Value *V) {
605 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
606 }
607};
608
609/// Represents a saturating add/sub intrinsic.
610class SaturatingInst : public BinaryOpIntrinsic {
611public:
612 static bool classof(const IntrinsicInst *I) {
613 switch (I->getIntrinsicID()) {
614 case Intrinsic::uadd_sat:
615 case Intrinsic::sadd_sat:
616 case Intrinsic::usub_sat:
617 case Intrinsic::ssub_sat:
618 return true;
619 default:
620 return false;
621 }
622 }
623 static bool classof(const Value *V) {
624 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
625 }
626};
627
628/// Common base class for all memory intrinsics. Simply provides
629/// common methods.
630/// Written as CRTP to avoid a common base class amongst the
631/// three atomicity hierarchies.
632template <typename Derived> class MemIntrinsicBase : public IntrinsicInst {
633private:
634 enum { ARG_DEST = 0, ARG_LENGTH = 2 };
635
636public:
637 Value *getRawDest() const {
638 return const_cast<Value *>(getArgOperand(ARG_DEST));
639 }
640 const Use &getRawDestUse() const { return getArgOperandUse(ARG_DEST); }
641 Use &getRawDestUse() { return getArgOperandUse(ARG_DEST); }
642
643 Value *getLength() const {
644 return const_cast<Value *>(getArgOperand(ARG_LENGTH));
645 }
646 const Use &getLengthUse() const { return getArgOperandUse(ARG_LENGTH); }
647 Use &getLengthUse() { return getArgOperandUse(ARG_LENGTH); }
648
649 /// This is just like getRawDest, but it strips off any cast
650 /// instructions (including addrspacecast) that feed it, giving the
651 /// original input. The returned value is guaranteed to be a pointer.
652 Value *getDest() const { return getRawDest()->stripPointerCasts(); }
653
654 unsigned getDestAddressSpace() const {
655 return cast<PointerType>(getRawDest()->getType())->getAddressSpace();
656 }
657
658 /// FIXME: Remove this function once transition to Align is over.
659 /// Use getDestAlign() instead.
660 unsigned getDestAlignment() const {
661 if (auto MA = getParamAlign(ARG_DEST))
662 return MA->value();
663 return 0;
664 }
665 MaybeAlign getDestAlign() const { return getParamAlign(ARG_DEST); }
666
667 /// Set the specified arguments of the instruction.
668 void setDest(Value *Ptr) {
669 assert(getRawDest()->getType() == Ptr->getType() &&(static_cast<void> (0))
670 "setDest called with pointer of wrong type!")(static_cast<void> (0));
671 setArgOperand(ARG_DEST, Ptr);
672 }
673
674 /// FIXME: Remove this function once transition to Align is over.
675 /// Use the version that takes MaybeAlign instead of this one.
676 void setDestAlignment(unsigned Alignment) {
677 setDestAlignment(MaybeAlign(Alignment));
678 }
679 void setDestAlignment(MaybeAlign Alignment) {
680 removeParamAttr(ARG_DEST, Attribute::Alignment);
681 if (Alignment)
682 addParamAttr(ARG_DEST,
683 Attribute::getWithAlignment(getContext(), *Alignment));
684 }
685 void setDestAlignment(Align Alignment) {
686 removeParamAttr(ARG_DEST, Attribute::Alignment);
687 addParamAttr(ARG_DEST,
688 Attribute::getWithAlignment(getContext(), Alignment));
689 }
690
691 void setLength(Value *L) {
692 assert(getLength()->getType() == L->getType() &&(static_cast<void> (0))
693 "setLength called with value of wrong type!")(static_cast<void> (0));
694 setArgOperand(ARG_LENGTH, L);
695 }
696};
697
698/// Common base class for all memory transfer intrinsics. Simply provides
699/// common methods.
700template <class BaseCL> class MemTransferBase : public BaseCL {
701private:
702 enum { ARG_SOURCE = 1 };
703
704public:
705 /// Return the arguments to the instruction.
706 Value *getRawSource() const {
707 return const_cast<Value *>(BaseCL::getArgOperand(ARG_SOURCE));
708 }
709 const Use &getRawSourceUse() const {
710 return BaseCL::getArgOperandUse(ARG_SOURCE);
711 }
712 Use &getRawSourceUse() { return BaseCL::getArgOperandUse(ARG_SOURCE); }
713
714 /// This is just like getRawSource, but it strips off any cast
715 /// instructions that feed it, giving the original input. The returned
716 /// value is guaranteed to be a pointer.
717 Value *getSource() const { return getRawSource()->stripPointerCasts(); }
718
719 unsigned getSourceAddressSpace() const {
720 return cast<PointerType>(getRawSource()->getType())->getAddressSpace();
721 }
722
723 /// FIXME: Remove this function once transition to Align is over.
724 /// Use getSourceAlign() instead.
725 unsigned getSourceAlignment() const {
726 if (auto MA = BaseCL::getParamAlign(ARG_SOURCE))
727 return MA->value();
728 return 0;
729 }
730
731 MaybeAlign getSourceAlign() const {
732 return BaseCL::getParamAlign(ARG_SOURCE);
733 }
734
735 void setSource(Value *Ptr) {
736 assert(getRawSource()->getType() == Ptr->getType() &&(static_cast<void> (0))
737 "setSource called with pointer of wrong type!")(static_cast<void> (0));
738 BaseCL::setArgOperand(ARG_SOURCE, Ptr);
739 }
740
741 /// FIXME: Remove this function once transition to Align is over.
742 /// Use the version that takes MaybeAlign instead of this one.
743 void setSourceAlignment(unsigned Alignment) {
744 setSourceAlignment(MaybeAlign(Alignment));
745 }
746 void setSourceAlignment(MaybeAlign Alignment) {
747 BaseCL::removeParamAttr(ARG_SOURCE, Attribute::Alignment);
748 if (Alignment)
749 BaseCL::addParamAttr(ARG_SOURCE, Attribute::getWithAlignment(
750 BaseCL::getContext(), *Alignment));
751 }
752 void setSourceAlignment(Align Alignment) {
753 BaseCL::removeParamAttr(ARG_SOURCE, Attribute::Alignment);
754 BaseCL::addParamAttr(ARG_SOURCE, Attribute::getWithAlignment(
755 BaseCL::getContext(), Alignment));
756 }
757};
758
759/// Common base class for all memset intrinsics. Simply provides
760/// common methods.
761template <class BaseCL> class MemSetBase : public BaseCL {
762private:
763 enum { ARG_VALUE = 1 };
764
765public:
766 Value *getValue() const {
767 return const_cast<Value *>(BaseCL::getArgOperand(ARG_VALUE));
768 }
769 const Use &getValueUse() const { return BaseCL::getArgOperandUse(ARG_VALUE); }
770 Use &getValueUse() { return BaseCL::getArgOperandUse(ARG_VALUE); }
771
772 void setValue(Value *Val) {
773 assert(getValue()->getType() == Val->getType() &&(static_cast<void> (0))
774 "setValue called with value of wrong type!")(static_cast<void> (0));
775 BaseCL::setArgOperand(ARG_VALUE, Val);
776 }
777};
778
779// The common base class for the atomic memset/memmove/memcpy intrinsics
780// i.e. llvm.element.unordered.atomic.memset/memcpy/memmove
781class AtomicMemIntrinsic : public MemIntrinsicBase<AtomicMemIntrinsic> {
782private:
783 enum { ARG_ELEMENTSIZE = 3 };
784
785public:
786 Value *getRawElementSizeInBytes() const {
787 return const_cast<Value *>(getArgOperand(ARG_ELEMENTSIZE));
788 }
789
790 ConstantInt *getElementSizeInBytesCst() const {
791 return cast<ConstantInt>(getRawElementSizeInBytes());
792 }
793
794 uint32_t getElementSizeInBytes() const {
795 return getElementSizeInBytesCst()->getZExtValue();
796 }
797
798 void setElementSizeInBytes(Constant *V) {
799 assert(V->getType() == Type::getInt8Ty(getContext()) &&(static_cast<void> (0))
800 "setElementSizeInBytes called with value of wrong type!")(static_cast<void> (0));
801 setArgOperand(ARG_ELEMENTSIZE, V);
802 }
803
804 static bool classof(const IntrinsicInst *I) {
805 switch (I->getIntrinsicID()) {
806 case Intrinsic::memcpy_element_unordered_atomic:
807 case Intrinsic::memmove_element_unordered_atomic:
808 case Intrinsic::memset_element_unordered_atomic:
809 return true;
810 default:
811 return false;
812 }
813 }
814 static bool classof(const Value *V) {
815 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
816 }
817};
818
819/// This class represents atomic memset intrinsic
820// i.e. llvm.element.unordered.atomic.memset
821class AtomicMemSetInst : public MemSetBase<AtomicMemIntrinsic> {
822public:
823 static bool classof(const IntrinsicInst *I) {
824 return I->getIntrinsicID() == Intrinsic::memset_element_unordered_atomic;
825 }
826 static bool classof(const Value *V) {
827 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
828 }
829};
830
831// This class wraps the atomic memcpy/memmove intrinsics
832// i.e. llvm.element.unordered.atomic.memcpy/memmove
833class AtomicMemTransferInst : public MemTransferBase<AtomicMemIntrinsic> {
834public:
835 static bool classof(const IntrinsicInst *I) {
836 switch (I->getIntrinsicID()) {
837 case Intrinsic::memcpy_element_unordered_atomic:
838 case Intrinsic::memmove_element_unordered_atomic:
839 return true;
840 default:
841 return false;
842 }
843 }
844 static bool classof(const Value *V) {
845 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
846 }
847};
848
849/// This class represents the atomic memcpy intrinsic
850/// i.e. llvm.element.unordered.atomic.memcpy
851class AtomicMemCpyInst : public AtomicMemTransferInst {
852public:
853 static bool classof(const IntrinsicInst *I) {
854 return I->getIntrinsicID() == Intrinsic::memcpy_element_unordered_atomic;
855 }
856 static bool classof(const Value *V) {
857 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
858 }
859};
860
861/// This class represents the atomic memmove intrinsic
862/// i.e. llvm.element.unordered.atomic.memmove
863class AtomicMemMoveInst : public AtomicMemTransferInst {
864public:
865 static bool classof(const IntrinsicInst *I) {
866 return I->getIntrinsicID() == Intrinsic::memmove_element_unordered_atomic;
867 }
868 static bool classof(const Value *V) {
869 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
870 }
871};
872
873/// This is the common base class for memset/memcpy/memmove.
874class MemIntrinsic : public MemIntrinsicBase<MemIntrinsic> {
875private:
876 enum { ARG_VOLATILE = 3 };
877
878public:
879 ConstantInt *getVolatileCst() const {
880 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(ARG_VOLATILE)));
881 }
882
883 bool isVolatile() const { return !getVolatileCst()->isZero(); }
884
885 void setVolatile(Constant *V) { setArgOperand(ARG_VOLATILE, V); }
886
887 // Methods for support type inquiry through isa, cast, and dyn_cast:
888 static bool classof(const IntrinsicInst *I) {
889 switch (I->getIntrinsicID()) {
890 case Intrinsic::memcpy:
891 case Intrinsic::memmove:
892 case Intrinsic::memset:
893 case Intrinsic::memcpy_inline:
894 return true;
895 default:
896 return false;
897 }
898 }
899 static bool classof(const Value *V) {
900 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
901 }
902};
903
904/// This class wraps the llvm.memset intrinsic.
905class MemSetInst : public MemSetBase<MemIntrinsic> {
906public:
907 // Methods for support type inquiry through isa, cast, and dyn_cast:
908 static bool classof(const IntrinsicInst *I) {
909 return I->getIntrinsicID() == Intrinsic::memset;
910 }
911 static bool classof(const Value *V) {
912 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
913 }
914};
915
916/// This class wraps the llvm.memcpy/memmove intrinsics.
917class MemTransferInst : public MemTransferBase<MemIntrinsic> {
918public:
919 // Methods for support type inquiry through isa, cast, and dyn_cast:
920 static bool classof(const IntrinsicInst *I) {
921 switch (I->getIntrinsicID()) {
922 case Intrinsic::memcpy:
923 case Intrinsic::memmove:
924 case Intrinsic::memcpy_inline:
925 return true;
926 default:
927 return false;
928 }
929 }
930 static bool classof(const Value *V) {
931 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
932 }
933};
934
935/// This class wraps the llvm.memcpy intrinsic.
936class MemCpyInst : public MemTransferInst {
937public:
938 // Methods for support type inquiry through isa, cast, and dyn_cast:
939 static bool classof(const IntrinsicInst *I) {
940 return I->getIntrinsicID() == Intrinsic::memcpy ||
941 I->getIntrinsicID() == Intrinsic::memcpy_inline;
942 }
943 static bool classof(const Value *V) {
944 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
945 }
946};
947
948/// This class wraps the llvm.memmove intrinsic.
949class MemMoveInst : public MemTransferInst {
950public:
951 // Methods for support type inquiry through isa, cast, and dyn_cast:
952 static bool classof(const IntrinsicInst *I) {
953 return I->getIntrinsicID() == Intrinsic::memmove;
954 }
955 static bool classof(const Value *V) {
956 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
957 }
958};
959
960/// This class wraps the llvm.memcpy.inline intrinsic.
961class MemCpyInlineInst : public MemCpyInst {
962public:
963 ConstantInt *getLength() const {
964 return cast<ConstantInt>(MemCpyInst::getLength());
965 }
966 // Methods for support type inquiry through isa, cast, and dyn_cast:
967 static bool classof(const IntrinsicInst *I) {
968 return I->getIntrinsicID() == Intrinsic::memcpy_inline;
969 }
970 static bool classof(const Value *V) {
971 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
972 }
973};
974
975// The common base class for any memset/memmove/memcpy intrinsics;
976// whether they be atomic or non-atomic.
977// i.e. llvm.element.unordered.atomic.memset/memcpy/memmove
978// and llvm.memset/memcpy/memmove
979class AnyMemIntrinsic : public MemIntrinsicBase<AnyMemIntrinsic> {
980public:
981 bool isVolatile() const {
982 // Only the non-atomic intrinsics can be volatile
983 if (auto *MI = dyn_cast<MemIntrinsic>(this))
984 return MI->isVolatile();
985 return false;
986 }
987
988 static bool classof(const IntrinsicInst *I) {
989 switch (I->getIntrinsicID()) {
990 case Intrinsic::memcpy:
991 case Intrinsic::memcpy_inline:
992 case Intrinsic::memmove:
993 case Intrinsic::memset:
994 case Intrinsic::memcpy_element_unordered_atomic:
995 case Intrinsic::memmove_element_unordered_atomic:
996 case Intrinsic::memset_element_unordered_atomic:
997 return true;
998 default:
999 return false;
1000 }
1001 }
1002 static bool classof(const Value *V) {
1003 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1004 }
1005};
1006
1007/// This class represents any memset intrinsic
1008// i.e. llvm.element.unordered.atomic.memset
1009// and llvm.memset
1010class AnyMemSetInst : public MemSetBase<AnyMemIntrinsic> {
1011public:
1012 static bool classof(const IntrinsicInst *I) {
1013 switch (I->getIntrinsicID()) {
1014 case Intrinsic::memset:
1015 case Intrinsic::memset_element_unordered_atomic:
1016 return true;
1017 default:
1018 return false;
1019 }
1020 }
1021 static bool classof(const Value *V) {
1022 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1023 }
1024};
1025
1026// This class wraps any memcpy/memmove intrinsics
1027// i.e. llvm.element.unordered.atomic.memcpy/memmove
1028// and llvm.memcpy/memmove
1029class AnyMemTransferInst : public MemTransferBase<AnyMemIntrinsic> {
1030public:
1031 static bool classof(const IntrinsicInst *I) {
1032 switch (I->getIntrinsicID()) {
1033 case Intrinsic::memcpy:
1034 case Intrinsic::memcpy_inline:
1035 case Intrinsic::memmove:
1036 case Intrinsic::memcpy_element_unordered_atomic:
1037 case Intrinsic::memmove_element_unordered_atomic:
1038 return true;
1039 default:
1040 return false;
1041 }
1042 }
1043 static bool classof(const Value *V) {
1044 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1045 }
1046};
1047
1048/// This class represents any memcpy intrinsic
1049/// i.e. llvm.element.unordered.atomic.memcpy
1050/// and llvm.memcpy
1051class AnyMemCpyInst : public AnyMemTransferInst {
1052public:
1053 static bool classof(const IntrinsicInst *I) {
1054 switch (I->getIntrinsicID()) {
1055 case Intrinsic::memcpy:
1056 case Intrinsic::memcpy_inline:
1057 case Intrinsic::memcpy_element_unordered_atomic:
1058 return true;
1059 default:
1060 return false;
1061 }
1062 }
1063 static bool classof(const Value *V) {
1064 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1065 }
1066};
1067
1068/// This class represents any memmove intrinsic
1069/// i.e. llvm.element.unordered.atomic.memmove
1070/// and llvm.memmove
1071class AnyMemMoveInst : public AnyMemTransferInst {
1072public:
1073 static bool classof(const IntrinsicInst *I) {
1074 switch (I->getIntrinsicID()) {
1075 case Intrinsic::memmove:
1076 case Intrinsic::memmove_element_unordered_atomic:
1077 return true;
1078 default:
1079 return false;
1080 }
1081 }
1082 static bool classof(const Value *V) {
1083 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1084 }
1085};
1086
1087/// This represents the llvm.va_start intrinsic.
1088class VAStartInst : public IntrinsicInst {
1089public:
1090 static bool classof(const IntrinsicInst *I) {
1091 return I->getIntrinsicID() == Intrinsic::vastart;
1092 }
1093 static bool classof(const Value *V) {
1094 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1095 }
1096
1097 Value *getArgList() const { return const_cast<Value *>(getArgOperand(0)); }
1098};
1099
1100/// This represents the llvm.va_end intrinsic.
1101class VAEndInst : public IntrinsicInst {
1102public:
1103 static bool classof(const IntrinsicInst *I) {
1104 return I->getIntrinsicID() == Intrinsic::vaend;
1105 }
1106 static bool classof(const Value *V) {
1107 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1108 }
1109
1110 Value *getArgList() const { return const_cast<Value *>(getArgOperand(0)); }
1111};
1112
1113/// This represents the llvm.va_copy intrinsic.
1114class VACopyInst : public IntrinsicInst {
1115public:
1116 static bool classof(const IntrinsicInst *I) {
1117 return I->getIntrinsicID() == Intrinsic::vacopy;
1118 }
1119 static bool classof(const Value *V) {
1120 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1121 }
1122
1123 Value *getDest() const { return const_cast<Value *>(getArgOperand(0)); }
1124 Value *getSrc() const { return const_cast<Value *>(getArgOperand(1)); }
1125};
1126
1127/// This represents the llvm.instrprof_increment intrinsic.
1128class InstrProfIncrementInst : public IntrinsicInst {
1129public:
1130 static bool classof(const IntrinsicInst *I) {
1131 return I->getIntrinsicID() == Intrinsic::instrprof_increment;
1132 }
1133 static bool classof(const Value *V) {
1134 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1135 }
1136
1137 GlobalVariable *getName() const {
1138 return cast<GlobalVariable>(
1139 const_cast<Value *>(getArgOperand(0))->stripPointerCasts());
1140 }
1141
1142 ConstantInt *getHash() const {
1143 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
1144 }
1145
1146 ConstantInt *getNumCounters() const {
1147 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(2)));
1148 }
1149
1150 ConstantInt *getIndex() const {
1151 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(3)));
1152 }
1153
1154 Value *getStep() const;
1155};
1156
1157class InstrProfIncrementInstStep : public InstrProfIncrementInst {
1158public:
1159 static bool classof(const IntrinsicInst *I) {
1160 return I->getIntrinsicID() == Intrinsic::instrprof_increment_step;
1161 }
1162 static bool classof(const Value *V) {
1163 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1164 }
1165};
1166
1167/// This represents the llvm.instrprof_value_profile intrinsic.
1168class InstrProfValueProfileInst : public IntrinsicInst {
1169public:
1170 static bool classof(const IntrinsicInst *I) {
1171 return I->getIntrinsicID() == Intrinsic::instrprof_value_profile;
1172 }
1173 static bool classof(const Value *V) {
1174 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1175 }
1176
1177 GlobalVariable *getName() const {
1178 return cast<GlobalVariable>(
1179 const_cast<Value *>(getArgOperand(0))->stripPointerCasts());
1180 }
1181
1182 ConstantInt *getHash() const {
1183 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
1184 }
1185
1186 Value *getTargetValue() const {
1187 return cast<Value>(const_cast<Value *>(getArgOperand(2)));
1188 }
1189
1190 ConstantInt *getValueKind() const {
1191 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(3)));
1192 }
1193
1194 // Returns the value site index.
1195 ConstantInt *getIndex() const {
1196 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(4)));
1197 }
1198};
1199
1200class PseudoProbeInst : public IntrinsicInst {
1201public:
1202 static bool classof(const IntrinsicInst *I) {
1203 return I->getIntrinsicID() == Intrinsic::pseudoprobe;
1204 }
1205
1206 static bool classof(const Value *V) {
1207 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1208 }
1209
1210 ConstantInt *getFuncGuid() const {
1211 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(0)));
1212 }
1213
1214 ConstantInt *getIndex() const {
1215 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
1216 }
1217
1218 ConstantInt *getAttributes() const {
1219 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(2)));
1220 }
1221
1222 ConstantInt *getFactor() const {
1223 return cast<ConstantInt>(const_cast<Value *>(getArgOperand(3)));
1224 }
1225};
1226
1227class NoAliasScopeDeclInst : public IntrinsicInst {
1228public:
1229 static bool classof(const IntrinsicInst *I) {
1230 return I->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl;
1231 }
1232
1233 static bool classof(const Value *V) {
1234 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1235 }
1236
1237 MDNode *getScopeList() const {
1238 auto *MV =
1239 cast<MetadataAsValue>(getOperand(Intrinsic::NoAliasScopeDeclScopeArg));
1240 return cast<MDNode>(MV->getMetadata());
1241 }
1242
1243 void setScopeList(MDNode *ScopeList) {
1244 setOperand(Intrinsic::NoAliasScopeDeclScopeArg,
1245 MetadataAsValue::get(getContext(), ScopeList));
1246 }
1247};
1248
1249// Defined in Statepoint.h -- NOT a subclass of IntrinsicInst
1250class GCStatepointInst;
1251
1252/// Common base class for representing values projected from a statepoint.
1253/// Currently, the only projections available are gc.result and gc.relocate.
1254class GCProjectionInst : public IntrinsicInst {
1255public:
1256 static bool classof(const IntrinsicInst *I) {
1257 return I->getIntrinsicID() == Intrinsic::experimental_gc_relocate ||
1258 I->getIntrinsicID() == Intrinsic::experimental_gc_result;
1259 }
1260
1261 static bool classof(const Value *V) {
1262 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1263 }
1264
1265 /// Return true if this relocate is tied to the invoke statepoint.
1266 /// This includes relocates which are on the unwinding path.
1267 bool isTiedToInvoke() const {
1268 const Value *Token = getArgOperand(0);
1269
1270 return isa<LandingPadInst>(Token) || isa<InvokeInst>(Token);
1271 }
1272
1273 /// The statepoint with which this gc.relocate is associated.
1274 const GCStatepointInst *getStatepoint() const;
1275};
1276
1277/// Represents calls to the gc.relocate intrinsic.
1278class GCRelocateInst : public GCProjectionInst {
1279public:
1280 static bool classof(const IntrinsicInst *I) {
1281 return I->getIntrinsicID() == Intrinsic::experimental_gc_relocate;
1282 }
1283
1284 static bool classof(const Value *V) {
1285 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1286 }
1287
1288 /// The index into the associate statepoint's argument list
1289 /// which contains the base pointer of the pointer whose
1290 /// relocation this gc.relocate describes.
1291 unsigned getBasePtrIndex() const {
1292 return cast<ConstantInt>(getArgOperand(1))->getZExtValue();
1293 }
1294
1295 /// The index into the associate statepoint's argument list which
1296 /// contains the pointer whose relocation this gc.relocate describes.
1297 unsigned getDerivedPtrIndex() const {
1298 return cast<ConstantInt>(getArgOperand(2))->getZExtValue();
1299 }
1300
1301 Value *getBasePtr() const;
1302 Value *getDerivedPtr() const;
1303};
1304
1305/// Represents calls to the gc.result intrinsic.
1306class GCResultInst : public GCProjectionInst {
1307public:
1308 static bool classof(const IntrinsicInst *I) {
1309 return I->getIntrinsicID() == Intrinsic::experimental_gc_result;
1310 }
1311
1312 static bool classof(const Value *V) {
1313 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1314 }
1315};
1316
1317
1318/// This represents the llvm.assume intrinsic.
1319class AssumeInst : public IntrinsicInst {
1320public:
1321 static bool classof(const IntrinsicInst *I) {
1322 return I->getIntrinsicID() == Intrinsic::assume;
1323 }
1324 static bool classof(const Value *V) {
1325 return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
1326 }
1327};
1328
1329} // end namespace llvm
1330
1331#endif // LLVM_IR_INTRINSICINST_H