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(-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(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>(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
85class PPCMergeStringPool : public ModulePass {
86public:
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
101private:
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.
118static 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.
154void 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
232bool 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.
296void 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
314char PPCMergeStringPool::ID = 0;
315
316INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
317                false)
318
319ModulePass *llvm::createPPCMergeStringPoolPass() {
320  return new PPCMergeStringPool();
321}
322