lib/Transforms/IPO/InlineSimple.cpp

   1 //===- FunctionInlining.cpp - Code to perform function inlining -----------===//
   2 //
   3 // This file implements inlining of functions.
   4 //
   5 // Specifically, this:
   6 //   * Exports functionality to inline any function call
   7 //   * Inlines functions that consist of a single basic block
   8 //   * Is able to inline ANY function call
   9 //   . Has a smart heuristic for when to inline a function
  10 //
  11 // Notice that:
  12 //   * This pass opens up a lot of opportunities for constant propogation.  It
  13 //     is a good idea to to run a constant propogation pass, then a DCE pass
  14 //     sometime after running this pass.
  15 //
  16 // FIXME: This pass should transform alloca instructions in the called function
  17 //        into malloc/free pairs!
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Transforms/IPO.h"
  22 #include "llvm/Transforms/Utils/Cloning.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/iTerminators.h"
  26 #include "llvm/iPHINode.h"
  27 #include "llvm/iOther.h"
  28 #include "llvm/Type.h"
  29 #include "Support/Statistic.h"
  30 #include <algorithm>
  31
  32 static Statistic<> NumInlined("inline", "Number of functions inlined");
  33 using std::cerr;
  34
  35 // InlineFunction - This function forcibly inlines the called function into the
  36 // basic block of the caller.  This returns false if it is not possible to
  37 // inline this call.  The program is still in a well defined state if this
  38 // occurs though.
  39 //
  40 // Note that this only does one level of inlining.  For example, if the
  41 // instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
  42 // exists in the instruction stream.  Similiarly this will inline a recursive
  43 // function by one level.
  44 //
  45 bool InlineFunction(CallInst *CI) {
  46   assert(isa<CallInst>(CI) && "InlineFunction only works on CallInst nodes");
  47   assert(CI->getParent() && "Instruction not embedded in basic block!");
  48   assert(CI->getParent()->getParent() && "Instruction not in function!");
  49
  50   const Function *CalledFunc = CI->getCalledFunction();
  51   if (CalledFunc == 0 ||   // Can't inline external function or indirect call!
  52       CalledFunc->isExternal()) return false;
  53
  54   //cerr << "Inlining " << CalledFunc->getName() << " into "
  55   //     << CurrentMeth->getName() << "\n";
  56
  57   BasicBlock *OrigBB = CI->getParent();
  58
  59   // Call splitBasicBlock - The original basic block now ends at the instruction
  60   // immediately before the call.  The original basic block now ends with an
  61   // unconditional branch to NewBB, and NewBB starts with the call instruction.
  62   //
  63   BasicBlock *NewBB = OrigBB->splitBasicBlock(CI);
  64   NewBB->setName("InlinedFunctionReturnNode");
  65
  66   // Remove (unlink) the CallInst from the start of the new basic block.
  67   NewBB->getInstList().remove(CI);
  68
  69   // If we have a return value generated by this call, convert it into a PHI
  70   // node that gets values from each of the old RET instructions in the original
  71   // function.
  72   //
  73   PHINode *PHI = 0;
  74   if (!CI->use_empty()) {
  75     // The PHI node should go at the front of the new basic block to merge all
  76     // possible incoming values.
  77     //
  78     PHI = new PHINode(CalledFunc->getReturnType(), CI->getName(),
  79                       NewBB->begin());
  80
  81     // Anything that used the result of the function call should now use the PHI
  82     // node as their operand.
  83     //
  84     CI->replaceAllUsesWith(PHI);
  85   }
  86
  87   // Get a pointer to the last basic block in the function, which will have the
  88   // new function inlined after it.
  89   //
  90   Function::iterator LastBlock = &OrigBB->getParent()->back();
  91
  92   // Calculate the vector of arguments to pass into the function cloner...
  93   std::map<const Value*, Value*> ValueMap;
  94   assert((unsigned)std::distance(CalledFunc->abegin(), CalledFunc->aend()) ==
  95          CI->getNumOperands()-1 && "No varargs calls can be inlined yet!");
  96
  97   unsigned i = 1;
  98   for (Function::const_aiterator I = CalledFunc->abegin(), E=CalledFunc->aend();
  99        I != E; ++I, ++i)
 100     ValueMap[I] = CI->getOperand(i);
 101
 102   // Since we are now done with the CallInst, we can delete it.
 103   delete CI;
 104
 105   // Make a vector to capture the return instructions in the cloned function...
 106   std::vector<ReturnInst*> Returns;
 107
 108   // Do all of the hard part of cloning the callee into the caller...
 109   CloneFunctionInto(OrigBB->getParent(), CalledFunc, ValueMap, Returns, ".i");
 110
 111   // Loop over all of the return instructions, turning them into unconditional
 112   // branches to the merge point now...
 113   for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
 114     ReturnInst *RI = Returns[i];
 115     BasicBlock *BB = RI->getParent();
 116
 117     // Add a branch to the merge point where the PHI node would live...
 118     new BranchInst(NewBB, RI);
 119
 120     if (PHI) {   // The PHI node should include this value!
 121       assert(RI->getReturnValue() && "Ret should have value!");
 122       assert(RI->getReturnValue()->getType() == PHI->getType() &&
 123              "Ret value not consistent in function!");
 124       PHI->addIncoming(RI->getReturnValue(), BB);
 125     }
 126
 127     // Delete the return instruction now
 128     BB->getInstList().erase(RI);
 129   }
 130
 131   // Check to see if the PHI node only has one argument.  This is a common
 132   // case resulting from there only being a single return instruction in the
 133   // function call.  Because this is so common, eliminate the PHI node.
 134   //
 135   if (PHI && PHI->getNumIncomingValues() == 1) {
 136     PHI->replaceAllUsesWith(PHI->getIncomingValue(0));
 137     PHI->getParent()->getInstList().erase(PHI);
 138   }
 139
 140   // Change the branch that used to go to NewBB to branch to the first basic
 141   // block of the inlined function.
 142   //
 143   TerminatorInst *Br = OrigBB->getTerminator();
 144   assert(Br && Br->getOpcode() == Instruction::Br &&
 145          "splitBasicBlock broken!");
 146   Br->setOperand(0, ++LastBlock);
 147   return true;
 148 }
 149
 150 static inline bool ShouldInlineFunction(const CallInst *CI, const Function *F) {
 151   assert(CI->getParent() && CI->getParent()->getParent() &&
 152          "Call not embedded into a function!");
 153
 154   // Don't inline a recursive call.
 155   if (CI->getParent()->getParent() == F) return false;
 156
 157   // Don't inline something too big.  This is a really crappy heuristic
 158   if (F->size() > 3) return false;
 159
 160   // Don't inline into something too big. This is a **really** crappy heuristic
 161   if (CI->getParent()->getParent()->size() > 10) return false;
 162
 163   // Go ahead and try just about anything else.
 164   return true;
 165 }
 166
 167
 168 static inline bool DoFunctionInlining(BasicBlock *BB) {
 169   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
 170     if (CallInst *CI = dyn_cast<CallInst>(&*I)) {
 171       // Check to see if we should inline this function
 172       Function *F = CI->getCalledFunction();
 173       if (F && ShouldInlineFunction(CI, F)) {
 174         return InlineFunction(CI);
 175       }
 176     }
 177   }
 178   return false;
 179 }
 180
 181 // doFunctionInlining - Use a heuristic based approach to inline functions that
 182 // seem to look good.
 183 //
 184 static bool doFunctionInlining(Function &F) {
 185   bool Changed = false;
 186
 187   // Loop through now and inline instructions a basic block at a time...
 188   for (Function::iterator I = F.begin(); I != F.end(); )
 189     if (DoFunctionInlining(I)) {
 190       ++NumInlined;
 191       Changed = true;
 192     } else {
 193       ++I;
 194     }
 195
 196   return Changed;
 197 }
 198
 199 namespace {
 200   struct FunctionInlining : public FunctionPass {
 201     virtual bool runOnFunction(Function &F) {
 202       return doFunctionInlining(F);
 203     }
 204   };
 205   RegisterOpt<FunctionInlining> X("inline", "Function Integration/Inlining");
 206 }
 207
 208 Pass *createFunctionInliningPass() { return new FunctionInlining(); }