1 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the interface to a pass that merges duplicate global
11 // constants together into a single constant that is shared. This is useful
12 // because some passes (ie TraceValues) insert a lot of string constants into
13 // the program, regardless of whether or not an existing string is available.
14 //
15 // Algorithm: ConstantMerge is designed to build up a map of available constants
16 // and eliminate duplicates when it is initialized.
17 //
18 //===----------------------------------------------------------------------===//
19
20 #define DEBUG_TYPE "constmerge"
21 #include "llvm/Transforms/IPO.h"
22 #include "llvm/Constants.h"
23 #include "llvm/DerivedTypes.h"
24 #include "llvm/Module.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Target/TargetData.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/PointerIntPair.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/Statistic.h"
31 using namespace llvm;
32
33 STATISTIC(NumMerged, "Number of global constants merged");
34
35 namespace {
36 struct ConstantMerge : public ModulePass {
37 static char ID; // Pass identification, replacement for typeid
ConstantMerge__anon030345270111::ConstantMerge38 ConstantMerge() : ModulePass(ID) {
39 initializeConstantMergePass(*PassRegistry::getPassRegistry());
40 }
41
42 // For this pass, process all of the globals in the module, eliminating
43 // duplicate constants.
44 bool runOnModule(Module &M);
45
46 // Return true iff we can determine the alignment of this global variable.
47 bool hasKnownAlignment(GlobalVariable *GV) const;
48
49 // Return the alignment of the global, including converting the default
50 // alignment to a concrete value.
51 unsigned getAlignment(GlobalVariable *GV) const;
52
53 const TargetData *TD;
54 };
55 }
56
57 char ConstantMerge::ID = 0;
58 INITIALIZE_PASS(ConstantMerge, "constmerge",
59 "Merge Duplicate Global Constants", false, false)
60
createConstantMergePass()61 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
62
63
64
65 /// Find values that are marked as llvm.used.
FindUsedValues(GlobalVariable * LLVMUsed,SmallPtrSet<const GlobalValue *,8> & UsedValues)66 static void FindUsedValues(GlobalVariable *LLVMUsed,
67 SmallPtrSet<const GlobalValue*, 8> &UsedValues) {
68 if (LLVMUsed == 0) return;
69 ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer());
70 if (Inits == 0) return;
71
72 for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i)
73 if (GlobalValue *GV =
74 dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts()))
75 UsedValues.insert(GV);
76 }
77
78 // True if A is better than B.
IsBetterCannonical(const GlobalVariable & A,const GlobalVariable & B)79 static bool IsBetterCannonical(const GlobalVariable &A,
80 const GlobalVariable &B) {
81 if (!A.hasLocalLinkage() && B.hasLocalLinkage())
82 return true;
83
84 if (A.hasLocalLinkage() && !B.hasLocalLinkage())
85 return false;
86
87 return A.hasUnnamedAddr();
88 }
89
hasKnownAlignment(GlobalVariable * GV) const90 bool ConstantMerge::hasKnownAlignment(GlobalVariable *GV) const {
91 return TD || GV->getAlignment() != 0;
92 }
93
getAlignment(GlobalVariable * GV) const94 unsigned ConstantMerge::getAlignment(GlobalVariable *GV) const {
95 if (TD)
96 return TD->getPreferredAlignment(GV);
97 return GV->getAlignment();
98 }
99
runOnModule(Module & M)100 bool ConstantMerge::runOnModule(Module &M) {
101 TD = getAnalysisIfAvailable<TargetData>();
102
103 // Find all the globals that are marked "used". These cannot be merged.
104 SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
105 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
106 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
107
108 // Map unique <constants, has-unknown-alignment> pairs to globals. We don't
109 // want to merge globals of unknown alignment with those of explicit
110 // alignment. If we have TargetData, we always know the alignment.
111 DenseMap<PointerIntPair<Constant*, 1, bool>, GlobalVariable*> CMap;
112
113 // Replacements - This vector contains a list of replacements to perform.
114 SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
115
116 bool MadeChange = false;
117
118 // Iterate constant merging while we are still making progress. Merging two
119 // constants together may allow us to merge other constants together if the
120 // second level constants have initializers which point to the globals that
121 // were just merged.
122 while (1) {
123
124 // First: Find the canonical constants others will be merged with.
125 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
126 GVI != E; ) {
127 GlobalVariable *GV = GVI++;
128
129 // If this GV is dead, remove it.
130 GV->removeDeadConstantUsers();
131 if (GV->use_empty() && GV->hasLocalLinkage()) {
132 GV->eraseFromParent();
133 continue;
134 }
135
136 // Only process constants with initializers in the default address space.
137 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
138 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
139 // Don't touch values marked with attribute(used).
140 UsedGlobals.count(GV))
141 continue;
142
143 // This transformation is legal for weak ODR globals in the sense it
144 // doesn't change semantics, but we really don't want to perform it
145 // anyway; it's likely to pessimize code generation, and some tools
146 // (like the Darwin linker in cases involving CFString) don't expect it.
147 if (GV->isWeakForLinker())
148 continue;
149
150 Constant *Init = GV->getInitializer();
151
152 // Check to see if the initializer is already known.
153 PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
154 GlobalVariable *&Slot = CMap[Pair];
155
156 // If this is the first constant we find or if the old one is local,
157 // replace with the current one. If the current is externally visible
158 // it cannot be replace, but can be the canonical constant we merge with.
159 if (Slot == 0 || IsBetterCannonical(*GV, *Slot))
160 Slot = GV;
161 }
162
163 // Second: identify all globals that can be merged together, filling in
164 // the Replacements vector. We cannot do the replacement in this pass
165 // because doing so may cause initializers of other globals to be rewritten,
166 // invalidating the Constant* pointers in CMap.
167 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
168 GVI != E; ) {
169 GlobalVariable *GV = GVI++;
170
171 // Only process constants with initializers in the default address space.
172 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
173 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
174 // Don't touch values marked with attribute(used).
175 UsedGlobals.count(GV))
176 continue;
177
178 // We can only replace constant with local linkage.
179 if (!GV->hasLocalLinkage())
180 continue;
181
182 Constant *Init = GV->getInitializer();
183
184 // Check to see if the initializer is already known.
185 PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
186 GlobalVariable *Slot = CMap[Pair];
187
188 if (!Slot || Slot == GV)
189 continue;
190
191 if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr())
192 continue;
193
194 if (!GV->hasUnnamedAddr())
195 Slot->setUnnamedAddr(false);
196
197 // Make all uses of the duplicate constant use the canonical version.
198 Replacements.push_back(std::make_pair(GV, Slot));
199 }
200
201 if (Replacements.empty())
202 return MadeChange;
203 CMap.clear();
204
205 // Now that we have figured out which replacements must be made, do them all
206 // now. This avoid invalidating the pointers in CMap, which are unneeded
207 // now.
208 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
209 // Bump the alignment if necessary.
210 if (Replacements[i].first->getAlignment() ||
211 Replacements[i].second->getAlignment()) {
212 Replacements[i].second->setAlignment(std::max(
213 Replacements[i].first->getAlignment(),
214 Replacements[i].second->getAlignment()));
215 }
216
217 // Eliminate any uses of the dead global.
218 Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
219
220 // Delete the global value from the module.
221 assert(Replacements[i].first->hasLocalLinkage() &&
222 "Refusing to delete an externally visible global variable.");
223 Replacements[i].first->eraseFromParent();
224 }
225
226 NumMerged += Replacements.size();
227 Replacements.clear();
228 }
229 }
230