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