InlineSimple.cpp revision 869adc283c0c15e46d9b18ca73628600f1c6c54e
1//===- InlineSimple.cpp - Code to perform simple function inlining --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements bottom-up inlining of functions into callees. 11// 12//===----------------------------------------------------------------------===// 13 14#include "Inliner.h" 15#include "llvm/Instructions.h" 16#include "llvm/Function.h" 17#include "llvm/Support/CallSite.h" 18#include "llvm/Transforms/IPO.h" 19using namespace llvm; 20 21namespace { 22 // FunctionInfo - For each function, calculate the size of it in blocks and 23 // instructions. 24 struct FunctionInfo { 25 // NumInsts, NumBlocks - Keep track of how large each function is, which is 26 // used to estimate the code size cost of inlining it. 27 unsigned NumInsts, NumBlocks; 28 29 // ConstantArgumentWeights - Each formal argument of the function is 30 // inspected to see if it is used in any contexts where making it a constant 31 // would reduce the code size. If so, we add some value to the argument 32 // entry here. 33 std::vector<unsigned> ConstantArgumentWeights; 34 35 FunctionInfo() : NumInsts(0), NumBlocks(0) {} 36 }; 37 38 class SimpleInliner : public Inliner { 39 std::map<const Function*, FunctionInfo> CachedFunctionInfo; 40 public: 41 int getInlineCost(CallSite CS); 42 }; 43 RegisterOpt<SimpleInliner> X("inline", "Function Integration/Inlining"); 44} 45 46Pass *llvm::createFunctionInliningPass() { return new SimpleInliner(); } 47 48// CountCodeReductionForConstant - Figure out an approximation for how many 49// instructions will be constant folded if the specified value is constant. 50// 51static unsigned CountCodeReductionForConstant(Value *V) { 52 unsigned Reduction = 0; 53 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 54 if (isa<BranchInst>(*UI)) 55 Reduction += 40; // Eliminating a conditional branch is a big win 56 else if (SwitchInst *SI = dyn_cast<SwitchInst>(*UI)) 57 // Eliminating a switch is a big win, proportional to the number of edges 58 // deleted. 59 Reduction += (SI->getNumSuccessors()-1) * 40; 60 else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 61 // Turning an indirect call into a direct call is a BIG win 62 Reduction += CI->getCalledValue() == V ? 500 : 0; 63 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 64 // Turning an indirect call into a direct call is a BIG win 65 Reduction += CI->getCalledValue() == V ? 500 : 0; 66 } else { 67 // Figure out if this instruction will be removed due to simple constant 68 // propagation. 69 Instruction &Inst = cast<Instruction>(**UI); 70 bool AllOperandsConstant = true; 71 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) 72 if (!isa<Constant>(Inst.getOperand(i)) && 73 !isa<GlobalValue>(Inst.getOperand(i)) && Inst.getOperand(i) != V) { 74 AllOperandsConstant = false; 75 break; 76 } 77 78 if (AllOperandsConstant) { 79 // We will get to remove this instruction... 80 Reduction += 7; 81 82 // And any other instructions that use it which become constants 83 // themselves. 84 Reduction += CountCodeReductionForConstant(&Inst); 85 } 86 } 87 88 return Reduction; 89} 90 91// getInlineCost - The heuristic used to determine if we should inline the 92// function call or not. 93// 94int SimpleInliner::getInlineCost(CallSite CS) { 95 Instruction *TheCall = CS.getInstruction(); 96 Function *Callee = CS.getCalledFunction(); 97 const Function *Caller = TheCall->getParent()->getParent(); 98 99 // Don't inline a directly recursive call. 100 if (Caller == Callee) return 2000000000; 101 102 // InlineCost - This value measures how good of an inline candidate this call 103 // site is to inline. A lower inline cost make is more likely for the call to 104 // be inlined. This value may go negative. 105 // 106 int InlineCost = 0; 107 108 // If there is only one call of the function, and it has internal linkage, 109 // make it almost guaranteed to be inlined. 110 // 111 if (Callee->hasInternalLinkage() && Callee->hasOneUse()) 112 InlineCost -= 30000; 113 114 // Get information about the callee... 115 FunctionInfo &CalleeFI = CachedFunctionInfo[Callee]; 116 117 // If we haven't calculated this information yet... 118 if (CalleeFI.NumBlocks == 0) { 119 unsigned NumInsts = 0, NumBlocks = 0; 120 121 // Look at the size of the callee. Each basic block counts as 20 units, and 122 // each instruction counts as 10. 123 for (Function::const_iterator BB = Callee->begin(), E = Callee->end(); 124 BB != E; ++BB) { 125 NumInsts += BB->size(); 126 NumBlocks++; 127 } 128 129 CalleeFI.NumBlocks = NumBlocks; 130 CalleeFI.NumInsts = NumInsts; 131 132 // Check out all of the arguments to the function, figuring out how much 133 // code can be eliminated if one of the arguments is a constant. 134 std::vector<unsigned> &ArgWeights = CalleeFI.ConstantArgumentWeights; 135 136 for (Function::aiterator I = Callee->abegin(), E = Callee->aend(); 137 I != E; ++I) 138 ArgWeights.push_back(CountCodeReductionForConstant(I)); 139 } 140 141 142 // Add to the inline quality for properties that make the call valuable to 143 // inline. This includes factors that indicate that the result of inlining 144 // the function will be optimizable. Currently this just looks at arguments 145 // passed into the function. 146 // 147 unsigned ArgNo = 0; 148 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 149 I != E; ++I, ++ArgNo) { 150 // Each argument passed in has a cost at both the caller and the callee 151 // sides. This favors functions that take many arguments over functions 152 // that take few arguments. 153 InlineCost -= 20; 154 155 // If this is a function being passed in, it is very likely that we will be 156 // able to turn an indirect function call into a direct function call. 157 if (isa<Function>(I)) 158 InlineCost -= 100; 159 160 // If an alloca is passed in, inlining this function is likely to allow 161 // significant future optimization possibilities (like scalar promotion, and 162 // scalarization), so encourage the inlining of the function. 163 // 164 else if (isa<AllocaInst>(I)) 165 InlineCost -= 60; 166 167 // If this is a constant being passed into the function, use the argument 168 // weights calculated for the callee to determine how much will be folded 169 // away with this information. 170 else if (isa<Constant>(I) || isa<GlobalVariable>(I)) { 171 if (ArgNo < CalleeFI.ConstantArgumentWeights.size()) 172 InlineCost -= CalleeFI.ConstantArgumentWeights[ArgNo]; 173 } 174 } 175 176 // Now that we have considered all of the factors that make the call site more 177 // likely to be inlined, look at factors that make us not want to inline it. 178 179 // Don't inline into something too big, which would make it bigger. Here, we 180 // count each basic block as a single unit. 181 InlineCost += Caller->size()*2; 182 183 184 // Look at the size of the callee. Each basic block counts as 20 units, and 185 // each instruction counts as 5. 186 InlineCost += CalleeFI.NumInsts*5 + CalleeFI.NumBlocks*20; 187 return InlineCost; 188} 189 190