SplitModule.cpp Source File (original) (raw)

40#include

41#include

42#include

43#include

44#include

45#include

47using namespace llvm;

49#define DEBUG_TYPE "split-module"

51namespace {

57bool compareClusters(const std::pair<unsigned, unsigned> &A,

58 const std::pair<unsigned, unsigned> &B) {

59 if (A.second || B.second)

60 return A.second > B.second;

61 return A.first > B.first;

62}

64using BalancingQueueType =

65 std::priority_queue<std::pair<unsigned, unsigned>,

66 std::vector<std::pair<unsigned, unsigned>>,

67 decltype(compareClusters) *>;

69}

73 assert((!isa(U) || isa(U)) && "Bad user");

75 if (const Instruction *I = dyn_cast(U)) {

76 const GlobalValue *F = I->getParent()->getParent();

77 GVtoClusterMap.unionSets(GV, F);

78 } else if (const GlobalValue *GVU = dyn_cast(U)) {

79 GVtoClusterMap.unionSets(GV, GVU);

80 } else {

82 }

83}

88 for (const auto *U : V->users()) {

91 while (!Worklist.empty()) {

94 if (isa(UU) && !isa(UU)) {

96 continue;

97 }

99 }

100 }

101}

102

105 if (const auto *GI = dyn_cast_or_null(GO))

106 GO = GI->getResolverFunction();

107 return GO;

108}

109

110

111

112

113

115 unsigned N) {

116

117

118

119 LLVM_DEBUG(dbgs() << "Partition module with (" << M.size()

120 << ") functions\n");

121 ClusterMapType GVtoClusterMap;

122 ComdatMembersType ComdatMembers;

123

124 auto recordGVSet = [&GVtoClusterMap, &ComdatMembers](GlobalValue &GV) {

125 if (GV.isDeclaration())

126 return;

127

128 if (!GV.hasName())

129 GV.setName("__llvmsplit_unnamed");

130

131

132

133

134

135 if (const Comdat *C = GV.getComdat()) {

136 auto &Member = ComdatMembers[C];

137 if (Member)

138 GVtoClusterMap.unionSets(Member, &GV);

139 else

140 Member = &GV;

141 }

142

143

144

146 if (&GV != Root)

147 GVtoClusterMap.unionSets(&GV, Root);

148

149 if (const Function *F = dyn_cast(&GV)) {

153 continue;

155 }

156 }

157

158 if (GV.hasLocalLinkage())

160 };

161

165

166

167

168 BalancingQueueType BalancingQueue(compareClusters);

169

170 for (unsigned i = 0; i < N; ++i)

171 BalancingQueue.push(std::make_pair(i, 0));

172

173 using SortType = std::pair<unsigned, ClusterMapType::iterator>;

174

177

178

179

180 for (ClusterMapType::iterator I = GVtoClusterMap.begin(),

181 E = GVtoClusterMap.end();

182 I != E; ++I)

183 if (I->isLeader())

185 std::make_pair(std::distance(GVtoClusterMap.member_begin(I),

186 GVtoClusterMap.member_end()),

187 I));

188

189 llvm::sort(Sets, [](const SortType &a, const SortType &b) {

190 if (a.first == b.first)

191 return a.second->getData()->getName() > b.second->getData()->getName();

192 else

193 return a.first > b.first;

194 });

195

196 for (auto &I : Sets) {

197 unsigned CurrentClusterID = BalancingQueue.top().first;

198 unsigned CurrentClusterSize = BalancingQueue.top().second;

199 BalancingQueue.pop();

200

201 LLVM_DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size("

202 << I.first << ") ----> " << I.second->getData()->getName()

203 << "\n");

204

205 for (ClusterMapType::member_iterator MI =

206 GVtoClusterMap.findLeader(I.second);

207 MI != GVtoClusterMap.member_end(); ++MI) {

208 if (!Visited.insert(*MI).second)

209 continue;

211 << ((*MI)->hasLocalLinkage() ? " l " : " e ") << "\n");

213 ClusterIDMap[*MI] = CurrentClusterID;

214 CurrentClusterSize++;

215 }

