1 //===- CallPromotionUtils.cpp - Utilities for call promotion ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements utilities useful for promoting indirect call sites to
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
16 #include "llvm/IR/IRBuilder.h"
17 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
21 #define DEBUG_TYPE "call-promotion-utils"
23 /// Fix-up phi nodes in an invoke instruction's normal destination.
25 /// After versioning an invoke instruction, values coming from the original
26 /// block will now either be coming from the original block or the "else" block.
27 static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
28 BasicBlock *ElseBlock,
29 Instruction *NewInst) {
30 for (auto &I : *Invoke->getNormalDest()) {
31 auto *Phi = dyn_cast<PHINode>(&I);
34 int Idx = Phi->getBasicBlockIndex(OrigBlock);
37 Value *V = Phi->getIncomingValue(Idx);
38 if (dyn_cast<Instruction>(V) == Invoke) {
39 Phi->setIncomingBlock(Idx, ElseBlock);
40 Phi->addIncoming(NewInst, OrigBlock);
43 Phi->addIncoming(V, ElseBlock);
47 /// Fix-up phi nodes in an invoke instruction's unwind destination.
49 /// After versioning an invoke instruction, values coming from the original
50 /// block will now be coming from either the "then" block or the "else" block.
51 static void fixupPHINodeForUnwindDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
52 BasicBlock *ThenBlock,
53 BasicBlock *ElseBlock) {
54 for (auto &I : *Invoke->getUnwindDest()) {
55 auto *Phi = dyn_cast<PHINode>(&I);
58 int Idx = Phi->getBasicBlockIndex(OrigBlock);
61 auto *V = Phi->getIncomingValue(Idx);
62 Phi->setIncomingBlock(Idx, ThenBlock);
63 Phi->addIncoming(V, ElseBlock);
67 /// Get the phi node having the returned value of a call or invoke instruction
69 static bool getRetPhiNode(Instruction *Inst, BasicBlock *Block) {
70 BasicBlock *FromBlock = Inst->getParent();
71 for (auto &I : *Block) {
72 PHINode *PHI = dyn_cast<PHINode>(&I);
75 int Idx = PHI->getBasicBlockIndex(FromBlock);
78 auto *V = PHI->getIncomingValue(Idx);
85 /// Create a phi node for the returned value of a call or invoke instruction.
87 /// After versioning a call or invoke instruction that returns a value, we have
88 /// to merge the value of the original and new instructions. We do this by
89 /// creating a phi node and replacing uses of the original instruction with this
91 static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst) {
93 if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
96 BasicBlock *RetValBB = NewInst->getParent();
97 if (auto *Invoke = dyn_cast<InvokeInst>(NewInst))
98 RetValBB = Invoke->getNormalDest();
99 BasicBlock *PhiBB = RetValBB->getSingleSuccessor();
101 if (getRetPhiNode(OrigInst, PhiBB))
104 IRBuilder<> Builder(&PhiBB->front());
105 PHINode *Phi = Builder.CreatePHI(OrigInst->getType(), 0);
106 SmallVector<User *, 16> UsersToUpdate;
107 for (User *U : OrigInst->users())
108 UsersToUpdate.push_back(U);
109 for (User *U : UsersToUpdate)
110 U->replaceUsesOfWith(OrigInst, Phi);
111 Phi->addIncoming(OrigInst, OrigInst->getParent());
112 Phi->addIncoming(NewInst, RetValBB);
115 /// Cast a call or invoke instruction to the given type.
117 /// When promoting a call site, the return type of the call site might not match
118 /// that of the callee. If this is the case, we have to cast the returned value
119 /// to the correct type. The location of the cast depends on if we have a call
120 /// or invoke instruction.
121 Instruction *createRetBitCast(CallSite CS, Type *RetTy) {
123 // Save the users of the calling instruction. These uses will be changed to
124 // use the bitcast after we create it.
125 SmallVector<User *, 16> UsersToUpdate;
126 for (User *U : CS.getInstruction()->users())
127 UsersToUpdate.push_back(U);
129 // Determine an appropriate location to create the bitcast for the return
130 // value. The location depends on if we have a call or invoke instruction.
131 Instruction *InsertBefore = nullptr;
132 if (auto *Invoke = dyn_cast<InvokeInst>(CS.getInstruction()))
133 InsertBefore = &*Invoke->getNormalDest()->getFirstInsertionPt();
135 InsertBefore = &*std::next(CS.getInstruction()->getIterator());
137 // Bitcast the return value to the correct type.
138 auto *Cast = CastInst::Create(Instruction::BitCast, CS.getInstruction(),
139 RetTy, "", InsertBefore);
141 // Replace all the original uses of the calling instruction with the bitcast.
142 for (User *U : UsersToUpdate)
143 U->replaceUsesOfWith(CS.getInstruction(), Cast);
148 /// Predicate and clone the given call site.
150 /// This function creates an if-then-else structure at the location of the call
151 /// site. The "if" condition compares the call site's called value to the given
152 /// callee. The original call site is moved into the "else" block, and a clone
153 /// of the call site is placed in the "then" block. The cloned instruction is
155 static Instruction *versionCallSite(CallSite CS, Value *Callee,
156 MDNode *BranchWeights,
157 BasicBlock *&ThenBlock,
158 BasicBlock *&ElseBlock,
159 BasicBlock *&MergeBlock) {
161 IRBuilder<> Builder(CS.getInstruction());
162 Instruction *OrigInst = CS.getInstruction();
164 // Create the compare. The called value and callee must have the same type to
167 Builder.CreateBitCast(CS.getCalledValue(), Builder.getInt8PtrTy());
168 auto *RHS = Builder.CreateBitCast(Callee, Builder.getInt8PtrTy());
169 auto *Cond = Builder.CreateICmpEQ(LHS, RHS);
171 // Create an if-then-else structure. The original instruction is moved into
172 // the "else" block, and a clone of the original instruction is placed in the
174 TerminatorInst *ThenTerm = nullptr;
175 TerminatorInst *ElseTerm = nullptr;
176 SplitBlockAndInsertIfThenElse(Cond, CS.getInstruction(), &ThenTerm, &ElseTerm,
178 ThenBlock = ThenTerm->getParent();
179 ElseBlock = ElseTerm->getParent();
180 MergeBlock = OrigInst->getParent();
182 ThenBlock->setName("if.true.direct_targ");
183 ElseBlock->setName("if.false.orig_indirect");
184 MergeBlock->setName("if.end.icp");
186 Instruction *NewInst = OrigInst->clone();
187 OrigInst->moveBefore(ElseTerm);
188 NewInst->insertBefore(ThenTerm);
190 // If the original call site is an invoke instruction, we have extra work to
191 // do since invoke instructions are terminating.
192 if (auto *OrigInvoke = dyn_cast<InvokeInst>(OrigInst)) {
193 auto *NewInvoke = cast<InvokeInst>(NewInst);
195 // Invoke instructions are terminating, so we don't need the terminator
196 // instructions that were just created.
197 ThenTerm->eraseFromParent();
198 ElseTerm->eraseFromParent();
200 // Branch from the "merge" block to the original normal destination.
201 Builder.SetInsertPoint(MergeBlock);
202 Builder.CreateBr(OrigInvoke->getNormalDest());
204 // Now set the normal destination of new the invoke instruction to be the
206 NewInvoke->setNormalDest(MergeBlock);
212 bool llvm::isLegalToPromote(CallSite CS, Function *Callee,
213 const char **FailureReason) {
214 assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
216 // Check the return type. The callee's return value type must be bitcast
217 // compatible with the call site's type.
218 Type *CallRetTy = CS.getInstruction()->getType();
219 Type *FuncRetTy = Callee->getReturnType();
220 if (CallRetTy != FuncRetTy)
221 if (!CastInst::isBitCastable(FuncRetTy, CallRetTy)) {
223 *FailureReason = "Return type mismatch";
227 // The number of formal arguments of the callee.
228 unsigned NumParams = Callee->getFunctionType()->getNumParams();
230 // Check the number of arguments. The callee and call site must agree on the
231 // number of arguments.
232 if (CS.arg_size() != NumParams && !Callee->isVarArg()) {
234 *FailureReason = "The number of arguments mismatch";
238 // Check the argument types. The callee's formal argument types must be
239 // bitcast compatible with the corresponding actual argument types of the call
241 for (unsigned I = 0; I < NumParams; ++I) {
242 Type *FormalTy = Callee->getFunctionType()->getFunctionParamType(I);
243 Type *ActualTy = CS.getArgument(I)->getType();
244 if (FormalTy == ActualTy)
246 if (!CastInst::isBitCastable(ActualTy, FormalTy)) {
248 *FailureReason = "Argument type mismatch";
256 static void promoteCall(CallSite CS, Function *Callee, Instruction *&Cast) {
257 assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
259 // Set the called function of the call site to be the given callee.
260 CS.setCalledFunction(Callee);
262 // Since the call site will no longer be direct, we must clear metadata that
263 // is only appropriate for indirect calls. This includes !prof and !callees
265 CS.getInstruction()->setMetadata(LLVMContext::MD_prof, nullptr);
266 CS.getInstruction()->setMetadata(LLVMContext::MD_callees, nullptr);
268 // If the function type of the call site matches that of the callee, no
269 // additional work is required.
270 if (CS.getFunctionType() == Callee->getFunctionType())
273 // Save the return types of the call site and callee.
274 Type *CallSiteRetTy = CS.getInstruction()->getType();
275 Type *CalleeRetTy = Callee->getReturnType();
277 // Change the function type of the call site the match that of the callee.
278 CS.mutateFunctionType(Callee->getFunctionType());
280 // Inspect the arguments of the call site. If an argument's type doesn't
281 // match the corresponding formal argument's type in the callee, bitcast it
282 // to the correct type.
283 for (Use &U : CS.args()) {
284 unsigned ArgNo = CS.getArgumentNo(&U);
285 Type *FormalTy = Callee->getFunctionType()->getParamType(ArgNo);
286 Type *ActualTy = U.get()->getType();
287 if (FormalTy != ActualTy) {
288 auto *Cast = CastInst::Create(Instruction::BitCast, U.get(), FormalTy, "",
289 CS.getInstruction());
290 CS.setArgument(ArgNo, Cast);
294 // If the return type of the call site doesn't match that of the callee, cast
295 // the returned value to the appropriate type.
296 if (!CallSiteRetTy->isVoidTy() && CallSiteRetTy != CalleeRetTy)
297 Cast = createRetBitCast(CS, CallSiteRetTy);
300 Instruction *llvm::promoteCallWithIfThenElse(CallSite CS, Function *Callee,
301 MDNode *BranchWeights) {
303 // Version the indirect call site. If the called value is equal to the given
304 // callee, 'NewInst' will be executed, otherwise the original call site will
306 BasicBlock *ThenBlock, *ElseBlock, *MergeBlock;
307 Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights, ThenBlock,
308 ElseBlock, MergeBlock);
310 // Promote 'NewInst' so that it directly calls the desired function.
311 Instruction *Cast = NewInst;
312 promoteCall(CallSite(NewInst), Callee, Cast);
314 // If the original call site is an invoke instruction, we have to fix-up phi
315 // nodes in the invoke's normal and unwind destinations.
316 if (auto *OrigInvoke = dyn_cast<InvokeInst>(CS.getInstruction())) {
317 fixupPHINodeForNormalDest(OrigInvoke, MergeBlock, ElseBlock, Cast);
318 fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
321 // Create a phi node for the returned value of the call site.
322 createRetPHINode(CS.getInstruction(), Cast ? Cast : NewInst);
324 // Return the new direct call.