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