ConstantMerge.cpp revision 249ddbfb29dfc2335f98984878c52b2c77703417
1//===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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#define DEBUG_TYPE "constmerge" 21#include "llvm/Transforms/IPO.h" 22#include "llvm/Module.h" 23#include "llvm/Pass.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/Support/Compiler.h" 26#include <map> 27using namespace llvm; 28 29STATISTIC(NumMerged, "Number of global constants merged"); 30 31namespace { 32 struct VISIBILITY_HIDDEN ConstantMerge : public ModulePass { 33 static char ID; // Pass identification, replacement for typeid 34 ConstantMerge() : ModulePass((intptr_t)&ID) {} 35 36 // run - For this pass, process all of the globals in the module, 37 // eliminating duplicate constants. 38 // 39 bool runOnModule(Module &M); 40 }; 41 42 char ConstantMerge::ID = 0; 43 RegisterPass<ConstantMerge>X("constmerge","Merge Duplicate Global Constants"); 44} 45 46ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 47 48bool ConstantMerge::runOnModule(Module &M) { 49 // Map unique constant/section pairs to globals. We don't want to merge 50 // globals in different sections. 51 std::map<std::pair<Constant*, std::string>, GlobalVariable*> CMap; 52 53 // Replacements - This vector contains a list of replacements to perform. 54 std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements; 55 56 bool MadeChange = false; 57 58 // Iterate constant merging while we are still making progress. Merging two 59 // constants together may allow us to merge other constants together if the 60 // second level constants have initializers which point to the globals that 61 // were just merged. 62 while (1) { 63 // First pass: identify all globals that can be merged together, filling in 64 // the Replacements vector. We cannot do the replacement in this pass 65 // because doing so may cause initializers of other globals to be rewritten, 66 // invalidating the Constant* pointers in CMap. 67 // 68 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 69 GVI != E; ) { 70 GlobalVariable *GV = GVI++; 71 72 // If this GV is dead, remove it. 73 GV->removeDeadConstantUsers(); 74 if (GV->use_empty() && GV->hasInternalLinkage()) { 75 GV->eraseFromParent(); 76 continue; 77 } 78 79 // Only process constants with initializers. 80 if (GV->isConstant() && GV->hasInitializer()) { 81 Constant *Init = GV->getInitializer(); 82 83 // Check to see if the initializer is already known. 84 GlobalVariable *&Slot = CMap[std::make_pair(Init, GV->getSection())]; 85 86 if (Slot == 0) { // Nope, add it to the map. 87 Slot = GV; 88 } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! 89 // Make all uses of the duplicate constant use the canonical version. 90 Replacements.push_back(std::make_pair(GV, Slot)); 91 } 92 } 93 } 94 95 if (Replacements.empty()) 96 return MadeChange; 97 CMap.clear(); 98 99 // Now that we have figured out which replacements must be made, do them all 100 // now. This avoid invalidating the pointers in CMap, which are unneeded 101 // now. 102 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 103 // Eliminate any uses of the dead global... 104 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 105 106 // Delete the global value from the module... 107 M.getGlobalList().erase(Replacements[i].first); 108 } 109 110 NumMerged += Replacements.size(); 111 Replacements.clear(); 112 } 113} 114