Bug Summary

File:lib/Transforms/Coroutines/CoroFrame.cpp
Warning:line 419, column 50
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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