xref: /freebsd/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCMergeStringPool.cpp (revision cb2887746f8b9dd4ad6b1e757cdc053a08b25a2e)
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