From c5bc067a0fb05fe36761bb280d630dce5611f400 Mon Sep 17 00:00:00 2001 From: Jiangning Liu Date: Fri, 13 Jun 2014 22:57:59 +0000 Subject: Move GlobalMerge from Transform to CodeGen. This patch is to move GlobalMerge pass from Transform/Scalar to CodeGen, because GlobalMerge depends on TargetMachine. In the mean time, the macro INITIALIZE_TM_PASS is also moved to CodeGen/Passes.h. With this fix we can avoid making libScalarOpts depend on libCodeGen. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210951 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/CMakeLists.txt | 1 - lib/Transforms/Scalar/GlobalMerge.cpp | 362 ---------------------------------- lib/Transforms/Scalar/Scalar.cpp | 1 - 3 files changed, 364 deletions(-) delete mode 100644 lib/Transforms/Scalar/GlobalMerge.cpp (limited to 'lib/Transforms') diff --git a/lib/Transforms/Scalar/CMakeLists.txt b/lib/Transforms/Scalar/CMakeLists.txt index b2461fc627..2dcfa237ca 100644 --- a/lib/Transforms/Scalar/CMakeLists.txt +++ b/lib/Transforms/Scalar/CMakeLists.txt @@ -8,7 +8,6 @@ add_llvm_library(LLVMScalarOpts EarlyCSE.cpp FlattenCFGPass.cpp GVN.cpp - GlobalMerge.cpp IndVarSimplify.cpp JumpThreading.cpp LICM.cpp diff --git a/lib/Transforms/Scalar/GlobalMerge.cpp b/lib/Transforms/Scalar/GlobalMerge.cpp deleted file mode 100644 index cf6cf072a8..0000000000 --- a/lib/Transforms/Scalar/GlobalMerge.cpp +++ /dev/null @@ -1,362 +0,0 @@ -//===-- GlobalMerge.cpp - Internal globals merging -----------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// This pass merges globals with internal linkage into one. This way all the -// globals which were merged into a biggest one can be addressed using offsets -// from the same base pointer (no need for separate base pointer for each of the -// global). Such a transformation can significantly reduce the register pressure -// when many globals are involved. -// -// For example, consider the code which touches several global variables at -// once: -// -// static int foo[N], bar[N], baz[N]; -// -// for (i = 0; i < N; ++i) { -// foo[i] = bar[i] * baz[i]; -// } -// -// On ARM the addresses of 3 arrays should be kept in the registers, thus -// this code has quite large register pressure (loop body): -// -// ldr r1, [r5], #4 -// ldr r2, [r6], #4 -// mul r1, r2, r1 -// str r1, [r0], #4 -// -// Pass converts the code to something like: -// -// static struct { -// int foo[N]; -// int bar[N]; -// int baz[N]; -// } merged; -// -// for (i = 0; i < N; ++i) { -// merged.foo[i] = merged.bar[i] * merged.baz[i]; -// } -// -// and in ARM code this becomes: -// -// ldr r0, [r5, #40] -// ldr r1, [r5, #80] -// mul r0, r1, r0 -// str r0, [r5], #4 -// -// note that we saved 2 registers here almostly "for free". -// ===---------------------------------------------------------------------===// - -#include "llvm/Transforms/Scalar.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/IR/Attributes.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/GlobalVariable.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Intrinsics.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/Target/TargetLoweringObjectFile.h" -using namespace llvm; - -#define DEBUG_TYPE "global-merge" - -static cl::opt -EnableGlobalMerge("enable-global-merge", cl::Hidden, - cl::desc("Enable global merge pass"), - cl::init(true)); - -static cl::opt -EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, - cl::desc("Enable global merge pass on constants"), - cl::init(false)); - -// FIXME: this could be a transitional option, and we probably need to remove -// it if only we are sure this optimization could always benefit all targets. -static cl::opt -EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, - cl::desc("Enable global merge pass on external linkage"), - cl::init(false)); - -STATISTIC(NumMerged , "Number of globals merged"); -namespace { - class GlobalMerge : public FunctionPass { - const TargetMachine *TM; - - bool doMerge(SmallVectorImpl &Globals, - Module &M, bool isConst, unsigned AddrSpace) const; - - /// \brief Check if the given variable has been identified as must keep - /// \pre setMustKeepGlobalVariables must have been called on the Module that - /// contains GV - bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { - return MustKeepGlobalVariables.count(GV); - } - - /// Collect every variables marked as "used" or used in a landing pad - /// instruction for this Module. - void setMustKeepGlobalVariables(Module &M); - - /// Collect every variables marked as "used" - void collectUsedGlobalVariables(Module &M); - - /// Keep track of the GlobalVariable that must not be merged away - SmallPtrSet MustKeepGlobalVariables; - - public: - static char ID; // Pass identification, replacement for typeid. - explicit GlobalMerge(const TargetMachine *TM = nullptr) - : FunctionPass(ID), TM(TM) { - initializeGlobalMergePass(*PassRegistry::getPassRegistry()); - } - - bool doInitialization(Module &M) override; - bool runOnFunction(Function &F) override; - bool doFinalization(Module &M) override; - - const char *getPassName() const override { - return "Merge internal globals"; - } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); - FunctionPass::getAnalysisUsage(AU); - } - }; -} // end anonymous namespace - -char GlobalMerge::ID = 0; -INITIALIZE_TM_PASS(GlobalMerge, "global-merge", "Merge global variables", - false, false) - -bool GlobalMerge::doMerge(SmallVectorImpl &Globals, - Module &M, bool isConst, unsigned AddrSpace) const { - const TargetLowering *TLI = TM->getTargetLowering(); - const DataLayout *DL = TLI->getDataLayout(); - - // FIXME: Infer the maximum possible offset depending on the actual users - // (these max offsets are different for the users inside Thumb or ARM - // functions) - unsigned MaxOffset = TLI->getMaximalGlobalOffset(); - - // FIXME: Find better heuristics - std::stable_sort(Globals.begin(), Globals.end(), - [DL](const GlobalVariable *GV1, const GlobalVariable *GV2) { - Type *Ty1 = cast(GV1->getType())->getElementType(); - Type *Ty2 = cast(GV2->getType())->getElementType(); - - return (DL->getTypeAllocSize(Ty1) < DL->getTypeAllocSize(Ty2)); - }); - - Type *Int32Ty = Type::getInt32Ty(M.getContext()); - - assert(Globals.size() > 1); - - // FIXME: This simple solution merges globals all together as maximum as - // possible. However, with this solution it would be hard to remove dead - // global symbols at link-time. An alternative solution could be checking - // global symbols references function by function, and make the symbols - // being referred in the same function merged and we would probably need - // to introduce heuristic algorithm to solve the merge conflict from - // different functions. - for (size_t i = 0, e = Globals.size(); i != e; ) { - size_t j = 0; - uint64_t MergedSize = 0; - std::vector Tys; - std::vector Inits; - - bool HasExternal = false; - GlobalVariable *TheFirstExternal = 0; - for (j = i; j != e; ++j) { - Type *Ty = Globals[j]->getType()->getElementType(); - MergedSize += DL->getTypeAllocSize(Ty); - if (MergedSize > MaxOffset) { - break; - } - Tys.push_back(Ty); - Inits.push_back(Globals[j]->getInitializer()); - - if (Globals[j]->hasExternalLinkage() && !HasExternal) { - HasExternal = true; - TheFirstExternal = Globals[j]; - } - } - - // If merged variables doesn't have external linkage, we needn't to expose - // the symbol after merging. - GlobalValue::LinkageTypes Linkage = HasExternal - ? GlobalValue::ExternalLinkage - : GlobalValue::InternalLinkage; - - // If merged variables have external linkage, we use symbol name of the - // first variable merged as the suffix of global symbol name. This would - // be able to avoid the link-time naming conflict for globalm symbols. - Twine MergedGVName = HasExternal - ? "_MergedGlobals_" + TheFirstExternal->getName() - : "_MergedGlobals"; - - StructType *MergedTy = StructType::get(M.getContext(), Tys); - Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); - - GlobalVariable *MergedGV = new GlobalVariable( - M, MergedTy, isConst, Linkage, MergedInit, MergedGVName, nullptr, - GlobalVariable::NotThreadLocal, AddrSpace); - - for (size_t k = i; k < j; ++k) { - GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage(); - std::string Name = Globals[k]->getName(); - - Constant *Idx[2] = { - ConstantInt::get(Int32Ty, 0), - ConstantInt::get(Int32Ty, k-i) - }; - Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); - Globals[k]->replaceAllUsesWith(GEP); - Globals[k]->eraseFromParent(); - - if (Linkage != GlobalValue::InternalLinkage) { - // Generate a new alias... - auto *PTy = cast(GEP->getType()); - GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(), - Linkage, Name, GEP, &M); - } - - NumMerged++; - } - i = j; - } - - return true; -} - -void GlobalMerge::collectUsedGlobalVariables(Module &M) { - // Extract global variables from llvm.used array - const GlobalVariable *GV = M.getGlobalVariable("llvm.used"); - if (!GV || !GV->hasInitializer()) return; - - // Should be an array of 'i8*'. - const ConstantArray *InitList = cast(GV->getInitializer()); - - for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) - if (const GlobalVariable *G = - dyn_cast(InitList->getOperand(i)->stripPointerCasts())) - MustKeepGlobalVariables.insert(G); -} - -void GlobalMerge::setMustKeepGlobalVariables(Module &M) { - collectUsedGlobalVariables(M); - - for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn; - ++IFn) { - for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end(); - IBB != IEndBB; ++IBB) { - // Follow the invoke link to find the landing pad instruction - const InvokeInst *II = dyn_cast(IBB->getTerminator()); - if (!II) continue; - - const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst(); - // Look for globals in the clauses of the landing pad instruction - for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses(); - Idx != NumClauses; ++Idx) - if (const GlobalVariable *GV = - dyn_cast(LPInst->getClause(Idx) - ->stripPointerCasts())) - MustKeepGlobalVariables.insert(GV); - } - } -} - -bool GlobalMerge::doInitialization(Module &M) { - if (!EnableGlobalMerge) - return false; - - DenseMap > Globals, ConstGlobals, - BSSGlobals; - const TargetLowering *TLI = TM->getTargetLowering(); - const DataLayout *DL = TLI->getDataLayout(); - unsigned MaxOffset = TLI->getMaximalGlobalOffset(); - bool Changed = false; - setMustKeepGlobalVariables(M); - - // Grab all non-const globals. - for (Module::global_iterator I = M.global_begin(), - E = M.global_end(); I != E; ++I) { - // Merge is safe for "normal" internal or external globals only - if (I->isDeclaration() || I->isThreadLocal() || I->hasSection()) - continue; - - if (!(EnableGlobalMergeOnExternal && I->hasExternalLinkage()) && - !I->hasInternalLinkage()) - continue; - - PointerType *PT = dyn_cast(I->getType()); - assert(PT && "Global variable is not a pointer!"); - - unsigned AddressSpace = PT->getAddressSpace(); - - // Ignore fancy-aligned globals for now. - unsigned Alignment = DL->getPreferredAlignment(I); - Type *Ty = I->getType()->getElementType(); - if (Alignment > DL->getABITypeAlignment(Ty)) - continue; - - // Ignore all 'special' globals. - if (I->getName().startswith("llvm.") || - I->getName().startswith(".llvm.")) - continue; - - // Ignore all "required" globals: - if (isMustKeepGlobalVariable(I)) - continue; - - if (DL->getTypeAllocSize(Ty) < MaxOffset) { - if (TargetLoweringObjectFile::getKindForGlobal(I, *TM).isBSSLocal()) - BSSGlobals[AddressSpace].push_back(I); - else if (I->isConstant()) - ConstGlobals[AddressSpace].push_back(I); - else - Globals[AddressSpace].push_back(I); - } - } - - for (DenseMap >::iterator - I = Globals.begin(), E = Globals.end(); I != E; ++I) - if (I->second.size() > 1) - Changed |= doMerge(I->second, M, false, I->first); - - for (DenseMap >::iterator - I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) - if (I->second.size() > 1) - Changed |= doMerge(I->second, M, false, I->first); - - if (EnableGlobalMergeOnConst) - for (DenseMap >::iterator - I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I) - if (I->second.size() > 1) - Changed |= doMerge(I->second, M, true, I->first); - - return Changed; -} - -bool GlobalMerge::runOnFunction(Function &F) { - return false; -} - -bool GlobalMerge::doFinalization(Module &M) { - MustKeepGlobalVariables.clear(); - return false; -} - -Pass *llvm::createGlobalMergePass(const TargetMachine *TM) { - return new GlobalMerge(TM); -} diff --git a/lib/Transforms/Scalar/Scalar.cpp b/lib/Transforms/Scalar/Scalar.cpp index 5c7db5b16e..edf012d811 100644 --- a/lib/Transforms/Scalar/Scalar.cpp +++ b/lib/Transforms/Scalar/Scalar.cpp @@ -38,7 +38,6 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) { initializeDSEPass(Registry); initializeGVNPass(Registry); initializeEarlyCSEPass(Registry); - initializeGlobalMergePass(Registry); initializeIndVarSimplifyPass(Registry); initializeJumpThreadingPass(Registry); initializeLICMPass(Registry); -- cgit v1.2.3