xref: /freebsd/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCMergeStringPool.cpp (revision a90b9d0159070121c221b966469c3e36d912bf82)
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 {
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>(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;
88   PPCMergeStringPool() : ModulePass(ID) {}
89 
90   bool runOnModule(Module &M) override { return mergeModuleStringPool(M); }
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     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.
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 
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.
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 
319 ModulePass *llvm::createPPCMergeStringPoolPass() {
320   return new PPCMergeStringPool();
321 }
322