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 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   // Replacements - This vector contains a list of replacements to perform.
135   SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
136 
137   bool MadeChange = false;
138 
139   // Iterate constant merging while we are still making progress.  Merging two
140   // constants together may allow us to merge other constants together if the
141   // second level constants have initializers which point to the globals that
142   // were just merged.
143   while (true) {
144     // First: Find the canonical constants others will be merged with.
145     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
146          GVI != E; ) {
147       GlobalVariable *GV = &*GVI++;
148 
149       // If this GV is dead, remove it.
150       GV->removeDeadConstantUsers();
151       if (GV->use_empty() && GV->hasLocalLinkage()) {
152         GV->eraseFromParent();
153         continue;
154       }
155 
156       // Only process constants with initializers in the default address space.
157       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
158           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
159           // Don't touch values marked with attribute(used).
160           UsedGlobals.count(GV))
161         continue;
162 
163       // This transformation is legal for weak ODR globals in the sense it
164       // doesn't change semantics, but we really don't want to perform it
165       // anyway; it's likely to pessimize code generation, and some tools
166       // (like the Darwin linker in cases involving CFString) don't expect it.
167       if (GV->isWeakForLinker())
168         continue;
169 
170       // Don't touch globals with metadata other then !dbg.
171       if (hasMetadataOtherThanDebugLoc(GV))
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 this is the first constant we find or if the old one is local,
180       // replace with the current one. If the current is externally visible
181       // it cannot be replace, but can be the canonical constant we merge with.
182       bool FirstConstantFound = !Slot;
183       if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) {
184         Slot = GV;
185         LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
186                           << (FirstConstantFound ? "\n" : " (updated)\n"));
187       }
188     }
189 
190     // Second: identify all globals that can be merged together, filling in
191     // the Replacements vector.  We cannot do the replacement in this pass
192     // because doing so may cause initializers of other globals to be rewritten,
193     // invalidating the Constant* pointers in CMap.
194     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
195          GVI != E; ) {
196       GlobalVariable *GV = &*GVI++;
197 
198       // Only process constants with initializers in the default address space.
199       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
200           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
201           // Don't touch values marked with attribute(used).
202           UsedGlobals.count(GV))
203         continue;
204 
205       // We can only replace constant with local linkage.
206       if (!GV->hasLocalLinkage())
207         continue;
208 
209       Constant *Init = GV->getInitializer();
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       Replacements.push_back(std::make_pair(GV, Slot));
227     }
228 
229     if (Replacements.empty())
230       return MadeChange;
231     CMap.clear();
232 
233     // Now that we have figured out which replacements must be made, do them all
234     // now.  This avoid invalidating the pointers in CMap, which are unneeded
235     // now.
236     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
237       GlobalVariable *Old = Replacements[i].first;
238       GlobalVariable *New = Replacements[i].second;
239       replace(M, Old, New);
240       MadeChange = true;
241     }
242 
243     NumMerged += Replacements.size();
244     Replacements.clear();
245   }
246 }
247 
248 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
249   if (!mergeConstants(M))
250     return PreservedAnalyses::all();
251   return PreservedAnalyses::none();
252 }
253 
254 namespace {
255 
256 struct ConstantMergeLegacyPass : public ModulePass {
257   static char ID; // Pass identification, replacement for typeid
258 
259   ConstantMergeLegacyPass() : ModulePass(ID) {
260     initializeConstantMergeLegacyPassPass(*PassRegistry::getPassRegistry());
261   }
262 
263   // For this pass, process all of the globals in the module, eliminating
264   // duplicate constants.
265   bool runOnModule(Module &M) override {
266     if (skipModule(M))
267       return false;
268     return mergeConstants(M);
269   }
270 };
271 
272 } // end anonymous namespace
273 
274 char ConstantMergeLegacyPass::ID = 0;
275 
276 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
277                 "Merge Duplicate Global Constants", false, false)
278 
279 ModulePass *llvm::createConstantMergePass() {
280   return new ConstantMergeLegacyPass();
281 }
282