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