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
34 STATISTIC(NumPooledStrings, "Number of Strings Pooled");
35
36 using namespace llvm;
37
38 static cl::opt<unsigned>
39 MaxStringsPooled("ppc-max-strings-pooled", cl::Hidden, cl::init(-1),
40 cl::desc("Maximum Number of Strings to Pool."));
41
42 static cl::opt<unsigned>
43 MinStringsBeforePool("ppc-min-strings-before-pool", cl::Hidden, cl::init(2),
44 cl::desc("Minimum number of string candidates before "
45 "pooling is considered."));
46
47 namespace {
48 struct {
operator ()__anon9fd8c7390111::__anon9fd8c739020849 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>(ConstLHS);
71 unsigned LHSSize =
72 ConstDataLHS->getNumElements() * ConstDataLHS->getElementByteSize();
73 const Constant *ConstRHS = RHS->getInitializer();
74 const ConstantDataSequential *ConstDataRHS =
75 dyn_cast<ConstantDataSequential>(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
85 class PPCMergeStringPool : public ModulePass {
86 public:
87 static char ID;
PPCMergeStringPool()88 PPCMergeStringPool() : ModulePass(ID) {}
89
doInitialization(Module & M)90 bool doInitialization(Module &M) override { return mergeModuleStringPool(M); }
runOnModule(Module & M)91 bool runOnModule(Module &M) override { return false; }
92
getPassName() const93 StringRef getPassName() const override { return "PPC Merge String Pool"; }
94
getAnalysisUsage(AnalysisUsage & AU) const95 void getAnalysisUsage(AnalysisUsage &AU) const override {
96 AU.addPreserved<DominatorTreeWrapperPass>();
97 AU.addPreserved<LoopInfoWrapperPass>();
98 AU.addPreserved<ScalarEvolutionWrapperPass>();
99 AU.addPreserved<SCEVAAWrapperPass>();
100 }
101
102 private:
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.
hasReplaceableUsers(GlobalVariable & GV)119 static bool hasReplaceableUsers(GlobalVariable &GV) {
120 for (User *CurrentUser : GV.users()) {
121 if (auto *I = dyn_cast<Instruction>(CurrentUser)) {
122 // Do not merge globals in exception pads.
123 if (I->isEHPad())
124 return false;
125
126 if (auto *II = dyn_cast<IntrinsicInst>(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>(CurrentUser))
142 return false;
143
144 // We only support Instruction and Constant users.
145 if (!isa<Constant>(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.
collectCandidateConstants(Module & M)155 void PPCMergeStringPool::collectCandidateConstants(Module &M) {
156 SmallVector<GlobalValue *, 4> UsedV;
157 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false);
158 SmallVector<GlobalValue *, 4> UsedVCompiler;
159 collectUsedGlobalVariables(M, 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(UsedV.begin(), UsedV.end());
164 AllUsedGlobals.insert(UsedVCompiler.begin(), 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 non-thread-local constants.
174 if (!Global.isConstant() || !Global.hasInitializer() ||
175 Global.isThreadLocal())
176 continue;
177
178 // If a global constant has a section we do not try to pool it because
179 // there is no guarantee that other constants will also be in the same
180 // section. Trying to pool constants from different sections (or no
181 // section) means that the pool has to be in multiple sections at the same
182 // time.
183 if (Global.hasSection())
184 continue;
185
186 // Do not pool constants with metadata because we should not add metadata
187 // to the pool when that metadata refers to a single constant in the pool.
188 if (Global.hasMetadata())
189 continue;
190
191 ConstantDataSequential *ConstData =
192 dyn_cast<ConstantDataSequential>(Global.getInitializer());
193
194 // If the constant is undef then ConstData will be null.
195 if (!ConstData)
196 continue;
197
198 // Do not pool globals that are part of llvm.used or llvm.compiler.end.
199 if (AllUsedGlobals.contains(&Global))
200 continue;
201
202 if (!hasReplaceableUsers(Global))
203 continue;
204
205 Align AlignOfGlobal = Global.getAlign().valueOrOne();
206
207 // TODO: At this point do not allow over-aligned types. Adding a type
208 // with larger alignment may lose the larger alignment once it is
209 // added to the struct.
210 // Fix this in a future patch.
211 if (AlignOfGlobal.value() > ConstData->getElementByteSize())
212 continue;
213
214 // Make sure that the global is only visible inside the compilation unit.
215 if (Global.getLinkage() != GlobalValue::PrivateLinkage &&
216 Global.getLinkage() != GlobalValue::InternalLinkage)
217 continue;
218
219 LLVM_DEBUG(dbgs() << "Constant data of Global: ");
220 LLVM_DEBUG(ConstData->dump());
221 LLVM_DEBUG(dbgs() << "\n\n");
222
223 MergeableStrings.push_back(&Global);
224 if (MaxAlignment < AlignOfGlobal)
225 MaxAlignment = AlignOfGlobal;
226
227 // If we have already reached the maximum number of pooled strings then
228 // there is no point in looking for more.
229 if (MergeableStrings.size() >= MaxStringsPooled)
230 break;
231 }
232 }
233
mergeModuleStringPool(Module & M)234 bool PPCMergeStringPool::mergeModuleStringPool(Module &M) {
235
236 LLVM_DEBUG(dbgs() << "Merging string pool for module: " << M.getName()
237 << "\n");
238 LLVM_DEBUG(dbgs() << "Number of globals is: " << M.global_size() << "\n");
239
240 collectCandidateConstants(M);
241
242 // If we have too few constants in the module that are merge candidates we
243 // will skip doing the merging.
244 if (MergeableStrings.size() < MinStringsBeforePool)
245 return false;
246
247 // Sort the global constants to make access more efficient.
248 std::sort(MergeableStrings.begin(), MergeableStrings.end(), CompareConstants);
249
250 SmallVector<Constant *> ConstantsInStruct;
251 for (GlobalVariable *GV : MergeableStrings)
252 ConstantsInStruct.push_back(GV->getInitializer());
253
254 // Use an anonymous struct to pool the strings.
255 // TODO: This pass uses a single anonymous struct for all of the pooled
256 // entries. This may cause a performance issue in the situation where
257 // computing the offset requires two instructions (addis, addi). For the
258 // future we may want to split this into multiple structs.
259 Constant *ConstantPool = ConstantStruct::getAnon(ConstantsInStruct);
260 PooledStructType = ConstantPool->getType();
261
262 // The GlobalVariable constructor calls
263 // MM->insertGlobalVariable(PooledGlobal).
264 GlobalVariable *PooledGlobal =
265 new GlobalVariable(M, PooledStructType,
266 /* isConstant */ true, GlobalValue::PrivateLinkage,
267 ConstantPool, "__ModuleStringPool");
268 PooledGlobal->setAlignment(MaxAlignment);
269
270 LLVM_DEBUG(dbgs() << "Constructing global variable for string pool: ");
271 LLVM_DEBUG(PooledGlobal->dump());
272
273 Context = &M.getContext();
274 size_t ElementIndex = 0;
275 for (GlobalVariable *GV : MergeableStrings) {
276
277 LLVM_DEBUG(dbgs() << "The global:\n");
278 LLVM_DEBUG(GV->dump());
279 LLVM_DEBUG(dbgs() << "Has " << GV->getNumUses() << " uses.\n");
280
281 // Access to the pooled constant strings require an offset. Add a GEP
282 // before every use in order to compute this offset.
283 replaceUsesWithGEP(GV, PooledGlobal, ElementIndex);
284
285 // Replace all the uses by metadata.
286 if (GV->isUsedByMetadata()) {
287 Constant *Indices[2] = {
288 ConstantInt::get(Type::getInt32Ty(*Context), 0),
289 ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex)};
290 Constant *ConstGEP = ConstantExpr::getInBoundsGetElementPtr(
291 PooledStructType, PooledGlobal, Indices);
292 ValueAsMetadata::handleRAUW(GV, ConstGEP);
293 }
294 assert(!GV->isUsedByMetadata() && "Should be no metadata use anymore");
295
296 // This GV has no more uses so we can erase it.
297 if (GV->use_empty())
298 GV->eraseFromParent();
299
300 NumPooledStrings++;
301 ElementIndex++;
302 }
303 return true;
304 }
305
306 // For pooled strings we need to add the offset into the pool for each string.
307 // This is done by adding a Get Element Pointer (GEP) before each user. This
308 // function adds the GEP.
replaceUsesWithGEP(GlobalVariable * GlobalToReplace,GlobalVariable * GPool,unsigned ElementIndex)309 void PPCMergeStringPool::replaceUsesWithGEP(GlobalVariable *GlobalToReplace,
310 GlobalVariable *GPool,
311 unsigned ElementIndex) {
312 SmallVector<Value *, 2> Indices;
313 Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), 0));
314 Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex));
315
316 Constant *ConstGEP =
317 ConstantExpr::getInBoundsGetElementPtr(PooledStructType, GPool, Indices);
318 LLVM_DEBUG(dbgs() << "Replacing this global:\n");
319 LLVM_DEBUG(GlobalToReplace->dump());
320 LLVM_DEBUG(dbgs() << "with this:\n");
321 LLVM_DEBUG(ConstGEP->dump());
322 GlobalToReplace->replaceAllUsesWith(ConstGEP);
323 }
324
325 } // namespace
326
327 char PPCMergeStringPool::ID = 0;
328
329 INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
330 false)
331
createPPCMergeStringPoolPass()332 ModulePass *llvm::createPPCMergeStringPoolPass() {
333 return new PPCMergeStringPool();
334 }
335