[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–1677

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

1733

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

1737

make it isAssumedNoCaptureMaybeReturned.

2647

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

2917

Again, why is this needed?

[uenoku]

Remove nocapture related change

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

2647

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)

2917

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

 };
 
 /// 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.
+    AANoAliasImpl::initialize(A);
+    if (isa<AllocaInst>(getAnchorValue()))
+      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.
+    // We can deduce "noalias" if the following conditions hold.
+    // (i)   Associated value is assumed to be noalias in the definition.
+    // (ii)  Associated value is assumed to be no-capture in all the uses
+    //       possibly executed before this callsite.
+    // (iii) There is no other pointer argument which could alias with the
+    //       value.
+
+    const Value &V = getAssociatedValue();
+    const IRPosition IRP = IRPosition::value(V);
+
+    // (i) Check whether noalias holds in the definition.
+
+    auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, IRP);
+
+    if (!NoAliasAA.isAssumedNoAlias())
+      return indicatePessimisticFixpoint();
+
+    LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] " << V
+                      << " is assumed NoAlias in the definition\n");
+
+    // (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.isAssumedNoCaptureMaybeReturned())
       return indicatePessimisticFixpoint();
+
+    // (iii) Check there is no other pointer argument which could alias with the
+    // value.
+    ImmutableCallSite ICS(&getAnchorValue());
+    for (unsigned i = 0; i < ICS.getNumArgOperands(); i++) {
+      if (getArgNo() == (int)i)
+        continue;
+      const Value *ArgOp = ICS.getArgOperand(i);
+      if (!ArgOp->getType()->isPointerTy())
+        continue;
+
+      // TODO: Use AliasAnalysis
+      //       AAResults& AAR = ..;
+      //       if(AAR.isNoAlias(&getAssociatedValue(), ArgOp))
+      //          return indicatePessimitisicFixpoint();
+
+      return 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 {
getDeducedAttributes(LLVMContext &Ctx,
                        SmallVectorImpl<Attribute> &Attrs) const override {
     if (!isAssumedNoCaptureMaybeReturned())
       return;
 
     if (isAssumedNoCapture())
       Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture));
     else if (ManifestInternal)
       Attrs.emplace_back(Attribute::get(Ctx, "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.
 

 /// NoCapture attribute for floating values.
 struct AANoCaptureFloating final : AANoCaptureImpl {
   AANoCaptureFloating(const IRPosition &IRP) : AANoCaptureImpl(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FLOATING_ATTR(nocapture)
   }
 };
 
 /// NoCapture attribute for function return value.
 struct AANoCaptureReturned final : AANoCaptureImpl {
   AANoCaptureReturned(const IRPosition &IRP) : AANoCaptureImpl(IRP) {
     llvm_unreachable("NoCapture is not applicable to function returns!");
   }
 
   /// See AbstractAttribute::initialize(...).

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

 
 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 i8* @malloc(i64 4)
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nonnull align 4 dereferenceable(1) [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias nonnull align 4 dereferenceable(1) [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias [[B]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* noalias [[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 [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* [[A]])
+; FIXME: This should be @use_nocapture(i8* noalias [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* [[A]])
+; CHECK-NEXT:    tail call void @use(i8* [[A]])
+; CHECK-NEXT:    tail call void @use_nocapture(i8* [[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
+}
+
+declare void @two_args(i8* nocapture , i8* nocapture)
+define void @test12_3(){
+; CHECK-LABEL: @test12_3(
+  %A = tail call noalias i8* @malloc(i64 4)
+; CHECK: tail call void @two_args(i8* %A, i8* %A)
+  tail call void @two_args(i8* %A, i8* %A)
+  ret void
+}
+
+define void @test12_4(){
+; CHECK-LABEL: @test12_4(
+  %A = tail call noalias i8* @malloc(i64 4)
+  %B = tail call noalias i8* @malloc(i64 4)
+  %A_0 = getelementptr i8, i8* %A, i64 0
+  %A_1 = getelementptr i8, i8* %A, i64 1
+  %B_0 = getelementptr i8, i8* %B, i64 0
+
+; FIXME: This should be @two_args(i8* noalias %A, i8* noalias %B)
+; CHECK: tail call void @two_args(i8* %A, i8* %B)
+  tail call void @two_args(i8* %A, i8* %B)
+
+; CHECK: tail call void @two_args(i8* %A, i8* %A_0)
+  tail call void @two_args(i8* %A, i8* %A_0)
+
+; CHECK: tail call void @two_args(i8* %A, i8* %A_1)
+  tail call void @two_args(i8* %A, i8* %A_1)
+
+; FIXME: This should be @two_args(i8* noalias %A_0, i8* noalias %B_0)
+; CHECK: tail call void @two_args(i8* %A_0, i8* %B_0)
+  tail call void @two_args(i8* %A_0, i8* %B_0)
+  ret void
+}