LLVM  14.0.0git
CoroElide.cpp
Go to the documentation of this file.
1 //===- CoroElide.cpp - Coroutine Frame Allocation Elision Pass ------------===//
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 
10 #include "CoroInternal.h"
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/Statistic.h"
15 #include "llvm/IR/Dominators.h"
16 #include "llvm/IR/InstIterator.h"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Pass.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "coro-elide"
25 
26 STATISTIC(NumOfCoroElided, "The # of coroutine get elided.");
27 
28 #ifndef NDEBUG
30  "coro-elide-info-output-file", cl::value_desc("filename"),
31  cl::desc("File to record the coroutines got elided"), cl::Hidden);
32 #endif
33 
34 namespace {
35 // Created on demand if the coro-elide pass has work to do.
36 struct Lowerer : coro::LowererBase {
42  SmallPtrSet<const SwitchInst *, 4> CoroSuspendSwitches;
43 
44  Lowerer(Module &M) : LowererBase(M) {}
45 
46  void elideHeapAllocations(Function *F, uint64_t FrameSize, Align FrameAlign,
47  AAResults &AA);
48  bool shouldElide(Function *F, DominatorTree &DT) const;
49  void collectPostSplitCoroIds(Function *F);
50  bool processCoroId(CoroIdInst *, AAResults &AA, DominatorTree &DT);
51  bool hasEscapePath(const CoroBeginInst *,
52  const SmallPtrSetImpl<BasicBlock *> &) const;
53 };
54 } // end anonymous namespace
55 
56 // Go through the list of coro.subfn.addr intrinsics and replace them with the
57 // provided constant.
60  if (Users.empty())
61  return;
62 
63  // See if we need to bitcast the constant to match the type of the intrinsic
64  // being replaced. Note: All coro.subfn.addr intrinsics return the same type,
65  // so we only need to examine the type of the first one in the list.
66  Type *IntrTy = Users.front()->getType();
67  Type *ValueTy = Value->getType();
68  if (ValueTy != IntrTy) {
69  // May need to tweak the function type to match the type expected at the
70  // use site.
71  assert(ValueTy->isPointerTy() && IntrTy->isPointerTy());
73  }
74 
75  // Now the value type matches the type of the intrinsic. Replace them all!
76  for (CoroSubFnInst *I : Users)
78 }
79 
80 // See if any operand of the call instruction references the coroutine frame.
81 static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA) {
82  for (Value *Op : CI->operand_values())
83  if (!AA.isNoAlias(Op, Frame))
84  return true;
85  return false;
86 }
87 
88 // Look for any tail calls referencing the coroutine frame and remove tail
89 // attribute from them, since now coroutine frame resides on the stack and tail
90 // call implies that the function does not references anything on the stack.
91 // However if it's a musttail call, we cannot remove the tailcall attribute.
92 // It's safe to keep it there as the musttail call is for symmetric transfer,
93 // and by that point the frame should have been destroyed and hence not
94 // interfering with operands.
95 static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA) {
96  Function &F = *Frame->getFunction();
97  for (Instruction &I : instructions(F))
98  if (auto *Call = dyn_cast<CallInst>(&I))
99  if (Call->isTailCall() && operandReferences(Call, Frame, AA) &&
100  !Call->isMustTailCall())
101  Call->setTailCall(false);
102 }
103 
104 // Given a resume function @f.resume(%f.frame* %frame), returns the size
105 // and expected alignment of %f.frame type.
106 static std::pair<uint64_t, Align> getFrameLayout(Function *Resume) {
107  // Prefer to pull information from the function attributes.
108  auto Size = Resume->getParamDereferenceableBytes(0);
109  auto Align = Resume->getParamAlign(0);
110 
111  // If those aren't given, extract them from the type.
112  if (Size == 0 || !Align) {
113  auto *FrameTy = Resume->arg_begin()->getType()->getPointerElementType();
114 
115  const DataLayout &DL = Resume->getParent()->getDataLayout();
116  if (!Size) Size = DL.getTypeAllocSize(FrameTy);
117  if (!Align) Align = DL.getABITypeAlign(FrameTy);
118  }
119 
120  return std::make_pair(Size, *Align);
121 }
122 
123 // Finds first non alloca instruction in the entry block of a function.
125  for (Instruction &I : F->getEntryBlock())
126  if (!isa<AllocaInst>(&I))
127  return &I;
128  llvm_unreachable("no terminator in the entry block");
129 }
130 
131 #ifndef NDEBUG
132 static std::unique_ptr<raw_fd_ostream> getOrCreateLogFile() {
134  "coro-elide-info-output-file shouldn't be empty");
135  std::error_code EC;
136  auto Result = std::make_unique<raw_fd_ostream>(CoroElideInfoOutputFilename,
137  EC, sys::fs::OF_Append);
138  if (!EC)
139  return Result;
140  llvm::errs() << "Error opening coro-elide-info-output-file '"
141  << CoroElideInfoOutputFilename << " for appending!\n";
142  return std::make_unique<raw_fd_ostream>(2, false); // stderr.
143 }
144 #endif
145 
146 // To elide heap allocations we need to suppress code blocks guarded by
147 // llvm.coro.alloc and llvm.coro.free instructions.
148 void Lowerer::elideHeapAllocations(Function *F, uint64_t FrameSize,
149  Align FrameAlign, AAResults &AA) {
150  LLVMContext &C = F->getContext();
151  auto *InsertPt =
152  getFirstNonAllocaInTheEntryBlock(CoroIds.front()->getFunction());
153 
154  // Replacing llvm.coro.alloc with false will suppress dynamic
155  // allocation as it is expected for the frontend to generate the code that
156  // looks like:
157  // id = coro.id(...)
158  // mem = coro.alloc(id) ? malloc(coro.size()) : 0;
159  // coro.begin(id, mem)
160  auto *False = ConstantInt::getFalse(C);
161  for (auto *CA : CoroAllocs) {
162  CA->replaceAllUsesWith(False);
163  CA->eraseFromParent();
164  }
165 
166  // FIXME: Design how to transmit alignment information for every alloca that
167  // is spilled into the coroutine frame and recreate the alignment information
168  // here. Possibly we will need to do a mini SROA here and break the coroutine
169  // frame into individual AllocaInst recreating the original alignment.
170  const DataLayout &DL = F->getParent()->getDataLayout();
171  auto FrameTy = ArrayType::get(Type::getInt8Ty(C), FrameSize);
172  auto *Frame = new AllocaInst(FrameTy, DL.getAllocaAddrSpace(), "", InsertPt);
173  Frame->setAlignment(FrameAlign);
174  auto *FrameVoidPtr =
175  new BitCastInst(Frame, Type::getInt8PtrTy(C), "vFrame", InsertPt);
176 
177  for (auto *CB : CoroBegins) {
178  CB->replaceAllUsesWith(FrameVoidPtr);
179  CB->eraseFromParent();
180  }
181 
182  // Since now coroutine frame lives on the stack we need to make sure that
183  // any tail call referencing it, must be made non-tail call.
184  removeTailCallAttribute(Frame, AA);
185 }
186 
187 bool Lowerer::hasEscapePath(const CoroBeginInst *CB,
188  const SmallPtrSetImpl<BasicBlock *> &TIs) const {
189  const auto &It = DestroyAddr.find(CB);
190  assert(It != DestroyAddr.end());
191 
192  // Limit the number of blocks we visit.
193  unsigned Limit = 32 * (1 + It->second.size());
194 
196  Worklist.push_back(CB->getParent());
197 
199  // Consider basicblock of coro.destroy as visited one, so that we
200  // skip the path pass through coro.destroy.
201  for (auto *DA : It->second)
202  Visited.insert(DA->getParent());
203 
204  do {
205  const auto *BB = Worklist.pop_back_val();
206  if (!Visited.insert(BB).second)
207  continue;
208  if (TIs.count(BB))
209  return true;
210 
211  // Conservatively say that there is potentially a path.
212  if (!--Limit)
213  return true;
214 
215  auto TI = BB->getTerminator();
216  // Although the default dest of coro.suspend switches is suspend pointer
217  // which means a escape path to normal terminator, it is reasonable to skip
218  // it since coroutine frame doesn't change outside the coroutine body.
219  if (isa<SwitchInst>(TI) &&
220  CoroSuspendSwitches.count(cast<SwitchInst>(TI))) {
221  Worklist.push_back(cast<SwitchInst>(TI)->getSuccessor(1));
222  Worklist.push_back(cast<SwitchInst>(TI)->getSuccessor(2));
223  } else
224  Worklist.append(succ_begin(BB), succ_end(BB));
225 
226  } while (!Worklist.empty());
227 
228  // We have exhausted all possible paths and are certain that coro.begin can
229  // not reach to any of terminators.
230  return false;
231 }
232 
233 bool Lowerer::shouldElide(Function *F, DominatorTree &DT) const {
234  // If no CoroAllocs, we cannot suppress allocation, so elision is not
235  // possible.
236  if (CoroAllocs.empty())
237  return false;
238 
239  // Check that for every coro.begin there is at least one coro.destroy directly
240  // referencing the SSA value of that coro.begin along each
241  // non-exceptional path.
242  // If the value escaped, then coro.destroy would have been referencing a
243  // memory location storing that value and not the virtual register.
244 
245  SmallPtrSet<BasicBlock *, 8> Terminators;
246  // First gather all of the non-exceptional terminators for the function.
247  // Consider the final coro.suspend as the real terminator when the current
248  // function is a coroutine.
249  for (BasicBlock &B : *F) {
250  auto *TI = B.getTerminator();
251  if (TI->getNumSuccessors() == 0 && !TI->isExceptionalTerminator() &&
252  !isa<UnreachableInst>(TI))
253  Terminators.insert(&B);
254  }
255 
256  // Filter out the coro.destroy that lie along exceptional paths.
257  SmallPtrSet<CoroBeginInst *, 8> ReferencedCoroBegins;
258  for (auto &It : DestroyAddr) {
259  // If there is any coro.destroy dominates all of the terminators for the
260  // coro.begin, we could know the corresponding coro.begin wouldn't escape.
261  for (Instruction *DA : It.second) {
262  if (llvm::all_of(Terminators, [&](auto *TI) {
263  return DT.dominates(DA, TI->getTerminator());
264  })) {
265  ReferencedCoroBegins.insert(It.first);
266  break;
267  }
268  }
269 
270  // Whether there is any paths from coro.begin to Terminators which not pass
271  // through any of the coro.destroys.
272  //
273  // hasEscapePath is relatively slow, so we avoid to run it as much as
274  // possible.
275  if (!ReferencedCoroBegins.count(It.first) &&
276  !hasEscapePath(It.first, Terminators))
277  ReferencedCoroBegins.insert(It.first);
278  }
279 
280  // If size of the set is the same as total number of coro.begin, that means we
281  // found a coro.free or coro.destroy referencing each coro.begin, so we can
282  // perform heap elision.
283  return ReferencedCoroBegins.size() == CoroBegins.size();
284 }
285 
286 void Lowerer::collectPostSplitCoroIds(Function *F) {
287  CoroIds.clear();
288  CoroSuspendSwitches.clear();
289  for (auto &I : instructions(F)) {
290  if (auto *CII = dyn_cast<CoroIdInst>(&I))
291  if (CII->getInfo().isPostSplit())
292  // If it is the coroutine itself, don't touch it.
293  if (CII->getCoroutine() != CII->getFunction())
294  CoroIds.push_back(CII);
295 
296  // Consider case like:
297  // %0 = call i8 @llvm.coro.suspend(...)
298  // switch i8 %0, label %suspend [i8 0, label %resume
299  // i8 1, label %cleanup]
300  // and collect the SwitchInsts which are used by escape analysis later.
301  if (auto *CSI = dyn_cast<CoroSuspendInst>(&I))
302  if (CSI->hasOneUse() && isa<SwitchInst>(CSI->use_begin()->getUser())) {
303  SwitchInst *SWI = cast<SwitchInst>(CSI->use_begin()->getUser());
304  if (SWI->getNumCases() == 2)
305  CoroSuspendSwitches.insert(SWI);
306  }
307  }
308 }
309 
310 bool Lowerer::processCoroId(CoroIdInst *CoroId, AAResults &AA,
311  DominatorTree &DT) {
312  CoroBegins.clear();
313  CoroAllocs.clear();
314  ResumeAddr.clear();
315  DestroyAddr.clear();
316 
317  // Collect all coro.begin and coro.allocs associated with this coro.id.
318  for (User *U : CoroId->users()) {
319  if (auto *CB = dyn_cast<CoroBeginInst>(U))
320  CoroBegins.push_back(CB);
321  else if (auto *CA = dyn_cast<CoroAllocInst>(U))
322  CoroAllocs.push_back(CA);
323  }
324 
325  // Collect all coro.subfn.addrs associated with coro.begin.
326  // Note, we only devirtualize the calls if their coro.subfn.addr refers to
327  // coro.begin directly. If we run into cases where this check is too
328  // conservative, we can consider relaxing the check.
329  for (CoroBeginInst *CB : CoroBegins) {
330  for (User *U : CB->users())
331  if (auto *II = dyn_cast<CoroSubFnInst>(U))
332  switch (II->getIndex()) {
334  ResumeAddr.push_back(II);
335  break;
337  DestroyAddr[CB].push_back(II);
338  break;
339  default:
340  llvm_unreachable("unexpected coro.subfn.addr constant");
341  }
342  }
343 
344  // PostSplit coro.id refers to an array of subfunctions in its Info
345  // argument.
346  ConstantArray *Resumers = CoroId->getInfo().Resumers;
347  assert(Resumers && "PostSplit coro.id Info argument must refer to an array"
348  "of coroutine subfunctions");
349  auto *ResumeAddrConstant =
351 
352  replaceWithConstant(ResumeAddrConstant, ResumeAddr);
353 
354  bool ShouldElide = shouldElide(CoroId->getFunction(), DT);
355 
356  auto *DestroyAddrConstant = ConstantExpr::getExtractValue(
357  Resumers,
359 
360  for (auto &It : DestroyAddr)
361  replaceWithConstant(DestroyAddrConstant, It.second);
362 
363  if (ShouldElide) {
364  auto FrameSizeAndAlign = getFrameLayout(cast<Function>(ResumeAddrConstant));
365  elideHeapAllocations(CoroId->getFunction(), FrameSizeAndAlign.first,
366  FrameSizeAndAlign.second, AA);
367  coro::replaceCoroFree(CoroId, /*Elide=*/true);
368  NumOfCoroElided++;
369 #ifndef NDEBUG
370  if (!CoroElideInfoOutputFilename.empty())
372  << "Elide " << CoroId->getCoroutine()->getName() << " in "
373  << CoroId->getFunction()->getName() << "\n";
374 #endif
375  }
376 
377  return true;
378 }
379 
380 // See if there are any coro.subfn.addr instructions referring to coro.devirt
381 // trigger, if so, replace them with a direct call to devirt trigger function.
384  for (auto &I : instructions(F))
385  if (auto *SubFn = dyn_cast<CoroSubFnInst>(&I))
386  if (SubFn->getIndex() == CoroSubFnInst::RestartTrigger)
387  DevirtAddr.push_back(SubFn);
388 
389  if (DevirtAddr.empty())
390  return false;
391 
392  Module &M = *F.getParent();
393  Function *DevirtFn = M.getFunction(CORO_DEVIRT_TRIGGER_FN);
394  assert(DevirtFn && "coro.devirt.fn not found");
395  replaceWithConstant(DevirtFn, DevirtAddr);
396 
397  return true;
398 }
399 
401  return coro::declaresIntrinsics(M, {"llvm.coro.id", "llvm.coro.id.async"});
402 }
403 
405  auto &M = *F.getParent();
407  return PreservedAnalyses::all();
408 
409  Lowerer L(M);
410  L.CoroIds.clear();
411  L.collectPostSplitCoroIds(&F);
412  // If we did not find any coro.id, there is nothing to do.
413  if (L.CoroIds.empty())
414  return PreservedAnalyses::all();
415 
416  AAResults &AA = AM.getResult<AAManager>(F);
418 
419  bool Changed = false;
420  for (auto *CII : L.CoroIds)
421  Changed |= L.processCoroId(CII, AA, DT);
422 
423  return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
424 }
425 
426 namespace {
427 struct CoroElideLegacy : FunctionPass {
428  static char ID;
429  CoroElideLegacy() : FunctionPass(ID) {
431  }
432 
433  std::unique_ptr<Lowerer> L;
434 
435  bool doInitialization(Module &M) override {
437  L = std::make_unique<Lowerer>(M);
438  return false;
439  }
440 
441  bool runOnFunction(Function &F) override {
442  if (!L)
443  return false;
444 
445  bool Changed = false;
446 
447  if (F.hasFnAttribute(CORO_PRESPLIT_ATTR))
448  Changed = replaceDevirtTrigger(F);
449 
450  L->CoroIds.clear();
451  L->collectPostSplitCoroIds(&F);
452  // If we did not find any coro.id, there is nothing to do.
453  if (L->CoroIds.empty())
454  return Changed;
455 
456  AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
457  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
458 
459  for (auto *CII : L->CoroIds)
460  Changed |= L->processCoroId(CII, AA, DT);
461 
462  return Changed;
463  }
464  void getAnalysisUsage(AnalysisUsage &AU) const override {
467  }
468  StringRef getPassName() const override { return "Coroutine Elision"; }
469 };
470 }
471 
472 char CoroElideLegacy::ID = 0;
474  CoroElideLegacy, "coro-elide",
475  "Coroutine frame allocation elision and indirect calls replacement", false,
476  false)
479  CoroElideLegacy, "coro-elide",
480  "Coroutine frame allocation elision and indirect calls replacement", false,
481  false)
482 
483 Pass *llvm::createCoroElideLegacyPass() { return new CoroElideLegacy(); }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::CoroSubFnInst::ResumeIndex
@ ResumeIndex
Definition: CoroInstr.h:41
llvm::CoroIdInst::getInfo
Info getInfo() const
Definition: CoroInstr.h:162
llvm::createCoroElideLegacyPass
Pass * createCoroElideLegacyPass()
Analyze coroutines use sites, devirtualize resume/destroy calls and elide heap allocation for corouti...
Definition: CoroElide.cpp:483
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
FileSystem.h
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:255
elide
coro elide
Definition: CoroElide.cpp:479
replaceDevirtTrigger
static bool replaceDevirtTrigger(Function &F)
Definition: CoroElide.cpp:382
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:228
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::CoroSubFnInst::DestroyIndex
@ DestroyIndex
Definition: CoroInstr.h:42
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
InstIterator.h
llvm::Function
Definition: Function.h:61
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(CoroElideLegacy, "coro-elide", "Coroutine frame allocation elision and indirect calls replacement", false, false) INITIALIZE_PASS_END(CoroElideLegacy
Pass.h
llvm::Function::getParamDereferenceableBytes
uint64_t getParamDereferenceableBytes(unsigned ArgNo) const
Extract the number of dereferenceable bytes for a parameter.
Definition: Function.h:488
llvm::CoroIdInst::getCoroutine
Function * getCoroutine() const
Definition: CoroInstr.h:182
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5200
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
ErrorHandling.h
llvm::AAResults::isNoAlias
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are no-alias.
Definition: AliasAnalysis.h:510
getOrCreateLogFile
static std::unique_ptr< raw_fd_ostream > getOrCreateLogFile()
Definition: CoroElide.cpp:132
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2208
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::CoroSubFnInst::CleanupIndex
@ CleanupIndex
Definition: CoroInstr.h:43
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::coro::declaresIntrinsics
bool declaresIntrinsics(const Module &M, const std::initializer_list< StringRef >)
Definition: Coroutines.cpp:161
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
and
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
Definition: README.txt:1271
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:201
CoroElide.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
operandReferences
static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:81
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1551
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
replaceWithConstant
static void replaceWithConstant(Constant *Value, SmallVectorImpl< CoroSubFnInst * > &Users)
Definition: CoroElide.cpp:58
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::CoroSubFnInst
This class represents the llvm.coro.subfn.addr instruction.
Definition: CoroInstr.h:35
llvm::coro::replaceCoroFree
void replaceCoroFree(CoroIdInst *CoroId, bool Elide)
Definition: Coroutines.cpp:174
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CoroInternal.h
llvm::cl::opt
Definition: CommandLine.h:1434
allocation
Eliminate PHI nodes for register allocation
Definition: PHIElimination.cpp:136
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
uint64_t
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
getFirstNonAllocaInTheEntryBlock
static Instruction * getFirstNonAllocaInTheEntryBlock(Function *F)
Definition: CoroElide.cpp:124
llvm::DenseMap
Definition: DenseMap.h:714
CORO_DEVIRT_TRIGGER_FN
#define CORO_DEVIRT_TRIGGER_FN
Definition: CoroInternal.h:44
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::CoroElidePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: CoroElide.cpp:404
llvm::replaceAndRecursivelySimplify
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
Definition: InstructionSimplify.cpp:6369
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SwitchInst::getNumCases
unsigned getNumCases() const
Return the number of 'cases' in this switch instruction, excluding the default case.
Definition: Instructions.h:3430
llvm::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:602
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::initializeCoroElideLegacyPass
void initializeCoroElideLegacyPass(PassRegistry &)
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CoroIdInst
This represents the llvm.coro.id instruction.
Definition: CoroInstr.h:113
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::Function::getParamAlign
MaybeAlign getParamAlign(unsigned ArgNo) const
Definition: Function.h:453
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
declaresCoroElideIntrinsics
static bool declaresCoroElideIntrinsics(Module &M)
Definition: CoroElide.cpp:400
llvm::CoroSubFnInst::RestartTrigger
@ RestartTrigger
Definition: CoroInstr.h:40
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
CORO_PRESPLIT_ATTR
#define CORO_PRESPLIT_ATTR
Definition: CoroInternal.h:39
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::CoroIdInst::Info::Resumers
ConstantArray * Resumers
Definition: CoroInstr.h:156
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
removeTailCallAttribute
static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA)
Definition: CoroElide.cpp:95
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::User::operand_values
iterator_range< value_op_iterator > operand_values()
Definition: User.h:266
llvm::cl::value_desc
Definition: CommandLine.h:424
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:748
replacement
coro Coroutine frame allocation elision and indirect calls replacement
Definition: CoroElide.cpp:480
getFrameLayout
static std::pair< uint64_t, Align > getFrameLayout(Function *Resume)
Definition: CoroElide.cpp:106
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
CoroElideInfoOutputFilename
static cl::opt< std::string > CoroElideInfoOutputFilename("coro-elide-info-output-file", cl::value_desc("filename"), cl::desc("File to record the coroutines got elided"), cl::Hidden)
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Dominators.h
llvm::Type::getPointerElementType
Type * getPointerElementType() const
Definition: Type.h:380
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1281
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::sys::fs::OF_Append
@ OF_Append
The file should be opened in append mode.
Definition: FileSystem.h:773
InstructionSimplify.h
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::coro::LowererBase
Definition: CoroInternal.h:60
llvm::CoroBeginInst
This class represents the llvm.coro.begin instruction.
Definition: CoroInstr.h:420
calls
amdgpu Simplify well known AMD library calls
Definition: AMDGPULibCalls.cpp:199
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::cl::desc
Definition: CommandLine.h:414
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::ConstantExpr::getExtractValue
static Constant * getExtractValue(Constant *Agg, ArrayRef< unsigned > Idxs, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2622
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37