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 #include "llvm/Transforms/IPO/ConstantMerge.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DataLayout.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/LLVMContext.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/Pass.h"
33 #include "llvm/Support/Casting.h"
34 #include "llvm/Transforms/IPO.h"
35 #include <algorithm>
36 #include <cassert>
37 #include <utility>
38 
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "constmerge"
42 
43 STATISTIC(NumMerged, "Number of global constants merged");
44 
45 /// Find values that are marked as llvm.used.
46 static void FindUsedValues(GlobalVariable *LLVMUsed,
47                            SmallPtrSetImpl<const GlobalValue*> &UsedValues) {
48   if (!LLVMUsed) return;
49   ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
50 
51   for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) {
52     Value *Operand = Inits->getOperand(i)->stripPointerCastsNoFollowAliases();
53     GlobalValue *GV = cast<GlobalValue>(Operand);
54     UsedValues.insert(GV);
55   }
56 }
57 
58 // True if A is better than B.
59 static bool IsBetterCanonical(const GlobalVariable &A,
60                               const GlobalVariable &B) {
61   if (!A.hasLocalLinkage() && B.hasLocalLinkage())
62     return true;
63 
64   if (A.hasLocalLinkage() && !B.hasLocalLinkage())
65     return false;
66 
67   return A.hasGlobalUnnamedAddr();
68 }
69 
70 static bool hasMetadataOtherThanDebugLoc(const GlobalVariable *GV) {
71   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
72   GV->getAllMetadata(MDs);
73   for (const auto &V : MDs)
74     if (V.first != LLVMContext::MD_dbg)
75       return true;
76   return false;
77 }
78 
79 static void copyDebugLocMetadata(const GlobalVariable *From,
80                                  GlobalVariable *To) {
81   SmallVector<DIGlobalVariableExpression *, 1> MDs;
82   From->getDebugInfo(MDs);
83   for (auto MD : MDs)
84     To->addDebugInfo(MD);
85 }
86 
87 static unsigned getAlignment(GlobalVariable *GV) {
88   unsigned Align = GV->getAlignment();
89   if (Align)
90     return Align;
91   return GV->getParent()->getDataLayout().getPreferredAlignment(GV);
92 }
93 
94 static bool mergeConstants(Module &M) {
95   // Find all the globals that are marked "used".  These cannot be merged.
96   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
97   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
98   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
99 
100   // Map unique constants to globals.
101   DenseMap<Constant *, GlobalVariable *> CMap;
102 
103   // Replacements - This vector contains a list of replacements to perform.
104   SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
105 
106   bool MadeChange = false;
107 
108   // Iterate constant merging while we are still making progress.  Merging two
109   // constants together may allow us to merge other constants together if the
110   // second level constants have initializers which point to the globals that
111   // were just merged.
112   while (true) {
113     // First: Find the canonical constants others will be merged with.
114     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
115          GVI != E; ) {
116       GlobalVariable *GV = &*GVI++;
117 
118       // If this GV is dead, remove it.
119       GV->removeDeadConstantUsers();
120       if (GV->use_empty() && GV->hasLocalLinkage()) {
121         GV->eraseFromParent();
122         continue;
123       }
124 
125       // Only process constants with initializers in the default address space.
126       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
127           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
128           // Don't touch values marked with attribute(used).
129           UsedGlobals.count(GV))
130         continue;
131 
132       // This transformation is legal for weak ODR globals in the sense it
133       // doesn't change semantics, but we really don't want to perform it
134       // anyway; it's likely to pessimize code generation, and some tools
135       // (like the Darwin linker in cases involving CFString) don't expect it.
136       if (GV->isWeakForLinker())
137         continue;
138 
139       // Don't touch globals with metadata other then !dbg.
140       if (hasMetadataOtherThanDebugLoc(GV))
141         continue;
142 
143       Constant *Init = GV->getInitializer();
144 
145       // Check to see if the initializer is already known.
146       GlobalVariable *&Slot = CMap[Init];
147 
148       // If this is the first constant we find or if the old one is local,
149       // replace with the current one. If the current is externally visible
150       // it cannot be replace, but can be the canonical constant we merge with.
151       if (!Slot || IsBetterCanonical(*GV, *Slot))
152         Slot = GV;
153     }
154 
155     // Second: identify all globals that can be merged together, filling in
156     // the Replacements vector.  We cannot do the replacement in this pass
157     // because doing so may cause initializers of other globals to be rewritten,
158     // invalidating the Constant* pointers in CMap.
159     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
160          GVI != E; ) {
161       GlobalVariable *GV = &*GVI++;
162 
163       // Only process constants with initializers in the default address space.
164       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
165           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
166           // Don't touch values marked with attribute(used).
167           UsedGlobals.count(GV))
168         continue;
169 
170       // We can only replace constant with local linkage.
171       if (!GV->hasLocalLinkage())
172         continue;
173 
174       Constant *Init = GV->getInitializer();
175 
176       // Check to see if the initializer is already known.
177       GlobalVariable *Slot = CMap[Init];
178 
179       if (!Slot || Slot == GV)
180         continue;
181 
182       if (!Slot->hasGlobalUnnamedAddr() && !GV->hasGlobalUnnamedAddr())
183         continue;
184 
185       if (hasMetadataOtherThanDebugLoc(GV))
186         continue;
187 
188       if (!GV->hasGlobalUnnamedAddr())
189         Slot->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
190 
191       // Make all uses of the duplicate constant use the canonical version.
192       Replacements.push_back(std::make_pair(GV, Slot));
193     }
194 
195     if (Replacements.empty())
196       return MadeChange;
197     CMap.clear();
198 
199     // Now that we have figured out which replacements must be made, do them all
200     // now.  This avoid invalidating the pointers in CMap, which are unneeded
201     // now.
202     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
203       // Bump the alignment if necessary.
204       if (Replacements[i].first->getAlignment() ||
205           Replacements[i].second->getAlignment()) {
206         Replacements[i].second->setAlignment(
207             std::max(getAlignment(Replacements[i].first),
208                      getAlignment(Replacements[i].second)));
209       }
210 
211       copyDebugLocMetadata(Replacements[i].first, Replacements[i].second);
212 
213       // Eliminate any uses of the dead global.
214       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
215 
216       // Delete the global value from the module.
217       assert(Replacements[i].first->hasLocalLinkage() &&
218              "Refusing to delete an externally visible global variable.");
219       Replacements[i].first->eraseFromParent();
220     }
221 
222     NumMerged += Replacements.size();
223     Replacements.clear();
224   }
225 }
226 
227 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
228   if (!mergeConstants(M))
229     return PreservedAnalyses::all();
230   return PreservedAnalyses::none();
231 }
232 
233 namespace {
234 
235 struct ConstantMergeLegacyPass : public ModulePass {
236   static char ID; // Pass identification, replacement for typeid
237 
238   ConstantMergeLegacyPass() : ModulePass(ID) {
239     initializeConstantMergeLegacyPassPass(*PassRegistry::getPassRegistry());
240   }
241 
242   // For this pass, process all of the globals in the module, eliminating
243   // duplicate constants.
244   bool runOnModule(Module &M) override {
245     if (skipModule(M))
246       return false;
247     return mergeConstants(M);
248   }
249 };
250 
251 } // end anonymous namespace
252 
253 char ConstantMergeLegacyPass::ID = 0;
254 
255 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
256                 "Merge Duplicate Global Constants", false, false)
257 
258 ModulePass *llvm::createConstantMergePass() {
259   return new ConstantMergeLegacyPass();
260 }
261