TransformUtils: Introduce module splitter.

[pcc]

Summary

The module splitter splits a module into linkable partitions. It will
be used to implement parallel LTO code generation.

This initial version of the splitter does not attempt to deal with the
somewhat subtle symbol visibility issues around module splitting. These
will be dealt with in a future change.

[mehdi_amini]

Hi Peter,

I wonder if we can't make the split really more efficient, especially memory wise. Ideally we should seek to:

• Limit looping over the module content
• Move content instead of duplicating it.

This is especially important since LTO deals with very large module.
So reusing the cloneModule() implementation is clever and nicely done, but on the long term I'm not sure it is the way to go. I can imagine many speed/memory improvements that could be done by splitting a Module in N partitions in one pass.
So I wonder: if we want to really productize this, I'm not sure that the current code sharing/intrusion in cloneModule() is the right way to go. What do you think?

If you still want to move forward with this patch as is for now, you may find some thoughts about the patch inline.

include/llvm/Transforms/Utils/SplitModule.h

32

What about adding a warning/todo/fixme about "some subtle symbol visibility issues" that have to be fixed?
(I notices you mention it'll be fixed later)

34

A function that "Split a Module in N partition" is very valuable. I'm not necessarily convinced that the interface doesn't intermix two different things:

• Splitting the module
• What to do with the partitions (including issuing threads, etc.)

What about providing the API that only cares about the actual split here?
(I understand that it does not provide some pipeline where the first thread starts before the other partitions are created, but still)

std::vector<std::unique_ptr<Module>> SplitModule(std::unique_ptr<Module> M, unsigned N);

std::vector<std::unique_ptr<Module>> SplitModule(std::unique_ptr<Module> M, unsigned N, std::function<unsigned(GlobalValue &GV)> PartitionSelection);

Where the callback allows the caller to control the partition logic.
The first one could call the second one with your current modulo-hash partition method as a callback.

Also if the Module is left in an undetermined state, the caller won't be able to do anything with it but destroying it, so we might better take ownership of it anyway. It might be possible to re-use it for partition 0 and save one clone?

lib/Transforms/Utils/CloneModule.cpp

41

I would found the callback call sites more readable with a name like "ShouldCloneDefinition", because "CloneDefinition" makes me think it will actually Clone something.
(just an opinion, feel free to do whatever seems best for you)

94

Function attributes are not required for correctness? I'm unsure about that.

lib/Transforms/Utils/SplitModule.cpp

37

Minor comment: the file is lib/Transforms/Utils/SplitModule.cpp but the name includes "lto"
Some context is leaking ;-)

tools/llvm-split/llvm-split.cpp

51

Not sure why the lambda needs to capture by copy?

[pcc]

• Address review comments

[pcc]

In D12132#227433, @joker.eph wrote:

Hi Peter,

I wonder if we can't make the split really more efficient, especially memory wise. Ideally we should seek to:

• Limit looping over the module content
• Move content instead of duplicating it.

This is especially important since LTO deals with very large module.
So reusing the cloneModule() implementation is clever and nicely done, but on the long term I'm not sure it is the way to go. I can imagine many speed/memory improvements that could be done by splitting a Module in N partitions in one pass.

I agree with all of this, and I'd be interested in exploring any ideas around making this more efficient, but at the very least I think it would be useful to have this in the tree as a benchmark of comparison against more efficient approaches. I suppose the question is what the best way of structuring this code would be given that we intend to replace parts of it with a better design later.

So I wonder: if we want to really productize this, I'm not sure that the current code sharing/intrusion in cloneModule() is the right way to go. What do you think?

Whichever component we replace cloneModule() with will basically need to solve the same problem of providing some way to partition the module. It should be simple to revert the change to cloneModule() later once we have something more reasonable; it should mostly be a matter of constant folding the calls to ShouldCloneDefinition.

include/llvm/Transforms/Utils/SplitModule.h

32

Done

34

