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; } @@ -843,6 +844,12 @@ /// 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; }; } // 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 blocks. + 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; @@ -570,6 +577,25 @@ IsFixed = true; IsValidState = false; } + + static bool isLiveRetValue(const AAIsDead *LivenessAA, + const SmallPtrSetImpl &ReturnInsts) { + if (!LivenessAA) + return true; + + bool IsLive = false; + for(auto RI : ReturnInsts) { + if (!LivenessAA->isAssumedDead(RI)) { + // At least one RI is live, so ReturnValue is not dead. + IsLive = true; + break; + } + } + + if (IsLive) + return true; + return false; + } }; ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) { @@ -579,8 +605,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 +630,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 +639,13 @@ // 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 (!isLiveRetValue(LivenessAA, RetInsts)) + 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 +669,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,9 +704,19 @@ 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; + + // Ignore dead ReturnValues. + if (!isLiveRetValue(LivenessAA, ReturnInsts)) + continue; + Value *RV = It.first; LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV << "\n"); @@ -687,6 +734,8 @@ // Try to find a assumed unique return value for the called function. auto *RetCSAA = A.getAAFor(*this, *RV); if (!RetCSAA) { + if (!HasOverdefinedReturnedCalls) + Changed = ChangeStatus::CHANGED; HasOverdefinedReturnedCalls = true; LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV << ") with " << (RetCSAA ? "invalid" : "no") @@ -695,7 +744,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 @@ -708,6 +757,8 @@ // If multiple, non-refinable values were found, there cannot be a unique // return value for the called function. The returned call is overdefined! if (!AssumedUniqueRV.getValue()) { + if (!HasOverdefinedReturnedCalls) + Changed = ChangeStatus::CHANGED; HasOverdefinedReturnedCalls = true; LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple " "potentially returned values\n"); @@ -736,9 +787,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 +941,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 blocks. + if (LivenessAA && LivenessAA->isAssumedDead(I)) + continue; + ImmutableCallSite ICS(I); auto *NoSyncAA = A.getAAFor(*this, *I); @@ -924,6 +978,9 @@ for (unsigned Opcode : Opcodes) { for (Instruction *I : OpcodeInstMap[Opcode]) { + // Skip assumed dead blocks. + 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 +1044,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)) + continue; auto ICS = ImmutableCallSite(I); auto *NoFreeAA = A.getAAFor(*this, *I); @@ -1038,17 +1100,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 +1164,8 @@ 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 +1235,12 @@ 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())) + return true; + auto *NonNullAA = A.getAAFor(*this, *CS.getInstruction(), ArgNo); // Check that NonNullAA is AANonNullCallSiteArgument. @@ -1288,10 +1362,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)) + continue; + auto ICS = ImmutableCallSite(I); if (ICS.hasFnAttr(Attribute::WillReturn)) @@ -1379,7 +1459,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 +1559,60 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; - /// See AAIsDead::isAssumedDead(). + /// See AAIsDead::isAssumedDead(BasicBlock *BB). bool isAssumedDead(BasicBlock *BB) const override { 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 false; return !AssumedLiveBlocks.count(BB); } + /// See AAIsDead::isAssumed(Instruction *I). + bool isAssumedDead(Instruction *I) const override { + if(!getAssumed()) + return false; + + // 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 { + if(!getKnown()) + return false; + + // 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 I is not in AssumedLiveBlocks and not after a noreturn call, than it + // is live. + if (!isAfterNoReturn(I)) + return false; + + // Definitely dead. + return true; + } + + /// 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 +1623,31 @@ SmallSetVector NoReturnCalls; }; +bool AAIsDeadFunction::isAfterNoReturn(Instruction *I) const { + BasicBlock *BB = I->getParent(); + Instruction *DeadInst = nullptr; + + for (Instruction *NoRet : NoReturnCalls) { + if (NoRet->getParent() == BB) { + DeadInst = NoRet->getNextNode(); + break; + } + } + + // No noreturn calls in this block. + if (!DeadInst) + return false; + + while (DeadInst) { + if (DeadInst == I) + return true; + + DeadInst = DeadInst->getNextNode(); + } + + return false; +} + bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) { BasicBlock *BB = I->getParent(); @@ -1548,6 +1694,8 @@ // will alow easier modification of NoReturnCalls collection SmallVector NoReturnChanged; ChangeStatus Status = ChangeStatus::UNCHANGED; + // ChangeStatus Status = NoReturnCalls.size() > 0 ? ChangeStatus::CHANGED + // : ChangeStatus::UNCHANGED; for (Instruction *I : NoReturnCalls) NoReturnChanged.push_back(I); @@ -1575,7 +1723,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,21 +1,57 @@ ; 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 +} + +; 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 { +; 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 +60,8 @@ 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) + %call = call i32 @bar() br label %cond.end cond.false: ; preds = %entry @@ -37,7 +74,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 +102,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 +125,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 +159,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 +179,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 +210,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 +236,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 +260,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 -}