From e3b557809604d036af6e00c60f012c2025b59a5e Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Sat, 11 Feb 2023 13:38:04 +0100 Subject: Vendor import of llvm-project main llvmorg-16-init-18548-gb0daacf58f41, the last commit before the upstream release/17.x branch was created. --- llvm/lib/CodeGen/TypePromotion.cpp | 246 +++++++++++++++++++++++++------------ 1 file changed, 170 insertions(+), 76 deletions(-) (limited to 'llvm/lib/CodeGen/TypePromotion.cpp') diff --git a/llvm/lib/CodeGen/TypePromotion.cpp b/llvm/lib/CodeGen/TypePromotion.cpp index 8dc8d381ad16..e6c0b3242d67 100644 --- a/llvm/lib/CodeGen/TypePromotion.cpp +++ b/llvm/lib/CodeGen/TypePromotion.cpp @@ -15,8 +15,10 @@ /// //===----------------------------------------------------------------------===// +#include "llvm/CodeGen/TypePromotion.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/TargetLowering.h" @@ -106,9 +108,9 @@ class IRPromoter { SetVector &Sources; SetVector &Sinks; SmallPtrSetImpl &SafeWrap; + SmallPtrSetImpl &InstsToRemove; IntegerType *ExtTy = nullptr; SmallPtrSet NewInsts; - SmallPtrSet InstsToRemove; DenseMap> TruncTysMap; SmallPtrSet Promoted; @@ -120,25 +122,26 @@ class IRPromoter { void Cleanup(); public: - IRPromoter(LLVMContext &C, unsigned Width, - SetVector &visited, SetVector &sources, - SetVector &sinks, - SmallPtrSetImpl &wrap) - : Ctx(C), PromotedWidth(Width), Visited(visited), - Sources(sources), Sinks(sinks), SafeWrap(wrap) { + IRPromoter(LLVMContext &C, unsigned Width, SetVector &visited, + SetVector &sources, SetVector &sinks, + SmallPtrSetImpl &wrap, + SmallPtrSetImpl &instsToRemove) + : Ctx(C), PromotedWidth(Width), Visited(visited), Sources(sources), + Sinks(sinks), SafeWrap(wrap), InstsToRemove(instsToRemove) { ExtTy = IntegerType::get(Ctx, PromotedWidth); } void Mutate(); }; -class TypePromotion : public FunctionPass { +class TypePromotionImpl { unsigned TypeSize = 0; LLVMContext *Ctx = nullptr; unsigned RegisterBitWidth = 0; SmallPtrSet AllVisited; SmallPtrSet SafeToPromote; SmallPtrSet SafeWrap; + SmallPtrSet InstsToRemove; // Does V have the same size result type as TypeSize. bool EqualTypeSize(Value *V); @@ -166,17 +169,25 @@ class TypePromotion : public FunctionPass { // Is V an instruction thats result can trivially promoted, or has safe // wrapping. bool isLegalToPromote(Value *V); - bool TryToPromote(Value *V, unsigned PromotedWidth); + bool TryToPromote(Value *V, unsigned PromotedWidth, const LoopInfo &LI); + +public: + bool run(Function &F, const TargetMachine *TM, + const TargetTransformInfo &TTI, const LoopInfo &LI); +}; +class TypePromotionLegacy : public FunctionPass { public: static char ID; - TypePromotion() : FunctionPass(ID) {} + TypePromotionLegacy() : FunctionPass(ID) {} void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.setPreservesCFG(); + AU.addPreserved(); } StringRef getPassName() const override { return PASS_NAME; } @@ -192,19 +203,19 @@ static bool GenerateSignBits(Instruction *I) { Opc == Instruction::SRem || Opc == Instruction::SExt; } -bool TypePromotion::EqualTypeSize(Value *V) { +bool TypePromotionImpl::EqualTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() == TypeSize; } -bool TypePromotion::LessOrEqualTypeSize(Value *V) { +bool TypePromotionImpl::LessOrEqualTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() <= TypeSize; } -bool TypePromotion::GreaterThanTypeSize(Value *V) { +bool TypePromotionImpl::GreaterThanTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() > TypeSize; } -bool TypePromotion::LessThanTypeSize(Value *V) { +bool TypePromotionImpl::LessThanTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() < TypeSize; } @@ -215,7 +226,7 @@ bool TypePromotion::LessThanTypeSize(Value *V) { /// return values because we only accept ones that guarantee a zeroext ret val. /// Many arguments will have the zeroext attribute too, so those would be free /// too. -bool TypePromotion::isSource(Value *V) { +bool TypePromotionImpl::isSource(Value *V) { if (!isa(V->getType())) return false; @@ -236,7 +247,7 @@ bool TypePromotion::isSource(Value *V) { /// Return true if V will require any promoted values to be truncated for the /// the IR to remain valid. We can't mutate the value type of these /// instructions. -bool TypePromotion::isSink(Value *V) { +bool TypePromotionImpl::isSink(Value *V) { // TODO The truncate also isn't actually necessary because we would already // proved that the data value is kept within the range of the original data // type. We currently remove any truncs inserted for handling zext sinks. @@ -262,7 +273,7 @@ bool TypePromotion::isSink(Value *V) { } /// Return whether this instruction can safely wrap. -bool TypePromotion::isSafeWrap(Instruction *I) { +bool TypePromotionImpl::isSafeWrap(Instruction *I) { // We can support a potentially wrapping instruction (I) if: // - It is only used by an unsigned icmp. // - The icmp uses a constant. @@ -368,7 +379,7 @@ bool TypePromotion::isSafeWrap(Instruction *I) { return false; } -bool TypePromotion::shouldPromote(Value *V) { +bool TypePromotionImpl::shouldPromote(Value *V) { if (!isa(V->getType()) || isSink(V)) return false; @@ -551,8 +562,13 @@ void IRPromoter::TruncateSinks() { } // Don't insert a trunc for a zext which can still legally promote. + // Nor insert a trunc when the input value to that trunc has the same width + // as the zext we are inserting it for. When this happens the input operand + // for the zext will be promoted to the same width as the zext's return type + // rendering that zext unnecessary. This zext gets removed before the end + // of the pass. if (auto ZExt = dyn_cast(I)) - if (ZExt->getType()->getScalarSizeInBits() > PromotedWidth) + if (ZExt->getType()->getScalarSizeInBits() >= PromotedWidth) continue; // Now handle the others. @@ -569,7 +585,7 @@ void IRPromoter::TruncateSinks() { void IRPromoter::Cleanup() { LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n"); // Some zexts will now have become redundant, along with their trunc - // operands, so remove them + // operands, so remove them. for (auto *V : Visited) { if (!isa(V)) continue; @@ -599,7 +615,6 @@ void IRPromoter::Cleanup() { for (auto *I : InstsToRemove) { LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n"); I->dropAllReferences(); - I->eraseFromParent(); } } @@ -620,6 +635,8 @@ void IRPromoter::ConvertTruncs() { ConstantInt *Mask = ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue()); Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask); + if (SrcTy != ExtTy) + Masked = Builder.CreateTrunc(Masked, ExtTy); if (auto *I = dyn_cast(Masked)) NewInsts.insert(I); @@ -673,7 +690,7 @@ void IRPromoter::Mutate() { /// We disallow booleans to make life easier when dealing with icmps but allow /// any other integer that fits in a scalar register. Void types are accepted /// so we can handle switches. -bool TypePromotion::isSupportedType(Value *V) { +bool TypePromotionImpl::isSupportedType(Value *V) { Type *Ty = V->getType(); // Allow voids and pointers, these won't be promoted. @@ -691,7 +708,7 @@ bool TypePromotion::isSupportedType(Value *V) { /// Disallow casts other than zext and truncs and only allow calls if their /// return value is zeroext. We don't allow opcodes that can introduce sign /// bits. -bool TypePromotion::isSupportedValue(Value *V) { +bool TypePromotionImpl::isSupportedValue(Value *V) { if (auto *I = dyn_cast(V)) { switch (I->getOpcode()) { default: @@ -739,7 +756,7 @@ bool TypePromotion::isSupportedValue(Value *V) { /// Check that the type of V would be promoted and that the original type is /// smaller than the targeted promoted type. Check that we're not trying to /// promote something larger than our base 'TypeSize' type. -bool TypePromotion::isLegalToPromote(Value *V) { +bool TypePromotionImpl::isLegalToPromote(Value *V) { auto *I = dyn_cast(V); if (!I) return true; @@ -754,9 +771,10 @@ bool TypePromotion::isLegalToPromote(Value *V) { return false; } -bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) { +bool TypePromotionImpl::TryToPromote(Value *V, unsigned PromotedWidth, + const LoopInfo &LI) { Type *OrigTy = V->getType(); - TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedSize(); + TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedValue(); SafeToPromote.clear(); SafeWrap.clear(); @@ -848,95 +866,134 @@ bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) { unsigned ToPromote = 0; unsigned NonFreeArgs = 0; + unsigned NonLoopSources = 0, LoopSinks = 0; SmallPtrSet Blocks; - for (auto *V : CurrentVisited) { - if (auto *I = dyn_cast(V)) + for (auto *CV : CurrentVisited) { + if (auto *I = dyn_cast(CV)) Blocks.insert(I->getParent()); - if (Sources.count(V)) { - if (auto *Arg = dyn_cast(V)) + if (Sources.count(CV)) { + if (auto *Arg = dyn_cast(CV)) if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr()) ++NonFreeArgs; + if (!isa(CV) || + !LI.getLoopFor(cast(CV)->getParent())) + ++NonLoopSources; continue; } - if (Sinks.count(cast(V))) + if (isa(CV)) + continue; + if (LI.getLoopFor(cast(CV)->getParent())) + ++LoopSinks; + if (Sinks.count(cast(CV))) continue; ++ToPromote; } // DAG optimizations should be able to handle these cases better, especially // for function arguments. - if (ToPromote < 2 || (Blocks.size() == 1 && (NonFreeArgs > SafeWrap.size()))) + if (!isa(V) && !(LoopSinks && NonLoopSources) && + (ToPromote < 2 || (Blocks.size() == 1 && NonFreeArgs > SafeWrap.size()))) return false; IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks, - SafeWrap); + SafeWrap, InstsToRemove); Promoter.Mutate(); return true; } -bool TypePromotion::runOnFunction(Function &F) { - if (skipFunction(F) || DisablePromotion) +bool TypePromotionImpl::run(Function &F, const TargetMachine *TM, + const TargetTransformInfo &TTI, + const LoopInfo &LI) { + if (DisablePromotion) return false; LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n"); - auto *TPC = getAnalysisIfAvailable(); - if (!TPC) - return false; - AllVisited.clear(); SafeToPromote.clear(); SafeWrap.clear(); bool MadeChange = false; const DataLayout &DL = F.getParent()->getDataLayout(); - const TargetMachine &TM = TPC->getTM(); - const TargetSubtargetInfo *SubtargetInfo = TM.getSubtargetImpl(F); + const TargetSubtargetInfo *SubtargetInfo = TM->getSubtargetImpl(F); const TargetLowering *TLI = SubtargetInfo->getTargetLowering(); - const TargetTransformInfo &TII = - getAnalysis().getTTI(F); RegisterBitWidth = - TII.getRegisterBitWidth(TargetTransformInfo::RGK_Scalar).getFixedSize(); + TTI.getRegisterBitWidth(TargetTransformInfo::RGK_Scalar).getFixedValue(); Ctx = &F.getParent()->getContext(); - // Search up from icmps to try to promote their operands. + // Return the preferred integer width of the instruction, or zero if we + // shouldn't try. + auto GetPromoteWidth = [&](Instruction *I) -> uint32_t { + if (!isa(I->getType())) + return 0; + + EVT SrcVT = TLI->getValueType(DL, I->getType()); + if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT())) + return 0; + + if (TLI->getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger) + return 0; + + EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT); + if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) { + LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register " + << "for promoted type\n"); + return 0; + } + + // TODO: Should we prefer to use RegisterBitWidth instead? + return PromotedVT.getFixedSizeInBits(); + }; + + auto BBIsInLoop = [&](BasicBlock *BB) -> bool { + for (auto *L : LI) + if (L->contains(BB)) + return true; + return false; + }; + for (BasicBlock &BB : F) { for (Instruction &I : BB) { if (AllVisited.count(&I)) continue; - if (!isa(&I)) - continue; - - auto *ICmp = cast(&I); - // Skip signed or pointer compares - if (ICmp->isSigned() || !isa(ICmp->getOperand(0)->getType())) - continue; - - LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n"); - - for (auto &Op : ICmp->operands()) { - if (auto *I = dyn_cast(Op)) { - EVT SrcVT = TLI->getValueType(DL, I->getType()); - if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT())) - break; - - if (TLI->getTypeAction(*Ctx, SrcVT) != - TargetLowering::TypePromoteInteger) - break; - EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT); - if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) { - LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register " - << "for promoted type\n"); - break; + if (isa(&I) && isa(I.getOperand(0)) && + isa(I.getType()) && BBIsInLoop(&BB)) { + LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << I.getOperand(0) + << "\n"); + EVT ZExtVT = TLI->getValueType(DL, I.getType()); + Instruction *Phi = static_cast(I.getOperand(0)); + auto PromoteWidth = ZExtVT.getFixedSizeInBits(); + if (RegisterBitWidth < PromoteWidth) { + LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target " + << "register for ZExt type\n"); + continue; + } + MadeChange |= TryToPromote(Phi, PromoteWidth, LI); + } else if (auto *ICmp = dyn_cast(&I)) { + // Search up from icmps to try to promote their operands. + // Skip signed or pointer compares + if (ICmp->isSigned()) + continue; + + LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n"); + + for (auto &Op : ICmp->operands()) { + if (auto *OpI = dyn_cast(Op)) { + if (auto PromotedWidth = GetPromoteWidth(OpI)) { + MadeChange |= TryToPromote(OpI, PromotedWidth, LI); + break; + } } - - MadeChange |= TryToPromote(I, PromotedVT.getFixedSizeInBits()); - break; } } } + if (!InstsToRemove.empty()) { + for (auto *I : InstsToRemove) + I->eraseFromParent(); + InstsToRemove.clear(); + } } AllVisited.clear(); @@ -946,9 +1003,46 @@ bool TypePromotion::runOnFunction(Function &F) { return MadeChange; } -INITIALIZE_PASS_BEGIN(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false) -INITIALIZE_PASS_END(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false) +INITIALIZE_PASS_BEGIN(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_END(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false) + +char TypePromotionLegacy::ID = 0; -char TypePromotion::ID = 0; +bool TypePromotionLegacy::runOnFunction(Function &F) { + if (skipFunction(F)) + return false; -FunctionPass *llvm::createTypePromotionPass() { return new TypePromotion(); } + auto *TPC = getAnalysisIfAvailable(); + if (!TPC) + return false; + + auto *TM = &TPC->getTM(); + auto &TTI = getAnalysis().getTTI(F); + auto &LI = getAnalysis().getLoopInfo(); + + TypePromotionImpl TP; + return TP.run(F, TM, TTI, LI); +} + +FunctionPass *llvm::createTypePromotionLegacyPass() { + return new TypePromotionLegacy(); +} + +PreservedAnalyses TypePromotionPass::run(Function &F, + FunctionAnalysisManager &AM) { + auto &TTI = AM.getResult(F); + auto &LI = AM.getResult(F); + TypePromotionImpl TP; + + bool Changed = TP.run(F, TM, TTI, LI); + if (!Changed) + return PreservedAnalyses::all(); + + PreservedAnalyses PA; + PA.preserveSet(); + PA.preserve(); + return PA; +} -- cgit v1.2.3