LLVM  14.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"
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.
46 static 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.
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 
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().getValueOr(
90 }
91 
92 static 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 
104 enum 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 
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 
135 static 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();
252  return PreservedAnalyses::none();
253 }
254 
255 namespace {
256 
257 struct ConstantMergeLegacyPass : public ModulePass {
258  static char ID; // Pass identification, replacement for typeid
259 
260  ConstantMergeLegacyPass() : ModulePass(ID) {
262  }
263 
264  // For this pass, process all of the globals in the module, eliminating
265  // duplicate constants.
266  bool runOnModule(Module &M) override {
267  if (skipModule(M))
268  return false;
269  return mergeConstants(M);
270  }
271 };
272 
273 } // end anonymous namespace
274 
276 
277 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
278  "Merge Duplicate Global Constants", false, false)
279 
281  return new ConstantMergeLegacyPass();
282 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::GlobalVariable::eraseFromParent
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:385
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ConstantMergePass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: ConstantMerge.cpp:249
llvm::DataLayout::getPreferredAlign
Align getPreferredAlign(const GlobalVariable *GV) const
Returns the preferred alignment of the specified global.
Definition: DataLayout.cpp:972
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
CanMerge::Yes
@ Yes
Pass.h
ConstantMerge.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::GlobalObject::getAlign
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
Definition: GlobalObject.h:80
llvm::GlobalValue::UnnamedAddr::None
@ None
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:687
llvm::initializeConstantMergeLegacyPassPass
void initializeConstantMergeLegacyPassPass(PassRegistry &)
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
DenseMap.h
Module.h
CanMerge::No
@ No
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
FindUsedValues
static void FindUsedValues(GlobalVariable *LLVMUsed, SmallPtrSetImpl< const GlobalValue * > &UsedValues)
Find values that are marked as llvm.used.
Definition: ConstantMerge.cpp:46
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GlobalValue.h
llvm::InlinerFunctionImportStatsOpts::No
@ No
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
mergeConstants
static bool mergeConstants(Module &M)
Definition: ConstantMerge.cpp:135
llvm::replace
void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd)
Given a sequence container Cont, replace the range [ContIt, ContEnd) with the range [ValIt,...
Definition: STLExtras.h:1755
makeMergeable
static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New)
Definition: ConstantMerge.cpp:105
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
SmallPtrSet.h
CanMerge
CanMerge
Definition: ConstantMerge.cpp:104
llvm::GlobalValue::hasGlobalUnnamedAddr
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:196
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
isUnmergeableGlobal
static bool isUnmergeableGlobal(GlobalVariable *GV, const SmallPtrSetImpl< const GlobalValue * > &UsedGlobals)
Definition: ConstantMerge.cpp:93
llvm::GlobalVariable::addDebugInfo
void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
Definition: Metadata.cpp:1554
llvm::Optional::getValueOr
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:297
llvm::GlobalObject::hasSection
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:104
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:136
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
llvm::GlobalVariable::hasDefinitiveInitializer
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Definition: GlobalVariable.h:110
IPO.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::make_early_inc_range
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:576
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
llvm::GlobalValue::isThreadLocal
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Definition: GlobalValue.h:244
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
IsBetterCanonical
static bool IsBetterCanonical(const GlobalVariable &A, const GlobalVariable &B)
Definition: ConstantMerge.cpp:59
DataLayout.h
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
hasMetadataOtherThanDebugLoc
static bool hasMetadataOtherThanDebugLoc(const GlobalVariable *GV)
Definition: ConstantMerge.cpp:70
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::Init
Definition: Record.h:271
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:687
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
GlobalVariable.h
Casting.h
copyDebugLocMetadata
static void copyDebugLocMetadata(const GlobalVariable *From, GlobalVariable *To)
Definition: ConstantMerge.cpp:79
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::PrevailingType::Yes
@ Yes
llvm::getAlign
bool getAlign(const Function &F, unsigned index, unsigned &align)
Definition: NVPTXUtilities.cpp:284
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
llvm::GlobalVariable::isConstant
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
Definition: GlobalVariable.h:153
llvm::createConstantMergePass
ModulePass * createConstantMergePass()
createConstantMergePass - This function returns a new pass that merges duplicate global constants tog...
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::GlobalObject::getAllMetadata
void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode * >> &MDs) const
Appends all metadata attached to this value to MDs, sorting by KindID.
Definition: Metadata.cpp:1223
llvm::GlobalValue::getType
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:271
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
INITIALIZE_PASS
INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge", "Merge Duplicate Global Constants", false, false) ModulePass *llvm
Definition: ConstantMerge.cpp:277
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SmallPtrSetImpl::insert
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37