Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -2390,12 +2390,18 @@ using Base = StateWrapper; AAReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {} + /// Returns true if 'From' instruction is assumed to reach 'To' instruction. + virtual bool getAssumedReachable(const Instruction &From, + const Instruction &To) const = 0; + /// Returns true if 'From' instruction is assumed to reach, 'To' instruction. /// Users should provide two positions they are interested in, and the class /// determines (and caches) reachability. bool isAssumedReachable(Attributor &A, const Instruction &From, const Instruction &To) const { - return A.getInfoCache().getPotentiallyReachable(From, To); + if (!A.getInfoCache().getPotentiallyReachable(From, To)) + return false; + return getAssumedReachable(From, To); } /// Returns true if 'From' instruction is known to reach, 'To' instruction. Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -2222,34 +2222,6 @@ void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); } }; -/// -------------------AAReachability Attribute-------------------------- - -struct AAReachabilityImpl : AAReachability { - AAReachabilityImpl(const IRPosition &IRP, Attributor &A) - : AAReachability(IRP, A) {} - - const std::string getAsStr() const override { - // TODO: Return the number of reachable queries. - return "reachable"; - } - - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } - - /// See AbstractAttribute::updateImpl(...). - ChangeStatus updateImpl(Attributor &A) override { - return indicatePessimisticFixpoint(); - } -}; - -struct AAReachabilityFunction final : public AAReachabilityImpl { - AAReachabilityFunction(const IRPosition &IRP, Attributor &A) - : AAReachabilityImpl(IRP, A) {} - - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); } -}; - /// ------------------------ NoAlias Argument Attribute ------------------------ struct AANoAliasImpl : AANoAlias { @@ -3275,6 +3247,134 @@ void trackStatistics() const override {} }; +/// -------------------AAReachability Attribute-------------------------- + +struct AAReachabilityImpl : AAReachability { + AAReachabilityImpl(const IRPosition &IRP, Attributor &A) + : AAReachability(IRP, A) {} + + const std::string getAsStr() const override { + // TODO: Return the number of reachable queries. + return "reachable"; + } + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + return indicatePessimisticFixpoint(); + } +}; + +struct AAReachabilityFunction final : public AAReachabilityImpl { + AAReachabilityFunction(const IRPosition &IRP, Attributor &A) + : AAReachabilityImpl(IRP, A) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override {} + + /// Helper function for updateImpl to add \p ToBB as successor of \p FromBB + ChangeStatus addEdge(const BasicBlock *FromBB, const BasicBlock *ToBB) { + auto InsertResult = SuccessorGraph.insert( + std::make_pair(FromBB, SetVector())); + auto SetInsertResult = InsertResult.first->second.insert(ToBB); + if (SetInsertResult == true) { + LLVM_DEBUG(dbgs() << "[AAReachability] Add edge : " << *FromBB << " -> " + << *ToBB << "\n"); + } + return SetInsertResult ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + Function &F = *getAnchorScope(); + const auto &FnLiveness = A.getAAFor(*this, getIRPosition()); + for (Function::const_iterator BBIt = F.begin(); BBIt != F.end(); BBIt++) { + if (A.isAssumedDead(BBIt->front(), this, &FnLiveness, + /* CheckBBLivenessOnly */ true, DepClassTy::REQUIRED)) + continue; + SmallVector AliveSuccessors; + for (BasicBlock::const_iterator InstIt = BBIt->begin(); + InstIt != BBIt->end(); InstIt++) { + const Instruction *I = &*InstIt; + if (A.isAssumedDead(*I, this, &FnLiveness)) + continue; + switch (I->getOpcode()) { + default: + if (I->isTerminator()) { + for (const BasicBlock *SuccBB : successors(I->getParent())) + AliveSuccessors.push_back(&SuccBB->front()); + } + break; + case Instruction::Call: + identifyAliveSuccessors(A, cast(*I), *this, + AliveSuccessors); + break; + case Instruction::Invoke: + identifyAliveSuccessors(A, cast(*I), *this, + AliveSuccessors); + break; + case Instruction::Br: + identifyAliveSuccessors(A, cast(*I), *this, + AliveSuccessors); + break; + case Instruction::Switch: + identifyAliveSuccessors(A, cast(*I), *this, + AliveSuccessors); + break; + } + } + const BasicBlock *FromBB = &*BBIt; + for (const Instruction *I : AliveSuccessors) { + if (I->getParent() == FromBB) + continue; + Changed = Changed | addEdge(FromBB, I->getParent()); + } + } + return Changed; + } + + /// Return wheather \p To is reachable from \p From or not. + bool getAssumedReachable(const Instruction &From, + const Instruction &To) const override { + const BasicBlock *FromBB = From.getParent(); + const BasicBlock *ToBB = To.getParent(); + + if (FromBB == ToBB) + return true; + + /// Basic blocks which are confirmed to be rechable from \p FromBB + SetVector ReachableBBs; + + SmallVector Worklist; + Worklist.push_back(FromBB); + + while (!Worklist.empty()) { + const BasicBlock *BB = Worklist.pop_back_val(); + LLVM_DEBUG(dbgs() << "[AAReachability] Explore BB : " << *BB << "\n"); + if (BB == ToBB) + return true; + auto GraphIt = SuccessorGraph.find(BB); + if (GraphIt == SuccessorGraph.end()) + continue; + for (const BasicBlock *NextBB : GraphIt->second) { + if (!ReachableBBs.count(NextBB)) { + Worklist.push_back(NextBB); + ReachableBBs.insert(NextBB); + } + } + } + return false; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); } + + /// Map from a basic block to its reachable successor basic blocks + DenseMap> SuccessorGraph; +}; + /// -------------------- Dereferenceable Argument Attribute -------------------- template <> Index: llvm/test/Transforms/Attributor/callbacks.ll =================================================================== --- llvm/test/Transforms/Attributor/callbacks.ll +++ llvm/test/Transforms/Attributor/callbacks.ll @@ -22,7 +22,6 @@ ; IS__TUNIT_OPM-NEXT: [[B:%.*]] = alloca i32, align 32 ; IS__TUNIT_OPM-NEXT: [[C:%.*]] = alloca i32*, align 64 ; IS__TUNIT_OPM-NEXT: [[PTR:%.*]] = alloca i32, align 128 -; IS__TUNIT_OPM-NEXT: [[TMP0:%.*]] = bitcast i32* [[B]] to i8* ; IS__TUNIT_OPM-NEXT: store i32 42, i32* [[B]], align 32 ; IS__TUNIT_OPM-NEXT: store i32* [[B]], i32** [[C]], align 64 ; IS__TUNIT_OPM-NEXT: call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* noalias nocapture align 536870912 null, i32* nonnull align 128 dereferenceable(4) [[PTR]], void (i32*, i32*, ...)* nonnull bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* align 256 [[A]], i64 undef, i32** nocapture nonnull readonly align 64 dereferenceable(8) [[C]]) @@ -34,7 +33,6 @@ ; IS__TUNIT_NPM-NEXT: [[B:%.*]] = alloca i32, align 32 ; IS__TUNIT_NPM-NEXT: [[C:%.*]] = alloca i32*, align 64 ; IS__TUNIT_NPM-NEXT: [[PTR:%.*]] = alloca i32, align 128 -; IS__TUNIT_NPM-NEXT: [[TMP0:%.*]] = bitcast i32* [[B]] to i8* ; IS__TUNIT_NPM-NEXT: store i32 42, i32* [[B]], align 32 ; IS__TUNIT_NPM-NEXT: store i32* [[B]], i32** [[C]], align 64 ; IS__TUNIT_NPM-NEXT: call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* noalias nocapture align 536870912 null, i32* nonnull align 128 dereferenceable(4) [[PTR]], void (i32*, i32*, ...)* nonnull bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* align 256 [[A]], i64 undef, i32** noalias nocapture nonnull readonly align 64 dereferenceable(8) [[C]]) @@ -46,7 +44,6 @@ ; IS__CGSCC_OPM-NEXT: [[B:%.*]] = alloca i32, align 32 ; IS__CGSCC_OPM-NEXT: [[C:%.*]] = alloca i32*, align 64 ; IS__CGSCC_OPM-NEXT: [[PTR:%.*]] = alloca i32, align 128 -; IS__CGSCC_OPM-NEXT: [[TMP0:%.*]] = bitcast i32* [[B]] to i8* ; IS__CGSCC_OPM-NEXT: store i32 42, i32* [[B]], align 32 ; IS__CGSCC_OPM-NEXT: store i32* [[B]], i32** [[C]], align 64 ; IS__CGSCC_OPM-NEXT: call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* noalias nocapture align 536870912 null, i32* nonnull align 128 dereferenceable(4) [[PTR]], void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* align 256 [[A]], i64 99, i32** nocapture nonnull readonly align 64 dereferenceable(8) [[C]]) @@ -58,7 +55,6 @@ ; IS__CGSCC_NPM-NEXT: [[B:%.*]] = alloca i32, align 32 ; IS__CGSCC_NPM-NEXT: [[C:%.*]] = alloca i32*, align 64 ; IS__CGSCC_NPM-NEXT: [[PTR:%.*]] = alloca i32, align 128 -; IS__CGSCC_NPM-NEXT: [[TMP0:%.*]] = bitcast i32* [[B]] to i8* ; IS__CGSCC_NPM-NEXT: store i32 42, i32* [[B]], align 32 ; IS__CGSCC_NPM-NEXT: store i32* [[B]], i32** [[C]], align 64 ; IS__CGSCC_NPM-NEXT: call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* noalias nocapture align 536870912 null, i32* nonnull align 128 dereferenceable(4) [[PTR]], void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* align 256 [[A]], i64 99, i32** noalias nocapture nonnull readonly align 64 dereferenceable(8) [[C]]) Index: llvm/test/Transforms/Attributor/noalias.ll =================================================================== --- llvm/test/Transforms/Attributor/noalias.ll +++ llvm/test/Transforms/Attributor/noalias.ll @@ -817,7 +817,7 @@ ; NOT_CGSCC_NPM-NEXT: tail call void @make_alias(i32* nofree writeonly [[P]]) ; NOT_CGSCC_NPM-NEXT: br label [[L3:%.*]] ; NOT_CGSCC_NPM: l2: -; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* nocapture nofree writeonly align 4 [[P]]) +; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* noalias nocapture nofree writeonly align 4 [[P]]) ; NOT_CGSCC_NPM-NEXT: br label [[L3]] ; NOT_CGSCC_NPM: l3: ; NOT_CGSCC_NPM-NEXT: ret void @@ -832,7 +832,7 @@ ; IS__CGSCC____-NEXT: tail call void @make_alias(i32* nofree writeonly [[P]]) ; IS__CGSCC____-NEXT: br label [[L3:%.*]] ; IS__CGSCC____: l2: -; IS__CGSCC____-NEXT: tail call void @only_store(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P]]) +; IS__CGSCC____-NEXT: tail call void @only_store(i32* noalias nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P]]) ; IS__CGSCC____-NEXT: br label [[L3]] ; IS__CGSCC____: l3: ; IS__CGSCC____-NEXT: ret void @@ -888,7 +888,7 @@ ; NOT_CGSCC_NPM-NEXT: tail call void @make_alias(i32* nofree writeonly [[P]]) ; NOT_CGSCC_NPM-NEXT: unreachable ; NOT_CGSCC_NPM: l2: -; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* nocapture nofree writeonly align 4 [[P]]) +; NOT_CGSCC_NPM-NEXT: tail call void @only_store(i32* noalias nocapture nofree writeonly align 4 [[P]]) ; NOT_CGSCC_NPM-NEXT: ret void ; ; IS__CGSCC____: Function Attrs: nofree norecurse nosync nounwind willreturn writeonly @@ -901,7 +901,7 @@ ; IS__CGSCC____-NEXT: tail call void @make_alias(i32* nofree nonnull writeonly align 4 dereferenceable(4) [[P]]) ; IS__CGSCC____-NEXT: unreachable ; IS__CGSCC____: l2: -; IS__CGSCC____-NEXT: tail call void @only_store(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P]]) +; IS__CGSCC____-NEXT: tail call void @only_store(i32* noalias nocapture nofree nonnull writeonly align 4 dereferenceable(4) [[P]]) ; IS__CGSCC____-NEXT: ret void ; entry: Index: llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll =================================================================== --- llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll +++ llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll @@ -166,7 +166,6 @@ ; IS__TUNIT____-NEXT: [[CALL8:%.*]] = call i32* @internal_ret0_nw(i32* nofree nonnull align 4 dereferenceable(4) [[R1]], i32* nofree nonnull align 4 dereferenceable(4) [[W0]]) ; IS__TUNIT____-NEXT: br label [[RETURN]] ; IS__TUNIT____: return: -; IS__TUNIT____-NEXT: [[RETVAL_0:%.*]] = phi i32* [ [[CALL8]], [[IF_END]] ], [ [[R1]], [[IF_THEN]] ] ; IS__TUNIT____-NEXT: ret i32* undef ; ; IS__CGSCC____: Function Attrs: argmemonly nofree nosync nounwind @@ -194,7 +193,6 @@ ; IS__CGSCC____-NEXT: [[CALL8:%.*]] = call i32* @internal_ret0_nw(i32* nofree nonnull align 4 dereferenceable(4) [[R1]], i32* nofree nonnull align 4 dereferenceable(4) [[W0]]) ; IS__CGSCC____-NEXT: br label [[RETURN]] ; IS__CGSCC____: return: -; IS__CGSCC____-NEXT: [[RETVAL_0:%.*]] = phi i32* [ [[CALL8]], [[IF_END]] ], [ [[R1]], [[IF_THEN]] ] ; IS__CGSCC____-NEXT: ret i32* undef ; entry: