← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/IPO/ConstantMerge.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/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
 
#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/ADT/DenseMap.h"
27
 
#include "llvm/ADT/SmallPtrSet.h"
28
 
#include "llvm/ADT/Statistic.h"
29
 
using namespace llvm;
30
 
 
31
 
STATISTIC(NumMerged, "Number of global constants merged");
32
 
 
33
 
namespace {
34
 
  struct ConstantMerge : public ModulePass {
35
 
    static char ID; // Pass identification, replacement for typeid
36
 
    ConstantMerge() : ModulePass(ID) {}
37
 
 
38
 
    // run - For this pass, process all of the globals in the module,
39
 
    // eliminating duplicate constants.
40
 
    //
41
 
    bool runOnModule(Module &M);
42
 
  };
43
 
}
44
 
 
45
 
char ConstantMerge::ID = 0;
46
 
INITIALIZE_PASS(ConstantMerge, "constmerge",
47
 
                "Merge Duplicate Global Constants", false, false);
48
 
 
49
 
ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
50
 
 
51
 
 
52
 
 
53
 
/// Find values that are marked as llvm.used.
54
 
static void FindUsedValues(GlobalVariable *LLVMUsed,
55
 
                           SmallPtrSet<const GlobalValue*, 8> &UsedValues) {
56
 
  if (LLVMUsed == 0) return;
57
 
  ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer());
58
 
  if (Inits == 0) return;
59
 
  
60
 
  for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i)
61
 
    if (GlobalValue *GV = 
62
 
        dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts()))
63
 
      UsedValues.insert(GV);
64
 
}
65
 
 
66
 
bool ConstantMerge::runOnModule(Module &M) {
67
 
  // Find all the globals that are marked "used".  These cannot be merged.
68
 
  SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
69
 
  FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
70
 
  FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
71
 
  
72
 
  // Map unique constant/section pairs to globals.  We don't want to merge
73
 
  // globals in different sections.
74
 
  DenseMap<Constant*, GlobalVariable*> CMap;
75
 
 
76
 
  // Replacements - This vector contains a list of replacements to perform.
77
 
  SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
78
 
 
79
 
  bool MadeChange = false;
80
 
 
81
 
  // Iterate constant merging while we are still making progress.  Merging two
82
 
  // constants together may allow us to merge other constants together if the
83
 
  // second level constants have initializers which point to the globals that
84
 
  // were just merged.
85
 
  while (1) {
86
 
    // First pass: identify all globals that can be merged together, filling in
87
 
    // the Replacements vector.  We cannot do the replacement in this pass
88
 
    // because doing so may cause initializers of other globals to be rewritten,
89
 
    // invalidating the Constant* pointers in CMap.
90
 
    //
91
 
    for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
92
 
         GVI != E; ) {
93
 
      GlobalVariable *GV = GVI++;
94
 
      
95
 
      // If this GV is dead, remove it.
96
 
      GV->removeDeadConstantUsers();
97
 
      if (GV->use_empty() && GV->hasLocalLinkage()) {
98
 
        GV->eraseFromParent();
99
 
        continue;
100
 
      }
101
 
      
102
 
      // Only process constants with initializers in the default addres space.
103
 
      if (!GV->isConstant() ||!GV->hasDefinitiveInitializer() ||
104
 
          GV->getType()->getAddressSpace() != 0 || !GV->getSection().empty() ||
105
 
          // Don't touch values marked with attribute(used).
106
 
          UsedGlobals.count(GV))
107
 
        continue;
108
 
      
109
 
      
110
 
      
111
 
      Constant *Init = GV->getInitializer();
112
 
 
113
 
      // Check to see if the initializer is already known.
114
 
      GlobalVariable *&Slot = CMap[Init];
115
 
 
116
 
      if (Slot == 0) {    // Nope, add it to the map.
117
 
        Slot = GV;
118
 
      } else if (GV->hasLocalLinkage()) {    // Yup, this is a duplicate!
119
 
        // Make all uses of the duplicate constant use the canonical version.
120
 
        Replacements.push_back(std::make_pair(GV, Slot));
121
 
      }
122
 
    }
123
 
 
124
 
    if (Replacements.empty())
125
 
      return MadeChange;
126
 
    CMap.clear();
127
 
 
128
 
    // Now that we have figured out which replacements must be made, do them all
129
 
    // now.  This avoid invalidating the pointers in CMap, which are unneeded
130
 
    // now.
131
 
    for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
132
 
      // Eliminate any uses of the dead global.
133
 
      Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
134
 
 
135
 
      // Delete the global value from the module.
136
 
      Replacements[i].first->eraseFromParent();
137
 
    }
138
 
 
139
 
    NumMerged += Replacements.size();
140
 
    Replacements.clear();
141
 
  }
142
 
}