I found that pipelining can give a significant performance boost -- on my machine it can take around 40 seconds to create each partition for Chromium -- so I'd like to find a way to keep it if possible. I came up with a new design for the API that avoids this function having to deal with threads, which I've implemented in the new patch.

Regarding the partition selection callback, I would suggest that we hold back on that until there is a use case for it.

Also if the Module is left in an undetermined state, the caller won't be able to do anything with it but destroying it, so we might better take ownership of it anyway.

Done, but D12205 will be needed later for the code generator.

It might be possible to re-use it for partition 0 and save one clone?

Yes, good point, that should be possible. I've added a FIXME.

lib/Transforms/Utils/CloneModule.cpp

41

Done

94

Yes, hence "generally". Note that this is for external references only. Thread-local variables are the only case that springs to mind where attributes matter. But it turns out that aliases of thread-local variables are broken anyway:

$ cat tl1.ll
@x = thread_local global i32 0
@y = alias i32* @x

define void @f() {
  store i32 42, i32* @x
  store i32 42, i32* @y
  ret void
}
$ ~/src/llvm-build-rel/bin/llc -o - tl1.ll -mtriple=x86_64-pc-win32
	.text
	.def	 f;
	.scl	2;
	.type	32;
	.endef
	.globl	f
	.align	16, 0x90
f:                                      # @f
.Ltmp0:
.seh_proc f
# BB#0:
.Ltmp1:
	.seh_endprologue
	movl	_tls_index(%rip), %eax
	movq	%gs:88, %rcx
	movq	(%rcx,%rax,8), %rax
	movl	$42, x@SECREL32(%rax)
	movl	$42, y(%rip)
	retq
.Ltmp2:
	.seh_endproc

	.section	.tls$,"dw"
	.globl	x                       # @x
	.align	4
x:
	.long	0                       # 0x0


	.globl	y
y = x
$ ~/src/llvm-build-rel/bin/llc -o - tl1.ll -mtriple=x86_64-unknown-linux
	.text
	.file	"tl1.ll"
	.globl	f
	.align	16, 0x90
	.type	f,@function
f:                                      # @f
	.cfi_startproc
# BB#0:
	movl	$42, %fs:x@TPOFF
	movl	$42, y(%rip)
	retq
.Lfunc_end0:
	.size	f, .Lfunc_end0-f
	.cfi_endproc

	.type	x,@object               # @x
	.section	.tbss,"awT",@nobits
	.globl	x
	.align	4
x:
	.long	0                       # 0x0
	.size	x, 4


	.globl	y
y = x
	.section	".note.GNU-stack","",@progbits
$ ~/src/llvm-build-rel/bin/llc -o - tl1.ll -mtriple=x86_64-apple-darwin
	.section	__TEXT,__text,regular,pure_instructions
	.globl	_f
	.align	4, 0x90
_f:                                     ## @f
	.cfi_startproc
## BB#0:
	pushq	%rax
Ltmp0:
	.cfi_def_cfa_offset 16
	movq	_x@TLVP(%rip), %rdi
	callq	*(%rdi)
	movl	$42, (%rax)
	movl	$42, _y(%rip)
	popq	%rax
	retq
	.cfi_endproc

.tbss _x$tlv$init, 4, 2                 ## @x

	.section	__DATA,__thread_vars,thread_local_variables
	.globl	_x
_x:
	.quad	__tlv_bootstrap
	.quad	0
	.quad	_x$tlv$init


	.globl	_y
_y = _x
.subsections_via_symbols

lib/Transforms/Utils/SplitModule.cpp

37

Fixed

tools/llvm-split/llvm-split.cpp

51

This protected against the possibility of std::string (OutName) not being thread safe, but with the API change this is no longer needed.

[pcc]

lib/Transforms/Utils/CloneModule.cpp

94

I spoke too soon. Looks like aliases can be thread-local, and their thread-localness is a property of the alias rather than being inherited from the aliasee. That seems really bizarre. But in any case we are copying the thread-local property from the alias, so we are fine as far as thread-localness goes.

