Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -97,6 +97,7 @@ #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/PassManager.h" @@ -249,6 +250,7 @@ /// /// \param F The function that is checked for attribute opportunities. /// \param InfoCache A cache for information queryable by the new attributes. + /// \param LoopInfoGetter A function that adds some analyses. /// \param Whitelist If not null, a set limiting the attribute opportunities. /// /// Note that abstract attribute instances are generally created even if the @@ -258,6 +260,7 @@ /// various places. void identifyDefaultAbstractAttributes( Function &F, InformationCache &InfoCache, + std::function &LoopInfoGetter, DenseSet *Whitelist = nullptr); /// Check \p Pred on all function call sites. @@ -345,6 +348,11 @@ return FuncRWInstsMap[&F]; } + /// Return LoopInfo for \p F. + LoopInfo *getLoopInfoForFunction(const Function &F) { + return FuncLoopInfoMap[&F]; + } + private: /// A map type from functions to opcode to instruction maps. using FuncInstOpcodeMapTy = DenseMap; @@ -352,6 +360,9 @@ /// A map type from functions to their read or write instructions. using FuncRWInstsMapTy = DenseMap; + /// A map type from functions to their LoopInfo. + using FuncLoopInfoMapTy = DenseMap; + /// A nested map that remembers all instructions in a function with a certain /// instruction opcode (Instruction::getOpcode()). FuncInstOpcodeMapTy FuncInstOpcodeMap; @@ -359,6 +370,9 @@ /// A map from functions to their instructions that may read or write memory. FuncRWInstsMapTy FuncRWInstsMap; + /// A map from functions to their LoopInfo. + FuncLoopInfoMapTy FuncLoopInfoMap; + /// Give the Attributor access to the members so /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them. friend struct Attributor; @@ -1027,6 +1041,38 @@ /// Unique ID (due to the unique address) static const char ID; }; +/// An abstract interface for loop attributes. +struct AALoop : public AbstractAttribute, public IRPosition { + IRPositionConstructorForward(AALoop, IRPosition); + + /// Return true if a loop is assumed "never-endless". + virtual bool isAssumedNeverEndless(Loop *) const = 0; + + /// Return true if a loop is assumed "always-endless". + virtual bool isAssumedAlwaysEndless(Loop *) const = 0; + + /// Return true if a loop is assumed "maybe-endless". + virtual bool isAssumedMaybeEndless(Loop *) const = 0; + + /// Return true if a loop is known "never-endless". + virtual bool isKnownNeverEndless(Loop *) const = 0; + + /// Return true if a loop is known "always-endless". + virtual bool isKnownAlwaysEndless(Loop *) const = 0; + + /// Return true if a loop is known "maybe-endless". + virtual bool isKnownMaybeEndless(Loop *) const = 0; + + /// Return an IR position, see struct IRPosition. + /// + ///{ + IRPosition &getIRPosition() { return *this; } + const IRPosition &getIRPosition() const { return *this; } + ///} + + /// Unique ID (due to the unique address) + static const char ID; +}; } // end namespace llvm Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -16,11 +16,13 @@ #include "llvm/Transforms/IPO/Attributor.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/GlobalsModRef.h" @@ -1243,33 +1245,21 @@ ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; }; -// Helper function that checks whether a function has any cycle. -// TODO: Replace with more efficent code -bool containsCycle(Function &F) { - SmallPtrSet Visited; - - // Traverse BB by dfs and check whether successor is already visited. - for (BasicBlock *BB : depth_first(&F)) { - Visited.insert(BB); - for (auto *SuccBB : successors(BB)) { - if (Visited.count(SuccBB)) - return true; - } - } - return false; +// Helper function that checks the function contains a irreducible loop. +static bool containsIrreducibleLoop(Function &F, InformationCache &InfoCache) { + const LoopInfo &LI = *InfoCache.getLoopInfoForFunction(F); + using RPOTraversal = ReversePostOrderTraversal; + RPOTraversal FuncRPOT(&F); + return containsIrreducibleCFG(FuncRPOT, LI); } -// Helper function that checks the function have a loop which might become an -// endless loop -// FIXME: Any cycle is regarded as endless loop for now. -// We have to allow some patterns. -bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); } - void AAWillReturnFunction::initialize(Attributor &A, InformationCache &InfoCache) { Function &F = getAnchorScope(); - if (containsPossiblyEndlessLoop(F)) + // If we find irreducible loop, indicate pessimistic for now. + if (containsIrreducibleLoop(F, InfoCache)) indicatePessimisticFixpoint(); } @@ -1299,6 +1289,12 @@ InfoCache)) return indicatePessimisticFixpoint(); + auto *LoopAA = A.getAAFor(*this, F); + + for (Loop *L : *InfoCache.getLoopInfoForFunction(F)) + if (!LoopAA || !LoopAA->isAssumedNeverEndless(L)) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; } @@ -2428,8 +2424,11 @@ void Attributor::identifyDefaultAbstractAttributes( Function &F, InformationCache &InfoCache, + std::function &LoopInfoGetter, DenseSet *Whitelist) { + InfoCache.FuncLoopInfoMap[&F] = &LoopInfoGetter(F); + // Check for dead BasicBlocks in every function. // We need dead instruction detection because we do not want to deal with // broken IR in which SSA rules do not apply. @@ -2593,7 +2592,9 @@ /// Pass (Manager) Boilerplate /// ---------------------------------------------------------------------------- -static bool runAttributorOnModule(Module &M) { +static bool +runAttributorOnModule(Module &M, + std::function &LoopInfoGetter) { if (DisableAttributor) return false; @@ -2627,14 +2628,19 @@ // Populate the Attributor with abstract attribute opportunities in the // function and the information cache with IR information. - A.identifyDefaultAbstractAttributes(F, InfoCache); + A.identifyDefaultAbstractAttributes(F, InfoCache, LoopInfoGetter); } return A.run(InfoCache) == ChangeStatus::CHANGED; } PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { - if (runAttributorOnModule(M)) { + auto &FAM = AM.getResult(M).getManager(); + + std::function LoopInfoGetter = + [&](Function &F) -> LoopInfo & { return FAM.getResult(F); }; + + if (runAttributorOnModule(M, LoopInfoGetter)) { // FIXME: Think about passes we will preserve and add them here. return PreservedAnalyses::none(); } @@ -2653,12 +2659,18 @@ bool runOnModule(Module &M) override { if (skipModule(M)) return false; - return runAttributorOnModule(M); + std::function LoopInfoGetter = + [&](Function &F) -> LoopInfo & { + return getAnalysis(F).getLoopInfo(); + }; + + return runAttributorOnModule(M, LoopInfoGetter); } void getAnalysisUsage(AnalysisUsage &AU) const override { // FIXME: Think about passes we will preserve and add them here. AU.setPreservesCFG(); + AU.addRequired(); } }; @@ -2680,8 +2692,10 @@ const char AAIsDead::ID = 0; const char AADereferenceable::ID = 0; const char AAAlign::ID = 0; +const char AALoop::ID = 0; INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) Index: llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll =================================================================== --- llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll +++ llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll @@ -161,5 +161,5 @@ ; ; CHECK-NOT: attributes # ; CHECK: attributes #{{.*}} = { nofree nosync nounwind } -; CHECK: attributes #{{.*}} = { nofree norecurse nosync nounwind } +; CHECK: attributes #{{.*}} = { nofree norecurse nosync nounwind willreturn } ; CHECK-NOT: attributes #