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