ConstantMerge.cpp revision 263508 
1//===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the interface to a pass that merges duplicate global
11// constants together into a single constant that is shared.  This is useful
12// because some passes (ie TraceValues) insert a lot of string constants into
13// the program, regardless of whether or not an existing string is available.
14//
15// Algorithm: ConstantMerge is designed to build up a map of available constants
16// and eliminate duplicates when it is initialized.
17//
18//===----------------------------------------------------------------------===//
19
20#define DEBUG_TYPE "constmerge"
21#include "llvm/Transforms/IPO.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/PointerIntPair.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DataLayout.h"
28#include "llvm/IR/DerivedTypes.h"
29#include "llvm/IR/Module.h"
30#include "llvm/IR/Operator.h"
31#include "llvm/Pass.h"
32using namespace llvm;
33
34STATISTIC(NumMerged, "Number of global constants merged");
35
36namespace {
37  struct ConstantMerge : public ModulePass {
38    static char ID; // Pass identification, replacement for typeid
39    ConstantMerge() : ModulePass(ID) {
40      initializeConstantMergePass(*PassRegistry::getPassRegistry());
41    }
42
43    // For this pass, process all of the globals in the module, eliminating
44    // duplicate constants.
45    bool runOnModule(Module &M);
46
47    // Return true iff we can determine the alignment of this global variable.
48    bool hasKnownAlignment(GlobalVariable *GV) const;
49
50    // Return the alignment of the global, including converting the default
51    // alignment to a concrete value.
52    unsigned getAlignment(GlobalVariable *GV) const;
53
54    const DataLayout *TD;
55  };
56}
57
58char ConstantMerge::ID = 0;
59INITIALIZE_PASS(ConstantMerge, "constmerge",
60                "Merge Duplicate Global Constants", false, false)
61
62ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
63
64
65
66/// Find values that are marked as llvm.used.
67static void FindUsedValues(GlobalVariable *LLVMUsed,
68                           SmallPtrSet<const GlobalValue*, 8> &UsedValues) {
69  if (LLVMUsed == 0) return;
70  ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
71
72  for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i) {
73    Value *Operand = Inits->getOperand(i)->stripPointerCastsNoFollowAliases();
74    GlobalValue *GV = cast<GlobalValue>(Operand);
75    UsedValues.insert(GV);
76  }
77}
78
79// True if A is better than B.
80static bool IsBetterCannonical(const GlobalVariable &A,
81                               const GlobalVariable &B) {
82  if (!A.hasLocalLinkage() && B.hasLocalLinkage())
83    return true;
84
85  if (A.hasLocalLinkage() && !B.hasLocalLinkage())
86    return false;
87
88  return A.hasUnnamedAddr();
89}
90
91bool ConstantMerge::hasKnownAlignment(GlobalVariable *GV) const {
92  return TD || GV->getAlignment() != 0;
93}
94
95unsigned ConstantMerge::getAlignment(GlobalVariable *GV) const {
96  unsigned Align = GV->getAlignment();
97  if (Align)
98    return Align;
99  if (TD)
100    return TD->getPreferredAlignment(GV);
101  return 0;
102}
103
104bool ConstantMerge::runOnModule(Module &M) {
105  TD = getAnalysisIfAvailable<DataLayout>();
106
107  // Find all the globals that are marked "used".  These cannot be merged.
108  SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
109  FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
110  FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
111
112  // Map unique <constants, has-unknown-alignment> pairs to globals.  We don't
113  // want to merge globals of unknown alignment with those of explicit
114  // alignment.  If we have DataLayout, we always know the alignment.
115  DenseMap<PointerIntPair<Constant*, 1, bool>, GlobalVariable*> CMap;
116
117  // Replacements - This vector contains a list of replacements to perform.
118  SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
119
120  bool MadeChange = false;
121
122  // Iterate constant merging while we are still making progress.  Merging two
123  // constants together may allow us to merge other constants together if the
124  // second level constants have initializers which point to the globals that
125  // were just merged.
126  while (1) {
127
128    // First: Find the canonical constants others will be merged with.
129    for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
130         GVI != E; ) {
131      GlobalVariable *GV = GVI++;
132
133      // If this GV is dead, remove it.
134      GV->removeDeadConstantUsers();
135      if (GV->use_empty() && GV->hasLocalLinkage()) {
136        GV->eraseFromParent();
137        continue;
138      }
139
140      // Only process constants with initializers in the default address space.
141      if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
142          GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
143          // Don't touch values marked with attribute(used).
144          UsedGlobals.count(GV))
145        continue;
146
147      // This transformation is legal for weak ODR globals in the sense it
148      // doesn't change semantics, but we really don't want to perform it
149      // anyway; it's likely to pessimize code generation, and some tools
150      // (like the Darwin linker in cases involving CFString) don't expect it.
151      if (GV->isWeakForLinker())
152        continue;
153
154      Constant *Init = GV->getInitializer();
155
156      // Check to see if the initializer is already known.
157      PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
158      GlobalVariable *&Slot = CMap[Pair];
159
160      // If this is the first constant we find or if the old one is local,
161      // replace with the current one. If the current is externally visible
162      // it cannot be replace, but can be the canonical constant we merge with.
163      if (Slot == 0 || IsBetterCannonical(*GV, *Slot))
164        Slot = GV;
165    }
166
167    // Second: identify all globals that can be merged together, filling in
168    // the Replacements vector.  We cannot do the replacement in this pass
169    // because doing so may cause initializers of other globals to be rewritten,
170    // invalidating the Constant* pointers in CMap.
171    for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
172         GVI != E; ) {
173      GlobalVariable *GV = GVI++;
174
175      // Only process constants with initializers in the default address space.
176      if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
177          GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
178          // Don't touch values marked with attribute(used).
179          UsedGlobals.count(GV))
180        continue;
181
182      // We can only replace constant with local linkage.
183      if (!GV->hasLocalLinkage())
184        continue;
185
186      Constant *Init = GV->getInitializer();
187
188      // Check to see if the initializer is already known.
189      PointerIntPair<Constant*, 1, bool> Pair(Init, hasKnownAlignment(GV));
190      GlobalVariable *Slot = CMap[Pair];
191
192      if (!Slot || Slot == GV)
193        continue;
194
195      if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr())
196        continue;
197
198      if (!GV->hasUnnamedAddr())
199        Slot->setUnnamedAddr(false);
200
201      // Make all uses of the duplicate constant use the canonical version.
202      Replacements.push_back(std::make_pair(GV, Slot));
203    }
204
205    if (Replacements.empty())
206      return MadeChange;
207    CMap.clear();
208
209    // Now that we have figured out which replacements must be made, do them all
210    // now.  This avoid invalidating the pointers in CMap, which are unneeded
211    // now.
212    for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
213      // Bump the alignment if necessary.
214      if (Replacements[i].first->getAlignment() ||
215          Replacements[i].second->getAlignment()) {
216        Replacements[i].second->setAlignment(
217            std::max(getAlignment(Replacements[i].first),
218                     getAlignment(Replacements[i].second)));
219      }
220
221      // Eliminate any uses of the dead global.
222      Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
223
224      // Delete the global value from the module.
225      assert(Replacements[i].first->hasLocalLinkage() &&
226             "Refusing to delete an externally visible global variable.");
227      Replacements[i].first->eraseFromParent();
228    }
229
230    NumMerged += Replacements.size();
231    Replacements.clear();
232  }
233}
234