llvm/lib/Target/PowerPC/PPCMergeStringPool.cpp

   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 doInitialization(Module &M) override { return mergeModuleStringPool(M); }
  91   bool runOnModule(Module &M) override { return false; }
  92
  93   StringRef getPassName() const override { return "PPC Merge String Pool"; }
  94
  95   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.
 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.
 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 constants.
 174     if (!Global.isConstant() || !Global.hasInitializer())
 175       continue;
 176
 177     // If a global constant has a section we do not try to pool it because
 178     // there is no guarantee that other constants will also be in the same
 179     // section. Trying to pool constants from different sections (or no
 180     // section) means that the pool has to be in multiple sections at the same
 181     // time.
 182     if (Global.hasSection())
 183       continue;
 184
 185     // Do not pool constants with metadata because we should not add metadata
 186     // to the pool when that metadata refers to a single constant in the pool.
 187     if (Global.hasMetadata())
 188       continue;
 189
 190     ConstantDataSequential *ConstData =
 191         dyn_cast<ConstantDataSequential>(Global.getInitializer());
 192
 193     // If the constant is undef then ConstData will be null.
 194     if (!ConstData)
 195       continue;
 196
 197     // Do not pool globals that are part of llvm.used or llvm.compiler.end.
 198     if (AllUsedGlobals.contains(&Global))
 199       continue;
 200
 201     if (!hasReplaceableUsers(Global))
 202       continue;
 203
 204     Align AlignOfGlobal = Global.getAlign().valueOrOne();
 205
 206     // TODO: At this point do not allow over-aligned types. Adding a type
 207     //       with larger alignment may lose the larger alignment once it is
 208     //       added to the struct.
 209     //       Fix this in a future patch.
 210     if (AlignOfGlobal.value() > ConstData->getElementByteSize())
 211       continue;
 212
 213     // Make sure that the global is only visible inside the compilation unit.
 214     if (Global.getLinkage() != GlobalValue::PrivateLinkage &&
 215         Global.getLinkage() != GlobalValue::InternalLinkage)
 216       continue;
 217
 218     LLVM_DEBUG(dbgs() << "Constant data of Global: ");
 219     LLVM_DEBUG(ConstData->dump());
 220     LLVM_DEBUG(dbgs() << "\n\n");
 221
 222     MergeableStrings.push_back(&Global);
 223     if (MaxAlignment < AlignOfGlobal)
 224       MaxAlignment = AlignOfGlobal;
 225
 226     // If we have already reached the maximum number of pooled strings then
 227     // there is no point in looking for more.
 228     if (MergeableStrings.size() >= MaxStringsPooled)
 229       break;
 230   }
 231 }
 232
 233 bool PPCMergeStringPool::mergeModuleStringPool(Module &M) {
 234
 235   LLVM_DEBUG(dbgs() << "Merging string pool for module: " << M.getName()
 236                     << "\n");
 237   LLVM_DEBUG(dbgs() << "Number of globals is: " << M.global_size() << "\n");
 238
 239   collectCandidateConstants(M);
 240
 241   // If we have too few constants in the module that are merge candidates we
 242   // will skip doing the merging.
 243   if (MergeableStrings.size() < MinStringsBeforePool)
 244     return false;
 245
 246   // Sort the global constants to make access more efficient.
 247   std::sort(MergeableStrings.begin(), MergeableStrings.end(), CompareConstants);
 248
 249   SmallVector<Constant *> ConstantsInStruct;
 250   for (GlobalVariable *GV : MergeableStrings)
 251     ConstantsInStruct.push_back(GV->getInitializer());
 252
 253   // Use an anonymous struct to pool the strings.
 254   // TODO: This pass uses a single anonymous struct for all of the pooled
 255   // entries. This may cause a performance issue in the situation where
 256   // computing the offset requires two instructions (addis, addi). For the
 257   // future we may want to split this into multiple structs.
 258   Constant *ConstantPool = ConstantStruct::getAnon(ConstantsInStruct);
 259   PooledStructType = ConstantPool->getType();
 260
 261   // The GlobalVariable constructor calls
 262   // MM->insertGlobalVariable(PooledGlobal).
 263   GlobalVariable *PooledGlobal =
 264       new GlobalVariable(M, PooledStructType,
 265                          /* isConstant */ true, GlobalValue::PrivateLinkage,
 266                          ConstantPool, "__ModuleStringPool");
 267   PooledGlobal->setAlignment(MaxAlignment);
 268
 269   LLVM_DEBUG(dbgs() << "Constructing global variable for string pool: ");
 270   LLVM_DEBUG(PooledGlobal->dump());
 271
 272   Context = &M.getContext();
 273   size_t ElementIndex = 0;
 274   for (GlobalVariable *GV : MergeableStrings) {
 275
 276     LLVM_DEBUG(dbgs() << "The global:\n");
 277     LLVM_DEBUG(GV->dump());
 278     LLVM_DEBUG(dbgs() << "Has " << GV->getNumUses() << " uses.\n");
 279
 280     // Access to the pooled constant strings require an offset. Add a GEP
 281     // before every use in order to compute this offset.
 282     replaceUsesWithGEP(GV, PooledGlobal, ElementIndex);
 283
 284     // Replace all the uses by metadata.
 285     if (GV->isUsedByMetadata()) {
 286       Constant *Indices[2] = {
 287           ConstantInt::get(Type::getInt32Ty(*Context), 0),
 288           ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex)};
 289       Constant *ConstGEP = ConstantExpr::getInBoundsGetElementPtr(
 290           PooledStructType, PooledGlobal, Indices);
 291       ValueAsMetadata::handleRAUW(GV, ConstGEP);
 292     }
 293     assert(!GV->isUsedByMetadata() && "Should be no metadata use anymore");
 294
 295     // This GV has no more uses so we can erase it.
 296     if (GV->use_empty())
 297       GV->eraseFromParent();
 298
 299     NumPooledStrings++;
 300     ElementIndex++;
 301   }
 302   return true;
 303 }
 304
 305 // For pooled strings we need to add the offset into the pool for each string.
 306 // This is done by adding a Get Element Pointer (GEP) before each user. This
 307 // function adds the GEP.
 308 void PPCMergeStringPool::replaceUsesWithGEP(GlobalVariable *GlobalToReplace,
 309                                             GlobalVariable *GPool,
 310                                             unsigned ElementIndex) {
 311   SmallVector<Value *, 2> Indices;
 312   Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), 0));
 313   Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex));
 314
 315   Constant *ConstGEP =
 316       ConstantExpr::getInBoundsGetElementPtr(PooledStructType, GPool, Indices);
 317   LLVM_DEBUG(dbgs() << "Replacing this global:\n");
 318   LLVM_DEBUG(GlobalToReplace->dump());
 319   LLVM_DEBUG(dbgs() << "with this:\n");
 320   LLVM_DEBUG(ConstGEP->dump());
 321   GlobalToReplace->replaceAllUsesWith(ConstGEP);
 322 }
 323
 324 } // namespace
 325
 326 char PPCMergeStringPool::ID = 0;
 327
 328 INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
 329                 false)
 330
 331 ModulePass *llvm::createPPCMergeStringPoolPass() {
 332   return new PPCMergeStringPool();
 333 }