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
33STATISTIC(NumPooledStrings, "Number of Strings Pooled");
34
35using namespace llvm;
36
37static 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
41static 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
46namespace {
47struct {
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
84class PPCMergeStringPool : public ModulePass {
85public:
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
101private:
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.
118static 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.
143void 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
221bool 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
293static 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.
303void 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
370char PPCMergeStringPool::ID = 0;
371
372INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
373 false)
374
375ModulePass *llvm::createPPCMergeStringPoolPass() {
376 return new PPCMergeStringPool();
377}
378

source code of llvm/lib/Target/PowerPC/PPCMergeStringPool.cpp