LLVM  9.0.0svn
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/Pass.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Transforms/IPO.h"
34 #include <algorithm>
35 #include <cassert>
36 #include <utility>
37 
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "constmerge"
41 
42 STATISTIC(NumIdenticalMerged, "Number of identical global constants merged");
43 
44 /// Find values that are marked as llvm.used.
45 static 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)->stripPointerCastsNoFollowAliases();
52  GlobalValue *GV = cast<GlobalValue>(Operand);
53  UsedValues.insert(GV);
54  }
55 }
56 
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())
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 
79  GlobalVariable *To) {
81  From->getDebugInfo(MDs);
82  for (auto MD : MDs)
83  To->addDebugInfo(MD);
84 }
85 
86 static unsigned getAlignment(GlobalVariable *GV) {
87  unsigned Align = GV->getAlignment();
88  if (Align)
89  return Align;
90  return GV->getParent()->getDataLayout().getPreferredAlignment(GV);
91 }
92 
93 static bool
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);
101 }
102 
103 enum class CanMerge { No, Yes };
105  if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
106  return CanMerge::No;
108  return CanMerge::No;
110  if (!Old->hasGlobalUnnamedAddr())
112  return CanMerge::Yes;
113 }
114 
115 static 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->getAlignment() || New->getAlignment())
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 
134 static 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 (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
156  GVI != E; ) {
157  GlobalVariable *GV = &*GVI++;
158 
159  // If this GV is dead, remove it.
161  if (GV->use_empty() && GV->hasLocalLinkage()) {
162  GV->eraseFromParent();
163  ++ChangesMade;
164  continue;
165  }
166 
167  if (isUnmergeableGlobal(GV, UsedGlobals))
168  continue;
169 
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())
175  continue;
176 
177  // Don't touch globals with metadata other then !dbg.
179  continue;
180 
181  Constant *Init = GV->getInitializer();
182 
183  // Check to see if the initializer is already known.
184  GlobalVariable *&Slot = CMap[Init];
185 
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)) {
191  Slot = GV;
192  LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
193  << (FirstConstantFound ? "\n" : " (updated)\n"));
194  }
195  }
196 
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();
202  GVI != E; ) {
203  GlobalVariable *GV = &*GVI++;
204 
205  if (isUnmergeableGlobal(GV, UsedGlobals))
206  continue;
207 
208  // We can only replace constant with local linkage.
209  if (!GV->hasLocalLinkage())
210  continue;
211 
212  Constant *Init = GV->getInitializer();
213 
214  // Check to see if the initializer is already known.
215  auto Found = CMap.find(Init);
216  if (Found == CMap.end())
217  continue;
218 
219  GlobalVariable *Slot = Found->second;
220  if (Slot == GV)
221  continue;
222 
223  if (makeMergeable(GV, Slot) == CanMerge::No)
224  continue;
225 
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));
230  }
231 
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
234  // now.
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);
239  ++ChangesMade;
240  ++NumIdenticalMerged;
241  }
242 
243  if (ChangesMade == OldChangesMade)
244  break;
245  OldChangesMade = ChangesMade;
246 
247  SameContentReplacements.clear();
248  CMap.clear();
249  }
250 
251  return ChangesMade;
252 }
253 
255  if (!mergeConstants(M))
256  return PreservedAnalyses::all();
257  return PreservedAnalyses::none();
258 }
259 
260 namespace {
261 
262 struct ConstantMergeLegacyPass : public ModulePass {
263  static char ID; // Pass identification, replacement for typeid
264 
265  ConstantMergeLegacyPass() : ModulePass(ID) {
267  }
268 
269  // For this pass, process all of the globals in the module, eliminating
270  // duplicate constants.
271  bool runOnModule(Module &M) override {
272  if (skipModule(M))
273  return false;
274  return mergeConstants(M);
275  }
276 };
277 
278 } // end anonymous namespace
279 
281 
282 INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge",
283  "Merge Duplicate Global Constants", false, false)
284 
286  return new ConstantMergeLegacyPass();
287 }
unsigned getAlignment() const
Definition: GlobalObject.h:58
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
bool hasLocalLinkage() const
Definition: GlobalValue.h:435
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
GlobalVariable * getGlobalVariable(StringRef Name) const
Look up the specified global variable in the module symbol table.
Definition: Module.h:390
STATISTIC(NumFunctions, "Total number of functions")
void getAllMetadata(SmallVectorImpl< std::pair< unsigned, MDNode *>> &MDs) const
Appends all attachments for the global to MDs, sorting by attachment ID.
Definition: Metadata.cpp:1413
void setAlignment(unsigned Align)
Definition: Globals.cpp:115
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
global_iterator global_begin()
Definition: Module.h:581
static bool IsBetterCanonical(const GlobalVariable &A, const GlobalVariable &B)
static unsigned getAlignment(GlobalVariable *GV)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
static bool hasMetadataOtherThanDebugLoc(const GlobalVariable *GV)
Value * getOperand(unsigned i) const
Definition: User.h:169
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:546
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
static bool isWeakForLinker(LinkageTypes Linkage)
Whether the definition of this global may be replaced at link time.
Definition: GlobalValue.h:369
INITIALIZE_PASS(ConstantMergeLegacyPass, "constmerge", "Merge Duplicate Global Constants", false, false) ModulePass *llvm
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void copyDebugLocMetadata(const GlobalVariable *From, GlobalVariable *To)
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:370
void getDebugInfo(SmallVectorImpl< DIGlobalVariableExpression *> &GVs) const
Fill the vector with all debug info attachements.
Definition: Metadata.cpp:1521
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Globals.cpp:358
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
ModulePass * createConstantMergePass()
createConstantMergePass - This function returns a new pass that merges duplicate global constants tog...
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:526
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
void initializeConstantMergeLegacyPassPass(PassRegistry &)
global_iterator global_end()
Definition: Module.h:583
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:81
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:199
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
CanMerge
unsigned getPreferredAlignment(const GlobalVariable *GV) const
Returns the preferred alignment of the specified global.
Definition: DataLayout.cpp:837
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:215
static bool isUnmergeableGlobal(GlobalVariable *GV, const SmallPtrSetImpl< const GlobalValue *> &UsedGlobals)
const Value * stripPointerCastsNoFollowAliases() const
Strip off pointer casts and all-zero GEPs.
Definition: Value.cpp:533
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
static bool mergeConstants(Module &M)
static void FindUsedValues(GlobalVariable *LLVMUsed, SmallPtrSetImpl< const GlobalValue *> &UsedValues)
Find values that are marked as llvm.used.
static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
Definition: Metadata.cpp:1517
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool use_empty() const
Definition: Value.h:322
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:273