[pcc]

• Remove unneeded dependency, rename CloneDefinition -> ShouldCloneDefinition, add makefile

[pcc]

• Update test

[mehdi_amini]

LGTM!

tools/llvm-split/llvm-split.cpp

51

Why is this needed at all? Can't the lambda reference OutputFilename directly?

[pcc]

tools/llvm-split/llvm-split.cpp

51

Just a leftover from the old code; removed.

include/llvm/Transforms/Utils/Cloning.h

 #ifndef LLVM_TRANSFORMS_UTILS_CLONING_H
 #define LLVM_TRANSFORMS_UTILS_CLONING_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
+#include <functional>
 
 namespace llvm {
 
 class Module;
 class Function;
 class Instruction;
 class Pass;
 class LPPassManager;

 class AssumptionCacheTracker;
 class DominatorTree;
 
 /// CloneModule - Return an exact copy of the specified module
 ///
 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<bool(const GlobalValue *)> CloneDefinition);
+
 /// ClonedCodeInfo - This struct can be used to capture information about code
 /// being cloned, while it is being cloned.
 struct ClonedCodeInfo {
   /// ContainsCalls - This is set to true if the cloned code contains a normal
   /// call instruction.
   bool ContainsCalls;
 
   /// ContainsDynamicAllocas - This is set to true if the cloned code contains

include/llvm/Transforms/Utils/SplitModule.h

+//===- 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 <functional>
+
+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<void(unsigned I, StringRef BC)> ModuleCallback);
+
+} // End llvm namespace
+
+#endif

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   MetaRenamer.cpp
   ModuleUtils.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp
   SimplifyLibCalls.cpp
+  SplitModule.cpp
   SymbolRewriter.cpp
   UnifyFunctionExitNodes.cpp
   Utils.cpp
   ValueMapper.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Utils
   )
 
 add_dependencies(LLVMTransformUtils intrinsics_gen)

