From a7649e87bb21bc913ae78a399a35354866b8dd72 Mon Sep 17 00:00:00 2001 From: Mehdi Amini Date: Tue, 24 Nov 2015 06:07:49 +0000 Subject: [PATCH] Add a FunctionImporter helper to perform summary-based cross-module function importing Summary: This is a helper to perform cross-module import for ThinLTO. Right now it is importing naively every possible called functions. Reviewers: tejohnson Subscribers: dexonsmith, llvm-commits Differential Revision: http://reviews.llvm.org/D14914 From: Mehdi Amini git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253954 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/InitializePasses.h | 1 + include/llvm/Transforms/IPO/FunctionImport.h | 51 ++++ lib/Transforms/IPO/CMakeLists.txt | 1 + lib/Transforms/IPO/FunctionImport.cpp | 239 ++++++++++++++++++ lib/Transforms/IPO/IPO.cpp | 1 + lib/Transforms/IPO/LLVMBuild.txt | 2 +- .../FunctionImport/Inputs/funcimport.ll | 93 +++++++ test/Transforms/FunctionImport/funcimport.ll | 42 +++ 8 files changed, 429 insertions(+), 1 deletion(-) create mode 100644 include/llvm/Transforms/IPO/FunctionImport.h create mode 100644 lib/Transforms/IPO/FunctionImport.cpp create mode 100644 test/Transforms/FunctionImport/Inputs/funcimport.ll create mode 100644 test/Transforms/FunctionImport/funcimport.ll diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index cdd2ba235e4..29c8b27db36 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -302,6 +302,7 @@ void initializeSjLjEHPreparePass(PassRegistry&); void initializeDemandedBitsPass(PassRegistry&); void initializeFuncletLayoutPass(PassRegistry &); void initializeLoopLoadEliminationPass(PassRegistry&); +void initializeFunctionImportPassPass(PassRegistry &); } #endif diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h new file mode 100644 index 00000000000..f06a1902175 --- /dev/null +++ b/include/llvm/Transforms/IPO/FunctionImport.h @@ -0,0 +1,51 @@ +//===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUNCTIONIMPORT_H +#define LLVM_FUNCTIONIMPORT_H + +#include "llvm/IR/DiagnosticInfo.h" +#include "llvm/ADT/StringMap.h" + +namespace llvm { +class LLVMContext; +class Module; +class FunctionInfoIndex; + +/// The function importer is automatically importing function from other modules +/// based on the provided summary informations. +class FunctionImporter { + + /// Cache of lazily loaded module for import. + StringMap> ModuleMap; + + /// The context that will be used for importing. + LLVMContext &Context; + + /// The summaries index used to trigger importing. + const FunctionInfoIndex &Index; + + /// Diagnostic will be sent to this handler. + DiagnosticHandlerFunction DiagnosticHandler; + + /// Retrieve a Module from the cache or lazily load it on demand. + Module &getOrLoadModule(StringRef FileName); + +public: + /// Create a Function Importer. + FunctionImporter(LLVMContext &Context, const FunctionInfoIndex &Index, + DiagnosticHandlerFunction DiagnosticHandler) + : Context(Context), Index(Index), DiagnosticHandler(DiagnosticHandler) {} + + /// Import functions in Module \p M based on the summary informations. + bool importFunctions(Module &M); +}; +} + +#endif // LLVM_FUNCTIONIMPORT_H diff --git a/lib/Transforms/IPO/CMakeLists.txt b/lib/Transforms/IPO/CMakeLists.txt index 8c777548137..ba77477f137 100644 --- a/lib/Transforms/IPO/CMakeLists.txt +++ b/lib/Transforms/IPO/CMakeLists.txt @@ -6,6 +6,7 @@ add_llvm_library(LLVMipo ElimAvailExtern.cpp ExtractGV.cpp FunctionAttrs.cpp + FunctionImport.cpp GlobalDCE.cpp GlobalOpt.cpp IPConstantPropagation.cpp diff --git a/lib/Transforms/IPO/FunctionImport.cpp b/lib/Transforms/IPO/FunctionImport.cpp new file mode 100644 index 00000000000..725796790ea --- /dev/null +++ b/lib/Transforms/IPO/FunctionImport.cpp @@ -0,0 +1,239 @@ +//===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements Function import based on summaries. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/FunctionImport.h" + +#include "llvm/ADT/StringSet.h" +#include "llvm/IR/AutoUpgrade.h" +#include "llvm/IR/DiagnosticPrinter.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/IRReader/IRReader.h" +#include "llvm/Linker/Linker.h" +#include "llvm/Object/FunctionIndexObjectFile.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/SourceMgr.h" +using namespace llvm; + +#define DEBUG_TYPE "function-import" + +// Load lazily a module from \p FileName in \p Context. +static std::unique_ptr loadFile(const std::string &FileName, + LLVMContext &Context) { + SMDiagnostic Err; + DEBUG(dbgs() << "Loading '" << FileName << "'\n"); + std::unique_ptr Result = getLazyIRFileModule(FileName, Err, Context); + if (!Result) { + Err.print("function-import", errs()); + return nullptr; + } + + Result->materializeMetadata(); + UpgradeDebugInfo(*Result); + + return Result; +} + +// Get a Module for \p FileName from the cache, or load it lazily. +Module &FunctionImporter::getOrLoadModule(StringRef FileName) { + auto &Module = ModuleMap[FileName]; + if (!Module) + Module = loadFile(FileName, Context); + return *Module; +} + +// Automatically import functions in Module \p M based on the summaries index. +// +// The current implementation imports every called functions that exists in the +// summaries index. +bool FunctionImporter::importFunctions(Module &M) { + assert(&Context == &M.getContext()); + + bool Changed = false; + + /// First step is collecting the called functions and the one defined in this + /// module. + StringSet<> CalledFunctions; + for (auto &F : M) { + if (F.isDeclaration() || F.hasFnAttribute(Attribute::OptimizeNone)) + continue; + for (auto &BB : F) { + for (auto &I : BB) { + if (isa(I)) { + DEBUG(dbgs() << "Found a call: '" << I << "'\n"); + auto CalledFunction = cast(I).getCalledFunction(); + if (CalledFunction && CalledFunction->hasName() && + CalledFunction->isDeclaration()) + CalledFunctions.insert(CalledFunction->getName()); + } + } + } + } + + /// Second step: for every call to an external function, try to import it. + + // Linker that will be used for importing function + Linker L(&M, DiagnosticHandler); + + /// Insert initial called function set in a worklist, so that we can add + /// transively called functions when importing. + SmallVector Worklist; + for (auto &CalledFunction : CalledFunctions) + Worklist.push_back(CalledFunction.first()); + + while (!Worklist.empty()) { + auto CalledFunctionName = Worklist.pop_back_val(); + DEBUG(dbgs() << "Process import for " << CalledFunctionName << "\n"); + + // Try to get a summary for this function call. + auto InfoList = Index.findFunctionInfoList(CalledFunctionName); + if (InfoList == Index.end()) { + DEBUG(dbgs() << "No summary for " << CalledFunctionName + << " Ignoring.\n"); + continue; + } + assert(!InfoList->second.empty() && "No summary, error at import?"); + + // Comdat can have multiple entries, FIXME: what do we do with them? + auto &Info = InfoList->second[0]; + assert(Info && "Nullptr in list, error importing summaries?\n"); + + auto *Summary = Info->functionSummary(); + if (!Summary) { + // FIXME: in case we are lazyloading summaries, we can do it now. + dbgs() << "Missing summary for " << CalledFunctionName + << ", error at import?\n"; + llvm_unreachable("Missing summary"); + } + + // + // No profitability notion right now, just import all the time... + // + + // Get the module path from the summary. + auto FileName = Summary->modulePath(); + DEBUG(dbgs() << "Importing " << CalledFunctionName << " from " << FileName + << "\n"); + + // Get the module for the import (potentially from the cache). + auto &Module = getOrLoadModule(FileName); + + // The function that we will import! + GlobalValue *SGV = Module.getNamedValue(CalledFunctionName); + Function *F = dyn_cast(SGV); + if (!F && isa(SGV)) { + auto *SGA = dyn_cast(SGV); + F = dyn_cast(SGA->getBaseObject()); + } + if (!F) { + errs() << "Can't load function '" << CalledFunctionName << "' in Module '" + << FileName << "', error in the summary?\n"; + llvm_unreachable("Can't load function in Module"); + } + + // We cannot import weak_any functions without possibly affecting the + // order they are seen and selected by the linker, changing program + // semantics. + if (F->hasWeakAnyLinkage()) { + DEBUG(dbgs() << "Ignoring import request for weak-any function " + << CalledFunctionName << " from " << FileName << "\n"); + continue; + } + + // Link in the specified function. + if (L.linkInModule(&Module, Linker::Flags::None, &Index, F)) + report_fatal_error("Function Import: link error"); + + // TODO: Process the newly imported function and add callees to the + // worklist. + + Changed = true; + } + return Changed; +} + +/// Summary file to use for function importing when using -function-import from +/// the command line. +static cl::opt + SummaryFile("summary-file", + cl::desc("The summary file to use for function importing.")); + +static void diagnosticHandler(const DiagnosticInfo &DI) { + raw_ostream &OS = errs(); + DiagnosticPrinterRawOStream DP(OS); + DI.print(DP); + OS << '\n'; +} + +/// Parse the function index out of an IR file and return the function +/// index object if found, or nullptr if not. +static std::unique_ptr +getFunctionIndexForFile(StringRef Path, std::string &Error, + DiagnosticHandlerFunction DiagnosticHandler) { + std::unique_ptr Buffer; + ErrorOr> BufferOrErr = + MemoryBuffer::getFile(Path); + if (std::error_code EC = BufferOrErr.getError()) { + Error = EC.message(); + return nullptr; + } + Buffer = std::move(BufferOrErr.get()); + ErrorOr> ObjOrErr = + object::FunctionIndexObjectFile::create(Buffer->getMemBufferRef(), + DiagnosticHandler); + if (std::error_code EC = ObjOrErr.getError()) { + Error = EC.message(); + return nullptr; + } + return (*ObjOrErr)->takeIndex(); +} + +/// Pass that performs cross-module function import provided a summary file. +class FunctionImportPass : public ModulePass { + +public: + /// Pass identification, replacement for typeid + static char ID; + + explicit FunctionImportPass() : ModulePass(ID) {} + + bool runOnModule(Module &M) override { + if (SummaryFile.empty()) { + report_fatal_error("error: -function-import requires -summary-file\n"); + } + std::string Error; + std::unique_ptr Index = + getFunctionIndexForFile(SummaryFile, Error, diagnosticHandler); + if (!Index) { + errs() << "Error loading file '" << SummaryFile << "': " << Error << "\n"; + return false; + } + + // Perform the import now. + FunctionImporter Importer(M.getContext(), *Index, diagnosticHandler); + return Importer.importFunctions(M); + + return false; + } +}; + +char FunctionImportPass::ID = 0; +INITIALIZE_PASS_BEGIN(FunctionImportPass, "function-import", + "Summary Based Function Import", false, false) +INITIALIZE_PASS_END(FunctionImportPass, "function-import", + "Summary Based Function Import", false, false) + +namespace llvm { +Pass *createFunctionImportPass() { return new FunctionImportPass(); } +} diff --git a/lib/Transforms/IPO/IPO.cpp b/lib/Transforms/IPO/IPO.cpp index 97e45843682..379af30c5d3 100644 --- a/lib/Transforms/IPO/IPO.cpp +++ b/lib/Transforms/IPO/IPO.cpp @@ -48,6 +48,7 @@ void llvm::initializeIPO(PassRegistry &Registry) { initializeBarrierNoopPass(Registry); initializeEliminateAvailableExternallyPass(Registry); initializeSampleProfileLoaderPass(Registry); + initializeFunctionImportPassPass(Registry); } void LLVMInitializeIPO(LLVMPassRegistryRef R) { diff --git a/lib/Transforms/IPO/LLVMBuild.txt b/lib/Transforms/IPO/LLVMBuild.txt index 2311e276f75..c14b6b70e74 100644 --- a/lib/Transforms/IPO/LLVMBuild.txt +++ b/lib/Transforms/IPO/LLVMBuild.txt @@ -20,4 +20,4 @@ type = Library name = IPO parent = Transforms library_name = ipo -required_libraries = Analysis Core InstCombine ProfileData Scalar Support TransformUtils Vectorize +required_libraries = Analysis Core InstCombine Linker ProfileData Scalar Support TransformUtils Vectorize diff --git a/test/Transforms/FunctionImport/Inputs/funcimport.ll b/test/Transforms/FunctionImport/Inputs/funcimport.ll new file mode 100644 index 00000000000..c0298b55ea4 --- /dev/null +++ b/test/Transforms/FunctionImport/Inputs/funcimport.ll @@ -0,0 +1,93 @@ +@globalvar = global i32 1, align 4 +@staticvar = internal global i32 1, align 4 +@staticconstvar = internal unnamed_addr constant [2 x i32] [i32 10, i32 20], align 4 +@commonvar = common global i32 0, align 4 +@P = internal global void ()* null, align 8 + +@weakalias = weak alias void (...), bitcast (void ()* @globalfunc1 to void (...)*) +@analias = alias void (...), bitcast (void ()* @globalfunc2 to void (...)*) +@linkoncealias = alias void (...), bitcast (void ()* @linkoncefunc to void (...)*) + +define void @globalfunc1() #0 { +entry: + ret void +} + +define void @globalfunc2() #0 { +entry: + ret void +} + +define linkonce_odr void @linkoncefunc() #0 { +entry: + ret void +} + +define i32 @referencestatics(i32 %i) #0 { +entry: + %i.addr = alloca i32, align 4 + store i32 %i, i32* %i.addr, align 4 + %call = call i32 @staticfunc() + %0 = load i32, i32* @staticvar, align 4 + %add = add nsw i32 %call, %0 + %1 = load i32, i32* %i.addr, align 4 + %idxprom = sext i32 %1 to i64 + %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* @staticconstvar, i64 0, i64 %idxprom + %2 = load i32, i32* %arrayidx, align 4 + %add1 = add nsw i32 %add, %2 + ret i32 %add1 +} + +define i32 @referenceglobals(i32 %i) #0 { +entry: + %i.addr = alloca i32, align 4 + store i32 %i, i32* %i.addr, align 4 + call void @globalfunc1() + %0 = load i32, i32* @globalvar, align 4 + ret i32 %0 +} + +define i32 @referencecommon(i32 %i) #0 { +entry: + %i.addr = alloca i32, align 4 + store i32 %i, i32* %i.addr, align 4 + %0 = load i32, i32* @commonvar, align 4 + ret i32 %0 +} + +define void @setfuncptr() #0 { +entry: + store void ()* @staticfunc2, void ()** @P, align 8 + ret void +} + +define void @callfuncptr() #0 { +entry: + %0 = load void ()*, void ()** @P, align 8 + call void %0() + ret void +} + +@weakvar = weak global i32 1, align 4 +define weak void @weakfunc() #0 { +entry: + ret void +} + +define void @callweakfunc() #0 { +entry: + call void @weakfunc() + ret void +} + +define internal i32 @staticfunc() #0 { +entry: + ret i32 1 +} + +define internal void @staticfunc2() #0 { +entry: + ret void +} + + diff --git a/test/Transforms/FunctionImport/funcimport.ll b/test/Transforms/FunctionImport/funcimport.ll new file mode 100644 index 00000000000..c9a376aca53 --- /dev/null +++ b/test/Transforms/FunctionImport/funcimport.ll @@ -0,0 +1,42 @@ +; Do setup work for all below tests: generate bitcode and combined index +; RUN: llvm-as -function-summary %s -o %t.bc +; RUN: llvm-as -function-summary %p/Inputs/funcimport.ll -o %t2.bc +; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc + +; Do the import now +; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -S | FileCheck %s + +define i32 @main() #0 { +entry: + call void (...) @weakalias() + call void (...) @analias() + %call = call i32 (...) @referencestatics() + %call1 = call i32 (...) @referenceglobals() + %call2 = call i32 (...) @referencecommon() + call void (...) @setfuncptr() + call void (...) @callfuncptr() + call void (...) @callweakfunc() + ret i32 0 +} + +; Won't import alias +declare void @weakalias(...) #1 +declare void @analias(...) #1 + +; CHECK-DAG: define available_externally i32 @referencestatics(i32 %i) +declare i32 @referencestatics(...) #1 + +; CHECK-DAG: define available_externally i32 @referenceglobals(i32 %i) +declare i32 @referenceglobals(...) #1 + +; CHECK-DAG: define available_externally i32 @referencecommon(i32 %i) +declare i32 @referencecommon(...) #1 + +; CHECK-DAG: define available_externally void @setfuncptr() +declare void @setfuncptr(...) #1 + +; CHECK-DAG: define available_externally void @callfuncptr() +declare void @callfuncptr(...) #1 + +; Won't import weak func +declare void @callweakfunc(...) #1 -- 2.34.1