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