Index: include/llvm/Transforms/Utils/Cloning.h =================================================================== --- include/llvm/Transforms/Utils/Cloning.h +++ include/llvm/Transforms/Utils/Cloning.h @@ -23,6 +23,7 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueMap.h" #include "llvm/Transforms/Utils/ValueMapper.h" +#include namespace llvm { @@ -52,6 +53,13 @@ Module *CloneModule(const Module *M); Module *CloneModule(const Module *M, ValueToValueMapTy &VMap); +/// Return a copy of the specified module. The CloneDefinition function controls +/// whether a specific GlobalValue's definition is cloned. If the function +/// returns false, the module copy will contain an external reference in place +/// of the global definition. +Module *CloneModule(const Module *M, ValueToValueMapTy &VMap, + std::function CloneDefinition); + /// ClonedCodeInfo - This struct can be used to capture information about code /// being cloned, while it is being cloned. struct ClonedCodeInfo { Index: include/llvm/Transforms/Utils/SplitModule.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/SplitModule.h @@ -0,0 +1,38 @@ +//===- SplitModule.h - Split a module into partitions -----------*- 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 the function llvm::SplitModule, which splits a module +// into multiple linkable partitions. It can be used to implement parallel code +// generation for link-time optimization. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SPLITMODULE_H +#define LLVM_TRANSFORMS_UTILS_SPLITMODULE_H + +#include + +namespace llvm { + +class Module; +class StringRef; + +/// Splits the module M into N linkable parts. For each partition, a thread is +/// created which calls ModuleCallback with two arguments: I, the partition +/// identifier (between 0 and N-1) and BC, a bitcode serialized representation +/// of the I'th partition of the module. +/// +/// This function returns once all ModuleCallback threads have finished +/// execution. M is in an indeterminate state after this function is called. +void SplitModule(Module *M, unsigned N, + std::function ModuleCallback); + +} // End llvm namespace + +#endif Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ SimplifyIndVar.cpp SimplifyInstructions.cpp SimplifyLibCalls.cpp + SplitModule.cpp SymbolRewriter.cpp UnifyFunctionExitNodes.cpp Utils.cpp Index: lib/Transforms/Utils/CloneModule.cpp =================================================================== --- lib/Transforms/Utils/CloneModule.cpp +++ lib/Transforms/Utils/CloneModule.cpp @@ -33,6 +33,12 @@ } Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { + return CloneModule(M, VMap, [](const GlobalValue *GV) { return true; }); +} + +Module * +llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap, + std::function CloneDefinition) { // First off, we need to create the new module. Module *New = new Module(M->getModuleIdentifier(), M->getContext()); New->setDataLayout(M->getDataLayout()); @@ -68,6 +74,26 @@ // Loop over the aliases in the module for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); I != E; ++I) { + if (!CloneDefinition(I)) { + // An alias cannot act as an external reference, so we need to create + // either a function or a global variable depending on the value type. + // FIXME: Once pointee types are gone we can probably pick one or the + // other. + GlobalValue *GV; + if (I->getValueType()->isFunctionTy()) + GV = Function::Create(cast(I->getValueType()), + GlobalValue::ExternalLinkage, I->getName(), New); + else + GV = new GlobalVariable( + *New, I->getValueType(), false, GlobalValue::ExternalLinkage, + (Constant *)nullptr, I->getName(), (GlobalVariable *)nullptr, + I->getThreadLocalMode(), I->getType()->getAddressSpace()); + VMap[I] = GV; + // We do not copy attributes (mainly because copying between different + // kinds of globals is forbidden), but this is generally not required for + // correctness. + continue; + } auto *PTy = cast(I->getType()); auto *GA = GlobalAlias::create(PTy, I->getLinkage(), I->getName(), New); GA->copyAttributesFrom(I); @@ -81,6 +107,11 @@ for (Module::const_global_iterator I = M->global_begin(), E = M->global_end(); I != E; ++I) { GlobalVariable *GV = cast(VMap[I]); + if (!CloneDefinition(I)) { + // Skip after setting the correct linkage for an external reference. + GV->setLinkage(GlobalValue::ExternalLinkage); + continue; + } if (I->hasInitializer()) GV->setInitializer(MapValue(I->getInitializer(), VMap)); } @@ -89,6 +120,11 @@ // for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { Function *F = cast(VMap[I]); + if (!CloneDefinition(I)) { + // Skip after setting the correct linkage for an external reference. + F->setLinkage(GlobalValue::ExternalLinkage); + continue; + } if (!I->isDeclaration()) { Function::arg_iterator DestI = F->arg_begin(); for (Function::const_arg_iterator J = I->arg_begin(); J != I->arg_end(); @@ -109,6 +145,9 @@ // And aliases for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); I != E; ++I) { + // We already dealt with undefined aliases above. + if (!CloneDefinition(I)) + continue; GlobalAlias *GA = cast(VMap[I]); if (const Constant *C = I->getAliasee()) GA->setAliasee(MapValue(C, VMap)); Index: lib/Transforms/Utils/LLVMBuild.txt =================================================================== --- lib/Transforms/Utils/LLVMBuild.txt +++ lib/Transforms/Utils/LLVMBuild.txt @@ -19,4 +19,4 @@ type = Library name = TransformUtils parent = Transforms -required_libraries = Analysis Core Support +required_libraries = BitReader BitWriter Analysis Core Support Index: lib/Transforms/Utils/SplitModule.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/SplitModule.cpp @@ -0,0 +1,91 @@ +//===- SplitModule.cpp - Split a module into partitions -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the function llvm::SplitModule, which splits a module +// into multiple linkable partitions. It can be used to implement parallel code +// generation for link-time optimization. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/SplitModule.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/Bitcode/ReaderWriter.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/Support/MD5.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include +#include + +using namespace llvm; + +static void externalize(GlobalValue *GV) { + if (GV->hasLocalLinkage()) { + GV->setLinkage(GlobalValue::ExternalLinkage); + GV->setVisibility(GlobalValue::HiddenVisibility); + } + + // Unnamed entities must be named consistently between modules. setName will + // give a distinct name to each such entity. + if (!GV->hasName()) + GV->setName("__llvmlto_unnamed"); +} + +// Returns whether GV should be in partition (0-based) I of N. +static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N) { + if (auto GA = dyn_cast(GV)) + if (const GlobalObject *Base = GA->getBaseObject()) + GV = Base; + + StringRef Name; + if (const Comdat *C = GV->getComdat()) + Name = C->getName(); + else + Name = GV->getName(); + + // Partition by MD5 hash. We only need a few bits for evenness as the number + // of partitions will generally be in the 1-2 figure range; the low 16 bits + // are enough. + MD5 H; + MD5::MD5Result R; + H.update(Name); + H.final(R); + return (R[0] | (R[1] << 8)) % N == I; +} + +void llvm::SplitModule( + Module *M, unsigned N, + std::function ModuleCallback) { + for (Function &F : *M) + externalize(&F); + for (GlobalVariable &GV : M->globals()) + externalize(&GV); + for (GlobalAlias &GA : M->aliases()) + externalize(&GA); + + std::vector Threads; + for (unsigned I = 0; I != N; ++I) { + ValueToValueMapTy VMap; + std::unique_ptr NewM( + CloneModule(M, VMap, [=](const GlobalValue *GV) { + return isInPartition(GV, I, N); + })); + if (I != 0) + NewM->setModuleInlineAsm(""); + std::string BC; + raw_string_ostream OS(BC); + WriteBitcodeToFile(NewM.get(), OS); + OS.flush(); + + Threads.emplace_back(ModuleCallback, I, std::move(BC)); + } + + for (auto &&T : Threads) + T.join(); +} Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt +++ test/CMakeLists.txt @@ -46,6 +46,7 @@ llvm-readobj llvm-rtdyld llvm-size + llvm-split llvm-symbolizer llvm-tblgen macho-dump Index: test/lit.cfg =================================================================== --- test/lit.cfg +++ test/lit.cfg @@ -248,6 +248,7 @@ r"\bllvm-readobj\b", r"\bllvm-rtdyld\b", r"\bllvm-size\b", + r"\bllvm-split\b", r"\bllvm-tblgen\b", r"\bllvm-c-test\b", r"\bmacho-dump\b", Index: test/tools/llvm-split/alias.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/alias.ll @@ -0,0 +1,19 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +; CHECK0-DAG: @afoo = alias [2 x i8*]* @foo +; CHECK1-DAG: @afoo = external global [2 x i8*] +@afoo = alias [2 x i8*]* @foo + +; CHECK0-DAG: declare void @abar() +; CHECK1-DAG: @abar = alias void ()* @bar +@abar = alias void ()* @bar + +@foo = global [2 x i8*] [i8* bitcast (void ()* @bar to i8*), i8* bitcast (void ()* @abar to i8*)] + +define void @bar() { + store [2 x i8*] zeroinitializer, [2 x i8*]* @foo + store [2 x i8*] zeroinitializer, [2 x i8*]* @afoo + ret void +} Index: test/tools/llvm-split/comdat.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/comdat.ll @@ -0,0 +1,19 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +$foo = comdat any + +; CHECK0: define void @foo() +; CHECK1: declare void @foo() +define void @foo() comdat { + call void @bar() + ret void +} + +; CHECK0: define void @bar() +; CHECK1: declare void @bar() +define void @bar() comdat($foo) { + call void @foo() + ret void +} Index: test/tools/llvm-split/function.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/function.ll @@ -0,0 +1,17 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +; CHECK0: define void @foo() +; CHECK1: declare void @foo() +define void @foo() { + call void @bar() + ret void +} + +; CHECK0: declare void @bar() +; CHECK1: define void @bar() +define void @bar() { + call void @foo() + ret void +} Index: test/tools/llvm-split/global.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/global.ll @@ -0,0 +1,11 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +; CHECK0: @foo = global i8* bitcast +; CHECK1: @foo = external global i8* +@foo = global i8* bitcast (i8** @bar to i8*) + +; CHECK0: @bar = external global i8* +; CHECK1: @bar = global i8* bitcast +@bar = global i8* bitcast (i8** @foo to i8*) Index: test/tools/llvm-split/internal.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/internal.ll @@ -0,0 +1,17 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +; CHECK0: define hidden void @foo() +; CHECK1: declare hidden void @foo() +define internal void @foo() { + call void @bar() + ret void +} + +; CHECK0: declare void @bar() +; CHECK1: define void @bar() +define void @bar() { + call void @foo() + ret void +} Index: test/tools/llvm-split/unnamed.ll =================================================================== --- /dev/null +++ test/tools/llvm-split/unnamed.ll @@ -0,0 +1,31 @@ +; RUN: llvm-split -o %t %s +; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=CHECK0 %s +; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=CHECK1 %s + +; CHECK0: define hidden void @__llvmlto_unnamed() +; CHECK1: declare hidden void @__llvmlto_unnamed() +define internal void @0() { + ; CHECK0: call void @foo() + call void @foo() + ret void +} + +; CHECK0: declare hidden void @__llvmlto_unnamed1() +; CHECK1: define hidden void @__llvmlto_unnamed1() +define internal void @1() { + ; CHECK1: call void @foo() + ; CHECK1: call void @foo() + call void @foo() + call void @foo() + ret void +} + +; CHECK0: define void @foo() +; CHECK1: declare void @foo() +define void @foo() { + ; CHECK0: call void @__llvmlto_unnamed1() + ; CHECK0: call void @__llvmlto_unnamed() + call void @1() + call void @0() + ret void +} Index: tools/LLVMBuild.txt =================================================================== --- tools/LLVMBuild.txt +++ tools/LLVMBuild.txt @@ -40,6 +40,7 @@ llvm-profdata llvm-rtdyld llvm-size + llvm-split macho-dump opt verify-uselistorder Index: tools/llvm-split/CMakeLists.txt =================================================================== --- /dev/null +++ tools/llvm-split/CMakeLists.txt @@ -0,0 +1,10 @@ +set(LLVM_LINK_COMPONENTS + TransformUtils + Core + IRReader + Support + ) + +add_llvm_tool(llvm-split + llvm-split.cpp + ) Index: tools/llvm-split/LLVMBuild.txt =================================================================== --- tools/llvm-split/LLVMBuild.txt +++ tools/llvm-split/LLVMBuild.txt @@ -1,4 +1,4 @@ -;===- ./lib/Transforms/Utils/LLVMBuild.txt ---------------------*- Conf -*--===; +;===- ./tools/llvm-split/LLVMBuild.txt -------------------------*- Conf -*--===; ; ; The LLVM Compiler Infrastructure ; @@ -16,7 +16,7 @@ ;===------------------------------------------------------------------------===; [component_0] -type = Library -name = TransformUtils -parent = Transforms -required_libraries = Analysis Core Support +type = Tool +name = llvm-split +parent = Tools +required_libraries = TransformUtils BitWriter Core IRReader Support Index: tools/llvm-split/llvm-split.cpp =================================================================== --- /dev/null +++ tools/llvm-split/llvm-split.cpp @@ -0,0 +1,67 @@ +//===-- llvm-split: command line tool for testing module splitter ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This program can be used to test the llvm::SplitModule function. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/StringExtras.h" +#include "llvm/Bitcode/ReaderWriter.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IRReader/IRReader.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/ToolOutputFile.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/SplitModule.h" + +using namespace llvm; + +static cl::opt +InputFilename(cl::Positional, cl::desc(""), + cl::init("-"), cl::value_desc("filename")); + +static cl::opt +OutputFilename("o", cl::desc("Override output filename"), + cl::value_desc("filename")); + +static cl::opt NumOutputs("j", cl::Prefix, cl::init(2), + cl::desc("Number of output files")); + +int main(int argc, char **argv) { + LLVMContext &Context = getGlobalContext(); + SMDiagnostic Err; + cl::ParseCommandLineOptions(argc, argv, "LLVM module splitter\n"); + + std::unique_ptr M = parseIRFile(InputFilename, Err, Context); + + if (!M) { + Err.print(argv[0], errs()); + return 1; + } + + std::string OutName = OutputFilename; + SplitModule(M.get(), NumOutputs, [=](unsigned I, StringRef BC) { + std::error_code EC; + std::unique_ptr Out( + new tool_output_file(OutName + utostr(I), EC, sys::fs::F_None)); + if (EC) { + errs() << EC.message() << '\n'; + exit(1); + } + + Out->os() << BC; + + // Declare success. + Out->keep(); + }); + + return 0; +}