Index: include/llvm/Analysis/CallGraph.h =================================================================== --- include/llvm/Analysis/CallGraph.h +++ include/llvm/Analysis/CallGraph.h @@ -52,6 +52,7 @@ #ifndef LLVM_ANALYSIS_CALLGRAPH_H #define LLVM_ANALYSIS_CALLGRAPH_H +#include "llvm/Analysis/CallGraphReport.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/STLExtras.h" #include "llvm/IR/CallSite.h" @@ -105,6 +106,10 @@ /// functions that it calls. void addToCallGraph(Function *F); + // A list of CGReports (e.g. the InlineReport) which can be manipulated + // in a minimal way outside their local context + SmallVector CGReports; + public: explicit CallGraph(Module &M); CallGraph(CallGraph &&Arg); @@ -162,6 +167,29 @@ /// \brief Similar to operator[], but this will insert a new CallGraphNode for /// \c F if one does not already exist. CallGraphNode *getOrInsertFunction(const Function *F); + + /// \brief Add 'Report' to the list of reports which describe how the + /// call graph is being transformed. These reports will need to be + /// updated when major changes are made to the call graph (e.g. adding + /// or deleting a function). + void registerCGReport(CallGraphReport* Report) { + for (unsigned I = 0, E = CGReports.size(); I < E; ++I) { + if (CGReports[I] == Report) { + return; + } + } + CGReports.push_back(Report); + } + + /// \brief For all registered CG reports, indicate that 'OldFunction' + /// has been replaced by 'NewFunction'. + void replaceFunctionWithFunctionInCGReports(Function* OldFunction, + Function* NewFunction) { + for (unsigned I = 0, E = CGReports.size(); I < E; ++I) { + CGReports[I]->replaceFunctionWithFunction(OldFunction, NewFunction); + } + } + }; /// \brief A node in the call graph for a module. Index: include/llvm/Analysis/CallGraphReport.h =================================================================== --- include/llvm/Analysis/CallGraphReport.h +++ include/llvm/Analysis/CallGraphReport.h @@ -0,0 +1,36 @@ +//===- CallGraphReport.h Implement call graph report ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file describes a class CallGraphReport which contains pure virtual +// functions that should be redefined for each subclass. These functions +// indicate how the reports in each subclass should be modified when a +// major transformation to the call graph occurs. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CALLGRAPHREPORT_H +#define LLVM_ANALYSIS_CALLGRAPHREPORT_H + +namespace llvm { + +class Function; + +// \brief Class describing a Report that describes major transformations +// on the call graph. +class CallGraphReport { +public: + + virtual void replaceFunctionWithFunction(Function* OldFunction, + Function* NewFunction) = 0; + +}; + +} + +#endif Index: include/llvm/Transforms/IPO/InlineReport.h =================================================================== --- include/llvm/Transforms/IPO/InlineReport.h +++ include/llvm/Transforms/IPO/InlineReport.h @@ -0,0 +1,353 @@ +//===- InlineReport.h Implement inlining report ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines various classes needed to represent an inlining report. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INLINEREPORT_H +#define LLVM_TRANSFORMS_IPO_INLINEREPORT_H + +#include "llvm/ADT/MapVector.h" +#include "llvm/Analysis/CallGraphReport.h" +#include "llvm/Analysis/CallGraphSCCPass.h" +#include "llvm/Analysis/InlineCost.h" +#include "llvm/Transforms/Utils/Cloning.h" + +namespace llvm { + +class InlineReportCallSite; + +typedef std::vector InlineReportCallSiteVector; + +namespace InlineReportTypes { + +typedef enum { + Basic = 1, // Print basic information like what was inlined + Reasons = 2, // Add reasons for inlining or not inlining + // (to be implemented) + SameLine = 4, // Put the reasons and the call site on the same lime + LineCol = 8, // Print the line and column of the call sites + // if we had appropriate source position information + File = 16, // Print the file of the call sites + Linkage = 32 // Print linkage info for routines and call sites: + // L: local (F.hasLocalLinkage()) + // O: link once ODR (one definition rule) + // (F.hasLinkOnceODRLinkage()) + // X: available externally (and generally not emitted) + // (F.hasAvailableExternallyLinkage()) + // A: alternate (something other than L, O, or X) +} InlineReportOptions; + +} + +class InlineReportFunction; + +/// +/// \brief Represents a CallSite in the inlining report +/// +class InlineReportCallSite { +public: + + // \brief Constructor for InlineReportCallSite + // The source file is given by 'M'. The line and column info by 'Dloc' + explicit InlineReportCallSite(InlineReportFunction* IRCallee, bool IsInlined, + Module* Module, DebugLoc* DLoc, Instruction* I) : IRCallee(IRCallee), + IsInlined(IsInlined), InlineCost(-1), OuterInlineCost (-1), + InlineThreshold (-1), Call (I), M (Module) { + Line = DLoc && DLoc->get() ? DLoc->getLine() : 0; + Col = DLoc && DLoc->get() ? DLoc->getCol() : 0; + Children.clear(); + }; + + ~InlineReportCallSite(void); + InlineReportCallSite(const InlineReportCallSite&) = delete; + void operator=(const InlineReportCallSite&) = delete; + + // \brief Return a clone of *this, but do not copy its children, and + // use the IIMap to get a new value for the 'Call'. + InlineReportCallSite* cloneBase(const ValueToValueMapTy& IIMap); + + InlineReportFunction* getIRCallee() const { return IRCallee; } + bool getIsInlined() const { return IsInlined; } + void setIsInlined(bool Inlined) { IsInlined = Inlined; } + + /// \brief Return the vector of InlineReportCallSites which represent + /// the calls made from the section of inlined code represented by + /// this InlineReportCallSite. + const InlineReportCallSiteVector& getChildren() { return Children; } + + /// \brief Inlining is inhibited if the inline cost is greater than + /// the threshold. + int getInlineCost() const { return InlineCost; } + void setInlineCost(int Cost) { InlineCost = Cost; } + + /// \brief Since inlining is bottom up, always selecting the leaf-most + /// call sites for inlining is not always best, as it may inhibit inlining + /// further up the call tree. Therefore, in addition to an inlining cost, + /// the inliner computes an outer inlining cost as well. Inlining is also + /// inhibited if the outer inlining cost is greater than the inline + /// threshold. + int getOuterInlineCost() const { return OuterInlineCost; } + void setOuterInlineCost(int Cost) { OuterInlineCost = Cost; } + + int getInlineThreshold() const { return InlineThreshold; } + void setInlineThreshold(int Threshold) { InlineThreshold = Threshold; } + Instruction* getCall() const { return Call; } + void setCall(Instruction* call) { Call = call; } + void addChild(InlineReportCallSite* IRCS) { + Children.push_back(IRCS); + } + + /// \brief Print the info in the inlining instance for the inling report + /// indenting 'indentCount' indentations, assuming an inlining report + /// level of 'ReportLevel'. + void print(unsigned IndentCount, unsigned ReportLevel); + + /// \brief Load the call represented by '*this' and all of its descendant + /// calls into the map 'Lmap'. + void loadCallsToMap(std::map& LMap); + +private: + InlineReportFunction* IRCallee; + bool IsInlined; + int InlineCost; + int OuterInlineCost; + int InlineThreshold; + InlineReportCallSiteVector Children; + Instruction* Call; + /// + /// \brief Used to get the file name when we print the report + Module* M; + /// + /// \brief The line and column number of the call site. These are 0 if + /// we are not compiling with -g or the lighter weight version + /// -gline-tables-only + unsigned Line; + unsigned Col; + void printCostAndThreshold(void); + void printOuterCostAndThreshold(void); + void printCalleeNameModuleLineCol(unsigned Level); + // \brief Return a pointer to a copy of Base with an empty Children vector + InlineReportCallSite* copyBase(const InlineReportCallSite& Base, + Instruction* NI); +}; + +/// +/// \brief Represents a routine (compiled or dead) in the inlining report +/// +class InlineReportFunction { +public: + + explicit InlineReportFunction(const Function* F) : IsDead(false), + IsCurrent(false), IsDeclaration(false), LinkageChar(' ') {}; + ~InlineReportFunction(void); + InlineReportFunction(const InlineReportFunction&) = delete; + void operator=(const InlineReportFunction&) = delete; + + /// \brief A vector of InlineReportCallSites representing the top-level + /// call sites in a function (i.e. those which appear in the source code + /// of the function). + const InlineReportCallSiteVector& getCallSites() { return CallSites; } + + /// \brief Add an InlineReportCallSite to the list of top-level calls for + /// this function. + void addCallSite(InlineReportCallSite* IRCS) { + CallSites.push_back(IRCS); + } + + /// \brief Return true if the function has been dead code eliminated. + bool getDead() const { return IsDead; } + + /// \brief Set whether the function is dead code eliminated. + void setDead(bool Dead) { IsDead = Dead; } + + /// \brief Return true if the inline report for this routine reflects + /// the changes that have been made to the routine since the last call + /// to Inliner::runOnSCC() + bool getCurrent(void) const { return IsCurrent; } + + /// \brief Set whether the inline report for the routine is current + void setCurrent(bool Current) { IsCurrent = Current; } + + bool getIsDeclaration(void) const { return IsDeclaration; } + + void setIsDeclaration(bool Declaration) { IsDeclaration = Declaration; } + + /// brief Get a single character indicating the linkage type + char getLinkageChar(void) { return LinkageChar; } + + /// brief Set a single character indicating the linkage type + void setLinkageChar(Function *F); + + std::string& getName() { return Name; } + + void setName(std::string FunctionName) { Name = FunctionName; } + + void print(unsigned Level) const; + +private: + bool IsDead; + bool IsCurrent; + bool IsDeclaration; + char LinkageChar; + std::string Name; + InlineReportCallSiteVector CallSites; +}; + +typedef MapVector + InlineReportFunctionMap; +typedef std::vector InlineReportFunctionVector; +typedef std::map + InlineReportInstructionCallSiteMap; + +/// +/// \brief The inlining report +/// +class InlineReport : public CallGraphReport { +public: + + explicit InlineReport(unsigned MyLevel) : + Level(MyLevel), ActiveInlineInstruction(nullptr) {}; + virtual ~InlineReport(void); + InlineReport(const InlineReport&) = delete; + void operator=(const InlineReport&) = delete; + + // \brief Create an InlineReportFunction to represent F + InlineReportFunction* addFunction(Function* F, Module* M); + + // \brief Create an InlineReportCallSite to represent CS + InlineReportCallSite* addCallSite(Function* F, CallSite* CS, Module* M); + + // \brief Create an InlineReportCallSite to represent CS, if one does + // not already exist + InlineReportCallSite* addNewCallSite(Function* F, CallSite* CS, + Module* M); + + // \brief Indicate that the Function is dead + void setDead(Function *F); + + /// \brief Indicate that CS has been inlined, and clone and attach the + /// inlining report for the function being inlined to the + /// InlineReportCallSite for CS. + void inlineCallSite(Instruction* NI, InlineReportCallSite* IRCS, Module* M, + Function* Callee, InlineFunctionInfo& InlineInfo); + + /// \brief Print the inlining report at the given level. + void print() const; + +#ifndef NDEBUG + /// \brief Run some simple consistency checking on 'F', e.g. + /// (1) Check that F is in the inline report's function map + /// (2) Check that all of the call/invoke instructions in F's IR + /// appear in the inline report for F + bool validateFunction(Function* F); + /// \brief Validate all of the functions in the IR function map + bool validate(void); +#endif // NDEBUG + + /// \brief Ensure that the inline report for this routine reflects the + /// changes thatr have been made to that routine since the last call to + /// Inliner::runOnSCC() + void makeCurrent(Module* M, Function* F); + + /// \brief Indicate that the inline reports may need to be made current + /// with InlineReport::makeCurrent() before they are changed to indicate + /// additional inlining. + void makeAllNotCurrent(void); + + void dumpFunctionMap(void); + + void replaceFunctionWithFunction(Function* OldFunction, + Function* NewFunction) override; + + void addCallback(Value* V); + + InlineReportCallSite* getCallSite(CallSite* CS); + + Instruction* getActiveInlineInstruction(void) + { return ActiveInlineInstruction; } + void setActiveInlineInstruction(Instruction* AII) + { ActiveInlineInstruction = AII; } + +private: + + /// \brief The Level is specified by the option -inline-report=N. + /// See llvm/lib/Transforms/IPO/Inliner.cpp for details on Level. + unsigned Level; + + // \brief The instruction for the call site currently being inlined + Instruction* ActiveInlineInstruction; + + /// \brief A mapping from Functions to InlineReportFunctions + InlineReportFunctionMap IRFunctionMap; + + /// \brief A mapping from Instructions to InlineReportCallSites + InlineReportInstructionCallSiteMap IRInstructionCallSiteMap; + + /// \brief A vector of InlineReportFunctions of Functions that have + /// been eliminated by dead static function elimination + InlineReportFunctionVector IRDeadFunctionVector; + + /// \brief Clone the vector of InlineReportCallSites for NewCallSite + /// using the mapping of old calls to new calls IIMap + void cloneChildren(const InlineReportCallSiteVector& OldCallSiteVector, + InlineReportCallSite* NewCallSite, ValueToValueMapTy& IIMap); + + // \brief Print the inlining option values + void printOptionValues(void) const; + + /// + /// \brief CallbackVM for Instructions and Functions in the InlineReport + /// + class InlineReportCallback : public CallbackVH { + InlineReport* IR; + void deleted() override { + assert(IR != nullptr); + if (isa(getValPtr())) { + /// \brief Indicate in the inline report that the call site + /// corresponding to the Value has been deleted + Instruction* I = cast(getValPtr()); + if (IR->getActiveInlineInstruction() != I) { + InlineReportInstructionCallSiteMap::const_iterator MapIt; + MapIt = IR->IRInstructionCallSiteMap.find(I); + if (MapIt != IR->IRInstructionCallSiteMap.end()) { + IR->IRInstructionCallSiteMap.erase(MapIt); + } + } + } + else if (isa(getValPtr())) { + /// \brief Indicate in the inline report that the function + /// corresponding to the Value has been deleted + Function* F = cast(getValPtr()); + InlineReportFunctionMap::iterator MapIt; + MapIt = IR->IRFunctionMap.find(F); + if (MapIt != IR->IRFunctionMap.end()) { + InlineReportFunction* IRF = MapIt->second; + IR->setDead(F); + IRF->setLinkageChar(F); + IR->IRFunctionMap.erase(MapIt); + IR->IRDeadFunctionVector.push_back(IRF); + } + } + setValPtr(nullptr); + }; + public: + InlineReportCallback(Value* V, InlineReport *CBIR) : + CallbackVH(V), IR(CBIR) {}; + virtual ~InlineReportCallback() {}; + }; + + SmallVector IRCallbackVector; + +}; + +} + +#endif Index: include/llvm/Transforms/IPO/InlinerPass.h =================================================================== --- include/llvm/Transforms/IPO/InlinerPass.h +++ include/llvm/Transforms/IPO/InlinerPass.h @@ -18,6 +18,7 @@ #define LLVM_TRANSFORMS_IPO_INLINERPASS_H #include "llvm/Analysis/CallGraphSCCPass.h" +#include "llvm/Transforms/IPO/InlineReport.h" namespace llvm { class AssumptionCacheTracker; @@ -62,14 +63,19 @@ /// deal with that subset of the functions. bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly = false); + InlineReport& getReport() { return Report; } + private: // InsertLifetime - Insert @llvm.lifetime intrinsics. bool InsertLifetime; /// shouldInline - Return true if the inliner should attempt to /// inline at the given CallSite. - bool shouldInline(CallSite CS); +bool shouldInline(CallSite CS); + // The inline report + InlineReport Report; + protected: AssumptionCacheTracker *ACT; }; Index: include/llvm/Transforms/Utils/Cloning.h =================================================================== --- include/llvm/Transforms/Utils/Cloning.h +++ include/llvm/Transforms/Utils/Cloning.h @@ -189,12 +189,18 @@ /// get copied into the caller. SmallVector StaticAllocas; + /// OriginalCalls - InlineFunction fills this in with callsites that + /// were cloned from the callee. This is only filled in if CG is + /// non-null. + SmallVector OriginalCalls; + /// InlinedCalls - InlineFunction fills this in with callsites that were /// inlined from the callee. This is only filled in if CG is non-null. SmallVector InlinedCalls; void reset() { StaticAllocas.clear(); + OriginalCalls.clear(); InlinedCalls.clear(); } }; Index: lib/Transforms/IPO/ArgumentPromotion.cpp =================================================================== --- lib/Transforms/IPO/ArgumentPromotion.cpp +++ lib/Transforms/IPO/ArgumentPromotion.cpp @@ -750,6 +750,9 @@ // Get the callgraph information that we need to update to reflect our // changes. CallGraph &CG = getAnalysis().getCallGraph(); + // Argument promotion is replacing F with NF. We need to update all + // of the call graph reports to reflect this. + CG.replaceFunctionWithFunctionInCGReports(F, NF); // Get a new callgraph node for NF. CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF); Index: lib/Transforms/IPO/CMakeLists.txt =================================================================== --- lib/Transforms/IPO/CMakeLists.txt +++ lib/Transforms/IPO/CMakeLists.txt @@ -15,6 +15,7 @@ IPO.cpp InferFunctionAttrs.cpp InlineAlways.cpp + InlineReport.cpp InlineSimple.cpp Inliner.cpp Internalize.cpp Index: lib/Transforms/IPO/InlineAlways.cpp =================================================================== --- lib/Transforms/IPO/InlineAlways.cpp +++ lib/Transforms/IPO/InlineAlways.cpp @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/IPO/InlinerPass.h" #include "llvm/Transforms/IPO.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/AssumptionCache.h" @@ -51,7 +52,9 @@ using llvm::Pass::doFinalization; bool doFinalization(CallGraph &CG) override { - return removeDeadFunctions(CG, /*AlwaysInlineOnly=*/ true); + bool ReturnValue = removeDeadFunctions(CG, /*AlwaysInlineOnly=*/ true); + getReport().print(); + return ReturnValue; } }; Index: lib/Transforms/IPO/InlineReport.cpp =================================================================== --- lib/Transforms/IPO/InlineReport.cpp +++ lib/Transforms/IPO/InlineReport.cpp @@ -0,0 +1,532 @@ +//===- InlineReport.cpp - Inline report ------------ ---------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the mechanics of the inlining report. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/InlineReport.h" +#include "llvm/Transforms/IPO/InlinerPass.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; +using namespace InlineReportTypes; + +/// +/// \brief Inlining report level option +/// +/// Specified with -inline-report=N +/// N is a bit mask with the following interpretation of the bits +/// 0: No inlining report +/// 1: Simple inlining report +/// 2: Add inlining reasons (to be implemented) +/// 4: Put the inlining reasons on the same line as the call sites +/// 8: Print the line and column info for each call site if available +/// 16: Print the file for each call site +/// 32: Print linkage info for each function and call site +/// +cl::opt +InlineReportLevel("inline-report", cl::Hidden, cl::init(0), + cl::Optional, cl::desc("Print inline report")); + +// +// The functions below implement the printing of the inlining report +// + +// +// Member functions for class InlineReportCallSite +// + +InlineReportCallSite::~InlineReportCallSite(void) { + while (!Children.empty()) { + InlineReportCallSite* cs = Children.back(); + Children.pop_back(); + delete cs; + } +} + +InlineReportCallSite* InlineReportCallSite::copyBase( + const InlineReportCallSite& Base, Instruction* NI) +{ + InlineReportCallSite* NewCS = new InlineReportCallSite(Base.IRCallee, + Base.IsInlined, Base.M, nullptr, NI); + NewCS->IsInlined = Base.IsInlined; + NewCS->InlineCost = Base.InlineCost; + NewCS->OuterInlineCost = Base.OuterInlineCost; + NewCS->InlineThreshold = Base.InlineThreshold; + NewCS->Line = Base.Line; + NewCS->Col = Base.Col; + NewCS->Children.clear(); + return NewCS; +} + +InlineReportCallSite* InlineReportCallSite::cloneBase( + const ValueToValueMapTy& IIMap) { + if (IsInlined) { + InlineReportCallSite* IRCSk = copyBase(*this, nullptr); + return IRCSk; + } + const Value* oldCall = this->getCall(); + if (oldCall == nullptr) { + return nullptr; + } + ValueToValueMapTy::const_iterator VMI = IIMap.find(oldCall); + if (VMI == IIMap.end()) { + return nullptr; + } + WeakVH newCall = VMI->second; + Instruction* NI = cast(newCall); + InlineReportCallSite* IRCSk = copyBase(*this, NI); + return IRCSk; +} + +/// +/// \brief Print 'indentCount' indentations +/// +static void printIndentCount(unsigned indentCount) { + for (unsigned J = 0; J < indentCount; ++J) { + llvm::errs() << " "; + } +} + +/// +/// \brief Print the linkage info for a function 'F' as a single letter, +/// if the 'Level' specifies InlineReportOptions::Linkage. +/// For an explanation of the meaning of these letters, see InlineReport.h. +/// +static void printFunctionLinkage(unsigned Level, InlineReportFunction* IRF) +{ + if (!(Level & InlineReportOptions::Linkage)) { + return; + } + llvm::errs() << IRF->getLinkageChar() << " "; +} + +/// +/// \brief Print the callee name, and if non-zero, the line and column +/// number of the call site +/// +void InlineReportCallSite::printCalleeNameModuleLineCol(unsigned Level) +{ + if (getIRCallee() != nullptr) { + printFunctionLinkage(Level, getIRCallee()); + llvm::errs() << getIRCallee()->getName(); + } + if (Level & InlineReportOptions::File) { + llvm::errs() << " " << M->getModuleIdentifier(); + } + if ((Level & InlineReportOptions::LineCol) && (Line != 0 || Col != 0)) { + llvm::errs() << " (" << Line << "," << Col << ")"; + } +} + +/// +/// \brief Print a representation of the inlining instance. +/// +/// indentCount: The number of indentations to print +/// level: The level N from '-inline-report=N' +/// +void InlineReportCallSite::print(unsigned IndentCount, unsigned Level) { + printIndentCount(IndentCount); + if (getIsInlined()) { + llvm::errs() << "-> INLINE: "; + printCalleeNameModuleLineCol(Level); + } + else { + llvm::errs() << "-> "; + printCalleeNameModuleLineCol(Level); + } + llvm::errs() << "\n"; +} + +// +// Member functions for class InlineReportFunction +// + +InlineReportFunction::~InlineReportFunction(void) { + while (!CallSites.empty()) { + InlineReportCallSite* CS = CallSites.back(); + CallSites.pop_back(); + delete CS; + } +} + +void InlineReportFunction::setLinkageChar(Function *F) { + LinkageChar = (F->hasLocalLinkage() ? 'L' : + (F->hasLinkOnceODRLinkage() ? 'O' : + (F->hasAvailableExternallyLinkage() ? 'X' : 'A'))); +} + +// +// Member functions for class InlineReport +// + +InlineReportFunction* InlineReport::addFunction(Function* F, Module* M) { + if (Level == 0) { + return nullptr; + } + if (F == nullptr) { + return nullptr; + } + InlineReportFunctionMap::const_iterator MapIt = IRFunctionMap.find(F); + if (MapIt != IRFunctionMap.end()) { + InlineReportFunction* IRF = MapIt->second; + makeCurrent(M, F); + return IRF; + } + InlineReportFunction* IRF = new InlineReportFunction(F); + IRFunctionMap.insert(std::make_pair(F, IRF)); + IRF->setName(F->getName().str()); + IRF->setIsDeclaration(F->isDeclaration()); + IRF->setLinkageChar(F); + addCallback(F); + return IRF; +} + +InlineReportCallSite* InlineReport::addCallSite(Function* F, CallSite* CS, + Module* M) { + if (Level == 0) { + return nullptr; + } + if (F == nullptr) { + return nullptr; + } + Instruction *I = CS->getInstruction(); + DebugLoc DLoc = CS->getInstruction()->getDebugLoc(); + InlineReportFunctionMap::const_iterator MapIt = IRFunctionMap.find(F); + assert(MapIt != IRFunctionMap.end()); + InlineReportFunction* IRF = MapIt->second; + Function* Callee = CS->getCalledFunction(); + InlineReportFunction* IRFC = nullptr; + if (Callee != nullptr) { + InlineReportFunctionMap::const_iterator MapItC + = IRFunctionMap.find(Callee); + IRFC = MapItC == IRFunctionMap.end() + ? addFunction(Callee, M) : MapItC->second; + } + InlineReportCallSite* IRCS = new InlineReportCallSite(IRFC, false, + M, &DLoc, I); + IRF->addCallSite(IRCS); + IRInstructionCallSiteMap.insert(std::make_pair(I, IRCS)); + addCallback(I); + return IRCS; +} + +InlineReportCallSite* InlineReport::addNewCallSite(Function* F, CallSite* CS, + Module* M) { + if (Level == 0) { + return nullptr; + } + InlineReportCallSite* IRCS = getCallSite(CS); + if (IRCS != nullptr) + return IRCS; + return addCallSite(F, CS, M); +} + +void InlineReport::setDead(Function* F) { + if (Level == 0) { + return; + } + InlineReportFunctionMap::const_iterator MapIt = IRFunctionMap.find(F); + assert(MapIt != IRFunctionMap.end()); + InlineReportFunction* INR = MapIt->second; + INR->setDead(true); +} + +void InlineReport::cloneChildren( + const InlineReportCallSiteVector& OldCallSiteVector, + InlineReportCallSite* NewCallSite, ValueToValueMapTy& IIMap) +{ + assert(NewCallSite->getChildren().empty()); + for (unsigned I = 0, E = OldCallSiteVector.size(); I < E; ++I) { + // + // Copy the old InlineReportCallSite and add it to the children of the + // cloned InlineReportCallSite. + InlineReportCallSite* IRCSj = OldCallSiteVector[I]; + InlineReportCallSite* IRCSk = IRCSj->cloneBase(IIMap); + if (IRCSk == nullptr) { + continue; + } + NewCallSite->addChild(IRCSk); + // + // We keep track of the new calls that are added added to the inline + // report in case they themselves will be inlined. + if (IRCSk->getCall() != nullptr) { + IRInstructionCallSiteMap.insert(std::make_pair(IRCSk->getCall(), IRCSk)); + addCallback(IRCSk->getCall()); + } + // + // Recursively copy the InlineReportCallSites for the children. + if (IRCSj->getIsInlined()) { + cloneChildren(IRCSj->getChildren(), IRCSk, IIMap); + } + } +} + +void InlineReport::inlineCallSite(Instruction* NI, InlineReportCallSite* IRCS, + Module* M, Function* Callee, InlineFunctionInfo& InlineInfo) { + if (Level == 0) { + return; + } + // + // Get the inline report for the routine being inlined. We are going + // to make a clone of it. + InlineReportFunctionMap::const_iterator MapItF = IRFunctionMap.find(Callee); + InlineReportFunction* INR = addFunction(Callee, M); + // + // Ensure that the report is up to date since the last call to + // Inliner::runOnSCC + makeCurrent(M, Callee); + // + // Create InlineReportCallSites "new calls" which appear in the inlined + // code. Also, create a mapping from the "original calls" which appeared + // in the routine that was inlined, to the "new calls". When we clone the + // inline report for the routine being inlined, we need to replace the + // original calls with the new calls in the cloned inline report. + // We use 'IIMap' to do that mapping. + ValueToValueMapTy IIMap; + SmallVector& OriginalCalls = InlineInfo.OriginalCalls; + SmallVector& NewCalls = InlineInfo.InlinedCalls; + for (unsigned I = 0, E = OriginalCalls.size(); I < E; ++I) { + IIMap.insert(std::make_pair(OriginalCalls[I], NewCalls[I])); + } + // + // Clone the inline report INR and attach it to the inlined call site IRCS. + // Use IIMap to map the original calls to the new calls in the cloned + // inline report. + cloneChildren(INR->getCallSites(), IRCS, IIMap); + // Indicate that the call has been inlined in the inline report + IRCS->setIsInlined(true); + // + // Remove the inlined instruction from the IRInstructionCallSiteMap + InlineReportInstructionCallSiteMap::const_iterator MapIt; + MapIt = IRInstructionCallSiteMap.find(NI); + assert(MapIt != IRInstructionCallSiteMap.end()); + IRInstructionCallSiteMap.erase(MapIt); + IRCS->setCall(nullptr); +} + +void InlineReport::printOptionValues(void) const { + llvm::errs() << "Option Values:\n"; + llvm::errs() << " inline-threshold: " + << llvm::getDefaultInlineThreshold() << "\n"; + llvm::errs() << "\n"; +} + +/// +/// \brief Print the callsites in the 'Vector' +/// +/// indentCount: The number of indentations to print +/// level: The level N from '-inline-report=N' +/// +static void printInlineReportCallSiteVector( + const InlineReportCallSiteVector& Vector, + unsigned IndentCount, unsigned Level) { + for (unsigned I = 0, E = Vector.size(); I < E; ++I) { + Vector[I]->print(IndentCount, Level); + printInlineReportCallSiteVector(Vector[I]->getChildren(), IndentCount + 1, + Level); + } +} + +void InlineReportFunction::print(unsigned Level) const { + if (Level == 0) { + return; + } + printInlineReportCallSiteVector(CallSites, 1, Level); +} + +void InlineReport::print(void) const { + if (Level == 0) { + return; + } + llvm::errs() << "---- Begin Inlining Report ----\n"; + printOptionValues(); + for (unsigned I = 0, E = IRDeadFunctionVector.size(); I < E; ++I) { + InlineReportFunction* IRF = IRDeadFunctionVector[I]; + llvm::errs() << "DEAD STATIC FUNC: "; + printFunctionLinkage(Level, IRF); + llvm::errs() << IRF->getName() << "\n\n"; + } + InlineReportFunctionMap::const_iterator Mit, E; + for (Mit = IRFunctionMap.begin(), E = IRFunctionMap.end(); Mit != E; ++Mit) { + Function* F = Mit->first; + // Update the linkage info one last time before printing, + // as it may have changed. + InlineReportFunction* IRF = Mit->second; + IRF->setLinkageChar(F); + if (!IRF->getIsDeclaration()) { + llvm::errs() << "COMPILE FUNC: "; + printFunctionLinkage(Level, IRF); + llvm::errs() << IRF->getName() << "\n"; + InlineReportFunction* IRF = Mit->second; + IRF->print(Level); + llvm::errs() << "\n"; + } + } + llvm::errs() << "---- End Inlining Report ------\n"; +} + +void InlineReportCallSite::loadCallsToMap(std::map& LMap) { + Instruction* NI = getCall(); + if (NI != nullptr) { + LMap.insert(std::make_pair(NI, true)); + } + for (unsigned I = 0, E = Children.size(); I < E; ++I) { + Children[I]->loadCallsToMap(LMap); + } +} + +#ifndef NDEBUG +bool InlineReport::validateFunction(Function* F) { + llvm::errs() << "Validating " << F->getName() << "\n"; + bool ReturnValue = true; + InlineReportFunctionMap::const_iterator MapIt; + MapIt = IRFunctionMap.find(F); + if (MapIt == IRFunctionMap.end()) { + return false; + } + InlineReportFunction* IRF = MapIt->second; + IRF->print(Level); + std::map OriginalCalls; + const InlineReportCallSiteVector& Vec = IRF->getCallSites(); + for (unsigned I = 0, E = Vec.size(); I < E; ++I) { + Vec[I]->loadCallsToMap(OriginalCalls); + } + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + CallSite CS(cast(I)); + if (!CS) { + continue; + } + Instruction* NI = CS.getInstruction(); + std::map::const_iterator MapIt; + MapIt = OriginalCalls.find(NI); + if (MapIt == OriginalCalls.end()) { + ReturnValue = false; + llvm::errs() << "Cannot find " << NI << "\n"; + NI->dump(); + } + } + } + llvm::errs() << "Done Validating " << F->getName() << "\n"; + return ReturnValue; +} + +bool InlineReport::validate(void) { + bool GlobalRv = true; + InlineReportFunctionMap::const_iterator MI, ME; + llvm::errs() << "Start Validation Pass\n"; + for (MI = IRFunctionMap.begin(), ME = IRFunctionMap.end(); MI != ME; ++MI) { + Function* F = MI->first; + bool LocalRv = validateFunction(F); + llvm::errs() << "Validated " << F->getName(); + if (LocalRv) { + llvm::errs() << " passed\n"; + } + else { + llvm::errs() << " failed\n"; + } + GlobalRv &= LocalRv; + } + llvm::errs() << "End Validation Pass\n"; + return GlobalRv; +} +#endif // NDEBUG + +void InlineReport::makeCurrent(Module* M, Function* F) { + InlineReportFunctionMap::const_iterator MapIt = IRFunctionMap.find(F); + assert(MapIt != IRFunctionMap.end()); + InlineReportFunction* IRF = MapIt->second; + if (IRF->getCurrent()) { + return; + } + if (F->isDeclaration()) { + IRF->setCurrent(true); + return; + } + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + CallSite CS(cast(I)); + if (!CS) { + continue; + } + Instruction* NI = CS.getInstruction(); + InlineReportInstructionCallSiteMap::const_iterator MapItICS; + MapItICS = IRInstructionCallSiteMap.find(NI); + if (MapItICS != IRInstructionCallSiteMap.end()) { + continue; + } + InlineReportCallSite* IRCS = addCallSite(F, &CS, M); + assert(IRCS != nullptr); + } + } + IRF->setCurrent(true); +} + +void InlineReport::makeAllNotCurrent(void) { + if (Level == 0) { + return; + } + InlineReportFunctionMap::const_iterator It, E; + for (It = IRFunctionMap.begin(), E = IRFunctionMap.end(); It != E; ++It) { + InlineReportFunction* IRF = It->second; + IRF->setCurrent(false); + } +} + +void InlineReport::replaceFunctionWithFunction(Function* OldFunction, + Function* NewFunction) { + InlineReportFunctionMap::const_iterator IrfIt; + if (OldFunction == NewFunction) { + return; + } + IrfIt = IRFunctionMap.find(OldFunction); + if (IrfIt == IRFunctionMap.end()) { + return; + } + InlineReportFunction* IRF = IrfIt->second; + int count = IRFunctionMap.erase(OldFunction); + assert(count == 1); + IRFunctionMap.insert(std::make_pair(NewFunction, IRF)); + IRF->setLinkageChar(NewFunction); + IRF->setName(NewFunction->getName()); +} + +InlineReportCallSite* InlineReport::getCallSite(CallSite* CS) { + if (Level == 0) { + return nullptr; + } + Instruction* NI = CS->getInstruction(); + InlineReportInstructionCallSiteMap::const_iterator + MapItC = IRInstructionCallSiteMap.find(NI); + if (MapItC == IRInstructionCallSiteMap.end()) { + return nullptr; + } + return MapItC->second; +} + +InlineReport::~InlineReport(void) { + while (!IRCallbackVector.empty()) { + InlineReportCallback* IRCB = IRCallbackVector.back(); + IRCallbackVector.pop_back(); + delete IRCB; + } + InlineReportFunctionMap::const_iterator FI, FE; + for (FI = IRFunctionMap.begin(), FE = IRFunctionMap.end(); FI != FE; ++FI) { + delete FI->second; + } +} + +void InlineReport::addCallback(Value* V) { + InlineReportCallback* IRCB = new InlineReportCallback(V, this); + IRCallbackVector.push_back(IRCB); +} + Index: lib/Transforms/IPO/Inliner.cpp =================================================================== --- lib/Transforms/IPO/Inliner.cpp +++ lib/Transforms/IPO/Inliner.cpp @@ -42,15 +42,19 @@ STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); STATISTIC(NumMergedAllocas, "Number of allocas merged together"); +extern cl::opt InlineReportLevel; + // This weirdly named statistic tracks the number of times that, when attempting // to inline a function A into B, we analyze the callers of B in order to see // if those would be more profitable and blocked inline steps. STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed"); -Inliner::Inliner(char &ID) : CallGraphSCCPass(ID), InsertLifetime(true) {} +Inliner::Inliner(char &ID) : CallGraphSCCPass(ID), InsertLifetime(true), + Report(InlineReportLevel) {} Inliner::Inliner(char &ID, bool InsertLifetime) - : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {} + : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime), + Report(InlineReportLevel) {} /// For this class, we declare that we require and preserve the call graph. /// If the derived class implements this method, it should @@ -361,6 +365,8 @@ ACT = &getAnalysis(); auto &TLI = getAnalysis().getTLI(); + CG.registerCGReport(&Report); + SmallPtrSet SCCFunctions; DEBUG(dbgs() << "Inliner visiting SCC:"); for (CallGraphNode *Node : SCC) { @@ -383,14 +389,21 @@ for (CallGraphNode *Node : SCC) { Function *F = Node->getFunction(); if (!F) continue; + + getReport().addFunction(F, &CG.getModule()); for (BasicBlock &BB : *F) for (Instruction &I : BB) { CallSite CS(cast(&I)); // If this isn't a call, or it is a call to an intrinsic, it can // never be inlined. - if (!CS || isa(I)) + if (!CS) continue; + + getReport().addNewCallSite(F, &CS, &CG.getModule()); + if (isa(I)) { + continue; + } // If this is a direct call to an external function, we can never inline // it. If it is an indirect call, inlining may resolve it to be a @@ -406,8 +419,10 @@ DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n"); // If there are no calls in this function, exit early. - if (CallSites.empty()) + if (CallSites.empty()) { + getReport().makeAllNotCurrent(); return false; + } // Now that we have all of the call sites, move the ones to functions in the // current SCC to the end of the list. @@ -477,20 +492,27 @@ } // Attempt to inline the function. + InlineReportCallSite* IRCS = getReport().getCallSite(&CS); + Instruction* NI = CS.getInstruction(); + getReport().setActiveInlineInstruction(NI); if (!InlineCallIfPossible(*this, CS, InlineInfo, InlinedArrayAllocas, InlineHistoryID, InsertLifetime)) { + getReport().setActiveInlineInstruction(nullptr); emitOptimizationRemarkMissed(CallerCtx, DEBUG_TYPE, *Caller, DLoc, Twine(Callee->getName() + " will not be inlined into " + Caller->getName())); continue; } + getReport().setActiveInlineInstruction(nullptr); ++NumInlined; // Report the inline decision. emitOptimizationRemark( CallerCtx, DEBUG_TYPE, *Caller, DLoc, Twine(Callee->getName() + " inlined into " + Caller->getName())); + getReport().inlineCallSite(NI, IRCS, &CG.getModule(), Callee, + InlineInfo); // If inlining this function gave us any new call sites, throw them // onto our worklist to process. They are useful inline candidates. @@ -517,6 +539,7 @@ CG[Callee]->getNumReferences() == 0) { DEBUG(dbgs() << " -> Deleting dead function: " << Callee->getName() << "\n"); + getReport().setDead(Callee); CallGraphNode *CalleeNode = CG[Callee]; // Remove any call graph edges from the callee to its callees. @@ -543,14 +566,16 @@ LocalChange = true; } } while (LocalChange); - + getReport().makeAllNotCurrent(); return Changed; } /// Remove now-dead linkonce functions at the end of /// processing to avoid breaking the SCC traversal. bool Inliner::doFinalization(CallGraph &CG) { - return removeDeadFunctions(CG); + bool ReturnValue = removeDeadFunctions(CG); + getReport().print(); + return ReturnValue; } /// Remove dead functions that are not included in DNR (Do Not Remove) list. Index: lib/Transforms/Utils/InlineFunction.cpp =================================================================== --- lib/Transforms/Utils/InlineFunction.cpp +++ lib/Transforms/Utils/InlineFunction.cpp @@ -1099,6 +1099,7 @@ // If the call was inlined, but then constant folded, there is no edge to // add. Check for this case. + const Instruction *OldCall = dyn_cast(VMI->first); Instruction *NewCall = dyn_cast(VMI->second); if (!NewCall) continue; @@ -1106,11 +1107,16 @@ // We do not treat intrinsic calls like real function calls because we // expect them to become inline code; do not add an edge for an intrinsic. CallSite CS = CallSite(NewCall); - if (CS && CS.getCalledFunction() && CS.getCalledFunction()->isIntrinsic()) + if (CS && CS.getCalledFunction() && CS.getCalledFunction()->isIntrinsic()) { + IFI.OriginalCalls.push_back(OldCall); + IFI.InlinedCalls.push_back(NewCall); continue; + } // Remember that this call site got inlined for the client of // InlineFunction. + + IFI.OriginalCalls.push_back(OldCall); IFI.InlinedCalls.push_back(NewCall); // It's possible that inlining the callsite will cause it to go from an