588 lines · cpp
1//===-- AMDGPUCodeGenPrepare.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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This pass does misc. AMDGPU optimizations on IR *just* before instruction11/// selection.12//13//===----------------------------------------------------------------------===//14 15#include "AMDGPU.h"16#include "AMDGPUTargetMachine.h"17#include "llvm/Analysis/AssumptionCache.h"18#include "llvm/Analysis/UniformityAnalysis.h"19#include "llvm/Analysis/ValueTracking.h"20#include "llvm/CodeGen/TargetPassConfig.h"21#include "llvm/IR/IRBuilder.h"22#include "llvm/IR/InstVisitor.h"23#include "llvm/IR/IntrinsicsAMDGPU.h"24#include "llvm/InitializePasses.h"25#include "llvm/Support/CommandLine.h"26#include "llvm/Support/KnownBits.h"27#include "llvm/Transforms/Utils/Local.h"28 29#define DEBUG_TYPE "amdgpu-late-codegenprepare"30 31using namespace llvm;32 33// Scalar load widening needs running after load-store-vectorizer as that pass34// doesn't handle overlapping cases. In addition, this pass enhances the35// widening to handle cases where scalar sub-dword loads are naturally aligned36// only but not dword aligned.37static cl::opt<bool>38 WidenLoads("amdgpu-late-codegenprepare-widen-constant-loads",39 cl::desc("Widen sub-dword constant address space loads in "40 "AMDGPULateCodeGenPrepare"),41 cl::ReallyHidden, cl::init(true));42 43namespace {44 45class AMDGPULateCodeGenPrepare46 : public InstVisitor<AMDGPULateCodeGenPrepare, bool> {47 Function &F;48 const DataLayout &DL;49 const GCNSubtarget &ST;50 51 AssumptionCache *const AC;52 UniformityInfo &UA;53 54 SmallVector<WeakTrackingVH, 8> DeadInsts;55 56public:57 AMDGPULateCodeGenPrepare(Function &F, const GCNSubtarget &ST,58 AssumptionCache *AC, UniformityInfo &UA)59 : F(F), DL(F.getDataLayout()), ST(ST), AC(AC), UA(UA) {}60 bool run();61 bool visitInstruction(Instruction &) { return false; }62 63 // Check if the specified value is at least DWORD aligned.64 bool isDWORDAligned(const Value *V) const {65 KnownBits Known = computeKnownBits(V, DL, AC);66 return Known.countMinTrailingZeros() >= 2;67 }68 69 bool canWidenScalarExtLoad(LoadInst &LI) const;70 bool visitLoadInst(LoadInst &LI);71};72 73using ValueToValueMap = DenseMap<const Value *, Value *>;74 75class LiveRegOptimizer {76private:77 Module &Mod;78 const DataLayout &DL;79 const GCNSubtarget &ST;80 81 /// The scalar type to convert to82 Type *const ConvertToScalar;83 /// Map of Value -> Converted Value84 ValueToValueMap ValMap;85 /// Map of containing conversions from Optimal Type -> Original Type per BB.86 DenseMap<BasicBlock *, ValueToValueMap> BBUseValMap;87 88public:89 /// Calculate the and \p return the type to convert to given a problematic \p90 /// OriginalType. In some instances, we may widen the type (e.g. v2i8 -> i32).91 Type *calculateConvertType(Type *OriginalType);92 /// Convert the virtual register defined by \p V to the compatible vector of93 /// legal type94 Value *convertToOptType(Instruction *V, BasicBlock::iterator &InstPt);95 /// Convert the virtual register defined by \p V back to the original type \p96 /// ConvertType, stripping away the MSBs in cases where there was an imperfect97 /// fit (e.g. v2i32 -> v7i8)98 Value *convertFromOptType(Type *ConvertType, Instruction *V,99 BasicBlock::iterator &InstPt,100 BasicBlock *InsertBlock);101 /// Check for problematic PHI nodes or cross-bb values based on the value102 /// defined by \p I, and coerce to legal types if necessary. For problematic103 /// PHI node, we coerce all incoming values in a single invocation.104 bool optimizeLiveType(Instruction *I,105 SmallVectorImpl<WeakTrackingVH> &DeadInsts);106 107 // Whether or not the type should be replaced to avoid inefficient108 // legalization code109 bool shouldReplace(Type *ITy) {110 FixedVectorType *VTy = dyn_cast<FixedVectorType>(ITy);111 if (!VTy)112 return false;113 114 const auto *TLI = ST.getTargetLowering();115 116 Type *EltTy = VTy->getElementType();117 // If the element size is not less than the convert to scalar size, then we118 // can't do any bit packing119 if (!EltTy->isIntegerTy() ||120 EltTy->getScalarSizeInBits() > ConvertToScalar->getScalarSizeInBits())121 return false;122 123 // Only coerce illegal types124 TargetLoweringBase::LegalizeKind LK =125 TLI->getTypeConversion(EltTy->getContext(), EVT::getEVT(EltTy, false));126 return LK.first != TargetLoweringBase::TypeLegal;127 }128 129 bool isOpLegal(Instruction *I) { return isa<StoreInst, IntrinsicInst>(I); }130 131 bool isCoercionProfitable(Instruction *II) {132 SmallPtrSet<Instruction *, 4> CVisited;133 SmallVector<Instruction *, 4> UserList;134 135 // Check users for profitable conditions (across block user which can136 // natively handle the illegal vector).137 for (User *V : II->users())138 if (auto *UseInst = dyn_cast<Instruction>(V))139 UserList.push_back(UseInst);140 141 auto IsLookThru = [](Instruction *II) {142 if (const auto *Intr = dyn_cast<IntrinsicInst>(II))143 return Intr->getIntrinsicID() == Intrinsic::amdgcn_perm;144 return isa<PHINode, ShuffleVectorInst, InsertElementInst,145 ExtractElementInst, CastInst>(II);146 };147 148 while (!UserList.empty()) {149 auto CII = UserList.pop_back_val();150 if (!CVisited.insert(CII).second)151 continue;152 153 // Same-BB filter must look at the *user*; and allow non-lookthrough154 // users when the def is a PHI (loop-header pattern).155 if (CII->getParent() == II->getParent() && !IsLookThru(CII) &&156 !isa<PHINode>(II))157 continue;158 159 if (isOpLegal(CII))160 return true;161 162 if (IsLookThru(CII))163 for (User *V : CII->users())164 if (auto *UseInst = dyn_cast<Instruction>(V))165 UserList.push_back(UseInst);166 }167 return false;168 }169 170 LiveRegOptimizer(Module &Mod, const GCNSubtarget &ST)171 : Mod(Mod), DL(Mod.getDataLayout()), ST(ST),172 ConvertToScalar(Type::getInt32Ty(Mod.getContext())) {}173};174 175} // end anonymous namespace176 177bool AMDGPULateCodeGenPrepare::run() {178 // "Optimize" the virtual regs that cross basic block boundaries. When179 // building the SelectionDAG, vectors of illegal types that cross basic blocks180 // will be scalarized and widened, with each scalar living in its181 // own register. To work around this, this optimization converts the182 // vectors to equivalent vectors of legal type (which are converted back183 // before uses in subsequent blocks), to pack the bits into fewer physical184 // registers (used in CopyToReg/CopyFromReg pairs).185 LiveRegOptimizer LRO(*F.getParent(), ST);186 187 bool Changed = false;188 189 bool HasScalarSubwordLoads = ST.hasScalarSubwordLoads();190 191 for (auto &BB : reverse(F))192 for (Instruction &I : make_early_inc_range(reverse(BB))) {193 Changed |= !HasScalarSubwordLoads && visit(I);194 Changed |= LRO.optimizeLiveType(&I, DeadInsts);195 }196 197 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts);198 return Changed;199}200 201Type *LiveRegOptimizer::calculateConvertType(Type *OriginalType) {202 assert(OriginalType->getScalarSizeInBits() <=203 ConvertToScalar->getScalarSizeInBits());204 205 FixedVectorType *VTy = cast<FixedVectorType>(OriginalType);206 207 TypeSize OriginalSize = DL.getTypeSizeInBits(VTy);208 TypeSize ConvertScalarSize = DL.getTypeSizeInBits(ConvertToScalar);209 unsigned ConvertEltCount =210 (OriginalSize + ConvertScalarSize - 1) / ConvertScalarSize;211 212 if (OriginalSize <= ConvertScalarSize)213 return IntegerType::get(Mod.getContext(), ConvertScalarSize);214 215 return VectorType::get(Type::getIntNTy(Mod.getContext(), ConvertScalarSize),216 ConvertEltCount, false);217}218 219Value *LiveRegOptimizer::convertToOptType(Instruction *V,220 BasicBlock::iterator &InsertPt) {221 FixedVectorType *VTy = cast<FixedVectorType>(V->getType());222 Type *NewTy = calculateConvertType(V->getType());223 224 TypeSize OriginalSize = DL.getTypeSizeInBits(VTy);225 TypeSize NewSize = DL.getTypeSizeInBits(NewTy);226 227 IRBuilder<> Builder(V->getParent(), InsertPt);228 // If there is a bitsize match, we can fit the old vector into a new vector of229 // desired type.230 if (OriginalSize == NewSize)231 return Builder.CreateBitCast(V, NewTy, V->getName() + ".bc");232 233 // If there is a bitsize mismatch, we must use a wider vector.234 assert(NewSize > OriginalSize);235 uint64_t ExpandedVecElementCount = NewSize / VTy->getScalarSizeInBits();236 237 SmallVector<int, 8> ShuffleMask;238 uint64_t OriginalElementCount = VTy->getElementCount().getFixedValue();239 for (unsigned I = 0; I < OriginalElementCount; I++)240 ShuffleMask.push_back(I);241 242 for (uint64_t I = OriginalElementCount; I < ExpandedVecElementCount; I++)243 ShuffleMask.push_back(OriginalElementCount);244 245 Value *ExpandedVec = Builder.CreateShuffleVector(V, ShuffleMask);246 return Builder.CreateBitCast(ExpandedVec, NewTy, V->getName() + ".bc");247}248 249Value *LiveRegOptimizer::convertFromOptType(Type *ConvertType, Instruction *V,250 BasicBlock::iterator &InsertPt,251 BasicBlock *InsertBB) {252 FixedVectorType *NewVTy = cast<FixedVectorType>(ConvertType);253 254 TypeSize OriginalSize = DL.getTypeSizeInBits(V->getType());255 TypeSize NewSize = DL.getTypeSizeInBits(NewVTy);256 257 IRBuilder<> Builder(InsertBB, InsertPt);258 // If there is a bitsize match, we simply convert back to the original type.259 if (OriginalSize == NewSize)260 return Builder.CreateBitCast(V, NewVTy, V->getName() + ".bc");261 262 // If there is a bitsize mismatch, then we must have used a wider value to263 // hold the bits.264 assert(OriginalSize > NewSize);265 // For wide scalars, we can just truncate the value.266 if (!V->getType()->isVectorTy()) {267 Instruction *Trunc = cast<Instruction>(268 Builder.CreateTrunc(V, IntegerType::get(Mod.getContext(), NewSize)));269 return cast<Instruction>(Builder.CreateBitCast(Trunc, NewVTy));270 }271 272 // For wider vectors, we must strip the MSBs to convert back to the original273 // type.274 VectorType *ExpandedVT = VectorType::get(275 Type::getIntNTy(Mod.getContext(), NewVTy->getScalarSizeInBits()),276 (OriginalSize / NewVTy->getScalarSizeInBits()), false);277 Instruction *Converted =278 cast<Instruction>(Builder.CreateBitCast(V, ExpandedVT));279 280 unsigned NarrowElementCount = NewVTy->getElementCount().getFixedValue();281 SmallVector<int, 8> ShuffleMask(NarrowElementCount);282 std::iota(ShuffleMask.begin(), ShuffleMask.end(), 0);283 284 return Builder.CreateShuffleVector(Converted, ShuffleMask);285}286 287bool LiveRegOptimizer::optimizeLiveType(288 Instruction *I, SmallVectorImpl<WeakTrackingVH> &DeadInsts) {289 SmallVector<Instruction *, 4> Worklist;290 SmallPtrSet<PHINode *, 4> PhiNodes;291 SmallPtrSet<Instruction *, 4> Defs;292 SmallPtrSet<Instruction *, 4> Uses;293 SmallPtrSet<Instruction *, 4> Visited;294 295 Worklist.push_back(cast<Instruction>(I));296 while (!Worklist.empty()) {297 Instruction *II = Worklist.pop_back_val();298 299 if (!Visited.insert(II).second)300 continue;301 302 if (!shouldReplace(II->getType()))303 continue;304 305 if (!isCoercionProfitable(II))306 continue;307 308 if (PHINode *Phi = dyn_cast<PHINode>(II)) {309 PhiNodes.insert(Phi);310 // Collect all the incoming values of problematic PHI nodes.311 for (Value *V : Phi->incoming_values()) {312 // Repeat the collection process for newly found PHI nodes.313 if (PHINode *OpPhi = dyn_cast<PHINode>(V)) {314 if (!PhiNodes.count(OpPhi) && !Visited.count(OpPhi))315 Worklist.push_back(OpPhi);316 continue;317 }318 319 Instruction *IncInst = dyn_cast<Instruction>(V);320 // Other incoming value types (e.g. vector literals) are unhandled321 if (!IncInst && !isa<ConstantAggregateZero>(V))322 return false;323 324 // Collect all other incoming values for coercion.325 if (IncInst)326 Defs.insert(IncInst);327 }328 }329 330 // Collect all relevant uses.331 for (User *V : II->users()) {332 // Repeat the collection process for problematic PHI nodes.333 if (PHINode *OpPhi = dyn_cast<PHINode>(V)) {334 if (!PhiNodes.count(OpPhi) && !Visited.count(OpPhi))335 Worklist.push_back(OpPhi);336 continue;337 }338 339 Instruction *UseInst = cast<Instruction>(V);340 // Collect all uses of PHINodes and any use the crosses BB boundaries.341 if (UseInst->getParent() != II->getParent() || isa<PHINode>(II)) {342 Uses.insert(UseInst);343 if (!isa<PHINode>(II))344 Defs.insert(II);345 }346 }347 }348 349 // Coerce and track the defs.350 for (Instruction *D : Defs) {351 if (!ValMap.contains(D)) {352 BasicBlock::iterator InsertPt = std::next(D->getIterator());353 Value *ConvertVal = convertToOptType(D, InsertPt);354 assert(ConvertVal);355 ValMap[D] = ConvertVal;356 }357 }358 359 // Construct new-typed PHI nodes.360 for (PHINode *Phi : PhiNodes) {361 ValMap[Phi] = PHINode::Create(calculateConvertType(Phi->getType()),362 Phi->getNumIncomingValues(),363 Phi->getName() + ".tc", Phi->getIterator());364 }365 366 // Connect all the PHI nodes with their new incoming values.367 for (PHINode *Phi : PhiNodes) {368 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);369 bool MissingIncVal = false;370 for (int I = 0, E = Phi->getNumIncomingValues(); I < E; I++) {371 Value *IncVal = Phi->getIncomingValue(I);372 if (isa<ConstantAggregateZero>(IncVal)) {373 Type *NewType = calculateConvertType(Phi->getType());374 NewPhi->addIncoming(ConstantInt::get(NewType, 0, false),375 Phi->getIncomingBlock(I));376 } else if (Value *Val = ValMap.lookup(IncVal))377 NewPhi->addIncoming(Val, Phi->getIncomingBlock(I));378 else379 MissingIncVal = true;380 }381 if (MissingIncVal) {382 Value *DeadVal = ValMap[Phi];383 // The coercion chain of the PHI is broken. Delete the Phi384 // from the ValMap and any connected / user Phis.385 SmallVector<Value *, 4> PHIWorklist;386 SmallPtrSet<Value *, 4> VisitedPhis;387 PHIWorklist.push_back(DeadVal);388 while (!PHIWorklist.empty()) {389 Value *NextDeadValue = PHIWorklist.pop_back_val();390 VisitedPhis.insert(NextDeadValue);391 auto OriginalPhi =392 llvm::find_if(PhiNodes, [this, &NextDeadValue](PHINode *CandPhi) {393 return ValMap[CandPhi] == NextDeadValue;394 });395 // This PHI may have already been removed from maps when396 // unwinding a previous Phi397 if (OriginalPhi != PhiNodes.end())398 ValMap.erase(*OriginalPhi);399 400 DeadInsts.emplace_back(cast<Instruction>(NextDeadValue));401 402 for (User *U : NextDeadValue->users()) {403 if (!VisitedPhis.contains(cast<PHINode>(U)))404 PHIWorklist.push_back(U);405 }406 }407 } else {408 DeadInsts.emplace_back(cast<Instruction>(Phi));409 }410 }411 // Coerce back to the original type and replace the uses.412 for (Instruction *U : Uses) {413 // Replace all converted operands for a use.414 for (auto [OpIdx, Op] : enumerate(U->operands())) {415 if (Value *Val = ValMap.lookup(Op)) {416 Value *NewVal = nullptr;417 if (BBUseValMap.contains(U->getParent()) &&418 BBUseValMap[U->getParent()].contains(Val))419 NewVal = BBUseValMap[U->getParent()][Val];420 else {421 BasicBlock::iterator InsertPt = U->getParent()->getFirstNonPHIIt();422 // We may pick up ops that were previously converted for users in423 // other blocks. If there is an originally typed definition of the Op424 // already in this block, simply reuse it.425 if (isa<Instruction>(Op) && !isa<PHINode>(Op) &&426 U->getParent() == cast<Instruction>(Op)->getParent()) {427 NewVal = Op;428 } else {429 NewVal =430 convertFromOptType(Op->getType(), cast<Instruction>(ValMap[Op]),431 InsertPt, U->getParent());432 BBUseValMap[U->getParent()][ValMap[Op]] = NewVal;433 }434 }435 assert(NewVal);436 U->setOperand(OpIdx, NewVal);437 }438 }439 }440 441 return true;442}443 444bool AMDGPULateCodeGenPrepare::canWidenScalarExtLoad(LoadInst &LI) const {445 unsigned AS = LI.getPointerAddressSpace();446 // Skip non-constant address space.447 if (AS != AMDGPUAS::CONSTANT_ADDRESS &&448 AS != AMDGPUAS::CONSTANT_ADDRESS_32BIT)449 return false;450 // Skip non-simple loads.451 if (!LI.isSimple())452 return false;453 Type *Ty = LI.getType();454 // Skip aggregate types.455 if (Ty->isAggregateType())456 return false;457 unsigned TySize = DL.getTypeStoreSize(Ty);458 // Only handle sub-DWORD loads.459 if (TySize >= 4)460 return false;461 // That load must be at least naturally aligned.462 if (LI.getAlign() < DL.getABITypeAlign(Ty))463 return false;464 // It should be uniform, i.e. a scalar load.465 return UA.isUniform(&LI);466}467 468bool AMDGPULateCodeGenPrepare::visitLoadInst(LoadInst &LI) {469 if (!WidenLoads)470 return false;471 472 // Skip if that load is already aligned on DWORD at least as it's handled in473 // SDAG.474 if (LI.getAlign() >= 4)475 return false;476 477 if (!canWidenScalarExtLoad(LI))478 return false;479 480 int64_t Offset = 0;481 auto *Base =482 GetPointerBaseWithConstantOffset(LI.getPointerOperand(), Offset, DL);483 // If that base is not DWORD aligned, it's not safe to perform the following484 // transforms.485 if (!isDWORDAligned(Base))486 return false;487 488 int64_t Adjust = Offset & 0x3;489 if (Adjust == 0) {490 // With a zero adjust, the original alignment could be promoted with a491 // better one.492 LI.setAlignment(Align(4));493 return true;494 }495 496 IRBuilder<> IRB(&LI);497 IRB.SetCurrentDebugLocation(LI.getDebugLoc());498 499 unsigned LdBits = DL.getTypeStoreSizeInBits(LI.getType());500 auto *IntNTy = Type::getIntNTy(LI.getContext(), LdBits);501 502 auto *NewPtr = IRB.CreateConstGEP1_64(503 IRB.getInt8Ty(),504 IRB.CreateAddrSpaceCast(Base, LI.getPointerOperand()->getType()),505 Offset - Adjust);506 507 LoadInst *NewLd = IRB.CreateAlignedLoad(IRB.getInt32Ty(), NewPtr, Align(4));508 NewLd->copyMetadata(LI);509 NewLd->setMetadata(LLVMContext::MD_range, nullptr);510 511 unsigned ShAmt = Adjust * 8;512 Value *NewVal = IRB.CreateBitCast(513 IRB.CreateTrunc(IRB.CreateLShr(NewLd, ShAmt),514 DL.typeSizeEqualsStoreSize(LI.getType()) ? IntNTy515 : LI.getType()),516 LI.getType());517 LI.replaceAllUsesWith(NewVal);518 DeadInsts.emplace_back(&LI);519 520 return true;521}522 523PreservedAnalyses524AMDGPULateCodeGenPreparePass::run(Function &F, FunctionAnalysisManager &FAM) {525 const GCNSubtarget &ST = TM.getSubtarget<GCNSubtarget>(F);526 AssumptionCache &AC = FAM.getResult<AssumptionAnalysis>(F);527 UniformityInfo &UI = FAM.getResult<UniformityInfoAnalysis>(F);528 529 bool Changed = AMDGPULateCodeGenPrepare(F, ST, &AC, UI).run();530 531 if (!Changed)532 return PreservedAnalyses::all();533 PreservedAnalyses PA = PreservedAnalyses::none();534 PA.preserveSet<CFGAnalyses>();535 return PA;536}537 538class AMDGPULateCodeGenPrepareLegacy : public FunctionPass {539public:540 static char ID;541 542 AMDGPULateCodeGenPrepareLegacy() : FunctionPass(ID) {}543 544 StringRef getPassName() const override {545 return "AMDGPU IR late optimizations";546 }547 548 void getAnalysisUsage(AnalysisUsage &AU) const override {549 AU.addRequired<TargetPassConfig>();550 AU.addRequired<AssumptionCacheTracker>();551 AU.addRequired<UniformityInfoWrapperPass>();552 // Invalidates UniformityInfo553 AU.setPreservesCFG();554 }555 556 bool runOnFunction(Function &F) override;557};558 559bool AMDGPULateCodeGenPrepareLegacy::runOnFunction(Function &F) {560 if (skipFunction(F))561 return false;562 563 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();564 const TargetMachine &TM = TPC.getTM<TargetMachine>();565 const GCNSubtarget &ST = TM.getSubtarget<GCNSubtarget>(F);566 567 AssumptionCache &AC =568 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);569 UniformityInfo &UI =570 getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();571 572 return AMDGPULateCodeGenPrepare(F, ST, &AC, UI).run();573}574 575INITIALIZE_PASS_BEGIN(AMDGPULateCodeGenPrepareLegacy, DEBUG_TYPE,576 "AMDGPU IR late optimizations", false, false)577INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)578INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)579INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass)580INITIALIZE_PASS_END(AMDGPULateCodeGenPrepareLegacy, DEBUG_TYPE,581 "AMDGPU IR late optimizations", false, false)582 583char AMDGPULateCodeGenPrepareLegacy::ID = 0;584 585FunctionPass *llvm::createAMDGPULateCodeGenPrepareLegacyPass() {586 return new AMDGPULateCodeGenPrepareLegacy();587}588