[Attributor] Add LoopInfo to InformationCache and improve willreturn deduction

[uenoku]

Summary

In this patch, LoopInfo is added to InformationCache and used for willreturn function attribute deduction.

We can have willreturn if we assume all the loops in the function are assumed as never-endless (concrete implementation is in D65296. In this patch, only interfaces are provided). If there is an irreducible loop in function, we reach pessimistic fixpoint for now.

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

374

I think you cannot cache the loop info objects (if you do not create them yourself at least). See also below.

llvm/lib/Transforms/IPO/Attributor.cpp

1255

Add this to the AALoop interface so we can query it easily and cache the results in there.

1296

LoopInfo::begin/end only traverses outermost loops.

Add a helper in the Attributor: checkForAllLoops(...) that traverses the outermost loops and transitively their child loops. We can then also employ liveness transparently.

2430

I think you have to store the LoopInfoGetter in the InfoCache and query it each time. Thought, I might be wrong.

llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll

163 ↗

(On Diff #213846)

Can you add the willreturn to the Function Attr: check where it changed?

[uenoku]

Rebase and add checkForAllLoop.

This code doesn't work well with Old PassManager so tests are currently missing.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1390

No static variables as part of the logic please.

[uenoku]

Address comment

[jdoerfert]

Does this affect any tests?

llvm/include/llvm/Transforms/IPO/Attributor.h

1523

Given that this already has an "AbstractState" you can put the implementations in this class.

llvm/lib/Transforms/IPO/Attributor.cpp

2724

You don't seem to use it here. Do you plan to create an AALoop for each loop or one for a function? I guess the latter would allow to cache irreducible information as well.

llvm/include/llvm/Transforms/IPO/Attributor.h

 #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"
 

   UNCHANGED,
 };
 
+using LoopInfoMapTy = const std::function<LoopInfo *(const Function &)>;
+
 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
 ///}

 /// 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<unsigned, SmallVector<Instruction *, 32>>;

     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<const Function *, OpcodeInstMapTy>;

   /// 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;

   /// 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

   /// instance, which can be queried without the need to look at the IR in
   /// various places.
   void identifyDefaultAbstractAttributes(
-      Function &F, DenseSet<const char *> *Whitelist = nullptr);
+      Function &F, LoopInfoMapTy &LoopInfoGetter,
+      DenseSet<const char *> *Whitelist = nullptr);
 
   /// Return true if \p AA (or its context instruction) is assumed dead.
   ///

       const llvm::function_ref<bool(Instruction &)> &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<bool(Loop &)> &Pred,
+                       AbstractAttribute &QueryingAA);
+
   /// Return the data layout associated with the anchor scope.
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 

   static const char ID;
 };
 
+/// An abstract interface for loop attributes.
+struct AALoop : public StateWrapper<BooleanState, AbstractAttribute>,
+                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

llvm/lib/Transforms/IPO/Attributor.cpp

 
 #include "llvm/Transforms/IPO/Attributor.h"
 
-#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"

     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
                           cl::desc("Maximal number of fixpoint iterations."),
                           cl::init(32));
-
 static cl::opt<bool> DisableAttributor(
     "attributor-disable", cl::Hidden,
     cl::desc("Disable the attributor inter-procedural deduction pass."),

 
 /// ------------------------ Will-Return Attributes ----------------------------
 
+// Helper function that checks the function contains a irreducible loop.
+// TODO: Move this to AALoop and cache the result.
+static bool containsIrreducibleLoop(const Function *F,  LoopInfo&LI) {
+    using RPOTraversal = ReversePostOrderTraversal<const Function *>;
+    RPOTraversal FuncRPOT(F);
+    bool Result = containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
+                                         const LoopInfo>(FuncRPOT, LI);
+
+    return Result;
+}
+
 // Helper function that checks whether a function has any cycle.
 // TODO: Replace with more efficent code
 static bool containsCycle(Function &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);
+// endless loop.
+static bool containsPossiblyEndlessLoop(Function *F, Attributor &A) {
+  if(!F || !F->hasExactDefinition()) return true;
+
+  if(LoopInfo *LI = A.getInfoCache().getLoopInfo(*F))
+    return containsIrreducibleLoop(F, *LI);
+  return containsCycle(*F);
 }
 
+
 struct AAWillReturnImpl : public AAWillReturn {
   AAWillReturnImpl(const IRPosition &IRP) : AAWillReturn(IRP) {}
 

     }
 
     Function *F = getAssociatedFunction();
-    if (containsPossiblyEndlessLoop(F))
+    if (containsPossiblyEndlessLoop(F, A))
       indicatePessimisticFixpoint();
   }
 

     if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this))
       return indicatePessimisticFixpoint();
 
+    auto &LoopAA = A.getAAFor<AALoop>(
+        *this, IRPosition::function(*getAssociatedFunction()));
+
+    auto CheckForLoop = [&](Loop &L) {
+      return !LoopAA.isAssumedNeverEndless(L);
+    };
+
+    if (!A.checkForAllLoop(CheckForLoop, *this))
+      return indicatePessimisticFixpoint();
+
     return ChangeStatus::UNCHANGED;
   }
 

 /// 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
 /// ----------------------------------------------------------------------------

   return true;
 }
 
+bool Attributor::checkForAllLoop(const llvm::function_ref<bool(Loop &)> &Pred,
+                                 AbstractAttribute &QueryingAA) {
+  const Function *AssociatedFunction =
+      QueryingAA.getIRPosition().getAssociatedFunction();
+  if (!AssociatedFunction)
+    return false;
+
+  // TODO: Use liveness
+  LoopInfo* LI = InfoCache.getLoopInfo(*AssociatedFunction);
+  if(!LI)
+    return false;
+
+  SmallVector<Loop *, 4> 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++)

 }
 
 void Attributor::identifyDefaultAbstractAttributes(
-    Function &F, DenseSet<const char *> *Whitelist) {
+    Function &F, LoopInfoMapTy& LoopInfoGetter,
+    DenseSet<const char *> *Whitelist) {
 
   IRPosition FPos = IRPosition::function(F);
 

 ///                       Pass (Manager) Boilerplate
 /// ----------------------------------------------------------------------------
 
-static bool runAttributorOnModule(Module &M) {
+static bool runAttributorOnModule(Module &M, LoopInfoMapTy &LoopInfoGetter) {
   if (DisableAttributor)
     return false;
 

 
   // 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) {

 
     // 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<FunctionAnalysisManagerModuleProxy>(M).getManager();
+
+  LoopInfoMapTy LoopInfoGetter = [&](const Function &F) -> LoopInfo * {
+    return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
+  };
+
+  if (runAttributorOnModule(M, LoopInfoGetter)) {
     // FIXME: Think about passes we will preserve and add them here.
     return PreservedAnalyses::none();
   }

   bool runOnModule(Module &M) override {
     if (skipModule(M))
       return false;
-    return runAttributorOnModule(M);
+
+    LoopInfoMapTy LoopInfoGetter = [&](const Function &F) -> LoopInfo * {
+      return nullptr;
+    };
+
+    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<LoopInfoWrapperPass>();
   }
 };
 

 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.

 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)

 
 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)