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(NumIdenticalMerged, "Number of identical 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 enum class CanMerge { No, Yes };
95 static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New) {
96   if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
97     return CanMerge::No;
98   if (hasMetadataOtherThanDebugLoc(Old))
99     return CanMerge::No;
100   assert(!hasMetadataOtherThanDebugLoc(New));
101   if (!Old->hasGlobalUnnamedAddr())
102     New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
103   return CanMerge::Yes;
104 }
105 
106 static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
107   Constant *NewConstant = New;
108 
109   LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
110                     << New->getName() << "\n");
111 
112   // Bump the alignment if necessary.
113   if (Old->getAlignment() || New->getAlignment())
114     New->setAlignment(std::max(getAlignment(Old), getAlignment(New)));
115 
116   copyDebugLocMetadata(Old, New);
117   Old->replaceAllUsesWith(NewConstant);
118 
119   // Delete the global value from the module.
120   assert(Old->hasLocalLinkage() &&
121          "Refusing to delete an externally visible global variable.");
122   Old->eraseFromParent();
123 }
124 
125 static bool mergeConstants(Module &M) {
126   // Find all the globals that are marked "used".  These cannot be merged.
127   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
128   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
129   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
130 
131   // Map unique constants to globals.
132   DenseMap<Constant *, GlobalVariable *> CMap;
133 
134   SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32>
135       SameContentReplacements;
136 
137   size_t ChangesMade = 0;
138   size_t OldChangesMade = 0;
139 
140   // Iterate constant merging while we are still making progress.  Merging two
141   // constants together may allow us to merge other constants together if the
142   // second level constants have initializers which point to the globals that
143   // were just merged.
144   while (true) {
145     // Find the canonical constants others will be merged with.
146     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
147          GVI != E; ) {
148       GlobalVariable *GV = &*GVI++;
149       Constant *Init = GV->getInitializer();
150 
151       // If this GV is dead, remove it.
152       GV->removeDeadConstantUsers();
153       if (GV->use_empty() && GV->hasLocalLinkage()) {
154         GV->eraseFromParent();
155         ++ChangesMade;
156         continue;
157       }
158 
159       // Only process constants with initializers in the default address space.
160       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
161           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
162           // Don't touch values marked with attribute(used).
163           UsedGlobals.count(GV))
164         continue;
165 
166       // This transformation is legal for weak ODR globals in the sense it
167       // doesn't change semantics, but we really don't want to perform it
168       // anyway; it's likely to pessimize code generation, and some tools
169       // (like the Darwin linker in cases involving CFString) don't expect it.
170       if (GV->isWeakForLinker())
171         continue;
172 
173       // Don't touch globals with metadata other then !dbg.
174       if (hasMetadataOtherThanDebugLoc(GV))
175         continue;
176 
177       // Check to see if the initializer is already known.
178       GlobalVariable *&Slot = CMap[Init];
179 
180       // If this is the first constant we find or if the old one is local,
181       // replace with the current one. If the current is externally visible
182       // it cannot be replace, but can be the canonical constant we merge with.
183       bool FirstConstantFound = !Slot;
184       if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) {
185         Slot = GV;
186         LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
187                           << (FirstConstantFound ? "\n" : " (updated)\n"));
188       }
189     }
190 
191     // Identify all globals that can be merged together, filling in the
192     // SameContentReplacements vector. We cannot do the replacement in this pass
193     // because doing so may cause initializers of other globals to be rewritten,
194     // invalidating the Constant* pointers in CMap.
195     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
196          GVI != E; ) {
197       GlobalVariable *GV = &*GVI++;
198       Constant *Init = GV->getInitializer();
199 
200       // Only process constants with initializers in the default address space.
201       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
202           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
203           // Don't touch values marked with attribute(used).
204           UsedGlobals.count(GV))
205         continue;
206 
207       // We can only replace constant with local linkage.
208       if (!GV->hasLocalLinkage())
209         continue;
210 
211       // Check to see if the initializer is already known.
212       auto Found = CMap.find(Init);
213       if (Found == CMap.end())
214         continue;
215 
216       GlobalVariable *Slot = Found->second;
217       if (Slot == GV)
218         continue;
219 
220       if (makeMergeable(GV, Slot) == CanMerge::No)
221         continue;
222 
223       // Make all uses of the duplicate constant use the canonical version.
224       LLVM_DEBUG(dbgs() << "Will replace: @" << GV->getName() << " -> @"
225                         << Slot->getName() << "\n");
226       SameContentReplacements.push_back(std::make_pair(GV, Slot));
227     }
228 
229     // Now that we have figured out which replacements must be made, do them all
230     // now.  This avoid invalidating the pointers in CMap, which are unneeded
231     // now.
232     for (unsigned i = 0, e = SameContentReplacements.size(); i != e; ++i) {
233       GlobalVariable *Old = SameContentReplacements[i].first;
234       GlobalVariable *New = SameContentReplacements[i].second;
235       replace(M, Old, New);
236       ++ChangesMade;
237       ++NumIdenticalMerged;
238     }
239 
240     if (ChangesMade == OldChangesMade)
241       break;
242     OldChangesMade = ChangesMade;
243 
244     SameContentReplacements.clear();
245     CMap.clear();
246   }
247 
248   return ChangesMade;
249 }
250 
251 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
252   if (!mergeConstants(M))
253     return PreservedAnalyses::all();
254   return PreservedAnalyses::none();
255 }
256 
257 namespace {
258 
259 struct ConstantMergeLegacyPass : public ModulePass {
260   static char ID; // Pass identification, replacement for typeid
261 
262   ConstantMergeLegacyPass() : ModulePass(ID) {
263     initializeConstantMergeLegacyPassPass(*PassRegistry::getPassRegistry());
264   }
265 
266   // For this pass, process all of the globals in the module, eliminating
267   // duplicate constants.
268   bool runOnModule(Module &M) override {
269     if (skipModule(M))
270       return false;
271     return mergeConstants(M);
272   }
273 };
274 
275 } // end anonymous namespace
276 
277 char ConstantMergeLegacyPass::ID = 0;
278 
279 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
280                 "Merge Duplicate Global Constants", false, false)
281 
282 ModulePass *llvm::createConstantMergePass() {
283   return new ConstantMergeLegacyPass();
284 }
285