ConstantMerge.cpp revision a65d6a686e6ad865c61aec70c5bdfb30bf6f5b22
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/ADT/DenseMap.h" 27#include "llvm/ADT/SmallPtrSet.h" 28#include "llvm/ADT/Statistic.h" 29using namespace llvm; 30 31STATISTIC(NumMerged, "Number of global constants merged"); 32 33namespace { 34 struct ConstantMerge : public ModulePass { 35 static char ID; // Pass identification, replacement for typeid 36 ConstantMerge() : ModulePass(ID) { 37 initializeConstantMergePass(*PassRegistry::getPassRegistry()); 38 } 39 40 // run - For this pass, process all of the globals in the module, 41 // eliminating duplicate constants. 42 // 43 bool runOnModule(Module &M); 44 }; 45} 46 47char ConstantMerge::ID = 0; 48INITIALIZE_PASS(ConstantMerge, "constmerge", 49 "Merge Duplicate Global Constants", false, false) 50 51ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } 52 53 54 55/// Find values that are marked as llvm.used. 56static void FindUsedValues(GlobalVariable *LLVMUsed, 57 SmallPtrSet<const GlobalValue*, 8> &UsedValues) { 58 if (LLVMUsed == 0) return; 59 ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer()); 60 if (Inits == 0) return; 61 62 for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) 63 if (GlobalValue *GV = 64 dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts())) 65 UsedValues.insert(GV); 66} 67 68bool ConstantMerge::runOnModule(Module &M) { 69 // Find all the globals that are marked "used". These cannot be merged. 70 SmallPtrSet<const GlobalValue*, 8> UsedGlobals; 71 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals); 72 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals); 73 74 // Map unique constant/section pairs to globals. We don't want to merge 75 // globals in different sections. 76 DenseMap<Constant*, GlobalVariable*> CMap; 77 78 // Replacements - This vector contains a list of replacements to perform. 79 SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements; 80 81 bool MadeChange = false; 82 83 // Iterate constant merging while we are still making progress. Merging two 84 // constants together may allow us to merge other constants together if the 85 // second level constants have initializers which point to the globals that 86 // were just merged. 87 while (1) { 88 // First pass: identify all globals that can be merged together, filling in 89 // the Replacements vector. We cannot do the replacement in this pass 90 // because doing so may cause initializers of other globals to be rewritten, 91 // invalidating the Constant* pointers in CMap. 92 // 93 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 94 GVI != E; ) { 95 GlobalVariable *GV = GVI++; 96 97 // If this GV is dead, remove it. 98 GV->removeDeadConstantUsers(); 99 if (GV->use_empty() && GV->hasLocalLinkage()) { 100 GV->eraseFromParent(); 101 continue; 102 } 103 104 // Only process constants with initializers in the default addres space. 105 if (!GV->isConstant() ||!GV->hasDefinitiveInitializer() || 106 GV->getType()->getAddressSpace() != 0 || !GV->getSection().empty() || 107 // Don't touch values marked with attribute(used). 108 UsedGlobals.count(GV)) 109 continue; 110 111 112 113 Constant *Init = GV->getInitializer(); 114 115 // Check to see if the initializer is already known. 116 GlobalVariable *&Slot = CMap[Init]; 117 118 if (Slot == 0) { // Nope, add it to the map. 119 Slot = GV; 120 } else if (GV->hasLocalLinkage()) { // Yup, this is a duplicate! 121 // Make all uses of the duplicate constant use the canonical version. 122 Replacements.push_back(std::make_pair(GV, Slot)); 123 } 124 } 125 126 if (Replacements.empty()) 127 return MadeChange; 128 CMap.clear(); 129 130 // Now that we have figured out which replacements must be made, do them all 131 // now. This avoid invalidating the pointers in CMap, which are unneeded 132 // now. 133 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 134 // Eliminate any uses of the dead global. 135 Replacements[i].first->replaceAllUsesWith(Replacements[i].second); 136 137 // Delete the global value from the module. 138 Replacements[i].first->eraseFromParent(); 139 } 140 141 NumMerged += Replacements.size(); 142 Replacements.clear(); 143 } 144} 145