[Attributor] Implement "noalias" callsite argument deduction

[uenoku]

Summary

Now, nocapture is deduced in Attributor therefore, this patch introduces deduction for noalias callsite argument using nocapture.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1675

Once I thought it is not sound to do this initialization but, I reconsider that unless we don't manifest the information for floating value, there is no problem.

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

235

We need to make sure this test works as well:

define void @test12_3(){
  %A = tail call noalias i8* @malloc(i64 4)
  tail call void @two_args(i8* %A, i8* %A)
  ret void
}

[uenoku]

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

235

If @two_args is:

declare void @two_args(i8* nocapture , i8* nocapture)

then

define void @test12_3(){
  %A = tail call noalias i8* @malloc(i64 4)
  tail call void @two_args(i8* noalias nocapture %A, i8* noalias nocapture%A)
  ret void
}

(If either argument is not marked as nocapture, there is no problem.)
It is not good ... I'll fix. We need to compare the call site argument and ensure that there is no copy.

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

235

We need to compare the call site argument and ensure that there is no copy.

Exactly. They need to be checked for aliases wrt. other arguments.

[uenoku]

Add test

[jdoerfert]

Except the nocapture changes this looks good to me. Can we make sure these are needed before we commit this?

llvm/lib/Transforms/IPO/Attributor.cpp

1732

AANoCapture will get a "isCapturedBefore" functionality at some point to solve this.

1736

make it isAssumedNoCaptureMaybeReturned.

2624

I do not understand these changes. Why do they help? Can we extract them into a different commit?

2894

Again, why is this needed?

[uenoku]

Remove nocapture related change

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

2624

I used an internal attribute to look at deduction but anyway I don't need anymore.
However, I think we need to check whether the value is an argument or not. (D67342)

2894

I encountered a runtime exception in test/Transform/FunctionAttrs/misc.ll. Once I added this check as a solution but now I find that it works well without the check.

[jdoerfert]

LGTM.

llvm/lib/Transforms/IPO/Attributor.cpp

do {
 
     // Look through phi nodes, visit all live operands.
     if (auto *PHI = dyn_cast<PHINode>(V)) {
       assert(LivenessAA &&
              "Expected liveness in the presence of instructions!");
       for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
         const BasicBlock *IncomingBB = PHI->getIncomingBlock(u);
         if (LivenessAA->isAssumedDead(IncomingBB->getTerminator())) {
-          AnyDead =true;
+          AnyDead = true;
           continue;
         }
         Worklist.push_back(PHI->getIncomingValue(u));
       }
       continue;
     }
 
     // Once a leaf is reached we inform the user through the callback.

 };
 
 /// NoAlias attribute for a floating value.
 struct AANoAliasFloating final : AANoAliasImpl {
   AANoAliasFloating(const IRPosition &IRP) : AANoAliasImpl(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    // TODO: It isn't sound to initialize as the same with `AANoAliasImpl`
-    // because `noalias` may not be valid in the current position.
+    if (hasAttr({Attribute::NoAlias}) || isa<AllocaInst>(getAssociatedValue()))
+      indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     // TODO: Implement this.
     return indicatePessimisticFixpoint();
   }
 
void initialize(Attributor &A) override {
     // See callsite argument attribute and callee argument attribute.
     ImmutableCallSite ICS(&getAnchorValue());
     if (ICS.paramHasAttr(getArgNo(), Attribute::NoAlias))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    // TODO: Implement this.
-    return indicatePessimisticFixpoint();
+    // We can deduce "noalias" if the following conditions hold.
+    // (i) Associated value is assumed to be noalias in the definition.
+    // (ii) Associated value are assumed to be no-capture in all the uses
+    // possibly executed before this callsite.
+
+    const IRPosition IRP = IRPosition::value(getAssociatedValue());
+
+    // (i) Check whether noalias holds in the definition.
+
+    auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, IRP);
+
+    if (!NoAliasAA.isAssumedNoAlias())
+      indicatePessimisticFixpoint();
+
+    // (ii) Check whether the value is captured in the scope using AANoCapture.
+    //      FIXME: This is conservative though, it is better to look at CFG and
+    //             check only uses possibly executed before this callsite.
+
+    auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP);
+    if (!NoCaptureAA.isAssumedNoCapture())
+      indicatePessimisticFixpoint();
+
+    return ChangeStatus::UNCHANGED;
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) }
 };
 
 /// NoAlias attribute for function return value.
 struct AANoAliasReturned final : AANoAliasImpl {
struct AANoCaptureImpl : public AANoCapture {
 
   /// see AbstractAttribute::isAssumedNoCaptureMaybeReturned(...).
   virtual void
   getDeducedAttributes(LLVMContext &Ctx,
                        SmallVectorImpl<Attribute> &Attrs) const override {
     if (!isAssumedNoCaptureMaybeReturned())
       return;
 
-    if (isAssumedNoCapture())
+    if (isAssumedNoCapture() && getArgNo() >= 0)
       Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture));
     else if (ManifestInternal)
-      Attrs.emplace_back(Attribute::get(Ctx, "no-capture-maybe-returned"));
+      Attrs.emplace_back(Attribute::get(
+          Ctx, isAssumedNoCapture() ? "no-capture-in-the-scope"
+                                    : "no-capture-maybe-returned"));
   }
 
   /// Set the NOT_CAPTURED_IN_MEM and NOT_CAPTURED_IN_RET bits in \p Known
   /// depending on the ability of the function associated with \p IRP to capture
   /// state in memory and through "returning/throwing", respectively.
   static void determineFunctionCaptureCapabilities(const Function &F,
                                                    IntegerState &State) {
     // TODO: Once we have memory behavior attributes we should use them here.
 
struct AANoCaptureCallSiteArgument final : AANoCaptureImpl {
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nocapture)};
 };
 
 /// NoCapture attribute for floating values.
 struct AANoCaptureFloating final : AANoCaptureImpl {
   AANoCaptureFloating(const IRPosition &IRP) : AANoCaptureImpl(IRP) {}
 
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    if (!isa<Instruction>(getAnchorValue()))
+      indicatePessimisticFixpoint();
+  }
+
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FLOATING_ATTR(nocapture)
   }
 };
 
 /// NoCapture attribute for function return value.
 struct AANoCaptureReturned final : AANoCaptureImpl {

llvm/test/Transforms/FunctionAttrs/internal-noalias.ll

-; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 < %s | FileCheck %s
+; RUN: opt -S -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 < %s | FileCheck %s
 
 define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
 entry:
   %call1 = call i32 @noalias_args(i32* %A, i32* %B)
   %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add = add nsw i32 %call1, %call2
   ret i32 %add
 }
 
 ; FIXME: Should be something like this.
 ; define internal i32 @noalias_args(i32* nocapture readonly %A, i32* noalias nocapture readonly %B)
