LLVM  13.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 values marked with attribute(used).
99  UsedGlobals.count(GV);
100 }
101 
102 enum class CanMerge { No, Yes };
104  if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
105  return CanMerge::No;
107  return CanMerge::No;
109  if (!Old->hasGlobalUnnamedAddr())
110  New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
111  return CanMerge::Yes;
112 }
113 
114 static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
115  Constant *NewConstant = New;
116 
117  LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
118  << New->getName() << "\n");
119 
120  // Bump the alignment if necessary.
121  if (Old->getAlign() || New->getAlign())
122  New->setAlignment(std::max(getAlign(Old), getAlign(New)));
123 
124  copyDebugLocMetadata(Old, New);
125  Old->replaceAllUsesWith(NewConstant);
126 
127  // Delete the global value from the module.
128  assert(Old->hasLocalLinkage() &&
129  "Refusing to delete an externally visible global variable.");
130  Old->eraseFromParent();
131 }
132 
133 static bool mergeConstants(Module &M) {
134  // Find all the globals that are marked "used". These cannot be merged.
136  FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
137  FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
138 
139  // Map unique constants to globals.
141 
143  SameContentReplacements;
144 
145  size_t ChangesMade = 0;
146  size_t OldChangesMade = 0;
147 
148  // Iterate constant merging while we are still making progress. Merging two
149  // constants together may allow us to merge other constants together if the
150  // second level constants have initializers which point to the globals that
151  // were just merged.
152  while (true) {
153  // Find the canonical constants others will be merged with.
154  for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
155  GVI != E; ) {
156  GlobalVariable *GV = &*GVI++;
157 
158  // If this GV is dead, remove it.
160  if (GV->use_empty() && GV->hasLocalLinkage()) {
161  GV->eraseFromParent();
162  ++ChangesMade;
163  continue;
164  }
165 
166  if (isUnmergeableGlobal(GV, UsedGlobals))
167  continue;
168 
169  // This transformation is legal for weak ODR globals in the sense it
170  // doesn't change semantics, but we really don't want to perform it
171  // anyway; it's likely to pessimize code generation, and some tools
172  // (like the Darwin linker in cases involving CFString) don't expect it.
173  if (GV->isWeakForLinker())
174  continue;
175 
176  // Don't touch globals with metadata other then !dbg.
178  continue;
179 
180  Constant *Init = GV->getInitializer();
181 
182  // Check to see if the initializer is already known.
183  GlobalVariable *&Slot = CMap[Init];
184 
185  // If this is the first constant we find or if the old one is local,
186  // replace with the current one. If the current is externally visible
187  // it cannot be replace, but can be the canonical constant we merge with.
188  bool FirstConstantFound = !Slot;
189  if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) {
190  Slot = GV;
191  LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
192  << (FirstConstantFound ? "\n" : " (updated)\n"));
193  }
194  }
195 
196  // Identify all globals that can be merged together, filling in the
197  // SameContentReplacements vector. We cannot do the replacement in this pass
198  // because doing so may cause initializers of other globals to be rewritten,
199  // invalidating the Constant* pointers in CMap.
200  for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
201  GVI != E; ) {
202  GlobalVariable *GV = &*GVI++;
203 
204  if (isUnmergeableGlobal(GV, UsedGlobals))
205  continue;
206 
207  // We can only replace constant with local linkage.
208  if (!GV->hasLocalLinkage())
209  continue;
210 
211  Constant *Init = GV->getInitializer();
212 
213  // Check to see if the initializer is already known.
214  auto Found = CMap.find(Init);
215  if (Found == CMap.end())
216  continue;
217 
218  GlobalVariable *Slot = Found->second;
219  if (Slot == GV)
220  continue;
221 
222  if (makeMergeable(GV, Slot) == CanMerge::No)
223  continue;
224 
225  // Make all uses of the duplicate constant use the canonical version.
226  LLVM_DEBUG(dbgs() << "Will replace: @" << GV->getName() << " -> @"
227  << Slot->getName() << "\n");
228  SameContentReplacements.push_back(std::make_pair(GV, Slot));
229  }
230 
231  // Now that we have figured out which replacements must be made, do them all
232  // now. This avoid invalidating the pointers in CMap, which are unneeded
233  // now.
234  for (unsigned i = 0, e = SameContentReplacements.size(); i != e; ++i) {
235  GlobalVariable *Old = SameContentReplacements[i].first;
236  GlobalVariable *New = SameContentReplacements[i].second;
237  replace(M, Old, New);
238  ++ChangesMade;
239  ++NumIdenticalMerged;
240  }
241 
242  if (ChangesMade == OldChangesMade)
243  break;
244  OldChangesMade = ChangesMade;
245 
246  SameContentReplacements.clear();
247  CMap.clear();
248  }
249 
250  return ChangesMade;
251 }
252 
254  if (!mergeConstants(M))
255  return PreservedAnalyses::all();
256  return PreservedAnalyses::none();
257 }
258 
259 namespace {
260 
261 struct ConstantMergeLegacyPass : public ModulePass {
262  static char ID; // Pass identification, replacement for typeid
263 
264  ConstantMergeLegacyPass() : ModulePass(ID) {
266  }
267 
268  // For this pass, process all of the globals in the module, eliminating
269  // duplicate constants.
270  bool runOnModule(Module &M) override {
271  if (skipModule(M))
272  return false;
273  return mergeConstants(M);
274  }
275 };
276 
277 } // end anonymous namespace
278 
280 
281 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
282  "Merge Duplicate Global Constants", false, false)
283 
285  return new ConstantMergeLegacyPass();
286 }
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
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:253
llvm::DataLayout::getPreferredAlign
Align getPreferredAlign(const GlobalVariable *GV) const
Returns the preferred alignment of the specified global.
Definition: DataLayout.cpp:905
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:82
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:662
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:122
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
mergeConstants
static bool mergeConstants(Module &M)
Definition: ConstantMerge.cpp:133
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:1697
makeMergeable
static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New)
Definition: ConstantMerge.cpp:103
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:407
llvm::Module::global_iterator
GlobalListType::iterator global_iterator
The Global Variable iterator.
Definition: Module.h:87
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
SmallPtrSet.h
CanMerge
CanMerge
Definition: ConstantMerge.cpp:102
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::Value::use_empty
bool use_empty() const
Definition: Value.h:357
llvm::GlobalVariable::addDebugInfo
void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
Definition: Metadata.cpp:1539
llvm::Optional::getValueOr
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:295
llvm::GlobalObject::hasSection
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:106
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::isWeakForLinker
static bool isWeakForLinker(LinkageTypes Linkage)
Whether the definition of this global may be replaced at link time.
Definition: GlobalValue.h:378
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::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::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
llvm::Constant::removeDeadConstantUsers
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:738
DataLayout.h
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:526
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:298
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:636
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:350
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:1217
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:397
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:281
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:38