1 //===- ConstantMerge.cpp - Merge duplicate global constants -----------------=//
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 an existing string is available.
8 // Algorithm: ConstantMerge is designed to build up a map of available constants
9 // and eliminate duplicates when it is initialized.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Transforms/IPO.h"
14 #include "llvm/Module.h"
15 #include "llvm/Constants.h"
16 #include "llvm/Pass.h"
17 #include "Support/StatisticReporter.h"
20 struct ConstantMerge : public Pass {
21 // run - For this pass, process all of the globals in the module,
22 // eliminating duplicate constants.
27 void replaceUsesOfWith(GlobalVariable *Old, GlobalVariable *New);
28 void replaceConstantWith(Constant *Old, Constant *New);
31 Statistic<> NumMerged("constmerge\t\t- Number of global constants merged");
32 RegisterOpt<ConstantMerge> X("constmerge","Merge Duplicate Global Constants");
35 Pass *createConstantMergePass() { return new ConstantMerge(); }
38 bool ConstantMerge::run(Module &M) {
39 std::map<Constant*, GlobalVariable*> CMap;
40 bool MadeChanges = false;
42 for (Module::giterator GV = M.gbegin(), E = M.gend(); GV != E; ++GV)
43 if (GV->isConstant()) { // Only process constants
44 assert(GV->hasInitializer() && "Globals constants must have inits!");
45 Constant *Init = GV->getInitializer();
47 // Check to see if the initializer is already known...
48 std::map<Constant*, GlobalVariable*>::iterator I = CMap.find(Init);
50 if (I == CMap.end()) { // Nope, add it to the map
51 CMap.insert(I, std::make_pair(Init, GV));
52 } else { // Yup, this is a duplicate!
53 // Make all uses of the duplicate constant use the cannonical version...
54 replaceUsesOfWith(GV, I->second);
56 // Delete the global value from the module... and back up iterator to
57 // not skip the next global...
58 GV = --M.getGlobalList().erase(GV);
68 /// replaceUsesOfWith - Replace all uses of Old with New. For instructions,
69 /// this is a really simple matter of replacing the reference to Old with a
70 /// reference to New. For constants references, however, we must carefully
71 /// build replacement constants to substitute in.
73 void ConstantMerge::replaceUsesOfWith(GlobalVariable *Old, GlobalVariable *New){
74 while (!Old->use_empty()) {
75 User *U = Old->use_back();
76 if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(U))
77 replaceConstantWith(CPR, ConstantPointerRef::get(New));
79 U->replaceUsesOfWith(Old, New);
83 /// replaceWith - Ok, so we have a constant 'Old' and we want to replace it with
84 /// 'New'. To do this, we have to recursively go through the uses of Old,
85 /// replacing them with new things. The problem is that if a constant uses Old,
86 /// then we need to replace the uses of the constant with uses of the equivalent
87 /// constant that uses New instead.
89 void ConstantMerge::replaceConstantWith(Constant *Old, Constant *New) {
90 while (!Old->use_empty()) {
91 User *U = Old->use_back();
93 if (Constant *C = dyn_cast<Constant>(U)) {
94 Constant *Replacement = 0;
96 // Depending on the type of constant, build a suitable replacement...
97 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
98 if (CE->getOpcode() == Instruction::GetElementPtr) {
99 std::vector<Constant*> Indices;
100 Constant *Pointer = cast<Constant>(CE->getOperand(0));
101 Indices.reserve(CE->getNumOperands()-1);
102 if (Pointer == Old) Pointer = New;
104 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) {
105 Constant *Val = cast<Constant>(CE->getOperand(i));
106 if (Val == Old) Val = New;
107 Indices.push_back(Val);
109 Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices);
110 } else if (CE->getOpcode() == Instruction::Cast) {
111 assert(CE->getOperand(0) == Old && "Cast only has one use!");
112 Replacement = ConstantExpr::getCast(New, CE->getType());
113 } else if (CE->getNumOperands() == 2) {
114 Constant *C1 = cast<Constant>(CE->getOperand(0));
115 Constant *C2 = cast<Constant>(CE->getOperand(1));
116 if (C1 == Old) C1 = New;
117 if (C2 == Old) C2 = New;
118 Replacement = ConstantExpr::get(CE->getOpcode(), C1, C2);
120 assert(0 && "Unknown ConstantExpr type!");
124 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
125 std::vector<Constant*> Values;
126 Values.reserve(CA->getValues().size());
127 for (unsigned i = 0, e = CA->getValues().size(); i != e; ++i) {
128 Constant *Val = cast<Constant>(CA->getValues()[i]);
129 if (Val == Old) Val = New;
130 Values.push_back(Val);
133 Replacement = ConstantArray::get(CA->getType(), Values);
134 } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
135 std::vector<Constant*> Values;
136 Values.reserve(CS->getValues().size());
138 for (unsigned i = 0, e = CS->getValues().size(); i != e; ++i) {
139 Constant *Val = cast<Constant>(CS->getValues()[i]);
140 if (Val == Old) Val = New;
141 Values.push_back(Val);
144 Replacement = ConstantStruct::get(CS->getType(), Values);
146 assert(0 && "Unexpected/unknown constant type!");
149 // Now that we have a suitable replacement, recursively eliminate C.
150 replaceConstantWith(C, Replacement);
153 // If it is not a constant, we can simply replace uses of Old with New.
154 U->replaceUsesOfWith(Old, New);
159 // No-one refers to this old dead constant now, destroy it!
160 Old->destroyConstant();