xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Utils/CallPromotionUtils.cpp (revision e1e636193db45630c7881246d25902e57c43d24e)
1 //===- CallPromotionUtils.cpp - Utilities for call promotion ----*- 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 implements utilities useful for promoting indirect call sites to
10 // direct call sites.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
15 #include "llvm/Analysis/Loads.h"
16 #include "llvm/Analysis/TypeMetadataUtils.h"
17 #include "llvm/IR/AttributeMask.h"
18 #include "llvm/IR/IRBuilder.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "call-promotion-utils"
25 
26 /// Fix-up phi nodes in an invoke instruction's normal destination.
27 ///
28 /// After versioning an invoke instruction, values coming from the original
29 /// block will now be coming from the "merge" block. For example, in the code
30 /// below:
31 ///
32 ///   then_bb:
33 ///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
34 ///
35 ///   else_bb:
36 ///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
37 ///
38 ///   merge_bb:
39 ///     %t2 = phi i32 [ %t0, %then_bb ], [ %t1, %else_bb ]
40 ///     br %normal_dst
41 ///
42 ///   normal_dst:
43 ///     %t3 = phi i32 [ %x, %orig_bb ], ...
44 ///
45 /// "orig_bb" is no longer a predecessor of "normal_dst", so the phi nodes in
46 /// "normal_dst" must be fixed to refer to "merge_bb":
47 ///
48 ///    normal_dst:
49 ///      %t3 = phi i32 [ %x, %merge_bb ], ...
50 ///
51 static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
52                                       BasicBlock *MergeBlock) {
53   for (PHINode &Phi : Invoke->getNormalDest()->phis()) {
54     int Idx = Phi.getBasicBlockIndex(OrigBlock);
55     if (Idx == -1)
56       continue;
57     Phi.setIncomingBlock(Idx, MergeBlock);
58   }
59 }
60 
61 /// Fix-up phi nodes in an invoke instruction's unwind destination.
62 ///
63 /// After versioning an invoke instruction, values coming from the original
64 /// block will now be coming from either the "then" block or the "else" block.
65 /// For example, in the code below:
66 ///
67 ///   then_bb:
68 ///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
69 ///
70 ///   else_bb:
71 ///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
72 ///
73 ///   unwind_dst:
74 ///     %t3 = phi i32 [ %x, %orig_bb ], ...
75 ///
76 /// "orig_bb" is no longer a predecessor of "unwind_dst", so the phi nodes in
77 /// "unwind_dst" must be fixed to refer to "then_bb" and "else_bb":
78 ///
79 ///   unwind_dst:
80 ///     %t3 = phi i32 [ %x, %then_bb ], [ %x, %else_bb ], ...
81 ///
82 static void fixupPHINodeForUnwindDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
83                                       BasicBlock *ThenBlock,
84                                       BasicBlock *ElseBlock) {
85   for (PHINode &Phi : Invoke->getUnwindDest()->phis()) {
86     int Idx = Phi.getBasicBlockIndex(OrigBlock);
87     if (Idx == -1)
88       continue;
89     auto *V = Phi.getIncomingValue(Idx);
90     Phi.setIncomingBlock(Idx, ThenBlock);
91     Phi.addIncoming(V, ElseBlock);
92   }
93 }
94 
95 /// Create a phi node for the returned value of a call or invoke instruction.
96 ///
97 /// After versioning a call or invoke instruction that returns a value, we have
98 /// to merge the value of the original and new instructions. We do this by
99 /// creating a phi node and replacing uses of the original instruction with this
100 /// phi node.
101 ///
102 /// For example, if \p OrigInst is defined in "else_bb" and \p NewInst is
103 /// defined in "then_bb", we create the following phi node:
104 ///
105 ///   ; Uses of the original instruction are replaced by uses of the phi node.
106 ///   %t0 = phi i32 [ %orig_inst, %else_bb ], [ %new_inst, %then_bb ],
107 ///
108 static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst,
109                              BasicBlock *MergeBlock, IRBuilder<> &Builder) {
110 
111   if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
112     return;
113 
114   Builder.SetInsertPoint(MergeBlock, MergeBlock->begin());
115   PHINode *Phi = Builder.CreatePHI(OrigInst->getType(), 0);
116   SmallVector<User *, 16> UsersToUpdate(OrigInst->users());
117   for (User *U : UsersToUpdate)
118     U->replaceUsesOfWith(OrigInst, Phi);
119   Phi->addIncoming(OrigInst, OrigInst->getParent());
120   Phi->addIncoming(NewInst, NewInst->getParent());
121 }
122 
123 /// Cast a call or invoke instruction to the given type.
124 ///
125 /// When promoting a call site, the return type of the call site might not match
126 /// that of the callee. If this is the case, we have to cast the returned value
127 /// to the correct type. The location of the cast depends on if we have a call
128 /// or invoke instruction.
129 ///
130 /// For example, if the call instruction below requires a bitcast after
131 /// promotion:
132 ///
133 ///   orig_bb:
134 ///     %t0 = call i32 @func()
135 ///     ...
136 ///
137 /// The bitcast is placed after the call instruction:
138 ///
139 ///   orig_bb:
140 ///     ; Uses of the original return value are replaced by uses of the bitcast.
141 ///     %t0 = call i32 @func()
142 ///     %t1 = bitcast i32 %t0 to ...
143 ///     ...
144 ///
145 /// A similar transformation is performed for invoke instructions. However,
146 /// since invokes are terminating, a new block is created for the bitcast. For
147 /// example, if the invoke instruction below requires a bitcast after promotion:
148 ///
149 ///   orig_bb:
150 ///     %t0 = invoke i32 @func() to label %normal_dst unwind label %unwind_dst
151 ///
152 /// The edge between the original block and the invoke's normal destination is
153 /// split, and the bitcast is placed there:
154 ///
155 ///   orig_bb:
156 ///     %t0 = invoke i32 @func() to label %split_bb unwind label %unwind_dst
157 ///
158 ///   split_bb:
159 ///     ; Uses of the original return value are replaced by uses of the bitcast.
160 ///     %t1 = bitcast i32 %t0 to ...
161 ///     br label %normal_dst
162 ///
163 static void createRetBitCast(CallBase &CB, Type *RetTy, CastInst **RetBitCast) {
164 
165   // Save the users of the calling instruction. These uses will be changed to
166   // use the bitcast after we create it.
167   SmallVector<User *, 16> UsersToUpdate(CB.users());
168 
169   // Determine an appropriate location to create the bitcast for the return
170   // value. The location depends on if we have a call or invoke instruction.
171   Instruction *InsertBefore = nullptr;
172   if (auto *Invoke = dyn_cast<InvokeInst>(&CB))
173     InsertBefore =
174         &SplitEdge(Invoke->getParent(), Invoke->getNormalDest())->front();
175   else
176     InsertBefore = &*std::next(CB.getIterator());
177 
178   // Bitcast the return value to the correct type.
179   auto *Cast = CastInst::CreateBitOrPointerCast(&CB, RetTy, "", InsertBefore);
180   if (RetBitCast)
181     *RetBitCast = Cast;
182 
183   // Replace all the original uses of the calling instruction with the bitcast.
184   for (User *U : UsersToUpdate)
185     U->replaceUsesOfWith(&CB, Cast);
186 }
187 
188 /// Predicate and clone the given call site.
189 ///
190 /// This function creates an if-then-else structure at the location of the call
191 /// site. The "if" condition compares the call site's called value to the given
192 /// callee. The original call site is moved into the "else" block, and a clone
193 /// of the call site is placed in the "then" block. The cloned instruction is
194 /// returned.
195 ///
196 /// For example, the call instruction below:
197 ///
198 ///   orig_bb:
199 ///     %t0 = call i32 %ptr()
200 ///     ...
201 ///
202 /// Is replace by the following:
203 ///
204 ///   orig_bb:
205 ///     %cond = icmp eq i32 ()* %ptr, @func
206 ///     br i1 %cond, %then_bb, %else_bb
207 ///
208 ///   then_bb:
209 ///     ; The clone of the original call instruction is placed in the "then"
210 ///     ; block. It is not yet promoted.
211 ///     %t1 = call i32 %ptr()
212 ///     br merge_bb
213 ///
214 ///   else_bb:
215 ///     ; The original call instruction is moved to the "else" block.
216 ///     %t0 = call i32 %ptr()
217 ///     br merge_bb
218 ///
219 ///   merge_bb:
220 ///     ; Uses of the original call instruction are replaced by uses of the phi
221 ///     ; node.
222 ///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
223 ///     ...
224 ///
225 /// A similar transformation is performed for invoke instructions. However,
226 /// since invokes are terminating, more work is required. For example, the
227 /// invoke instruction below:
228 ///
229 ///   orig_bb:
230 ///     %t0 = invoke %ptr() to label %normal_dst unwind label %unwind_dst
231 ///
232 /// Is replace by the following:
233 ///
234 ///   orig_bb:
235 ///     %cond = icmp eq i32 ()* %ptr, @func
236 ///     br i1 %cond, %then_bb, %else_bb
237 ///
238 ///   then_bb:
239 ///     ; The clone of the original invoke instruction is placed in the "then"
240 ///     ; block, and its normal destination is set to the "merge" block. It is
241 ///     ; not yet promoted.
242 ///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
243 ///
244 ///   else_bb:
245 ///     ; The original invoke instruction is moved into the "else" block, and
246 ///     ; its normal destination is set to the "merge" block.
247 ///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
248 ///
249 ///   merge_bb:
250 ///     ; Uses of the original invoke instruction are replaced by uses of the
251 ///     ; phi node, and the merge block branches to the normal destination.
252 ///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
253 ///     br %normal_dst
254 ///
255 /// An indirect musttail call is processed slightly differently in that:
256 /// 1. No merge block needed for the orginal and the cloned callsite, since
257 ///    either one ends the flow. No phi node is needed either.
258 /// 2. The return statement following the original call site is duplicated too
259 ///    and placed immediately after the cloned call site per the IR convention.
260 ///
261 /// For example, the musttail call instruction below:
262 ///
263 ///   orig_bb:
264 ///     %t0 = musttail call i32 %ptr()
265 ///     ...
266 ///
267 /// Is replaced by the following:
268 ///
269 ///   cond_bb:
270 ///     %cond = icmp eq i32 ()* %ptr, @func
271 ///     br i1 %cond, %then_bb, %orig_bb
272 ///
273 ///   then_bb:
274 ///     ; The clone of the original call instruction is placed in the "then"
275 ///     ; block. It is not yet promoted.
276 ///     %t1 = musttail call i32 %ptr()
277 ///     ret %t1
278 ///
279 ///   orig_bb:
280 ///     ; The original call instruction stays in its original block.
281 ///     %t0 = musttail call i32 %ptr()
282 ///     ret %t0
283 CallBase &llvm::versionCallSite(CallBase &CB, Value *Callee,
284                                 MDNode *BranchWeights) {
285 
286   IRBuilder<> Builder(&CB);
287   CallBase *OrigInst = &CB;
288   BasicBlock *OrigBlock = OrigInst->getParent();
289 
290   // Create the compare. The called value and callee must have the same type to
291   // be compared.
292   if (CB.getCalledOperand()->getType() != Callee->getType())
293     Callee = Builder.CreateBitCast(Callee, CB.getCalledOperand()->getType());
294   auto *Cond = Builder.CreateICmpEQ(CB.getCalledOperand(), Callee);
295 
296   if (OrigInst->isMustTailCall()) {
297     // Create an if-then structure. The original instruction stays in its block,
298     // and a clone of the original instruction is placed in the "then" block.
299     Instruction *ThenTerm =
300         SplitBlockAndInsertIfThen(Cond, &CB, false, BranchWeights);
301     BasicBlock *ThenBlock = ThenTerm->getParent();
302     ThenBlock->setName("if.true.direct_targ");
303     CallBase *NewInst = cast<CallBase>(OrigInst->clone());
304     NewInst->insertBefore(ThenTerm);
305 
306     // Place a clone of the optional bitcast after the new call site.
307     Value *NewRetVal = NewInst;
308     auto Next = OrigInst->getNextNode();
309     if (auto *BitCast = dyn_cast_or_null<BitCastInst>(Next)) {
310       assert(BitCast->getOperand(0) == OrigInst &&
311              "bitcast following musttail call must use the call");
312       auto NewBitCast = BitCast->clone();
313       NewBitCast->replaceUsesOfWith(OrigInst, NewInst);
314       NewBitCast->insertBefore(ThenTerm);
315       NewRetVal = NewBitCast;
316       Next = BitCast->getNextNode();
317     }
318 
319     // Place a clone of the return instruction after the new call site.
320     ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
321     assert(Ret && "musttail call must precede a ret with an optional bitcast");
322     auto NewRet = Ret->clone();
323     if (Ret->getReturnValue())
324       NewRet->replaceUsesOfWith(Ret->getReturnValue(), NewRetVal);
325     NewRet->insertBefore(ThenTerm);
326 
327     // A return instructions is terminating, so we don't need the terminator
328     // instruction just created.
329     ThenTerm->eraseFromParent();
330 
331     return *NewInst;
332   }
333 
334   // Create an if-then-else structure. The original instruction is moved into
335   // the "else" block, and a clone of the original instruction is placed in the
336   // "then" block.
337   Instruction *ThenTerm = nullptr;
338   Instruction *ElseTerm = nullptr;
339   SplitBlockAndInsertIfThenElse(Cond, &CB, &ThenTerm, &ElseTerm, BranchWeights);
340   BasicBlock *ThenBlock = ThenTerm->getParent();
341   BasicBlock *ElseBlock = ElseTerm->getParent();
342   BasicBlock *MergeBlock = OrigInst->getParent();
343 
344   ThenBlock->setName("if.true.direct_targ");
345   ElseBlock->setName("if.false.orig_indirect");
346   MergeBlock->setName("if.end.icp");
347 
348   CallBase *NewInst = cast<CallBase>(OrigInst->clone());
349   OrigInst->moveBefore(ElseTerm);
350   NewInst->insertBefore(ThenTerm);
351 
352   // If the original call site is an invoke instruction, we have extra work to
353   // do since invoke instructions are terminating. We have to fix-up phi nodes
354   // in the invoke's normal and unwind destinations.
355   if (auto *OrigInvoke = dyn_cast<InvokeInst>(OrigInst)) {
356     auto *NewInvoke = cast<InvokeInst>(NewInst);
357 
358     // Invoke instructions are terminating, so we don't need the terminator
359     // instructions that were just created.
360     ThenTerm->eraseFromParent();
361     ElseTerm->eraseFromParent();
362 
363     // Branch from the "merge" block to the original normal destination.
364     Builder.SetInsertPoint(MergeBlock);
365     Builder.CreateBr(OrigInvoke->getNormalDest());
366 
367     // Fix-up phi nodes in the original invoke's normal and unwind destinations.
368     fixupPHINodeForNormalDest(OrigInvoke, OrigBlock, MergeBlock);
369     fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
370 
371     // Now set the normal destinations of the invoke instructions to be the
372     // "merge" block.
373     OrigInvoke->setNormalDest(MergeBlock);
374     NewInvoke->setNormalDest(MergeBlock);
375   }
376 
377   // Create a phi node for the returned value of the call site.
378   createRetPHINode(OrigInst, NewInst, MergeBlock, Builder);
379 
380   return *NewInst;
381 }
382 
383 bool llvm::isLegalToPromote(const CallBase &CB, Function *Callee,
384                             const char **FailureReason) {
385   assert(!CB.getCalledFunction() && "Only indirect call sites can be promoted");
386 
387   auto &DL = Callee->getParent()->getDataLayout();
388 
389   // Check the return type. The callee's return value type must be bitcast
390   // compatible with the call site's type.
391   Type *CallRetTy = CB.getType();
392   Type *FuncRetTy = Callee->getReturnType();
393   if (CallRetTy != FuncRetTy)
394     if (!CastInst::isBitOrNoopPointerCastable(FuncRetTy, CallRetTy, DL)) {
395       if (FailureReason)
396         *FailureReason = "Return type mismatch";
397       return false;
398     }
399 
400   // The number of formal arguments of the callee.
401   unsigned NumParams = Callee->getFunctionType()->getNumParams();
402 
403   // The number of actual arguments in the call.
404   unsigned NumArgs = CB.arg_size();
405 
406   // Check the number of arguments. The callee and call site must agree on the
407   // number of arguments.
408   if (NumArgs != NumParams && !Callee->isVarArg()) {
409     if (FailureReason)
410       *FailureReason = "The number of arguments mismatch";
411     return false;
412   }
413 
414   // Check the argument types. The callee's formal argument types must be
415   // bitcast compatible with the corresponding actual argument types of the call
416   // site.
417   unsigned I = 0;
418   for (; I < NumParams; ++I) {
419     // Make sure that the callee and call agree on byval/inalloca. The types do
420     // not have to match.
421     if (Callee->hasParamAttribute(I, Attribute::ByVal) !=
422         CB.getAttributes().hasParamAttr(I, Attribute::ByVal)) {
423       if (FailureReason)
424         *FailureReason = "byval mismatch";
425       return false;
426     }
427     if (Callee->hasParamAttribute(I, Attribute::InAlloca) !=
428         CB.getAttributes().hasParamAttr(I, Attribute::InAlloca)) {
429       if (FailureReason)
430         *FailureReason = "inalloca mismatch";
431       return false;
432     }
433 
434     Type *FormalTy = Callee->getFunctionType()->getFunctionParamType(I);
435     Type *ActualTy = CB.getArgOperand(I)->getType();
436     if (FormalTy == ActualTy)
437       continue;
438     if (!CastInst::isBitOrNoopPointerCastable(ActualTy, FormalTy, DL)) {
439       if (FailureReason)
440         *FailureReason = "Argument type mismatch";
441       return false;
442     }
443 
444     // MustTail call needs stricter type match. See
445     // Verifier::verifyMustTailCall().
446     if (CB.isMustTailCall()) {
447       PointerType *PF = dyn_cast<PointerType>(FormalTy);
448       PointerType *PA = dyn_cast<PointerType>(ActualTy);
449       if (!PF || !PA || PF->getAddressSpace() != PA->getAddressSpace()) {
450         if (FailureReason)
451           *FailureReason = "Musttail call Argument type mismatch";
452         return false;
453       }
454     }
455   }
456   for (; I < NumArgs; I++) {
457     // Vararg functions can have more arguments than parameters.
458     assert(Callee->isVarArg());
459     if (CB.paramHasAttr(I, Attribute::StructRet)) {
460       if (FailureReason)
461         *FailureReason = "SRet arg to vararg function";
462       return false;
463     }
464   }
465 
466   return true;
467 }
468 
469 CallBase &llvm::promoteCall(CallBase &CB, Function *Callee,
470                             CastInst **RetBitCast) {
471   assert(!CB.getCalledFunction() && "Only indirect call sites can be promoted");
472 
473   // Set the called function of the call site to be the given callee (but don't
474   // change the type).
475   CB.setCalledOperand(Callee);
476 
477   // Since the call site will no longer be direct, we must clear metadata that
478   // is only appropriate for indirect calls. This includes !prof and !callees
479   // metadata.
480   CB.setMetadata(LLVMContext::MD_prof, nullptr);
481   CB.setMetadata(LLVMContext::MD_callees, nullptr);
482 
483   // If the function type of the call site matches that of the callee, no
484   // additional work is required.
485   if (CB.getFunctionType() == Callee->getFunctionType())
486     return CB;
487 
488   // Save the return types of the call site and callee.
489   Type *CallSiteRetTy = CB.getType();
490   Type *CalleeRetTy = Callee->getReturnType();
491 
492   // Change the function type of the call site the match that of the callee.
493   CB.mutateFunctionType(Callee->getFunctionType());
494 
495   // Inspect the arguments of the call site. If an argument's type doesn't
496   // match the corresponding formal argument's type in the callee, bitcast it
497   // to the correct type.
498   auto CalleeType = Callee->getFunctionType();
499   auto CalleeParamNum = CalleeType->getNumParams();
500 
501   LLVMContext &Ctx = Callee->getContext();
502   const AttributeList &CallerPAL = CB.getAttributes();
503   // The new list of argument attributes.
504   SmallVector<AttributeSet, 4> NewArgAttrs;
505   bool AttributeChanged = false;
506 
507   for (unsigned ArgNo = 0; ArgNo < CalleeParamNum; ++ArgNo) {
508     auto *Arg = CB.getArgOperand(ArgNo);
509     Type *FormalTy = CalleeType->getParamType(ArgNo);
510     Type *ActualTy = Arg->getType();
511     if (FormalTy != ActualTy) {
512       auto *Cast = CastInst::CreateBitOrPointerCast(Arg, FormalTy, "", &CB);
513       CB.setArgOperand(ArgNo, Cast);
514 
515       // Remove any incompatible attributes for the argument.
516       AttrBuilder ArgAttrs(Ctx, CallerPAL.getParamAttrs(ArgNo));
517       ArgAttrs.remove(AttributeFuncs::typeIncompatible(FormalTy));
518 
519       // We may have a different byval/inalloca type.
520       if (ArgAttrs.getByValType())
521         ArgAttrs.addByValAttr(Callee->getParamByValType(ArgNo));
522       if (ArgAttrs.getInAllocaType())
523         ArgAttrs.addInAllocaAttr(Callee->getParamInAllocaType(ArgNo));
524 
525       NewArgAttrs.push_back(AttributeSet::get(Ctx, ArgAttrs));
526       AttributeChanged = true;
527     } else
528       NewArgAttrs.push_back(CallerPAL.getParamAttrs(ArgNo));
529   }
530 
531   // If the return type of the call site doesn't match that of the callee, cast
532   // the returned value to the appropriate type.
533   // Remove any incompatible return value attribute.
534   AttrBuilder RAttrs(Ctx, CallerPAL.getRetAttrs());
535   if (!CallSiteRetTy->isVoidTy() && CallSiteRetTy != CalleeRetTy) {
536     createRetBitCast(CB, CallSiteRetTy, RetBitCast);
537     RAttrs.remove(AttributeFuncs::typeIncompatible(CalleeRetTy));
538     AttributeChanged = true;
539   }
540 
541   // Set the new callsite attribute.
542   if (AttributeChanged)
543     CB.setAttributes(AttributeList::get(Ctx, CallerPAL.getFnAttrs(),
544                                         AttributeSet::get(Ctx, RAttrs),
545                                         NewArgAttrs));
546 
547   return CB;
548 }
549 
550 CallBase &llvm::promoteCallWithIfThenElse(CallBase &CB, Function *Callee,
551                                           MDNode *BranchWeights) {
552 
553   // Version the indirect call site. If the called value is equal to the given
554   // callee, 'NewInst' will be executed, otherwise the original call site will
555   // be executed.
556   CallBase &NewInst = versionCallSite(CB, Callee, BranchWeights);
557 
558   // Promote 'NewInst' so that it directly calls the desired function.
559   return promoteCall(NewInst, Callee);
560 }
561 
562 bool llvm::tryPromoteCall(CallBase &CB) {
563   assert(!CB.getCalledFunction());
564   Module *M = CB.getCaller()->getParent();
565   const DataLayout &DL = M->getDataLayout();
566   Value *Callee = CB.getCalledOperand();
567 
568   LoadInst *VTableEntryLoad = dyn_cast<LoadInst>(Callee);
569   if (!VTableEntryLoad)
570     return false; // Not a vtable entry load.
571   Value *VTableEntryPtr = VTableEntryLoad->getPointerOperand();
572   APInt VTableOffset(DL.getTypeSizeInBits(VTableEntryPtr->getType()), 0);
573   Value *VTableBasePtr = VTableEntryPtr->stripAndAccumulateConstantOffsets(
574       DL, VTableOffset, /* AllowNonInbounds */ true);
575   LoadInst *VTablePtrLoad = dyn_cast<LoadInst>(VTableBasePtr);
576   if (!VTablePtrLoad)
577     return false; // Not a vtable load.
578   Value *Object = VTablePtrLoad->getPointerOperand();
579   APInt ObjectOffset(DL.getTypeSizeInBits(Object->getType()), 0);
580   Value *ObjectBase = Object->stripAndAccumulateConstantOffsets(
581       DL, ObjectOffset, /* AllowNonInbounds */ true);
582   if (!(isa<AllocaInst>(ObjectBase) && ObjectOffset == 0))
583     // Not an Alloca or the offset isn't zero.
584     return false;
585 
586   // Look for the vtable pointer store into the object by the ctor.
587   BasicBlock::iterator BBI(VTablePtrLoad);
588   Value *VTablePtr = FindAvailableLoadedValue(
589       VTablePtrLoad, VTablePtrLoad->getParent(), BBI, 0, nullptr, nullptr);
590   if (!VTablePtr)
591     return false; // No vtable found.
592   APInt VTableOffsetGVBase(DL.getTypeSizeInBits(VTablePtr->getType()), 0);
593   Value *VTableGVBase = VTablePtr->stripAndAccumulateConstantOffsets(
594       DL, VTableOffsetGVBase, /* AllowNonInbounds */ true);
595   GlobalVariable *GV = dyn_cast<GlobalVariable>(VTableGVBase);
596   if (!(GV && GV->isConstant() && GV->hasDefinitiveInitializer()))
597     // Not in the form of a global constant variable with an initializer.
598     return false;
599 
600   Constant *VTableGVInitializer = GV->getInitializer();
601   APInt VTableGVOffset = VTableOffsetGVBase + VTableOffset;
602   if (!(VTableGVOffset.getActiveBits() <= 64))
603     return false; // Out of range.
604   Constant *Ptr = getPointerAtOffset(VTableGVInitializer,
605                                      VTableGVOffset.getZExtValue(),
606                                      *M);
607   if (!Ptr)
608     return false; // No constant (function) pointer found.
609   Function *DirectCallee = dyn_cast<Function>(Ptr->stripPointerCasts());
610   if (!DirectCallee)
611     return false; // No function pointer found.
612 
613   if (!isLegalToPromote(CB, DirectCallee))
614     return false;
615 
616   // Success.
617   promoteCall(CB, DirectCallee);
618   return true;
619 }
620 
621 #undef DEBUG_TYPE
622