LLVM 17.0.0git
ConstantMerge.cpp
Go to the documentation of this file.
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
20#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/GlobalValue.h"
29#include "llvm/IR/LLVMContext.h"
30#include "llvm/IR/Module.h"
32#include "llvm/Pass.h"
34#include "llvm/Transforms/IPO.h"
35#include <algorithm>
36#include <cassert>
37#include <utility>
38
39using namespace llvm;
40
41#define DEBUG_TYPE "constmerge"
42
43STATISTIC(NumIdenticalMerged, "Number of identical global constants merged");
44
45/// Find values that are marked as llvm.used.
46static void FindUsedValues(GlobalVariable *LLVMUsed,
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.
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
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
80 GlobalVariable *To) {
82 From->getDebugInfo(MDs);
83 for (auto *MD : MDs)
84 To->addDebugInfo(MD);
85}
86
88 return GV->getAlign().value_or(
90}
91
92static bool
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
104enum class CanMerge { No, Yes };
106 if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
107 return CanMerge::No;
109 return CanMerge::No;
111 if (!Old->hasGlobalUnnamedAddr())
112 New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
113 return CanMerge::Yes;
114}
115
116static 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
135static bool mergeConstants(Module &M) {
136 // Find all the globals that are marked "used". These cannot be merged.
138 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
139 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
140
141 // Map unique constants to globals.
143
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.
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
250 if (!mergeConstants(M))
251 return PreservedAnalyses::all();
253}
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static bool IsBetterCanonical(const GlobalVariable &A, const GlobalVariable &B)
static bool hasMetadataOtherThanDebugLoc(const GlobalVariable *GV)
static void copyDebugLocMetadata(const GlobalVariable *From, GlobalVariable *To)
static bool mergeConstants(Module &M)
static Align getAlign(GlobalVariable *GV)
static bool isUnmergeableGlobal(GlobalVariable *GV, const SmallPtrSetImpl< const GlobalValue * > &UsedGlobals)
static void FindUsedValues(GlobalVariable *LLVMUsed, SmallPtrSetImpl< const GlobalValue * > &UsedValues)
Find values that are marked as llvm.used.
CanMerge
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This is an important base class in LLVM.
Definition: Constant.h:41
Align getPreferredAlign(const GlobalVariable *GV) const
Returns the preferred alignment of the specified global.
Definition: DataLayout.cpp:994
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
Definition: GlobalObject.h:79
void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode * > > &MDs) const
Appends all metadata attached to this value to MDs, sorting by KindID.
Definition: Metadata.cpp:1314
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:109
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Definition: GlobalValue.h:259
bool hasLocalLinkage() const
Definition: GlobalValue.h:523
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:290
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:211
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:468
void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
Definition: Metadata.cpp:1638
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39