InlineSimple.cpp revision 869adc283c0c15e46d9b18ca73628600f1c6c54e
1237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner//===- InlineSimple.cpp - Code to perform simple function inlining --------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 10ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// This file implements bottom-up inlining of functions into callees. 110154505ab74e7bd0d4dc85dbddc1ff0df6357606Chris Lattner// 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 13009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 14237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "Inliner.h" 15869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner#include "llvm/Instructions.h" 16237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Function.h" 17e54453387486c1d5e61401e1d4febd3f6ebe86cfChris Lattner#include "llvm/Support/CallSite.h" 18237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner#include "llvm/Transforms/IPO.h" 19869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattnerusing namespace llvm; 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 21ca398dc3989d35e8516489fd163e012133bd41cbChris Lattnernamespace { 22884d6c4e10501116a8ff45616231564a2738daddChris Lattner // FunctionInfo - For each function, calculate the size of it in blocks and 23884d6c4e10501116a8ff45616231564a2738daddChris Lattner // instructions. 24884d6c4e10501116a8ff45616231564a2738daddChris Lattner struct FunctionInfo { 25869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // NumInsts, NumBlocks - Keep track of how large each function is, which is 26869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // used to estimate the code size cost of inlining it. 27884d6c4e10501116a8ff45616231564a2738daddChris Lattner unsigned NumInsts, NumBlocks; 28884d6c4e10501116a8ff45616231564a2738daddChris Lattner 29869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // ConstantArgumentWeights - Each formal argument of the function is 30869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // inspected to see if it is used in any contexts where making it a constant 31869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // would reduce the code size. If so, we add some value to the argument 32869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // entry here. 33869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner std::vector<unsigned> ConstantArgumentWeights; 34869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 35884d6c4e10501116a8ff45616231564a2738daddChris Lattner FunctionInfo() : NumInsts(0), NumBlocks(0) {} 36884d6c4e10501116a8ff45616231564a2738daddChris Lattner }; 37884d6c4e10501116a8ff45616231564a2738daddChris Lattner 38884d6c4e10501116a8ff45616231564a2738daddChris Lattner class SimpleInliner : public Inliner { 39884d6c4e10501116a8ff45616231564a2738daddChris Lattner std::map<const Function*, FunctionInfo> CachedFunctionInfo; 40884d6c4e10501116a8ff45616231564a2738daddChris Lattner public: 41237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner int getInlineCost(CallSite CS); 42ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner }; 43237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner RegisterOpt<SimpleInliner> X("inline", "Function Integration/Inlining"); 44ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner} 45ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 46869adc283c0c15e46d9b18ca73628600f1c6c54eChris LattnerPass *llvm::createFunctionInliningPass() { return new SimpleInliner(); } 47869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 48869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner// CountCodeReductionForConstant - Figure out an approximation for how many 49869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner// instructions will be constant folded if the specified value is constant. 50869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner// 51869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattnerstatic unsigned CountCodeReductionForConstant(Value *V) { 52869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner unsigned Reduction = 0; 53869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 54869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner if (isa<BranchInst>(*UI)) 55869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += 40; // Eliminating a conditional branch is a big win 56869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner else if (SwitchInst *SI = dyn_cast<SwitchInst>(*UI)) 57869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Eliminating a switch is a big win, proportional to the number of edges 58869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // deleted. 59869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += (SI->getNumSuccessors()-1) * 40; 60869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 61869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Turning an indirect call into a direct call is a BIG win 62869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += CI->getCalledValue() == V ? 500 : 0; 63869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 64869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Turning an indirect call into a direct call is a BIG win 65869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += CI->getCalledValue() == V ? 500 : 0; 66869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } else { 67869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Figure out if this instruction will be removed due to simple constant 68869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // propagation. 69869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Instruction &Inst = cast<Instruction>(**UI); 70869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner bool AllOperandsConstant = true; 71869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) 72869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner if (!isa<Constant>(Inst.getOperand(i)) && 73869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner !isa<GlobalValue>(Inst.getOperand(i)) && Inst.getOperand(i) != V) { 74869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner AllOperandsConstant = false; 75869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner break; 76869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 77869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 78869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner if (AllOperandsConstant) { 79869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // We will get to remove this instruction... 80869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += 7; 81869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 82869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // And any other instructions that use it which become constants 83869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // themselves. 84869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Reduction += CountCodeReductionForConstant(&Inst); 85869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 86869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 87869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 88869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner return Reduction; 89869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner} 90009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 91237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// getInlineCost - The heuristic used to determine if we should inline the 92237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner// function call or not. 93ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner// 94237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattnerint SimpleInliner::getInlineCost(CallSite CS) { 95e54453387486c1d5e61401e1d4febd3f6ebe86cfChris Lattner Instruction *TheCall = CS.getInstruction(); 96869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner Function *Callee = CS.getCalledFunction(); 97e54453387486c1d5e61401e1d4febd3f6ebe86cfChris Lattner const Function *Caller = TheCall->getParent()->getParent(); 98009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 99237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // Don't inline a directly recursive call. 100237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner if (Caller == Callee) return 2000000000; 101237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner 102237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // InlineCost - This value measures how good of an inline candidate this call 103237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // site is to inline. A lower inline cost make is more likely for the call to 104237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner // be inlined. This value may go negative. 105009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // 106237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner int InlineCost = 0; 107009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 108ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // If there is only one call of the function, and it has internal linkage, 109ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // make it almost guaranteed to be inlined. 110009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // 111bacc773d207700dede0701d08e15dfdc650678e9Chris Lattner if (Callee->hasInternalLinkage() && Callee->hasOneUse()) 112237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineCost -= 30000; 113009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 114869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Get information about the callee... 115869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner FunctionInfo &CalleeFI = CachedFunctionInfo[Callee]; 116869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 117869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // If we haven't calculated this information yet... 118869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner if (CalleeFI.NumBlocks == 0) { 119869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner unsigned NumInsts = 0, NumBlocks = 0; 120869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 121869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Look at the size of the callee. Each basic block counts as 20 units, and 122869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // each instruction counts as 10. 123869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner for (Function::const_iterator BB = Callee->begin(), E = Callee->end(); 124869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner BB != E; ++BB) { 125869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner NumInsts += BB->size(); 126869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner NumBlocks++; 127869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 128869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 129869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner CalleeFI.NumBlocks = NumBlocks; 130869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner CalleeFI.NumInsts = NumInsts; 131869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 132869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // Check out all of the arguments to the function, figuring out how much 133869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // code can be eliminated if one of the arguments is a constant. 134869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner std::vector<unsigned> &ArgWeights = CalleeFI.ConstantArgumentWeights; 135869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 136869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner for (Function::aiterator I = Callee->abegin(), E = Callee->aend(); 137869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner I != E; ++I) 138869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner ArgWeights.push_back(CountCodeReductionForConstant(I)); 139869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 140869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 141869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 142cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Add to the inline quality for properties that make the call valuable to 143ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // inline. This includes factors that indicate that the result of inlining 144ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // the function will be optimizable. Currently this just looks at arguments 145ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // passed into the function. 146ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // 147869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner unsigned ArgNo = 0; 148e54453387486c1d5e61401e1d4febd3f6ebe86cfChris Lattner for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 149869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner I != E; ++I, ++ArgNo) { 150ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // Each argument passed in has a cost at both the caller and the callee 151ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // sides. This favors functions that take many arguments over functions 152ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // that take few arguments. 153237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineCost -= 20; 154ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 155ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // If this is a function being passed in, it is very likely that we will be 156ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // able to turn an indirect function call into a direct function call. 157ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner if (isa<Function>(I)) 158237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineCost -= 100; 159ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner 160869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // If an alloca is passed in, inlining this function is likely to allow 161869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // significant future optimization possibilities (like scalar promotion, and 162869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // scalarization), so encourage the inlining of the function. 163009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // 164869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner else if (isa<AllocaInst>(I)) 165237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner InlineCost -= 60; 166869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner 167869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // If this is a constant being passed into the function, use the argument 168869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // weights calculated for the callee to determine how much will be folded 169869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // away with this information. 170869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner else if (isa<Constant>(I) || isa<GlobalVariable>(I)) { 171869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner if (ArgNo < CalleeFI.ConstantArgumentWeights.size()) 172869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner InlineCost -= CalleeFI.ConstantArgumentWeights[ArgNo]; 173869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner } 174009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner } 175009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 176ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // Now that we have considered all of the factors that make the call site more 177ca398dc3989d35e8516489fd163e012133bd41cbChris Lattner // likely to be inlined, look at factors that make us not want to inline it. 178009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 179da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner // Don't inline into something too big, which would make it bigger. Here, we 180da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner // count each basic block as a single unit. 181da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner InlineCost += Caller->size()*2; 182da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner 183da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner 184da78b002ca6bdaf9fd58443d943f60b8529bcf36Chris Lattner // Look at the size of the callee. Each basic block counts as 20 units, and 185869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner // each instruction counts as 5. 186869adc283c0c15e46d9b18ca73628600f1c6c54eChris Lattner InlineCost += CalleeFI.NumInsts*5 + CalleeFI.NumBlocks*20; 187237ef567f6764f24a47c63121cc0a599ddc8f56dChris Lattner return InlineCost; 188009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 189d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 190