LLVM  13.0.0git
SplitModule.cpp
Go to the documentation of this file.
1 //===- SplitModule.cpp - Split a module into partitions -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the function llvm::SplitModule, which splits a module
10 // into multiple linkable partitions. It can be used to implement parallel code
11 // generation for link-time optimization.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/IR/Comdat.h"
22 #include "llvm/IR/Constant.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/GlobalAlias.h"
26 #include "llvm/IR/GlobalObject.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/User.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/MD5.h"
41 #include <algorithm>
42 #include <cassert>
43 #include <iterator>
44 #include <memory>
45 #include <queue>
46 #include <utility>
47 #include <vector>
48 
49 using namespace llvm;
50 
51 #define DEBUG_TYPE "split-module"
52 
53 namespace {
54 
55 using ClusterMapType = EquivalenceClasses<const GlobalValue *>;
56 using ComdatMembersType = DenseMap<const Comdat *, const GlobalValue *>;
57 using ClusterIDMapType = DenseMap<const GlobalValue *, unsigned>;
58 
59 } // end anonymous namespace
60 
61 static void addNonConstUser(ClusterMapType &GVtoClusterMap,
62  const GlobalValue *GV, const User *U) {
63  assert((!isa<Constant>(U) || isa<GlobalValue>(U)) && "Bad user");
64 
65  if (const Instruction *I = dyn_cast<Instruction>(U)) {
66  const GlobalValue *F = I->getParent()->getParent();
67  GVtoClusterMap.unionSets(GV, F);
68  } else if (isa<GlobalIndirectSymbol>(U) || isa<Function>(U) ||
69  isa<GlobalVariable>(U)) {
70  GVtoClusterMap.unionSets(GV, cast<GlobalValue>(U));
71  } else {
72  llvm_unreachable("Underimplemented use case");
73  }
74 }
75 
76 // Adds all GlobalValue users of V to the same cluster as GV.
77 static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap,
78  const GlobalValue *GV, const Value *V) {
79  for (auto *U : V->users()) {
81  Worklist.push_back(U);
82  while (!Worklist.empty()) {
83  const User *UU = Worklist.pop_back_val();
84  // For each constant that is not a GV (a pure const) recurse.
85  if (isa<Constant>(UU) && !isa<GlobalValue>(UU)) {
86  Worklist.append(UU->user_begin(), UU->user_end());
87  continue;
88  }
89  addNonConstUser(GVtoClusterMap, GV, UU);
90  }
91  }
92 }
93 
94 // Find partitions for module in the way that no locals need to be
95 // globalized.
96 // Try to balance pack those partitions into N files since this roughly equals
97 // thread balancing for the backend codegen step.
98 static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap,
99  unsigned N) {
100  // At this point module should have the proper mix of globals and locals.
101  // As we attempt to partition this module, we must not change any
102  // locals to globals.
103  LLVM_DEBUG(dbgs() << "Partition module with (" << M.size() << ")functions\n");
104  ClusterMapType GVtoClusterMap;
105  ComdatMembersType ComdatMembers;
106 
107  auto recordGVSet = [&GVtoClusterMap, &ComdatMembers](GlobalValue &GV) {
108  if (GV.isDeclaration())
109  return;
110 
111  if (!GV.hasName())
112  GV.setName("__llvmsplit_unnamed");
113 
114  // Comdat groups must not be partitioned. For comdat groups that contain
115  // locals, record all their members here so we can keep them together.
116  // Comdat groups that only contain external globals are already handled by
117  // the MD5-based partitioning.
118  if (const Comdat *C = GV.getComdat()) {
119  auto &Member = ComdatMembers[C];
120  if (Member)
121  GVtoClusterMap.unionSets(Member, &GV);
122  else
123  Member = &GV;
124  }
125 
126  // For aliases we should not separate them from their aliasees regardless
127  // of linkage.
128  if (auto *GIS = dyn_cast<GlobalIndirectSymbol>(&GV)) {
129  if (const GlobalObject *Base = GIS->getBaseObject())
130  GVtoClusterMap.unionSets(&GV, Base);
131  }
132 
133  if (const Function *F = dyn_cast<Function>(&GV)) {
134  for (const BasicBlock &BB : *F) {
136  if (!BA || !BA->isConstantUsed())
137  continue;
138  addAllGlobalValueUsers(GVtoClusterMap, F, BA);
139  }
140  }
141 
142  if (GV.hasLocalLinkage())
143  addAllGlobalValueUsers(GVtoClusterMap, &GV, &GV);
144  };
145 
146  llvm::for_each(M.functions(), recordGVSet);
147  llvm::for_each(M.globals(), recordGVSet);
148  llvm::for_each(M.aliases(), recordGVSet);
149 
150  // Assigned all GVs to merged clusters while balancing number of objects in
151  // each.
152  auto CompareClusters = [](const std::pair<unsigned, unsigned> &a,
153  const std::pair<unsigned, unsigned> &b) {
154  if (a.second || b.second)
155  return a.second > b.second;
156  else
157  return a.first > b.first;
158  };
159 
160  std::priority_queue<std::pair<unsigned, unsigned>,
161  std::vector<std::pair<unsigned, unsigned>>,
162  decltype(CompareClusters)>
163  BalancinQueue(CompareClusters);
164  // Pre-populate priority queue with N slot blanks.
165  for (unsigned i = 0; i < N; ++i)
166  BalancinQueue.push(std::make_pair(i, 0));
167 
168  using SortType = std::pair<unsigned, ClusterMapType::iterator>;
169 
172 
173  // To guarantee determinism, we have to sort SCC according to size.
174  // When size is the same, use leader's name.
175  for (ClusterMapType::iterator I = GVtoClusterMap.begin(),
176  E = GVtoClusterMap.end(); I != E; ++I)
177  if (I->isLeader())
178  Sets.push_back(
179  std::make_pair(std::distance(GVtoClusterMap.member_begin(I),
180  GVtoClusterMap.member_end()), I));
181 
182  llvm::sort(Sets, [](const SortType &a, const SortType &b) {
183  if (a.first == b.first)
184  return a.second->getData()->getName() > b.second->getData()->getName();
185  else
186  return a.first > b.first;
187  });
188 
189  for (auto &I : Sets) {
190  unsigned CurrentClusterID = BalancinQueue.top().first;
191  unsigned CurrentClusterSize = BalancinQueue.top().second;
192  BalancinQueue.pop();
193 
194  LLVM_DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size("
195  << I.first << ") ----> " << I.second->getData()->getName()
196  << "\n");
197 
198  for (ClusterMapType::member_iterator MI =
199  GVtoClusterMap.findLeader(I.second);
200  MI != GVtoClusterMap.member_end(); ++MI) {
201  if (!Visited.insert(*MI).second)
202  continue;
203  LLVM_DEBUG(dbgs() << "----> " << (*MI)->getName()
204  << ((*MI)->hasLocalLinkage() ? " l " : " e ") << "\n");
205  Visited.insert(*MI);
206  ClusterIDMap[*MI] = CurrentClusterID;
207  CurrentClusterSize++;
208  }
209  // Add this set size to the number of entries in this cluster.
210  BalancinQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize));
211  }
212 }
213 
214 static void externalize(GlobalValue *GV) {
215  if (GV->hasLocalLinkage()) {
218  }
219 
220  // Unnamed entities must be named consistently between modules. setName will
221  // give a distinct name to each such entity.
222  if (!GV->hasName())
223  GV->setName("__llvmsplit_unnamed");
224 }
225 
226 // Returns whether GV should be in partition (0-based) I of N.
227 static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N) {
228  if (auto *GIS = dyn_cast<GlobalIndirectSymbol>(GV))
229  if (const GlobalObject *Base = GIS->getBaseObject())
230  GV = Base;
231 
232  StringRef Name;
233  if (const Comdat *C = GV->getComdat())
234  Name = C->getName();
235  else
236  Name = GV->getName();
237 
238  // Partition by MD5 hash. We only need a few bits for evenness as the number
239  // of partitions will generally be in the 1-2 figure range; the low 16 bits
240  // are enough.
241  MD5 H;
242  MD5::MD5Result R;
243  H.update(Name);
244  H.final(R);
245  return (R[0] | (R[1] << 8)) % N == I;
246 }
247 
249  Module &M, unsigned N,
250  function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback,
251  bool PreserveLocals) {
252  if (!PreserveLocals) {
253  for (Function &F : M)
254  externalize(&F);
255  for (GlobalVariable &GV : M.globals())
256  externalize(&GV);
257  for (GlobalAlias &GA : M.aliases())
258  externalize(&GA);
259  for (GlobalIFunc &GIF : M.ifuncs())
260  externalize(&GIF);
261  }
262 
263  // This performs splitting without a need for externalization, which might not
264  // always be possible.
265  ClusterIDMapType ClusterIDMap;
266  findPartitions(M, ClusterIDMap, N);
267 
268  // FIXME: We should be able to reuse M as the last partition instead of
269  // cloning it. Note that the callers at the moment expect the module to
270  // be preserved, so will need some adjustments as well.
271  for (unsigned I = 0; I < N; ++I) {
272  ValueToValueMapTy VMap;
273  std::unique_ptr<Module> MPart(
274  CloneModule(M, VMap, [&](const GlobalValue *GV) {
275  if (ClusterIDMap.count(GV))
276  return (ClusterIDMap[GV] == I);
277  else
278  return isInPartition(GV, I, N);
279  }));
280  if (I != 0)
281  MPart->setModuleInlineAsm("");
282  ModuleCallback(std::move(MPart));
283  }
284 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:102
llvm
Definition: AllocatorList.h:23
GlobalIndirectSymbol.h
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
Comdat.h
ValueMapper.h
llvm::GlobalValue::HiddenVisibility
@ HiddenVisibility
The GV is hidden.
Definition: GlobalValue.h:64
return
return
Definition: README.txt:242
llvm::Function
Definition: Function.h:61
StringRef.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:58
llvm::Value::hasName
bool hasName() const
Definition: Value.h:262
ErrorHandling.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::GlobalAlias
Definition: GlobalAlias.h:27
externalize
static void externalize(GlobalValue *GV)
Definition: SplitModule.cpp:214
DenseMap.h
Module.h
addAllGlobalValueUsers
static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const Value *V)
Definition: SplitModule.cpp:77
findPartitions
static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap, unsigned N)
Definition: SplitModule.cpp:98
GlobalObject.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:398
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction.h
GlobalValue.h
Constants.h
MD5.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:647
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GlobalObject
Definition: GlobalObject.h:28
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
SplitModule.h
llvm::Instruction
Definition: Instruction.h:45
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:361
SmallPtrSet.h
llvm::Comdat
Definition: Comdat.h:31
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:406
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1475
addNonConstUser
static void addNonConstUser(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const User *U)
Definition: SplitModule.cpp:61
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::MD5
Definition: MD5.h:41
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:847
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::MD5::MD5Result
Definition: MD5.h:55
Constant.h
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
H
#define H(x, y, z)
Definition: MD5.cpp:58
GlobalVariable.h
llvm::GlobalValue::getComdat
const Comdat * getComdat() const
Definition: Globals.cpp:172
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
EquivalenceClasses.h
GlobalAlias.h
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
SmallVector.h
User.h
llvm::CloneModule
std::unique_ptr< Module > CloneModule(const Module &M)
Return an exact copy of the specified module.
Definition: CloneModule.cpp:34
N
#define N
isInPartition
static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N)
Definition: SplitModule.cpp:227
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::BlockAddress::lookup
static BlockAddress * lookup(const BasicBlock *BB)
Lookup an existing BlockAddress constant for the given BasicBlock.
Definition: Constants.cpp:1839
llvm::Constant::isConstantUsed
bool isConstantUsed() const
Return true if the constant has users other than constant expressions and other dangling things.
Definition: Constants.cpp:647
raw_ostream.h
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:32
llvm::SplitModule
void SplitModule(Module &M, unsigned N, function_ref< void(std::unique_ptr< Module > MPart)> ModuleCallback, bool PreserveLocals=false)
Splits the module M into N linkable partitions.
Definition: SplitModule.cpp:248
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:235
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364