ConstantMerge.cpp revision 7569322765651f19eea0609fb082e6b267d5d2b5
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/DerivedTypes.h" 23#include "llvm/Module.h" 24#include "llvm/Pass.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/Statistic.h" 27using namespace llvm; 28 29STATISTIC(NumMerged, "Number of global constants merged"); 30 31namespace { 32 struct 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; 44INITIALIZE_PASS(ConstantMerge, "constmerge", 45 "Merge Duplicate Global Constants", false, false); 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 DenseMap<Constant*, GlobalVariable*> CMap; 53 54 // Replacements - This vector contains a list of replacements to perform. 55 SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> 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 in the default addres space. 81 if (!GV->isConstant() ||!GV->hasDefinitiveInitializer() || 82 GV->getType()->getAddressSpace() != 0 || !GV->getSection().empty()) 83 continue; 84 85 Constant *Init = GV->getInitializer(); 86 87 // Check to see if the initializer is already known. 88 GlobalVariable *&Slot = CMap[Init]; 89 90 if (Slot == 0) { // Nope, add it to the map. 91 Slot = GV; 92 } else if (GV->hasLocalLinkage()) { // Yup, this is a duplicate! 93 // Make all uses of the duplicate constant use the canonical version. 94 Replacements.push_back(std::make_pair(GV, Slot)); 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 Replacements[i].first->eraseFromParent(); 111 } 112 113 NumMerged += Replacements.size(); 114 Replacements.clear(); 115 } 116} 117