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/Support/Casting.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Transforms/IPO.h"
34#include <algorithm>
35#include <cassert>
36#include <utility>
37
38using namespace llvm;
39
40#define DEBUG_TYPE "constmerge"
41
42STATISTIC(NumIdenticalMerged, "Number of identical global constants merged");
43
44/// Find values that are marked as llvm.used.
45static void FindUsedValues(GlobalVariable *LLVMUsed,
46 SmallPtrSetImpl<const GlobalValue*> &UsedValues) {
47 if (!LLVMUsed) return;
48 ConstantArray *Inits = cast<ConstantArray>(Val: LLVMUsed->getInitializer());
49
50 for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) {
51 Value *Operand = Inits->getOperand(i_nocapture: i)->stripPointerCasts();
52 GlobalValue *GV = cast<GlobalValue>(Val: Operand);
53 UsedValues.insert(Ptr: GV);
54 }
55}
56
57// True if A is better than B.
58static bool IsBetterCanonical(const GlobalVariable &A,
59 const GlobalVariable &B) {
60 if (!A.hasLocalLinkage() && B.hasLocalLinkage())
61 return true;
62
63 if (A.hasLocalLinkage() && !B.hasLocalLinkage())
64 return false;
65
66 if (A.hasGlobalUnnamedAddr() != B.hasGlobalUnnamedAddr())
67 return A.hasGlobalUnnamedAddr();
68
69 return !A.hasComdat();
70}
71
72static void copyDebugLocMetadata(const GlobalVariable *From,
73 GlobalVariable *To) {
74 SmallVector<DIGlobalVariableExpression *, 1> MDs;
75 From->getDebugInfo(GVs&: MDs);
76 for (auto *MD : MDs)
77 To->addDebugInfo(GV: MD);
78}
79
80static Align getAlign(GlobalVariable *GV) {
81 return GV->getAlign().value_or(
82 u: GV->getDataLayout().getPreferredAlign(GV));
83}
84
85static bool
86isUnmergeableGlobal(GlobalVariable *GV,
87 const SmallPtrSetImpl<const GlobalValue *> &UsedGlobals) {
88 // Only process constants with initializers in the default address space.
89 return !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
90 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
91 // Don't touch thread-local variables.
92 GV->isThreadLocal() ||
93 // Don't touch values marked with attribute(used).
94 UsedGlobals.count(Ptr: GV);
95}
96
97enum class CanMerge { No, Yes };
98static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New) {
99 if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
100 return CanMerge::No;
101 if (Old->hasMetadataOtherThanDebugLoc())
102 return CanMerge::No;
103 assert(!New->hasMetadataOtherThanDebugLoc());
104
105 // Merging constants with different comdats means one group cannot in general
106 // be dropped independently without the other group now having an invalid
107 // reference to the dropped constant.
108 // If we merge into a constant that does not have comdat, we can merge even
109 // when the old constant has a comdat group because it has local linkage and
110 // is therefore not the comdat key.
111 if (Old->getComdat() != New->getComdat() && New->hasComdat())
112 return CanMerge::No;
113
114 if (!Old->hasGlobalUnnamedAddr())
115 New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
116 return CanMerge::Yes;
117}
118
119static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
120 Constant *NewConstant = New;
121
122 LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
123 << New->getName() << "\n");
124
125 // Bump the alignment if necessary.
126 if (Old->getAlign() || New->getAlign())
127 New->setAlignment(std::max(a: getAlign(GV: Old), b: getAlign(GV: New)));
128
129 copyDebugLocMetadata(From: Old, To: New);
130 Old->replaceAllUsesWith(V: NewConstant);
131
132 // Delete the global value from the module.
133 assert(Old->hasLocalLinkage() &&
134 "Refusing to delete an externally visible global variable.");
135 Old->eraseFromParent();
136}
137
138static bool mergeConstants(Module &M) {
139 // Find all the globals that are marked "used". These cannot be merged.
140 SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
141 FindUsedValues(LLVMUsed: M.getGlobalVariable(Name: "llvm.used"), UsedValues&: UsedGlobals);
142 FindUsedValues(LLVMUsed: M.getGlobalVariable(Name: "llvm.compiler.used"), UsedValues&: UsedGlobals);
143
144 // Map unique constants to globals.
145 DenseMap<Constant *, GlobalVariable *> CMap;
146
147 SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32>
148 SameContentReplacements;
149
150 size_t ChangesMade = 0;
151 size_t OldChangesMade = 0;
152
153 // Iterate constant merging while we are still making progress. Merging two
154 // constants together may allow us to merge other constants together if the
155 // second level constants have initializers which point to the globals that
156 // were just merged.
157 while (true) {
158 // Find the canonical constants others will be merged with.
159 for (GlobalVariable &GV : llvm::make_early_inc_range(Range: M.globals())) {
160 // If this GV is dead, remove it.
161 GV.removeDeadConstantUsers();
162 if (GV.use_empty() && GV.hasLocalLinkage()) {
163 GV.eraseFromParent();
164 ++ChangesMade;
165 continue;
166 }
167
168 if (isUnmergeableGlobal(GV: &GV, UsedGlobals))
169 continue;
170
171 // This transformation is legal for weak ODR globals in the sense it
172 // doesn't change semantics, but we really don't want to perform it
173 // anyway; it's likely to pessimize code generation, and some tools
174 // (like the Darwin linker in cases involving CFString) don't expect it.
175 if (GV.isWeakForLinker())
176 continue;
177
178 // Don't touch globals with metadata other then !dbg.
179 if (GV.hasMetadataOtherThanDebugLoc())
180 continue;
181
182 Constant *Init = GV.getInitializer();
183
184 // Check to see if the initializer is already known.
185 GlobalVariable *&Slot = CMap[Init];
186
187 // If this is the first constant we find or if the old one is local,
188 // replace with the current one. If the current is externally visible
189 // it cannot be replace, but can be the canonical constant we merge with.
190 bool FirstConstantFound = !Slot;
191 if (FirstConstantFound || IsBetterCanonical(A: GV, B: *Slot)) {
192 Slot = &GV;
193 LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV.getName()
194 << (FirstConstantFound ? "\n" : " (updated)\n"));
195 }
196 }
197
198 // Identify all globals that can be merged together, filling in the
199 // SameContentReplacements vector. We cannot do the replacement in this pass
200 // because doing so may cause initializers of other globals to be rewritten,
201 // invalidating the Constant* pointers in CMap.
202 for (GlobalVariable &GV : llvm::make_early_inc_range(Range: M.globals())) {
203 if (isUnmergeableGlobal(GV: &GV, UsedGlobals))
204 continue;
205
206 // We can only replace constant with local linkage.
207 if (!GV.hasLocalLinkage())
208 continue;
209
210 Constant *Init = GV.getInitializer();
211
212 // Check to see if the initializer is already known.
213 auto Found = CMap.find(Val: Init);
214 if (Found == CMap.end())
215 continue;
216
217 GlobalVariable *Slot = Found->second;
218 if (Slot == &GV)
219 continue;
220
221 if (makeMergeable(Old: &GV, New: Slot) == CanMerge::No)
222 continue;
223
224 // Make all uses of the duplicate constant use the canonical version.
225 LLVM_DEBUG(dbgs() << "Will replace: @" << GV.getName() << " -> @"
226 << Slot->getName() << "\n");
227 SameContentReplacements.push_back(Elt: std::make_pair(x: &GV, y&: Slot));
228 }
229
230 // Now that we have figured out which replacements must be made, do them all
231 // now. This avoid invalidating the pointers in CMap, which are unneeded
232 // now.
233 for (const auto &[Old, New] : SameContentReplacements) {
234 replace(M, Old, New);
235 ++ChangesMade;
236 ++NumIdenticalMerged;
237 }
238
239 if (ChangesMade == OldChangesMade)
240 break;
241 OldChangesMade = ChangesMade;
242
243 SameContentReplacements.clear();
244 CMap.clear();
245 }
246
247 return ChangesMade;
248}
249
250PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
251 if (!mergeConstants(M))
252 return PreservedAnalyses::all();
253 return PreservedAnalyses::none();
254}
255