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" 31using namespace llvm; 32 33STATISTIC(NumMerged, "Number of global constants merged"); 34 35namespace { 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 57char ConstantMerge::ID = 0; 58INITIALIZE_PASS(ConstantMerge, "constmerge", 59 "Merge Duplicate Global Constants", false, false) 60 61ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 62 63 64 65/// Find values that are marked as llvm.used. 66static 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. 79static 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 90bool ConstantMerge::hasKnownAlignment(GlobalVariable *GV) const { 91 return TD || GV->getAlignment() != 0; 92} 93 94unsigned ConstantMerge::getAlignment(GlobalVariable *GV) const { 95 if (TD) 96 return TD->getPreferredAlignment(GV); 97 return GV->getAlignment(); 98} 99 100bool 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 // This transformation is legal for weak ODR globals in the sense it 144 // doesn't change semantics, but we really don't want to perform it 145 // anyway; it's likely to pessimize code generation, and some tools 146 // (like the Darwin linker in cases involving CFString) don't expect it. 147 if (GV->isWeakForLinker()) 148 continue; 149 150 Constant *Init = GV->getInitializer(); 151 152 // Check to see if the initializer is already known. 153 PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV)); 154 GlobalVariable *&Slot = CMap[Pair]; 155 156 // If this is the first constant we find or if the old one is local, 157 // replace with the current one. If the current is externally visible 158 // it cannot be replace, but can be the canonical constant we merge with. 159 if (Slot == 0 || IsBetterCannonical(*GV, *Slot)) 160 Slot = GV; 161 } 162 163 // Second: identify all globals that can be merged together, filling in 164 // the Replacements vector. We cannot do the replacement in this pass 165 // because doing so may cause initializers of other globals to be rewritten, 166 // invalidating the Constant* pointers in CMap. 167 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 168 GVI != E; ) { 169 GlobalVariable *GV = GVI++; 170 171 // Only process constants with initializers in the default address space. 172 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() || 173 GV->getType()->getAddressSpace() != 0 || GV->hasSection() || 174 // Don't touch values marked with attribute(used). 175 UsedGlobals.count(GV)) 176 continue; 177 178 // We can only replace constant with local linkage. 179 if (!GV->hasLocalLinkage()) 180 continue; 181 182 Constant *Init = GV->getInitializer(); 183 184 // Check to see if the initializer is already known. 185 PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV)); 186 GlobalVariable *Slot = CMap[Pair]; 187 188 if (!Slot || Slot == GV) 189 continue; 190 191 if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr()) 192 continue; 193 194 if (!GV->hasUnnamedAddr()) 195 Slot->setUnnamedAddr(false); 196 197 // Make all uses of the duplicate constant use the canonical version. 198 Replacements.push_back(std::make_pair(GV, Slot)); 199 } 200 201 if (Replacements.empty()) 202 return MadeChange; 203 CMap.clear(); 204 205 // Now that we have figured out which replacements must be made, do them all 206 // now. This avoid invalidating the pointers in CMap, which are unneeded 207 // now. 208 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 209 // Bump the alignment if necessary. 210 if (Replacements[i].first->getAlignment() || 211 Replacements[i].second->getAlignment()) { 212 Replacements[i].second->setAlignment(std::max( 213 Replacements[i].first->getAlignment(), 214 Replacements[i].second->getAlignment())); 215 } 216 217 // Eliminate any uses of the dead global. 218 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 219 220 // Delete the global value from the module. 221 assert(Replacements[i].first->hasLocalLinkage() && 222 "Refusing to delete an externally visible global variable."); 223 Replacements[i].first->eraseFromParent(); 224 } 225 226 NumMerged += Replacements.size(); 227 Replacements.clear(); 228 } 229} 230