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/Constants.h" 23 #include "llvm/DerivedTypes.h" 24 #include "llvm/Module.h" 25 #include "llvm/Pass.h" 26 #include "llvm/ADT/DenseMap.h" 27 #include "llvm/ADT/SmallPtrSet.h" 28 #include "llvm/ADT/Statistic.h" 29 using namespace llvm; 30 31 STATISTIC(NumMerged, "Number of global constants merged"); 32 33 namespace { 34 struct ConstantMerge : public ModulePass { 35 static char ID; // Pass identification, replacement for typeid 36 ConstantMerge() : ModulePass(ID) { 37 initializeConstantMergePass(*PassRegistry::getPassRegistry()); 38 } 39 40 // run - For this pass, process all of the globals in the module, 41 // eliminating duplicate constants. 42 // 43 bool runOnModule(Module &M); 44 }; 45 } 46 47 char ConstantMerge::ID = 0; 48 INITIALIZE_PASS(ConstantMerge, "constmerge", 49 "Merge Duplicate Global Constants", false, false) 50 51 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 52 53 54 55 /// Find values that are marked as llvm.used. 56 static void FindUsedValues(GlobalVariable *LLVMUsed, 57 SmallPtrSet<const GlobalValue*, 8> &UsedValues) { 58 if (LLVMUsed == 0) return; 59 ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer()); 60 if (Inits == 0) return; 61 62 for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) 63 if (GlobalValue *GV = 64 dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts())) 65 UsedValues.insert(GV); 66 } 67 68 // True if A is better than B. 69 static bool IsBetterCannonical(const GlobalVariable &A, 70 const GlobalVariable &B) { 71 if (!A.hasLocalLinkage() && B.hasLocalLinkage()) 72 return true; 73 74 if (A.hasLocalLinkage() && !B.hasLocalLinkage()) 75 return false; 76 77 return A.hasUnnamedAddr(); 78 } 79 80 bool ConstantMerge::runOnModule(Module &M) { 81 // Find all the globals that are marked "used". These cannot be merged. 82 SmallPtrSet<const GlobalValue*, 8> UsedGlobals; 83 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals); 84 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals); 85 86 // Map unique constant/section pairs to globals. We don't want to merge 87 // globals in different sections. 88 DenseMap<Constant*, GlobalVariable*> CMap; 89 90 // Replacements - This vector contains a list of replacements to perform. 91 SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements; 92 93 bool MadeChange = false; 94 95 // Iterate constant merging while we are still making progress. Merging two 96 // constants together may allow us to merge other constants together if the 97 // second level constants have initializers which point to the globals that 98 // were just merged. 99 while (1) { 100 101 // First: Find the canonical constants others will be merged with. 102 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 103 GVI != E; ) { 104 GlobalVariable *GV = GVI++; 105 106 // If this GV is dead, remove it. 107 GV->removeDeadConstantUsers(); 108 if (GV->use_empty() && GV->hasLocalLinkage()) { 109 GV->eraseFromParent(); 110 continue; 111 } 112 113 // Only process constants with initializers in the default address space. 114 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() || 115 GV->getType()->getAddressSpace() != 0 || GV->hasSection() || 116 // Don't touch values marked with attribute(used). 117 UsedGlobals.count(GV)) 118 continue; 119 120 Constant *Init = GV->getInitializer(); 121 122 // Check to see if the initializer is already known. 123 GlobalVariable *&Slot = CMap[Init]; 124 125 // If this is the first constant we find or if the old on is local, 126 // replace with the current one. It the current is externally visible 127 // it cannot be replace, but can be the canonical constant we merge with. 128 if (Slot == 0 || IsBetterCannonical(*GV, *Slot)) { 129 Slot = GV; 130 } 131 } 132 133 // Second: identify all globals that can be merged together, filling in 134 // the Replacements vector. We cannot do the replacement in this pass 135 // because doing so may cause initializers of other globals to be rewritten, 136 // invalidating the Constant* pointers in CMap. 137 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 138 GVI != E; ) { 139 GlobalVariable *GV = GVI++; 140 141 // Only process constants with initializers in the default address space. 142 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() || 143 GV->getType()->getAddressSpace() != 0 || GV->hasSection() || 144 // Don't touch values marked with attribute(used). 145 UsedGlobals.count(GV)) 146 continue; 147 148 // We can only replace constant with local linkage. 149 if (!GV->hasLocalLinkage()) 150 continue; 151 152 Constant *Init = GV->getInitializer(); 153 154 // Check to see if the initializer is already known. 155 GlobalVariable *Slot = CMap[Init]; 156 157 if (!Slot || Slot == GV) 158 continue; 159 160 if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr()) 161 continue; 162 163 if (!GV->hasUnnamedAddr()) 164 Slot->setUnnamedAddr(false); 165 166 // Make all uses of the duplicate constant use the canonical version. 167 Replacements.push_back(std::make_pair(GV, Slot)); 168 } 169 170 if (Replacements.empty()) 171 return MadeChange; 172 CMap.clear(); 173 174 // Now that we have figured out which replacements must be made, do them all 175 // now. This avoid invalidating the pointers in CMap, which are unneeded 176 // now. 177 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 178 // Eliminate any uses of the dead global. 179 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 180 181 // Delete the global value from the module. 182 assert(Replacements[i].first->hasLocalLinkage() && 183 "Refusing to delete an externally visible global variable."); 184 Replacements[i].first->eraseFromParent(); 185 } 186 187 NumMerged += Replacements.size(); 188 Replacements.clear(); 189 } 190 } 191
