Mercurial > hg > CbC > CbC_llvm

comparison lib/Transforms/IPO/ConstantMerge.cpp @ 148:63bd29f05246

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 19:46:37 +0900
parents c2174574ed3a
children
comparison
equal deleted inserted replaced
146:3fc4d5c3e21e 148:63bd29f05246
1 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// 1 //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 // 8 //
10 // This file defines the interface to a pass that merges duplicate global 9 // 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 10 // constants together into a single constant that is shared. This is useful
38 37
39 using namespace llvm; 38 using namespace llvm;
40 39
41 #define DEBUG_TYPE "constmerge" 40 #define DEBUG_TYPE "constmerge"
42 41
43 STATISTIC(NumMerged, "Number of global constants merged"); 42 STATISTIC(NumIdenticalMerged, "Number of identical global constants merged");
44 43
45 /// Find values that are marked as llvm.used. 44 /// Find values that are marked as llvm.used.
46 static void FindUsedValues(GlobalVariable *LLVMUsed, 45 static void FindUsedValues(GlobalVariable *LLVMUsed,
47 SmallPtrSetImpl<const GlobalValue*> &UsedValues) { 46 SmallPtrSetImpl<const GlobalValue*> &UsedValues) {
48 if (!LLVMUsed) return; 47 if (!LLVMUsed) return;
89 if (Align) 88 if (Align)
90 return Align; 89 return Align;
91 return GV->getParent()->getDataLayout().getPreferredAlignment(GV); 90 return GV->getParent()->getDataLayout().getPreferredAlignment(GV);
92 } 91 }
93 92
93 static bool
94 isUnmergeableGlobal(GlobalVariable *GV,
95 const SmallPtrSetImpl<const GlobalValue *> &UsedGlobals) {
96 // Only process constants with initializers in the default address space.
97 return !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
98 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
99 // Don't touch values marked with attribute(used).
100 UsedGlobals.count(GV);
101 }
102
103 enum class CanMerge { No, Yes };
104 static CanMerge makeMergeable(GlobalVariable *Old, GlobalVariable *New) {
105 if (!Old->hasGlobalUnnamedAddr() && !New->hasGlobalUnnamedAddr())
106 return CanMerge::No;
107 if (hasMetadataOtherThanDebugLoc(Old))
108 return CanMerge::No;
109 assert(!hasMetadataOtherThanDebugLoc(New));
110 if (!Old->hasGlobalUnnamedAddr())
111 New->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
112 return CanMerge::Yes;
113 }
114
115 static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New) {
116 Constant *NewConstant = New;
117
118 LLVM_DEBUG(dbgs() << "Replacing global: @" << Old->getName() << " -> @"
119 << New->getName() << "\n");
120
121 // Bump the alignment if necessary.
122 if (Old->getAlignment() || New->getAlignment())
123 New->setAlignment(std::max(getAlignment(Old), getAlignment(New)));
124
125 copyDebugLocMetadata(Old, New);
126 Old->replaceAllUsesWith(NewConstant);
127
128 // Delete the global value from the module.
129 assert(Old->hasLocalLinkage() &&
130 "Refusing to delete an externally visible global variable.");
131 Old->eraseFromParent();
132 }
133
94 static bool mergeConstants(Module &M) { 134 static bool mergeConstants(Module &M) {
95 // Find all the globals that are marked "used". These cannot be merged. 135 // Find all the globals that are marked "used". These cannot be merged.
96 SmallPtrSet<const GlobalValue*, 8> UsedGlobals; 136 SmallPtrSet<const GlobalValue*, 8> UsedGlobals;
97 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals); 137 FindUsedValues(M.getGlobalVariable("llvm.used"), UsedGlobals);
98 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals); 138 FindUsedValues(M.getGlobalVariable("llvm.compiler.used"), UsedGlobals);
99 139
100 // Map unique constants to globals. 140 // Map unique constants to globals.
101 DenseMap<Constant *, GlobalVariable *> CMap; 141 DenseMap<Constant *, GlobalVariable *> CMap;
102 142
103 // Replacements - This vector contains a list of replacements to perform. 143 SmallVector<std::pair<GlobalVariable *, GlobalVariable *>, 32>
104 SmallVector<std::pair<GlobalVariable*, GlobalVariable*>, 32> Replacements; 144 SameContentReplacements;
105 145
106 bool MadeChange = false; 146 size_t ChangesMade = 0;
147 size_t OldChangesMade = 0;
107 148
108 // Iterate constant merging while we are still making progress. Merging two 149 // Iterate constant merging while we are still making progress. Merging two
109 // constants together may allow us to merge other constants together if the 150 // constants together may allow us to merge other constants together if the
110 // second level constants have initializers which point to the globals that 151 // second level constants have initializers which point to the globals that
111 // were just merged. 152 // were just merged.
112 while (true) { 153 while (true) {
113 // First: Find the canonical constants others will be merged with. 154 // Find the canonical constants others will be merged with.
114 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 155 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
115 GVI != E; ) { 156 GVI != E; ) {
116 GlobalVariable *GV = &*GVI++; 157 GlobalVariable *GV = &*GVI++;
117 158
118 // If this GV is dead, remove it. 159 // If this GV is dead, remove it.
119 GV->removeDeadConstantUsers(); 160 GV->removeDeadConstantUsers();
120 if (GV->use_empty() && GV->hasLocalLinkage()) { 161 if (GV->use_empty() && GV->hasLocalLinkage()) {
121 GV->eraseFromParent(); 162 GV->eraseFromParent();
163 ++ChangesMade;
122 continue; 164 continue;
123 } 165 }
124 166
125 // Only process constants with initializers in the default address space. 167 if (isUnmergeableGlobal(GV, UsedGlobals))
126 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
127 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
128 // Don't touch values marked with attribute(used).
129 UsedGlobals.count(GV))
130 continue; 168 continue;
131 169
132 // This transformation is legal for weak ODR globals in the sense it 170 // This transformation is legal for weak ODR globals in the sense it
133 // doesn't change semantics, but we really don't want to perform it 171 // doesn't change semantics, but we really don't want to perform it
134 // anyway; it's likely to pessimize code generation, and some tools 172 // anyway; it's likely to pessimize code generation, and some tools
146 GlobalVariable *&Slot = CMap[Init]; 184 GlobalVariable *&Slot = CMap[Init];
147 185
148 // If this is the first constant we find or if the old one is local, 186 // If this is the first constant we find or if the old one is local,
149 // replace with the current one. If the current is externally visible 187 // replace with the current one. If the current is externally visible
150 // it cannot be replace, but can be the canonical constant we merge with. 188 // it cannot be replace, but can be the canonical constant we merge with.
151 if (!Slot || IsBetterCanonical(*GV, *Slot)) 189 bool FirstConstantFound = !Slot;
190 if (FirstConstantFound || IsBetterCanonical(*GV, *Slot)) {
152 Slot = GV; 191 Slot = GV;
192 LLVM_DEBUG(dbgs() << "Cmap[" << *Init << "] = " << GV->getName()
193 << (FirstConstantFound ? "\n" : " (updated)\n"));
194 }
153 } 195 }
154 196
155 // Second: identify all globals that can be merged together, filling in 197 // Identify all globals that can be merged together, filling in the
156 // the Replacements vector. We cannot do the replacement in this pass 198 // SameContentReplacements vector. We cannot do the replacement in this pass
157 // because doing so may cause initializers of other globals to be rewritten, 199 // because doing so may cause initializers of other globals to be rewritten,
158 // invalidating the Constant* pointers in CMap. 200 // invalidating the Constant* pointers in CMap.
159 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 201 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
160 GVI != E; ) { 202 GVI != E; ) {
161 GlobalVariable *GV = &*GVI++; 203 GlobalVariable *GV = &*GVI++;
162 204
163 // Only process constants with initializers in the default address space. 205 if (isUnmergeableGlobal(GV, UsedGlobals))
164 if (!GV->isConstant() || !GV->hasDefinitiveInitializer() ||
165 GV->getType()->getAddressSpace() != 0 || GV->hasSection() ||
166 // Don't touch values marked with attribute(used).
167 UsedGlobals.count(GV))
168 continue; 206 continue;
169 207
170 // We can only replace constant with local linkage. 208 // We can only replace constant with local linkage.
171 if (!GV->hasLocalLinkage()) 209 if (!GV->hasLocalLinkage())
172 continue; 210 continue;
173 211
174 Constant *Init = GV->getInitializer(); 212 Constant *Init = GV->getInitializer();
175 213
176 // Check to see if the initializer is already known. 214 // Check to see if the initializer is already known.
177 GlobalVariable *Slot = CMap[Init]; 215 auto Found = CMap.find(Init);
178 216 if (Found == CMap.end())
179 if (!Slot || Slot == GV) 217 continue;
180 continue; 218
181 219 GlobalVariable *Slot = Found->second;
182 if (!Slot->hasGlobalUnnamedAddr() && !GV->hasGlobalUnnamedAddr()) 220 if (Slot == GV)
183 continue; 221 continue;
184 222
185 if (hasMetadataOtherThanDebugLoc(GV)) 223 if (makeMergeable(GV, Slot) == CanMerge::No)
186 continue; 224 continue;
187
188 if (!GV->hasGlobalUnnamedAddr())
189 Slot->setUnnamedAddr(GlobalValue::UnnamedAddr::None);
190 225
191 // Make all uses of the duplicate constant use the canonical version. 226 // Make all uses of the duplicate constant use the canonical version.
192 Replacements.push_back(std::make_pair(GV, Slot)); 227 LLVM_DEBUG(dbgs() << "Will replace: @" << GV->getName() << " -> @"
228 << Slot->getName() << "\n");
229 SameContentReplacements.push_back(std::make_pair(GV, Slot));
193 } 230 }
194
195 if (Replacements.empty())
196 return MadeChange;
197 CMap.clear();
198 231
199 // Now that we have figured out which replacements must be made, do them all 232 // Now that we have figured out which replacements must be made, do them all
200 // now. This avoid invalidating the pointers in CMap, which are unneeded 233 // now. This avoid invalidating the pointers in CMap, which are unneeded
201 // now. 234 // now.
202 for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { 235 for (unsigned i = 0, e = SameContentReplacements.size(); i != e; ++i) {
203 // Bump the alignment if necessary. 236 GlobalVariable *Old = SameContentReplacements[i].first;
204 if (Replacements[i].first->getAlignment() || 237 GlobalVariable *New = SameContentReplacements[i].second;
205 Replacements[i].second->getAlignment()) { 238 replace(M, Old, New);
206 Replacements[i].second->setAlignment( 239 ++ChangesMade;
207 std::max(getAlignment(Replacements[i].first), 240 ++NumIdenticalMerged;
208 getAlignment(Replacements[i].second)));
209 }
210
211 copyDebugLocMetadata(Replacements[i].first, Replacements[i].second);
212
213 // Eliminate any uses of the dead global.
214 Replacements[i].first->replaceAllUsesWith(Replacements[i].second);
215
216 // Delete the global value from the module.
217 assert(Replacements[i].first->hasLocalLinkage() &&
218 "Refusing to delete an externally visible global variable.");
219 Replacements[i].first->eraseFromParent();
220 } 241 }
221 242
222 NumMerged += Replacements.size(); 243 if (ChangesMade == OldChangesMade)
223 Replacements.clear(); 244 break;
224 } 245 OldChangesMade = ChangesMade;
246
247 SameContentReplacements.clear();
248 CMap.clear();
249 }
250
251 return ChangesMade;
225 } 252 }
226 253
227 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) { 254 PreservedAnalyses ConstantMergePass::run(Module &M, ModuleAnalysisManager &) {
228 if (!mergeConstants(M)) 255 if (!mergeConstants(M))
229 return PreservedAnalyses::all(); 256 return PreservedAnalyses::all();