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/ADT/SetVector.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/PassManager.h" @@ -116,6 +117,8 @@ UNCHANGED, }; +using LoopInfoMapTy = const std::function; + ChangeStatus operator|(ChangeStatus l, ChangeStatus r); ChangeStatus operator&(ChangeStatus l, ChangeStatus r); ///} @@ -495,7 +498,8 @@ /// reusable, it is advised to inherit from the InformationCache and cast the /// instance down in the abstract attributes. struct InformationCache { - InformationCache(const DataLayout &DL) : DL(DL) {} + InformationCache(const DataLayout &DL, LoopInfoMapTy &LoopInfoGetter) + : DL(DL), LoopInfoGetter(LoopInfoGetter) {} /// A map type from opcodes to instructions with this opcode. using OpcodeInstMapTy = DenseMap>; @@ -514,6 +518,8 @@ return FuncRWInstsMap[&F]; } + LoopInfo &getLoopInfo(const Function &F) { return LoopInfoGetter(F); } + private: /// A map type from functions to opcode to instruction maps. using FuncInstOpcodeMapTy = DenseMap; @@ -531,6 +537,9 @@ /// The datalayout used in the module. const DataLayout &DL; + /// A map from function to LoopInfo. + LoopInfoMapTy &LoopInfoGetter; + /// Give the Attributor access to the members so /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them. friend struct Attributor; @@ -641,6 +650,7 @@ /// abstract attribute objects for them. /// /// \param F The function that is checked for attribute opportunities. + /// \param LoopInfoGetter A map from function to its LoopInfo. /// \param Whitelist If not null, a set limiting the attribute opportunities. /// /// Note that abstract attribute instances are generally created even if the @@ -649,7 +659,8 @@ /// instance, which can be queried without the need to look at the IR in /// various places. void identifyDefaultAbstractAttributes( - Function &F, DenseSet *Whitelist = nullptr); + Function &F, LoopInfoMapTy &LoopInfoGetter, + DenseSet *Whitelist = nullptr); /// Return true if \p AA (or its context instruction) is assumed dead. /// @@ -712,6 +723,13 @@ const llvm::function_ref &Pred, AbstractAttribute &QueryingAA); + /// Check \p Pred on all loops in the function. + /// + /// This method will evaluate \p Pred on all loops and return true if \p Pred + /// holds on all of them. + bool checkForAllLoop(const llvm::function_ref &Pred, + AbstractAttribute &QueryingAA); + /// Return the data layout associated with the anchor scope. const DataLayout &getDataLayout() const { return InfoCache.DL; } @@ -1395,6 +1413,43 @@ static const char ID; }; +/// An abstract interface for loop attributes. +struct AALoop : public StateWrapper, + public IRPosition { + AALoop(const IRPosition &IRP) : IRPosition(IRP) {} + + /// 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; } + ///} + + /// Create an abstract attribute view for the position \p IRP. + static AALoop &createForPosition(const IRPosition &IRP, Attributor &A); + + /// Unique ID (due to the unique address) + static const char ID; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -15,12 +15,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" @@ -1384,28 +1385,23 @@ /// ------------------------ Will-Return Attributes ---------------------------- -// Helper function that checks whether a function has any cycle. -// TODO: Replace with more efficent code -static bool containsCycle(Function &F) { - SmallPtrSet Visited; +// Helper function that checks the function contains a irreducible loop. +static bool containsIrreducibleLoop(const Function *F, Attributor &A) { + static DenseMap ContainsIrreducibleLoopCache; + if (!F || !F->hasExactDefinition()) + return true; - // 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; -} + if (ContainsIrreducibleLoopCache.count(F)) + return ContainsIrreducibleLoopCache[F]; -// 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. -static bool containsPossiblyEndlessLoop(Function *F) { - return !F || !F->hasExactDefinition() || containsCycle(*F); + const LoopInfo &LI = A.getInfoCache().getLoopInfo(*F); + using RPOTraversal = ReversePostOrderTraversal; + RPOTraversal FuncRPOT(F); + bool Result = containsIrreducibleCFG(FuncRPOT, LI); + + ContainsIrreducibleLoopCache[F] = Result; + return Result; } struct AAWillReturnImpl : public AAWillReturn { @@ -1419,7 +1415,7 @@ } Function *F = getAssociatedFunction(); - if (containsPossiblyEndlessLoop(F)) + if (containsIrreducibleLoop(F, A)) indicatePessimisticFixpoint(); } @@ -1439,6 +1435,16 @@ if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this)) return indicatePessimisticFixpoint(); + auto &LoopAA = A.getAAFor( + *this, IRPosition::function(*getAssociatedFunction())); + + auto CheckForLoop = [&](Loop &L) { + return !LoopAA.isAssumedNeverEndless(L); + }; + + if (!A.checkForAllLoop(CheckForLoop, *this)) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; } @@ -2236,6 +2242,63 @@ /// NoReturn attribute deduction for a call sites. using AANoReturnCallSite = AANoReturnFunction; +struct AALoopImpl : public AALoop { + AALoopImpl(const IRPosition &IRP) : AALoop(IRP) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { return "AALoop"; } + + /// See AbstractAttribute::updateImpl(Attributor &A). + virtual ChangeStatus updateImpl(Attributor &A) override { + // TODO: Implement this + return indicatePessimisticFixpoint(); + } + + /// See AALoop::isAssumedNeverEndless(Loop&). + virtual bool isAssumedNeverEndless(Loop &) const override { + // TODO: Implement this + return false; + } + + /// See AALoop::isAssumedAlwaysEndless(Loop&). + virtual bool isAssumedAlwaysEndless(Loop &) const override { + // TODO: Implement this + return false; + } + + /// See AALoop::isAssumedMaybeEndless(Loop&). + virtual bool isAssumedMaybeEndless(Loop &) const override { + // TODO: Implement this + return false; + } + + /// See AALoop::isKnownNeverEndless(Loop&). + virtual bool isKnownNeverEndless(Loop &) const override { + // TODO: Implement this + return false; + } + + /// See AALoop::isKnownAlwaysEndless(Loop&). + virtual bool isKnownAlwaysEndless(Loop &) const override { + // TODO: Implement this + return false; + } + + /// See AALoop::isKnownMaybeEndless(Loop&). + virtual bool isKnownMaybeEndless(Loop &) const override { + // TODO: Implement this + return false; + } +}; +struct AALoopFunction final : public AALoopImpl { + AALoopFunction(const IRPosition &IRP) : AALoopImpl(IRP) {} + + /// See AbstractAttribute::trackStatistics(). + void trackStatistics() const override {} +}; + +using AALoopCallSite = AALoopFunction; + /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -2404,7 +2467,23 @@ return true; } +bool Attributor::checkForAllLoop(const llvm::function_ref &Pred, + AbstractAttribute &QueryingAA) { + const Function *AssociatedFunction = + QueryingAA.getIRPosition().getAssociatedFunction(); + if (!AssociatedFunction) + return false; + + // TODO: Use liveness + LoopInfo &LI = InfoCache.getLoopInfo(*AssociatedFunction); + SmallVector PreorderLoops = LI.getLoopsInPreorder(); + for (auto *L : PreorderLoops) + if (!Pred(*L)) + return false; + + return true; +} ChangeStatus Attributor::run() { // Initialize all abstract attributes, allow new ones to be created. for (unsigned u = 0; u < AllAbstractAttributes.size(); u++) @@ -2576,7 +2655,8 @@ } void Attributor::identifyDefaultAbstractAttributes( - Function &F, DenseSet *Whitelist) { + Function &F, LoopInfoMapTy &LoopInfoGetter, + DenseSet *Whitelist) { IRPosition FPos = IRPosition::function(F); @@ -2754,7 +2834,7 @@ /// Pass (Manager) Boilerplate /// ---------------------------------------------------------------------------- -static bool runAttributorOnModule(Module &M) { +static bool runAttributorOnModule(Module &M, LoopInfoMapTy &LoopInfoGetter) { if (DisableAttributor) return false; @@ -2763,7 +2843,7 @@ // Create an Attributor and initially empty information cache that is filled // while we identify default attribute opportunities. - InformationCache InfoCache(M.getDataLayout()); + InformationCache InfoCache(M.getDataLayout(), LoopInfoGetter); Attributor A(InfoCache); for (Function &F : M) { @@ -2788,14 +2868,20 @@ // Populate the Attributor with abstract attribute opportunities in the // function and the information cache with IR information. - A.identifyDefaultAbstractAttributes(F); + A.identifyDefaultAbstractAttributes(F, LoopInfoGetter); } return A.run() == ChangeStatus::CHANGED; } PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { - if (runAttributorOnModule(M)) { + auto &FAM = AM.getResult(M).getManager(); + + LoopInfoMapTy LoopInfoGetter = [&](const Function &F) -> LoopInfo & { + return FAM.getResult(const_cast(F)); + }; + + if (runAttributorOnModule(M, LoopInfoGetter)) { // FIXME: Think about passes we will preserve and add them here. return PreservedAnalyses::none(); } @@ -2814,12 +2900,19 @@ bool runOnModule(Module &M) override { if (skipModule(M)) return false; - return runAttributorOnModule(M); + + LoopInfoMapTy LoopInfoGetter = [&](const Function &F) -> LoopInfo & { + return getAnalysis(const_cast(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(); } }; @@ -2841,6 +2934,7 @@ const char AAIsDead::ID = 0; const char AADereferenceable::ID = 0; const char AAAlign::ID = 0; +const char AALoop::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -2896,6 +2990,7 @@ CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues) +CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AALoop) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias) @@ -2909,5 +3004,6 @@ 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)