592 lines · cpp
1//==- AArch64PromoteConstant.cpp - Promote constant to global for AArch64 --==//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the AArch64PromoteConstant pass which promotes constants10// to global variables when this is likely to be more efficient. Currently only11// types related to constant vector (i.e., constant vector, array of constant12// vectors, constant structure with a constant vector field, etc.) are promoted13// to global variables. Constant vectors are likely to be lowered in target14// constant pool during instruction selection already; therefore, the access15// will remain the same (memory load), but the structure types are not split16// into different constant pool accesses for each field. A bonus side effect is17// that created globals may be merged by the global merge pass.18//19// FIXME: This pass may be useful for other targets too.20//===----------------------------------------------------------------------===//21 22#include "AArch64.h"23#include "llvm/ADT/DenseMap.h"24#include "llvm/ADT/SmallVector.h"25#include "llvm/ADT/Statistic.h"26#include "llvm/IR/BasicBlock.h"27#include "llvm/IR/Constant.h"28#include "llvm/IR/Constants.h"29#include "llvm/IR/Dominators.h"30#include "llvm/IR/Function.h"31#include "llvm/IR/GlobalValue.h"32#include "llvm/IR/GlobalVariable.h"33#include "llvm/IR/IRBuilder.h"34#include "llvm/IR/InstIterator.h"35#include "llvm/IR/Instruction.h"36#include "llvm/IR/Instructions.h"37#include "llvm/IR/IntrinsicInst.h"38#include "llvm/IR/Module.h"39#include "llvm/IR/Type.h"40#include "llvm/InitializePasses.h"41#include "llvm/Pass.h"42#include "llvm/Support/Casting.h"43#include "llvm/Support/CommandLine.h"44#include "llvm/Support/Debug.h"45#include "llvm/Support/raw_ostream.h"46#include <cassert>47#include <utility>48 49using namespace llvm;50 51#define DEBUG_TYPE "aarch64-promote-const"52 53// Stress testing mode - disable heuristics.54static cl::opt<bool> Stress("aarch64-stress-promote-const", cl::Hidden,55 cl::desc("Promote all vector constants"));56 57STATISTIC(NumPromoted, "Number of promoted constants");58STATISTIC(NumPromotedUses, "Number of promoted constants uses");59 60//===----------------------------------------------------------------------===//61// AArch64PromoteConstant62//===----------------------------------------------------------------------===//63 64namespace {65 66/// Promotes interesting constant into global variables.67/// The motivating example is:68/// static const uint16_t TableA[32] = {69/// 41944, 40330, 38837, 37450, 36158, 34953, 33826, 32768,70/// 31776, 30841, 29960, 29128, 28340, 27595, 26887, 26215,71/// 25576, 24967, 24386, 23832, 23302, 22796, 22311, 21846,72/// 21400, 20972, 20561, 20165, 19785, 19419, 19066, 18725,73/// };74///75/// uint8x16x4_t LoadStatic(void) {76/// uint8x16x4_t ret;77/// ret.val[0] = vld1q_u16(TableA + 0);78/// ret.val[1] = vld1q_u16(TableA + 8);79/// ret.val[2] = vld1q_u16(TableA + 16);80/// ret.val[3] = vld1q_u16(TableA + 24);81/// return ret;82/// }83///84/// The constants in this example are folded into the uses. Thus, 4 different85/// constants are created.86///87/// As their type is vector the cheapest way to create them is to load them88/// for the memory.89///90/// Therefore the final assembly final has 4 different loads. With this pass91/// enabled, only one load is issued for the constants.92class AArch64PromoteConstant : public ModulePass {93public:94 struct PromotedConstant {95 bool ShouldConvert = false;96 GlobalVariable *GV = nullptr;97 };98 using PromotionCacheTy = SmallDenseMap<Constant *, PromotedConstant, 16>;99 100 struct UpdateRecord {101 Constant *C;102 Instruction *User;103 unsigned Op;104 105 UpdateRecord(Constant *C, Instruction *User, unsigned Op)106 : C(C), User(User), Op(Op) {}107 };108 109 static char ID;110 111 AArch64PromoteConstant() : ModulePass(ID) {}112 113 StringRef getPassName() const override { return "AArch64 Promote Constant"; }114 115 /// Iterate over the functions and promote the interesting constants into116 /// global variables with module scope.117 bool runOnModule(Module &M) override {118 LLVM_DEBUG(dbgs() << getPassName() << '\n');119 if (skipModule(M))120 return false;121 bool Changed = false;122 PromotionCacheTy PromotionCache;123 for (auto &MF : M) {124 Changed |= runOnFunction(MF, PromotionCache);125 }126 return Changed;127 }128 129private:130 /// Look for interesting constants used within the given function.131 /// Promote them into global variables, load these global variables within132 /// the related function, so that the number of inserted load is minimal.133 bool runOnFunction(Function &F, PromotionCacheTy &PromotionCache);134 135 // This transformation requires dominator info136 void getAnalysisUsage(AnalysisUsage &AU) const override {137 AU.setPreservesCFG();138 AU.addRequired<DominatorTreeWrapperPass>();139 AU.addPreserved<DominatorTreeWrapperPass>();140 }141 142 /// Type to store a list of Uses.143 using Uses = SmallVector<std::pair<Instruction *, unsigned>, 4>;144 /// Map an insertion point to all the uses it dominates.145 using InsertionPoints = DenseMap<Instruction *, Uses>;146 147 /// Find the closest point that dominates the given Use.148 Instruction *findInsertionPoint(Instruction &User, unsigned OpNo);149 150 /// Check if the given insertion point is dominated by an existing151 /// insertion point.152 /// If true, the given use is added to the list of dominated uses for153 /// the related existing point.154 /// \param NewPt the insertion point to be checked155 /// \param User the user of the constant156 /// \param OpNo the operand number of the use157 /// \param InsertPts existing insertion points158 /// \pre NewPt and all instruction in InsertPts belong to the same function159 /// \return true if one of the insertion point in InsertPts dominates NewPt,160 /// false otherwise161 bool isDominated(Instruction *NewPt, Instruction *User, unsigned OpNo,162 InsertionPoints &InsertPts);163 164 /// Check if the given insertion point can be merged with an existing165 /// insertion point in a common dominator.166 /// If true, the given use is added to the list of the created insertion167 /// point.168 /// \param NewPt the insertion point to be checked169 /// \param User the user of the constant170 /// \param OpNo the operand number of the use171 /// \param InsertPts existing insertion points172 /// \pre NewPt and all instruction in InsertPts belong to the same function173 /// \pre isDominated returns false for the exact same parameters.174 /// \return true if it exists an insertion point in InsertPts that could175 /// have been merged with NewPt in a common dominator,176 /// false otherwise177 bool tryAndMerge(Instruction *NewPt, Instruction *User, unsigned OpNo,178 InsertionPoints &InsertPts);179 180 /// Compute the minimal insertion points to dominates all the interesting181 /// uses of value.182 /// Insertion points are group per function and each insertion point183 /// contains a list of all the uses it dominates within the related function184 /// \param User the user of the constant185 /// \param OpNo the operand number of the constant186 /// \param[out] InsertPts output storage of the analysis187 void computeInsertionPoint(Instruction *User, unsigned OpNo,188 InsertionPoints &InsertPts);189 190 /// Insert a definition of a new global variable at each point contained in191 /// InsPtsPerFunc and update the related uses (also contained in192 /// InsPtsPerFunc).193 void insertDefinitions(Function &F, GlobalVariable &GV,194 InsertionPoints &InsertPts);195 196 /// Do the constant promotion indicated by the Updates records, keeping track197 /// of globals in PromotionCache.198 void promoteConstants(Function &F, SmallVectorImpl<UpdateRecord> &Updates,199 PromotionCacheTy &PromotionCache);200 201 /// Transfer the list of dominated uses of IPI to NewPt in InsertPts.202 /// Append Use to this list and delete the entry of IPI in InsertPts.203 static void appendAndTransferDominatedUses(Instruction *NewPt,204 Instruction *User, unsigned OpNo,205 InsertionPoints::iterator &IPI,206 InsertionPoints &InsertPts) {207 // Record the dominated use.208 IPI->second.emplace_back(User, OpNo);209 // Transfer the dominated uses of IPI to NewPt210 // Inserting into the DenseMap may invalidate existing iterator.211 // Keep a copy of the key to find the iterator to erase. Keep a copy of the212 // value so that we don't have to dereference IPI->second.213 Instruction *OldInstr = IPI->first;214 Uses OldUses = std::move(IPI->second);215 InsertPts[NewPt] = std::move(OldUses);216 // Erase IPI.217 InsertPts.erase(OldInstr);218 }219};220 221} // end anonymous namespace222 223char AArch64PromoteConstant::ID = 0;224 225INITIALIZE_PASS_BEGIN(AArch64PromoteConstant, "aarch64-promote-const",226 "AArch64 Promote Constant Pass", false, false)227INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)228INITIALIZE_PASS_END(AArch64PromoteConstant, "aarch64-promote-const",229 "AArch64 Promote Constant Pass", false, false)230 231ModulePass *llvm::createAArch64PromoteConstantPass() {232 return new AArch64PromoteConstant();233}234 235/// Check if the given type uses a vector type.236static bool isConstantUsingVectorTy(const Type *CstTy) {237 if (CstTy->isVectorTy())238 return true;239 if (CstTy->isStructTy()) {240 for (unsigned EltIdx = 0, EndEltIdx = CstTy->getStructNumElements();241 EltIdx < EndEltIdx; ++EltIdx)242 if (isConstantUsingVectorTy(CstTy->getStructElementType(EltIdx)))243 return true;244 } else if (CstTy->isArrayTy())245 return isConstantUsingVectorTy(CstTy->getArrayElementType());246 return false;247}248 249// Returns true if \p C contains only ConstantData leafs and no global values,250// block addresses or constant expressions. Traverses ConstantAggregates.251static bool containsOnlyConstantData(const Constant *C) {252 if (isa<ConstantData>(C))253 return true;254 255 if (isa<GlobalValue>(C) || isa<BlockAddress>(C) || isa<ConstantExpr>(C))256 return false;257 258 return all_of(C->operands(), [](const Use &U) {259 return containsOnlyConstantData(cast<Constant>(&U));260 });261}262 263/// Check if the given use (Instruction + OpIdx) of Cst should be converted into264/// a load of a global variable initialized with Cst.265/// A use should be converted if it is legal to do so.266/// For instance, it is not legal to turn the mask operand of a shuffle vector267/// into a load of a global variable.268static bool shouldConvertUse(const Constant *Cst, const Instruction *Instr,269 unsigned OpIdx) {270 // shufflevector instruction expects a const for the mask argument, i.e., the271 // third argument. Do not promote this use in that case.272 if (isa<const ShuffleVectorInst>(Instr) && OpIdx == 2)273 return false;274 275 // extractvalue instruction expects a const idx.276 if (isa<const ExtractValueInst>(Instr) && OpIdx > 0)277 return false;278 279 // extractvalue instruction expects a const idx.280 if (isa<const InsertValueInst>(Instr) && OpIdx > 1)281 return false;282 283 if (isa<const AllocaInst>(Instr) && OpIdx > 0)284 return false;285 286 // Alignment argument must be constant.287 if (isa<const LoadInst>(Instr) && OpIdx > 0)288 return false;289 290 // Alignment argument must be constant.291 if (isa<const StoreInst>(Instr) && OpIdx > 1)292 return false;293 294 // Index must be constant.295 if (isa<const GetElementPtrInst>(Instr) && OpIdx > 0)296 return false;297 298 // Personality function and filters must be constant.299 // Give up on that instruction.300 if (isa<const LandingPadInst>(Instr))301 return false;302 303 // Switch instruction expects constants to compare to.304 if (isa<const SwitchInst>(Instr))305 return false;306 307 // Expected address must be a constant.308 if (isa<const IndirectBrInst>(Instr))309 return false;310 311 // Do not mess with intrinsics.312 if (isa<const IntrinsicInst>(Instr))313 return false;314 315 // Do not mess with inline asm.316 const CallInst *CI = dyn_cast<const CallInst>(Instr);317 return !(CI && CI->isInlineAsm());318}319 320/// Check if the given Cst should be converted into321/// a load of a global variable initialized with Cst.322/// A constant should be converted if it is likely that the materialization of323/// the constant will be tricky. Thus, we give up on zero or undef values.324///325/// \todo Currently, accept only vector related types.326/// Also we give up on all simple vector type to keep the existing327/// behavior. Otherwise, we should push here all the check of the lowering of328/// BUILD_VECTOR. By giving up, we lose the potential benefit of merging329/// constant via global merge and the fact that the same constant is stored330/// only once with this method (versus, as many function that uses the constant331/// for the regular approach, even for float).332/// Again, the simplest solution would be to promote every333/// constant and rematerialize them when they are actually cheap to create.334static bool shouldConvertImpl(const Constant *Cst) {335 if (isa<const UndefValue>(Cst))336 return false;337 338 // FIXME: In some cases, it may be interesting to promote in memory339 // a zero initialized constant.340 // E.g., when the type of Cst require more instructions than the341 // adrp/add/load sequence or when this sequence can be shared by several342 // instances of Cst.343 // Ideally, we could promote this into a global and rematerialize the constant344 // when it was a bad idea.345 if (Cst->isZeroValue())346 return false;347 348 // Globals cannot be or contain scalable vectors.349 if (Cst->getType()->isScalableTy())350 return false;351 352 if (Stress)353 return true;354 355 // FIXME: see function \todo356 if (Cst->getType()->isVectorTy())357 return false;358 return isConstantUsingVectorTy(Cst->getType());359}360 361static bool362shouldConvert(Constant &C,363 AArch64PromoteConstant::PromotionCacheTy &PromotionCache) {364 auto Converted = PromotionCache.insert(365 std::make_pair(&C, AArch64PromoteConstant::PromotedConstant()));366 if (Converted.second)367 Converted.first->second.ShouldConvert = shouldConvertImpl(&C);368 return Converted.first->second.ShouldConvert;369}370 371Instruction *AArch64PromoteConstant::findInsertionPoint(Instruction &User,372 unsigned OpNo) {373 // If this user is a phi, the insertion point is in the related374 // incoming basic block.375 if (PHINode *PhiInst = dyn_cast<PHINode>(&User))376 return PhiInst->getIncomingBlock(OpNo)->getTerminator();377 378 return &User;379}380 381bool AArch64PromoteConstant::isDominated(Instruction *NewPt, Instruction *User,382 unsigned OpNo,383 InsertionPoints &InsertPts) {384 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(385 *NewPt->getParent()->getParent()).getDomTree();386 387 // Traverse all the existing insertion points and check if one is dominating388 // NewPt. If it is, remember that.389 for (auto &IPI : InsertPts) {390 if (NewPt == IPI.first || DT.dominates(IPI.first, NewPt) ||391 // When IPI.first is a terminator instruction, DT may think that392 // the result is defined on the edge.393 // Here we are testing the insertion point, not the definition.394 (IPI.first->getParent() != NewPt->getParent() &&395 DT.dominates(IPI.first->getParent(), NewPt->getParent()))) {396 // No need to insert this point. Just record the dominated use.397 LLVM_DEBUG(dbgs() << "Insertion point dominated by:\n");398 LLVM_DEBUG(IPI.first->print(dbgs()));399 LLVM_DEBUG(dbgs() << '\n');400 IPI.second.emplace_back(User, OpNo);401 return true;402 }403 }404 return false;405}406 407bool AArch64PromoteConstant::tryAndMerge(Instruction *NewPt, Instruction *User,408 unsigned OpNo,409 InsertionPoints &InsertPts) {410 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(411 *NewPt->getParent()->getParent()).getDomTree();412 BasicBlock *NewBB = NewPt->getParent();413 414 // Traverse all the existing insertion point and check if one is dominated by415 // NewPt and thus useless or can be combined with NewPt into a common416 // dominator.417 for (InsertionPoints::iterator IPI = InsertPts.begin(),418 EndIPI = InsertPts.end();419 IPI != EndIPI; ++IPI) {420 BasicBlock *CurBB = IPI->first->getParent();421 if (NewBB == CurBB) {422 // Instructions are in the same block.423 // By construction, NewPt is dominating the other.424 // Indeed, isDominated returned false with the exact same arguments.425 LLVM_DEBUG(dbgs() << "Merge insertion point with:\n");426 LLVM_DEBUG(IPI->first->print(dbgs()));427 LLVM_DEBUG(dbgs() << "\nat considered insertion point.\n");428 appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts);429 return true;430 }431 432 // Look for a common dominator433 BasicBlock *CommonDominator = DT.findNearestCommonDominator(NewBB, CurBB);434 // If none exists, we cannot merge these two points.435 if (!CommonDominator)436 continue;437 438 if (CommonDominator != NewBB) {439 // By construction, the CommonDominator cannot be CurBB.440 assert(CommonDominator != CurBB &&441 "Instruction has not been rejected during isDominated check!");442 // Take the last instruction of the CommonDominator as insertion point443 NewPt = CommonDominator->getTerminator();444 }445 // else, CommonDominator is the block of NewBB, hence NewBB is the last446 // possible insertion point in that block.447 LLVM_DEBUG(dbgs() << "Merge insertion point with:\n");448 LLVM_DEBUG(IPI->first->print(dbgs()));449 LLVM_DEBUG(dbgs() << '\n');450 LLVM_DEBUG(NewPt->print(dbgs()));451 LLVM_DEBUG(dbgs() << '\n');452 appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts);453 return true;454 }455 return false;456}457 458void AArch64PromoteConstant::computeInsertionPoint(459 Instruction *User, unsigned OpNo, InsertionPoints &InsertPts) {460 LLVM_DEBUG(dbgs() << "Considered use, opidx " << OpNo << ":\n");461 LLVM_DEBUG(User->print(dbgs()));462 LLVM_DEBUG(dbgs() << '\n');463 464 Instruction *InsertionPoint = findInsertionPoint(*User, OpNo);465 466 LLVM_DEBUG(dbgs() << "Considered insertion point:\n");467 LLVM_DEBUG(InsertionPoint->print(dbgs()));468 LLVM_DEBUG(dbgs() << '\n');469 470 if (isDominated(InsertionPoint, User, OpNo, InsertPts))471 return;472 // This insertion point is useful, check if we can merge some insertion473 // point in a common dominator or if NewPt dominates an existing one.474 if (tryAndMerge(InsertionPoint, User, OpNo, InsertPts))475 return;476 477 LLVM_DEBUG(dbgs() << "Keep considered insertion point\n");478 479 // It is definitely useful by its own480 InsertPts[InsertionPoint].emplace_back(User, OpNo);481}482 483static void ensurePromotedGV(Function &F, Constant &C,484 AArch64PromoteConstant::PromotedConstant &PC) {485 assert(PC.ShouldConvert &&486 "Expected that we should convert this to a global");487 if (PC.GV)488 return;489 PC.GV = new GlobalVariable(490 *F.getParent(), C.getType(), true, GlobalValue::InternalLinkage, nullptr,491 "_PromotedConst", nullptr, GlobalVariable::NotThreadLocal);492 PC.GV->setInitializer(&C);493 LLVM_DEBUG(dbgs() << "Global replacement: ");494 LLVM_DEBUG(PC.GV->print(dbgs()));495 LLVM_DEBUG(dbgs() << '\n');496 ++NumPromoted;497}498 499void AArch64PromoteConstant::insertDefinitions(Function &F,500 GlobalVariable &PromotedGV,501 InsertionPoints &InsertPts) {502#ifndef NDEBUG503 // Do more checking for debug purposes.504 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();505#endif506 assert(!InsertPts.empty() && "Empty uses does not need a definition");507 508 for (const auto &IPI : InsertPts) {509 // Create the load of the global variable.510 IRBuilder<> Builder(IPI.first);511 LoadInst *LoadedCst =512 Builder.CreateLoad(PromotedGV.getValueType(), &PromotedGV);513 LLVM_DEBUG(dbgs() << "**********\n");514 LLVM_DEBUG(dbgs() << "New def: ");515 LLVM_DEBUG(LoadedCst->print(dbgs()));516 LLVM_DEBUG(dbgs() << '\n');517 518 // Update the dominated uses.519 for (auto Use : IPI.second) {520#ifndef NDEBUG521 assert(DT.dominates(LoadedCst,522 findInsertionPoint(*Use.first, Use.second)) &&523 "Inserted definition does not dominate all its uses!");524#endif525 LLVM_DEBUG({526 dbgs() << "Use to update " << Use.second << ":";527 Use.first->print(dbgs());528 dbgs() << '\n';529 });530 Use.first->setOperand(Use.second, LoadedCst);531 ++NumPromotedUses;532 }533 }534}535 536void AArch64PromoteConstant::promoteConstants(537 Function &F, SmallVectorImpl<UpdateRecord> &Updates,538 PromotionCacheTy &PromotionCache) {539 // Promote the constants.540 for (auto U = Updates.begin(), E = Updates.end(); U != E;) {541 LLVM_DEBUG(dbgs() << "** Compute insertion points **\n");542 auto First = U;543 Constant *C = First->C;544 InsertionPoints InsertPts;545 do {546 computeInsertionPoint(U->User, U->Op, InsertPts);547 } while (++U != E && U->C == C);548 549 auto &Promotion = PromotionCache[C];550 ensurePromotedGV(F, *C, Promotion);551 insertDefinitions(F, *Promotion.GV, InsertPts);552 }553}554 555bool AArch64PromoteConstant::runOnFunction(Function &F,556 PromotionCacheTy &PromotionCache) {557 // Look for instructions using constant vector. Promote that constant to a558 // global variable. Create as few loads of this variable as possible and559 // update the uses accordingly.560 SmallVector<UpdateRecord, 64> Updates;561 for (Instruction &I : instructions(&F)) {562 // Traverse the operand, looking for constant vectors. Replace them by a563 // load of a global variable of constant vector type.564 for (Use &U : I.operands()) {565 Constant *Cst = dyn_cast<Constant>(U);566 // There is no point in promoting global values as they are already567 // global. Do not promote constants containing constant expression, global568 // values or blockaddresses either, as they may require some code569 // expansion.570 if (!Cst || isa<GlobalValue>(Cst) || !containsOnlyConstantData(Cst))571 continue;572 573 // Check if this constant is worth promoting.574 if (!shouldConvert(*Cst, PromotionCache))575 continue;576 577 // Check if this use should be promoted.578 unsigned OpNo = &U - I.op_begin();579 if (!shouldConvertUse(Cst, &I, OpNo))580 continue;581 582 Updates.emplace_back(Cst, &I, OpNo);583 }584 }585 586 if (Updates.empty())587 return false;588 589 promoteConstants(F, Updates, PromotionCache);590 return true;591}592