1//===- CoroAnnotationElide.cpp - Elide attributed safe coroutine calls ----===//
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// \file
10// This pass transforms all Call or Invoke instructions that are annotated
11// "coro_elide_safe" to call the `.noalloc` variant of coroutine instead.
12// The frame of the callee coroutine is allocated inside the caller. A pointer
13// to the allocated frame will be passed into the `.noalloc` ramp function.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Coroutines/CoroAnnotationElide.h"
18
19#include "llvm/Analysis/CGSCCPassManager.h"
20#include "llvm/Analysis/LazyCallGraph.h"
21#include "llvm/Analysis/OptimizationRemarkEmitter.h"
22#include "llvm/IR/Analysis.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/Instruction.h"
25#include "llvm/IR/Module.h"
26#include "llvm/IR/PassManager.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Transforms/Utils/CallGraphUpdater.h"
29#include "llvm/Transforms/Utils/Cloning.h"
30
31#include <cassert>
32
33using namespace llvm;
34
35#define DEBUG_TYPE "coro-annotation-elide"
36
37static cl::opt<float> CoroElideBranchRatio(
38 "coro-elide-branch-ratio", cl::init(Val: 0.55), cl::Hidden,
39 cl::desc("Minimum BranchProbability to consider a elide a coroutine."));
40
41static Instruction *getFirstNonAllocaInTheEntryBlock(Function *F) {
42 for (Instruction &I : F->getEntryBlock())
43 if (!isa<AllocaInst>(Val: &I))
44 return &I;
45 llvm_unreachable("no terminator in the entry block");
46}
47
48// Create an alloca in the caller, using FrameSize and FrameAlign as the callee
49// coroutine's activation frame.
50static Value *allocateFrameInCaller(Function *Caller, uint64_t FrameSize,
51 Align FrameAlign) {
52 LLVMContext &C = Caller->getContext();
53 BasicBlock::iterator InsertPt =
54 getFirstNonAllocaInTheEntryBlock(F: Caller)->getIterator();
55 const DataLayout &DL = Caller->getDataLayout();
56 auto FrameTy = ArrayType::get(ElementType: Type::getInt8Ty(C), NumElements: FrameSize);
57 auto *Frame = new AllocaInst(FrameTy, DL.getAllocaAddrSpace(), "", InsertPt);
58 Frame->setAlignment(FrameAlign);
59 return Frame;
60}
61
62// Given a call or invoke instruction to the elide safe coroutine, this function
63// does the following:
64// - Allocate a frame for the callee coroutine in the caller using alloca.
65// - Replace the old CB with a new Call or Invoke to `NewCallee`, with the
66// pointer to the frame as an additional argument to NewCallee.
67static void processCall(CallBase *CB, Function *Caller, Function *NewCallee,
68 uint64_t FrameSize, Align FrameAlign) {
69 // TODO: generate the lifetime intrinsics for the new frame. This will require
70 // introduction of two pesudo lifetime intrinsics in the frontend around the
71 // `co_await` expression and convert them to real lifetime intrinsics here.
72 auto *FramePtr = allocateFrameInCaller(Caller, FrameSize, FrameAlign);
73 auto NewCBInsertPt = CB->getIterator();
74 llvm::CallBase *NewCB = nullptr;
75 SmallVector<Value *, 4> NewArgs;
76 NewArgs.append(in_start: CB->arg_begin(), in_end: CB->arg_end());
77 NewArgs.push_back(Elt: FramePtr);
78
79 if (auto *CI = dyn_cast<CallInst>(Val: CB)) {
80 auto *NewCI = CallInst::Create(Ty: NewCallee->getFunctionType(), Func: NewCallee,
81 Args: NewArgs, NameStr: "", InsertBefore: NewCBInsertPt);
82 NewCI->setTailCallKind(CI->getTailCallKind());
83 NewCB = NewCI;
84 } else if (auto *II = dyn_cast<InvokeInst>(Val: CB)) {
85 NewCB = InvokeInst::Create(Ty: NewCallee->getFunctionType(), Func: NewCallee,
86 IfNormal: II->getNormalDest(), IfException: II->getUnwindDest(),
87 Args: NewArgs, Bundles: {}, NameStr: "", InsertBefore: NewCBInsertPt);
88 } else {
89 llvm_unreachable("CallBase should either be Call or Invoke!");
90 }
91
92 NewCB->setCalledFunction(FTy: NewCallee->getFunctionType(), Fn: NewCallee);
93 NewCB->setCallingConv(CB->getCallingConv());
94 NewCB->setAttributes(CB->getAttributes());
95 NewCB->setDebugLoc(CB->getDebugLoc());
96 std::copy(first: CB->bundle_op_info_begin(), last: CB->bundle_op_info_end(),
97 result: NewCB->bundle_op_info_begin());
98
99 NewCB->removeFnAttr(Kind: llvm::Attribute::CoroElideSafe);
100 CB->replaceAllUsesWith(V: NewCB);
101
102 InlineFunctionInfo IFI;
103 InlineResult IR = InlineFunction(CB&: *NewCB, IFI);
104 if (IR.isSuccess()) {
105 CB->eraseFromParent();
106 } else {
107 NewCB->replaceAllUsesWith(V: CB);
108 NewCB->eraseFromParent();
109 }
110}
111
112PreservedAnalyses CoroAnnotationElidePass::run(LazyCallGraph::SCC &C,
113 CGSCCAnalysisManager &AM,
114 LazyCallGraph &CG,
115 CGSCCUpdateResult &UR) {
116 bool Changed = false;
117 CallGraphUpdater CGUpdater;
118 CGUpdater.initialize(LCG&: CG, SCC&: C, AM, UR);
119
120 auto &FAM =
121 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
122
123 for (LazyCallGraph::Node &N : C) {
124 Function *Callee = &N.getFunction();
125 Function *NewCallee = Callee->getParent()->getFunction(
126 Name: (Callee->getName() + ".noalloc").str());
127 if (!NewCallee)
128 continue;
129
130 SmallVector<CallBase *, 4> Users;
131 for (auto *U : Callee->users()) {
132 if (auto *CB = dyn_cast<CallBase>(Val: U)) {
133 if (CB->getCalledFunction() == Callee)
134 Users.push_back(Elt: CB);
135 }
136 }
137 auto FramePtrArgPosition = NewCallee->arg_size() - 1;
138 auto FrameSize =
139 NewCallee->getParamDereferenceableBytes(ArgNo: FramePtrArgPosition);
140 auto FrameAlign =
141 NewCallee->getParamAlign(ArgNo: FramePtrArgPosition).valueOrOne();
142
143 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *Callee);
144
145 for (auto *CB : Users) {
146 auto *Caller = CB->getFunction();
147 if (!Caller)
148 continue;
149
150 bool IsCallerPresplitCoroutine = Caller->isPresplitCoroutine();
151 bool HasAttr = CB->hasFnAttr(Kind: llvm::Attribute::CoroElideSafe);
152 if (IsCallerPresplitCoroutine && HasAttr) {
153 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: *Caller);
154
155 auto BlockFreq = BFI.getBlockFreq(BB: CB->getParent()).getFrequency();
156 auto EntryFreq = BFI.getEntryFreq().getFrequency();
157 uint64_t MinFreq =
158 static_cast<uint64_t>(EntryFreq * CoroElideBranchRatio);
159
160 if (BlockFreq < MinFreq) {
161 ORE.emit(RemarkBuilder: [&]() {
162 return OptimizationRemarkMissed(
163 DEBUG_TYPE, "CoroAnnotationElideUnlikely", Caller)
164 << "'" << ore::NV("callee", Callee->getName())
165 << "' not elided in '"
166 << ore::NV("caller", Caller->getName())
167 << "' because of low frequency: "
168 << ore::NV("block_freq", BlockFreq)
169 << " (threshold: " << ore::NV("min_freq", MinFreq) << ")";
170 });
171 continue;
172 }
173
174 auto *CallerN = CG.lookup(F: *Caller);
175 auto *CallerC = CallerN ? CG.lookupSCC(N&: *CallerN) : nullptr;
176 // If CallerC is nullptr, it means LazyCallGraph hasn't visited Caller
177 // yet. Skip the call graph update.
178 auto ShouldUpdateCallGraph = !!CallerC;
179 processCall(CB, Caller, NewCallee, FrameSize, FrameAlign);
180
181 ORE.emit(RemarkBuilder: [&]() {
182 return OptimizationRemark(DEBUG_TYPE, "CoroAnnotationElide", Caller)
183 << "'" << ore::NV("callee", Callee->getName())
184 << "' elided in '" << ore::NV("caller", Caller->getName())
185 << "' (block_freq: " << ore::NV("block_freq", BlockFreq)
186 << ")";
187 });
188
189 FAM.invalidate(IR&: *Caller, PA: PreservedAnalyses::none());
190 Changed = true;
191 if (ShouldUpdateCallGraph)
192 updateCGAndAnalysisManagerForCGSCCPass(G&: CG, C&: *CallerC, N&: *CallerN, AM, UR,
193 FAM);
194
195 } else {
196 ORE.emit(RemarkBuilder: [&]() {
197 return OptimizationRemarkMissed(DEBUG_TYPE, "CoroAnnotationElide",
198 Caller)
199 << "'" << ore::NV("callee", Callee->getName())
200 << "' not elided in '" << ore::NV("caller", Caller->getName())
201 << "' (caller_presplit="
202 << ore::NV("caller_presplit", IsCallerPresplitCoroutine)
203 << ", elide_safe_attr=" << ore::NV("elide_safe_attr", HasAttr)
204 << ")";
205 });
206 }
207 }
208 }
209
210 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
211}
212