X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FConstantMerge.cpp;h=7c71065674ec798a538f6f75de871a0d91cff503;hb=4ee451de366474b9c228b4e5fa573795a715216d;hp=a635b8d21bed9982cbbc69fca5fe179a743b62c8;hpb=97e52e43361e77963145b95a576db11b4d14d309;p=oota-llvm.git diff --git a/lib/Transforms/IPO/ConstantMerge.cpp b/lib/Transforms/IPO/ConstantMerge.cpp index a635b8d21be..7c71065674e 100644 --- a/lib/Transforms/IPO/ConstantMerge.cpp +++ b/lib/Transforms/IPO/ConstantMerge.cpp @@ -1,103 +1,116 @@ -//===- ConstantMerge.cpp - Merge duplicate global constants -----------------=// +//===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file defines the interface to a pass that merges duplicate global // constants together into a single constant that is shared. This is useful // because some passes (ie TraceValues) insert a lot of string constants into -// the program, regardless of whether or not they duplicate an existing string. +// the program, regardless of whether or not an existing string is available. // // Algorithm: ConstantMerge is designed to build up a map of available constants -// and elminate duplicates when it is initialized. -// -// The DynamicConstantMerge method is a superset of the ConstantMerge algorithm -// that checks for each function to see if constants have been added to the -// constant pool since it was last run... if so, it processes them. +// and eliminate duplicates when it is initialized. // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/ConstantMerge.h" -#include "llvm/GlobalVariable.h" +#define DEBUG_TYPE "constmerge" +#include "llvm/Transforms/IPO.h" #include "llvm/Module.h" -#include "llvm/Function.h" #include "llvm/Pass.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Compiler.h" +using namespace llvm; -// mergeDuplicateConstants - Workhorse for the pass. This eliminates duplicate -// constants, starting at global ConstantNo, and adds vars to the map if they -// are new and unique. -// -static inline -bool mergeDuplicateConstants(Module *M, unsigned &ConstantNo, - std::map &CMap) { - Module::GlobalListType &GList = M->getGlobalList(); - if (GList.size() <= ConstantNo) return false; // No new constants - bool MadeChanges = false; - - for (; ConstantNo < GList.size(); ++ConstantNo) { - GlobalVariable *GV = GList[ConstantNo]; - if (GV->isConstant()) { // Only process constants - assert(GV->hasInitializer() && "Globals constants must have inits!"); - Constant *Init = GV->getInitializer(); - - // Check to see if the initializer is already known... - std::map::iterator I = CMap.find(Init); - - if (I == CMap.end()) { // Nope, add it to the map - CMap.insert(std::make_pair(Init, GV)); - } else { // Yup, this is a duplicate! - // Make all uses of the duplicate constant use the cannonical version... - GV->replaceAllUsesWith(I->second); - - // Remove and delete the global value from the module... - delete GList.remove(GList.begin()+ConstantNo); - - --ConstantNo; // Don't skip the next constant. - MadeChanges = true; - } - } - } - return MadeChanges; -} +STATISTIC(NumMerged, "Number of global constants merged"); namespace { - // FIXME: ConstantMerge should not be a FunctionPass!!! - class ConstantMerge : public FunctionPass { - protected: - std::map Constants; - unsigned LastConstantSeen; - public: - inline ConstantMerge() : LastConstantSeen(0) {} - - // doInitialization - For this pass, process all of the globals in the - // module, eliminating duplicate constants. + struct VISIBILITY_HIDDEN ConstantMerge : public ModulePass { + static char ID; // Pass identification, replacement for typeid + ConstantMerge() : ModulePass((intptr_t)&ID) {} + + // run - For this pass, process all of the globals in the module, + // eliminating duplicate constants. // - bool doInitialization(Module *M) { - return ::mergeDuplicateConstants(M, LastConstantSeen, Constants); - } - - bool runOnFunction(Function *) { return false; } - - // doFinalization - Clean up internal state for this module + bool runOnModule(Module &M); + }; + + char ConstantMerge::ID = 0; + RegisterPassX("constmerge","Merge Duplicate Global Constants"); +} + +ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } + +bool ConstantMerge::runOnModule(Module &M) { + // Map unique constant/section pairs to globals. We don't want to merge + // globals in different sections. + std::map, GlobalVariable*> CMap; + + // Replacements - This vector contains a list of replacements to perform. + std::vector > Replacements; + + bool MadeChange = false; + + // Iterate constant merging while we are still making progress. Merging two + // constants together may allow us to merge other constants together if the + // second level constants have initializers which point to the globals that + // were just merged. + while (1) { + // First pass: identify all globals that can be merged together, filling in + // the Replacements vector. We cannot do the replacement in this pass + // because doing so may cause initializers of other globals to be rewritten, + // invalidating the Constant* pointers in CMap. // - bool doFinalization(Module *M) { - LastConstantSeen = 0; - Constants.clear(); - return false; - } + for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); + GVI != E; ) { + GlobalVariable *GV = GVI++; + + // If this GV is dead, remove it. + GV->removeDeadConstantUsers(); + if (GV->use_empty() && GV->hasInternalLinkage()) { + GV->eraseFromParent(); + continue; + } + + // Only process constants with initializers. + if (GV->isConstant() && GV->hasInitializer()) { + Constant *Init = GV->getInitializer(); + + // Check to see if the initializer is already known. + GlobalVariable *&Slot = CMap[std::make_pair(Init, GV->getSection())]; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); + if (Slot == 0) { // Nope, add it to the map. + Slot = GV; + } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! + // Make all uses of the duplicate constant use the canonical version. + Replacements.push_back(std::make_pair(GV, Slot)); + } else if (GV->hasInternalLinkage()) { + // Make all uses of the duplicate constant use the canonical version. + Replacements.push_back(std::make_pair(Slot, GV)); + Slot = GV; + } + } } - }; - - struct DynamicConstantMerge : public ConstantMerge { - // runOnFunction - Check to see if any globals have been added to the - // global list for the module. If so, eliminate them. - // - bool runOnFunction(Function *F) { - return ::mergeDuplicateConstants(F->getParent(), LastConstantSeen, - Constants); + + if (Replacements.empty()) + return MadeChange; + CMap.clear(); + + // Now that we have figured out which replacements must be made, do them all + // now. This avoid invalidating the pointers in CMap, which are unneeded + // now. + for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { + // Eliminate any uses of the dead global... + Replacements[i].first->replaceAllUsesWith(Replacements[i].second); + + // Delete the global value from the module... + M.getGlobalList().erase(Replacements[i].first); } - }; -} -Pass *createConstantMergePass() { return new ConstantMerge(); } -Pass *createDynamicConstantMergePass() { return new DynamicConstantMerge(); } + NumMerged += Replacements.size(); + Replacements.clear(); + } +}