[Attributor][WIP] Introduce Loop AA

[bbn]

Summary

This function abstract attribute identifies whether the loops in a function are
"always-endless" or "never-endless". We can use such information to improve
the deduction of "willreturn" and undefined behavior.

[bbn]

I am still working on this, tests will be added later.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7948–7952

I don't think this is correct.
for known endless, range can contain 1 if the range is in [0,1].
I don't think you can prove a loop is endless by looking at the range (except for it always being 0)
IMHO you should look at the SCEV, what does other people think ?
@jdoerfert

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7948–7952

I am sorry I ment never endless. in the 3th line phab won't let me change the inline comment.

[baziotis]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7942

Instead of looping every instruction, you can use getTerminator() and check if it's a branch.

7943

For that to make sense, you have to verify that the branch isConditional(). Also, note that loops
may be rotated. In that case, the condition is not in the header block, but in the latch.

Generally, loops can get quite complicated and so, as Kuter said, you probably want to use
SCEV (for example, backedge taken count etc.) I'll have to think that again because SCEV
won't benefit from Attributor, meaning, at a high-level, using constant range AA when it makes
sense seems reasonable.

[uenoku]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

FWIW, AAConstantRange actually uses SCEV internally but I agree that using AAConstantRange might make things complicated as a starting point. So you can use SCEV first.

[baziotis]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

Yes, but the point is that using constant range directly makes things difficult because we have to re-deduce information and loop structure that SCEV is supposed to handle (e.g. the code above is doing something similar to backedge taken count).

[bbn]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

Thanks for the idea.

1. I think even if the loop is rotated, we can use such method to determine whether a loop is endless or not, right?
2. I think SCEV could be a good idea, but I cannot find a reasonable test for this. The range I get is always "full-set", can you give an example for this? Thanks

[uenoku]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

I think SCEV could be a good idea, but I cannot find a reasonable test for this. The range I get is always "full-set", can you give an example for this?

We have tests for loop terminations in a test for willreturn (I guess)

[baziotis]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

1. Well, it gets really complicated (and hacky) really fast. You have to have two code paths; one for rotated and one for not. Also, I agree with Kuter in the other comment. For an "always true" condition, the range has to be _equal_ to 1, not just contain it.

But even with an always true condition, you're not sure the loop is endless.
Because the loop might have some kind of control
flow inside that makes the loop stop. For example:

while (some condition that is always true) {
  if (some condition that makes the loop stop at some point)
    break;
}

Which brings us again to the initial point: It seems using SCEV is the only sane way. SCEV is
supposed to handle all that and other analyses / transformations to use it, instead of replicating
part of its functionality.

I think SCEV could be a good idea, but I cannot find a reasonable test for this

For what ?

The range I get is always "full-set", can you give an example for this?

@uenoku should be able to help you here.

[uenoku]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

I think even if the loop is rotated, we can use such method to determine whether a loop is endless or not, right

Maybe we can first check the loop is canonicalized or not. If the loop is LCSSA, things get easier.
But as @baziotis says we need to replicate the code so it's not clear we should do similar things here.
One solution would be adding callbacks to SCEV and using Attributor information from SCEV but it would be (really) complicated and difficult.

[bbn]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

Thanks for the idea here. I will take a look at it.

[baziotis]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

Maybe we can first check the loop is canonicalized or not. If the loop is LCSSA, things get easier.

How would LCSSA help ? Btw, @bbn if you want to read about LCSSA or other canonical forms, you can check this: https://llvm.org/docs/LoopTerminology.html

One solution would be adding callbacks to SCEV and using Attributor information from SCEV but it would be (really) complicated and difficult.

I mean yes, ideally SCEV would do its thing by taking advantage of the Attributor. But right now, it's certainly a bad idea unless we have a good plan for it.

[uenoku]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

I thought we can use SCEV more easily and discuss the exit conditions more simply by restricting the loop form. However, Come to think of it, LCSSA itself doesn't help the dedication. Sorry for confusion;)

