From d19d4d30d84cf6befcda72ff957bf31a7e4e7335 Mon Sep 17 00:00:00 2001 From: Sergei Larin Date: Mon, 18 Jan 2016 21:07:13 +0000 Subject: Add to the split module utility an SCC based method which allows not to globalize any local variables. Summary: Currently llvm::SplitModule as the first step globalizes all local objects, which might not be desirable in some scenarios. This change adds a new flag to llvm::SplitModule that uses SCC approach to search for a balanced partition without the need to externalize symbols. Such partition might not be possible or fully balanced for a given number of partitions, and is a function of the module properties (global/local dependencies within the module). Joint development Tobias Edler von Koch (tobias@codeaurora.org) and Sergei Larin (slarin@codeaurora.org) Subscribers: llvm-commits, joker.eph Differential Revision: http://reviews.llvm.org/D16124 llvm-svn: 258083 --- llvm/lib/Transforms/Utils/SplitModule.cpp | 207 +++++++++++++++++++++++++++--- 1 file changed, 188 insertions(+), 19 deletions(-) mode change 100644 => 100755 llvm/lib/Transforms/Utils/SplitModule.cpp (limited to 'llvm/lib/Transforms/Utils/SplitModule.cpp') diff --git a/llvm/lib/Transforms/Utils/SplitModule.cpp b/llvm/lib/Transforms/Utils/SplitModule.cpp old mode 100644 new mode 100755 index ad6b782..b3d0f52 --- a/llvm/lib/Transforms/Utils/SplitModule.cpp +++ b/llvm/lib/Transforms/Utils/SplitModule.cpp @@ -13,19 +13,166 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "split-module" + #include "llvm/Transforms/Utils/SplitModule.h" +#include "llvm/ADT/EquivalenceClasses.h" #include "llvm/ADT/Hashing.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalObject.h" #include "llvm/IR/GlobalValue.h" #include "llvm/IR/Module.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/MD5.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Cloning.h" +#include using namespace llvm; +namespace { +typedef EquivalenceClasses ClusterMapType; +typedef DenseMap ComdatMembersType; +typedef DenseMap ClusterIDMapType; +} + +static void addNonConstUser(ClusterMapType &GVtoClusterMap, + const GlobalValue *GV, const User *U) { + assert((!isa(U) || isa(U)) && "Bad user"); + + if (const Instruction *I = dyn_cast(U)) { + const GlobalValue *F = I->getParent()->getParent(); + GVtoClusterMap.unionSets(GV, F); + } else if (isa(U) || isa(U) || + isa(U)) { + GVtoClusterMap.unionSets(GV, cast(U)); + } else { + llvm_unreachable("Underimplemented use case"); + } +} + +// Find partitions for module in the way that no locals need to be +// globalized. +// Try to balance pack those partitions into N files since this roughly equals +// thread balancing for the backend codegen step. +static void findPartitions(Module *M, ClusterIDMapType &ClusterIDMap, + unsigned N) { + // At this point module should have the proper mix of globals and locals. + // As we attempt to partition this module, we must not change any + // locals to globals. + + DEBUG(dbgs() << "Partition module with (" << M->size() << ")functions\n"); + ClusterMapType GVtoClusterMap; + ComdatMembersType ComdatMembers; + + auto recordGVSet = [&GVtoClusterMap, &ComdatMembers](GlobalValue &GV) { + if (GV.isDeclaration()) + return; + + if (!GV.hasName()) + GV.setName("__llvmsplit_unnamed"); + + // Comdat groups must not be partitioned. For comdat groups that contain + // locals, record all their members here so we can keep them together. + // Comdat groups that only contain external globals are already handled by + // the MD5-based partitioning. + if (const Comdat *C = GV.getComdat()) { + auto &Member = ComdatMembers[C]; + if (Member) + GVtoClusterMap.unionSets(Member, &GV); + else + Member = &GV; + } + + // Further only iterate over local GVs. + if (!GV.hasLocalLinkage()) + return; + + for (auto *U : GV.users()) { + SmallVector Worklist; + Worklist.push_back(U); + while (!Worklist.empty()) { + const User *UU = Worklist.pop_back_val(); + // For each constant that is not a GV (a pure const) recurse. + if (isa(UU) && !isa(UU)) { + Worklist.append(UU->user_begin(), UU->user_end()); + continue; + } + addNonConstUser(GVtoClusterMap, &GV, UU); + } + } + }; + + std::for_each(M->begin(), M->end(), recordGVSet); + std::for_each(M->global_begin(), M->global_end(), recordGVSet); + std::for_each(M->alias_begin(), M->alias_end(), recordGVSet); + + // Assigned all GVs to merged clusters while balancing number of objects in + // each. + auto CompareClusters = [](const std::pair &a, + const std::pair &b) { + if (a.second || b.second) + return a.second > b.second; + else + return a.first > b.first; + }; + + std::priority_queue, + std::vector>, + decltype(CompareClusters)> + BalancinQueue(CompareClusters); + // Pre-populate priority queue with N slot blanks. + for (unsigned i = 0; i < N; ++i) + BalancinQueue.push(std::make_pair(i, 0)); + + typedef std::pair SortType; + SmallVector Sets; + SmallPtrSet Visited; + + // To guarantee determinism, we have to sort SCC according to size. + // When size is the same, use leader's name. + for (ClusterMapType::iterator I = GVtoClusterMap.begin(), + E = GVtoClusterMap.end(); I != E; ++I) + if (I->isLeader()) + Sets.push_back( + std::make_pair(std::distance(GVtoClusterMap.member_begin(I), + GVtoClusterMap.member_end()), I)); + + std::sort(Sets.begin(), Sets.end(), [](const SortType &a, const SortType &b) { + if (a.first == b.first) + return a.second->getData()->getName() > b.second->getData()->getName(); + else + return a.first > b.first; + }); + + for (auto &I : Sets) { + unsigned CurrentClusterID = BalancinQueue.top().first; + unsigned CurrentClusterSize = BalancinQueue.top().second; + BalancinQueue.pop(); + + DEBUG(dbgs() << "Root[" << CurrentClusterID << "] cluster_size(" << I.first + << ") ----> " << I.second->getData()->getName() << "\n"); + + for (ClusterMapType::member_iterator MI = + GVtoClusterMap.findLeader(I.second); + MI != GVtoClusterMap.member_end(); ++MI) { + if (!Visited.insert(*MI).second) + continue; + DEBUG(dbgs() << "----> " << (*MI)->getName() + << ((*MI)->hasLocalLinkage() ? " l " : " e ") << "\n"); + Visited.insert(*MI); + ClusterIDMap[*MI] = CurrentClusterID; + CurrentClusterSize++; + } + // Add this set size to the number of entries in this cluster. + BalancinQueue.push(std::make_pair(CurrentClusterID, CurrentClusterSize)); + } +} + static void externalize(GlobalValue *GV) { if (GV->hasLocalLinkage()) { GV->setLinkage(GlobalValue::ExternalLinkage); @@ -62,24 +209,46 @@ static bool isInPartition(const GlobalValue *GV, unsigned I, unsigned N) { void llvm::SplitModule( std::unique_ptr M, unsigned N, - std::function MPart)> ModuleCallback) { - for (Function &F : *M) - externalize(&F); - for (GlobalVariable &GV : M->globals()) - externalize(&GV); - for (GlobalAlias &GA : M->aliases()) - externalize(&GA); - - // FIXME: We should be able to reuse M as the last partition instead of - // cloning it. - for (unsigned I = 0; I != N; ++I) { - ValueToValueMapTy VMap; - std::unique_ptr MPart( - CloneModule(M.get(), VMap, [=](const GlobalValue *GV) { - return isInPartition(GV, I, N); - })); - if (I != 0) - MPart->setModuleInlineAsm(""); - ModuleCallback(std::move(MPart)); + std::function MPart)> ModuleCallback, + bool PreserveLocals) { + if (!PreserveLocals) { + for (Function &F : *M) + externalize(&F); + for (GlobalVariable &GV : M->globals()) + externalize(&GV); + for (GlobalAlias &GA : M->aliases()) + externalize(&GA); + + // FIXME: We should be able to reuse M as the last partition instead of + // cloning it. + for (unsigned I = 0; I != N; ++I) { + ValueToValueMapTy VMap; + std::unique_ptr MPart( + CloneModule(M.get(), VMap, [=](const GlobalValue *GV) { + return isInPartition(GV, I, N); + })); + if (I != 0) + MPart->setModuleInlineAsm(""); + ModuleCallback(std::move(MPart)); + } + } else { + // This performs splitting without a need for externalization, which might not + // always be possible. + ClusterIDMapType ClusterIDMap; + findPartitions(M.get(), ClusterIDMap, N); + + for (unsigned I = 0; I < N; ++I) { + ValueToValueMapTy VMap; + std::unique_ptr MPart( + CloneModule(M.get(), VMap, [&](const GlobalValue *GV) { + if (ClusterIDMap.count(GV)) + return (ClusterIDMap[GV] == I); + else + return isInPartition(GV, I, N); + })); + if (I != 0) + MPart->setModuleInlineAsm(""); + ModuleCallback(std::move(MPart)); + } } } -- cgit v1.1