LLVM  14.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<GlobalAlias>(&GV)) {
129  if (const GlobalObject *Base = GIS->getBaseObject())
130  GVtoClusterMap.unionSets(&GV, Base);
131  } else if (auto *GIS = dyn_cast<GlobalIFunc>(&GV)) {
132  GVtoClusterMap.unionSets(&GV, GIS->getResolverFunction());
133  }
134 
135  if (const Function *F = dyn_cast<Function>(&GV)) {
136  for (const BasicBlock &BB : *F) {
138  if (!BA || !BA->isConstantUsed())
139  continue;
140  addAllGlobalValueUsers(GVtoClusterMap, F, BA);
141  }
142  }
143 
144  if (GV.hasLocalLinkage())
145  addAllGlobalValueUsers(GVtoClusterMap, &GV, &GV);
146  };
147 
148  llvm::for_each(M.functions(), recordGVSet);
149  llvm::for_each(M.globals(), recordGVSet);
150  llvm::for_each(M.aliases(), recordGVSet);
151 
152  // Assigned all GVs to merged clusters while balancing number of objects in
153  // each.
154  auto CompareClusters = [](const std::pair<unsigned, unsigned> &a,
155  const std::pair<unsigned, unsigned> &b) {
156  if (a.second || b.second)
157  return a.second > b.second;
158  else
159  return a.first > b.first;
160  };
161 
162  std::priority_queue<std::pair<unsigned, unsigned>,
163  std::vector<std::pair<unsigned, unsigned>>,
164  decltype(CompareClusters)>
165  BalancinQueue(CompareClusters);
166  // Pre-populate priority queue with N slot blanks.
167  for (unsigned i = 0; i < N; ++i)
168  BalancinQueue.push(std::make_pair(i, 0));
169 
170  using SortType = std::pair<unsigned, ClusterMapType::iterator>;
171 
174 
175  // To guarantee determinism, we have to sort SCC according to size.
176  // When size is the same, use leader's name.
177  for (ClusterMapType::iterator I = GVtoClusterMap.begin(),
178  E = GVtoClusterMap.end(); I != E; ++I)
179  if (I->isLeader())
180  Sets.push_back(
181  std::make_pair(std::distance(GVtoClusterMap.member_begin(I),
182  GVtoClusterMap.member_end()), I));
183 
184  llvm::sort(Sets, [](const SortType &a, const SortType &b) {
185  if (a.first == b.first)
186  return a.second->getData()->getName() > b.second->getData()->getName();
187  else
188  return a.first > b.first;
189  });
190 
191  for (auto &I : Sets) {
192  unsigned CurrentClusterID = BalancinQueue.top().first;
193  unsigned CurrentClusterSize = BalancinQueue.top().second;
194  BalancinQueue.pop();
195 
196  LLVM_DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size("
197  << I.first << ") ----> " << I.second->getData()->getName()
198  << "\n");
199 
200  for (ClusterMapType::member_iterator MI =
201  GVtoClusterMap.findLeader(I.second);
202  MI != GVtoClusterMap.member_end(); ++MI) {
203  if (!Visited.insert(*MI).second)
204  continue;
205  LLVM_DEBUG(dbgs() << "----> " << (*MI)->getName()
206  << ((*MI)->hasLocalLinkage() ? " l " : " e ") << "\n");
207  Visited.insert(*MI);
208  ClusterIDMap[*MI] = CurrentClusterID;
209  CurrentClusterSize++;
210  }
211  // Add this set size to the number of entries in this cluster.
212  BalancinQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize));
213  }
214 }
215 
216 static void externalize(GlobalValue *GV) {
217  if (GV->hasLocalLinkage()) {
220  }
221 
222  // Unnamed entities must be named consistently between modules. setName will
223  // give a distinct name to each such entity.
224  if (!GV->hasName())
225  GV->setName("__llvmsplit_unnamed");
226 }
227 
228 // Returns whether GV should be in partition (0-based) I of N.
229 static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N) {
230  if (auto *GIS = dyn_cast<GlobalAlias>(GV)) {
231  if (const GlobalObject *Base = GIS->getBaseObject())
232  GV = Base;
233  } else if (auto *GIS = dyn_cast<GlobalIFunc>(GV)) {
234  GV = GIS->getResolverFunction();
235  }
236 
237  StringRef Name;
238  if (const Comdat *C = GV->getComdat())
239  Name = C->getName();
240  else
241  Name = GV->getName();
242 
243  // Partition by MD5 hash. We only need a few bits for evenness as the number
244  // of partitions will generally be in the 1-2 figure range; the low 16 bits
245  // are enough.
246  MD5 H;
247  MD5::MD5Result R;
248  H.update(Name);
249  H.final(R);
250  return (R[0] | (R[1] << 8)) % N == I;
251 }
252 
254  Module &M, unsigned N,
255  function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback,
256  bool PreserveLocals) {
257  if (!PreserveLocals) {
258  for (Function &F : M)
259  externalize(&F);
260  for (GlobalVariable &GV : M.globals())
261  externalize(&GV);
262  for (GlobalAlias &GA : M.aliases())
263  externalize(&GA);
264  for (GlobalIFunc &GIF : M.ifuncs())
265  externalize(&GIF);
266  }
267 
268  // This performs splitting without a need for externalization, which might not
269  // always be possible.
270  ClusterIDMapType ClusterIDMap;
271  findPartitions(M, ClusterIDMap, N);
272 
273  // FIXME: We should be able to reuse M as the last partition instead of
274  // cloning it. Note that the callers at the moment expect the module to
275  // be preserved, so will need some adjustments as well.
276  for (unsigned I = 0; I < N; ++I) {
277  ValueToValueMapTy VMap;
278  std::unique_ptr<Module> MPart(
279  CloneModule(M, VMap, [&](const GlobalValue *GV) {
280  if (ClusterIDMap.count(GV))
281  return (ClusterIDMap[GV] == I);
282  else
283  return isInPartition(GV, I, N);
284  }));
285  if (I != 0)
286  MPart->setModuleInlineAsm("");
287  ModuleCallback(std::move(MPart));
288  }
289 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
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:1168
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:216
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:635
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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:163
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:648
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:376
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:1544
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:848
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:309
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::MD5::MD5Result
Definition: MD5.h:43
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:1492
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:229
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:1827
llvm::Constant::isConstantUsed
bool isConstantUsed() const
Return true if the constant has users other than constant expressions and other dangling things.
Definition: Constants.cpp:649
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:253
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