1 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
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
7 //===----------------------------------------------------------------------===//
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.
14 // Algorithm: ConstantMerge is designed to build up a map of available constants
15 // and eliminate duplicates when it is initialized.
17 //===----------------------------------------------------------------------===//
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/Pass.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Transforms/IPO.h"
40 #define DEBUG_TYPE "constmerge"
42 STATISTIC(NumIdenticalMerged
, "Number of identical global constants merged");
44 /// Find values that are marked as llvm.used.
45 static void FindUsedValues(GlobalVariable
*LLVMUsed
,
46 SmallPtrSetImpl
<const GlobalValue
*> &UsedValues
) {
47 if (!LLVMUsed
) return;
48 ConstantArray
*Inits
= cast
<ConstantArray
>(LLVMUsed
->getInitializer());
50 for (unsigned i
= 0, e
= Inits
->getNumOperands(); i
!= e
; ++i
) {
51 Value
*Operand
= Inits
->getOperand(i
)->stripPointerCasts();
52 GlobalValue
*GV
= cast
<GlobalValue
>(Operand
);
53 UsedValues
.insert(GV
);
57 // True if A is better than B.
58 static bool IsBetterCanonical(const GlobalVariable
&A
,
59 const GlobalVariable
&B
) {
60 if (!A
.hasLocalLinkage() && B
.hasLocalLinkage())
63 if (A
.hasLocalLinkage() && !B
.hasLocalLinkage())
66 return A
.hasGlobalUnnamedAddr();
69 static bool hasMetadataOtherThanDebugLoc(const GlobalVariable
*GV
) {
70 SmallVector
<std::pair
<unsigned, MDNode
*>, 4> MDs
;
71 GV
->getAllMetadata(MDs
);
72 for (const auto &V
: MDs
)
73 if (V
.first
!= LLVMContext::MD_dbg
)
78 static void copyDebugLocMetadata(const GlobalVariable
*From
,
80 SmallVector
<DIGlobalVariableExpression
*, 1> MDs
;
81 From
->getDebugInfo(MDs
);
86 static unsigned getAlignment(GlobalVariable
*GV
) {
87 unsigned Align
= GV
->getAlignment();
90 return GV
->getParent()->getDataLayout().getPreferredAlignment(GV
);
94 isUnmergeableGlobal(GlobalVariable
*GV
,
95 const SmallPtrSetImpl
<const GlobalValue
*> &UsedGlobals
) {
96 // Only process constants with initializers in the default address space.
97 return !GV
->isConstant() || !GV
->hasDefinitiveInitializer() ||
98 GV
->getType()->getAddressSpace() != 0 || GV
->hasSection() ||
99 // Don't touch values marked with attribute(used).
100 UsedGlobals
.count(GV
);
103 enum class CanMerge
{ No
, Yes
};
104 static CanMerge
makeMergeable(GlobalVariable
*Old
, GlobalVariable
*New
) {
105 if (!Old
->hasGlobalUnnamedAddr() && !New
->hasGlobalUnnamedAddr())
107 if (hasMetadataOtherThanDebugLoc(Old
))
109 assert(!hasMetadataOtherThanDebugLoc(New
));
110 if (!Old
->hasGlobalUnnamedAddr())
111 New
->setUnnamedAddr(GlobalValue::UnnamedAddr::None
);
112 return CanMerge::Yes
;
115 static void replace(Module
&M
, GlobalVariable
*Old
, GlobalVariable
*New
) {
116 Constant
*NewConstant
= New
;
118 LLVM_DEBUG(dbgs() << "Replacing global: @" << Old
->getName() << " -> @"
119 << New
->getName() << "\n");
121 // Bump the alignment if necessary.
122 if (Old
->getAlignment() || New
->getAlignment())
123 New
->setAlignment(std::max(getAlignment(Old
), getAlignment(New
)));
125 copyDebugLocMetadata(Old
, New
);
126 Old
->replaceAllUsesWith(NewConstant
);
128 // Delete the global value from the module.
129 assert(Old
->hasLocalLinkage() &&
130 "Refusing to delete an externally visible global variable.");
131 Old
->eraseFromParent();
134 static bool mergeConstants(Module
&M
) {
135 // Find all the globals that are marked "used". These cannot be merged.
136 SmallPtrSet
<const GlobalValue
*, 8> UsedGlobals
;
137 FindUsedValues(M
.getGlobalVariable("llvm.used"), UsedGlobals
);
138 FindUsedValues(M
.getGlobalVariable("llvm.compiler.used"), UsedGlobals
);
140 // Map unique constants to globals.
141 DenseMap
<Constant
*, GlobalVariable
*> CMap
;
143 SmallVector
<std::pair
<GlobalVariable
*, GlobalVariable
*>, 32>
144 SameContentReplacements
;
146 size_t ChangesMade
= 0;
147 size_t OldChangesMade
= 0;
149 // Iterate constant merging while we are still making progress. Merging two
150 // constants together may allow us to merge other constants together if the
151 // second level constants have initializers which point to the globals that
154 // Find the canonical constants others will be merged with.
155 for (Module::global_iterator GVI
= M
.global_begin(), E
= M
.global_end();
157 GlobalVariable
*GV
= &*GVI
++;
159 // If this GV is dead, remove it.
160 GV
->removeDeadConstantUsers();
161 if (GV
->use_empty() && GV
->hasLocalLinkage()) {
162 GV
->eraseFromParent();
167 if (isUnmergeableGlobal(GV
, UsedGlobals
))
170 // This transformation is legal for weak ODR globals in the sense it
171 // doesn't change semantics, but we really don't want to perform it
172 // anyway; it's likely to pessimize code generation, and some tools
173 // (like the Darwin linker in cases involving CFString) don't expect it.
174 if (GV
->isWeakForLinker())
177 // Don't touch globals with metadata other then !dbg.
178 if (hasMetadataOtherThanDebugLoc(GV
))
181 Constant
*Init
= GV
->getInitializer();
183 // Check to see if the initializer is already known.
184 GlobalVariable
*&Slot
= CMap
[Init
];
186 // If this is the first constant we find or if the old one is local,
187 // replace with the current one. If the current is externally visible
188 // it cannot be replace, but can be the canonical constant we merge with.
189 bool FirstConstantFound
= !Slot
;
190 if (FirstConstantFound
|| IsBetterCanonical(*GV
, *Slot
)) {
192 LLVM_DEBUG(dbgs() << "Cmap[" << *Init
<< "] = " << GV
->getName()
193 << (FirstConstantFound
? "\n" : " (updated)\n"));
197 // Identify all globals that can be merged together, filling in the
198 // SameContentReplacements vector. We cannot do the replacement in this pass
199 // because doing so may cause initializers of other globals to be rewritten,
200 // invalidating the Constant* pointers in CMap.
201 for (Module::global_iterator GVI
= M
.global_begin(), E
= M
.global_end();
203 GlobalVariable
*GV
= &*GVI
++;
205 if (isUnmergeableGlobal(GV
, UsedGlobals
))
208 // We can only replace constant with local linkage.
209 if (!GV
->hasLocalLinkage())
212 Constant
*Init
= GV
->getInitializer();
214 // Check to see if the initializer is already known.
215 auto Found
= CMap
.find(Init
);
216 if (Found
== CMap
.end())
219 GlobalVariable
*Slot
= Found
->second
;
223 if (makeMergeable(GV
, Slot
) == CanMerge::No
)
226 // Make all uses of the duplicate constant use the canonical version.
227 LLVM_DEBUG(dbgs() << "Will replace: @" << GV
->getName() << " -> @"
228 << Slot
->getName() << "\n");
229 SameContentReplacements
.push_back(std::make_pair(GV
, Slot
));
232 // Now that we have figured out which replacements must be made, do them all
233 // now. This avoid invalidating the pointers in CMap, which are unneeded
235 for (unsigned i
= 0, e
= SameContentReplacements
.size(); i
!= e
; ++i
) {
236 GlobalVariable
*Old
= SameContentReplacements
[i
].first
;
237 GlobalVariable
*New
= SameContentReplacements
[i
].second
;
238 replace(M
, Old
, New
);
240 ++NumIdenticalMerged
;
243 if (ChangesMade
== OldChangesMade
)
245 OldChangesMade
= ChangesMade
;
247 SameContentReplacements
.clear();
254 PreservedAnalyses
ConstantMergePass::run(Module
&M
, ModuleAnalysisManager
&) {
255 if (!mergeConstants(M
))
256 return PreservedAnalyses::all();
257 return PreservedAnalyses::none();
262 struct ConstantMergeLegacyPass
: public ModulePass
{
263 static char ID
; // Pass identification, replacement for typeid
265 ConstantMergeLegacyPass() : ModulePass(ID
) {
266 initializeConstantMergeLegacyPassPass(*PassRegistry::getPassRegistry());
269 // For this pass, process all of the globals in the module, eliminating
270 // duplicate constants.
271 bool runOnModule(Module
&M
) override
{
274 return mergeConstants(M
);
278 } // end anonymous namespace
280 char ConstantMergeLegacyPass::ID
= 0;
282 INITIALIZE_PASS(ConstantMergeLegacyPass
, "constmerge",
283 "Merge Duplicate Global Constants", false, false)
285 ModulePass
*llvm::createConstantMergePass() {
286 return new ConstantMergeLegacyPass();