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 ()__anonf0e1b5010111::__anonf0e1b501020849 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
runOnModule(Module & M)90 bool runOnModule(Module &M) override { return mergeModuleStringPool(M); }
91
getPassName() const92 StringRef getPassName() const override { return "PPC Merge String Pool"; }
93
getAnalysisUsage(AnalysisUsage & AU) const94 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.
hasReplaceableUsers(GlobalVariable & GV)118 static bool hasReplaceableUsers(GlobalVariable &GV) {
119 for (User *CurrentUser : GV.users()) {
120 if (auto *I = dyn_cast<Instruction>(CurrentUser)) {
121 // Do not merge globals in exception pads.
122 if (I->isEHPad())
123 return false;
124
125 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
126 // Some intrinsics require a plain global.
127 if (II->getIntrinsicID() == Intrinsic::eh_typeid_for)
128 return false;
129 }
130
131 // Other instruction users are always valid.
132 continue;
133 }
134
135 // We cannot replace GlobalValue users because they are not just nodes
136 // in IR. To replace a user like this we would need to create a new
137 // GlobalValue with the replacement and then try to delete the original
138 // GlobalValue. Deleting the original would only happen if it has no other
139 // uses.
140 if (isa<GlobalValue>(CurrentUser))
141 return false;
142
143 // We only support Instruction and Constant users.
144 if (!isa<Constant>(CurrentUser))
145 return false;
146 }
147
148 return true;
149 }
150
151 // Run through all of the constants in the module and determine if they are
152 // valid candidates to be merged into the string pool. Valid candidates will
153 // be added to MergeableStrings.
collectCandidateConstants(Module & M)154 void PPCMergeStringPool::collectCandidateConstants(Module &M) {
155 SmallVector<GlobalValue *, 4> UsedV;
156 collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false);
157 SmallVector<GlobalValue *, 4> UsedVCompiler;
158 collectUsedGlobalVariables(M, UsedVCompiler, /*CompilerUsed=*/true);
159 // Combine all of the Global Variables marked as used into a SmallPtrSet for
160 // faster lookup inside the loop.
161 SmallPtrSet<GlobalValue *, 8> AllUsedGlobals;
162 AllUsedGlobals.insert(UsedV.begin(), UsedV.end());
163 AllUsedGlobals.insert(UsedVCompiler.begin(), UsedVCompiler.end());
164
165 for (GlobalVariable &Global : M.globals()) {
166 LLVM_DEBUG(dbgs() << "Looking at global:");
167 LLVM_DEBUG(Global.dump());
168 LLVM_DEBUG(dbgs() << "isConstant() " << Global.isConstant() << "\n");
169 LLVM_DEBUG(dbgs() << "hasInitializer() " << Global.hasInitializer()
170 << "\n");
171
172 // We can only pool constants.
173 if (!Global.isConstant() || !Global.hasInitializer())
174 continue;
175
176 // If a global constant has a section we do not try to pool it because
177 // there is no guarantee that other constants will also be in the same
178 // section. Trying to pool constants from different sections (or no
179 // section) means that the pool has to be in multiple sections at the same
180 // time.
181 if (Global.hasSection())
182 continue;
183
184 // Do not pool constants with metadata because we should not add metadata
185 // to the pool when that metadata refers to a single constant in the pool.
186 if (Global.hasMetadata())
187 continue;
188
189 ConstantDataSequential *ConstData =
190 dyn_cast<ConstantDataSequential>(Global.getInitializer());
191
192 // If the constant is undef then ConstData will be null.
193 if (!ConstData)
194 continue;
195
196 // Do not pool globals that are part of llvm.used or llvm.compiler.end.
197 if (AllUsedGlobals.contains(&Global))
198 continue;
199
200 if (!hasReplaceableUsers(Global))
201 continue;
202
203 Align AlignOfGlobal = Global.getAlign().valueOrOne();
204
205 // TODO: At this point do not allow over-aligned types. Adding a type
206 // with larger alignment may lose the larger alignment once it is
207 // added to the struct.
208 // Fix this in a future patch.
209 if (AlignOfGlobal.value() > ConstData->getElementByteSize())
210 continue;
211
212 // Make sure that the global is only visible inside the compilation unit.
213 if (Global.getLinkage() != GlobalValue::PrivateLinkage &&
214 Global.getLinkage() != GlobalValue::InternalLinkage)
215 continue;
216
217 LLVM_DEBUG(dbgs() << "Constant data of Global: ");
218 LLVM_DEBUG(ConstData->dump());
219 LLVM_DEBUG(dbgs() << "\n\n");
220
221 MergeableStrings.push_back(&Global);
222 if (MaxAlignment < AlignOfGlobal)
223 MaxAlignment = AlignOfGlobal;
224
225 // If we have already reached the maximum number of pooled strings then
226 // there is no point in looking for more.
227 if (MergeableStrings.size() >= MaxStringsPooled)
228 break;
229 }
230 }
231
mergeModuleStringPool(Module & M)232 bool PPCMergeStringPool::mergeModuleStringPool(Module &M) {
233
234 LLVM_DEBUG(dbgs() << "Merging string pool for module: " << M.getName()
235 << "\n");
236 LLVM_DEBUG(dbgs() << "Number of globals is: " << M.global_size() << "\n");
237
238 collectCandidateConstants(M);
239
240 // If we have too few constants in the module that are merge candidates we
241 // will skip doing the merging.
242 if (MergeableStrings.size() < MinStringsBeforePool)
243 return false;
244
245 // Sort the global constants to make access more efficient.
246 std::sort(MergeableStrings.begin(), MergeableStrings.end(), CompareConstants);
247
248 SmallVector<Constant *> ConstantsInStruct;
249 for (GlobalVariable *GV : MergeableStrings)
250 ConstantsInStruct.push_back(GV->getInitializer());
251
252 // Use an anonymous struct to pool the strings.
253 // TODO: This pass uses a single anonymous struct for all of the pooled
254 // entries. This may cause a performance issue in the situation where
255 // computing the offset requires two instructions (addis, addi). For the
256 // future we may want to split this into multiple structs.
257 Constant *ConstantPool = ConstantStruct::getAnon(ConstantsInStruct);
258 PooledStructType = ConstantPool->getType();
259
260 // The GlobalVariable constructor calls
261 // MM->insertGlobalVariable(PooledGlobal).
262 GlobalVariable *PooledGlobal =
263 new GlobalVariable(M, PooledStructType,
264 /* isConstant */ true, GlobalValue::PrivateLinkage,
265 ConstantPool, "__ModuleStringPool");
266 PooledGlobal->setAlignment(MaxAlignment);
267
268 LLVM_DEBUG(dbgs() << "Constructing global variable for string pool: ");
269 LLVM_DEBUG(PooledGlobal->dump());
270
271 Context = &M.getContext();
272 size_t ElementIndex = 0;
273 for (GlobalVariable *GV : MergeableStrings) {
274
275 LLVM_DEBUG(dbgs() << "The global:\n");
276 LLVM_DEBUG(GV->dump());
277 LLVM_DEBUG(dbgs() << "Has " << GV->getNumUses() << " uses.\n");
278
279 // Access to the pooled constant strings require an offset. Add a GEP
280 // before every use in order to compute this offset.
281 replaceUsesWithGEP(GV, PooledGlobal, ElementIndex);
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 // For pooled strings we need to add the offset into the pool for each string.
294 // This is done by adding a Get Element Pointer (GEP) before each user. This
295 // function adds the GEP.
replaceUsesWithGEP(GlobalVariable * GlobalToReplace,GlobalVariable * GPool,unsigned ElementIndex)296 void PPCMergeStringPool::replaceUsesWithGEP(GlobalVariable *GlobalToReplace,
297 GlobalVariable *GPool,
298 unsigned ElementIndex) {
299 SmallVector<Value *, 2> Indices;
300 Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), 0));
301 Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex));
302
303 Constant *ConstGEP =
304 ConstantExpr::getInBoundsGetElementPtr(PooledStructType, GPool, Indices);
305 LLVM_DEBUG(dbgs() << "Replacing this global:\n");
306 LLVM_DEBUG(GlobalToReplace->dump());
307 LLVM_DEBUG(dbgs() << "with this:\n");
308 LLVM_DEBUG(ConstGEP->dump());
309 GlobalToReplace->replaceAllUsesWith(ConstGEP);
310 }
311
312 } // namespace
313
314 char PPCMergeStringPool::ID = 0;
315
316 INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
317 false)
318
createPPCMergeStringPoolPass()319 ModulePass *llvm::createPPCMergeStringPoolPass() {
320 return new PPCMergeStringPool();
321 }
322