1 //===- ConstantMerge.cpp - Merge duplicate global constants -----------------=//
2 //
3 // This file defines the interface to a pass that merges duplicate global
4 // constants together into a single constant that is shared.  This is useful
5 // because some passes (ie TraceValues) insert a lot of string constants into
6 // the program, regardless of whether or not they duplicate an existing string.
7 //
8 // Algorithm: ConstantMerge is designed to build up a map of available constants
9 // and elminate duplicates when it is initialized.
10 //
11 // The DynamicConstantMerge method is a superset of the ConstantMerge algorithm
12 // that checks for each function to see if constants have been added to the
13 // constant pool since it was last run... if so, it processes them.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Transforms/ConstantMerge.h"
18 #include "llvm/GlobalVariable.h"
19 #include "llvm/Module.h"
20 #include "llvm/Function.h"
21 #include "llvm/Pass.h"
22 #include "Support/StatisticReporter.h"
23 
24 static Statistic<> NumMerged("constmerge\t\t- Number of global constants merged");
25 
26 // mergeDuplicateConstants - Workhorse for the pass.  This eliminates duplicate
27 // constants, starting at global ConstantNo, and adds vars to the map if they
28 // are new and unique.
29 //
30 static inline
31 bool mergeDuplicateConstants(Module *M, unsigned &ConstantNo,
32                              std::map<Constant*, GlobalVariable*> &CMap) {
33   Module::GlobalListType &GList = M->getGlobalList();
34   if (GList.size() <= ConstantNo) return false;   // No new constants
35   bool MadeChanges = false;
36 
37   for (; ConstantNo < GList.size(); ++ConstantNo) {
38     GlobalVariable *GV = GList[ConstantNo];
39     if (GV->isConstant()) {  // Only process constants
40       assert(GV->hasInitializer() && "Globals constants must have inits!");
41       Constant *Init = GV->getInitializer();
42 
43       // Check to see if the initializer is already known...
44       std::map<Constant*, GlobalVariable*>::iterator I = CMap.find(Init);
45 
46       if (I == CMap.end()) {    // Nope, add it to the map
47         CMap.insert(std::make_pair(Init, GV));
48       } else {                  // Yup, this is a duplicate!
49         // Make all uses of the duplicate constant use the cannonical version...
50         GV->replaceAllUsesWith(I->second);
51 
52         // Remove and delete the global value from the module...
53         delete GList.remove(GList.begin()+ConstantNo);
54 
55         --ConstantNo;  // Don't skip the next constant.
56         ++NumMerged;
57         MadeChanges = true;
58       }
59     }
60   }
61   return MadeChanges;
62 }
63 
64 namespace {
65   // FIXME: ConstantMerge should not be a FunctionPass!!!
66   class ConstantMerge : public FunctionPass {
67   protected:
68     std::map<Constant*, GlobalVariable*> Constants;
69     unsigned LastConstantSeen;
70   public:
71     inline ConstantMerge() : LastConstantSeen(0) {}
72 
73     const char *getPassName() const {return "Merge Duplicate Global Constants";}
74 
75     // doInitialization - For this pass, process all of the globals in the
76     // module, eliminating duplicate constants.
77     //
78     bool doInitialization(Module *M) {
79       return ::mergeDuplicateConstants(M, LastConstantSeen, Constants);
80     }
81 
82     bool runOnFunction(Function *) { return false; }
83 
84     // doFinalization - Clean up internal state for this module
85     //
86     bool doFinalization(Module *M) {
87       LastConstantSeen = 0;
88       Constants.clear();
89       return false;
90     }
91 
92     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
93       AU.setPreservesAll();
94     }
95   };
96 
97   struct DynamicConstantMerge : public ConstantMerge {
98     const char *getPassName() const { return "Dynamic Constant Merge"; }
99 
100     // runOnFunction - Check to see if any globals have been added to the
101     // global list for the module.  If so, eliminate them.
102     //
103     bool runOnFunction(Function *F) {
104       return ::mergeDuplicateConstants(F->getParent(), LastConstantSeen,
105                                        Constants);
106     }
107   };
108 }
109 
110 Pass *createConstantMergePass() { return new ConstantMerge(); }
111 Pass *createDynamicConstantMergePass() { return new DynamicConstantMerge(); }
112