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::vector<Value*> ArgVector;
  94   for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
  95     ArgVector.push_back(CI->getOperand(i));
  96
  97   // Since we are now done with the CallInst, we can delete it.
  98   delete CI;
  99
 100   // Make a vector to capture the return instructions in the cloned function...
 101   std::vector<ReturnInst*> Returns;
 102
 103   // Do all of the hard part of cloning the callee into the caller...
 104   CloneFunctionInto(OrigBB->getParent(), CalledFunc, ArgVector, Returns, ".i");
 105
 106   // Loop over all of the return instructions, turning them into unconditional
 107   // branches to the merge point now...
 108   for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
 109     ReturnInst *RI = Returns[i];
 110     BasicBlock *BB = RI->getParent();
 111
 112     // Add a branch to the merge point where the PHI node would live...
 113     new BranchInst(NewBB, RI);
 114
 115     if (PHI) {   // The PHI node should include this value!
 116       assert(RI->getReturnValue() && "Ret should have value!");
 117       assert(RI->getReturnValue()->getType() == PHI->getType() &&
 118              "Ret value not consistent in function!");
 119       PHI->addIncoming(RI->getReturnValue(), BB);
 120     }
 121
 122     // Delete the return instruction now
 123     BB->getInstList().erase(RI);
 124   }
 125
 126   // Check to see if the PHI node only has one argument.  This is a common
 127   // case resulting from there only being a single return instruction in the
 128   // function call.  Because this is so common, eliminate the PHI node.
 129   //
 130   if (PHI && PHI->getNumIncomingValues() == 1) {
 131     PHI->replaceAllUsesWith(PHI->getIncomingValue(0));
 132     PHI->getParent()->getInstList().erase(PHI);
 133   }
 134
 135   // Change the branch that used to go to NewBB to branch to the first basic
 136   // block of the inlined function.
 137   //
 138   TerminatorInst *Br = OrigBB->getTerminator();
 139   assert(Br && Br->getOpcode() == Instruction::Br &&
 140          "splitBasicBlock broken!");
 141   Br->setOperand(0, ++LastBlock);
 142   return true;
 143 }
 144
 145 static inline bool ShouldInlineFunction(const CallInst *CI, const Function *F) {
 146   assert(CI->getParent() && CI->getParent()->getParent() &&
 147          "Call not embedded into a function!");
 148
 149   // Don't inline a recursive call.
 150   if (CI->getParent()->getParent() == F) return false;
 151
 152   // Don't inline something too big.  This is a really crappy heuristic
 153   if (F->size() > 3) return false;
 154
 155   // Don't inline into something too big. This is a **really** crappy heuristic
 156   if (CI->getParent()->getParent()->size() > 10) return false;
 157
 158   // Go ahead and try just about anything else.
 159   return true;
 160 }
 161
 162
 163 static inline bool DoFunctionInlining(BasicBlock *BB) {
 164   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
 165     if (CallInst *CI = dyn_cast<CallInst>(&*I)) {
 166       // Check to see if we should inline this function
 167       Function *F = CI->getCalledFunction();
 168       if (F && ShouldInlineFunction(CI, F)) {
 169         return InlineFunction(CI);
 170       }
 171     }
 172   }
 173   return false;
 174 }
 175
 176 // doFunctionInlining - Use a heuristic based approach to inline functions that
 177 // seem to look good.
 178 //
 179 static bool doFunctionInlining(Function &F) {
 180   bool Changed = false;
 181
 182   // Loop through now and inline instructions a basic block at a time...
 183   for (Function::iterator I = F.begin(); I != F.end(); )
 184     if (DoFunctionInlining(I)) {
 185       ++NumInlined;
 186       Changed = true;
 187     } else {
 188       ++I;
 189     }
 190
 191   return Changed;
 192 }
 193
 194 namespace {
 195   struct FunctionInlining : public FunctionPass {
 196     virtual bool runOnFunction(Function &F) {
 197       return doFunctionInlining(F);
 198     }
 199   };
 200   RegisterOpt<FunctionInlining> X("inline", "Function Integration/Inlining");
 201 }
 202
 203 Pass *createFunctionInliningPass() { return new FunctionInlining(); }