1 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the interface to a pass that merges duplicate global
10 // constants together into a single constant that is shared.  This is useful
11 // because some passes (ie TraceValues) insert a lot of string constants into
12 // the program, regardless of whether or not an existing string is available.
13 //
14 // Algorithm: ConstantMerge is designed to build up a map of available constants
15 // and eliminate duplicates when it is initialized.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/Transforms/IPO/ConstantMerge.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/GlobalValue.h"
28 #include "llvm/IR/GlobalVariable.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/InitializePasses.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.
FindUsedValues(GlobalVariable * LLVMUsed,SmallPtrSetImpl<const GlobalValue * > & UsedValues)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)->stripPointerCasts();
53     GlobalValue *GV = cast<GlobalValue>(Operand);
54     UsedValues.insert(GV);
55   }
56 }
57 
58 // True if A is better than B.
IsBetterCanonical(const GlobalVariable & A,const GlobalVariable & 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 
hasMetadataOtherThanDebugLoc(const GlobalVariable * GV)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 
copyDebugLocMetadata(const GlobalVariable * From,GlobalVariable * To)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 
getAlign(GlobalVariable * GV)87 static Align getAlign(GlobalVariable *GV) {
88   return GV->getAlign().value_or(
89       GV->getParent()->getDataLayout().getPreferredAlign(GV));
90 }
91 
92 static bool
isUnmergeableGlobal(GlobalVariable * GV,const SmallPtrSetImpl<const GlobalValue * > & UsedGlobals)93 isUnmergeableGlobal(GlobalVariable *GV,
94                     const SmallPtrSetImpl<const GlobalValue *> &UsedGlobals) {
95   // Only process constants with initializers in the default address space.
96   return !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
97          GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
98          // Don't touch thread-local variables.
99          GV->isThreadLocal() ||
100          // Don't touch values marked with attribute(used).
101          UsedGlobals.count(GV);
102 }
103 
104 enum class CanMerge { No, Yes };
makeMergeable(GlobalVariable * Old,GlobalVariable * New)105 static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New) {
106   if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
107     return CanMerge::No;
108   if (hasMetadataOtherThanDebugLoc(Old))
109     return CanMerge::No;
110   assert(!hasMetadataOtherThanDebugLoc(New));
111   if (!Old->hasGlobalUnnamedAddr())
112     New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
113   return CanMerge::Yes;
114 }
115 
replace(Module & M,GlobalVariable * Old,GlobalVariable * New)116 static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
117   Constant *NewConstant = New;
118 
119   LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
120                     << New->getName() << "\n");
121 
122   // Bump the alignment if necessary.
123   if (Old->getAlign() || New->getAlign())
124     New->setAlignment(std::max(getAlign(Old), getAlign(New)));
125 
126   copyDebugLocMetadata(Old, New);
127   Old->replaceAllUsesWith(NewConstant);
128 
129   // Delete the global value from the module.
130   assert(Old->hasLocalLinkage() &&
131          "Refusing to delete an externally visible global variable.");
132   Old->eraseFromParent();
133 }
134 
mergeConstants(Module & M)135 static bool mergeConstants(Module &M) {
136   // Find all the globals that are marked "used".  These cannot be merged.
137   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
138   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
139   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
140 
141   // Map unique constants to globals.
142   DenseMap<Constant *, GlobalVariable *> CMap;
143 
144   SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32>
145       SameContentReplacements;
146 
147   size_t ChangesMade = 0;
148   size_t OldChangesMade = 0;
149 
150   // Iterate constant merging while we are still making progress.  Merging two
151   // constants together may allow us to merge other constants together if the
152   // second level constants have initializers which point to the globals that
153   // were just merged.
154   while (true) {
155     // Find the canonical constants others will be merged with.
156     for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
157       // If this GV is dead, remove it.
158       GV.removeDeadConstantUsers();
159       if (GV.use_empty() && GV.hasLocalLinkage()) {
160         GV.eraseFromParent();
161         ++ChangesMade;
162         continue;
163       }
164 
165       if (isUnmergeableGlobal(&GV, UsedGlobals))
166         continue;
167 
168       // This transformation is legal for weak ODR globals in the sense it
169       // doesn't change semantics, but we really don't want to perform it
170       // anyway; it's likely to pessimize code generation, and some tools
171       // (like the Darwin linker in cases involving CFString) don't expect it.
172       if (GV.isWeakForLinker())
173         continue;
174 
175       // Don't touch globals with metadata other then !dbg.
176       if (hasMetadataOtherThanDebugLoc(&GV))
177         continue;
178 
179       Constant *Init = GV.getInitializer();
180 
181       // Check to see if the initializer is already known.
182       GlobalVariable *&Slot = CMap[Init];
183 
184       // If this is the first constant we find or if the old one is local,
185       // replace with the current one. If the current is externally visible
186       // it cannot be replace, but can be the canonical constant we merge with.
187       bool FirstConstantFound = !Slot;
188       if (FirstConstantFound || IsBetterCanonical(GV, *Slot)) {
189         Slot = &GV;
190         LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV.getName()
191                           << (FirstConstantFound ? "\n" : " (updated)\n"));
192       }
193     }
194 
195     // Identify all globals that can be merged together, filling in the
196     // SameContentReplacements vector. We cannot do the replacement in this pass
197     // because doing so may cause initializers of other globals to be rewritten,
198     // invalidating the Constant* pointers in CMap.
199     for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
200       if (isUnmergeableGlobal(&GV, UsedGlobals))
201         continue;
202 
203       // We can only replace constant with local linkage.
204       if (!GV.hasLocalLinkage())
205         continue;
206 
207       Constant *Init = GV.getInitializer();
208 
209       // Check to see if the initializer is already known.
210       auto Found = CMap.find(Init);
211       if (Found == CMap.end())
212         continue;
213 
214       GlobalVariable *Slot = Found->second;
215       if (Slot == &GV)
216         continue;
217 
218       if (makeMergeable(&GV, Slot) == CanMerge::No)
219         continue;
220 
221       // Make all uses of the duplicate constant use the canonical version.
222       LLVM_DEBUG(dbgs() << "Will replace: @" << GV.getName() << " -> @"
223                         << Slot->getName() << "\n");
224       SameContentReplacements.push_back(std::make_pair(&GV, Slot));
225     }
226 
227     // Now that we have figured out which replacements must be made, do them all
228     // now.  This avoid invalidating the pointers in CMap, which are unneeded
229     // now.
230     for (unsigned i = 0, e = SameContentReplacements.size(); i != e; ++i) {
231       GlobalVariable *Old = SameContentReplacements[i].first;
232       GlobalVariable *New = SameContentReplacements[i].second;
233       replace(M, Old, New);
234       ++ChangesMade;
235       ++NumIdenticalMerged;
236     }
237 
238     if (ChangesMade == OldChangesMade)
239       break;
240     OldChangesMade = ChangesMade;
241 
242     SameContentReplacements.clear();
243     CMap.clear();
244   }
245 
246   return ChangesMade;
247 }
248 
run(Module & M,ModuleAnalysisManager &)249 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
250   if (!mergeConstants(M))
251     return PreservedAnalyses::all();
252   return PreservedAnalyses::none();
253 }
254 
255 namespace {
256 
257 struct ConstantMergeLegacyPass : public ModulePass {
258   static char ID; // Pass identification, replacement for typeid
259 
ConstantMergeLegacyPass__anonc67db78c0111::ConstantMergeLegacyPass260   ConstantMergeLegacyPass() : ModulePass(ID) {
261     initializeConstantMergeLegacyPassPass(*PassRegistry::getPassRegistry());
262   }
263 
264   // For this pass, process all of the globals in the module, eliminating
265   // duplicate constants.
runOnModule__anonc67db78c0111::ConstantMergeLegacyPass266   bool runOnModule(Module &M) override {
267     if (skipModule(M))
268       return false;
269     return mergeConstants(M);
270   }
271 };
272 
273 } // end anonymous namespace
274 
275 char ConstantMergeLegacyPass::ID = 0;
276 
277 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
278                 "Merge Duplicate Global Constants", false, false)
279 
createConstantMergePass()280 ModulePass *llvm::createConstantMergePass() {
281   return new ConstantMergeLegacyPass();
282 }
283