170745c661de12e3e5b7892776b190f2db703509bChris Lattner//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 26899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// 36899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// The LLVM Compiler Infrastructure 46899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// 86899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel//===----------------------------------------------------------------------===// 96899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// 1058ca8d55d4ad9d277f251c4c85fb6db30d96bfc7Dan Gohman// This file implements heuristics for inlining decisions. 116899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel// 126899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel//===----------------------------------------------------------------------===// 136899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel 14e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#ifndef LLVM_ANALYSIS_INLINECOST_H 15e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#define LLVM_ANALYSIS_INLINECOST_H 166899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel 1786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth#include "llvm/Analysis/CallGraphSCCPass.h" 18066b5d8403483bf3a8bb033b690da318fbc68e79Benjamin Kramer#include <cassert> 19066b5d8403483bf3a8bb033b690da318fbc68e79Benjamin Kramer#include <climits> 206899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel 216899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patelnamespace llvm { 224ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthclass CallSite; 234ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthclass DataLayout; 244ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthclass Function; 258d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruthclass TargetTransformInfo; 264ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 274ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthnamespace InlineConstants { 284ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth // Various magic constants used to adjust heuristics. 294ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int InstrCost = 5; 304ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int IndirectCallThreshold = 100; 314ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int CallPenalty = 25; 324ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int LastCallToStaticBonus = -15000; 334ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int ColdccPenalty = 2000; 344ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int NoreturnPenalty = 10000; 354ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// Do not inline functions which allocate this many bytes on the stack 364ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// when the caller is recursive. 374ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const unsigned TotalAllocaSizeRecursiveCaller = 1024; 384ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth} 394ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 404ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// \brief Represents the cost of inlining a function. 414ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// 424ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// This supports special values for functions which should "always" or 434ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// "never" be inlined. Otherwise, the cost represents a unitless amount; 444ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// smaller values increase the likelihood of the function being inlined. 454ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// 464ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// Objects of this type also provide the adjusted threshold for inlining 474ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// based on the information available for a particular callsite. They can be 484ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// directly tested to determine if inlining should occur given the cost and 494ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth/// threshold for this cost metric. 504ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthclass InlineCost { 514ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth enum SentinelValues { 524ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth AlwaysInlineCost = INT_MIN, 534ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth NeverInlineCost = INT_MAX 544ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth }; 554ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 564ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief The estimated cost of inlining this callsite. 574ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int Cost; 584ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 594ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief The adjusted threshold against which this cost was computed. 604ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth const int Threshold; 616899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel 624ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth // Trivial constructor, interesting logic in the factory functions below. 634ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} 644ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 654ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthpublic: 664ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth static InlineCost get(int Cost, int Threshold) { 674ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 684ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 694ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth return InlineCost(Cost, Threshold); 704ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth } 714ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth static InlineCost getAlways() { 724ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth return InlineCost(AlwaysInlineCost, 0); 734ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth } 744ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth static InlineCost getNever() { 754ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth return InlineCost(NeverInlineCost, 0); 76bdb984bc2757114bc706026603ed40d7f508c4c1Dale Johannesen } 77bdb984bc2757114bc706026603ed40d7f508c4c1Dale Johannesen 784ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Test whether the inline cost is low enough for inlining. 79453f4f01302f00651aae2fc7658f6e23a2beadb0David Blaikie LLVM_EXPLICIT operator bool() const { 804ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth return Cost < Threshold; 814ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth } 824ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 834ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth bool isAlways() const { return Cost == AlwaysInlineCost; } 844ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth bool isNever() const { return Cost == NeverInlineCost; } 854ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth bool isVariable() const { return !isAlways() && !isNever(); } 864ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 874ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Get the inline cost estimate. 884ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// It is an error to call this on an "always" or "never" InlineCost. 894ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth int getCost() const { 904ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth assert(isVariable() && "Invalid access of InlineCost"); 914ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth return Cost; 924ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth } 934ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 944ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Get the cost delta from the threshold for inlining. 954ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// Only valid if the cost is of the variable kind. Returns a negative 964ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// value if the cost is too high to inline. 974ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth int getCostDelta() const { return Threshold - getCost(); } 984ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth}; 994ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 10078e1cdaba3cad6e85ff631542052bbb718c7e588Chandler Carruth/// \brief Cost analyzer used by inliner. 10186953b5795007eaa98838297360a6987e33e92e7Chandler Carruthclass InlineCostAnalysis : public CallGraphSCCPass { 1028d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth const TargetTransformInfo *TTI; 1034ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 1044ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruthpublic: 10586953b5795007eaa98838297360a6987e33e92e7Chandler Carruth static char ID; 1064ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 10786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth InlineCostAnalysis(); 10886953b5795007eaa98838297360a6987e33e92e7Chandler Carruth ~InlineCostAnalysis(); 10986953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 11086953b5795007eaa98838297360a6987e33e92e7Chandler Carruth // Pass interface implementation. 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnSCC(CallGraphSCC &SCC) override; 1134ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 1144ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Get an InlineCost object representing the cost of inlining this 1154ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// callsite. 116f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth /// 1174ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// Note that threshold is passed into this function. Only costs below the 1184ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// threshold are computed with any accuracy. The threshold can be used to 1194ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// bound the computation necessary to determine whether the cost is 1204ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// sufficiently low to warrant inlining. 12186953b5795007eaa98838297360a6987e33e92e7Chandler Carruth /// 12286953b5795007eaa98838297360a6987e33e92e7Chandler Carruth /// Also note that calling this function *dynamically* computes the cost of 12386953b5795007eaa98838297360a6987e33e92e7Chandler Carruth /// inlining the callsite. It is an expensive, heavyweight call. 1244ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth InlineCost getInlineCost(CallSite CS, int Threshold); 1254ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 1264ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Get an InlineCost with the callee explicitly specified. 1274ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// This allows you to calculate the cost of inlining a function via a 1284ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// pointer. This behaves exactly as the version with no explicit callee 1294ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// parameter in all other respects. 1304ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth // 1314ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth // Note: This is used by out-of-tree passes, please do not remove without 1324ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth // adding a replacement API. 1334ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 1344ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth 1354ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth /// \brief Minimal filter to detect invalid constructs for inlining. 1364ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth bool isInlineViable(Function &Callee); 1374ef13242ab7473de62c2c4d77de3c69d362bd9efChandler Carruth}; 138aa034fa2299e41b73f60d3993f5460260e239fabJakob Stoklund Olesen 1396899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel} 1406899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel 1416899b314225dd5fa5ccc2a5692daaa89c1d623d8Devang Patel#endif 142