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