lib/Transforms/Utils/CloneModule.cpp

 Module *llvm::CloneModule(const Module *M) {
   // Create the value map that maps things from the old module over to the new
   // module.
   ValueToValueMapTy VMap;
   return CloneModule(M, VMap);
 }
 
 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<bool(const GlobalValue *)> CloneDefinition) {
   // First off, we need to create the new module.
   Module *New = new Module(M->getModuleIdentifier(), M->getContext());
   New->setDataLayout(M->getDataLayout());
   New->setTargetTriple(M->getTargetTriple());
   New->setModuleInlineAsm(M->getModuleInlineAsm());
    
   // Loop over all of the global variables, making corresponding globals in the
   // new module.  Here we add them to the VMap and to the new Module.  We
Function *NF =
                        I->getLinkage(), I->getName(), New);
     NF->copyAttributesFrom(I);
     VMap[I] = NF;
   }
 
   // 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<FunctionType>(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<PointerType>(I->getType());
     auto *GA = GlobalAlias::create(PTy, I->getLinkage(), I->getName(), New);
     GA->copyAttributesFrom(I);
     VMap[I] = GA;
   }
   
   // Now that all of the things that global variable initializer can refer to
   // have been created, loop through and copy the global variable referrers
   // over...  We also set the attributes on the global now.
   //
   for (Module::const_global_iterator I = M->global_begin(), E = M->global_end();
        I != E; ++I) {
     GlobalVariable *GV = cast<GlobalVariable>(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));
   }
 
   // Similarly, copy over function bodies now...
   //
   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
     Function *F = cast<Function>(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();
            ++J) {
         DestI->setName(J->getName());
         VMap[J] = DestI++;
       }
 
       SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
       CloneFunctionInto(F, I, VMap, /*ModuleLevelChanges=*/true, Returns);
 
     }
 
     if (I->hasPersonalityFn())
       F->setPersonalityFn(MapValue(I->getPersonalityFn(), VMap));
   }
 
   // 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<GlobalAlias>(VMap[I]);
     if (const Constant *C = I->getAliasee())
       GA->setAliasee(MapValue(C, VMap));
   }
 
   // And named metadata....
   for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
          E = M->named_metadata_end(); I != E; ++I) {

lib/Transforms/Utils/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = TransformUtils
 parent = Transforms
-required_libraries = Analysis Core Support
+required_libraries = BitReader BitWriter Analysis Core Support

lib/Transforms/Utils/SplitModule.cpp

+//===- 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 <list>
+#include <thread>
+
+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<GlobalAlias>(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<void(unsigned I, StringRef BC)> ModuleCallback) {
+  for (Function &F : *M)
+    externalize(&F);
+  for (GlobalVariable &GV : M->globals())
+    externalize(&GV);
+  for (GlobalAlias &GA : M->aliases())
+    externalize(&GA);
+
+  std::vector<std::thread> Threads;
+  for (unsigned I = 0; I != N; ++I) {
+    ValueToValueMapTy VMap;
+    std::unique_ptr<Module> 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();
+}

test/CMakeLists.txt

set(LLVM_TEST_DEPENDS
           llvm-mcmarkup
           llvm-nm
           llvm-objdump
           llvm-profdata
           llvm-ranlib
           llvm-readobj
           llvm-rtdyld
           llvm-size
+          llvm-split
           llvm-symbolizer
           llvm-tblgen
           macho-dump
           opt
           FileCheck
           count
           not
           yaml-bench

test/lit.cfg

for pattern in [r"\bbugpoint\b(?!-)",
                 r"\bllvm-mcmarkup\b",
                 r"\bllvm-nm\b",
                 r"\bllvm-objdump\b",
                 r"\bllvm-profdata\b",
                 r"\bllvm-ranlib\b",
                 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",
                 NOJUNK + r"\bopt\b",
                 r"\bFileCheck\b",
                 r"\bobj2yaml\b",
                 r"\byaml2obj\b",
                 r"\byaml-bench\b",

test/tools/llvm-split/alias.ll

+; 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
+}

test/tools/llvm-split/comdat.ll

+; 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
+}

test/tools/llvm-split/function.ll

+; 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
+}

test/tools/llvm-split/global.ll

+; 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*)

test/tools/llvm-split/internal.ll

+; 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
+}

test/tools/llvm-split/unnamed.ll

+; 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
+}

tools/LLVMBuild.txt

  llvm-mc
  llvm-mcmarkup
  llvm-nm
  llvm-objdump
  llvm-pdbdump
  llvm-profdata
  llvm-rtdyld
  llvm-size
+ llvm-split
  macho-dump
  opt
  verify-uselistorder
 
 [component_0]
 type = Group
 name = Tools
 parent = $ROOT

tools/llvm-split/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  TransformUtils
+  Core
+  IRReader
+  Support
+  )
+
+add_llvm_tool(llvm-split
+  llvm-split.cpp
+  )

tools/llvm-split/LLVMBuild.txt

-;===- ./lib/Transforms/Utils/LLVMBuild.txt ---------------------*- Conf -*--===;
+;===- ./tools/llvm-split/LLVMBuild.txt -------------------------*- Conf -*--===;
 ;
 ;                     The LLVM Compiler Infrastructure
 ;
 ; This file is distributed under the University of Illinois Open Source
 ; License. See LICENSE.TXT for details.
 ;
 ;===------------------------------------------------------------------------===;
 ;
 ; This is an LLVMBuild description file for the components in this subdirectory.
 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [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

tools/llvm-split/llvm-split.cpp

+//===-- 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<std::string>
+InputFilename(cl::Positional, cl::desc("<input bitcode file>"),
+    cl::init("-"), cl::value_desc("filename"));
+
+static cl::opt<std::string>
+OutputFilename("o", cl::desc("Override output filename"),
+               cl::value_desc("filename"));
+
+static cl::opt<unsigned> 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<Module> 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<tool_output_file> 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;
+}