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" 24 using namespace llvm; 25 26 namespace { 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 RegisterOpt<ConstantMerge> X("constmerge","Merge Duplicate Global Constants"); 37 } 38 39 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 40 41 bool ConstantMerge::runOnModule(Module &M) { 42 std::map<Constant*, GlobalVariable*> CMap; 43 44 // Replacements - This vector contains a list of replacements to perform. 45 std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements; 46 47 bool MadeChange = false; 48 49 // Iterate constant merging while we are still making progress. Merging two 50 // constants together may allow us to merge other constants together if the 51 // second level constants have initializers which point to the globals that 52 // were just merged. 53 while (1) { 54 // First pass: identify all globals that can be merged together, filling in 55 // the Replacements vector. We cannot do the replacement in this pass 56 // because doing so may cause initializers of other globals to be rewritten, 57 // invalidating the Constant* pointers in CMap. 58 // 59 for (Module::global_iterator GV = M.global_begin(), E = M.global_end(); GV != E; ++GV) 60 // Only process constants with initializers 61 if (GV->isConstant() && GV->hasInitializer()) { 62 Constant *Init = GV->getInitializer(); 63 64 // Check to see if the initializer is already known... 65 std::map<Constant*, GlobalVariable*>::iterator I = CMap.find(Init); 66 67 if (I == CMap.end()) { // Nope, add it to the map 68 CMap.insert(I, std::make_pair(Init, GV)); 69 } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! 70 // Make all uses of the duplicate constant use the canonical version. 71 Replacements.push_back(std::make_pair(GV, I->second)); 72 } else if (I->second->hasInternalLinkage()) { 73 // Make all uses of the duplicate constant use the canonical version. 74 Replacements.push_back(std::make_pair(I->second, GV)); 75 I->second = GV; 76 } 77 } 78 79 if (Replacements.empty()) 80 return MadeChange; 81 CMap.clear(); 82 83 // Now that we have figured out which replacements must be made, do them all 84 // now. This avoid invalidating the pointers in CMap, which are unneeded 85 // now. 86 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 87 // Eliminate any uses of the dead global... 88 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 89 90 // Delete the global value from the module... 91 M.getGlobalList().erase(Replacements[i].first); 92 } 93 94 NumMerged += Replacements.size(); 95 Replacements.clear(); 96 } 97 } 98