LLVM 22.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/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,
47 if (!LLVMUsed) return;
48 ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
49
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);
54 }
55}
56
57// True if A is better than B.
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 return A.hasGlobalUnnamedAddr();
67}
68
71 GV->getAllMetadata(MDs);
72 for (const auto &V : MDs)
73 if (V.first != LLVMContext::MD_dbg)
74 return true;
75 return false;
76}
77
78static void copyDebugLocMetadata(const GlobalVariable *From,
79 GlobalVariable *To) {
81 From->getDebugInfo(MDs);
82 for (auto *MD : MDs)
83 To->addDebugInfo(MD);
84}
85
87 return GV->getAlign().value_or(
89}
90
91static bool
93 const SmallPtrSetImpl<const GlobalValue *> &UsedGlobals) {
94 // Only process constants with initializers in the default address space.
95 return !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
96 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
97 // Don't touch thread-local variables.
98 GV->isThreadLocal() ||
99 // Don't touch values marked with attribute(used).
100 UsedGlobals.count(GV);
101}
102
103enum class CanMerge { No, Yes };
105 if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
106 return CanMerge::No;
108 return CanMerge::No;
110 if (!Old->hasGlobalUnnamedAddr())
111 New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
112 return CanMerge::Yes;
113}
114
115static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
116 Constant *NewConstant = New;
117
118 LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
119 << New->getName() << "\n");
120
121 // Bump the alignment if necessary.
122 if (Old->getAlign() || New->getAlign())
123 New->setAlignment(std::max(getAlign(Old), getAlign(New)));
124
125 copyDebugLocMetadata(Old, New);
126 Old->replaceAllUsesWith(NewConstant);
127
128 // Delete the global value from the module.
129 assert(Old->hasLocalLinkage() &&
130 "Refusing to delete an externally visible global variable.");
131 Old->eraseFromParent();
132}
133
134static bool mergeConstants(Module &M) {
135 // Find all the globals that are marked "used". These cannot be merged.
137 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
138 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
139
140 // Map unique constants to globals.
142
144 SameContentReplacements;
145
146 size_t ChangesMade = 0;
147 size_t OldChangesMade = 0;
148
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
152 // were just merged.
153 while (true) {
154 // Find the canonical constants others will be merged with.
155 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
156 // If this GV is dead, remove it.
157 GV.removeDeadConstantUsers();
158 if (GV.use_empty() && GV.hasLocalLinkage()) {
159 GV.eraseFromParent();
160 ++ChangesMade;
161 continue;
162 }
163
164 if (isUnmergeableGlobal(&GV, UsedGlobals))
165 continue;
166
167 // This transformation is legal for weak ODR globals in the sense it
168 // doesn't change semantics, but we really don't want to perform it
169 // anyway; it's likely to pessimize code generation, and some tools
170 // (like the Darwin linker in cases involving CFString) don't expect it.
171 if (GV.isWeakForLinker())
172 continue;
173
174 // Don't touch globals with metadata other then !dbg.
176 continue;
177
178 Constant *Init = GV.getInitializer();
179
180 // Check to see if the initializer is already known.
181 GlobalVariable *&Slot = CMap[Init];
182
183 // If this is the first constant we find or if the old one is local,
184 // replace with the current one. If the current is externally visible
185 // it cannot be replace, but can be the canonical constant we merge with.
186 bool FirstConstantFound = !Slot;
187 if (FirstConstantFound || IsBetterCanonical(GV, *Slot)) {
188 Slot = &GV;
189 LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV.getName()
190 << (FirstConstantFound ? "\n" : " (updated)\n"));
191 }
192 }
193
194 // Identify all globals that can be merged together, filling in the
195 // SameContentReplacements vector. We cannot do the replacement in this pass
196 // because doing so may cause initializers of other globals to be rewritten,
197 // invalidating the Constant* pointers in CMap.
198 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
199 if (isUnmergeableGlobal(&GV, UsedGlobals))
200 continue;
201
202 // We can only replace constant with local linkage.
203 if (!GV.hasLocalLinkage())
204 continue;
205
206 Constant *Init = GV.getInitializer();
207
208 // Check to see if the initializer is already known.
209 auto Found = CMap.find(Init);
210 if (Found == CMap.end())
211 continue;
212
213 GlobalVariable *Slot = Found->second;
214 if (Slot == &GV)
215 continue;
216
217 if (makeMergeable(&GV, Slot) == CanMerge::No)
218 continue;
219
220 // Make all uses of the duplicate constant use the canonical version.
221 LLVM_DEBUG(dbgs() << "Will replace: @" << GV.getName() << " -> @"
222 << Slot->getName() << "\n");
223 SameContentReplacements.push_back(std::make_pair(&GV, Slot));
224 }
225
226 // Now that we have figured out which replacements must be made, do them all
227 // now. This avoid invalidating the pointers in CMap, which are unneeded
228 // now.
229 for (const auto &[Old, New] : SameContentReplacements) {
230 replace(M, Old, New);
231 ++ChangesMade;
232 ++NumIdenticalMerged;
233 }
234
235 if (ChangesMade == OldChangesMade)
236 break;
237 OldChangesMade = ChangesMade;
238
239 SameContentReplacements.clear();
240 CMap.clear();
241 }
242
243 return ChangesMade;
244}
245
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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 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.
static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
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:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
ConstantArray - Constant Array Declarations.
Definition Constants.h:433
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This is an important base class in LLVM.
Definition Constant.h:43
LLVM_ABI Align getPreferredAlign(const GlobalVariable *GV) const
Returns the preferred alignment of the specified global.
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:165
iterator end()
Definition DenseMap.h:81
LLVM_ABI void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode * > > &MDs) const
Appends all metadata attached to this value to MDs, sorting by KindID.
bool hasSection() const
Check if this global has a custom object file section.
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
bool hasLocalLinkage() const
PointerType * getType() const
Global values are always pointers.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this global belongs to.
Definition Globals.cpp:132
bool hasGlobalUnnamedAddr() const
MaybeAlign getAlign() const
Returns the alignment of the given variable.
LLVM_ABI void getDebugInfo(SmallVectorImpl< DIGlobalVariableExpression * > &GVs) const
Fill the vector with all debug info attachements.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
LLVM_ABI void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition Globals.cpp:519
LLVM_ABI void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
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:67
unsigned getAddressSpace() const
Return the address space of the Pointer type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition Analysis.h:115
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Value * getOperand(unsigned i) const
Definition User.h:232
unsigned getNumOperands() const
Definition User.h:254
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:546
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition Value.cpp:701
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:322
This is an optimization pass for GlobalISel generic memory operations.
MaybeAlign getAlign(const CallInst &I, unsigned Index)
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:634
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
void replace(R &&Range, const T &OldValue, const T &NewValue)
Provide wrappers to std::replace which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1840
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition MIRParser.h:39
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39