• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
ConstantMerge__anondd12b4640111::ConstantMerge36     ConstantMerge() : ModulePass(ID) {
37       initializeConstantMergePass(*PassRegistry::getPassRegistry());
38     }
39 
40     // run - For this pass, process all of the globals in the module,
41     // eliminating duplicate constants.
42     //
43     bool runOnModule(Module &M);
44   };
45 }
46 
47 char ConstantMerge::ID = 0;
48 INITIALIZE_PASS(ConstantMerge, "constmerge",
49                 "Merge Duplicate Global Constants", false, false)
50 
createConstantMergePass()51 ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); }
52 
53 
54 
55 /// Find values that are marked as llvm.used.
FindUsedValues(GlobalVariable * LLVMUsed,SmallPtrSet<const GlobalValue *,8> & UsedValues)56 static void FindUsedValues(GlobalVariable *LLVMUsed,
57                            SmallPtrSet<const GlobalValue*, 8> &UsedValues) {
58   if (LLVMUsed == 0) return;
59   ConstantArray *Inits = dyn_cast<ConstantArray>(LLVMUsed->getInitializer());
60   if (Inits == 0) return;
61 
62   for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i)
63     if (GlobalValue *GV =
64         dyn_cast<GlobalValue>(Inits->getOperand(i)->stripPointerCasts()))
65       UsedValues.insert(GV);
66 }
67 
68 // True if A is better than B.
IsBetterCannonical(const GlobalVariable & A,const GlobalVariable & B)69 static bool IsBetterCannonical(const GlobalVariable &A,
70                                const GlobalVariable &B) {
71   if (!A.hasLocalLinkage() && B.hasLocalLinkage())
72     return true;
73 
74   if (A.hasLocalLinkage() && !B.hasLocalLinkage())
75     return false;
76 
77   return A.hasUnnamedAddr();
78 }
79 
runOnModule(Module & M)80 bool ConstantMerge::runOnModule(Module &M) {
81   // Find all the globals that are marked "used".  These cannot be merged.
82   SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
83   FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
84   FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
85 
86   // Map unique constant/section pairs to globals.  We don't want to merge
87   // globals in different sections.
88   DenseMap<Constant*, GlobalVariable*> CMap;
89 
90   // Replacements - This vector contains a list of replacements to perform.
91   SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements;
92 
93   bool MadeChange = false;
94 
95   // Iterate constant merging while we are still making progress.  Merging two
96   // constants together may allow us to merge other constants together if the
97   // second level constants have initializers which point to the globals that
98   // were just merged.
99   while (1) {
100 
101     // First: Find the canonical constants others will be merged with.
102     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
103          GVI != E; ) {
104       GlobalVariable *GV = GVI++;
105 
106       // If this GV is dead, remove it.
107       GV->removeDeadConstantUsers();
108       if (GV->use_empty() && GV->hasLocalLinkage()) {
109         GV->eraseFromParent();
110         continue;
111       }
112 
113       // Only process constants with initializers in the default address space.
114       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
115           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
116           // Don't touch values marked with attribute(used).
117           UsedGlobals.count(GV))
118         continue;
119 
120       Constant *Init = GV->getInitializer();
121 
122       // Check to see if the initializer is already known.
123       GlobalVariable *&Slot = CMap[Init];
124 
125       // If this is the first constant we find or if the old on is local,
126       // replace with the current one. It the current is externally visible
127       // it cannot be replace, but can be the canonical constant we merge with.
128       if (Slot == 0 || IsBetterCannonical(*GV, *Slot)) {
129         Slot = GV;
130       }
131     }
132 
133     // Second: identify all globals that can be merged together, filling in
134     // the Replacements vector.  We cannot do the replacement in this pass
135     // because doing so may cause initializers of other globals to be rewritten,
136     // invalidating the Constant* pointers in CMap.
137     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
138          GVI != E; ) {
139       GlobalVariable *GV = GVI++;
140 
141       // Only process constants with initializers in the default address space.
142       if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
143           GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
144           // Don't touch values marked with attribute(used).
145           UsedGlobals.count(GV))
146         continue;
147 
148       // We can only replace constant with local linkage.
149       if (!GV->hasLocalLinkage())
150         continue;
151 
152       Constant *Init = GV->getInitializer();
153 
154       // Check to see if the initializer is already known.
155       GlobalVariable *Slot = CMap[Init];
156 
157       if (!Slot || Slot == GV)
158         continue;
159 
160       if (!Slot->hasUnnamedAddr() && !GV->hasUnnamedAddr())
161         continue;
162 
163       if (!GV->hasUnnamedAddr())
164         Slot->setUnnamedAddr(false);
165 
166       // Make all uses of the duplicate constant use the canonical version.
167       Replacements.push_back(std::make_pair(GV, Slot));
168     }
169 
170     if (Replacements.empty())
171       return MadeChange;
172     CMap.clear();
173 
174     // Now that we have figured out which replacements must be made, do them all
175     // now.  This avoid invalidating the pointers in CMap, which are unneeded
176     // now.
177     for (unsigned i = 0, e = Replacements.size(); i != e; ++i) {
178       // Eliminate any uses of the dead global.
179       Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
180 
181       // Delete the global value from the module.
182       assert(Replacements[i].first->hasLocalLinkage() &&
183              "Refusing to delete an externally visible global variable.");
184       Replacements[i].first->eraseFromParent();
185     }
186 
187     NumMerged += Replacements.size();
188     Replacements.clear();
189   }
190 }
191