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 @@ -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; } 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 blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I->getParent())) + 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; @@ -579,8 +586,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 +611,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 +620,26 @@ // returned value. Optional UniqueRV; - std::function Pred = [&](Value &RV) -> bool { + std::function &)> Pred = + [&](Value &RV, SmallPtrSet &RetInsts) -> bool { + + bool IsLive = false; + + if (LivenessAA) { + for (auto RI : RetInsts) { + if (!LivenessAA->isAssumedDead(RI->getParent())) { + // If at least one RI is live, then ReturnValue is not dead. + IsLive = true; + break; + } + } + + if (!IsLive) { + UniqueRV = nullptr; + return false; + } + } + // 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 +663,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; + SmallPtrSet RetInsts = It.second; ImmutableCallSite ICS(RV); if (ICS && !HasOverdefinedReturnedCalls) continue; - if (!Pred(*RV)) + if (!Pred(*RV, RetInsts)) return false; } @@ -667,9 +698,26 @@ decltype(ReturnedValues) AddRVs; bool HasCallSite = false; + auto *LivenessAA = A.getAAFor(*this, getAnchorScope()); + // Look at all returned call sites. for (auto &It : ReturnedValues) { SmallPtrSet &ReturnInsts = It.second; + + if (LivenessAA) { + bool IsLive = false; + for (auto RI : ReturnInsts) { + if (!LivenessAA->isAssumedDead(RI->getParent())) { + // At least one RI is live, so ReturnValues is not dead. + IsLive = true; + break; + } + } + + if (!IsLive) + continue; + } + Value *RV = It.first; LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV << "\n"); @@ -695,7 +743,7 @@ } // Try to find a assumed unique return value for the called function. - Optional AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue(); + Optional AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue(LivenessAA); // If no assumed unique return value was found due to the lack of // candidates, we may need to resolve more calls (through more update @@ -893,9 +941,16 @@ 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 blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I->getParent())) { + continue; + } + ImmutableCallSite ICS(I); auto *NoSyncAA = A.getAAFor(*this, *I); @@ -924,6 +979,9 @@ for (unsigned Opcode : Opcodes) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip assumed dead blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I->getParent())) + 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 +1045,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 blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I->getParent())) + continue; auto ICS = ImmutableCallSite(I); auto *NoFreeAA = A.getAAFor(*this, *I); @@ -1038,17 +1101,20 @@ /// (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, SmallPtrSet &RetInsts) -> bool { + Function &F = getAnchorScope(); + + if (isKnownNonZero(&RV, F.getParent()->getDataLayout())) return true; auto *NonNullAA = A.getAAFor(*this, RV); @@ -1097,7 +1163,7 @@ return ChangeStatus::CHANGED; } - std::function Pred = this->generatePredicate(A); + std::function &)> Pred = this->generatePredicate(A); if (!AARetVal->checkForallReturnedValues(Pred)) { indicatePessimisticFixpoint(); return ChangeStatus::CHANGED; @@ -1167,6 +1233,13 @@ std::function CallSiteCheck = [&](CallSite CS) { assert(CS && "Sanity check: Call site was not initialized properly!"); + auto *LivenessAA = A.getAAFor(*this, F); + + // Skip assumed dead blocks. + + if (LivenessAA && LivenessAA->isAssumedDead(CS.getInstruction()->getParent())) + return true; + auto *NonNullAA = A.getAAFor(*this, *CS.getInstruction(), ArgNo); // Check that NonNullAA is AANonNullCallSiteArgument. @@ -1288,10 +1361,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 blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I->getParent())) + continue; + auto ICS = ImmutableCallSite(I); if (ICS.hasFnAttr(Attribute::WillReturn)) @@ -1379,7 +1458,8 @@ return ChangeStatus::CHANGED; } - std::function Pred = [&](Value &RV) -> bool { + std::function &)> Pred = + [&](Value &RV, SmallPtrSet &RetInsts) -> bool { if (Constant *C = dyn_cast(&RV)) if (C->isNullValue() || isa(C)) return true; @@ -1575,7 +1655,7 @@ LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size() - << "Total number of blocks: " + << " Total number of blocks: " << getAnchorScope().size() << "\n"); return Status; 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,8 +1,8 @@ ; 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() @@ -10,12 +10,47 @@ declare i32 @bar() -; TEST 1: cond.true is dead, but cond.end is not, since cond.false is live +define i32 @volatile_load(i32*) norecurse nounwind uwtable { + %2 = load volatile 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* %ptr1) +define i32 @first_block_no_return(i32 %a, i32* %ptr1) #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 + %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 { +; FIXME: This function should be marked nosync, because @volatile_load is +; called in a dead block. +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 +59,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 +72,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 +100,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 +123,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 +157,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 +177,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 +208,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 +234,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 +258,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 -}