-; CHECK: define internal i32 @noalias_args(i32* nocapture %A, i32* nocapture %B)
+; CHECK: define internal i32 @noalias_args(i32* nocapture %A, i32* noalias nocapture %B)
 
 define internal i32 @noalias_args(i32* %A, i32* %B) #0 {
 entry:
   %0 = load i32, i32* %A, align 4
   %1 = load i32, i32* %B, align 4
   %add = add nsw i32 %0, %1
   %call = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add2 = add nsw i32 %add, %call
   ret i32 %add2
 }
 
 
 ; FIXME: Should be something like this.
 ; define internal i32 @noalias_args_argmem(i32* noalias nocapture readonly %A, i32* noalias nocapture readonly %B)
-; CHECK: define internal i32 @noalias_args_argmem(i32* nocapture %A, i32* nocapture %B)
+; CHECK: define internal i32 @noalias_args_argmem(i32* nocapture %A, i32* noalias nocapture %B)
 ;
 define internal i32 @noalias_args_argmem(i32* %A, i32* %B) #1 {
 entry:
   %0 = load i32, i32* %A, align 4
   %1 = load i32, i32* %B, align 4
   %add = add nsw i32 %0, %1
   ret i32 %add
 }

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

-; RUN: opt -S -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=5 < %s | FileCheck %s
+; RUN: opt -S -attributor -attributor-disable=false -attributor-manifest-internal -attributor-max-iterations-verify -attributor-max-iterations=5 < %s | FileCheck %s
 
 ; TEST 1 - negative.
 
 ; void *G;
 ; void *foo(){
 ;   void *V = malloc(4);
 ;   G = V;
 ;   return V;

 
 declare void @test11_helper(i8* %a, i8 *%b)
 define void @test11(i8* noalias %a) {
 ; CHECK: define void @test11(i8* noalias %a)
 ; CHECK-NEXT:   tail call void @test11_helper(i8* %a, i8* %a)
   tail call void @test11_helper(i8* %a, i8* %a)
   ret void
 }
+
+; TEST 12
+; CallSite Argument
+declare void @use_nocapture(i8* nocapture)
+declare void @use(i8*)
+define void @test12_1() {
+; CHECK-LABEL: @test12_1(
+; CHECK-NEXT:    [[A:%.*]] = alloca i8, align 4
+; CHECK-NEXT:    [[B:%.*]] = tail call noalias "no-capture-in-the-scope" i8* @malloc(i64 4)
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nocapture nonnull align 4 dereferenceable(1) [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nocapture nonnull align 4 dereferenceable(1) [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nocapture [[B]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nocapture [[B]])
+; CHECK-NEXT:    ret void
+;
+  %A = alloca i8, align 4
+  %B = tail call noalias i8* @malloc(i64 4)
+  tail call void @use_nocapture(i8* %A)
+  tail call void @use_nocapture(i8* %A)
+  tail call void @use_nocapture(i8* %B)
+  tail call void @use_nocapture(i8* %B)
+  ret void
+}
+
+define void @test12_2(){
+; CHECK-LABEL: @test12_2(
+; CHECK-NEXT:    [[A:%.*]] = tail call noalias i8* @malloc(i64 4)
+; FIXME: This should be @use_nocapture(i8* noalias nocapture [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* nocapture [[A]])
+; FIXME: This should be @use_nocapture(i8* noalias nocapture [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* nocapture [[A]])
+; CHECK-NEXT:    tail call void @use(i8* [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* nocapture [[A]])
+; CHECK-NEXT:    ret void
+;
+  %A = tail call noalias i8* @malloc(i64 4)
+  tail call void @use_nocapture(i8* %A)
+  tail call void @use_nocapture(i8* %A)
+  tail call void @use(i8* %A)
+  tail call void @use_nocapture(i8* %A)
+  ret void
+}