LLVM  16.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"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/GlobalVariable.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/User.h"
32 #include "llvm/IR/Value.h"
33 #include "llvm/Support/Casting.h"
34 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/MD5.h"
40 #include <algorithm>
41 #include <cassert>
42 #include <iterator>
43 #include <memory>
44 #include <queue>
45 #include <utility>
46 #include <vector>
47 
48 using namespace llvm;
49 
50 #define DEBUG_TYPE "split-module"
51 
52 namespace {
53 
54 using ClusterMapType = EquivalenceClasses<const GlobalValue *>;
55 using ComdatMembersType = DenseMap<const Comdat *, const GlobalValue *>;
56 using ClusterIDMapType = DenseMap<const GlobalValue *, unsigned>;
57 
58 } // end anonymous namespace
59 
60 static void addNonConstUser(ClusterMapType &GVtoClusterMap,
61  const GlobalValue *GV, const User *U) {
62  assert((!isa<Constant>(U) || isa<GlobalValue>(U)) && "Bad user");
63 
64  if (const Instruction *I = dyn_cast<Instruction>(U)) {
65  const GlobalValue *F = I->getParent()->getParent();
66  GVtoClusterMap.unionSets(GV, F);
67  } else if (const GlobalValue *GVU = dyn_cast<GlobalValue>(U)) {
68  GVtoClusterMap.unionSets(GV, GVU);
69  } else {
70  llvm_unreachable("Underimplemented use case");
71  }
72 }
73 
74 // Adds all GlobalValue users of V to the same cluster as GV.
75 static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap,
76  const GlobalValue *GV, const Value *V) {
77  for (const auto *U : V->users()) {
79  Worklist.push_back(U);
80  while (!Worklist.empty()) {
81  const User *UU = Worklist.pop_back_val();
82  // For each constant that is not a GV (a pure const) recurse.
83  if (isa<Constant>(UU) && !isa<GlobalValue>(UU)) {
84  Worklist.append(UU->user_begin(), UU->user_end());
85  continue;
86  }
87  addNonConstUser(GVtoClusterMap, GV, UU);
88  }
89  }
90 }
91 
93  const GlobalObject *GO = GV->getAliaseeObject();
94  if (const auto *GI = dyn_cast_or_null<GlobalIFunc>(GO))
95  GO = GI->getResolverFunction();
96  return GO;
97 }
98 
99 // Find partitions for module in the way that no locals need to be
100 // globalized.
101 // Try to balance pack those partitions into N files since this roughly equals
102 // thread balancing for the backend codegen step.
103 static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap,
104  unsigned N) {
105  // At this point module should have the proper mix of globals and locals.
106  // As we attempt to partition this module, we must not change any
107  // locals to globals.
108  LLVM_DEBUG(dbgs() << "Partition module with (" << M.size() << ")functions\n");
109  ClusterMapType GVtoClusterMap;
110  ComdatMembersType ComdatMembers;
111 
112  auto recordGVSet = [&GVtoClusterMap, &ComdatMembers](GlobalValue &GV) {
113  if (GV.isDeclaration())
114  return;
115 
116  if (!GV.hasName())
117  GV.setName("__llvmsplit_unnamed");
118 
119  // Comdat groups must not be partitioned. For comdat groups that contain
120  // locals, record all their members here so we can keep them together.
121  // Comdat groups that only contain external globals are already handled by
122  // the MD5-based partitioning.
123  if (const Comdat *C = GV.getComdat()) {
124  auto &Member = ComdatMembers[C];
125  if (Member)
126  GVtoClusterMap.unionSets(Member, &GV);
127  else
128  Member = &GV;
129  }
130 
131  // Aliases should not be separated from their aliasees and ifuncs should
132  // not be separated from their resolvers regardless of linkage.
133  if (const GlobalObject *Root = getGVPartitioningRoot(&GV))
134  if (&GV != Root)
135  GVtoClusterMap.unionSets(&GV, Root);
136 
137  if (const Function *F = dyn_cast<Function>(&GV)) {
138  for (const BasicBlock &BB : *F) {
140  if (!BA || !BA->isConstantUsed())
141  continue;
142  addAllGlobalValueUsers(GVtoClusterMap, F, BA);
143  }
144  }
145 
146  if (GV.hasLocalLinkage())
147  addAllGlobalValueUsers(GVtoClusterMap, &GV, &GV);
148  };
149 
150  llvm::for_each(M.functions(), recordGVSet);
151  llvm::for_each(M.globals(), recordGVSet);
152  llvm::for_each(M.aliases(), recordGVSet);
153 
154  // Assigned all GVs to merged clusters while balancing number of objects in
155  // each.
156  auto CompareClusters = [](const std::pair<unsigned, unsigned> &a,
157  const std::pair<unsigned, unsigned> &b) {
158  if (a.second || b.second)
159  return a.second > b.second;
160  else
161  return a.first > b.first;
162  };
163 
164  std::priority_queue<std::pair<unsigned, unsigned>,
165  std::vector<std::pair<unsigned, unsigned>>,
166  decltype(CompareClusters)>
167  BalancinQueue(CompareClusters);
168  // Pre-populate priority queue with N slot blanks.
169  for (unsigned i = 0; i < N; ++i)
170  BalancinQueue.push(std::make_pair(i, 0));
171 
172  using SortType = std::pair<unsigned, ClusterMapType::iterator>;
173 
176 
177  // To guarantee determinism, we have to sort SCC according to size.
178  // When size is the same, use leader's name.
179  for (ClusterMapType::iterator I = GVtoClusterMap.begin(),
180  E = GVtoClusterMap.end(); I != E; ++I)
181  if (I->isLeader())
182  Sets.push_back(
183  std::make_pair(std::distance(GVtoClusterMap.member_begin(I),
184  GVtoClusterMap.member_end()), I));
185 
186  llvm::sort(Sets, [](const SortType &a, const SortType &b) {
187  if (a.first == b.first)
188  return a.second->getData()->getName() > b.second->getData()->getName();
189  else
190  return a.first > b.first;
191  });
192 
193  for (auto &I : Sets) {
194  unsigned CurrentClusterID = BalancinQueue.top().first;
195  unsigned CurrentClusterSize = BalancinQueue.top().second;
196  BalancinQueue.pop();
197 
198  LLVM_DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size("
199  << I.first << ") ----> " << I.second->getData()->getName()
200  << "\n");
201 
202  for (ClusterMapType::member_iterator MI =
203  GVtoClusterMap.findLeader(I.second);
204  MI != GVtoClusterMap.member_end(); ++MI) {
205  if (!Visited.insert(*MI).second)
206  continue;
207  LLVM_DEBUG(dbgs() << "----> " << (*MI)->getName()
208  << ((*MI)->hasLocalLinkage() ? " l " : " e ") << "\n");
209  Visited.insert(*MI);
210  ClusterIDMap[*MI] = CurrentClusterID;
211  CurrentClusterSize++;
212  }
213  // Add this set size to the number of entries in this cluster.
214  BalancinQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize));
215  }
216 }
217 
218 static void externalize(GlobalValue *GV) {
219  if (GV->hasLocalLinkage()) {
222  }
223 
224  // Unnamed entities must be named consistently between modules. setName will
225  // give a distinct name to each such entity.
226  if (!GV->hasName())
227  GV->setName("__llvmsplit_unnamed");
228 }
229 
230 // Returns whether GV should be in partition (0-based) I of N.
231 static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N) {
232  if (const GlobalObject *Root = getGVPartitioningRoot(GV))
233  GV = Root;
234 
235  StringRef Name;
236  if (const Comdat *C = GV->getComdat())
237  Name = C->getName();
238  else
239  Name = GV->getName();
240 
241  // Partition by MD5 hash. We only need a few bits for evenness as the number
242  // of partitions will generally be in the 1-2 figure range; the low 16 bits
243  // are enough.
244  MD5 H;
245  MD5::MD5Result R;
246  H.update(Name);
247  H.final(R);
248  return (R[0] | (R[1] << 8)) % N == I;
249 }
250 
252  Module &M, unsigned N,
253  function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback,
254  bool PreserveLocals) {
255  if (!PreserveLocals) {
256  for (Function &F : M)
257  externalize(&F);
258  for (GlobalVariable &GV : M.globals())
259  externalize(&GV);
260  for (GlobalAlias &GA : M.aliases())
261  externalize(&GA);
262  for (GlobalIFunc &GIF : M.ifuncs())
263  externalize(&GIF);
264  }
265 
266  // This performs splitting without a need for externalization, which might not
267  // always be possible.
268  ClusterIDMapType ClusterIDMap;
269  findPartitions(M, ClusterIDMap, N);
270 
271  // FIXME: We should be able to reuse M as the last partition instead of
272  // cloning it. Note that the callers at the moment expect the module to
273  // be preserved, so will need some adjustments as well.
274  for (unsigned I = 0; I < N; ++I) {
275  ValueToValueMapTy VMap;
276  std::unique_ptr<Module> MPart(
277  CloneModule(M, VMap, [&](const GlobalValue *GV) {
278  if (ClusterIDMap.count(GV))
279  return (ClusterIDMap[GV] == I);
280  else
281  return isInPartition(GV, I, N);
282  }));
283  if (I != 0)
284  MPart->setModuleInlineAsm("");
285  ModuleCallback(std::move(MPart));
286  }
287 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:60
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:1199
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:60
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
ErrorHandling.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::GlobalAlias
Definition: GlobalAlias.h:28
externalize
static void externalize(GlobalValue *GV)
Definition: SplitModule.cpp:218
DenseMap.h
Module.h
addAllGlobalValueUsers
static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const Value *V)
Definition: SplitModule.cpp:75
findPartitions
static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap, unsigned N)
Definition: SplitModule.cpp:103
GlobalObject.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:397
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::GlobalObject
Definition: GlobalObject.h:27
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:42
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
SmallPtrSet.h
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
llvm::Comdat
Definition: Comdat.h:33
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1657
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:405
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:1702
addNonConstUser
static void addNonConstUser(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const User *U)
Definition: SplitModule.cpp:60
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:58
Cloning.h
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:530
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:521
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:849
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::GlobalValue::getAliaseeObject
const GlobalObject * getAliaseeObject() const
Definition: Globals.cpp:365
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::MD5::MD5Result
Definition: MD5.h:43
Constant.h
H
#define H(x, y, z)
Definition: MD5.cpp:57
GlobalVariable.h
llvm::GlobalValue::getComdat
const Comdat * getComdat() const
Definition: Globals.cpp:181
Casting.h
Function.h
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:37
N
#define N
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
isInPartition
static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N)
Definition: SplitModule.cpp:231
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:1769
llvm::Constant::isConstantUsed
bool isConstantUsed() const
Return true if the constant has users other than constant expressions and other dangling things.
Definition: Constants.cpp:601
raw_ostream.h
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:34
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:251
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:248
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
getGVPartitioningRoot
static const GlobalObject * getGVPartitioningRoot(const GlobalValue *GV)
Definition: SplitModule.cpp:92
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:365