1193323Sed//===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the interface to a pass that merges duplicate global 11193323Sed// constants together into a single constant that is shared. This is useful 12193323Sed// because some passes (ie TraceValues) insert a lot of string constants into 13193323Sed// the program, regardless of whether or not an existing string is available. 14193323Sed// 15193323Sed// Algorithm: ConstantMerge is designed to build up a map of available constants 16193323Sed// and eliminate duplicates when it is initialized. 17193323Sed// 18193323Sed//===----------------------------------------------------------------------===// 19193323Sed 20193323Sed#define DEBUG_TYPE "constmerge" 21193323Sed#include "llvm/Transforms/IPO.h" 22203954Srdivacky#include "llvm/ADT/DenseMap.h" 23226633Sdim#include "llvm/ADT/PointerIntPair.h" 24212904Sdim#include "llvm/ADT/SmallPtrSet.h" 25193323Sed#include "llvm/ADT/Statistic.h" 26249423Sdim#include "llvm/IR/Constants.h" 27249423Sdim#include "llvm/IR/DataLayout.h" 28249423Sdim#include "llvm/IR/DerivedTypes.h" 29249423Sdim#include "llvm/IR/Module.h" 30251662Sdim#include "llvm/IR/Operator.h" 31249423Sdim#include "llvm/Pass.h" 32193323Sedusing namespace llvm; 33193323Sed 34193323SedSTATISTIC(NumMerged, "Number of global constants merged"); 35193323Sed 36193323Sednamespace { 37198892Srdivacky struct ConstantMerge : public ModulePass { 38193323Sed static char ID; // Pass identification, replacement for typeid 39218893Sdim ConstantMerge() : ModulePass(ID) { 40218893Sdim initializeConstantMergePass(*PassRegistry::getPassRegistry()); 41218893Sdim } 42193323Sed 43226633Sdim // For this pass, process all of the globals in the module, eliminating 44226633Sdim // duplicate constants. 45193323Sed bool runOnModule(Module &M); 46226633Sdim 47226633Sdim // Return true iff we can determine the alignment of this global variable. 48226633Sdim bool hasKnownAlignment(GlobalVariable *GV) const; 49226633Sdim 50226633Sdim // Return the alignment of the global, including converting the default 51226633Sdim // alignment to a concrete value. 52226633Sdim unsigned getAlignment(GlobalVariable *GV) const; 53226633Sdim 54243830Sdim const DataLayout *TD; 55193323Sed }; 56193323Sed} 57193323Sed 58193323Sedchar ConstantMerge::ID = 0; 59212904SdimINITIALIZE_PASS(ConstantMerge, "constmerge", 60218893Sdim "Merge Duplicate Global Constants", false, false) 61193323Sed 62193323SedModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 63193323Sed 64212904Sdim 65212904Sdim 66212904Sdim/// Find values that are marked as llvm.used. 67212904Sdimstatic void FindUsedValues(GlobalVariable *LLVMUsed, 68212904Sdim SmallPtrSet<const GlobalValue*, 8> &UsedValues) { 69212904Sdim if (LLVMUsed == 0) return; 70251662Sdim ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer()); 71251662Sdim 72251662Sdim for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) { 73251662Sdim Value *Operand = Inits->getOperand(i)->stripPointerCastsNoFollowAliases(); 74251662Sdim GlobalValue *GV = cast<GlobalValue>(Operand); 75251662Sdim UsedValues.insert(GV); 76251662Sdim } 77212904Sdim} 78212904Sdim 79218893Sdim// True if A is better than B. 80218893Sdimstatic bool IsBetterCannonical(const GlobalVariable &A, 81218893Sdim const GlobalVariable &B) { 82218893Sdim if (!A.hasLocalLinkage() && B.hasLocalLinkage()) 83218893Sdim return true; 84218893Sdim 85218893Sdim if (A.hasLocalLinkage() && !B.hasLocalLinkage()) 86218893Sdim return false; 87218893Sdim 88218893Sdim return A.hasUnnamedAddr(); 89218893Sdim} 90218893Sdim 91226633Sdimbool ConstantMerge::hasKnownAlignment(GlobalVariable *GV) const { 92226633Sdim return TD || GV->getAlignment() != 0; 93226633Sdim} 94226633Sdim 95226633Sdimunsigned ConstantMerge::getAlignment(GlobalVariable *GV) const { 96226633Sdim if (TD) 97226633Sdim return TD->getPreferredAlignment(GV); 98226633Sdim return GV->getAlignment(); 99226633Sdim} 100226633Sdim 101193323Sedbool ConstantMerge::runOnModule(Module &M) { 102243830Sdim TD = getAnalysisIfAvailable<DataLayout>(); 103226633Sdim 104212904Sdim // Find all the globals that are marked "used". These cannot be merged. 105212904Sdim SmallPtrSet<const GlobalValue*, 8> UsedGlobals; 106212904Sdim FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals); 107212904Sdim FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals); 108212904Sdim 109226633Sdim // Map unique <constants, has-unknown-alignment> pairs to globals. We don't 110226633Sdim // want to merge globals of unknown alignment with those of explicit 111243830Sdim // alignment. If we have DataLayout, we always know the alignment. 112226633Sdim DenseMap<PointerIntPair<Constant*, 1, bool>, GlobalVariable*> CMap; 113193323Sed 114193323Sed // Replacements - This vector contains a list of replacements to perform. 115203954Srdivacky SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements; 116193323Sed 117193323Sed bool MadeChange = false; 118193323Sed 119193323Sed // Iterate constant merging while we are still making progress. Merging two 120193323Sed // constants together may allow us to merge other constants together if the 121193323Sed // second level constants have initializers which point to the globals that 122193323Sed // were just merged. 123193323Sed while (1) { 124218893Sdim 125218893Sdim // First: Find the canonical constants others will be merged with. 126193323Sed for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 127193323Sed GVI != E; ) { 128193323Sed GlobalVariable *GV = GVI++; 129218893Sdim 130193323Sed // If this GV is dead, remove it. 131193323Sed GV->removeDeadConstantUsers(); 132193323Sed if (GV->use_empty() && GV->hasLocalLinkage()) { 133193323Sed GV->eraseFromParent(); 134193323Sed continue; 135193323Sed } 136218893Sdim 137218893Sdim // Only process constants with initializers in the default address space. 138218893Sdim if (!GV->isConstant() || !GV->hasDefinitiveInitializer() || 139218893Sdim GV->getType()->getAddressSpace() != 0 || GV->hasSection() || 140212904Sdim // Don't touch values marked with attribute(used). 141212904Sdim UsedGlobals.count(GV)) 142203954Srdivacky continue; 143218893Sdim 144234353Sdim // This transformation is legal for weak ODR globals in the sense it 145234353Sdim // doesn't change semantics, but we really don't want to perform it 146234353Sdim // anyway; it's likely to pessimize code generation, and some tools 147234353Sdim // (like the Darwin linker in cases involving CFString) don't expect it. 148234353Sdim if (GV->isWeakForLinker()) 149234353Sdim continue; 150234353Sdim 151203954Srdivacky Constant *Init = GV->getInitializer(); 152193323Sed 153203954Srdivacky // Check to see if the initializer is already known. 154226633Sdim PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV)); 155226633Sdim GlobalVariable *&Slot = CMap[Pair]; 156193323Sed 157234353Sdim // If this is the first constant we find or if the old one is local, 158234353Sdim // replace with the current one. If the current is externally visible 159218893Sdim // it cannot be replace, but can be the canonical constant we merge with. 160234353Sdim if (Slot == 0 || IsBetterCannonical(*GV, *Slot)) 161203954Srdivacky Slot = GV; 162193323Sed } 163193323Sed 164218893Sdim // Second: identify all globals that can be merged together, filling in 165218893Sdim // the Replacements vector. We cannot do the replacement in this pass 166218893Sdim // because doing so may cause initializers of other globals to be rewritten, 167218893Sdim // invalidating the Constant* pointers in CMap. 168218893Sdim for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 169218893Sdim GVI != E; ) { 170218893Sdim GlobalVariable *GV = GVI++; 171218893Sdim 172218893Sdim // Only process constants with initializers in the default address space. 173218893Sdim if (!GV->isConstant() || !GV->hasDefinitiveInitializer() || 174218893Sdim GV->getType()->getAddressSpace() != 0 || GV->hasSection() || 175218893Sdim // Don't touch values marked with attribute(used). 176218893Sdim UsedGlobals.count(GV)) 177218893Sdim continue; 178218893Sdim 179218893Sdim // We can only replace constant with local linkage. 180218893Sdim if (!GV->hasLocalLinkage()) 181218893Sdim continue; 182218893Sdim 183218893Sdim Constant *Init = GV->getInitializer(); 184218893Sdim 185218893Sdim // Check to see if the initializer is already known. 186226633Sdim PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV)); 187226633Sdim GlobalVariable *Slot = CMap[Pair]; 188218893Sdim 189218893Sdim if (!Slot || Slot == GV) 190218893Sdim continue; 191218893Sdim 192218893Sdim if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr()) 193218893Sdim continue; 194218893Sdim 195218893Sdim if (!GV->hasUnnamedAddr()) 196218893Sdim Slot->setUnnamedAddr(false); 197218893Sdim 198218893Sdim // Make all uses of the duplicate constant use the canonical version. 199218893Sdim Replacements.push_back(std::make_pair(GV, Slot)); 200218893Sdim } 201218893Sdim 202193323Sed if (Replacements.empty()) 203193323Sed return MadeChange; 204193323Sed CMap.clear(); 205193323Sed 206193323Sed // Now that we have figured out which replacements must be made, do them all 207193323Sed // now. This avoid invalidating the pointers in CMap, which are unneeded 208193323Sed // now. 209193323Sed for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 210226633Sdim // Bump the alignment if necessary. 211226633Sdim if (Replacements[i].first->getAlignment() || 212226633Sdim Replacements[i].second->getAlignment()) { 213226633Sdim Replacements[i].second->setAlignment(std::max( 214226633Sdim Replacements[i].first->getAlignment(), 215226633Sdim Replacements[i].second->getAlignment())); 216226633Sdim } 217226633Sdim 218203954Srdivacky // Eliminate any uses of the dead global. 219193323Sed Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 220193323Sed 221203954Srdivacky // Delete the global value from the module. 222218893Sdim assert(Replacements[i].first->hasLocalLinkage() && 223218893Sdim "Refusing to delete an externally visible global variable."); 224203954Srdivacky Replacements[i].first->eraseFromParent(); 225193323Sed } 226193323Sed 227193323Sed NumMerged += Replacements.size(); 228193323Sed Replacements.clear(); 229193323Sed } 230193323Sed} 231