diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -789,10 +789,25 @@ identifyDefaultAbstractAttributes(const_cast(F)); } - /// Record that \p I is deleted after information was manifested. + /// Record that \p U is to be replaces with \p NV after information was + /// manifested. This also triggers deletion of trivially dead istructions. + bool changeUseAfterManifest(Use &U, Value &NV) { + Value *&V = ToBeChangedUses[&U]; + if (V && (V->stripPointerCasts() == NV.stripPointerCasts() || + isa_and_nonnull(V))) + return false; + assert((!V || V == &NV || isa(NV)) && + "Use was registered twice for replacement with different values!"); + V = &NV; + return true; + } + + /// Record that \p I is deleted after information was manifested. This also + /// triggers deletion of trivially dead istructions. void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); } - /// Record that \p BB is deleted after information was manifested. + /// Record that \p BB is deleted after information was manifested. This also + /// triggers deletion of trivially dead istructions. void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); } /// Record that \p F is deleted after information was manifested. @@ -803,6 +818,13 @@ /// If \p LivenessAA is not provided it is queried. bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA); + /// Check \p Pred on all (transitive) uses of \p V. + /// + /// This method will evaluate \p Pred on all (transitive) uses of the + /// associated value and return true if \p Pred holds every time. + bool checkForAllUses(const function_ref &Pred, + const AbstractAttribute &QueryingAA, const Value &V); + /// Check \p Pred on all function call sites. /// /// This method will evaluate \p Pred on call sites and return @@ -972,6 +994,10 @@ /// A set to remember the functions we already assume to be live and visited. DenseSet VisitedFunctions; + /// Uses we replace with a new value after manifest is done. We will remove + /// then trivially dead instructions as well. + DenseMap ToBeChangedUses; + /// Functions, blocks, and instructions we delete after manifest is done. /// ///{ @@ -1683,6 +1709,9 @@ public IRPosition { AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {} + /// Returns true if the underlying value is assumed dead. + virtual bool isAssumedDead() const = 0; + /// Returns true if \p BB is assumed dead. virtual bool isAssumedDead(const BasicBlock *BB) const = 0; diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -2095,9 +2095,204 @@ /// -------------------AAIsDead Function Attribute----------------------- -struct AAIsDeadImpl : public AAIsDead { - AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {} +struct AAIsDeadValueImpl : public AAIsDead { + AAIsDeadValueImpl(const IRPosition &IRP) : AAIsDead(IRP) {} + /// See AAIsDead::isAssumedDead(). + bool isAssumedDead() const override { return getAssumed(); } + + /// See AAIsDead::isAssumedDead(BasicBlock *). + bool isAssumedDead(const BasicBlock *BB) const override { return false; } + + /// See AAIsDead::isKnownDead(BasicBlock *). + bool isKnownDead(const BasicBlock *BB) const override { return false; } + + /// See AAIsDead::isAssumedDead(Instruction *I). + bool isAssumedDead(const Instruction *I) const override { + return I == getCtxI() && isAssumedDead(); + } + + /// See AAIsDead::isKnownDead(Instruction *I). + bool isKnownDead(const Instruction *I) const override { + return I == getCtxI() && getKnown(); + } + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return isAssumedDead() ? "assumed-dead" : "assumed-live"; + } +}; + +struct AAIsDeadFloating : public AAIsDeadValueImpl { + AAIsDeadFloating(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (Instruction *I = dyn_cast(&getAssociatedValue())) + if (!wouldInstructionBeTriviallyDead(I)) + indicatePessimisticFixpoint(); + if (isa(getAssociatedValue())) + indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + auto UsePred = [&](const Use &U, bool &Follow) { + Instruction *UserI = cast(U.getUser()); + if (CallSite CS = CallSite(UserI)) { + if (!CS.isArgOperand(&U)) + return false; + const IRPosition &CSArgPos = + IRPosition::callsite_argument(CS, CS.getArgumentNo(&U)); + const auto &CSArgIsDead = A.getAAFor(*this, CSArgPos); + return CSArgIsDead.isAssumedDead(); + } + if (ReturnInst *RI = dyn_cast(UserI)) { + const IRPosition &RetPos = IRPosition::returned(*RI->getFunction()); + const auto &RetIsDeadAA = A.getAAFor(*this, RetPos); + return RetIsDeadAA.isAssumedDead(); + } + Follow = true; + return wouldInstructionBeTriviallyDead(UserI); + }; + + if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + Value &V = getAssociatedValue(); + if (auto *I = dyn_cast(&V)) + if (wouldInstructionBeTriviallyDead(I)) { + A.deleteAfterManifest(*I); + return ChangeStatus::CHANGED; + } + + if (V.use_empty()) + return ChangeStatus::UNCHANGED; + + UndefValue &UV = *UndefValue::get(V.getType()); + bool AnyChange = false; + for (Use &U : V.uses()) + AnyChange |= A.changeUseAfterManifest(U, UV); + return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(IsDead) + } +}; + +struct AAIsDeadArgument : public AAIsDeadFloating { + AAIsDeadArgument(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (!getAssociatedFunction()->hasExactDefinition()) + indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) } +}; + +struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl { + AAIsDeadCallSiteArgument(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (isa(getAssociatedValue())) + indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Once we have call site specific value information we can provide + // call site specific liveness information and then it makes + // sense to specialize attributes for call sites arguments instead of + // redirecting requests to the callee argument. + Argument *Arg = getAssociatedArgument(); + if (!Arg) + return indicatePessimisticFixpoint(); + const IRPosition &ArgPos = IRPosition::argument(*Arg); + auto &ArgAA = A.getAAFor(*this, ArgPos); + return clampStateAndIndicateChange( + getState(), static_cast(ArgAA.getState())); + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + CallBase &CB = cast(getAnchorValue()); + Use &U = CB.getArgOperandUse(getArgNo()); + assert(!isa(U.get()) && + "Expected undef values to be filtered out!"); + UndefValue &UV = *UndefValue::get(U->getType()); + if (A.changeUseAfterManifest(U, UV)) + return ChangeStatus::CHANGED; + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) } +}; + +struct AAIsDeadReturned : public AAIsDeadValueImpl { + AAIsDeadReturned(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + + auto PredForCallSite = [&](AbstractCallSite ACS) { + if (ACS.isCallbackCall()) + return false; + const IRPosition &CSRetPos = + IRPosition::callsite_returned(ACS.getCallSite()); + const auto &RetIsDeadAA = A.getAAFor(*this, CSRetPos); + return RetIsDeadAA.isAssumedDead(); + }; + + if (!A.checkForAllCallSites(PredForCallSite, *this, true)) + return indicatePessimisticFixpoint(); + + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + // TODO: Rewrite the signature to return void? + bool AnyChange = false; + UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType()); + auto RetInstPred = [&](Instruction &I) { + ReturnInst &RI = cast(I); + if (!isa(RI.getReturnValue())) + AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV); + return true; + }; + A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret}); + return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) } +}; + +struct AAIsDeadCallSiteReturned : public AAIsDeadFloating { + AAIsDeadCallSiteReturned(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(IsDead) } +}; + +struct AAIsDeadFunction : public AAIsDead { + AAIsDeadFunction(const IRPosition &IRP) : AAIsDead(IRP) {} + + /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { const Function *F = getAssociatedFunction(); if (F && !F->isDeclaration()) @@ -2231,6 +2426,12 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override {} + + /// Returns true if the function is assumed dead. + bool isAssumedDead() const override { return false; } + /// See AAIsDead::isAssumedDead(BasicBlock *). bool isAssumedDead(const BasicBlock *BB) const override { assert(BB->getParent() == getAssociatedFunction() && @@ -2303,18 +2504,7 @@ SmallSetVector NoReturnCalls; }; -struct AAIsDeadFunction final : public AAIsDeadImpl { - AAIsDeadFunction(const IRPosition &IRP) : AAIsDeadImpl(IRP) {} - - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { - STATS_DECL(PartiallyDeadBlocks, Function, - "Number of basic blocks classified as partially dead"); - BUILD_STAT_NAME(PartiallyDeadBlocks, Function) += NoReturnCalls.size(); - } -}; - -bool AAIsDeadImpl::isAfterNoReturn(const Instruction *I) const { +bool AAIsDeadFunction::isAfterNoReturn(const Instruction *I) const { const Instruction *PrevI = I->getPrevNode(); while (PrevI) { if (NoReturnCalls.count(PrevI)) @@ -2324,8 +2514,8 @@ return false; } -const Instruction *AAIsDeadImpl::findNextNoReturn(Attributor &A, - const Instruction *I) { +const Instruction *AAIsDeadFunction::findNextNoReturn(Attributor &A, + const Instruction *I) { const BasicBlock *BB = I->getParent(); const Function &F = *BB->getParent(); @@ -2374,7 +2564,7 @@ return nullptr; } -ChangeStatus AAIsDeadImpl::updateImpl(Attributor &A) { +ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { ChangeStatus Status = ChangeStatus::UNCHANGED; // Temporary collection to iterate over existing noreturn instructions. This @@ -2423,8 +2613,8 @@ } /// Liveness information for a call sites. -struct AAIsDeadCallSite final : AAIsDeadImpl { - AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadImpl(IRP) {} +struct AAIsDeadCallSite final : AAIsDeadFunction { + AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadFunction(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { @@ -4249,6 +4439,8 @@ if (!CtxI) return false; + // TODO: Find a good way to utilize fine and coarse grained liveness + // information. if (!LivenessAA) LivenessAA = &getAAFor(AA, IRPosition::function(*CtxI->getFunction()), @@ -4267,6 +4459,58 @@ return true; } +bool Attributor::checkForAllUses( + const function_ref &Pred, + const AbstractAttribute &QueryingAA, const Value &V) { + const IRPosition &IRP = QueryingAA.getIRPosition(); + SmallVector Worklist; + SmallPtrSet Visited; + + for (const Use &U : V.uses()) + Worklist.push_back(&U); + + LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size() + << " initial uses to check\n"); + + if (Worklist.empty()) + return true; + + bool AnyDead = false; + const Function *ScopeFn = IRP.getAnchorScope(); + const auto *LivenessAA = + ScopeFn ? &getAAFor(QueryingAA, IRPosition::function(*ScopeFn), + /* TrackDependence */ false) + : nullptr; + + while (!Worklist.empty()) { + const Use *U = Worklist.pop_back_val(); + if (!Visited.insert(U).second) + continue; + LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << "\n"); + if (Instruction *UserI = dyn_cast(U->getUser())) + if (LivenessAA && LivenessAA->isAssumedDead(UserI)) { + LLVM_DEBUG(dbgs() << "[Attributor] Dead user: " << *UserI << ": " + << static_cast(*LivenessAA) + << "\n"); + AnyDead = true; + continue; + } + + bool Follow = false; + if (!Pred(*U, Follow)) + return false; + if (!Follow) + continue; + for (const Use &UU : U->getUser()->uses()) + Worklist.push_back(&UU); + } + + if (AnyDead) + recordDependence(*LivenessAA, QueryingAA); + + return true; +} + bool Attributor::checkForAllCallSites( const function_ref &Pred, const AbstractAttribute &QueryingAA, bool RequireAllCallSites) { @@ -4633,13 +4877,48 @@ LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " << ToBeDeletedFunctions.size() << " functions and " << ToBeDeletedBlocks.size() << " blocks and " - << ToBeDeletedInsts.size() << " instructions\n"); + << ToBeDeletedInsts.size() << " instructions and " + << ToBeChangedUses.size() << " uses\n"); + + SmallVector DeadInsts; + SmallVector TerminatorsToFold; + SmallVector UnreachablesToInsert; + + for (auto &It : ToBeChangedUses) { + Use *U = It.first; + Value *NewV = It.second; + Value *OldV = U->get(); + LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() + << " instead of " << *OldV << "\n"); + U->set(NewV); + if (Instruction *I = dyn_cast(OldV)) + if (!isa(I) && !ToBeDeletedInsts.count(I) && isInstructionTriviallyDead(I)) { + DeadInsts.push_back(I); + } + if (isa(NewV) && isa(U->getUser())) { + Instruction *UserI = cast(U->getUser()); + if (isa(NewV)) { + UnreachablesToInsert.push_back(UserI); + } else { + TerminatorsToFold.push_back(UserI); + } + } + } + for (Instruction *I : UnreachablesToInsert) + changeToUnreachable(I, /* UseLLVMTrap */ false); + for (Instruction *I : TerminatorsToFold) + ConstantFoldTerminator(I->getParent()); + for (Instruction *I : ToBeDeletedInsts) { - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - I->eraseFromParent(); + I->replaceAllUsesWith(UndefValue::get(I->getType())); + if (!isa(I) && isInstructionTriviallyDead(I)) + DeadInsts.push_back(I); + else + I->eraseFromParent(); } + RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); + if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { SmallVector ToBeDeletedBBs; ToBeDeletedBBs.reserve(NumDeadBlocks); @@ -4676,14 +4955,12 @@ if (!F) continue; - const auto *LivenessAA = - lookupAAFor(IRPosition::function(*F)); - if (LivenessAA && - !checkForAllCallSites([](AbstractCallSite ACS) { return false; }, - *LivenessAA, true)) + if (!checkForAllCallSites([](AbstractCallSite ACS) { return false; }, + *F, true, nullptr)) continue; STATS_TRACK(AAIsDead, Function); + ToBeDeletedFunctions.insert(F); F->replaceAllUsesWith(UndefValue::get(F->getType())); F->eraseFromParent(); InternalFns[u] = nullptr; @@ -4800,6 +5077,9 @@ IRPosition RetPos = IRPosition::returned(F); + // Every returned value might be dead. + getOrCreateAAFor(RetPos); + // Every function might be simplified. getOrCreateAAFor(RetPos); @@ -4850,11 +5130,21 @@ auto CallSitePred = [&](Instruction &I) -> bool { CallSite CS(&I); - if (CS.getCalledFunction()) { - for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) { + if (Function *Callee = CS.getCalledFunction()) { + if (!Callee->getReturnType()->isVoidTy()) { + IRPosition CSRetPos = IRPosition::callsite_returned(CS); + + // Call site return values might be dead. + getOrCreateAAFor(CSRetPos); + } + + for (int i = 0, e = Callee->arg_size(); i < e; i++) { IRPosition CSArgPos = IRPosition::callsite_argument(CS, i); + // Every call site argument might be dead. + getOrCreateAAFor(CSArgPos); + // Call site argument might be simplified. getOrCreateAAFor(CSArgPos); @@ -5156,7 +5446,6 @@ CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoRecurse) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAWillReturn) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn) -CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull) @@ -5166,6 +5455,7 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) +CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack) diff --git a/llvm/test/Transforms/FunctionAttrs/align.ll b/llvm/test/Transforms/FunctionAttrs/align.ll --- a/llvm/test/Transforms/FunctionAttrs/align.ll +++ b/llvm/test/Transforms/FunctionAttrs/align.ll @@ -1,3 +1,4 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" @@ -83,14 +84,11 @@ ; Function Attrs: nounwind readnone ssp uwtable define internal i8* @f1(i8* readnone %0) local_unnamed_addr #0 { -; ATTRIBUTOR: define internal nonnull align 8 dereferenceable(1) i8* @f1(i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" %0) %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 ;