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 be coming from the "merge" block. For example, in the code
  27 /// below:
  28 ///
  29 ///   then_bb:
  30 ///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
  31 ///
  32 ///   else_bb:
  33 ///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
  34 ///
  35 ///   merge_bb:
  36 ///     %t2 = phi i32 [ %t0, %then_bb ], [ %t1, %else_bb ]
  37 ///     br %normal_dst
  38 ///
  39 ///   normal_dst:
  40 ///     %t3 = phi i32 [ %x, %orig_bb ], ...
  41 ///
  42 /// "orig_bb" is no longer a predecessor of "normal_dst", so the phi nodes in
  43 /// "normal_dst" must be fixed to refer to "merge_bb":
  44 ///
  45 ///    normal_dst:
  46 ///      %t3 = phi i32 [ %x, %merge_bb ], ...
  47 ///
  48 static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
  49                                       BasicBlock *MergeBlock) {
  50   for (auto &I : *Invoke->getNormalDest()) {
  51     auto *Phi = dyn_cast<PHINode>(&I);
  52     if (!Phi)
  53       break;
  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 (auto &I : *Invoke->getUnwindDest()) {
  86     auto *Phi = dyn_cast<PHINode>(&I);
  87     if (!Phi)
  88       break;
  89     int Idx = Phi->getBasicBlockIndex(OrigBlock);
  90     if (Idx == -1)
  91       continue;
  92     auto *V = Phi->getIncomingValue(Idx);
  93     Phi->setIncomingBlock(Idx, ThenBlock);
  94     Phi->addIncoming(V, ElseBlock);
  95   }
  96 }
  97
  98 /// Create a phi node for the returned value of a call or invoke instruction.
  99 ///
 100 /// After versioning a call or invoke instruction that returns a value, we have
 101 /// to merge the value of the original and new instructions. We do this by
 102 /// creating a phi node and replacing uses of the original instruction with this
 103 /// phi node.
 104 ///
 105 /// For example, if \p OrigInst is defined in "else_bb" and \p NewInst is
 106 /// defined in "then_bb", we create the following phi node:
 107 ///
 108 ///   ; Uses of the original instruction are replaced by uses of the phi node.
 109 ///   %t0 = phi i32 [ %orig_inst, %else_bb ], [ %new_inst, %then_bb ],
 110 ///
 111 static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst,
 112                              BasicBlock *MergeBlock, IRBuilder<> &Builder) {
 113
 114   if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
 115     return;
 116
 117   Builder.SetInsertPoint(&MergeBlock->front());
 118   PHINode *Phi = Builder.CreatePHI(OrigInst->getType(), 0);
 119   SmallVector<User *, 16> UsersToUpdate;
 120   for (User *U : OrigInst->users())
 121     UsersToUpdate.push_back(U);
 122   for (User *U : UsersToUpdate)
 123     U->replaceUsesOfWith(OrigInst, Phi);
 124   Phi->addIncoming(OrigInst, OrigInst->getParent());
 125   Phi->addIncoming(NewInst, NewInst->getParent());
 126 }
 127
 128 /// Cast a call or invoke instruction to the given type.
 129 ///
 130 /// When promoting a call site, the return type of the call site might not match
 131 /// that of the callee. If this is the case, we have to cast the returned value
 132 /// to the correct type. The location of the cast depends on if we have a call
 133 /// or invoke instruction.
 134 ///
 135 /// For example, if the call instruction below requires a bitcast after
 136 /// promotion:
 137 ///
 138 ///   orig_bb:
 139 ///     %t0 = call i32 @func()
 140 ///     ...
 141 ///
 142 /// The bitcast is placed after the call instruction:
 143 ///
 144 ///   orig_bb:
 145 ///     ; Uses of the original return value are replaced by uses of the bitcast.
 146 ///     %t0 = call i32 @func()
 147 ///     %t1 = bitcast i32 %t0 to ...
 148 ///     ...
 149 ///
 150 /// A similar transformation is performed for invoke instructions. However,
 151 /// since invokes are terminating, a new block is created for the bitcast. For
 152 /// example, if the invoke instruction below requires a bitcast after promotion:
 153 ///
 154 ///   orig_bb:
 155 ///     %t0 = invoke i32 @func() to label %normal_dst unwind label %unwind_dst
 156 ///
 157 /// The edge between the original block and the invoke's normal destination is
 158 /// split, and the bitcast is placed there:
 159 ///
 160 ///   orig_bb:
 161 ///     %t0 = invoke i32 @func() to label %split_bb unwind label %unwind_dst
 162 ///
 163 ///   split_bb:
 164 ///     ; Uses of the original return value are replaced by uses of the bitcast.
 165 ///     %t1 = bitcast i32 %t0 to ...
 166 ///     br label %normal_dst
 167 ///
 168 static void createRetBitCast(CallSite CS, Type *RetTy, CastInst **RetBitCast) {
 169
 170   // Save the users of the calling instruction. These uses will be changed to
 171   // use the bitcast after we create it.
 172   SmallVector<User *, 16> UsersToUpdate;
 173   for (User *U : CS.getInstruction()->users())
 174     UsersToUpdate.push_back(U);
 175
 176   // Determine an appropriate location to create the bitcast for the return
 177   // value. The location depends on if we have a call or invoke instruction.
 178   Instruction *InsertBefore = nullptr;
 179   if (auto *Invoke = dyn_cast<InvokeInst>(CS.getInstruction()))
 180     InsertBefore =
 181         &SplitEdge(Invoke->getParent(), Invoke->getNormalDest())->front();
 182   else
 183     InsertBefore = &*std::next(CS.getInstruction()->getIterator());
 184
 185   // Bitcast the return value to the correct type.
 186   auto *Cast = CastInst::Create(Instruction::BitCast, CS.getInstruction(),
 187                                 RetTy, "", InsertBefore);
 188   if (RetBitCast)
 189     *RetBitCast = Cast;
 190
 191   // Replace all the original uses of the calling instruction with the bitcast.
 192   for (User *U : UsersToUpdate)
 193     U->replaceUsesOfWith(CS.getInstruction(), Cast);
 194 }
 195
 196 /// Predicate and clone the given call site.
 197 ///
 198 /// This function creates an if-then-else structure at the location of the call
 199 /// site. The "if" condition compares the call site's called value to the given
 200 /// callee. The original call site is moved into the "else" block, and a clone
 201 /// of the call site is placed in the "then" block. The cloned instruction is
 202 /// returned.
 203 ///
 204 /// For example, the call instruction below:
 205 ///
 206 ///   orig_bb:
 207 ///     %t0 = call i32 %ptr()
 208 ///     ...
 209 ///
 210 /// Is replace by the following:
 211 ///
 212 ///   orig_bb:
 213 ///     %cond = icmp eq i32 ()* %ptr, @func
 214 ///     br i1 %cond, %then_bb, %else_bb
 215 ///
 216 ///   then_bb:
 217 ///     ; The clone of the original call instruction is placed in the "then"
 218 ///     ; block. It is not yet promoted.
 219 ///     %t1 = call i32 %ptr()
 220 ///     br merge_bb
 221 ///
 222 ///   else_bb:
 223 ///     ; The original call instruction is moved to the "else" block.
 224 ///     %t0 = call i32 %ptr()
 225 ///     br merge_bb
 226 ///
 227 ///   merge_bb:
 228 ///     ; Uses of the original call instruction are replaced by uses of the phi
 229 ///     ; node.
 230 ///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
 231 ///     ...
 232 ///
 233 /// A similar transformation is performed for invoke instructions. However,
 234 /// since invokes are terminating, more work is required. For example, the
 235 /// invoke instruction below:
 236 ///
 237 ///   orig_bb:
 238 ///     %t0 = invoke %ptr() to label %normal_dst unwind label %unwind_dst
 239 ///
 240 /// Is replace by the following:
 241 ///
 242 ///   orig_bb:
 243 ///     %cond = icmp eq i32 ()* %ptr, @func
 244 ///     br i1 %cond, %then_bb, %else_bb
 245 ///
 246 ///   then_bb:
 247 ///     ; The clone of the original invoke instruction is placed in the "then"
 248 ///     ; block, and its normal destination is set to the "merge" block. It is
 249 ///     ; not yet promoted.
 250 ///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
 251 ///
 252 ///   else_bb:
 253 ///     ; The original invoke instruction is moved into the "else" block, and
 254 ///     ; its normal destination is set to the "merge" block.
 255 ///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
 256 ///
 257 ///   merge_bb:
 258 ///     ; Uses of the original invoke instruction are replaced by uses of the
 259 ///     ; phi node, and the merge block branches to the normal destination.
 260 ///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
 261 ///     br %normal_dst
 262 ///
 263 static Instruction *versionCallSite(CallSite CS, Value *Callee,
 264                                     MDNode *BranchWeights) {
 265
 266   IRBuilder<> Builder(CS.getInstruction());
 267   Instruction *OrigInst = CS.getInstruction();
 268   BasicBlock *OrigBlock = OrigInst->getParent();
 269
 270   // Create the compare. The called value and callee must have the same type to
 271   // be compared.
 272   if (CS.getCalledValue()->getType() != Callee->getType())
 273     Callee = Builder.CreateBitCast(Callee, CS.getCalledValue()->getType());
 274   auto *Cond = Builder.CreateICmpEQ(CS.getCalledValue(), Callee);
 275
 276   // Create an if-then-else structure. The original instruction is moved into
 277   // the "else" block, and a clone of the original instruction is placed in the
 278   // "then" block.
 279   TerminatorInst *ThenTerm = nullptr;
 280   TerminatorInst *ElseTerm = nullptr;
 281   SplitBlockAndInsertIfThenElse(Cond, CS.getInstruction(), &ThenTerm, &ElseTerm,
 282                                 BranchWeights);
 283   BasicBlock *ThenBlock = ThenTerm->getParent();
 284   BasicBlock *ElseBlock = ElseTerm->getParent();
 285   BasicBlock *MergeBlock = OrigInst->getParent();
 286
 287   ThenBlock->setName("if.true.direct_targ");
 288   ElseBlock->setName("if.false.orig_indirect");
 289   MergeBlock->setName("if.end.icp");
 290
 291   Instruction *NewInst = OrigInst->clone();
 292   OrigInst->moveBefore(ElseTerm);
 293   NewInst->insertBefore(ThenTerm);
 294
 295   // If the original call site is an invoke instruction, we have extra work to
 296   // do since invoke instructions are terminating. We have to fix-up phi nodes
 297   // in the invoke's normal and unwind destinations.
 298   if (auto *OrigInvoke = dyn_cast<InvokeInst>(OrigInst)) {
 299     auto *NewInvoke = cast<InvokeInst>(NewInst);
 300
 301     // Invoke instructions are terminating, so we don't need the terminator
 302     // instructions that were just created.
 303     ThenTerm->eraseFromParent();
 304     ElseTerm->eraseFromParent();
 305
 306     // Branch from the "merge" block to the original normal destination.
 307     Builder.SetInsertPoint(MergeBlock);
 308     Builder.CreateBr(OrigInvoke->getNormalDest());
 309
 310     // Fix-up phi nodes in the original invoke's normal and unwind destinations.
 311     fixupPHINodeForNormalDest(OrigInvoke, OrigBlock, MergeBlock);
 312     fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
 313
 314     // Now set the normal destinations of the invoke instructions to be the
 315     // "merge" block.
 316     OrigInvoke->setNormalDest(MergeBlock);
 317     NewInvoke->setNormalDest(MergeBlock);
 318   }
 319
 320   // Create a phi node for the returned value of the call site.
 321   createRetPHINode(OrigInst, NewInst, MergeBlock, Builder);
 322
 323   return NewInst;
 324 }
 325
 326 bool llvm::isLegalToPromote(CallSite CS, Function *Callee,
 327                             const char **FailureReason) {
 328   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 329
 330   // Check the return type. The callee's return value type must be bitcast
 331   // compatible with the call site's type.
 332   Type *CallRetTy = CS.getInstruction()->getType();
 333   Type *FuncRetTy = Callee->getReturnType();
 334   if (CallRetTy != FuncRetTy)
 335     if (!CastInst::isBitCastable(FuncRetTy, CallRetTy)) {
 336       if (FailureReason)
 337         *FailureReason = "Return type mismatch";
 338       return false;
 339     }
 340
 341   // The number of formal arguments of the callee.
 342   unsigned NumParams = Callee->getFunctionType()->getNumParams();
 343
 344   // Check the number of arguments. The callee and call site must agree on the
 345   // number of arguments.
 346   if (CS.arg_size() != NumParams && !Callee->isVarArg()) {
 347     if (FailureReason)
 348       *FailureReason = "The number of arguments mismatch";
 349     return false;
 350   }
 351
 352   // Check the argument types. The callee's formal argument types must be
 353   // bitcast compatible with the corresponding actual argument types of the call
 354   // site.
 355   for (unsigned I = 0; I < NumParams; ++I) {
 356     Type *FormalTy = Callee->getFunctionType()->getFunctionParamType(I);
 357     Type *ActualTy = CS.getArgument(I)->getType();
 358     if (FormalTy == ActualTy)
 359       continue;
 360     if (!CastInst::isBitCastable(ActualTy, FormalTy)) {
 361       if (FailureReason)
 362         *FailureReason = "Argument type mismatch";
 363       return false;
 364     }
 365   }
 366
 367   return true;
 368 }
 369
 370 Instruction *llvm::promoteCall(CallSite CS, Function *Callee,
 371                                CastInst **RetBitCast) {
 372   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 373
 374   // Set the called function of the call site to be the given callee.
 375   CS.setCalledFunction(Callee);
 376
 377   // Since the call site will no longer be direct, we must clear metadata that
 378   // is only appropriate for indirect calls. This includes !prof and !callees
 379   // metadata.
 380   CS.getInstruction()->setMetadata(LLVMContext::MD_prof, nullptr);
 381   CS.getInstruction()->setMetadata(LLVMContext::MD_callees, nullptr);
 382
 383   // If the function type of the call site matches that of the callee, no
 384   // additional work is required.
 385   if (CS.getFunctionType() == Callee->getFunctionType())
 386     return CS.getInstruction();
 387
 388   // Save the return types of the call site and callee.
 389   Type *CallSiteRetTy = CS.getInstruction()->getType();
 390   Type *CalleeRetTy = Callee->getReturnType();
 391
 392   // Change the function type of the call site the match that of the callee.
 393   CS.mutateFunctionType(Callee->getFunctionType());
 394
 395   // Inspect the arguments of the call site. If an argument's type doesn't
 396   // match the corresponding formal argument's type in the callee, bitcast it
 397   // to the correct type.
 398   for (Use &U : CS.args()) {
 399     unsigned ArgNo = CS.getArgumentNo(&U);
 400     Type *FormalTy = Callee->getFunctionType()->getParamType(ArgNo);
 401     Type *ActualTy = U.get()->getType();
 402     if (FormalTy != ActualTy) {
 403       auto *Cast = CastInst::Create(Instruction::BitCast, U.get(), FormalTy, "",
 404                                     CS.getInstruction());
 405       CS.setArgument(ArgNo, Cast);
 406     }
 407   }
 408
 409   // If the return type of the call site doesn't match that of the callee, cast
 410   // the returned value to the appropriate type.
 411   if (!CallSiteRetTy->isVoidTy() && CallSiteRetTy != CalleeRetTy)
 412     createRetBitCast(CS, CallSiteRetTy, RetBitCast);
 413
 414   return CS.getInstruction();
 415 }
 416
 417 Instruction *llvm::promoteCallWithIfThenElse(CallSite CS, Function *Callee,
 418                                              MDNode *BranchWeights) {
 419
 420   // Version the indirect call site. If the called value is equal to the given
 421   // callee, 'NewInst' will be executed, otherwise the original call site will
 422   // be executed.
 423   Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights);
 424
 425   // Promote 'NewInst' so that it directly calls the desired function.
 426   return promoteCall(CallSite(NewInst), Callee);
 427 }
 428
 429 #undef DEBUG_TYPE