contrib/llvm/lib/Transforms/Utils/CallPromotionUtils.cpp

   1 //===- CallPromotionUtils.cpp - Utilities for call promotion ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements utilities useful for promoting indirect call sites to
  11 // direct call sites.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
  16 #include "llvm/IR/IRBuilder.h"
  17 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  18
  19 using namespace llvm;
  20
  21 #define DEBUG_TYPE "call-promotion-utils"
  22
  23 /// Fix-up phi nodes in an invoke instruction's normal destination.
  24 ///
  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);
  32     if (!Phi)
  33       break;
  34     int Idx = Phi->getBasicBlockIndex(OrigBlock);
  35     if (Idx == -1)
  36       continue;
  37     Value *V = Phi->getIncomingValue(Idx);
  38     if (dyn_cast<Instruction>(V) == Invoke) {
  39       Phi->setIncomingBlock(Idx, ElseBlock);
  40       Phi->addIncoming(NewInst, OrigBlock);
  41       continue;
  42     }
  43     Phi->addIncoming(V, ElseBlock);
  44   }
  45 }
  46
  47 /// Fix-up phi nodes in an invoke instruction's unwind destination.
  48 ///
  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);
  56     if (!Phi)
  57       break;
  58     int Idx = Phi->getBasicBlockIndex(OrigBlock);
  59     if (Idx == -1)
  60       continue;
  61     auto *V = Phi->getIncomingValue(Idx);
  62     Phi->setIncomingBlock(Idx, ThenBlock);
  63     Phi->addIncoming(V, ElseBlock);
  64   }
  65 }
  66
  67 /// Get the phi node having the returned value of a call or invoke instruction
  68 /// as it's operand.
  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);
  73     if (!PHI)
  74       break;
  75     int Idx = PHI->getBasicBlockIndex(FromBlock);
  76     if (Idx == -1)
  77       continue;
  78     auto *V = PHI->getIncomingValue(Idx);
  79     if (V == Inst)
  80       return true;
  81   }
  82   return false;
  83 }
  84
  85 /// Create a phi node for the returned value of a call or invoke instruction.
  86 ///
  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
  90 /// phi node.
  91 static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst) {
  92
  93   if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
  94     return;
  95
  96   BasicBlock *RetValBB = NewInst->getParent();
  97   if (auto *Invoke = dyn_cast<InvokeInst>(NewInst))
  98     RetValBB = Invoke->getNormalDest();
  99   BasicBlock *PhiBB = RetValBB->getSingleSuccessor();
 100
 101   if (getRetPhiNode(OrigInst, PhiBB))
 102     return;
 103
 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);
 113 }
 114
 115 /// Cast a call or invoke instruction to the given type.
 116 ///
 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) {
 122
 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);
 128
 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();
 134   else
 135     InsertBefore = &*std::next(CS.getInstruction()->getIterator());
 136
 137   // Bitcast the return value to the correct type.
 138   auto *Cast = CastInst::Create(Instruction::BitCast, CS.getInstruction(),
 139                                 RetTy, "", InsertBefore);
 140
 141   // Replace all the original uses of the calling instruction with the bitcast.
 142   for (User *U : UsersToUpdate)
 143     U->replaceUsesOfWith(CS.getInstruction(), Cast);
 144
 145   return Cast;
 146 }
 147
 148 /// Predicate and clone the given call site.
 149 ///
 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
 154 /// returned.
 155 static Instruction *versionCallSite(CallSite CS, Value *Callee,
 156                                     MDNode *BranchWeights,
 157                                     BasicBlock *&ThenBlock,
 158                                     BasicBlock *&ElseBlock,
 159                                     BasicBlock *&MergeBlock) {
 160
 161   IRBuilder<> Builder(CS.getInstruction());
 162   Instruction *OrigInst = CS.getInstruction();
 163
 164   // Create the compare. The called value and callee must have the same type to
 165   // be compared.
 166   auto *LHS =
 167       Builder.CreateBitCast(CS.getCalledValue(), Builder.getInt8PtrTy());
 168   auto *RHS = Builder.CreateBitCast(Callee, Builder.getInt8PtrTy());
 169   auto *Cond = Builder.CreateICmpEQ(LHS, RHS);
 170
 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
 173   // "then" block.
 174   TerminatorInst *ThenTerm = nullptr;
 175   TerminatorInst *ElseTerm = nullptr;
 176   SplitBlockAndInsertIfThenElse(Cond, CS.getInstruction(), &ThenTerm, &ElseTerm,
 177                                 BranchWeights);
 178   ThenBlock = ThenTerm->getParent();
 179   ElseBlock = ElseTerm->getParent();
 180   MergeBlock = OrigInst->getParent();
 181
 182   ThenBlock->setName("if.true.direct_targ");
 183   ElseBlock->setName("if.false.orig_indirect");
 184   MergeBlock->setName("if.end.icp");
 185
 186   Instruction *NewInst = OrigInst->clone();
 187   OrigInst->moveBefore(ElseTerm);
 188   NewInst->insertBefore(ThenTerm);
 189
 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);
 194
 195     // Invoke instructions are terminating, so we don't need the terminator
 196     // instructions that were just created.
 197     ThenTerm->eraseFromParent();
 198     ElseTerm->eraseFromParent();
 199
 200     // Branch from the "merge" block to the original normal destination.
 201     Builder.SetInsertPoint(MergeBlock);
 202     Builder.CreateBr(OrigInvoke->getNormalDest());
 203
 204     // Now set the normal destination of new the invoke instruction to be the
 205     // "merge" block.
 206     NewInvoke->setNormalDest(MergeBlock);
 207   }
 208
 209   return NewInst;
 210 }
 211
 212 bool llvm::isLegalToPromote(CallSite CS, Function *Callee,
 213                             const char **FailureReason) {
 214   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 215
 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)) {
 222       if (FailureReason)
 223         *FailureReason = "Return type mismatch";
 224       return false;
 225     }
 226
 227   // The number of formal arguments of the callee.
 228   unsigned NumParams = Callee->getFunctionType()->getNumParams();
 229
 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()) {
 233     if (FailureReason)
 234       *FailureReason = "The number of arguments mismatch";
 235     return false;
 236   }
 237
 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
 240   // site.
 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)
 245       continue;
 246     if (!CastInst::isBitCastable(ActualTy, FormalTy)) {
 247       if (FailureReason)
 248         *FailureReason = "Argument type mismatch";
 249       return false;
 250     }
 251   }
 252
 253   return true;
 254 }
 255
 256 static void promoteCall(CallSite CS, Function *Callee, Instruction *&Cast) {
 257   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 258
 259   // Set the called function of the call site to be the given callee.
 260   CS.setCalledFunction(Callee);
 261
 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
 264   // metadata.
 265   CS.getInstruction()->setMetadata(LLVMContext::MD_prof, nullptr);
 266   CS.getInstruction()->setMetadata(LLVMContext::MD_callees, nullptr);
 267
 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())
 271     return;
 272
 273   // Save the return types of the call site and callee.
 274   Type *CallSiteRetTy = CS.getInstruction()->getType();
 275   Type *CalleeRetTy = Callee->getReturnType();
 276
 277   // Change the function type of the call site the match that of the callee.
 278   CS.mutateFunctionType(Callee->getFunctionType());
 279
 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);
 291     }
 292   }
 293
 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);
 298 }
 299
 300 Instruction *llvm::promoteCallWithIfThenElse(CallSite CS, Function *Callee,
 301                                              MDNode *BranchWeights) {
 302
 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
 305   // be executed.
 306   BasicBlock *ThenBlock, *ElseBlock, *MergeBlock;
 307   Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights, ThenBlock,
 308                                          ElseBlock, MergeBlock);
 309
 310   // Promote 'NewInst' so that it directly calls the desired function.
 311   Instruction *Cast = NewInst;
 312   promoteCall(CallSite(NewInst), Callee, Cast);
 313
 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);
 319   }
 320
 321   // Create a phi node for the returned value of the call site.
 322   createRetPHINode(CS.getInstruction(), Cast ? Cast : NewInst);
 323
 324   // Return the new direct call.
 325   return NewInst;
 326 }
 327
 328 #undef DEBUG_TYPE