1 | //===-- PPCMergeStringPool.cpp -------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This transformation tries to merge the strings in the module into one pool |
10 | // of strings. The idea is to reduce the number of TOC entries in the module so |
11 | // that instead of having one TOC entry for each string there is only one global |
12 | // TOC entry and all of the strings are referenced off of that one entry plus |
13 | // an offset. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #include "PPC.h" |
18 | #include "llvm/ADT/Statistic.h" |
19 | #include "llvm/Analysis/DomTreeUpdater.h" |
20 | #include "llvm/Analysis/LoopInfo.h" |
21 | #include "llvm/Analysis/LoopIterator.h" |
22 | #include "llvm/Analysis/ScalarEvolution.h" |
23 | #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" |
24 | #include "llvm/IR/Constants.h" |
25 | #include "llvm/IR/Instructions.h" |
26 | #include "llvm/IR/Module.h" |
27 | #include "llvm/IR/ValueSymbolTable.h" |
28 | #include "llvm/Pass.h" |
29 | #include "llvm/Support/CommandLine.h" |
30 | |
31 | #define DEBUG_TYPE "ppc-merge-strings" |
32 | |
33 | STATISTIC(NumPooledStrings, "Number of Strings Pooled" ); |
34 | |
35 | using namespace llvm; |
36 | |
37 | static cl::opt<unsigned> |
38 | MaxStringsPooled("ppc-max-strings-pooled" , cl::Hidden, cl::init(Val: -1), |
39 | cl::desc("Maximum Number of Strings to Pool." )); |
40 | |
41 | static cl::opt<unsigned> |
42 | MinStringsBeforePool("ppc-min-strings-before-pool" , cl::Hidden, cl::init(Val: 2), |
43 | cl::desc("Minimum number of string candidates before " |
44 | "pooling is considered." )); |
45 | |
46 | namespace { |
47 | struct { |
48 | bool operator()(const GlobalVariable *LHS, const GlobalVariable *RHS) const { |
49 | // First priority is alignment. |
50 | // If elements are sorted in terms of alignment then there won't be an |
51 | // issue with incorrect alignment that would require padding. |
52 | Align LHSAlign = LHS->getAlign().valueOrOne(); |
53 | Align RHSAlign = RHS->getAlign().valueOrOne(); |
54 | if (LHSAlign > RHSAlign) |
55 | return true; |
56 | else if (LHSAlign < RHSAlign) |
57 | return false; |
58 | |
59 | // Next priority is the number of uses. |
60 | // Smaller offsets are easier to materialize because materializing a large |
61 | // offset may require more than one instruction. (ie addis, addi). |
62 | if (LHS->getNumUses() > RHS->getNumUses()) |
63 | return true; |
64 | else if (LHS->getNumUses() < RHS->getNumUses()) |
65 | return false; |
66 | |
67 | const Constant *ConstLHS = LHS->getInitializer(); |
68 | const ConstantDataSequential *ConstDataLHS = |
69 | dyn_cast<ConstantDataSequential>(Val: ConstLHS); |
70 | unsigned LHSSize = |
71 | ConstDataLHS->getNumElements() * ConstDataLHS->getElementByteSize(); |
72 | const Constant *ConstRHS = RHS->getInitializer(); |
73 | const ConstantDataSequential *ConstDataRHS = |
74 | dyn_cast<ConstantDataSequential>(Val: ConstRHS); |
75 | unsigned RHSSize = |
76 | ConstDataRHS->getNumElements() * ConstDataRHS->getElementByteSize(); |
77 | |
78 | // Finally smaller constants should go first. This is, again, trying to |
79 | // minimize the offsets into the final struct. |
80 | return LHSSize < RHSSize; |
81 | } |
82 | } CompareConstants; |
83 | |
84 | class PPCMergeStringPool : public ModulePass { |
85 | public: |
86 | static char ID; |
87 | PPCMergeStringPool() : ModulePass(ID) {} |
88 | |
89 | bool doInitialization(Module &M) override { return mergeModuleStringPool(M); } |
90 | bool runOnModule(Module &M) override { return false; } |
91 | |
92 | StringRef getPassName() const override { return "PPC Merge String Pool" ; } |
93 | |
94 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
95 | AU.addPreserved<DominatorTreeWrapperPass>(); |
96 | AU.addPreserved<LoopInfoWrapperPass>(); |
97 | AU.addPreserved<ScalarEvolutionWrapperPass>(); |
98 | AU.addPreserved<SCEVAAWrapperPass>(); |
99 | } |
100 | |
101 | private: |
102 | // Globals in a Module are already unique so a set is not required and a |
103 | // vector will do. |
104 | std::vector<GlobalVariable *> MergeableStrings; |
105 | Align MaxAlignment; |
106 | Type *PooledStructType; |
107 | LLVMContext *Context; |
108 | void collectCandidateConstants(Module &M); |
109 | bool mergeModuleStringPool(Module &M); |
110 | void replaceUsesWithGEP(GlobalVariable *GlobalToReplace, GlobalVariable *GPool, |
111 | unsigned ElementIndex); |
112 | }; |
113 | |
114 | |
115 | // In order for a constant to be pooled we need to be able to replace all of |
116 | // the uses for that constant. This function checks all of the uses to make |
117 | // sure that they can be replaced. |
118 | static bool hasReplaceableUsers(GlobalVariable &GV) { |
119 | for (User *CurrentUser : GV.users()) { |
120 | // Instruction users are always valid. |
121 | if (isa<Instruction>(Val: CurrentUser)) |
122 | continue; |
123 | |
124 | // We cannot replace GlobalValue users because they are not just nodes |
125 | // in IR. To replace a user like this we would need to create a new |
126 | // GlobalValue with the replacement and then try to delete the original |
127 | // GlobalValue. Deleting the original would only happen if it has no other |
128 | // uses. |
129 | if (isa<GlobalValue>(Val: CurrentUser)) |
130 | return false; |
131 | |
132 | // We only support Instruction and Constant users. |
133 | if (!isa<Constant>(Val: CurrentUser)) |
134 | return false; |
135 | } |
136 | |
137 | return true; |
138 | } |
139 | |
140 | // Run through all of the constants in the module and determine if they are |
141 | // valid candidates to be merged into the string pool. Valid candidates will |
142 | // be added to MergeableStrings. |
143 | void PPCMergeStringPool::collectCandidateConstants(Module &M) { |
144 | SmallVector<GlobalValue *, 4> UsedV; |
145 | collectUsedGlobalVariables(M, Vec&: UsedV, /*CompilerUsed=*/false); |
146 | SmallVector<GlobalValue *, 4> UsedVCompiler; |
147 | collectUsedGlobalVariables(M, Vec&: UsedVCompiler, /*CompilerUsed=*/true); |
148 | // Combine all of the Global Variables marked as used into a SmallPtrSet for |
149 | // faster lookup inside the loop. |
150 | SmallPtrSet<GlobalValue *, 8> AllUsedGlobals; |
151 | AllUsedGlobals.insert(I: UsedV.begin(), E: UsedV.end()); |
152 | AllUsedGlobals.insert(I: UsedVCompiler.begin(), E: UsedVCompiler.end()); |
153 | |
154 | for (GlobalVariable &Global : M.globals()) { |
155 | LLVM_DEBUG(dbgs() << "Looking at global:" ); |
156 | LLVM_DEBUG(Global.dump()); |
157 | LLVM_DEBUG(dbgs() << "isConstant() " << Global.isConstant() << "\n" ); |
158 | LLVM_DEBUG(dbgs() << "hasInitializer() " << Global.hasInitializer() |
159 | << "\n" ); |
160 | |
161 | // We can only pool constants. |
162 | if (!Global.isConstant() || !Global.hasInitializer()) |
163 | continue; |
164 | |
165 | // If a global constant has a section we do not try to pool it because |
166 | // there is no guarantee that other constants will also be in the same |
167 | // section. Trying to pool constants from different sections (or no |
168 | // section) means that the pool has to be in multiple sections at the same |
169 | // time. |
170 | if (Global.hasSection()) |
171 | continue; |
172 | |
173 | // Do not pool constants with metadata because we should not add metadata |
174 | // to the pool when that metadata refers to a single constant in the pool. |
175 | if (Global.hasMetadata()) |
176 | continue; |
177 | |
178 | ConstantDataSequential *ConstData = |
179 | dyn_cast<ConstantDataSequential>(Val: Global.getInitializer()); |
180 | |
181 | // If the constant is undef then ConstData will be null. |
182 | if (!ConstData) |
183 | continue; |
184 | |
185 | // Do not pool globals that are part of llvm.used or llvm.compiler.end. |
186 | if (AllUsedGlobals.contains(Ptr: &Global)) |
187 | continue; |
188 | |
189 | if (!hasReplaceableUsers(GV&: Global)) |
190 | continue; |
191 | |
192 | Align AlignOfGlobal = Global.getAlign().valueOrOne(); |
193 | |
194 | // TODO: At this point do not allow over-aligned types. Adding a type |
195 | // with larger alignment may lose the larger alignment once it is |
196 | // added to the struct. |
197 | // Fix this in a future patch. |
198 | if (AlignOfGlobal.value() > ConstData->getElementByteSize()) |
199 | continue; |
200 | |
201 | // Make sure that the global is only visible inside the compilation unit. |
202 | if (Global.getLinkage() != GlobalValue::PrivateLinkage && |
203 | Global.getLinkage() != GlobalValue::InternalLinkage) |
204 | continue; |
205 | |
206 | LLVM_DEBUG(dbgs() << "Constant data of Global: " ); |
207 | LLVM_DEBUG(ConstData->dump()); |
208 | LLVM_DEBUG(dbgs() << "\n\n" ); |
209 | |
210 | MergeableStrings.push_back(x: &Global); |
211 | if (MaxAlignment < AlignOfGlobal) |
212 | MaxAlignment = AlignOfGlobal; |
213 | |
214 | // If we have already reached the maximum number of pooled strings then |
215 | // there is no point in looking for more. |
216 | if (MergeableStrings.size() >= MaxStringsPooled) |
217 | break; |
218 | } |
219 | } |
220 | |
221 | bool PPCMergeStringPool::mergeModuleStringPool(Module &M) { |
222 | |
223 | LLVM_DEBUG(dbgs() << "Merging string pool for module: " << M.getName() |
224 | << "\n" ); |
225 | LLVM_DEBUG(dbgs() << "Number of globals is: " << M.global_size() << "\n" ); |
226 | |
227 | collectCandidateConstants(M); |
228 | |
229 | // If we have too few constants in the module that are merge candidates we |
230 | // will skip doing the merging. |
231 | if (MergeableStrings.size() < MinStringsBeforePool) |
232 | return false; |
233 | |
234 | // Sort the global constants to make access more efficient. |
235 | std::sort(first: MergeableStrings.begin(), last: MergeableStrings.end(), comp: CompareConstants); |
236 | |
237 | SmallVector<Constant *> ConstantsInStruct; |
238 | for (GlobalVariable *GV : MergeableStrings) |
239 | ConstantsInStruct.push_back(Elt: GV->getInitializer()); |
240 | |
241 | // Use an anonymous struct to pool the strings. |
242 | // TODO: This pass uses a single anonymous struct for all of the pooled |
243 | // entries. This may cause a performance issue in the situation where |
244 | // computing the offset requires two instructions (addis, addi). For the |
245 | // future we may want to split this into multiple structs. |
246 | Constant *ConstantPool = ConstantStruct::getAnon(V: ConstantsInStruct); |
247 | PooledStructType = ConstantPool->getType(); |
248 | |
249 | // The GlobalVariable constructor calls |
250 | // MM->insertGlobalVariable(PooledGlobal). |
251 | GlobalVariable *PooledGlobal = |
252 | new GlobalVariable(M, PooledStructType, |
253 | /* isConstant */ true, GlobalValue::PrivateLinkage, |
254 | ConstantPool, "__ModuleStringPool" ); |
255 | PooledGlobal->setAlignment(MaxAlignment); |
256 | |
257 | LLVM_DEBUG(dbgs() << "Constructing global variable for string pool: " ); |
258 | LLVM_DEBUG(PooledGlobal->dump()); |
259 | |
260 | Context = &M.getContext(); |
261 | size_t ElementIndex = 0; |
262 | for (GlobalVariable *GV : MergeableStrings) { |
263 | |
264 | LLVM_DEBUG(dbgs() << "The global:\n" ); |
265 | LLVM_DEBUG(GV->dump()); |
266 | LLVM_DEBUG(dbgs() << "Has " << GV->getNumUses() << " uses.\n" ); |
267 | |
268 | // Access to the pooled constant strings require an offset. Add a GEP |
269 | // before every use in order to compute this offset. |
270 | replaceUsesWithGEP(GlobalToReplace: GV, GPool: PooledGlobal, ElementIndex); |
271 | |
272 | // Replace all the uses by metadata. |
273 | if (GV->isUsedByMetadata()) { |
274 | Constant *Indices[2] = { |
275 | ConstantInt::get(Ty: Type::getInt32Ty(C&: *Context), V: 0), |
276 | ConstantInt::get(Ty: Type::getInt32Ty(C&: *Context), V: ElementIndex)}; |
277 | Constant *ConstGEP = ConstantExpr::getInBoundsGetElementPtr( |
278 | Ty: PooledStructType, C: PooledGlobal, IdxList: Indices); |
279 | ValueAsMetadata::handleRAUW(From: GV, To: ConstGEP); |
280 | } |
281 | assert(!GV->isUsedByMetadata() && "Should be no metadata use anymore" ); |
282 | |
283 | // This GV has no more uses so we can erase it. |
284 | if (GV->use_empty()) |
285 | GV->eraseFromParent(); |
286 | |
287 | NumPooledStrings++; |
288 | ElementIndex++; |
289 | } |
290 | return true; |
291 | } |
292 | |
293 | static bool userHasOperand(User *TheUser, GlobalVariable *GVOperand) { |
294 | for (Value *Op : TheUser->operands()) |
295 | if (Op == GVOperand) |
296 | return true; |
297 | return false; |
298 | } |
299 | |
300 | // For pooled strings we need to add the offset into the pool for each string. |
301 | // This is done by adding a Get Element Pointer (GEP) before each user. This |
302 | // function adds the GEP. |
303 | void PPCMergeStringPool::replaceUsesWithGEP(GlobalVariable *GlobalToReplace, |
304 | GlobalVariable *GPool, |
305 | unsigned ElementIndex) { |
306 | SmallVector<Value *, 2> Indices; |
307 | Indices.push_back(Elt: ConstantInt::get(Ty: Type::getInt32Ty(C&: *Context), V: 0)); |
308 | Indices.push_back(Elt: ConstantInt::get(Ty: Type::getInt32Ty(C&: *Context), V: ElementIndex)); |
309 | |
310 | // Need to save a temporary copy of each user list because we remove uses |
311 | // as we replace them. |
312 | SmallVector<User *> Users; |
313 | for (User *CurrentUser : GlobalToReplace->users()) |
314 | Users.push_back(Elt: CurrentUser); |
315 | |
316 | for (User *CurrentUser : Users) { |
317 | Instruction *UserInstruction = dyn_cast<Instruction>(Val: CurrentUser); |
318 | Constant *UserConstant = dyn_cast<Constant>(Val: CurrentUser); |
319 | |
320 | // At this point we expect that the user is either an instruction or a |
321 | // constant. |
322 | assert((UserConstant || UserInstruction) && |
323 | "Expected the user to be an instruction or a constant." ); |
324 | |
325 | // The user was not found so it must have been replaced earlier. |
326 | if (!userHasOperand(TheUser: CurrentUser, GVOperand: GlobalToReplace)) |
327 | continue; |
328 | |
329 | // We cannot replace operands in globals so we ignore those. |
330 | if (isa<GlobalValue>(Val: CurrentUser)) |
331 | continue; |
332 | |
333 | if (!UserInstruction) { |
334 | // User is a constant type. |
335 | Constant *ConstGEP = ConstantExpr::getInBoundsGetElementPtr( |
336 | Ty: PooledStructType, C: GPool, IdxList: Indices); |
337 | UserConstant->handleOperandChange(GlobalToReplace, ConstGEP); |
338 | continue; |
339 | } |
340 | |
341 | if (PHINode *UserPHI = dyn_cast<PHINode>(Val: UserInstruction)) { |
342 | // GEP instructions cannot be added before PHI nodes. |
343 | // With getInBoundsGetElementPtr we create the GEP and then replace it |
344 | // inline into the PHI. |
345 | Constant *ConstGEP = ConstantExpr::getInBoundsGetElementPtr( |
346 | Ty: PooledStructType, C: GPool, IdxList: Indices); |
347 | UserPHI->replaceUsesOfWith(From: GlobalToReplace, To: ConstGEP); |
348 | continue; |
349 | } |
350 | // The user is a valid instruction that is not a PHINode. |
351 | GetElementPtrInst *GEPInst = |
352 | GetElementPtrInst::Create(PointeeType: PooledStructType, Ptr: GPool, IdxList: Indices); |
353 | GEPInst->insertBefore(InsertPos: UserInstruction); |
354 | |
355 | LLVM_DEBUG(dbgs() << "Inserting GEP before:\n" ); |
356 | LLVM_DEBUG(UserInstruction->dump()); |
357 | |
358 | LLVM_DEBUG(dbgs() << "Replacing this global:\n" ); |
359 | LLVM_DEBUG(GlobalToReplace->dump()); |
360 | LLVM_DEBUG(dbgs() << "with this:\n" ); |
361 | LLVM_DEBUG(GEPInst->dump()); |
362 | |
363 | // After the GEP is inserted the GV can be replaced. |
364 | CurrentUser->replaceUsesOfWith(From: GlobalToReplace, To: GEPInst); |
365 | } |
366 | } |
367 | |
368 | } // namespace |
369 | |
370 | char PPCMergeStringPool::ID = 0; |
371 | |
372 | INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool" , false, |
373 | false) |
374 | |
375 | ModulePass *llvm::createPPCMergeStringPoolPass() { |
376 | return new PPCMergeStringPool(); |
377 | } |
378 | |