[Attributor] Loop Abstract Attribute

[uenoku]

Summary

This patch would add Loop Abstract Attribute which analyses a termination of Loop in Attributor Framework.
This attribute will determine whether the loop satisfies each of these properties.

• always-endless

It means that a loop will terminate finally. This property would be used to improve willreturn attribute deduction.

• never-endless

It means that a loop will never terminate. This property would be used to improve noreturn attribute deduction.

Currently, this patch only contains the prototype of them so a lot of things including tests will be added later.

[jdoerfert]

I think we also want to look at:

• loop exit conditions to show that they are trivial/never fulfilled
• instructions in the loop to show that endless loops would cause UB eventually

[uenoku]

In D65296#1602397, @jdoerfert wrote:

• instructions in the loop to show that endless loops would cause UB eventually

I couldn't come up with how this can be used for the deduction. For example, alloca in the loop would cause UB but what information this gives us? I think endless loops would itself be a very strong thing.

[lebedev.ri]

Please note that endless loops in itself is not UB in IR.

[uenoku]

In D65296#1603832, @lebedev.ri wrote:

Please note that endless loops in itself is not UB in IR.

I see. Thanks.

[jdoerfert]

In D65296#1603832, @lebedev.ri wrote:

Please note that endless loops in itself is not UB in IR.

Correct.

One way to generate UB is through accesses or control involving poison.
What I wanted us to do is derive "not endless" for the following kinds of loops:

int s = ...
while (s++) ...;                     // overflow -> poison value -> poison in control 
while (s + NonZero != N) ...;        // overflow -> poison value -> poison in control
while (s * NonOneNonZero != N) ...;  // overflow -> poison value -> poison in control
...

while (...)
  access A[s++]        // overflow -> poison value -> poison access address 

unsigned u = ...;
while (...)
  access A[u++]        // Assuming NULL is not a valid pointer && "alignment of %ptr" modulo "sizeof(*ptr)" == 0

while (...)
  access A[u++]        // not strictly UB, depending on the types, but reasonable to exploit anyway (I think), potentially under a flag)

