LLVM  mainline
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   };
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                            SmallPtrSetImpl<const GlobalValue*> &UsedValues) {
00069   if (!LLVMUsed) 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 unsigned ConstantMerge::getAlignment(GlobalVariable *GV) const {
00092   unsigned Align = GV->getAlignment();
00093   if (Align)
00094     return Align;
00095   return GV->getParent()->getDataLayout().getPreferredAlignment(GV);
00096 }
00097 
00098 bool ConstantMerge::runOnModule(Module &M) {
00099 
00100   // Find all the globals that are marked "used".  These cannot be merged.
00101   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
00102   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
00103   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
00104 
00105   // Map unique constants to globals.
00106   DenseMap<Constant *, GlobalVariable *> CMap;
00107 
00108   // Replacements - This vector contains a list of replacements to perform.
00109   SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
00110 
00111   bool MadeChange = false;
00112 
00113   // Iterate constant merging while we are still making progress.  Merging two
00114   // constants together may allow us to merge other constants together if the
00115   // second level constants have initializers which point to the globals that
00116   // were just merged.
00117   while (1) {
00118 
00119     // First: Find the canonical constants others will be merged with.
00120     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
00121          GVI != E; ) {
00122       GlobalVariable *GV = GVI++;
00123 
00124       // If this GV is dead, remove it.
00125       GV->removeDeadConstantUsers();
00126       if (GV->use_empty() && GV->hasLocalLinkage()) {
00127         GV->eraseFromParent();
00128         continue;
00129       }
00130 
00131       // Only process constants with initializers in the default address space.
00132       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
00133           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
00134           // Don't touch values marked with attribute(used).
00135           UsedGlobals.count(GV))
00136         continue;
00137 
00138       // This transformation is legal for weak ODR globals in the sense it
00139       // doesn't change semantics, but we really don't want to perform it
00140       // anyway; it's likely to pessimize code generation, and some tools
00141       // (like the Darwin linker in cases involving CFString) don't expect it.
00142       if (GV->isWeakForLinker())
00143         continue;
00144 
00145       Constant *Init = GV->getInitializer();
00146 
00147       // Check to see if the initializer is already known.
00148       GlobalVariable *&Slot = CMap[Init];
00149 
00150       // If this is the first constant we find or if the old one is local,
00151       // replace with the current one. If the current is externally visible
00152       // it cannot be replace, but can be the canonical constant we merge with.
00153       if (!Slot || IsBetterCanonical(*GV, *Slot))
00154         Slot = GV;
00155     }
00156 
00157     // Second: identify all globals that can be merged together, filling in
00158     // the Replacements vector.  We cannot do the replacement in this pass
00159     // because doing so may cause initializers of other globals to be rewritten,
00160     // invalidating the Constant* pointers in CMap.
00161     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
00162          GVI != E; ) {
00163       GlobalVariable *GV = GVI++;
00164 
00165       // Only process constants with initializers in the default address space.
00166       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
00167           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
00168           // Don't touch values marked with attribute(used).
00169           UsedGlobals.count(GV))
00170         continue;
00171 
00172       // We can only replace constant with local linkage.
00173       if (!GV->hasLocalLinkage())
00174         continue;
00175 
00176       Constant *Init = GV->getInitializer();
00177 
00178       // Check to see if the initializer is already known.
00179       GlobalVariable *Slot = CMap[Init];
00180 
00181       if (!Slot || Slot == GV)
00182         continue;
00183 
00184       if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr())
00185         continue;
00186 
00187       if (!GV->hasUnnamedAddr())
00188         Slot->setUnnamedAddr(false);
00189 
00190       // Make all uses of the duplicate constant use the canonical version.
00191       Replacements.push_back(std::make_pair(GV, Slot));
00192     }
00193 
00194     if (Replacements.empty())
00195       return MadeChange;
00196     CMap.clear();
00197 
00198     // Now that we have figured out which replacements must be made, do them all
00199     // now.  This avoid invalidating the pointers in CMap, which are unneeded
00200     // now.
00201     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
00202       // Bump the alignment if necessary.
00203       if (Replacements[i].first->getAlignment() ||
00204           Replacements[i].second->getAlignment()) {
00205         Replacements[i].second->setAlignment(
00206             std::max(getAlignment(Replacements[i].first),
00207                      getAlignment(Replacements[i].second)));
00208       }
00209 
00210       // Eliminate any uses of the dead global.
00211       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
00212 
00213       // Delete the global value from the module.
00214       assert(Replacements[i].first->hasLocalLinkage() &&
00215              "Refusing to delete an externally visible global variable.");
00216       Replacements[i].first->eraseFromParent();
00217     }
00218 
00219     NumMerged += Replacements.size();
00220     Replacements.clear();
00221   }
00222 }