I mean yes, ideally SCEV would do its thing by taking advantage of the Attributor. But right now, it's certainly a bad idea unless we have a good plan for it.

Yes, I agree

[baziotis]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7943

Great and np. So, @bbn you can try SCEV and don't hesitate to ask if you have any problem. SCEV is a beast, I know from experience :)

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

struct AAUndefinedBehavior
   static bool classof(const AbstractAttribute *AA) {
     return (AA->getIdAddr() == &ID);
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// An abstract attribute for loops.
+struct AALoop : public StateWrapper<BooleanState, AbstractAttribute> {
+  using Base = StateWrapper<BooleanState, AbstractAttribute>;
+  AALoop(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+  /// Return true if the loop is assumed "never-endless"
+  virtual bool isAssumedNeverEndless(Loop *) const = 0;
+
+  /// Return true if the loop is known "always-endless"
+  virtual bool isKnownAlwaysEndless(Loop *) const = 0;
+
+  /// Create an abstract attribute view for the position \p IRP
+  static AALoop &createForPosition(const IRPosition &IRP, Attributor &A);
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AALoop"; }
+
+  /// See AbstractAttribute::getIdAddr()
+  const char *getIdAddr() const override { return &ID; }
+
+  /// This function should return true if the type of \p AA is
+  /// AALoop
+  static bool classof(const AbstractAttribute *AA) {
+    return (AA->getIdAddr() == &ID);
+  }
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
 /// An abstract interface to determine reachability of point A to B.
 struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute> {
   using Base = StateWrapper<BooleanState, AbstractAttribute>;
   AAReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
 
   /// 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.

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyValueInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/InitializePasses.h"
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   getOrCreateAAFor<AAIsDead>(FPos);
 
   // Every function might be "will-return".
   getOrCreateAAFor<AAWillReturn>(FPos);
 
   // Every function might contain instructions that cause "undefined behavior".
   getOrCreateAAFor<AAUndefinedBehavior>(FPos);
 
+  // Every function might contain loops
+  // TODO: lets only analyse functions that only contain loops
+  getOrCreateAAFor<AALoop>(FPos);
+
   // Every function can be nounwind.
   getOrCreateAAFor<AANoUnwind>(FPos);
 
   // Every function might be marked "nosync"
   getOrCreateAAFor<AANoSync>(FPos);
 
   // Every function might be "no-free".
   getOrCreateAAFor<AANoFree>(FPos);

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 //===- AttributorAttributes.cpp - Attributes for Attributor deduction -----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // See the Attributor.h file comment and the class descriptions in that file for
 // more information.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CaptureTracking.h"

 PIPE_OPERATOR(AAReachability)
 PIPE_OPERATOR(AAMemoryBehavior)
 PIPE_OPERATOR(AAMemoryLocation)
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
 PIPE_OPERATOR(AAPotentialValues)
 PIPE_OPERATOR(AANoUndef)
+PIPE_OPERATOR(AALoop)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
 
 namespace {
 
 static Optional<ConstantInt *>
 getAssumedConstantInt(Attributor &A, const Value &V,

 struct AANoUndefCallSiteReturned final
     : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl> {
   AANoUndefCallSiteReturned(const IRPosition &IRP, Attributor &A)
       : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl>(IRP, A) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noundef) }
 };
+
+/// ------------------------ Loop Attribute -----------------------------------
+
+struct AALoopImpl : public AALoop {
+  AALoopImpl(const IRPosition &IRP, Attributor &A) : AALoop(IRP, A) {}
+
+  /// See AbstractAttribute::getAsStr()
+  const std::string getAsStr() const override {
+    std::string Str;
+    llvm::raw_string_ostream OS(Str);
+    OS << "Loop always_endless / may_never_endless: " << KnownAELoops.size()
+       << '/' << MayNELoops.size() << '\n';
+  }
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    // get loop analysis
+    Function *F = getAnchorScope();
+    assert(F && "AALoop expect function scope!");
+    LoopInfo *LI =
+        A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(*F);
+    if (!LI) {
+      indicatePessimisticFixpoint();
+      return;
+    }
+
+    // Check loops for the function and loops that are obviously endless.
+    // TODO: for now we don't handle dead loops here. Such loop will be
+    // eliminated using
+    //       DCE I think, the header will never be accessed.
+    for (Loop *L : LI->getLoopsInPreorder()) {
+      SmallVector<BasicBlock *, 4> ExitingBlocks;
+      L->getExitingBlocks(ExitingBlocks);
+
+      // If a loop does not have exiting block, we can safely say that this loop
+      // is endless
+      if (!ExitingBlocks.size())
+        KnownAELoops.insert(L);
+    }
+  }
+
+  ChangeStatus updateImpl(Attributor &A) override {
+    const size_t AEPrevSize = KnownAELoops.size();
+    const size_t NEPrevSize = MayNELoops.size();
+
+    Function *F = getAnchorScope();
+    LoopInfo *LI =
+        A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(*F);
+
+    // Check for all loops, if the entering condition - the cmp result is always
+    // true, we determine this loop as endless
+    for (Loop *L : LI->getLoopsInPreorder()) {
+      if (KnownAELoops.count(L) && MayNELoops.count(L))
+        continue;
+
+      BasicBlock *HeaderBB = L->getHeader();
+      for (Instruction &I : *HeaderBB) {
+        if (auto *BI = dyn_cast<BranchInst>(&I)) {
+          auto *Op = BI->getOperand(0);
+          const auto &OpAA =
+              A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*Op));
+          auto KnownState = OpAA.getKnown();
+
+          if (KnownState.contains(APInt(1, 1)))
+            KnownAELoops.insert(L);
+          else if (KnownState.isFullSet())
+            MayNELoops.insert(L);
+        }
+      }
+    }
+
+    if (AEPrevSize != KnownAELoops.size() || NEPrevSize != MayNELoops.size())
+      return ChangeStatus::CHANGED;
+
+    return ChangeStatus::UNCHANGED;
+  }
+
+  bool isKnownAlwaysEndless(Loop *L) const override {
+    return KnownAELoops.count(L);
+  }
+
+  bool isAssumedNeverEndless(Loop *L) const override {
+    return MayNELoops.count(L);
+  }
+
+protected:
+  /// A set of all the loops that are known to be always endless (never
+  /// terminate)
+  SmallPtrSet<Loop *, 8> KnownAELoops;
+
+private:
+  /// A set of loops that are assumed to terminate.
+  SmallPtrSet<Loop *, 8> MayNELoops;
+};
+
+struct AALoopFunction final : AALoopImpl {
+  AALoopFunction(const IRPosition &IRP, Attributor &A) : AALoopImpl(IRP, A) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECL(AlwaysEndlessLoops, Loop,
+               "Number of loops known to be always-endless");
+    BUILD_STAT_NAME(AlwaysEndlessLoops, Loop) += KnownAELoops.size();
+  }
+};
 } // namespace
 
 const char AAReturnedValues::ID = 0;
 const char AANoUnwind::ID = 0;
 const char AANoSync::ID = 0;
 const char AANoFree::ID = 0;
 const char AANonNull::ID = 0;
 const char AANoRecurse::ID = 0;

 const char AAValueSimplify::ID = 0;
 const char AAHeapToStack::ID = 0;
 const char AAPrivatizablePtr::ID = 0;
 const char AAMemoryBehavior::ID = 0;
 const char AAMemoryLocation::ID = 0;
 const char AAValueConstantRange::ID = 0;
 const char AAPotentialValues::ID = 0;
 const char AANoUndef::ID = 0;
+const char AALoop::ID = 0;
 
 // Macro magic to create the static generator function for attributes that
 // follow the naming scheme.
 
 #define SWITCH_PK_INV(CLASS, PK, POS_NAME)                                     \
   case IRPosition::PK:                                                         \
     llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
 

 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPotentialValues)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoUndef)
 
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree)
 
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack)
+CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AALoop)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior)
 
 CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior)
 
 #undef CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef SWITCH_PK_CREATE
 #undef SWITCH_PK_INV