From c5e1ec47c719806fcc882470595960512edc7441 Mon Sep 17 00:00:00 2001 From: Daniel Dunbar Date: Thu, 30 Oct 2008 19:26:59 +0000 Subject: [PATCH] Add InlineCost class for represent the estimated cost of inlining a function. - This explicitly models the costs for functions which should "always" or "never" be inlined. This fixes bugs where such costs were not previously respected. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58450 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/IPO/InlinerPass.h | 3 +- include/llvm/Transforms/Utils/InlineCost.h | 40 ++++++++++++++++++- lib/Transforms/IPO/InlineAlways.cpp | 2 +- lib/Transforms/IPO/InlineSimple.cpp | 2 +- lib/Transforms/IPO/Inliner.cpp | 15 ++++++- lib/Transforms/Utils/BasicInliner.cpp | 25 ++++++++---- lib/Transforms/Utils/InlineCost.cpp | 14 ++++--- .../Inline/2008-10-30-AlwaysInline.ll | 14 +++++++ 8 files changed, 97 insertions(+), 18 deletions(-) create mode 100644 test/Transforms/Inline/2008-10-30-AlwaysInline.ll diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h index 00950f78e8c..082dd82a67e 100644 --- a/include/llvm/Transforms/IPO/InlinerPass.h +++ b/include/llvm/Transforms/IPO/InlinerPass.h @@ -18,6 +18,7 @@ #define INLINER_H #include "llvm/CallGraphSCCPass.h" +#include "llvm/Transforms/Utils/InlineCost.h" namespace llvm { class CallSite; @@ -53,7 +54,7 @@ struct Inliner : public CallGraphSCCPass { /// returned is greater than the current inline threshold, the call site is /// not inlined. /// - virtual int getInlineCost(CallSite CS) = 0; + virtual InlineCost getInlineCost(CallSite CS) = 0; // getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a // higher threshold to determine if the function call should be inlined. diff --git a/include/llvm/Transforms/Utils/InlineCost.h b/include/llvm/Transforms/Utils/InlineCost.h index 154ba1a4d45..1698a819400 100644 --- a/include/llvm/Transforms/Utils/InlineCost.h +++ b/include/llvm/Transforms/Utils/InlineCost.h @@ -15,6 +15,7 @@ #define LLVM_TRANSFORMS_UTILS_INLINECOST_H #include "llvm/ADT/SmallPtrSet.h" +#include #include #include @@ -24,6 +25,41 @@ namespace llvm { class Function; class CallSite; + /// InlineCost - Represent the cost of inlining a function. This + /// supports special values for functions which should "always" or + /// "never" be inlined. Otherwise, the cost represents a unitless + /// amount; smaller values increase the likelyhood of the function + /// being inlined. + class InlineCost { + enum Kind { + Value, + Always, + Never + }; + + int Cost : 30; + unsigned Type : 2; + + InlineCost(int C, int T) : Cost(C), Type(T) { + assert(Cost == C && "Cost exceeds InlineCost precision"); + } + public: + static InlineCost get(int Cost) { return InlineCost(Cost, Value); } + static InlineCost getAlways() { return InlineCost(0, Always); } + static InlineCost getNever() { return InlineCost(0, Never); } + + bool isVariable() const { return Type == Value; } + bool isAlways() const { return Type == Always; } + bool isNever() const { return Type == Never; } + + /// getValue() - Return a "variable" inline cost's amount. It is + /// an error to call this on an "always" or "never" InlineCost. + int getValue() const { + assert(Type == Value && "Invalid access of InlineCost"); + return Cost; + } + }; + /// InlineCostAnalyzer - Cost analyzer used by inliner. class InlineCostAnalyzer { struct ArgInfo { @@ -83,8 +119,8 @@ namespace llvm { /// getInlineCost - The heuristic used to determine if we should inline the /// function call or not. /// - int getInlineCost(CallSite CS, - SmallPtrSet &NeverInline); + InlineCost getInlineCost(CallSite CS, + SmallPtrSet &NeverInline); /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a /// higher threshold to determine if the function call should be inlined. diff --git a/lib/Transforms/IPO/InlineAlways.cpp b/lib/Transforms/IPO/InlineAlways.cpp index 2799d6b22bc..d809b5aed17 100644 --- a/lib/Transforms/IPO/InlineAlways.cpp +++ b/lib/Transforms/IPO/InlineAlways.cpp @@ -39,7 +39,7 @@ namespace { // Use extremely low threshold. AlwaysInliner() : Inliner(&ID, -2000000000) {} static char ID; // Pass identification, replacement for typeid - int getInlineCost(CallSite CS) { + InlineCost getInlineCost(CallSite CS) { return CA.getInlineCost(CS, NeverInline); } float getInlineFudgeFactor(CallSite CS) { diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp index 02cae2a6e67..8ae52353833 100644 --- a/lib/Transforms/IPO/InlineSimple.cpp +++ b/lib/Transforms/IPO/InlineSimple.cpp @@ -37,7 +37,7 @@ namespace { SimpleInliner() : Inliner(&ID) {} SimpleInliner(int Threshold) : Inliner(&ID, Threshold) {} static char ID; // Pass identification, replacement for typeid - int getInlineCost(CallSite CS) { + InlineCost getInlineCost(CallSite CS) { return CA.getInlineCost(CS, NeverInline); } float getInlineFudgeFactor(CallSite CS) { diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp index 74af18396d4..2321047a375 100644 --- a/lib/Transforms/IPO/Inliner.cpp +++ b/lib/Transforms/IPO/Inliner.cpp @@ -76,9 +76,22 @@ static bool InlineCallIfPossible(CallSite CS, CallGraph &CG, /// shouldInline - Return true if the inliner should attempt to inline /// at the given CallSite. bool Inliner::shouldInline(CallSite CS) { - int Cost = getInlineCost(CS); + InlineCost IC = getInlineCost(CS); float FudgeFactor = getInlineFudgeFactor(CS); + if (IC.isAlways()) { + DOUT << " Inlining: cost=always" + << ", Call: " << *CS.getInstruction(); + return true; + } + + if (IC.isNever()) { + DOUT << " NOT Inlining: cost=never" + << ", Call: " << *CS.getInstruction(); + return false; + } + + int Cost = IC.getValue(); int CurrentThreshold = InlineThreshold; Function *Fn = CS.getCaller(); if (Fn && !Fn->isDeclaration() diff --git a/lib/Transforms/Utils/BasicInliner.cpp b/lib/Transforms/Utils/BasicInliner.cpp index ba1fb3d9c4e..73e8bd84676 100644 --- a/lib/Transforms/Utils/BasicInliner.cpp +++ b/lib/Transforms/Utils/BasicInliner.cpp @@ -107,16 +107,27 @@ void BasicInlinerImpl::inlineFunctions() { --index; continue; } - int InlineCost = CA.getInlineCost(CS, NeverInline); - if (InlineCost >= (int) BasicInlineThreshold) { - DOUT << " NOT Inlining: cost = " << InlineCost - << ", call: " << *CS.getInstruction(); + InlineCost IC = CA.getInlineCost(CS, NeverInline); + if (IC.isAlways()) { + DOUT << " Inlining: cost=always" + <<", call: " << *CS.getInstruction(); + } else if (IC.isNever()) { + DOUT << " NOT Inlining: cost=never" + <<", call: " << *CS.getInstruction(); continue; + } else { + int Cost = IC.getValue(); + + if (Cost >= BasicInlineThreshold) { + DOUT << " NOT Inlining: cost = " << Cost + << ", call: " << *CS.getInstruction(); + continue; + } else { + DOUT << " Inlining: cost = " << Cost + << ", call: " << *CS.getInstruction(); + } } - DOUT << " Inlining: cost=" << InlineCost - <<", call: " << *CS.getInstruction(); - // Inline if (InlineFunction(CS, NULL, TD)) { if (Callee->use_empty() && Callee->hasInternalLinkage()) diff --git a/lib/Transforms/Utils/InlineCost.cpp b/lib/Transforms/Utils/InlineCost.cpp index c665b126345..b85a45590cb 100644 --- a/lib/Transforms/Utils/InlineCost.cpp +++ b/lib/Transforms/Utils/InlineCost.cpp @@ -169,7 +169,7 @@ void InlineCostAnalyzer::FunctionInfo::analyzeFunction(Function *F) { // getInlineCost - The heuristic used to determine if we should inline the // function call or not. // -int InlineCostAnalyzer::getInlineCost(CallSite CS, +InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, SmallPtrSet &NeverInline) { Instruction *TheCall = CS.getInstruction(); Function *Callee = CS.getCalledFunction(); @@ -187,7 +187,7 @@ int InlineCostAnalyzer::getInlineCost(CallSite CS, // Don't inline functions marked noinline. NeverInline.count(Callee)) - return 2000000000; + return llvm::InlineCost::getNever(); // InlineCost - This value measures how good of an inline candidate this call // site is to inline. A lower inline cost make is more likely for the call to @@ -224,10 +224,14 @@ int InlineCostAnalyzer::getInlineCost(CallSite CS, // If we should never inline this, return a huge cost. if (CalleeFI.NeverInline) - return 2000000000; + return InlineCost::getNever(); + // FIXME: It would be nice to kill off CalleeFI.NeverInline. Then we + // could move this up and avoid computing the FunctionInfo for + // things we are going to just return always inline for. This + // requires handling setjmp somewhere else, however. if (!Callee->isDeclaration() && Callee->hasFnAttr(Attribute::AlwaysInline)) - return -2000000000; + return InlineCost::getAlways(); // Add to the inline quality for properties that make the call valuable to // inline. This includes factors that indicate that the result of inlining @@ -274,7 +278,7 @@ int InlineCostAnalyzer::getInlineCost(CallSite CS, // Look at the size of the callee. Each instruction counts as 5. InlineCost += CalleeFI.NumInsts*5; - return InlineCost; + return llvm::InlineCost::get(InlineCost); } // getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a diff --git a/test/Transforms/Inline/2008-10-30-AlwaysInline.ll b/test/Transforms/Inline/2008-10-30-AlwaysInline.ll new file mode 100644 index 00000000000..765fc757876 --- /dev/null +++ b/test/Transforms/Inline/2008-10-30-AlwaysInline.ll @@ -0,0 +1,14 @@ +; RUN: llvm-as < %s | opt -always-inline | llvm-dis | not grep call + +; Ensure that threshold doesn't disrupt always inline. +; RUN: llvm-as < %s | opt -inline-threshold=-2000000001 -always-inline | llvm-dis | not grep call + + +define internal i32 @if0() alwaysinline { + ret i32 1 +} + +define i32 @f0() { + %r = call i32 @if0() + ret i32 %r +} -- 2.34.1