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