15f757f3fSDimitry Andric //===-- PPCMergeStringPool.cpp -------------------------------------------===//
25f757f3fSDimitry Andric //
35f757f3fSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
45f757f3fSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
55f757f3fSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
65f757f3fSDimitry Andric //
75f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
85f757f3fSDimitry Andric //
95f757f3fSDimitry Andric // This transformation tries to merge the strings in the module into one pool
105f757f3fSDimitry Andric // of strings. The idea is to reduce the number of TOC entries in the module so
115f757f3fSDimitry Andric // that instead of having one TOC entry for each string there is only one global
125f757f3fSDimitry Andric // TOC entry and all of the strings are referenced off of that one entry plus
135f757f3fSDimitry Andric // an offset.
145f757f3fSDimitry Andric //
155f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
165f757f3fSDimitry Andric
175f757f3fSDimitry Andric #include "PPC.h"
185f757f3fSDimitry Andric #include "llvm/ADT/Statistic.h"
195f757f3fSDimitry Andric #include "llvm/Analysis/DomTreeUpdater.h"
205f757f3fSDimitry Andric #include "llvm/Analysis/LoopInfo.h"
215f757f3fSDimitry Andric #include "llvm/Analysis/LoopIterator.h"
225f757f3fSDimitry Andric #include "llvm/Analysis/ScalarEvolution.h"
235f757f3fSDimitry Andric #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
245f757f3fSDimitry Andric #include "llvm/IR/Constants.h"
255f757f3fSDimitry Andric #include "llvm/IR/Instructions.h"
263a079333SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
275f757f3fSDimitry Andric #include "llvm/IR/Module.h"
285f757f3fSDimitry Andric #include "llvm/IR/ValueSymbolTable.h"
295f757f3fSDimitry Andric #include "llvm/Pass.h"
305f757f3fSDimitry Andric #include "llvm/Support/CommandLine.h"
315f757f3fSDimitry Andric
325f757f3fSDimitry Andric #define DEBUG_TYPE "ppc-merge-strings"
335f757f3fSDimitry Andric
345f757f3fSDimitry Andric STATISTIC(NumPooledStrings, "Number of Strings Pooled");
355f757f3fSDimitry Andric
365f757f3fSDimitry Andric using namespace llvm;
375f757f3fSDimitry Andric
385f757f3fSDimitry Andric static cl::opt<unsigned>
395f757f3fSDimitry Andric MaxStringsPooled("ppc-max-strings-pooled", cl::Hidden, cl::init(-1),
405f757f3fSDimitry Andric cl::desc("Maximum Number of Strings to Pool."));
415f757f3fSDimitry Andric
425f757f3fSDimitry Andric static cl::opt<unsigned>
435f757f3fSDimitry Andric MinStringsBeforePool("ppc-min-strings-before-pool", cl::Hidden, cl::init(2),
445f757f3fSDimitry Andric cl::desc("Minimum number of string candidates before "
455f757f3fSDimitry Andric "pooling is considered."));
465f757f3fSDimitry Andric
475f757f3fSDimitry Andric namespace {
485f757f3fSDimitry Andric struct {
operator ()__anonf0e1b5010111::__anonf0e1b5010208495f757f3fSDimitry Andric bool operator()(const GlobalVariable *LHS, const GlobalVariable *RHS) const {
505f757f3fSDimitry Andric // First priority is alignment.
515f757f3fSDimitry Andric // If elements are sorted in terms of alignment then there won't be an
525f757f3fSDimitry Andric // issue with incorrect alignment that would require padding.
535f757f3fSDimitry Andric Align LHSAlign = LHS->getAlign().valueOrOne();
545f757f3fSDimitry Andric Align RHSAlign = RHS->getAlign().valueOrOne();
555f757f3fSDimitry Andric if (LHSAlign > RHSAlign)
565f757f3fSDimitry Andric return true;
575f757f3fSDimitry Andric else if (LHSAlign < RHSAlign)
585f757f3fSDimitry Andric return false;
595f757f3fSDimitry Andric
605f757f3fSDimitry Andric // Next priority is the number of uses.
615f757f3fSDimitry Andric // Smaller offsets are easier to materialize because materializing a large
625f757f3fSDimitry Andric // offset may require more than one instruction. (ie addis, addi).
635f757f3fSDimitry Andric if (LHS->getNumUses() > RHS->getNumUses())
645f757f3fSDimitry Andric return true;
655f757f3fSDimitry Andric else if (LHS->getNumUses() < RHS->getNumUses())
665f757f3fSDimitry Andric return false;
675f757f3fSDimitry Andric
685f757f3fSDimitry Andric const Constant *ConstLHS = LHS->getInitializer();
695f757f3fSDimitry Andric const ConstantDataSequential *ConstDataLHS =
705f757f3fSDimitry Andric dyn_cast<ConstantDataSequential>(ConstLHS);
715f757f3fSDimitry Andric unsigned LHSSize =
725f757f3fSDimitry Andric ConstDataLHS->getNumElements() * ConstDataLHS->getElementByteSize();
735f757f3fSDimitry Andric const Constant *ConstRHS = RHS->getInitializer();
745f757f3fSDimitry Andric const ConstantDataSequential *ConstDataRHS =
755f757f3fSDimitry Andric dyn_cast<ConstantDataSequential>(ConstRHS);
765f757f3fSDimitry Andric unsigned RHSSize =
775f757f3fSDimitry Andric ConstDataRHS->getNumElements() * ConstDataRHS->getElementByteSize();
785f757f3fSDimitry Andric
795f757f3fSDimitry Andric // Finally smaller constants should go first. This is, again, trying to
805f757f3fSDimitry Andric // minimize the offsets into the final struct.
815f757f3fSDimitry Andric return LHSSize < RHSSize;
825f757f3fSDimitry Andric }
835f757f3fSDimitry Andric } CompareConstants;
845f757f3fSDimitry Andric
855f757f3fSDimitry Andric class PPCMergeStringPool : public ModulePass {
865f757f3fSDimitry Andric public:
875f757f3fSDimitry Andric static char ID;
PPCMergeStringPool()885f757f3fSDimitry Andric PPCMergeStringPool() : ModulePass(ID) {}
895f757f3fSDimitry Andric
runOnModule(Module & M)905f757f3fSDimitry Andric bool runOnModule(Module &M) override { return mergeModuleStringPool(M); }
915f757f3fSDimitry Andric
getPassName() const925f757f3fSDimitry Andric StringRef getPassName() const override { return "PPC Merge String Pool"; }
935f757f3fSDimitry Andric
getAnalysisUsage(AnalysisUsage & AU) const945f757f3fSDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override {
955f757f3fSDimitry Andric AU.addPreserved<DominatorTreeWrapperPass>();
965f757f3fSDimitry Andric AU.addPreserved<LoopInfoWrapperPass>();
975f757f3fSDimitry Andric AU.addPreserved<ScalarEvolutionWrapperPass>();
985f757f3fSDimitry Andric AU.addPreserved<SCEVAAWrapperPass>();
995f757f3fSDimitry Andric }
1005f757f3fSDimitry Andric
1015f757f3fSDimitry Andric private:
1025f757f3fSDimitry Andric // Globals in a Module are already unique so a set is not required and a
1035f757f3fSDimitry Andric // vector will do.
1045f757f3fSDimitry Andric std::vector<GlobalVariable *> MergeableStrings;
1055f757f3fSDimitry Andric Align MaxAlignment;
1065f757f3fSDimitry Andric Type *PooledStructType;
1075f757f3fSDimitry Andric LLVMContext *Context;
1085f757f3fSDimitry Andric void collectCandidateConstants(Module &M);
1095f757f3fSDimitry Andric bool mergeModuleStringPool(Module &M);
1105f757f3fSDimitry Andric void replaceUsesWithGEP(GlobalVariable *GlobalToReplace, GlobalVariable *GPool,
1115f757f3fSDimitry Andric unsigned ElementIndex);
1125f757f3fSDimitry Andric };
1135f757f3fSDimitry Andric
1145f757f3fSDimitry Andric
1155f757f3fSDimitry Andric // In order for a constant to be pooled we need to be able to replace all of
1165f757f3fSDimitry Andric // the uses for that constant. This function checks all of the uses to make
1175f757f3fSDimitry Andric // sure that they can be replaced.
hasReplaceableUsers(GlobalVariable & GV)1185f757f3fSDimitry Andric static bool hasReplaceableUsers(GlobalVariable &GV) {
1195f757f3fSDimitry Andric for (User *CurrentUser : GV.users()) {
1203a079333SDimitry Andric if (auto *I = dyn_cast<Instruction>(CurrentUser)) {
1213a079333SDimitry Andric // Do not merge globals in exception pads.
1223a079333SDimitry Andric if (I->isEHPad())
1233a079333SDimitry Andric return false;
1243a079333SDimitry Andric
1253a079333SDimitry Andric if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1263a079333SDimitry Andric // Some intrinsics require a plain global.
1273a079333SDimitry Andric if (II->getIntrinsicID() == Intrinsic::eh_typeid_for)
1283a079333SDimitry Andric return false;
1293a079333SDimitry Andric }
1303a079333SDimitry Andric
1313a079333SDimitry Andric // Other instruction users are always valid.
1325f757f3fSDimitry Andric continue;
1333a079333SDimitry Andric }
1345f757f3fSDimitry Andric
1355f757f3fSDimitry Andric // We cannot replace GlobalValue users because they are not just nodes
1365f757f3fSDimitry Andric // in IR. To replace a user like this we would need to create a new
1375f757f3fSDimitry Andric // GlobalValue with the replacement and then try to delete the original
1385f757f3fSDimitry Andric // GlobalValue. Deleting the original would only happen if it has no other
1395f757f3fSDimitry Andric // uses.
1405f757f3fSDimitry Andric if (isa<GlobalValue>(CurrentUser))
1415f757f3fSDimitry Andric return false;
1425f757f3fSDimitry Andric
1435f757f3fSDimitry Andric // We only support Instruction and Constant users.
1445f757f3fSDimitry Andric if (!isa<Constant>(CurrentUser))
1455f757f3fSDimitry Andric return false;
1465f757f3fSDimitry Andric }
1475f757f3fSDimitry Andric
1485f757f3fSDimitry Andric return true;
1495f757f3fSDimitry Andric }
1505f757f3fSDimitry Andric
1515f757f3fSDimitry Andric // Run through all of the constants in the module and determine if they are
1525f757f3fSDimitry Andric // valid candidates to be merged into the string pool. Valid candidates will
1535f757f3fSDimitry Andric // be added to MergeableStrings.
collectCandidateConstants(Module & M)1545f757f3fSDimitry Andric void PPCMergeStringPool::collectCandidateConstants(Module &M) {
1555f757f3fSDimitry Andric SmallVector<GlobalValue *, 4> UsedV;
1565f757f3fSDimitry Andric collectUsedGlobalVariables(M, UsedV, /*CompilerUsed=*/false);
1575f757f3fSDimitry Andric SmallVector<GlobalValue *, 4> UsedVCompiler;
1585f757f3fSDimitry Andric collectUsedGlobalVariables(M, UsedVCompiler, /*CompilerUsed=*/true);
1595f757f3fSDimitry Andric // Combine all of the Global Variables marked as used into a SmallPtrSet for
1605f757f3fSDimitry Andric // faster lookup inside the loop.
1615f757f3fSDimitry Andric SmallPtrSet<GlobalValue *, 8> AllUsedGlobals;
1625f757f3fSDimitry Andric AllUsedGlobals.insert(UsedV.begin(), UsedV.end());
1635f757f3fSDimitry Andric AllUsedGlobals.insert(UsedVCompiler.begin(), UsedVCompiler.end());
1645f757f3fSDimitry Andric
1655f757f3fSDimitry Andric for (GlobalVariable &Global : M.globals()) {
1665f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Looking at global:");
1675f757f3fSDimitry Andric LLVM_DEBUG(Global.dump());
1685f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "isConstant() " << Global.isConstant() << "\n");
1695f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "hasInitializer() " << Global.hasInitializer()
1705f757f3fSDimitry Andric << "\n");
1715f757f3fSDimitry Andric
1725f757f3fSDimitry Andric // We can only pool constants.
1735f757f3fSDimitry Andric if (!Global.isConstant() || !Global.hasInitializer())
1745f757f3fSDimitry Andric continue;
1755f757f3fSDimitry Andric
1765f757f3fSDimitry Andric // If a global constant has a section we do not try to pool it because
1775f757f3fSDimitry Andric // there is no guarantee that other constants will also be in the same
1785f757f3fSDimitry Andric // section. Trying to pool constants from different sections (or no
1795f757f3fSDimitry Andric // section) means that the pool has to be in multiple sections at the same
1805f757f3fSDimitry Andric // time.
1815f757f3fSDimitry Andric if (Global.hasSection())
1825f757f3fSDimitry Andric continue;
1835f757f3fSDimitry Andric
1845f757f3fSDimitry Andric // Do not pool constants with metadata because we should not add metadata
1855f757f3fSDimitry Andric // to the pool when that metadata refers to a single constant in the pool.
1865f757f3fSDimitry Andric if (Global.hasMetadata())
1875f757f3fSDimitry Andric continue;
1885f757f3fSDimitry Andric
1895f757f3fSDimitry Andric ConstantDataSequential *ConstData =
1905f757f3fSDimitry Andric dyn_cast<ConstantDataSequential>(Global.getInitializer());
1915f757f3fSDimitry Andric
1925f757f3fSDimitry Andric // If the constant is undef then ConstData will be null.
1935f757f3fSDimitry Andric if (!ConstData)
1945f757f3fSDimitry Andric continue;
1955f757f3fSDimitry Andric
1965f757f3fSDimitry Andric // Do not pool globals that are part of llvm.used or llvm.compiler.end.
1975f757f3fSDimitry Andric if (AllUsedGlobals.contains(&Global))
1985f757f3fSDimitry Andric continue;
1995f757f3fSDimitry Andric
2005f757f3fSDimitry Andric if (!hasReplaceableUsers(Global))
2015f757f3fSDimitry Andric continue;
2025f757f3fSDimitry Andric
2035f757f3fSDimitry Andric Align AlignOfGlobal = Global.getAlign().valueOrOne();
2045f757f3fSDimitry Andric
2055f757f3fSDimitry Andric // TODO: At this point do not allow over-aligned types. Adding a type
2065f757f3fSDimitry Andric // with larger alignment may lose the larger alignment once it is
2075f757f3fSDimitry Andric // added to the struct.
2085f757f3fSDimitry Andric // Fix this in a future patch.
2095f757f3fSDimitry Andric if (AlignOfGlobal.value() > ConstData->getElementByteSize())
2105f757f3fSDimitry Andric continue;
2115f757f3fSDimitry Andric
2125f757f3fSDimitry Andric // Make sure that the global is only visible inside the compilation unit.
2135f757f3fSDimitry Andric if (Global.getLinkage() != GlobalValue::PrivateLinkage &&
2145f757f3fSDimitry Andric Global.getLinkage() != GlobalValue::InternalLinkage)
2155f757f3fSDimitry Andric continue;
2165f757f3fSDimitry Andric
2175f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Constant data of Global: ");
2185f757f3fSDimitry Andric LLVM_DEBUG(ConstData->dump());
2195f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "\n\n");
2205f757f3fSDimitry Andric
2215f757f3fSDimitry Andric MergeableStrings.push_back(&Global);
2225f757f3fSDimitry Andric if (MaxAlignment < AlignOfGlobal)
2235f757f3fSDimitry Andric MaxAlignment = AlignOfGlobal;
2245f757f3fSDimitry Andric
2255f757f3fSDimitry Andric // If we have already reached the maximum number of pooled strings then
2265f757f3fSDimitry Andric // there is no point in looking for more.
2275f757f3fSDimitry Andric if (MergeableStrings.size() >= MaxStringsPooled)
2285f757f3fSDimitry Andric break;
2295f757f3fSDimitry Andric }
2305f757f3fSDimitry Andric }
2315f757f3fSDimitry Andric
mergeModuleStringPool(Module & M)2325f757f3fSDimitry Andric bool PPCMergeStringPool::mergeModuleStringPool(Module &M) {
2335f757f3fSDimitry Andric
2345f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Merging string pool for module: " << M.getName()
2355f757f3fSDimitry Andric << "\n");
2365f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Number of globals is: " << M.global_size() << "\n");
2375f757f3fSDimitry Andric
2385f757f3fSDimitry Andric collectCandidateConstants(M);
2395f757f3fSDimitry Andric
2405f757f3fSDimitry Andric // If we have too few constants in the module that are merge candidates we
2415f757f3fSDimitry Andric // will skip doing the merging.
2425f757f3fSDimitry Andric if (MergeableStrings.size() < MinStringsBeforePool)
2435f757f3fSDimitry Andric return false;
2445f757f3fSDimitry Andric
2455f757f3fSDimitry Andric // Sort the global constants to make access more efficient.
2465f757f3fSDimitry Andric std::sort(MergeableStrings.begin(), MergeableStrings.end(), CompareConstants);
2475f757f3fSDimitry Andric
2485f757f3fSDimitry Andric SmallVector<Constant *> ConstantsInStruct;
2495f757f3fSDimitry Andric for (GlobalVariable *GV : MergeableStrings)
2505f757f3fSDimitry Andric ConstantsInStruct.push_back(GV->getInitializer());
2515f757f3fSDimitry Andric
2525f757f3fSDimitry Andric // Use an anonymous struct to pool the strings.
2535f757f3fSDimitry Andric // TODO: This pass uses a single anonymous struct for all of the pooled
2545f757f3fSDimitry Andric // entries. This may cause a performance issue in the situation where
2555f757f3fSDimitry Andric // computing the offset requires two instructions (addis, addi). For the
2565f757f3fSDimitry Andric // future we may want to split this into multiple structs.
2575f757f3fSDimitry Andric Constant *ConstantPool = ConstantStruct::getAnon(ConstantsInStruct);
2585f757f3fSDimitry Andric PooledStructType = ConstantPool->getType();
2595f757f3fSDimitry Andric
2605f757f3fSDimitry Andric // The GlobalVariable constructor calls
2615f757f3fSDimitry Andric // MM->insertGlobalVariable(PooledGlobal).
2625f757f3fSDimitry Andric GlobalVariable *PooledGlobal =
2635f757f3fSDimitry Andric new GlobalVariable(M, PooledStructType,
2645f757f3fSDimitry Andric /* isConstant */ true, GlobalValue::PrivateLinkage,
2655f757f3fSDimitry Andric ConstantPool, "__ModuleStringPool");
2665f757f3fSDimitry Andric PooledGlobal->setAlignment(MaxAlignment);
2675f757f3fSDimitry Andric
2685f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Constructing global variable for string pool: ");
2695f757f3fSDimitry Andric LLVM_DEBUG(PooledGlobal->dump());
2705f757f3fSDimitry Andric
2715f757f3fSDimitry Andric Context = &M.getContext();
2725f757f3fSDimitry Andric size_t ElementIndex = 0;
2735f757f3fSDimitry Andric for (GlobalVariable *GV : MergeableStrings) {
2745f757f3fSDimitry Andric
2755f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "The global:\n");
2765f757f3fSDimitry Andric LLVM_DEBUG(GV->dump());
2775f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Has " << GV->getNumUses() << " uses.\n");
2785f757f3fSDimitry Andric
2795f757f3fSDimitry Andric // Access to the pooled constant strings require an offset. Add a GEP
2805f757f3fSDimitry Andric // before every use in order to compute this offset.
2815f757f3fSDimitry Andric replaceUsesWithGEP(GV, PooledGlobal, ElementIndex);
2825f757f3fSDimitry Andric
2835f757f3fSDimitry Andric // This GV has no more uses so we can erase it.
2845f757f3fSDimitry Andric if (GV->use_empty())
2855f757f3fSDimitry Andric GV->eraseFromParent();
2865f757f3fSDimitry Andric
2875f757f3fSDimitry Andric NumPooledStrings++;
2885f757f3fSDimitry Andric ElementIndex++;
2895f757f3fSDimitry Andric }
2905f757f3fSDimitry Andric return true;
2915f757f3fSDimitry Andric }
2925f757f3fSDimitry Andric
2935f757f3fSDimitry Andric // For pooled strings we need to add the offset into the pool for each string.
2945f757f3fSDimitry Andric // This is done by adding a Get Element Pointer (GEP) before each user. This
2955f757f3fSDimitry Andric // function adds the GEP.
replaceUsesWithGEP(GlobalVariable * GlobalToReplace,GlobalVariable * GPool,unsigned ElementIndex)2965f757f3fSDimitry Andric void PPCMergeStringPool::replaceUsesWithGEP(GlobalVariable *GlobalToReplace,
2975f757f3fSDimitry Andric GlobalVariable *GPool,
2985f757f3fSDimitry Andric unsigned ElementIndex) {
2995f757f3fSDimitry Andric SmallVector<Value *, 2> Indices;
3005f757f3fSDimitry Andric Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), 0));
3015f757f3fSDimitry Andric Indices.push_back(ConstantInt::get(Type::getInt32Ty(*Context), ElementIndex));
3025f757f3fSDimitry Andric
303*f30188c4SDimitry Andric Constant *ConstGEP =
304*f30188c4SDimitry Andric ConstantExpr::getInBoundsGetElementPtr(PooledStructType, GPool, Indices);
3055f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "Replacing this global:\n");
3065f757f3fSDimitry Andric LLVM_DEBUG(GlobalToReplace->dump());
3075f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "with this:\n");
3083a079333SDimitry Andric LLVM_DEBUG(ConstGEP->dump());
3093a079333SDimitry Andric GlobalToReplace->replaceAllUsesWith(ConstGEP);
3105f757f3fSDimitry Andric }
3115f757f3fSDimitry Andric
3125f757f3fSDimitry Andric } // namespace
3135f757f3fSDimitry Andric
3145f757f3fSDimitry Andric char PPCMergeStringPool::ID = 0;
3155f757f3fSDimitry Andric
3165f757f3fSDimitry Andric INITIALIZE_PASS(PPCMergeStringPool, DEBUG_TYPE, "PPC Merge String Pool", false,
3175f757f3fSDimitry Andric false)
3185f757f3fSDimitry Andric
createPPCMergeStringPoolPass()3195f757f3fSDimitry Andric ModulePass *llvm::createPPCMergeStringPoolPass() {
3205f757f3fSDimitry Andric return new PPCMergeStringPool();
3215f757f3fSDimitry Andric }
322