216

217 BalancingQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize));

218 }

219}

220

225 }

226

227

228

230 GV->setName("__llvmsplit_unnamed");

231}

232

233

236 GV = Root;

237

240 Name = C->getName();

241 else

243

244

245

246

250 H.final(R);

251 return (R[0] | (R[1] << 8)) % N == I;

252}

253

256 function_ref<void(std::unique_ptr MPart)> ModuleCallback,

257 bool PreserveLocals, bool RoundRobin) {

258 if (!PreserveLocals) {

267 }

268

269

270

271 ClusterIDMapType ClusterIDMap;

273

274

275

276

277

278

279 if (RoundRobin) {

282 for (const auto &F : M.functions()) {

283 if (F.isDeclaration() ||

284 F.getLinkage() != GlobalValue::LinkageTypes::ExternalLinkage)

285 continue;

286 auto It = ClusterIDMap.find(&F);

287 if (It == ClusterIDMap.end())

289 else

290 ++ModuleFunctionCount[It->second];

291 }

292 BalancingQueueType BalancingQueue(compareClusters);

293 for (unsigned I = 0; I < N; ++I) {

294 if (auto It = ModuleFunctionCount.find(I);

295 It != ModuleFunctionCount.end())

296 BalancingQueue.push(*It);

297 else

298 BalancingQueue.push({I, 0});

299 }

300 for (const auto *const F : UnmappedFunctions) {

301 const unsigned I = BalancingQueue.top().first;

302 const unsigned Count = BalancingQueue.top().second;

303 BalancingQueue.pop();

304 ClusterIDMap.insert({F, I});

305 BalancingQueue.push({I, Count + 1});

306 }

307 }

308

309

310

311

312 for (unsigned I = 0; I < N; ++I) {

314 std::unique_ptr MPart(

316 if (auto It = ClusterIDMap.find(GV); It != ClusterIDMap.end())

317 return It->second == I;

318 else

320 }));

321 if (I != 0)

322 MPart->setModuleInlineAsm("");

323 ModuleCallback(std::move(MPart));

324 }

325}

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

Module.h This file contains the declarations for the Module class.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N)

static void addNonConstUser(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const User *U)

static void findPartitions(Module &M, ClusterIDMapType &ClusterIDMap, unsigned N)

static void externalize(GlobalValue *GV)

static const GlobalObject * getGVPartitioningRoot(const GlobalValue *GV)

static void addAllGlobalValueUsers(ClusterMapType &GVtoClusterMap, const GlobalValue *GV, const Value *V)

LLVM Basic Block Representation.

The address of a basic block.

static BlockAddress * lookup(const BasicBlock *BB)

Lookup an existing BlockAddress constant for the given BasicBlock.

bool isConstantUsed() const

Return true if the constant has users other than constant expressions and other dangling things.

iterator find(const_arg_type_t< KeyT > Val)

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

bool hasLocalLinkage() const

const Comdat * getComdat() const

void setLinkage(LinkageTypes LT)

const GlobalObject * getAliaseeObject() const

@ HiddenVisibility

The GV is hidden.

void setVisibility(VisibilityTypes V)

@ ExternalLinkage

Externally visible function.

A Module instance is used to store all the information related to an LLVM module.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

LLVM Value Representation.

user_iterator user_begin()

void setName(const Twine &Name)

Change the name of the value.

StringRef getName() const

Return a constant reference to the value's name.

An efficient, type-erasing, non-owning reference to a callable.

This file contains the declaration of the Comdat class, which represents a single COMDAT in LLVM.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

UnaryFunction for_each(R &&Range, UnaryFunction F)

Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.

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.

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

std::unique_ptr< Module > CloneModule(const Module &M)

Return an exact copy of the specified module.