ConstantMerge.cpp revision 7f8897f22e88271cfa114998a4d6088e7c8e8e11
1//===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the interface to a pass that merges duplicate global 11// constants together into a single constant that is shared. This is useful 12// because some passes (ie TraceValues) insert a lot of string constants into 13// the program, regardless of whether or not an existing string is available. 14// 15// Algorithm: ConstantMerge is designed to build up a map of available constants 16// and eliminate duplicates when it is initialized. 17// 18//===----------------------------------------------------------------------===// 19 20#include "llvm/Transforms/IPO.h" 21#include "llvm/Module.h" 22#include "llvm/Pass.h" 23#include "llvm/ADT/Statistic.h" 24using namespace llvm; 25 26namespace { 27 Statistic<> NumMerged("constmerge", "Number of global constants merged"); 28 29 struct ConstantMerge : public ModulePass { 30 // run - For this pass, process all of the globals in the module, 31 // eliminating duplicate constants. 32 // 33 bool runOnModule(Module &M); 34 }; 35 36 RegisterPass<ConstantMerge>X("constmerge","Merge Duplicate Global Constants"); 37} 38 39ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 40 41bool ConstantMerge::runOnModule(Module &M) { 42 // Map unique constant/section pairs to globals. We don't want to merge 43 // globals in different sections. 44 std::map<std::pair<Constant*, std::string>, GlobalVariable*> CMap; 45 46 // Replacements - This vector contains a list of replacements to perform. 47 std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements; 48 49 bool MadeChange = false; 50 51 // Iterate constant merging while we are still making progress. Merging two 52 // constants together may allow us to merge other constants together if the 53 // second level constants have initializers which point to the globals that 54 // were just merged. 55 while (1) { 56 // First pass: identify all globals that can be merged together, filling in 57 // the Replacements vector. We cannot do the replacement in this pass 58 // because doing so may cause initializers of other globals to be rewritten, 59 // invalidating the Constant* pointers in CMap. 60 // 61 for (Module::global_iterator GV = M.global_begin(), E = M.global_end(); 62 GV != E; ++GV) 63 // Only process constants with initializers. 64 if (GV->isConstant() && GV->hasInitializer()) { 65 Constant *Init = GV->getInitializer(); 66 67 // Check to see if the initializer is already known. 68 GlobalVariable *&Slot = CMap[std::make_pair(Init, GV->getSection())]; 69 70 if (Slot == 0) { // Nope, add it to the map. 71 Slot = GV; 72 } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! 73 // Make all uses of the duplicate constant use the canonical version. 74 Replacements.push_back(std::make_pair(GV, Slot)); 75 } else if (GV->hasInternalLinkage()) { 76 // Make all uses of the duplicate constant use the canonical version. 77 Replacements.push_back(std::make_pair(Slot, GV)); 78 Slot = GV; 79 } 80 } 81 82 if (Replacements.empty()) 83 return MadeChange; 84 CMap.clear(); 85 86 // Now that we have figured out which replacements must be made, do them all 87 // now. This avoid invalidating the pointers in CMap, which are unneeded 88 // now. 89 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 90 // Eliminate any uses of the dead global... 91 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 92 93 // Delete the global value from the module... 94 M.getGlobalList().erase(Replacements[i].first); 95 } 96 97 NumMerged += Replacements.size(); 98 Replacements.clear(); 99 } 100} 101