(I use signed/unsigned as an alternative to nsw/nuw in the GEP/add.)
We have helpers to determine poison and poison propagation (I think). For now, I'd be fine with the easy cases
for (int i = ...; i cmp ...; i++) { ... } and `for (int i = ...; ...; i++) { ... A[i] ... }
(Must-be-executed is can/should potentially be used here as well.)

For example, alloca in the loop would cause UB but what information this gives us

Arguably, it would not be UB even if every implementation has limited memory. The problem is, I think, that a failed allocation alone is not UB.
Even if we have accesses on that allocation (which I doubt we find in the wild anyway), we would be in the same case as the last example above, not actually UB.

[jdoerfert]

Maybe, to simplify the first version, due the following "cannot be infinite" check: if the loop doesn't make forward progress, thus it is nosync, it has to be ending eventually.

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

 //   need to traverse the IR repeatedly.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #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"
 
 namespace llvm {
 
 struct AbstractAttribute;
 struct InformationCache;
 
struct AADereferenceable : public AbstractAttribute {
 
   /// See AbastractState::getAttrKind().
   Attribute::AttrKind getAttrKind() const override { return ID; }
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::Dereferenceable;
 };
 
+/// An abstract interface for loop attributes.
+struct AALoop : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AALoop(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(V, InfoCache) {}
+
+  /// See AbastractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override { return ID; }
+
+  /// 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;
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID =
+      Attribute::AttrKind(Attribute::EndAttrKinds + 2);
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

ChangeStatus AADereferenceableCallSiteArgument::updateImpl(Attributor &A) {
 
   takeAssumedDerefBytesMinimum(
       computeAssumedDerefenceableBytes(A, V, IsNonNull, IsGlobal));
   updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
 
   return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
                                                        : ChangeStatus::CHANGED;
 }
+/// -------------------AALoop Function Attribute-----------------------
+struct AALoopFunction : AALoop, BooleanState {
+
+  AALoopFunction(Function &F, InformationCache &InfoCache)
+      : AALoop(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  /// See AbstractAttribute::getManifestPosition().
+  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
+
+  const std::string getAsStr() const override {
+    return "LoopAA(N " + std::to_string(NoReturnCalls.size()) + "/W " +
+           std::to_string(WillReturnCalls.size()) + ")";
+  }
+
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+    for (Instruction &I : instructions(F)) {
+      ImmutableCallSite ICS(&I);
+      if (ICS) {
+        NoReturnCalls.insert(&I);
+        WillReturnCalls.insert(&I);
+      }
+    }
+  }
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AALoop::isAssumedNeverEndless(Loop*).
+  bool isAssumedNeverEndless(Loop *) const override;
+
+  /// See AALoop::isAssumedAlwaysEndless(Loop*).
+  bool isAssumedAlwaysEndless(Loop *) const override;
+
+  /// Collection of calls with noreturn attribute, assumed or knwon.
+  SmallSetVector<Instruction *, 4> NoReturnCalls;
+
+  /// Collection of calls with willreturn attribute, assumed or knwon.
+  SmallSetVector<Instruction *, 4> WillReturnCalls;
+};
+
+ChangeStatus AALoopFunction::updateImpl(Attributor &A) {
+  SmallVector<Instruction *, 8> NoReturnBefore, WillReturnBefore;
+
+  ChangeStatus Status = ChangeStatus::UNCHANGED;
+
+  NoReturnBefore.assign(NoReturnCalls.begin(), NoReturnCalls.end());
+  WillReturnBefore.assign(WillReturnCalls.begin(), WillReturnCalls.end());
+
+  for (Instruction *I : NoReturnBefore) {
+    auto NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
+    if (!NoReturnAA || !NoReturnAA->isAssumedNoReturn()) {
+      NoReturnCalls.remove(I);
+      Status = ChangeStatus::CHANGED;
+    }
+  }
+
+  for (Instruction *I : WillReturnBefore) {
+    auto WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
+    if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
+      WillReturnCalls.remove(I);
+      Status = ChangeStatus::CHANGED;
+    }
+  }
+
+  if (WillReturnCalls.empty() && NoReturnCalls.empty())
+    indicatePessimisticFixpoint();
+
+  return Status;
+}
+// "always-endless" is assumed if the loop satisfies any of following
+// conditions.
+// (i) There is no exit block.
+// (ii) There is function call assumed no-return and guaranteed to be executed.
+// (iii) Break condition would be never
+// satisfied.
+bool AALoopFunction::isAssumedAlwaysEndless(Loop *L) const {
+
+  // (i) Check whether there is no exit block.
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() == 0)
+    return true;
+
+  // (ii) For now, only traverse instructions in Header.
+  BasicBlock &Header = *L->getHeader();
+  for (Instruction &I : Header) {
+    ImmutableCallSite ICS(&I);
+    if (ICS && NoReturnCalls.count(&I))
+      return true;
+  }
+
+  // TODO: Implement break condition check(iii).
+
+  return false;
+}
+// "never-endless" is assumed if the loop satisfies all of following conditions.
+// (i) All calls are assumed willreturn.
+// (ii) Break condition would be satisfied anyway.
+bool AALoopFunction::isAssumedNeverEndless(Loop *L) const {
+  for (BasicBlock *BB : L->getBlocks()) {
+    for (Instruction &I : *BB) {
+      ImmutableCallSite ICS(&I);
+      if (ICS && !WillReturnCalls.count(&I))
+        return false;
+    }
+  }
+  // TODO: Implement (ii)
+  return false;
+}
 
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
                                       std::function<bool(CallSite)> &Pred,
                                       bool RequireAllCallSites) {
void Attributor::identifyDefaultAbstractAttributes(
   }
 
   // Every function might be "will-return".
   registerAA(*new AAWillReturnFunction(F, InfoCache));
 
   // Check for dead BasicBlocks in every function.
   registerAA(*new AAIsDeadFunction(F, InfoCache));
 
+  // Register AALoop for every function.
+  registerAA(*new AALoopFunction(F, InfoCache));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
   for (Instruction &I : instructions(&F)) {
     bool IsInterestingOpcode = false;