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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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/Module.h"
00022 #include "llvm/Pass.h"
00023 #include "llvm/ADT/Statistic.h"
00024 using namespace llvm;
00025 
00026 namespace {
00027   Statistic<> NumMerged("constmerge", "Number of global constants merged");
00028 
00029   struct ConstantMerge : public ModulePass {
00030     // run - For this pass, process all of the globals in the module,
00031     // eliminating duplicate constants.
00032     //
00033     bool runOnModule(Module &M);
00034   };
00035 
00036   RegisterOpt<ConstantMerge> X("constmerge","Merge Duplicate Global Constants");
00037 }
00038 
00039 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
00040 
00041 bool ConstantMerge::runOnModule(Module &M) {
00042   // Map unique constant/section pairs to globals.  We don't want to merge
00043   // globals in different sections.
00044   std::map<std::pair<Constant*, std::string>, GlobalVariable*> CMap;
00045 
00046   // Replacements - This vector contains a list of replacements to perform.
00047   std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements;
00048 
00049   bool MadeChange = false;
00050 
00051   // Iterate constant merging while we are still making progress.  Merging two
00052   // constants together may allow us to merge other constants together if the
00053   // second level constants have initializers which point to the globals that
00054   // were just merged.
00055   while (1) {
00056     // First pass: identify all globals that can be merged together, filling in
00057     // the Replacements vector.  We cannot do the replacement in this pass
00058     // because doing so may cause initializers of other globals to be rewritten,
00059     // invalidating the Constant* pointers in CMap.
00060     //
00061     for (Module::global_iterator GV = M.global_begin(), E = M.global_end();
00062          GV != E; ++GV)
00063       // Only process constants with initializers.
00064       if (GV->isConstant() && GV->hasInitializer()) {
00065         Constant *Init = GV->getInitializer();
00066 
00067         // Check to see if the initializer is already known.
00068         GlobalVariable *&Slot = CMap[std::make_pair(Init, GV->getSection())];
00069 
00070         if (Slot == 0) {    // Nope, add it to the map.
00071           Slot = GV;
00072         } else if (GV->hasInternalLinkage()) {    // Yup, this is a duplicate!
00073           // Make all uses of the duplicate constant use the canonical version.
00074           Replacements.push_back(std::make_pair(GV, Slot));
00075         } else if (GV->hasInternalLinkage()) {
00076           // Make all uses of the duplicate constant use the canonical version.
00077           Replacements.push_back(std::make_pair(Slot, GV));
00078           Slot = GV;
00079         }
00080       }
00081 
00082     if (Replacements.empty())
00083       return MadeChange;
00084     CMap.clear();
00085 
00086     // Now that we have figured out which replacements must be made, do them all
00087     // now.  This avoid invalidating the pointers in CMap, which are unneeded
00088     // now.
00089     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
00090       // Eliminate any uses of the dead global...
00091       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
00092 
00093       // Delete the global value from the module...
00094       M.getGlobalList().erase(Replacements[i].first);
00095     }
00096 
00097     NumMerged += Replacements.size();
00098     Replacements.clear();
00099   }
00100 }