LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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   std::map<Constant*, GlobalVariable*> CMap;
00043 
00044   // Replacements - This vector contains a list of replacements to perform.
00045   std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements;
00046 
00047   bool MadeChange = false;
00048 
00049   // Iterate constant merging while we are still making progress.  Merging two
00050   // constants together may allow us to merge other constants together if the
00051   // second level constants have initializers which point to the globals that
00052   // were just merged.
00053   while (1) {
00054     // First pass: identify all globals that can be merged together, filling in
00055     // the Replacements vector.  We cannot do the replacement in this pass
00056     // because doing so may cause initializers of other globals to be rewritten,
00057     // invalidating the Constant* pointers in CMap.
00058     //
00059     for (Module::giterator GV = M.gbegin(), E = M.gend(); GV != E; ++GV)
00060       // Only process constants with initializers
00061       if (GV->isConstant() && GV->hasInitializer()) {
00062         Constant *Init = GV->getInitializer();
00063         
00064         // Check to see if the initializer is already known...
00065         std::map<Constant*, GlobalVariable*>::iterator I = CMap.find(Init);
00066         
00067         if (I == CMap.end()) {    // Nope, add it to the map
00068           CMap.insert(I, std::make_pair(Init, GV));
00069         } else if (GV->hasInternalLinkage()) {    // Yup, this is a duplicate!
00070           // Make all uses of the duplicate constant use the canonical version.
00071           Replacements.push_back(std::make_pair(GV, I->second));
00072         } else if (I->second->hasInternalLinkage()) {
00073           // Make all uses of the duplicate constant use the canonical version.
00074           Replacements.push_back(std::make_pair(I->second, GV));
00075           I->second = GV;
00076         }
00077       }
00078     
00079     if (Replacements.empty())
00080       return MadeChange;
00081     CMap.clear();
00082     
00083     // Now that we have figured out which replacements must be made, do them all
00084     // now.  This avoid invalidating the pointers in CMap, which are unneeded
00085     // now.
00086     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
00087       // Eliminate any uses of the dead global...
00088       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
00089       
00090       // Delete the global value from the module...
00091       M.getGlobalList().erase(Replacements[i].first);
00092     }
00093     
00094     NumMerged += Replacements.size();
00095     Replacements.clear();
00096   }
00097 }