LLVM  14.0.0git
CallPromotionUtils.cpp
Go to the documentation of this file.
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 
15 #include "llvm/Analysis/Loads.h"
17 #include "llvm/IR/IRBuilder.h"
18 #include "llvm/IR/Instructions.h"
20 
21 using namespace llvm;
22 
23 #define DEBUG_TYPE "call-promotion-utils"
24 
25 /// Fix-up phi nodes in an invoke instruction's normal destination.
26 ///
27 /// After versioning an invoke instruction, values coming from the original
28 /// block will now be coming from the "merge" block. For example, in the code
29 /// below:
30 ///
31 /// then_bb:
32 /// %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
33 ///
34 /// else_bb:
35 /// %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
36 ///
37 /// merge_bb:
38 /// %t2 = phi i32 [ %t0, %then_bb ], [ %t1, %else_bb ]
39 /// br %normal_dst
40 ///
41 /// normal_dst:
42 /// %t3 = phi i32 [ %x, %orig_bb ], ...
43 ///
44 /// "orig_bb" is no longer a predecessor of "normal_dst", so the phi nodes in
45 /// "normal_dst" must be fixed to refer to "merge_bb":
46 ///
47 /// normal_dst:
48 /// %t3 = phi i32 [ %x, %merge_bb ], ...
49 ///
50 static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
51  BasicBlock *MergeBlock) {
52  for (PHINode &Phi : Invoke->getNormalDest()->phis()) {
53  int Idx = Phi.getBasicBlockIndex(OrigBlock);
54  if (Idx == -1)
55  continue;
56  Phi.setIncomingBlock(Idx, MergeBlock);
57  }
58 }
59 
60 /// Fix-up phi nodes in an invoke instruction's unwind destination.
61 ///
62 /// After versioning an invoke instruction, values coming from the original
63 /// block will now be coming from either the "then" block or the "else" block.
64 /// For example, in the code below:
65 ///
66 /// then_bb:
67 /// %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
68 ///
69 /// else_bb:
70 /// %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
71 ///
72 /// unwind_dst:
73 /// %t3 = phi i32 [ %x, %orig_bb ], ...
74 ///
75 /// "orig_bb" is no longer a predecessor of "unwind_dst", so the phi nodes in
76 /// "unwind_dst" must be fixed to refer to "then_bb" and "else_bb":
77 ///
78 /// unwind_dst:
79 /// %t3 = phi i32 [ %x, %then_bb ], [ %x, %else_bb ], ...
80 ///
81 static void fixupPHINodeForUnwindDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
82  BasicBlock *ThenBlock,
83  BasicBlock *ElseBlock) {
84  for (PHINode &Phi : Invoke->getUnwindDest()->phis()) {
85  int Idx = Phi.getBasicBlockIndex(OrigBlock);
86  if (Idx == -1)
87  continue;
88  auto *V = Phi.getIncomingValue(Idx);
89  Phi.setIncomingBlock(Idx, ThenBlock);
90  Phi.addIncoming(V, ElseBlock);
91  }
92 }
93 
94 /// Create a phi node for the returned value of a call or invoke instruction.
95 ///
96 /// After versioning a call or invoke instruction that returns a value, we have
97 /// to merge the value of the original and new instructions. We do this by
98 /// creating a phi node and replacing uses of the original instruction with this
99 /// phi node.
100 ///
101 /// For example, if \p OrigInst is defined in "else_bb" and \p NewInst is
102 /// defined in "then_bb", we create the following phi node:
103 ///
104 /// ; Uses of the original instruction are replaced by uses of the phi node.
105 /// %t0 = phi i32 [ %orig_inst, %else_bb ], [ %new_inst, %then_bb ],
106 ///
107 static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst,
108  BasicBlock *MergeBlock, IRBuilder<> &Builder) {
109 
110  if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
111  return;
112 
113  Builder.SetInsertPoint(&MergeBlock->front());
114  PHINode *Phi = Builder.CreatePHI(OrigInst->getType(), 0);
115  SmallVector<User *, 16> UsersToUpdate(OrigInst->users());
116  for (User *U : UsersToUpdate)
117  U->replaceUsesOfWith(OrigInst, Phi);
118  Phi->addIncoming(OrigInst, OrigInst->getParent());
119  Phi->addIncoming(NewInst, NewInst->getParent());
120 }
121 
122 /// Cast a call or invoke instruction to the given type.
123 ///
124 /// When promoting a call site, the return type of the call site might not match
125 /// that of the callee. If this is the case, we have to cast the returned value
126 /// to the correct type. The location of the cast depends on if we have a call
127 /// or invoke instruction.
128 ///
129 /// For example, if the call instruction below requires a bitcast after
130 /// promotion:
131 ///
132 /// orig_bb:
133 /// %t0 = call i32 @func()
134 /// ...
135 ///
136 /// The bitcast is placed after the call instruction:
137 ///
138 /// orig_bb:
139 /// ; Uses of the original return value are replaced by uses of the bitcast.
140 /// %t0 = call i32 @func()
141 /// %t1 = bitcast i32 %t0 to ...
142 /// ...
143 ///
144 /// A similar transformation is performed for invoke instructions. However,
145 /// since invokes are terminating, a new block is created for the bitcast. For
146 /// example, if the invoke instruction below requires a bitcast after promotion:
147 ///
148 /// orig_bb:
149 /// %t0 = invoke i32 @func() to label %normal_dst unwind label %unwind_dst
150 ///
151 /// The edge between the original block and the invoke's normal destination is
152 /// split, and the bitcast is placed there:
153 ///
154 /// orig_bb:
155 /// %t0 = invoke i32 @func() to label %split_bb unwind label %unwind_dst
156 ///
157 /// split_bb:
158 /// ; Uses of the original return value are replaced by uses of the bitcast.
159 /// %t1 = bitcast i32 %t0 to ...
160 /// br label %normal_dst
161 ///
162 static void createRetBitCast(CallBase &CB, Type *RetTy, CastInst **RetBitCast) {
163 
164  // Save the users of the calling instruction. These uses will be changed to
165  // use the bitcast after we create it.
166  SmallVector<User *, 16> UsersToUpdate(CB.users());
167 
168  // Determine an appropriate location to create the bitcast for the return
169  // value. The location depends on if we have a call or invoke instruction.
170  Instruction *InsertBefore = nullptr;
171  if (auto *Invoke = dyn_cast<InvokeInst>(&CB))
172  InsertBefore =
173  &SplitEdge(Invoke->getParent(), Invoke->getNormalDest())->front();
174  else
175  InsertBefore = &*std::next(CB.getIterator());
176 
177  // Bitcast the return value to the correct type.
178  auto *Cast = CastInst::CreateBitOrPointerCast(&CB, RetTy, "", InsertBefore);
179  if (RetBitCast)
180  *RetBitCast = Cast;
181 
182  // Replace all the original uses of the calling instruction with the bitcast.
183  for (User *U : UsersToUpdate)
184  U->replaceUsesOfWith(&CB, Cast);
185 }
186 
187 /// Predicate and clone the given call site.
188 ///
189 /// This function creates an if-then-else structure at the location of the call
190 /// site. The "if" condition compares the call site's called value to the given
191 /// callee. The original call site is moved into the "else" block, and a clone
192 /// of the call site is placed in the "then" block. The cloned instruction is
193 /// returned.
194 ///
195 /// For example, the call instruction below:
196 ///
197 /// orig_bb:
198 /// %t0 = call i32 %ptr()
199 /// ...
200 ///
201 /// Is replace by the following:
202 ///
203 /// orig_bb:
204 /// %cond = icmp eq i32 ()* %ptr, @func
205 /// br i1 %cond, %then_bb, %else_bb
206 ///
207 /// then_bb:
208 /// ; The clone of the original call instruction is placed in the "then"
209 /// ; block. It is not yet promoted.
210 /// %t1 = call i32 %ptr()
211 /// br merge_bb
212 ///
213 /// else_bb:
214 /// ; The original call instruction is moved to the "else" block.
215 /// %t0 = call i32 %ptr()
216 /// br merge_bb
217 ///
218 /// merge_bb:
219 /// ; Uses of the original call instruction are replaced by uses of the phi
220 /// ; node.
221 /// %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
222 /// ...
223 ///
224 /// A similar transformation is performed for invoke instructions. However,
225 /// since invokes are terminating, more work is required. For example, the
226 /// invoke instruction below:
227 ///
228 /// orig_bb:
229 /// %t0 = invoke %ptr() to label %normal_dst unwind label %unwind_dst
230 ///
231 /// Is replace by the following:
232 ///
233 /// orig_bb:
234 /// %cond = icmp eq i32 ()* %ptr, @func
235 /// br i1 %cond, %then_bb, %else_bb
236 ///
237 /// then_bb:
238 /// ; The clone of the original invoke instruction is placed in the "then"
239 /// ; block, and its normal destination is set to the "merge" block. It is
240 /// ; not yet promoted.
241 /// %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
242 ///
243 /// else_bb:
244 /// ; The original invoke instruction is moved into the "else" block, and
245 /// ; its normal destination is set to the "merge" block.
246 /// %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
247 ///
248 /// merge_bb:
249 /// ; Uses of the original invoke instruction are replaced by uses of the
250 /// ; phi node, and the merge block branches to the normal destination.
251 /// %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
252 /// br %normal_dst
253 ///
254 /// An indirect musttail call is processed slightly differently in that:
255 /// 1. No merge block needed for the orginal and the cloned callsite, since
256 /// either one ends the flow. No phi node is needed either.
257 /// 2. The return statement following the original call site is duplicated too
258 /// and placed immediately after the cloned call site per the IR convention.
259 ///
260 /// For example, the musttail call instruction below:
261 ///
262 /// orig_bb:
263 /// %t0 = musttail call i32 %ptr()
264 /// ...
265 ///
266 /// Is replaced by the following:
267 ///
268 /// cond_bb:
269 /// %cond = icmp eq i32 ()* %ptr, @func
270 /// br i1 %cond, %then_bb, %orig_bb
271 ///
272 /// then_bb:
273 /// ; The clone of the original call instruction is placed in the "then"
274 /// ; block. It is not yet promoted.
275 /// %t1 = musttail call i32 %ptr()
276 /// ret %t1
277 ///
278 /// orig_bb:
279 /// ; The original call instruction stays in its original block.
280 /// %t0 = musttail call i32 %ptr()
281 /// ret %t0
282 static CallBase &versionCallSite(CallBase &CB, Value *Callee,
283  MDNode *BranchWeights) {
284 
285  IRBuilder<> Builder(&CB);
286  CallBase *OrigInst = &CB;
287  BasicBlock *OrigBlock = OrigInst->getParent();
288 
289  // Create the compare. The called value and callee must have the same type to
290  // be compared.
291  if (CB.getCalledOperand()->getType() != Callee->getType())
292  Callee = Builder.CreateBitCast(Callee, CB.getCalledOperand()->getType());
293  auto *Cond = Builder.CreateICmpEQ(CB.getCalledOperand(), Callee);
294 
295  if (OrigInst->isMustTailCall()) {
296  // Create an if-then structure. The original instruction stays in its block,
297  // and a clone of the original instruction is placed in the "then" block.
298  Instruction *ThenTerm =
299  SplitBlockAndInsertIfThen(Cond, &CB, false, BranchWeights);
300  BasicBlock *ThenBlock = ThenTerm->getParent();
301  ThenBlock->setName("if.true.direct_targ");
302  CallBase *NewInst = cast<CallBase>(OrigInst->clone());
303  NewInst->insertBefore(ThenTerm);
304 
305  // Place a clone of the optional bitcast after the new call site.
306  Value *NewRetVal = NewInst;
307  auto Next = OrigInst->getNextNode();
308  if (auto *BitCast = dyn_cast_or_null<BitCastInst>(Next)) {
309  assert(BitCast->getOperand(0) == OrigInst &&
310  "bitcast following musttail call must use the call");
311  auto NewBitCast = BitCast->clone();
312  NewBitCast->replaceUsesOfWith(OrigInst, NewInst);
313  NewBitCast->insertBefore(ThenTerm);
314  NewRetVal = NewBitCast;
315  Next = BitCast->getNextNode();
316  }
317 
318  // Place a clone of the return instruction after the new call site.
319  ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
320  assert(Ret && "musttail call must precede a ret with an optional bitcast");
321  auto NewRet = Ret->clone();
322  if (Ret->getReturnValue())
323  NewRet->replaceUsesOfWith(Ret->getReturnValue(), NewRetVal);
324  NewRet->insertBefore(ThenTerm);
325 
326  // A return instructions is terminating, so we don't need the terminator
327  // instruction just created.
328  ThenTerm->eraseFromParent();
329 
330  return *NewInst;
331  }
332 
333  // Create an if-then-else structure. The original instruction is moved into
334  // the "else" block, and a clone of the original instruction is placed in the
335  // "then" block.
336  Instruction *ThenTerm = nullptr;
337  Instruction *ElseTerm = nullptr;
338  SplitBlockAndInsertIfThenElse(Cond, &CB, &ThenTerm, &ElseTerm, BranchWeights);
339  BasicBlock *ThenBlock = ThenTerm->getParent();
340  BasicBlock *ElseBlock = ElseTerm->getParent();
341  BasicBlock *MergeBlock = OrigInst->getParent();
342 
343  ThenBlock->setName("if.true.direct_targ");
344  ElseBlock->setName("if.false.orig_indirect");
345  MergeBlock->setName("if.end.icp");
346 
347  CallBase *NewInst = cast<CallBase>(OrigInst->clone());
348  OrigInst->moveBefore(ElseTerm);
349  NewInst->insertBefore(ThenTerm);
350 
351  // If the original call site is an invoke instruction, we have extra work to
352  // do since invoke instructions are terminating. We have to fix-up phi nodes
353  // in the invoke's normal and unwind destinations.
354  if (auto *OrigInvoke = dyn_cast<InvokeInst>(OrigInst)) {
355  auto *NewInvoke = cast<InvokeInst>(NewInst);
356 
357  // Invoke instructions are terminating, so we don't need the terminator
358  // instructions that were just created.
359  ThenTerm->eraseFromParent();
360  ElseTerm->eraseFromParent();
361 
362  // Branch from the "merge" block to the original normal destination.
363  Builder.SetInsertPoint(MergeBlock);
364  Builder.CreateBr(OrigInvoke->getNormalDest());
365 
366  // Fix-up phi nodes in the original invoke's normal and unwind destinations.
367  fixupPHINodeForNormalDest(OrigInvoke, OrigBlock, MergeBlock);
368  fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
369 
370  // Now set the normal destinations of the invoke instructions to be the
371  // "merge" block.
372  OrigInvoke->setNormalDest(MergeBlock);
373  NewInvoke->setNormalDest(MergeBlock);
374  }
375 
376  // Create a phi node for the returned value of the call site.
377  createRetPHINode(OrigInst, NewInst, MergeBlock, Builder);
378 
379  return *NewInst;
380 }
381 
382 bool llvm::isLegalToPromote(const CallBase &CB, Function *Callee,
383  const char **FailureReason) {
384  assert(!CB.getCalledFunction() && "Only indirect call sites can be promoted");
385 
386  auto &DL = Callee->getParent()->getDataLayout();
387 
388  // Check the return type. The callee's return value type must be bitcast
389  // compatible with the call site's type.
390  Type *CallRetTy = CB.getType();
391  Type *FuncRetTy = Callee->getReturnType();
392  if (CallRetTy != FuncRetTy)
393  if (!CastInst::isBitOrNoopPointerCastable(FuncRetTy, CallRetTy, DL)) {
394  if (FailureReason)
395  *FailureReason = "Return type mismatch";
396  return false;
397  }
398 
399  // The number of formal arguments of the callee.
400  unsigned NumParams = Callee->getFunctionType()->getNumParams();
401 
402  // The number of actual arguments in the call.
403  unsigned NumArgs = CB.arg_size();
404 
405  // Check the number of arguments. The callee and call site must agree on the
406  // number of arguments.
407  if (NumArgs != NumParams && !Callee->isVarArg()) {
408  if (FailureReason)
409  *FailureReason = "The number of arguments mismatch";
410  return false;
411  }
412 
413  // Check the argument types. The callee's formal argument types must be
414  // bitcast compatible with the corresponding actual argument types of the call
415  // site.
416  unsigned I = 0;
417  for (; I < NumParams; ++I) {
419  Type *ActualTy = CB.getArgOperand(I)->getType();
420  if (FormalTy == ActualTy)
421  continue;
422  if (!CastInst::isBitOrNoopPointerCastable(ActualTy, FormalTy, DL)) {
423  if (FailureReason)
424  *FailureReason = "Argument type mismatch";
425  return false;
426  }
427  // Make sure that the callee and call agree on byval/inalloca. The types do
428  // not have to match.
429 
430  if (Callee->hasParamAttribute(I, Attribute::ByVal) !=
431  CB.getAttributes().hasParamAttr(I, Attribute::ByVal)) {
432  if (FailureReason)
433  *FailureReason = "byval mismatch";
434  return false;
435  }
436  if (Callee->hasParamAttribute(I, Attribute::InAlloca) !=
437  CB.getAttributes().hasParamAttr(I, Attribute::InAlloca)) {
438  if (FailureReason)
439  *FailureReason = "inalloca mismatch";
440  return false;
441  }
442  }
443  for (; I < NumArgs; I++) {
444  // Vararg functions can have more arguments than parameters.
445  assert(Callee->isVarArg());
446  if (CB.paramHasAttr(I, Attribute::StructRet)) {
447  if (FailureReason)
448  *FailureReason = "SRet arg to vararg function";
449  return false;
450  }
451  }
452 
453  return true;
454 }
455 
457  CastInst **RetBitCast) {
458  assert(!CB.getCalledFunction() && "Only indirect call sites can be promoted");
459 
460  // Set the called function of the call site to be the given callee (but don't
461  // change the type).
463 
464  // Since the call site will no longer be direct, we must clear metadata that
465  // is only appropriate for indirect calls. This includes !prof and !callees
466  // metadata.
467  CB.setMetadata(LLVMContext::MD_prof, nullptr);
468  CB.setMetadata(LLVMContext::MD_callees, nullptr);
469 
470  // If the function type of the call site matches that of the callee, no
471  // additional work is required.
472  if (CB.getFunctionType() == Callee->getFunctionType())
473  return CB;
474 
475  // Save the return types of the call site and callee.
476  Type *CallSiteRetTy = CB.getType();
477  Type *CalleeRetTy = Callee->getReturnType();
478 
479  // Change the function type of the call site the match that of the callee.
481 
482  // Inspect the arguments of the call site. If an argument's type doesn't
483  // match the corresponding formal argument's type in the callee, bitcast it
484  // to the correct type.
485  auto CalleeType = Callee->getFunctionType();
486  auto CalleeParamNum = CalleeType->getNumParams();
487 
488  LLVMContext &Ctx = Callee->getContext();
489  const AttributeList &CallerPAL = CB.getAttributes();
490  // The new list of argument attributes.
491  SmallVector<AttributeSet, 4> NewArgAttrs;
492  bool AttributeChanged = false;
493 
494  for (unsigned ArgNo = 0; ArgNo < CalleeParamNum; ++ArgNo) {
495  auto *Arg = CB.getArgOperand(ArgNo);
496  Type *FormalTy = CalleeType->getParamType(ArgNo);
497  Type *ActualTy = Arg->getType();
498  if (FormalTy != ActualTy) {
499  auto *Cast = CastInst::CreateBitOrPointerCast(Arg, FormalTy, "", &CB);
500  CB.setArgOperand(ArgNo, Cast);
501 
502  // Remove any incompatible attributes for the argument.
503  AttrBuilder ArgAttrs(CallerPAL.getParamAttrs(ArgNo));
504  ArgAttrs.remove(AttributeFuncs::typeIncompatible(FormalTy));
505 
506  // We may have a different byval/inalloca type.
507  if (ArgAttrs.getByValType())
508  ArgAttrs.addByValAttr(Callee->getParamByValType(ArgNo));
509  if (ArgAttrs.getInAllocaType())
510  ArgAttrs.addInAllocaAttr(Callee->getParamInAllocaType(ArgNo));
511 
512  NewArgAttrs.push_back(AttributeSet::get(Ctx, ArgAttrs));
513  AttributeChanged = true;
514  } else
515  NewArgAttrs.push_back(CallerPAL.getParamAttrs(ArgNo));
516  }
517 
518  // If the return type of the call site doesn't match that of the callee, cast
519  // the returned value to the appropriate type.
520  // Remove any incompatible return value attribute.
521  AttrBuilder RAttrs(CallerPAL, AttributeList::ReturnIndex);
522  if (!CallSiteRetTy->isVoidTy() && CallSiteRetTy != CalleeRetTy) {
523  createRetBitCast(CB, CallSiteRetTy, RetBitCast);
524  RAttrs.remove(AttributeFuncs::typeIncompatible(CalleeRetTy));
525  AttributeChanged = true;
526  }
527 
528  // Set the new callsite attribute.
529  if (AttributeChanged)
530  CB.setAttributes(AttributeList::get(Ctx, CallerPAL.getFnAttrs(),
531  AttributeSet::get(Ctx, RAttrs),
532  NewArgAttrs));
533 
534  return CB;
535 }
536 
538  MDNode *BranchWeights) {
539 
540  // Version the indirect call site. If the called value is equal to the given
541  // callee, 'NewInst' will be executed, otherwise the original call site will
542  // be executed.
543  CallBase &NewInst = versionCallSite(CB, Callee, BranchWeights);
544 
545  // Promote 'NewInst' so that it directly calls the desired function.
546  return promoteCall(NewInst, Callee);
547 }
548 
550  assert(!CB.getCalledFunction());
551  Module *M = CB.getCaller()->getParent();
552  const DataLayout &DL = M->getDataLayout();
553  Value *Callee = CB.getCalledOperand();
554 
555  LoadInst *VTableEntryLoad = dyn_cast<LoadInst>(Callee);
556  if (!VTableEntryLoad)
557  return false; // Not a vtable entry load.
558  Value *VTableEntryPtr = VTableEntryLoad->getPointerOperand();
559  APInt VTableOffset(DL.getTypeSizeInBits(VTableEntryPtr->getType()), 0);
560  Value *VTableBasePtr = VTableEntryPtr->stripAndAccumulateConstantOffsets(
561  DL, VTableOffset, /* AllowNonInbounds */ true);
562  LoadInst *VTablePtrLoad = dyn_cast<LoadInst>(VTableBasePtr);
563  if (!VTablePtrLoad)
564  return false; // Not a vtable load.
565  Value *Object = VTablePtrLoad->getPointerOperand();
566  APInt ObjectOffset(DL.getTypeSizeInBits(Object->getType()), 0);
567  Value *ObjectBase = Object->stripAndAccumulateConstantOffsets(
568  DL, ObjectOffset, /* AllowNonInbounds */ true);
569  if (!(isa<AllocaInst>(ObjectBase) && ObjectOffset == 0))
570  // Not an Alloca or the offset isn't zero.
571  return false;
572 
573  // Look for the vtable pointer store into the object by the ctor.
574  BasicBlock::iterator BBI(VTablePtrLoad);
575  Value *VTablePtr = FindAvailableLoadedValue(
576  VTablePtrLoad, VTablePtrLoad->getParent(), BBI, 0, nullptr, nullptr);
577  if (!VTablePtr)
578  return false; // No vtable found.
579  APInt VTableOffsetGVBase(DL.getTypeSizeInBits(VTablePtr->getType()), 0);
580  Value *VTableGVBase = VTablePtr->stripAndAccumulateConstantOffsets(
581  DL, VTableOffsetGVBase, /* AllowNonInbounds */ true);
582  GlobalVariable *GV = dyn_cast<GlobalVariable>(VTableGVBase);
583  if (!(GV && GV->isConstant() && GV->hasDefinitiveInitializer()))
584  // Not in the form of a global constant variable with an initializer.
585  return false;
586 
587  Constant *VTableGVInitializer = GV->getInitializer();
588  APInt VTableGVOffset = VTableOffsetGVBase + VTableOffset;
589  if (!(VTableGVOffset.getActiveBits() <= 64))
590  return false; // Out of range.
591  Constant *Ptr = getPointerAtOffset(VTableGVInitializer,
592  VTableGVOffset.getZExtValue(),
593  *M);
594  if (!Ptr)
595  return false; // No constant (function) pointer found.
596  Function *DirectCallee = dyn_cast<Function>(Ptr->stripPointerCasts());
597  if (!DirectCallee)
598  return false; // No function pointer found.
599 
600  if (!isLegalToPromote(CB, DirectCallee))
601  return false;
602 
603  // Success.
604  promoteCall(CB, DirectCallee);
605  return true;
606 }
607 
608 #undef DEBUG_TYPE
llvm::InvokeInst::getNormalDest
BasicBlock * getNormalDest() const
Definition: Instructions.h:3881
fixupPHINodeForUnwindDest
static void fixupPHINodeForUnwindDest(InvokeInst *Invoke, BasicBlock *OrigBlock, BasicBlock *ThenBlock, BasicBlock *ElseBlock)
Fix-up phi nodes in an invoke instruction's unwind destination.
Definition: CallPromotionUtils.cpp:81
llvm::AttrBuilder::getByValType
Type * getByValType() const
Retrieve the byval type.
Definition: Attributes.h:1037
llvm
This file implements support for optimizing divisions by a constant.
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::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2986
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
Loads.h
llvm::Function
Definition: Function.h:62
llvm::CallBase::mutateFunctionType
void mutateFunctionType(FunctionType *FTy)
Definition: InstrTypes.h:1243
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::IRBuilder<>
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::AttributeList::get
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:1011
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::AttributeFuncs::typeIncompatible
AttrBuilder typeIncompatible(Type *Ty)
Which attributes cannot be applied to a type.
Definition: Attributes.cpp:1811
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::AttributeList
Definition: Attributes.h:399
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1458
llvm::CallBase::getFunctionType
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1241
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1362
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:298
llvm::Value::stripAndAccumulateConstantOffsets
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
llvm::FunctionType::getNumParams
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:267
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::AttrBuilder::addByValAttr
AttrBuilder & addByValAttr(Type *Ty)
This turns a byval type into the form used internally in Attribute.
Definition: Attributes.cpp:1698
llvm::User
Definition: User.h:44
createRetPHINode
static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst, BasicBlock *MergeBlock, IRBuilder<> &Builder)
Create a phi node for the returned value of a call or invoke instruction.
Definition: CallPromotionUtils.cpp:107
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1383
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1462
llvm::promoteCallWithIfThenElse
CallBase & promoteCallWithIfThenElse(CallBase &CB, Function *Callee, MDNode *BranchWeights=nullptr)
Promote the given indirect call site to conditionally call Callee.
Definition: CallPromotionUtils.cpp:537
TypeMetadataUtils.h
versionCallSite
static CallBase & versionCallSite(CallBase &CB, Value *Callee, MDNode *BranchWeights)
Predicate and clone the given call site.
Definition: CallPromotionUtils.cpp:282
llvm::Instruction
Definition: Instruction.h:45
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1460
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::FunctionCallee::getFunctionType
FunctionType * getFunctionType()
Definition: DerivedTypes.h:182
llvm::isLegalToPromote
bool isLegalToPromote(const CallBase &CB, Function *Callee, const char **FailureReason=nullptr)
Return true if the given indirect call site can be made to call Callee.
Definition: CallPromotionUtils.cpp:382
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallBase::getCaller
Function * getCaller()
Helper to get the caller (the parent function).
Definition: Instructions.cpp:282
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::OutputFileType::Object
@ Object
llvm::AttributeList::ReturnIndex
@ ReturnIndex
Definition: Attributes.h:402
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:136
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:578
llvm::GlobalVariable::hasDefinitiveInitializer
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Definition: GlobalVariable.h:110
llvm::AttributeSet::get
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
Definition: Attributes.cpp:590
llvm::AttrBuilder::addInAllocaAttr
AttrBuilder & addInAllocaAttr(Type *Ty)
This turns an inalloca type into the form used internally in Attribute.
Definition: Attributes.cpp:1714
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::AttrBuilder
Definition: Attributes.h:931
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::SplitBlockAndInsertIfThenElse
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
Definition: BasicBlockUtils.cpp:1439
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:850
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
CallPromotionUtils.h
llvm::CastInst::isBitOrNoopPointerCastable
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
Definition: Instructions.cpp:3336
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::CallBase::paramHasAttr
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
Definition: Instructions.cpp:341
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1333
llvm::Constant::stripPointerCasts
const Constant * stripPointerCasts() const
Definition: Constant.h:207
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:493
llvm::AttrBuilder::remove
AttrBuilder & remove(const AttrBuilder &B)
Remove the attributes from the builder.
Definition: Attributes.cpp:1736
llvm::CastInst::CreateBitOrPointerCast
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
Definition: Instructions.cpp:3231
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1326
llvm::FindAvailableLoadedValue
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:431
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1376
llvm::CallBase::setCalledOperand
void setCalledOperand(Value *V)
Definition: InstrTypes.h:1416
createRetBitCast
static void createRetBitCast(CallBase &CB, Type *RetTy, CastInst **RetBitCast)
Cast a call or invoke instruction to the given type.
Definition: CallPromotionUtils.cpp:162
Instructions.h
llvm::getPointerAtOffset
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)
Processes a Constant recursively looking into elements of arrays, structs and expressions to find a t...
Definition: TypeMetadataUtils.cpp:129
llvm::GlobalVariable::isConstant
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
Definition: GlobalVariable.h:153
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1328
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::APInt::getActiveBits
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1434
llvm::PHINode
Definition: Instructions.h:2633
llvm::promoteCall
CallBase & promoteCall(CallBase &CB, Function *Callee, CastInst **RetBitCast=nullptr)
Promote the given indirect call site to unconditionally call Callee.
Definition: CallPromotionUtils.cpp:456
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::SplitBlockAndInsertIfThen
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
Definition: BasicBlockUtils.cpp:1418
llvm::Type::getFunctionParamType
Type * getFunctionParamType(unsigned i) const
Definition: DerivedTypes.h:153
llvm::AttributeList::hasParamAttr
bool hasParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the attribute exists for the given argument.
Definition: Attributes.h:722
llvm::AttributeList::getParamAttrs
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
Definition: Attributes.cpp:1354
llvm::AttrBuilder::getInAllocaType
Type * getInAllocaType() const
Retrieve the inalloca type.
Definition: Attributes.h:1051
BasicBlockUtils.h
llvm::InvokeInst::getUnwindDest
BasicBlock * getUnwindDest() const
Definition: Instructions.h:3884
fixupPHINodeForNormalDest
static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock, BasicBlock *MergeBlock)
Fix-up phi nodes in an invoke instruction's normal destination.
Definition: CallPromotionUtils.cpp:50
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::tryPromoteCall
bool tryPromoteCall(CallBase &CB)
Try to promote (devirtualize) a virtual call on an Alloca.
Definition: CallPromotionUtils.cpp:549
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97