← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Transforms/IPO/ConstantMerge.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

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