[Attributor] NoAlias on return values.

[sstefan1]

Summary

Porting function return value attribute noalias to attributor.
This will be followed with a patch for callsite and function argumets.

[jdoerfert]

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

657 ↗

(On Diff #203759)

"does not alias." is confusing, maybe phrase it is "noalias".

llvm/lib/Transforms/IPO/Attributor.cpp

364 ↗

(On Diff #203759)

Use the AAReturnedValuesImpl instead of an explicit traversal. The AAReturnedValuesImpl knows what is returned and through which return instructions.

371 ↗

(On Diff #203759)

Move this check in the initialize method.

380 ↗

(On Diff #203759)

This is not what we want to check. Look at the returned values and the locations where they are returned.

[sstefan1]

• Addressing comments.
• Updated test cases in nonnull.ll
• Added noalias.ll which, for now, has only one test case. More will be added with other patches regarding noalias attribute.

[jdoerfert]

Why should the return values in nonnull.ll be noalias?

Please also add more explicit noalias return value tests.

llvm/lib/Transforms/IPO/Attributor.cpp

707 ↗

(On Diff #203953)

Why a pessimistic fixpoint? It should be optimistic, right?

723 ↗

(On Diff #203953)

In short:
for (auto &It : *AARetValImpl)

725 ↗

(On Diff #203953)

Make it a const reference, thus add &

731 ↗

(On Diff #203953)

Stores capture, so make the last one a true, also use the /* argumentname */ syntax to explain the booleans.

737 ↗

(On Diff #203953)

You want to check RV here not the return instructions it can be returned through. The latter is only interesting to improve the escape query above but that is future work.

738 ↗

(On Diff #203953)

The call site should be checked separately, e.g. before you ask for the AANoAlias attribute for RV. If RV is a call site and is returnDoesNotAlias all is good. Otherwise, we look at the AANoAlias. That should actually suffice (no Returned needed) and making it more general might make the code potentially more applicable in the future.

903 ↗

(On Diff #203953)

Add the Whitelist check please.

llvm/test/Transforms/FunctionAttrs/noalias.ll

1 ↗

(On Diff #203953)

Can you rename the file to noalias_returned.ll or returned_noalias.ll and also explicitly enable the attributor via -attributor-disable=false

[sstefan1]

Why should the return values in nonnull.ll be noalias?

All functions returning pointer never actually capture it, or they return null. Isn't that enough?

llvm/lib/Transforms/IPO/Attributor.cpp

707 ↗

(On Diff #203953)

Yes, don't know how it happened.

[lebedev.ri]

In D63067#1538100, @sstefan1 wrote:

Why should the return values in nonnull.ll be noalias?

All functions returning pointer never actually capture it, or they return null. Isn't that enough?

This doesn't seem sufficient to me.
Consider:

file1.c
int* getter();
int* callee0() { // will get marked as noalias
  return getter();
}
int* callee1() { // will get marked as noalias
  return getter();
}
int entry() {
  int* p0 = callee0();
  int* p1 = callee1();
  // do p0 and p1 alias?
}

file2.c
int* global;
int* getter() { return global; } // oops

[jdoerfert]

In D63067#1538120, @lebedev.ri wrote:

In D63067#1538100, @sstefan1 wrote:

Why should the return values in nonnull.ll be noalias?

All functions returning pointer never actually capture it, or they return null. Isn't that enough?

This doesn't seem sufficient to me.
Consider:

file1.c
int* getter();
int* callee0() { // will get marked as noalias
  return getter();
}
int* callee1() { // will get marked as noalias
  return getter();
}
int entry() {
  int* p0 = callee0();
  int* p1 = callee1();
  // do p0 and p1 alias?
}

file2.c
int* global;
int* getter() { return global; } // oops

The problem is the pointers returned need to be noalias return pointers as well (that is the missing sufficient condition).

[sstefan1]

addressing comments.

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

903 ↗

(On Diff #203953)

I added the check here, since all noalias attrs will have same id, and both returned and noalias returned are only one per fucntion.

[jdoerfert]

More comments. Can you diff it against the master branch so one can easily see all changes?

llvm/lib/Transforms/IPO/Attributor.cpp

728 ↗

(On Diff #204086)

Please add /* ReturnCaptures */ and a comment (TODO or FIXME) that mentions we could improve the capture check in two ways. 1) Use the AANoCapture facilities, 2) use the location of the associated return insts.

(I just saw, part of the FIXME is down there already!)

733 ↗

(On Diff #204086)

I think you should move a check before the capture check that makes sure we actually have a call site here (for now, thus add a FIXME to support more). If we do not have a call site, we can for now not derive noalias for the return value.

738 ↗

(On Diff #203953)

This was not correct. You need to check for a call here explicitly but you want to check RV.

903 ↗

(On Diff #203953)

The Whitelist check for AANoAliasReturned should be separate and look for AANoAliasReturned::ID.

[sstefan1]

fixed diff, addressed comments

[jdoerfert]

We need more test cases, e.g. as the one below which shows some limits of the current impl.

#include <stdlib.h>

void *baz();
void *foo(int a);

void *bar()  {
  foo(0);
  return baz();
}

void *foo(int a)  {
  if (a)
    bar();
  return malloc(4);
}

llvm/lib/Transforms/IPO/Attributor.cpp

716 ↗

(On Diff #204211)

You have to actually change the status to indicate a pessimistic fixpoint.

725 ↗

(On Diff #204211)

You need to actually give up if RV is not a call site, so if ICS is null.

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

33 ↗

(On Diff #204211)

No need for this check line, I think.

[sstefan1]

We need more test cases, e.g. as the one below which shows some limits of the current impl.

I added just one, besides your example, will add more soon.

• small changes
• added some tests.

[jdoerfert]

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

592 ↗

(On Diff #204410)

is "noalias"

llvm/lib/Transforms/IPO/Attributor.cpp

677 ↗

(On Diff #204410)

No need to overload getDeducedAttributes. The default one will do the right thing.

[sstefan1]

Rebased and added more tests.

[sstefan1]

• removing unnecessary llvm_debug

[jdoerfert]

Fix one comment and Test 5, no check lines and unclear what it is supposed to test. Maybe just remove it.

LGTM otherwise.

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

795 ↗

(On Diff #210972)

is noalias

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

struct AAWillReturn : public AbstractAttribute {
   virtual bool isKnownWillReturn() const = 0;
 
   /// Return true if "willreturn" is assumed.
   virtual bool isAssumedWillReturn() const = 0;
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::WillReturn;
 };
+
+/// An abstract interface for all noalias attributes.
+struct AANoAlias : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoAlias(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(V, InfoCache) {}
+
+  /// Return true if we assume that the underlying value is alias.
+  virtual bool isAssumedNoAlias() const = 0;
+
+  /// Return true if we know that underlying value is noalias.
+  virtual bool isKnownNoAlias() const = 0;
+
+  /// 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::NoAlias;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

 
 #include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
STATISTIC(NumFnArgumentReturned,
           "Number of function arguments marked returned");
 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
 STATISTIC(NumFnReturnedNonNull,
           "Number of function return values marked nonnull");
 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
+STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
 
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint
case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
       break;
     default:
       break;
     }
     break;
   case Attribute::WillReturn:
     NumFnWillReturn++;
     break;
+  case Attribute::NoAlias:
+    NumFnArgumentNoAlias++;
+    return;
   default:
     return;
   }
 }
 
 template <typename StateTy>
 using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
 template <typename StateTy>
for (Instruction *I : OpcodeInstMap[Opcode]) {
         return ChangeStatus::CHANGED;
       }
     }
   }
 
   return ChangeStatus::UNCHANGED;
 }
 
+/// ------------------------ NoAlias Argument Attribute ------------------------
+
+struct AANoAliasImpl : AANoAlias, BooleanState {
+
+  AANoAliasImpl(Value &V, InformationCache &InfoCache)
+      : AANoAlias(V, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  const std::string getAsStr() const override {
+    return getAssumed() ? "noalias" : "may-alias";
+  }
+
+  /// See AANoAlias::isAssumedNoAlias().
+  bool isAssumedNoAlias() const override { return getAssumed(); }
+
+  /// See AANoAlias::isKnowndNoAlias().
+  bool isKnownNoAlias() const override { return getKnown(); }
+};
+
+/// NoAlias attribute for function return value.
+struct AANoAliasReturned : AANoAliasImpl {
+
+  AANoAliasReturned(Function &F, InformationCache &InfoCache)
+      : AANoAliasImpl(F, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_RETURNED;
+  }
+
+  /// See AbstractAttriubute::initialize(...).
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+
+    // Already noalias.
+    if (F.returnDoesNotAlias()) {
+      indicateOptimisticFixpoint();
+      return;
+    }
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+};
+
+ChangeStatus AANoAliasReturned::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  auto *AARetValImpl = A.getAAFor<AAReturnedValuesImpl>(*this, F);
+  if (!AARetValImpl) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+    if (Constant *C = dyn_cast<Constant>(&RV))
+      if (C->isNullValue() || isa<UndefValue>(C))
+        return true;
+
+    /// For now, we can only deduce noalias if we have call sites.
+    /// FIXME: add more support.
+    ImmutableCallSite ICS(&RV);
+    if (!ICS)
+      return false;
+
+    auto *NoAliasAA = A.getAAFor<AANoAlias>(*this, RV);
+
+    if (!ICS.returnDoesNotAlias() && (!NoAliasAA ||
+        !NoAliasAA->isAssumedNoAlias()))
+      return false;
+
+    /// FIXME: We can improve capture check in two ways:
+    /// 1. Use the AANoCapture facilities.
+    /// 2. Use the location of return insts for escape queries.
+    if (PointerMayBeCaptured(&RV, /* ReturnCaptures */ false,
+                             /* StoreCaptures */ true))
+      return false;
+
+
+    return true;
+  };
+
+  if (!AARetValImpl->checkForallReturnedValues(Pred)) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
                                       std::function<bool(CallSite)> &Pred,
                                       bool RequireAllCallSites) {
   // We can try to determine information from
void Attributor::identifyDefaultAbstractAttributes(
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // though it is an argument attribute.
     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
 
+    if (ReturnType->isPointerTy()) {
       // Every function with pointer return type might be marked nonnull.
-    if (ReturnType->isPointerTy() &&
-        (!Whitelist || Whitelist->count(AANonNullReturned::ID)))
+      if (!Whitelist || Whitelist->count(AANonNullReturned::ID))
         registerAA(*new AANonNullReturned(F, InfoCache));
+
+      // Every function with pointer return type might be marked noalias.
+      if (!Whitelist || Whitelist->count(AANoAliasReturned::ID))
+        registerAA(*new AANoAliasReturned(F, InfoCache));
+    }
   }
 
   // Every argument with pointer type might be marked nonnull.
   for (Argument &Arg : F.args()) {
     if (Arg.getType()->isPointerTy())
       registerAA(*new AANonNullArgument(Arg, InfoCache));
   }
 

llvm/trunk/test/Transforms/FunctionAttrs/noalias_returned.ll

+; RUN: opt -S -attributor -attributor-disable=false < %s | FileCheck %s
+
+; TEST 1 - negative.
+
+; void *G;
+; void *foo(){
+;   void *V = malloc(4);
+;   G = V;
+;   return V;
+; }
+
+@G = external global i8*
+
+; CHECK: define i8* @foo()
+define i8* @foo() {
+  %1 = tail call noalias i8* @malloc(i64 4)
+  store i8* %1, i8** @G, align 8
+  ret i8* %1
+}
+
+declare noalias i8* @malloc(i64)
+
+; TEST 2
+; call noalias function in return instruction.
+
+; CHECK: define noalias i8* @return_noalias()
+define i8* @return_noalias(){
+  %1 = tail call noalias i8* @malloc(i64 4)
+  ret i8* %1
+}
+
+declare i8* @alias()
+
+; TEST 3
+; CHECK: define i8* @call_alias()
+; CHECK-NOT: noalias
+define i8* @call_alias(){
+  %1 = tail call i8* @alias()
+  ret i8* %1
+}
+
+; TEST 4
+; void *baz();
+; void *foo(int a);
+;
+; void *bar()  {
+;   foo(0);
+;    return baz();
+; }
+;
+; void *foo(int a)  {
+;   if (a)
+;   bar();
+;   return malloc(4);
+; }
+
+; CHECK: define i8* @bar()
+define i8* @bar() nounwind uwtable {
+  %1 = tail call i8* (...) @baz()
+  ret i8* %1
+}
+
+; CHECK: define noalias i8* @foo1(i32)
+define i8* @foo1(i32) nounwind uwtable {
+  %2 = icmp eq i32 %0, 0
+  br i1 %2, label %5, label %3
+
+3:                                                ; preds = %1
+  %4 = tail call i8* (...) @baz()
+  br label %5
+
+5:                                                ; preds = %1, %3
+  %6 = tail call noalias i8* @malloc(i64 4)
+  ret i8* %6
+}
+
+declare i8* @baz(...) nounwind uwtable
+
+; TEST 5
+
+; Returning global pointer. Should not be noalias.
+; CHECK: define nonnull i8** @getter()
+define i8** @getter() {
+  ret i8** @G
+}
+
+; Returning global pointer. Should not be noalias.
+; CHECK: define nonnull i8** @calle1()
+define i8** @calle1(){
+  %1 = call i8** @getter()
+  ret i8** %1
+}
+
+; TEST 6
+declare noalias i8* @strdup(i8* nocapture) nounwind
+
+; CHECK: define noalias i8* @test6()
+define i8* @test6() nounwind uwtable ssp {
+  %x = alloca [2 x i8], align 1
+  %arrayidx = getelementptr inbounds [2 x i8], [2 x i8]* %x, i64 0, i64 0
+  store i8 97, i8* %arrayidx, align 1
+  %arrayidx1 = getelementptr inbounds [2 x i8], [2 x i8]* %x, i64 0, i64 1
+  store i8 0, i8* %arrayidx1, align 1
+  %call = call noalias i8* @strdup(i8* %arrayidx) nounwind
+  ret i8* %call
+}
+
+; TEST 7
+
+; CHECK: define noalias i8* @test7()
+define i8* @test7() nounwind {
+entry:
+  %A = call noalias i8* @malloc(i64 4) nounwind
+  %tobool = icmp eq i8* %A, null
+  br i1 %tobool, label %return, label %if.end
+
+if.end:
+  store i8 7, i8* %A
+  br label %return
+
+return:
+  %retval.0 = phi i8* [ %A, %if.end ], [ null, %entry ]
+  ret i8* %retval.0
+}
+
+; TEST 8
+
+; CHECK: define noalias i8* @test8(i32*)
+define i8* @test8(i32*) nounwind uwtable {
+  %2 = tail call noalias i8* @malloc(i64 4)
+  %3 = icmp ne i32* %0, null
+  br i1 %3, label %4, label %5
+
+4:                                                ; preds = %1
+  store i8 10, i8* %2
+  br label %5
+
+5:                                                ; preds = %1, %4
+  ret i8* %2
+}

llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll

 define i8* @test2(i8* nonnull %p) {
 ; BOTH: define nonnull i8* @test2
   ret i8* %p
 }
 
 ; Given an SCC where one of the functions can not be marked nonnull,
 ; can we still mark the other one which is trivially nonnull
 define i8* @scc_binder() {
-; BOTH: define i8* @scc_binder
+; FNATTR: define i8* @scc_binder
+; ATTRIBUTOR: define noalias i8* @scc_binder
   call i8* @test3()
   ret i8* null
 }
 
 define i8* @test3() {
 ; BOTH: define nonnull i8* @test3
   call i8* @scc_binder()
   %ret = call i8* @ret_nonnull()
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions, we can mark them
 ; nonnull if neither can ever return null.  (In this case, they
 ; just never return period.)
 define i8* @test4_helper() {
 ; FNATTR: define noalias nonnull i8* @test4_helper
-; ATTRIBUTOR: define nonnull i8* @test4_helper
+; ATTRIBUTOR: define noalias nonnull i8* @test4_helper
   %ret = call i8* @test4()
   ret i8* %ret
 }
 
 define i8* @test4() {
 ; FNATTR: define noalias nonnull i8* @test4
-; ATTRIBUTOR: define nonnull i8* @test4
+; ATTRIBUTOR: define noalias nonnull i8* @test4
   %ret = call i8* @test4_helper()
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions which *can* return null
 ; make sure we haven't marked them as nonnull.
 define i8* @test5_helper() {
 ; FNATTR: define noalias i8* @test5_helper
-; ATTRIBUTOR: define i8* @test5_helper
+; ATTRIBUTOR: define noalias i8* @test5_helper
   %ret = call i8* @test5()
   ret i8* null
 }
 
 define i8* @test5() {
 ; FNATTR: define noalias i8* @test5
-; ATTRIBUTOR: define i8* @test5
+; ATTRIBUTOR: define noalias i8* @test5
   %ret = call i8* @test5_helper()
   ret i8* %ret
 }
 
 ; Local analysis, but going through a self recursive phi
 define i8* @test6() {
 entry:
 ; BOTH: define nonnull i8* @test6