LLVM API Documentation

ConstantMerge.cpp
Go to the documentation of this file.
00001 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the interface to a pass that merges duplicate global
00011 // constants together into a single constant that is shared.  This is useful
00012 // because some passes (ie TraceValues) insert a lot of string constants into
00013 // the program, regardless of whether or not an existing string is available.
00014 //
00015 // Algorithm: ConstantMerge is designed to build up a map of available constants
00016 // and eliminate duplicates when it is initialized.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "constmerge"
00021 #include "llvm/Transforms/IPO.h"
00022 #include "llvm/ADT/DenseMap.h"
00023 #include "llvm/ADT/PointerIntPair.h"
00024 #include "llvm/ADT/SmallPtrSet.h"
00025 #include "llvm/ADT/Statistic.h"
00026 #include "llvm/IR/Constants.h"
00027 #include "llvm/IR/DataLayout.h"
00028 #include "llvm/IR/DerivedTypes.h"
00029 #include "llvm/IR/Module.h"
00030 #include "llvm/IR/Operator.h"
00031 #include "llvm/Pass.h"
00032 using namespace llvm;
00033 
00034 STATISTIC(NumMerged, "Number of global constants merged");
00035 
00036 namespace {
00037   struct ConstantMerge : public ModulePass {
00038     static char ID; // Pass identification, replacement for typeid
00039     ConstantMerge() : ModulePass(ID) {
00040       initializeConstantMergePass(*PassRegistry::getPassRegistry());
00041     }
00042 
00043     // For this pass, process all of the globals in the module, eliminating
00044     // duplicate constants.
00045     bool runOnModule(Module &M) override;
00046 
00047     // Return true iff we can determine the alignment of this global variable.
00048     bool hasKnownAlignment(GlobalVariable *GV) const;
00049 
00050     // Return the alignment of the global, including converting the default
00051     // alignment to a concrete value.
00052     unsigned getAlignment(GlobalVariable *GV) const;
00053 
00054     const DataLayout *DL;
00055   };
00056 }
00057 
00058 char ConstantMerge::ID = 0;
00059 INITIALIZE_PASS(ConstantMerge, "constmerge",
00060                 "Merge Duplicate Global Constants", false, false)
00061 
00062 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
00063 
00064 
00065 
00066 /// Find values that are marked as llvm.used.
00067 static void FindUsedValues(GlobalVariable *LLVMUsed,
00068                            SmallPtrSet<const GlobalValue*, 8> &UsedValues) {
00069   if (LLVMUsed == 0) return;
00070   ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
00071 
00072   for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) {
00073     Value *Operand = Inits->getOperand(i)->stripPointerCastsNoFollowAliases();
00074     GlobalValue *GV = cast<GlobalValue>(Operand);
00075     UsedValues.insert(GV);
00076   }
00077 }
00078 
00079 // True if A is better than B.
00080 static bool IsBetterCanonical(const GlobalVariable &A,
00081                               const GlobalVariable &B) {
00082   if (!A.hasLocalLinkage() && B.hasLocalLinkage())
00083     return true;
00084 
00085   if (A.hasLocalLinkage() && !B.hasLocalLinkage())
00086     return false;
00087 
00088   return A.hasUnnamedAddr();
00089 }
00090 
00091 bool ConstantMerge::hasKnownAlignment(GlobalVariable *GV) const {
00092   return DL || GV->getAlignment() != 0;
00093 }
00094 
00095 unsigned ConstantMerge::getAlignment(GlobalVariable *GV) const {
00096   unsigned Align = GV->getAlignment();
00097   if (Align)
00098     return Align;
00099   if (DL)
00100     return DL->getPreferredAlignment(GV);
00101   return 0;
00102 }
00103 
00104 bool ConstantMerge::runOnModule(Module &M) {
00105   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
00106   DL = DLP ? &DLP->getDataLayout() : 0;
00107 
00108   // Find all the globals that are marked "used".  These cannot be merged.
00109   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
00110   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
00111   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
00112   
00113   // Map unique <constants, has-unknown-alignment> pairs to globals.  We don't
00114   // want to merge globals of unknown alignment with those of explicit
00115   // alignment.  If we have DataLayout, we always know the alignment.
00116   DenseMap<PointerIntPair<Constant*, 1, bool>, GlobalVariable*> CMap;
00117 
00118   // Replacements - This vector contains a list of replacements to perform.
00119   SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
00120 
00121   bool MadeChange = false;
00122 
00123   // Iterate constant merging while we are still making progress.  Merging two
00124   // constants together may allow us to merge other constants together if the
00125   // second level constants have initializers which point to the globals that
00126   // were just merged.
00127   while (1) {
00128 
00129     // First: Find the canonical constants others will be merged with.
00130     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
00131          GVI != E; ) {
00132       GlobalVariable *GV = GVI++;
00133 
00134       // If this GV is dead, remove it.
00135       GV->removeDeadConstantUsers();
00136       if (GV->use_empty() && GV->hasLocalLinkage()) {
00137         GV->eraseFromParent();
00138         continue;
00139       }
00140 
00141       // Only process constants with initializers in the default address space.
00142       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
00143           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
00144           // Don't touch values marked with attribute(used).
00145           UsedGlobals.count(GV))
00146         continue;
00147 
00148       // This transformation is legal for weak ODR globals in the sense it
00149       // doesn't change semantics, but we really don't want to perform it
00150       // anyway; it's likely to pessimize code generation, and some tools
00151       // (like the Darwin linker in cases involving CFString) don't expect it.
00152       if (GV->isWeakForLinker())
00153         continue;
00154 
00155       Constant *Init = GV->getInitializer();
00156 
00157       // Check to see if the initializer is already known.
00158       PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
00159       GlobalVariable *&Slot = CMap[Pair];
00160 
00161       // If this is the first constant we find or if the old one is local,
00162       // replace with the current one. If the current is externally visible
00163       // it cannot be replace, but can be the canonical constant we merge with.
00164       if (Slot == 0 || IsBetterCanonical(*GV, *Slot))
00165         Slot = GV;
00166     }
00167 
00168     // Second: identify all globals that can be merged together, filling in
00169     // the Replacements vector.  We cannot do the replacement in this pass
00170     // because doing so may cause initializers of other globals to be rewritten,
00171     // invalidating the Constant* pointers in CMap.
00172     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
00173          GVI != E; ) {
00174       GlobalVariable *GV = GVI++;
00175 
00176       // Only process constants with initializers in the default address space.
00177       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
00178           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
00179           // Don't touch values marked with attribute(used).
00180           UsedGlobals.count(GV))
00181         continue;
00182 
00183       // We can only replace constant with local linkage.
00184       if (!GV->hasLocalLinkage())
00185         continue;
00186 
00187       Constant *Init = GV->getInitializer();
00188 
00189       // Check to see if the initializer is already known.
00190       PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
00191       GlobalVariable *Slot = CMap[Pair];
00192 
00193       if (!Slot || Slot == GV)
00194         continue;
00195 
00196       if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr())
00197         continue;
00198 
00199       if (!GV->hasUnnamedAddr())
00200         Slot->setUnnamedAddr(false);
00201 
00202       // Make all uses of the duplicate constant use the canonical version.
00203       Replacements.push_back(std::make_pair(GV, Slot));
00204     }
00205 
00206     if (Replacements.empty())
00207       return MadeChange;
00208     CMap.clear();
00209 
00210     // Now that we have figured out which replacements must be made, do them all
00211     // now.  This avoid invalidating the pointers in CMap, which are unneeded
00212     // now.
00213     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
00214       // Bump the alignment if necessary.
00215       if (Replacements[i].first->getAlignment() ||
00216           Replacements[i].second->getAlignment()) {
00217         Replacements[i].second->setAlignment(
00218             std::max(getAlignment(Replacements[i].first),
00219                      getAlignment(Replacements[i].second)));
00220       }
00221 
00222       // Eliminate any uses of the dead global.
00223       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
00224 
00225       // Delete the global value from the module.
00226       assert(Replacements[i].first->hasLocalLinkage() &&
00227              "Refusing to delete an externally visible global variable.");
00228       Replacements[i].first->eraseFromParent();
00229     }
00230 
00231     NumMerged += Replacements.size();
00232     Replacements.clear();
00233   }
00234 }