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 @@ -269,7 +269,7 @@ /// true if \p Pred holds in every call sites. However, this is only possible /// all call sites are known, hence the function has internal linkage. bool checkForAllCallSites(Function &F, std::function &Pred, - bool RequireAllCallSites); + bool RequireAllCallSites, AbstractAttribute *AA); private: /// The set of all abstract attributes. @@ -671,8 +671,9 @@ /// This method will evaluate \p Pred on returned values and return /// true if (1) all returned values are known, and (2) \p Pred returned true /// for all returned values. - virtual bool - checkForallReturnedValues(std::function &Pred) const = 0; + virtual bool checkForallReturnedValues( + std::function &)> &Pred) + const = 0; /// See AbstractAttribute::getAttrKind() Attribute::AttrKind getAttrKind() const override { return ID; } @@ -843,6 +844,28 @@ /// Returns true if \p BB is known dead. virtual bool isKnownDead(BasicBlock *BB) const = 0; + + /// Returns true if \p I is assumed dead. + virtual bool isAssumedDead(Instruction *I) const = 0; + + /// Returns true if \p I is known dead. + virtual bool isKnownDead(Instruction *I) const = 0; + + /// This method is used to check if at least one instruction in a collection + /// of instructions is live. + template + bool isLiveInstSet(T begin, T end) const { + for (T I = begin; I != end; ++I) { + assert(isa(*I) && "It has to be collection of Instructions"); + assert((*I)->getParent()->getParent() == &getAnchorScope() && + "Instruction must be in the same anchor scope function."); + + if (!isAssumedDead(*I)) + return true; + } + + return false; + } }; } // end namespace llvm 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 @@ -420,8 +420,14 @@ (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet, (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume}; + auto *LivenessAA = A.getAAFor(*this, F); + for (unsigned Opcode : Opcodes) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip dead instructions. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; + if (!I->mayThrow()) continue; @@ -546,11 +552,12 @@ /// Return an assumed unique return value if a single candidate is found. If /// there cannot be one, return a nullptr. If it is not clear yet, return the /// Optional::NoneType. - Optional getAssumedUniqueReturnValue() const; + Optional getAssumedUniqueReturnValue(const AAIsDead *LivenessAA) const; /// See AbstractState::checkForallReturnedValues(...). - bool - checkForallReturnedValues(std::function &Pred) const override; + bool checkForallReturnedValues( + std::function &)> &Pred) + const override; /// Pretty print the attribute similar to the IR representation. const std::string getAsStr() const override; @@ -566,6 +573,7 @@ IsFixed = true; IsValidState &= true; } + void indicatePessimisticFixpoint() override { IsFixed = true; IsValidState = false; @@ -579,8 +587,10 @@ assert(isValidState()); NumFnKnownReturns++; + auto *LivenessAA = A.getAAFor(*this, getAnchorScope()); + // Check if we have an assumed unique return value that we could manifest. - Optional UniqueRV = getAssumedUniqueReturnValue(); + Optional UniqueRV = getAssumedUniqueReturnValue(LivenessAA); if (!UniqueRV.hasValue() || !UniqueRV.getValue()) return Changed; @@ -602,7 +612,8 @@ (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")"; } -Optional AAReturnedValuesImpl::getAssumedUniqueReturnValue() const { +Optional AAReturnedValuesImpl::getAssumedUniqueReturnValue( + const AAIsDead *LivenessAA) const { // If checkForallReturnedValues provides a unique value, ignoring potential // undef values that can also be present, it is assumed to be the actual // return value and forwarded to the caller of this method. If there are @@ -610,7 +621,15 @@ // returned value. Optional UniqueRV; - std::function Pred = [&](Value &RV) -> bool { + std::function &)> Pred = + [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { + + // If all ReturnInsts are dead, then ReturnValue is dead as well + // and can be ignored. + if (LivenessAA && + !LivenessAA->isLiveInstSet(RetInsts.begin(), RetInsts.end())) + return true; + // If we found a second returned value and neither the current nor the saved // one is an undef, there is no unique returned value. Undefs are special // since we can pretend they have any value. @@ -634,20 +653,22 @@ } bool AAReturnedValuesImpl::checkForallReturnedValues( - std::function &Pred) const { + std::function &)> &Pred) const { if (!isValidState()) return false; // Check all returned values but ignore call sites as long as we have not // encountered an overdefined one during an update. for (auto &It : ReturnedValues) { + Value *RV = It.first; + const SmallPtrSetImpl &RetInsts = It.second; ImmutableCallSite ICS(RV); if (ICS && !HasOverdefinedReturnedCalls) continue; - if (!Pred(*RV)) + if (!Pred(*RV, RetInsts)) return false; } @@ -667,10 +688,20 @@ decltype(ReturnedValues) AddRVs; bool HasCallSite = false; + // Keep track of any change to trigger updates on dependent attributes. + ChangeStatus Changed = ChangeStatus::UNCHANGED; + + auto *LivenessAA = A.getAAFor(*this, getAnchorScope()); + // Look at all returned call sites. for (auto &It : ReturnedValues) { SmallPtrSet &ReturnInsts = It.second; Value *RV = It.first; + + // Ignore dead ReturnValues. + if (LivenessAA && !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end())) + continue; + LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV << "\n"); @@ -694,8 +725,11 @@ continue; } + auto *LivenessCSAA = A.getAAFor(*this, RetCSAA->getAnchorScope()); + // Try to find a assumed unique return value for the called function. - Optional AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue(); + Optional AssumedUniqueRV = + RetCSAA->getAssumedUniqueReturnValue(LivenessCSAA); // If no assumed unique return value was found due to the lack of // candidates, we may need to resolve more calls (through more update @@ -736,9 +770,6 @@ AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end()); } - // Keep track of any change to trigger updates on dependent attributes. - ChangeStatus Changed = ChangeStatus::UNCHANGED; - for (auto &It : AddRVs) { assert(!It.second.empty() && "Entry does not add anything."); auto &ReturnInsts = ReturnedValues[It.first]; @@ -893,9 +924,15 @@ ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) { Function &F = getAnchorScope(); + auto *LivenessAA = A.getAAFor(*this, F); + /// We are looking for volatile instructions or Non-Relaxed atomics. /// FIXME: We should ipmrove the handling of intrinsics. for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) { + // Skip assumed dead instructions. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; + ImmutableCallSite ICS(I); auto *NoSyncAA = A.getAAFor(*this, *I); @@ -924,6 +961,9 @@ for (unsigned Opcode : Opcodes) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip assumed dead instructions. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; // At this point we handled all read/write effects and they are all // nosync, so they can be skipped. if (I->mayReadOrWriteMemory()) @@ -987,10 +1027,15 @@ // The map from instruction opcodes to those instructions in the function. auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + auto *LivenessAA = A.getAAFor(*this, F); + for (unsigned Opcode : {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, (unsigned)Instruction::Call}) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip assumed dead instructions. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; auto ICS = ImmutableCallSite(I); auto *NoFreeAA = A.getAAFor(*this, *I); @@ -1038,17 +1083,22 @@ /// (i) A value is known nonZero(=nonnull). /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is /// true. - std::function generatePredicate(Attributor &); + std::function &)> + generatePredicate(Attributor &); }; -std::function AANonNullImpl::generatePredicate(Attributor &A) { +std::function &)> +AANonNullImpl::generatePredicate(Attributor &A) { // FIXME: The `AAReturnedValues` should provide the predicate with the // `ReturnInst` vector as well such that we can use the control flow sensitive // version of `isKnownNonZero`. This should fix `test11` in // `test/Transforms/FunctionAttrs/nonnull.ll` - std::function Pred = [&](Value &RV) -> bool { - if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout())) + std::function &)> Pred = + [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { + Function &F = getAnchorScope(); + + if (isKnownNonZero(&RV, F.getParent()->getDataLayout())) return true; auto *NonNullAA = A.getAAFor(*this, RV); @@ -1097,7 +1147,8 @@ return ChangeStatus::CHANGED; } - std::function Pred = this->generatePredicate(A); + std::function &)> Pred = + this->generatePredicate(A); if (!AARetVal->checkForallReturnedValues(Pred)) { indicatePessimisticFixpoint(); return ChangeStatus::CHANGED; @@ -1157,6 +1208,7 @@ private: unsigned ArgNo; }; + ChangeStatus AANonNullArgument::updateImpl(Attributor &A) { Function &F = getAnchorScope(); Argument &Arg = cast(getAnchoredValue()); @@ -1186,7 +1238,8 @@ return false; }; - if (!A.checkForAllCallSites(F, CallSiteCheck, true)) { + + if (!A.checkForAllCallSites(F, CallSiteCheck, true, this)) { indicatePessimisticFixpoint(); return ChangeStatus::CHANGED; } @@ -1288,10 +1341,16 @@ // The map from instruction opcodes to those instructions in the function. auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + auto *LivenessAA = A.getAAFor(*this, F); + for (unsigned Opcode : {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, (unsigned)Instruction::Call}) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip assumed dead instructions. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; + auto ICS = ImmutableCallSite(I); if (ICS.hasFnAttr(Attribute::WillReturn)) @@ -1379,7 +1438,8 @@ return ChangeStatus::CHANGED; } - std::function Pred = [&](Value &RV) -> bool { + std::function &)> Pred = + [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { if (Constant *C = dyn_cast(&RV)) if (C->isNullValue() || isa(C)) return true; @@ -1478,20 +1538,50 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; - /// See AAIsDead::isAssumedDead(). + /// See AAIsDead::isAssumedDead(BasicBlock *BB). bool isAssumedDead(BasicBlock *BB) const override { + assert(BB->getParent() == &getAnchorScope() && + "BB must be in the same anchor scope function."); + if (!getAssumed()) return false; return !AssumedLiveBlocks.count(BB); } - /// See AAIsDead::isKnownDead(). + /// See AAIsDead::isKnownDead(BasicBlock *BB). bool isKnownDead(BasicBlock *BB) const override { - if (!getKnown()) + return getKnown() && isAssumedDead(BB); + } + + /// See AAIsDead::isAssumed(Instruction *I). + bool isAssumedDead(Instruction *I) const override { + assert(I->getParent()->getParent() == &getAnchorScope() && + "Instruction must be in the same anchor scope function."); + + if(!getAssumed()) return false; - return !AssumedLiveBlocks.count(BB); + + // If it is not in AssumedLiveBlocks then it for sure dead. + // Otherwise, it can still be after noreturn call in a live block. + if (!AssumedLiveBlocks.count(I->getParent())) + return true; + + // If it is not after a noreturn call, than it is live. + if (!isAfterNoReturn(I)) + return false; + + // Definitely dead. + return true; + } + + /// See AAIsDead::isKnownDead(Instruction *I). + bool isKnownDead(Instruction *I) const override { + return getKnown() && isAssumedDead(I); } + /// Check if instruction is after noreturn call, in other words, assumed dead. + bool isAfterNoReturn(Instruction *I) const; + /// Collection of to be explored paths. SmallSetVector ToBeExploredPaths; @@ -1502,6 +1592,16 @@ SmallSetVector NoReturnCalls; }; +bool AAIsDeadFunction::isAfterNoReturn(Instruction *I) const { + Instruction *PrevI = I->getPrevNode(); + while (PrevI) { + if (NoReturnCalls.count(PrevI)) + return true; + PrevI = PrevI->getPrevNode(); + } + return false; +} + bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) { BasicBlock *BB = I->getParent(); @@ -1561,13 +1661,13 @@ NoReturnCalls.remove(I); + // At least one new path. + Status = ChangeStatus::CHANGED; + // No new paths. if (Size == ToBeExploredPaths.size()) continue; - // At least one new path. - Status = ChangeStatus::CHANGED; - // explore new paths. while (Size != ToBeExploredPaths.size()) explorePath(A, ToBeExploredPaths[Size++]); @@ -1575,7 +1675,7 @@ LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size() - << "Total number of blocks: " + << " Total number of blocks: " << getAnchorScope().size() << "\n"); return Status; @@ -1587,7 +1687,8 @@ bool Attributor::checkForAllCallSites(Function &F, std::function &Pred, - bool RequireAllCallSites) { + bool RequireAllCallSites, + AbstractAttribute *AA) { // We can try to determine information from // the call sites. However, this is only possible all call sites are known, // hence the function has internal linkage. @@ -1611,6 +1712,13 @@ return false; } + Function *AnchorValue = CS->getFunction(); + auto *LivenessAA = getAAFor(*AA, *AnchorValue); + + // Skip dead calls. + if (LivenessAA && LivenessAA->isAssumedDead(CS.getInstruction())) + continue; + if (Pred(CS)) continue; diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -748,4 +748,6 @@ ; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readnone uwtable } ; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readonly uwtable } ; BOTH-DAG: attributes #{{[0-9]*}} = { noinline nounwind uwtable } +; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readnone uwtable willreturn } +; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind uwtable willreturn } ; BOTH-NOT: attributes # diff --git a/llvm/test/Transforms/FunctionAttrs/liveness.ll b/llvm/test/Transforms/FunctionAttrs/liveness.ll --- a/llvm/test/Transforms/FunctionAttrs/liveness.ll +++ b/llvm/test/Transforms/FunctionAttrs/liveness.ll @@ -1,21 +1,67 @@ ; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s -declare void @no_return_call() noreturn +declare void @no_return_call() nofree noreturn nounwind readnone -declare void @normal_call() +declare void @normal_call() readnone declare i32 @foo() declare i32 @foo_noreturn() noreturn -declare i32 @bar() +declare i32 @bar() nosync readnone -; TEST 1: cond.true is dead, but cond.end is not, since cond.false is live +; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn +define i32 @volatile_load(i32*) norecurse nounwind uwtable { + %2 = load volatile i32, i32* %0, align 4 + ret i32 %2 +} + +; CHECK: Function Attrs: nofree norecurse nosync nounwind uwtable willreturn +; CHECK-NEXT: define internal i32 @internal_load(i32* nonnull) +define internal i32 @internal_load(i32*) norecurse nounwind uwtable { + %2 = load i32, i32* %0, align 4 + ret i32 %2 +} +; TEST 1: Only first block is live. + +; CHECK: Function Attrs: nofree nosync nounwind +; CHECK-NEXT: define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2) +define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2) #0 { +entry: + call i32 @internal_load(i32* %ptr1) + ; CHECK: call i32 @internal_load(i32* nonnull %ptr1) + call void @no_return_call() + ; CHECK: call void @no_return_call() + ; CHECK-NEXT: unreachable + %cmp = icmp eq i32 %a, 0 + br i1 %cmp, label %cond.true, label %cond.false + +cond.true: ; preds = %entry + call i32 @internal_load(i32* %ptr2) + ; CHECK: call i32 @internal_load(i32* %ptr2) + %load = call i32 @volatile_load(i32* %ptr1) + call void @normal_call() + %call = call i32 @foo() + br label %cond.end + +cond.false: ; preds = %entry + call void @normal_call() + %call1 = call i32 @bar() + br label %cond.end + +cond.end: ; preds = %cond.false, %cond.true + %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ] + ret i32 %cond +} + +; TEST 2: cond.true is dead, but cond.end is not, since cond.false is live ; This is just an example. For example we can put a sync call in a ; dead block and check if it is deduced. -define i32 @dead_block_present(i32 %a) #0 { +; CHECK: Function Attrs: nosync +; CHECK-NEXT: define i32 @dead_block_present(i32 %a, i32* %ptr1) +define i32 @dead_block_present(i32 %a, i32* %ptr1) #0 { entry: %cmp = icmp eq i32 %a, 0 br i1 %cmp, label %cond.true, label %cond.false @@ -24,7 +70,7 @@ call void @no_return_call() ; CHECK: call void @no_return_call() ; CHECK-NEXT: unreachable - %call = call i32 @foo() + %call = call i32 @volatile_load(i32* %ptr1) br label %cond.end cond.false: ; preds = %entry @@ -37,7 +83,7 @@ ret i32 %cond } -; TEST 2: both cond.true and cond.false are dead, therfore cond.end is dead as well. +; TEST 3: both cond.true and cond.false are dead, therfore cond.end is dead as well. define i32 @all_dead(i32 %a) #0 { entry: @@ -65,7 +111,7 @@ declare i32 @__gxx_personality_v0(...) -; TEST 3: All blocks are live. +; TEST 4: All blocks are live. ; CHECK: define i32 @all_live(i32 %a) define i32 @all_live(i32 %a) #0 { @@ -88,7 +134,7 @@ ret i32 %cond } -; TEST 4 noreturn invoke instruction replaced by a call and an unreachable instruction +; TEST 5 noreturn invoke instruction replaced by a call and an unreachable instruction ; put after it. ; CHECK: define i32 @invoke_noreturn(i32 %a) @@ -122,7 +168,7 @@ ret i32 0 } -; TEST 5: Undefined behvior, taken from LangRef. +; TEST 6: Undefined behvior, taken from LangRef. ; FIXME: Should be able to detect undefined behavior. ; CHECK define @ub(i32) @@ -142,7 +188,7 @@ br label %while.body } -; TEST 6: Infinite loop. +; TEST 7: Infinite loop. ; FIXME: Detect infloops, and mark affected blocks dead. define i32 @test5(i32, i32) #0 { @@ -173,7 +219,7 @@ ret void } -; TEST 7: Recursion +; TEST 8: Recursion ; FIXME: everything after first block should be marked dead ; and unreachable should be put after call to @rec(). @@ -199,7 +245,7 @@ %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ] ret i32 %7 } -; TEST 8: Recursion +; TEST 9: Recursion ; FIXME: contains recursive call to itself in cond.elseif block define i32 @test7(i32, i32) #0 { @@ -223,28 +269,3 @@ %8 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ] ret i32 %8 } - -; TEST 9: Only first block is live. - -define i32 @first_block_no_return(i32 %a) #0 { -entry: - call void @no_return_call() - ; CHECK: call void @no_return_call() - ; CHECK-NEXT: unreachable - %cmp = icmp eq i32 %a, 0 - br i1 %cmp, label %cond.true, label %cond.false - -cond.true: ; preds = %entry - call void @normal_call() - %call = call i32 @foo() - br label %cond.end - -cond.false: ; preds = %entry - call void @normal_call() - %call1 = call i32 @bar() - br label %cond.end - -cond.end: ; preds = %cond.false, %cond.true - %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ] - ret i32 %cond -} diff --git a/llvm/test/Transforms/FunctionAttrs/willreturn.ll b/llvm/test/Transforms/FunctionAttrs/willreturn.ll --- a/llvm/test/Transforms/FunctionAttrs/willreturn.ll +++ b/llvm/test/Transforms/FunctionAttrs/willreturn.ll @@ -454,10 +454,9 @@ ; unreachable exit ; 15.1 (positive case) -; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define void @unreachable_exit_positive1() -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable willreturn ; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1() define void @unreachable_exit_positive1() #0 { tail call void @will_return() @@ -471,7 +470,7 @@ ; FIXME: missing willreturn ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32) -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable ; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32) define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 { %2 = icmp slt i32 %0, 1 @@ -515,7 +514,7 @@ ; FNATTR: Function Attrs: noinline nounwind uwtable ; FNATTR-NOT: willreturn ; FNATTR-NEXT: define void @unreachable_exit_negative2() -; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable +; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable ; ATTRIBUTOR-NOT: willreturn ; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2() define void @unreachable_exit_negative2() #0 {