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 @@ -815,10 +815,16 @@ identifyDefaultAbstractAttributes(const_cast(F)); } - /// Record that \p I is deleted after information was manifested. + /// Record that \p U is to be replaces with undef after information was + /// manifested. This also triggers deletion of trivially dead istructions. + void makeUndefAfterManifest(Use &U) { ToBeMadeUndef.insert(&U); } + + /// 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. @@ -829,6 +835,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 the associated value. + /// + /// 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); + /// Check \p Pred on all function call sites. /// /// This method will evaluate \p Pred on call sites and return @@ -995,6 +1008,10 @@ /// A set to remember the functions we already assume to be live and visited. DenseSet VisitedFunctions; + /// Uses we replace with undef after manifest is done. We will remove + /// trivially dead instructions as well. + SmallPtrSet ToBeMadeUndef; + /// Functions, blocks, and instructions we delete after manifest is done. /// ///{ @@ -1596,6 +1613,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 @@ -2159,9 +2159,178 @@ /// -------------------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::isAssumed(Instruction *I). + bool isAssumedDead(const Instruction *I) const override { return false; } + + /// See AAIsDead::isKnownDead(Instruction *I). + bool isKnownDead(const Instruction *I) const override { return false; } + + /// 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(); + } + + /// 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)) { + 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)) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + Value &V = getAssociatedValue(); + if (V.use_empty()) + return ChangeStatus::UNCHANGED; + + for (Use &U : V.uses()) + A.makeUndefAfterManifest(U); + return ChangeStatus::CHANGED; + } + + /// 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::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()); + A.makeUndefAfterManifest(CB.getArgOperandUse(getArgNo())); + return ChangeStatus::CHANGED; + } + + /// 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; + auto RetInstPred = [&](Instruction &I) { + ReturnInst &RI = cast(I); + if (!isa(RI.getReturnValue())) { + AnyChange = true; + A.makeUndefAfterManifest(RI.getOperandUse(0)); + } + 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()) @@ -2295,6 +2464,16 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; + /// 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(); + } + + /// 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() && @@ -2367,18 +2546,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)) @@ -2388,8 +2556,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(); @@ -2438,7 +2606,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 @@ -2487,8 +2655,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 { @@ -3373,10 +3541,12 @@ if (!SimplifiedAssociatedValue.hasValue() || !SimplifiedAssociatedValue.getValue()) return Changed; + Value &V = getAssociatedValue(); + if (isa(V)) + return Changed; if (auto *C = dyn_cast(SimplifiedAssociatedValue.getValue())) { // We can replace the AssociatedValue with the constant. - Value &V = getAssociatedValue(); if (!V.user_empty() && &V != C && V.getType() == C->getType()) { LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C << "\n"); @@ -4234,6 +4404,56 @@ return true; } +bool Attributor::checkForAllUses( + const function_ref &Pred, + const AbstractAttribute &QueryingAA) { + const IRPosition &IRP = QueryingAA.getIRPosition(); + const Value &AssociatedValue = IRP.getAssociatedValue(); + SmallVector Worklist; + SmallPtrSet Visited; + + for (const Use &U : AssociatedValue.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)) { + 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) { @@ -4593,11 +4813,26 @@ LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " << ToBeDeletedFunctions.size() << " functions and " << ToBeDeletedBlocks.size() << " blocks and " - << ToBeDeletedInsts.size() << " instructions\n"); + << ToBeDeletedInsts.size() << " instructions and " + << ToBeMadeUndef.size() << " uses\n"); + + SmallVector DeadInsts; for (Instruction *I : ToBeDeletedInsts) { - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - I->eraseFromParent(); + I->replaceAllUsesWith(UndefValue::get(I->getType())); + if (isInstructionTriviallyDead(I)) + DeadInsts.push_back(I); + else + I->eraseFromParent(); + } + RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); + + for (Use *U : ToBeMadeUndef) { + Value *V = U->get(); + UndefValue *UV = UndefValue::get(V->getType()); + U->set(UV); + if (Instruction *I = dyn_cast(V)) + if (isInstructionTriviallyDead(I)) + ToBeDeletedInsts.insert(I); } if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { @@ -4748,6 +4983,9 @@ IRPosition RetPos = IRPosition::returned(F); + // Every returned value might be dead. + getOrCreateAAFor(RetPos); + // Every function might be simplified. getOrCreateAAFor(RetPos); @@ -4798,11 +5036,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); @@ -5101,7 +5349,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) @@ -5111,6 +5358,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,23 @@ ; 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) +; ATTRIBUTOR-LABEL: define {{[^@]+}}@f1 +; ATTRIBUTOR-SAME: (i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" [[TMP0:%.*]]) local_unnamed_addr +; ATTRIBUTOR-NEXT: [[TMP2:%.*]] = icmp eq i8* [[TMP0]], null +; ATTRIBUTOR-NEXT: br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]] +; ATTRIBUTOR: 3: +; ATTRIBUTOR-NEXT: [[TMP4:%.*]] = tail call align 8 i8* @f2(i8* nonnull align 8 dereferenceable(1) @a1) +; ATTRIBUTOR-NEXT: [[L:%.*]] = load i8, i8* undef, align 8 +; ATTRIBUTOR-NEXT: br label [[TMP5]] +; ATTRIBUTOR: 5: +; ATTRIBUTOR-NEXT: [[TMP6:%.*]] = phi i8* [ undef, [[TMP3]] ], [ [[TMP0]], [[TMP1:%.*]] ] +; ATTRIBUTOR-NEXT: ret i8* undef +; %2 = icmp eq i8* %0, null br i1 %2, label %3, label %5 ;