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