Movatterモバイル変換

[0]ホーム
URL:

LLVM 20.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
15#include "llvm/Transforms/Utils/SplitModule.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/EquivalenceClasses.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"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/MD5.h"
37#include "llvm/Support/raw_ostream.h"
38#include "llvm/Transforms/Utils/Cloning.h"
39#include "llvm/Transforms/Utils/ValueMapper.h"
40#include <cassert>
41#include <iterator>
42#include <memory>
43#include <queue>
44#include <utility>
45#include <vector>
46
47using namespacellvm;
48
49#define DEBUG_TYPE "split-module"
50
51namespace{
52
53usingClusterMapType =EquivalenceClasses<const GlobalValue *>;
54usingComdatMembersType =DenseMap<const Comdat *, const GlobalValue *>;
55usingClusterIDMapType =DenseMap<const GlobalValue *, unsigned>;
56
57bool compareClusters(const std::pair<unsigned, unsigned> &A,
58const std::pair<unsigned, unsigned> &B) {
59if (A.second ||B.second)
60returnA.second >B.second;
61returnA.first >B.first;
62}
63
64usingBalancingQueueType =
65 std::priority_queue<std::pair<unsigned, unsigned>,
66 std::vector<std::pair<unsigned, unsigned>>,
67decltype(compareClusters) *>;
68
69}// end anonymous namespace
70
71staticvoidaddNonConstUser(ClusterMapType &GVtoClusterMap,
72constGlobalValue *GV,constUser *U) {
73assert((!isa<Constant>(U) || isa<GlobalValue>(U)) &&"Bad user");
74
75if (constInstruction *I = dyn_cast<Instruction>(U)) {
76constGlobalValue *F =I->getParent()->getParent();
77 GVtoClusterMap.unionSets(GV,F);
78 }elseif (constGlobalValue *GVU = dyn_cast<GlobalValue>(U)) {
79 GVtoClusterMap.unionSets(GV, GVU);
80 }else {
81llvm_unreachable("Underimplemented use case");
82 }
83}
84
85// Adds all GlobalValue users of V to the same cluster as GV.
86staticvoidaddAllGlobalValueUsers(ClusterMapType &GVtoClusterMap,
87constGlobalValue *GV,constValue *V) {
88for (constauto *U : V->users()) {
89SmallVector<const User *, 4> Worklist;
90 Worklist.push_back(U);
91while (!Worklist.empty()) {
92constUser *UU = Worklist.pop_back_val();
93// For each constant that is not a GV (a pure const) recurse.
94if (isa<Constant>(UU) && !isa<GlobalValue>(UU)) {
95 Worklist.append(UU->user_begin(), UU->user_end());
96continue;
97 }
98addNonConstUser(GVtoClusterMap, GV, UU);
99 }
100 }
101}
102
103staticconstGlobalObject *getGVPartitioningRoot(constGlobalValue *GV) {
104constGlobalObject *GO = GV->getAliaseeObject();
105if (constauto *GI = dyn_cast_or_null<GlobalIFunc>(GO))
106 GO = GI->getResolverFunction();
107return GO;
108}
109
110// Find partitions for module in the way that no locals need to be
111// globalized.
112// Try to balance pack those partitions into N files since this roughly equals
113// thread balancing for the backend codegen step.
114staticvoidfindPartitions(Module &M, ClusterIDMapType &ClusterIDMap,
115unsignedN) {
116// At this point module should have the proper mix of globals and locals.
117// As we attempt to partition this module, we must not change any
118// locals to globals.
119LLVM_DEBUG(dbgs() <<"Partition module with (" << M.size()
120 <<") functions\n");
121 ClusterMapType GVtoClusterMap;
122 ComdatMembersType ComdatMembers;
123
124auto recordGVSet = [&GVtoClusterMap, &ComdatMembers](GlobalValue &GV) {
125if (GV.isDeclaration())
126return;
127
128if (!GV.hasName())
129 GV.setName("__llvmsplit_unnamed");
130
131// Comdat groups must not be partitioned. For comdat groups that contain
132// locals, record all their members here so we can keep them together.
133// Comdat groups that only contain external globals are already handled by
134// the MD5-based partitioning.
135if (constComdat *C = GV.getComdat()) {
136auto &Member = ComdatMembers[C];
137if (Member)
138 GVtoClusterMap.unionSets(Member, &GV);
139else
140 Member = &GV;
141 }
142
143// Aliases should not be separated from their aliasees and ifuncs should
144// not be separated from their resolvers regardless of linkage.
145if (constGlobalObject *Root =getGVPartitioningRoot(&GV))
146if (&GV != Root)
147 GVtoClusterMap.unionSets(&GV, Root);
148
149if (constFunction *F = dyn_cast<Function>(&GV)) {
150for (constBasicBlock &BB : *F) {
151BlockAddress *BA =BlockAddress::lookup(&BB);
152if (!BA || !BA->isConstantUsed())
153continue;
154addAllGlobalValueUsers(GVtoClusterMap,F, BA);
155 }
156 }
157
158if (GV.hasLocalLinkage())
159addAllGlobalValueUsers(GVtoClusterMap, &GV, &GV);
160 };
161
162llvm::for_each(M.functions(), recordGVSet);
163llvm::for_each(M.globals(), recordGVSet);
164llvm::for_each(M.aliases(), recordGVSet);
165
166// Assigned all GVs to merged clusters while balancing number of objects in
167// each.
168 BalancingQueueType BalancingQueue(compareClusters);
169// Pre-populate priority queue with N slot blanks.
170for (unsigned i = 0; i <N; ++i)
171 BalancingQueue.push(std::make_pair(i, 0));
172
173usingSortType = std::pair<unsigned, ClusterMapType::iterator>;
174
175SmallVector<SortType, 64> Sets;
176SmallPtrSet<const GlobalValue *, 32> Visited;
177
178// To guarantee determinism, we have to sort SCC according to size.
179// When size is the same, use leader's name.
180for (ClusterMapType::iteratorI = GVtoClusterMap.begin(),
181 E = GVtoClusterMap.end();
182I != E; ++I)
183if (I->isLeader())
184 Sets.push_back(
185 std::make_pair(std::distance(GVtoClusterMap.member_begin(I),
186 GVtoClusterMap.member_end()),
187I));
188
189llvm::sort(Sets, [](const SortType &a,const SortType &b) {
190if (a.first == b.first)
191return a.second->getData()->getName() > b.second->getData()->getName();
192else
193return a.first > b.first;
194 });
195
196for (auto &I : Sets) {
197unsigned CurrentClusterID = BalancingQueue.top().first;
198unsigned CurrentClusterSize = BalancingQueue.top().second;
199 BalancingQueue.pop();
200
201LLVM_DEBUG(dbgs() <<"Root[" << CurrentClusterID <<"] cluster_size("
202 <<I.first <<") ----> " <<I.second->getData()->getName()
203 <<"\n");
204
205for (ClusterMapType::member_iteratorMI =
206 GVtoClusterMap.findLeader(I.second);
207MI != GVtoClusterMap.member_end(); ++MI) {
208if (!Visited.insert(*MI).second)
209continue;
210LLVM_DEBUG(dbgs() <<"----> " << (*MI)->getName()
211 << ((*MI)->hasLocalLinkage() ?" l " :" e ") <<"\n");
212 Visited.insert(*MI);
213 ClusterIDMap[*MI] = CurrentClusterID;
214 CurrentClusterSize++;
215 }
216// Add this set size to the number of entries in this cluster.
217 BalancingQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize));
218 }
219}
220
221staticvoidexternalize(GlobalValue *GV) {
222if (GV->hasLocalLinkage()) {
223 GV->setLinkage(GlobalValue::ExternalLinkage);
224 GV->setVisibility(GlobalValue::HiddenVisibility);
225 }
226
227// Unnamed entities must be named consistently between modules. setName will
228// give a distinct name to each such entity.
229if (!GV->hasName())
230 GV->setName("__llvmsplit_unnamed");
231}
232
233// Returns whether GV should be in partition (0-based) I of N.
234staticboolisInPartition(constGlobalValue *GV,unsignedI,unsignedN) {
235if (constGlobalObject *Root =getGVPartitioningRoot(GV))
236 GV = Root;
237
238StringRefName;
239if (constComdat *C = GV->getComdat())
240Name =C->getName();
241else
242Name = GV->getName();
243
244// Partition by MD5 hash. We only need a few bits for evenness as the number
245// of partitions will generally be in the 1-2 figure range; the low 16 bits
246// are enough.
247MD5H;
248MD5::MD5Result R;
249H.update(Name);
250H.final(R);
251return (R[0] | (R[1] << 8)) %N ==I;
252}
253
254voidllvm::SplitModule(
255Module &M,unsignedN,
256function_ref<void(std::unique_ptr<Module> MPart)> ModuleCallback,
257bool PreserveLocals,bool RoundRobin) {
258if (!PreserveLocals) {
259for (Function &F : M)
260externalize(&F);
261for (GlobalVariable &GV : M.globals())
262externalize(&GV);
263for (GlobalAlias &GA : M.aliases())
264externalize(&GA);
265for (GlobalIFunc &GIF : M.ifuncs())
266externalize(&GIF);
267 }
268
269// This performs splitting without a need for externalization, which might not
270// always be possible.
271 ClusterIDMapType ClusterIDMap;
272findPartitions(M, ClusterIDMap,N);
273
274// Find functions not mapped to modules in ClusterIDMap and count functions
275// per module. Map unmapped functions using round-robin so that they skip
276// being distributed by isInPartition() based on function name hashes below.
277// This provides better uniformity of distribution of functions to modules
278// in some cases - for example when the number of functions equals to N.
279if (RoundRobin) {
280DenseMap<unsigned, unsigned> ModuleFunctionCount;
281SmallVector<const GlobalValue *> UnmappedFunctions;
282for (constauto &F : M.functions()) {
283if (F.isDeclaration() ||
284F.getLinkage() != GlobalValue::LinkageTypes::ExternalLinkage)
285continue;
286auto It = ClusterIDMap.find(&F);
287if (It == ClusterIDMap.end())
288 UnmappedFunctions.push_back(&F);
289else
290 ++ModuleFunctionCount[It->second];
291 }
292 BalancingQueueType BalancingQueue(compareClusters);
293for (unsignedI = 0;I <N; ++I) {
294if (auto It = ModuleFunctionCount.find(I);
295 It != ModuleFunctionCount.end())
296 BalancingQueue.push(*It);
297else
298 BalancingQueue.push({I, 0});
299 }
300for (constauto *constF : UnmappedFunctions) {
301constunsignedI = BalancingQueue.top().first;
302constunsigned Count = BalancingQueue.top().second;
303 BalancingQueue.pop();
304 ClusterIDMap.insert({F,I});
305 BalancingQueue.push({I, Count + 1});
306 }
307 }
308
309// FIXME: We should be able to reuse M as the last partition instead of
310// cloning it. Note that the callers at the moment expect the module to
311// be preserved, so will need some adjustments as well.
312for (unsignedI = 0;I <N; ++I) {
313ValueToValueMapTy VMap;
314 std::unique_ptr<Module> MPart(
315CloneModule(M, VMap, [&](constGlobalValue *GV) {
316if (auto It = ClusterIDMap.find(GV); It != ClusterIDMap.end())
317return It->second ==I;
318else
319returnisInPartition(GV,I,N);
320 }));
321if (I != 0)
322 MPart->setModuleInlineAsm("");
323 ModuleCallback(std::move(MPart));
324 }
325}
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Casting.h
Cloning.h
Constants.h
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Debug.h
LLVM_DEBUG
#define LLVM_DEBUG(...)
Definition:Debug.h:106
DenseMap.h
This file defines the DenseMap class.
Name
std::string Name
Definition:ELFObjHandler.cpp:77
EquivalenceClasses.h
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
GlobalAlias.h
GlobalObject.h
GlobalValue.h
GlobalVariable.h
MI
IRTranslator LLVM IR MI
Definition:IRTranslator.cpp:112
Constant.h
Function.h
Instruction.h
Module.h
Module.h This file contains the declarations for the Module class.
User.h
Value.h
F
#define F(x, y, z)
Definition:MD5.cpp:55
I
#define I(x, y, z)
Definition:MD5.cpp:58
H
#define H(x, y, z)
Definition:MD5.cpp:57
MD5.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallPtrSet.h
This file defines the SmallPtrSet class.
SmallVector.h
This file defines the SmallVector class.
isInPartition
static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N)
Definition:SplitModule.cpp:234
addNonConstUser
static void addNonConstUser(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const User *U)
Definition:SplitModule.cpp:71
findPartitions
static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap, unsigned N)
Definition:SplitModule.cpp:114
externalize
static void externalize(GlobalValue *GV)
Definition:SplitModule.cpp:221
getGVPartitioningRoot
static const GlobalObject * getGVPartitioningRoot(const GlobalValue *GV)
Definition:SplitModule.cpp:103
addAllGlobalValueUsers
static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const Value *V)
Definition:SplitModule.cpp:86
SplitModule.h
StringRef.h
ValueMapper.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition:BasicBlock.h:61
llvm::BlockAddress
The address of a basic block.
Definition:Constants.h:893
llvm::BlockAddress::lookup
static BlockAddress * lookup(const BasicBlock *BB)
Lookup an existing BlockAddress constant for the given BasicBlock.
Definition:Constants.cpp:1915
llvm::Comdat
Definition:Comdat.h:33
llvm::Constant::isConstantUsed
bool isConstantUsed() const
Return true if the constant has users other than constant expressions and other dangling things.
Definition:Constants.cpp:639
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition:DenseMap.h:156
llvm::DenseMapBase::end
iterator end()
Definition:DenseMap.h:84
llvm::DenseMap
Definition:DenseMap.h:727
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition:EquivalenceClasses.h:60
llvm::Function
Definition:Function.h:63
llvm::GlobalAlias
Definition:GlobalAlias.h:28
llvm::GlobalIFunc
Definition:GlobalIFunc.h:34
llvm::GlobalObject
Definition:GlobalObject.h:27
llvm::GlobalValue
Definition:GlobalValue.h:48
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition:GlobalValue.h:529
llvm::GlobalValue::getComdat
const Comdat * getComdat() const
Definition:Globals.cpp:199
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition:GlobalValue.h:538
llvm::GlobalValue::getAliaseeObject
const GlobalObject * getAliaseeObject() const
Definition:Globals.cpp:400
llvm::GlobalValue::HiddenVisibility
@ HiddenVisibility
The GV is hidden.
Definition:GlobalValue.h:68
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition:GlobalValue.h:255
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition:GlobalValue.h:52
llvm::GlobalVariable
Definition:GlobalVariable.h:39
llvm::Instruction
Definition:Instruction.h:68
llvm::MD5
Definition:MD5.h:41
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition:Module.h:65
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:384
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition:SmallPtrSet.h:519
llvm::SmallVectorBase::empty
bool empty() const
Definition:SmallVector.h:81
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition:SmallVector.h:673
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition:SmallVector.h:683
llvm::SmallVectorTemplateBase::push_back
void push_back(const T &Elt)
Definition:SmallVector.h:413
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition:SmallVector.h:1196
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition:StringRef.h:51
llvm::User
Definition:User.h:44
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::Value
LLVM Value Representation.
Definition:Value.h:74
llvm::Value::user_begin
user_iterator user_begin()
Definition:Value.h:397
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition:Value.cpp:377
llvm::Value::user_end
user_iterator user_end()
Definition:Value.h:405
llvm::Value::hasName
bool hasName() const
Definition:Value.h:261
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition:Value.cpp:309
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition:STLFunctionalExtras.h:37
Comdat.h
This file contains the declaration of the Comdat class, which represents a single COMDAT in LLVM.
ErrorHandling.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition:ErrorHandling.h:143
llvm::CallingConv::C
@ C
The default llvm calling convention, compatible with C.
Definition:CallingConv.h:34
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:AddressRanges.h:18
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:1732
llvm::SplitModule
void SplitModule(Module &M, unsigned N, function_ref< void(std::unique_ptr< Module > MPart)> ModuleCallback, bool PreserveLocals=false, bool RoundRobin=false)
Splits the module M into N linkable partitions.
Definition:SplitModule.cpp:254
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition:STLExtras.h:1664
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition:Debug.cpp:163
llvm::CloneModule
std::unique_ptr< Module > CloneModule(const Module &M)
Return an exact copy of the specified module.
Definition:CloneModule.cpp:39
raw_ostream.h
N
#define N
llvm::MD5::MD5Result
Definition:MD5.h:43
Generated on Fri Jul 18 2025 16:44:06 for LLVM by doxygen 1.9.6
[8]ページ先頭
©2009-2025 Movatter.jp