Use caller information to avoid noalias metadata

[jdoerfert]

Summary

Before introducing noalias metadata after inlining we check if we need
it or if it is already implied in the caller. That is the case if
the parameter is an argument of the caller that has a noalias attribute
and is otherwise not used in the call. For the former we only look
through pointer casts for now, for the latter we assume all instructions
to be potentially influenced by the caller argument in question.

[• dberlin]

It's early in the morning, but I'm having a little trouble understanding the overall goal. Is this fixing a bug, it just being done because it's a waste of time to add the metadata in this situation.

[jdoerfert]

In D31582#716278, @dberlin wrote:

It's early in the morning, but I'm having a little trouble understanding the overall goal. Is this fixing a bug, it just being done because it's a waste of time to add the metadata in this situation.

The latter. There is no correctness bug, just to much metadata in certain situations. The initial idea was to improve the situation of the XLA folks that have to limit the amount of alias information they generate due to the compile time impact.
While David informed me this might not help their case at all, it should avoid the generation of metadata in some cases and could be extended to handle more.

At the end of the day this is just an idea I wanted to try out and see if folks like it and if it is worth pursuing.

[• dberlin]

Gotcha.
Seems reasonable if it's not helpful, and it's cheap to avoid it.

lib/Transforms/Utils/InlineFunction.cpp

 static void AddAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap,
                                   const DataLayout &DL, AAResults *CalleeAAR) {
   if (!EnableNoAliasConversion)
     return;
 
   const Function *CalledFunc = CS.getCalledFunction();
   SmallVector<const Argument *, 4> NoAliasArgs;
 
-  for (const Argument &Arg : CalledFunc->args())
-    if (Arg.hasNoAliasAttr() && !Arg.use_empty())
-      NoAliasArgs.push_back(&Arg);
+  for (const Argument &Arg : CalledFunc->args()) {
+    if (!Arg.hasNoAliasAttr() || Arg.use_empty())
+      continue;
+
+    // Check if we need no alias metadata (or any other annotation) for this
+    // argument or if it is already implied in the caller. That is the case if
+    // the parameter is an argument of the caller that has a noalias attribute
+    // and is otherwise not used in the call. For the former we only look
+    // through pointer casts for now, for the latter we assume all instructions
+    // to be potentially influenced by the caller argument in question.
+
+    // TODO: We could strip of even GEPs here.
+    Value *Parameter = CS.getArgument(Arg.getArgNo())->stripPointerCasts();
+
+    // Check the first property, the parameter is an argument of the caller with
+    // a noalias attribute.
+    Argument *CallSiteArg = dyn_cast<Argument>(Parameter);
+    if (!CallSiteArg || !CallSiteArg->hasNoAliasAttr()) {
+      NoAliasArgs.push_back(&Arg);
+      continue;
+    }
+
+    // Helper function to determine if an argument might be derived from the
+    // CallSiteArg define above.
+    auto IsNotDerivedFrom = [&](const Argument &OtherArg) {
+      if (&Arg == &OtherArg)
+        return true;
+
+      // TODO: We could strip of even GEPs here.
+      Value *Parameter =
+          CS.getArgument(OtherArg.getArgNo())->stripPointerCasts();
+
+      // This is only a conservative approximation.
+      return !isa<Instruction>(Parameter);
+    };
+
+    // If not other argument is dervied from CallSiteArg the noalias annotation
+    // on CallSiteArg suffice.
+    if (std::all_of(CalledFunc->arg_begin(), CalledFunc->arg_end(),
+                    IsNotDerivedFrom))
+      continue;
+
+  }
 
   if (NoAliasArgs.empty())
     return;
 
   // To do a good job, if a noalias variable is captured, we need to know if
   // the capture point dominates the particular use we're considering.
   DominatorTree DT;
   DT.recalculate(const_cast<Function&>(*CalledFunc));

test/Transforms/Inline/noalias2.ll

entry:
   %0 = load float, float* %c, align 4
   %arrayidx = getelementptr inbounds float, float* %a, i64 7
   store float %0, float* %arrayidx, align 4
   ret void
 }
 
 ; CHECK: define void @foo(float* noalias nocapture %a, float* noalias nocapture readonly %c) #0 {
 ; CHECK: entry:
-; CHECK:   %0 = load float, float* %c, align 4, !alias.scope !0, !noalias !3
+; CHECK:   %0 = load float, float* %c, align 4
 ; CHECK:   %arrayidx.i = getelementptr inbounds float, float* %a, i64 5
-; CHECK:   store float %0, float* %arrayidx.i, align 4, !alias.scope !3, !noalias !0
+; CHECK:   store float %0, float* %arrayidx.i, align 4
 ; CHECK:   %1 = load float, float* %c, align 4
 ; CHECK:   %arrayidx = getelementptr inbounds float, float* %a, i64 7
 ; CHECK:   store float %1, float* %arrayidx, align 4
 ; CHECK:   ret void
 ; CHECK: }
 
 define void @hello2(float* noalias nocapture %a, float* noalias nocapture %b, float* nocapture readonly %c) #0 {
 entry:
entry:
   %0 = load float, float* %c, align 4
   %arrayidx = getelementptr inbounds float, float* %a, i64 7
   store float %0, float* %arrayidx, align 4
   ret void
 }
 
 ; CHECK: define void @foo2(float* nocapture %a, float* nocapture %b, float* nocapture readonly %c) #0 {
 ; CHECK: entry:
-; CHECK:   %0 = load float, float* %c, align 4, !alias.scope !5, !noalias !10
+; CHECK:   %0 = load float, float* %c, align 4, !alias.scope ![[NA1:[0-9]*]], !noalias ![[NA0:[0-9]*]]
 ; CHECK:   %arrayidx.i.i = getelementptr inbounds float, float* %a, i64 5
-; CHECK:   store float %0, float* %arrayidx.i.i, align 4, !alias.scope !10, !noalias !5
-; CHECK:   %1 = load float, float* %c, align 4, !alias.scope !13, !noalias !14
+; CHECK:   store float %0, float* %arrayidx.i.i, align 4, !alias.scope ![[NA0]], !noalias ![[NA1]]
+; CHECK:   %1 = load float, float* %c, align 4, !alias.scope ![[NA3:[0-9]*]], !noalias ![[NA2:[0-9]*]]
 ; CHECK:   %arrayidx.i = getelementptr inbounds float, float* %a, i64 7
-; CHECK:   store float %1, float* %arrayidx.i, align 4, !alias.scope !14, !noalias !13
-; CHECK:   %2 = load float, float* %c, align 4, !noalias !15
+; CHECK:   store float %1, float* %arrayidx.i, align 4, !alias.scope ![[NA2]], !noalias ![[NA3]]
+; CHECK:   %2 = load float, float* %c, align 4, !noalias ![[NA4:[0-9]*]]
 ; CHECK:   %arrayidx.i1 = getelementptr inbounds float, float* %a, i64 6
-; CHECK:   store float %2, float* %arrayidx.i1, align 4, !alias.scope !19, !noalias !20
+; CHECK:   store float %2, float* %arrayidx.i1, align 4, !alias.scope ![[NA6:[0-9]*]], !noalias ![[NA5:[0-9]*]]
 ; CHECK:   %arrayidx1.i = getelementptr inbounds float, float* %b, i64 8
-; CHECK:   store float %2, float* %arrayidx1.i, align 4, !alias.scope !20, !noalias !19
+; CHECK:   store float %2, float* %arrayidx1.i, align 4, !alias.scope ![[NA5]], !noalias ![[NA6]]
 ; CHECK:   %3 = load float, float* %c, align 4
 ; CHECK:   %arrayidx = getelementptr inbounds float, float* %a, i64 7
 ; CHECK:   store float %3, float* %arrayidx, align 4
 ; CHECK:   ret void
 ; CHECK: }
 
-; CHECK: !0 = !{!1}
-; CHECK: !1 = distinct !{!1, !2, !"hello: %c"}
-; CHECK: !2 = distinct !{!2, !"hello"}
-; CHECK: !3 = !{!4}
-; CHECK: !4 = distinct !{!4, !2, !"hello: %a"}
-; CHECK: !5 = !{!6, !8}
-; CHECK: !6 = distinct !{!6, !7, !"hello: %c"}
-; CHECK: !7 = distinct !{!7, !"hello"}
-; CHECK: !8 = distinct !{!8, !9, !"foo: %c"}
-; CHECK: !9 = distinct !{!9, !"foo"}
-; CHECK: !10 = !{!11, !12}
-; CHECK: !11 = distinct !{!11, !7, !"hello: %a"}
-; CHECK: !12 = distinct !{!12, !9, !"foo: %a"}
-; CHECK: !13 = !{!8}
-; CHECK: !14 = !{!12}
-; CHECK: !15 = !{!16, !18}
-; CHECK: !16 = distinct !{!16, !17, !"hello2: %a"}
-; CHECK: !17 = distinct !{!17, !"hello2"}
-; CHECK: !18 = distinct !{!18, !17, !"hello2: %b"}
-; CHECK: !19 = !{!16}
-; CHECK: !20 = !{!18}
+; CHECK-DAG: ![[NA1]] = !{![[FooC:[0-9]*]]}
+; CHECK-DAG: ![[FooC:[0-9]*]] = distinct !{![[FooC]], ![[Foo:[0-9]*]], !"foo: %c"}
+; CHECK-DAG: ![[Foo]] = distinct !{![[Foo]], !"foo"}
+; CHECK-DAG: ![[NA0]] = !{![[FooA:[0-9]*]]}
+; CHECK-DAG: ![[FooA]] = distinct !{![[FooA]], ![[Foo]], !"foo: %a"}
+; CHECK-DAG: ![[NA4]] = !{![[Hello2A:[0-9]*]], ![[Hello2B:[0-9]*]]}
+; CHECK-DAG: ![[Hello2A]] = distinct !{![[Hello2A]], ![[Hello2:[0-9]*]], !"hello2: %a"}
+; CHECK-DAG: ![[Hello2]] = distinct !{![[Hello2]], !"hello2"}
+; CHECK-DAG: ![[Hello2B]] = distinct !{![[Hello2B]], ![[Hello2]], !"hello2: %b"}
+; CHECK-DAG: ![[NA6]] = !{![[Hello2A]]}
+; CHECK-DAG: ![[FooC]]0 = !{![[Hello2B]]}
 
 attributes #0 = { nounwind uwtable }
 

test/Transforms/Inline/noalias3.ll

+; RUN: opt -inline -S < %s | FileCheck %s
+;
+; // Function that will be inlined in bar and baz.
+; static void foo(float *restrict a, float *restrict b, float *c) {
+;   *a = *b + *c;
+;   *b = *a + *c;
+;   *c = *a + *b;
+; }
+;
+; // "a" and "b" are restricted in the caller so no need for metadata.
+; void bar(float *restrict a, double *restrict b, float *c, int i) {
+;   float *bcast = (float *)b;
+;   *a = *bcast + *c;
+;   foo(a, bcast, c);
+;   *a = *bcast + *c;
+; }
+;
+; // Only "a" is restricted in the caller so we need metadata for "b".
+; void baz(float *restrict a, float *b, float * restrict c) {
+;   *a = *b + *c;
+;   foo(a, b, c);
+;   *a = *b + *c;
+; }
+
+; CHECK: define void @bar
+; CHECK-NOT: alias.scope
+;
+; CHECK: define void @baz
+; CHECK-NOT: float* %a, align 4, !alias.scope
+; CHECK: float* %b, align 4, !alias.scope
+
+; Function Attrs: nounwind uwtable
+define internal void @foo(float* noalias %a, float* noalias %b, float* %c) #0 {
+entry:
+  %tmp = load float, float* %b, align 4
+  %tmp1 = load float, float* %c, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  %add1 = fadd float %add, %tmp1
+  store float %add1, float* %b, align 4
+  %add2 = fadd float %add, %add1
+  store float %add2, float* %c, align 4
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define void @bar(float* noalias %a, double* noalias %b, float* %c, i32 %i) #0 {
+entry:
+  %cast = bitcast double* %b to float *
+  %tmp = load float, float* %cast, align 4
+  %tmp1 = load float, float* %c, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  %idxprom = sext i32 %i to i64
+  call void @foo(float* %a, float* %cast, float* %c)
+  %tmp2 = load float, float* %cast, align 4
+  %tmp3 = load float, float* %c, align 4
+  %add1 = fadd float %tmp2, %tmp3
+  store float %add1, float* %a, align 4
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define void @baz(float* noalias %a, float* %b, float* noalias %c) #0 {
+entry:
+  %tmp = load float, float* %b, align 4
+  %tmp1 = load float, float* %c, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  call void @foo(float* %a, float* %b, float* %c)
+  %tmp2 = load float, float* %b, align 4
+  %tmp3 = load float, float* %c, align 4
+  %add1 = fadd float %tmp2, %tmp3
+  store float %add1, float* %a, align 4
+  ret void
+}
+
+attributes #0 = { nounwind uwtable }

test/Transforms/Inline/noalias4.ll

+; RUN: opt -inline -S < %s | FileCheck %s
+
+; Verify we emit the noalias scope metadata after inlining of foo as the
+; information in the callers does not suffice.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define internal void @foo(float* noalias %a, float* noalias %b, float* %c) #0 {
+entry:
+  %tmp = load float, float* %b, align 4
+  %tmp1 = load float, float* %c, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  %add1 = fadd float %add, %tmp1
+  store float %add1, float* %b, align 4
+  %add2 = fadd float %add, %add1
+  store float %add2, float* %c, align 4
+  ret void
+}
+
+; Function Attrs: nounwind uwtable
+define void @bar(float* noalias %a, float* noalias %b, float* %c, i32 %i) #0 {
+entry:
+  %tmp = load float, float* %b, align 4
+  %tmp1 = load float, float* %c, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  %idxprom = sext i32 %i to i64
+  %arrayidx = getelementptr inbounds float, float* %a, i64 %idxprom
+  call void @foo(float* %a, float* %arrayidx, float* %c)
+  %tmp2 = load float, float* %b, align 4
+  %tmp3 = load float, float* %c, align 4
+  %add1 = fadd float %tmp2, %tmp3
+  store float %add1, float* %a, align 4
+  ret void
+}
+; CHECK: @bar
+; CHECK:  %tmp.i = load float, float* %arrayidx, align 4, !alias.scope !0, !noalias !3
+; CHECK:  %tmp1.i = load float, float* %c, align 4, !noalias !5
+; CHECK:  store float %add.i, float* %a, align 4, !alias.scope !3, !noalias !0
+; CHECK:  store float %add1.i, float* %arrayidx, align 4, !alias.scope !0, !noalias !3
+; CHECK:  store float %add2.i, float* %c, align 4, !noalias !5
+
+; Function Attrs: nounwind uwtable
+define void @baz(float* noalias %a, float* noalias %b) #0 {
+entry:
+  %call = call float* @func(float* %a, float* %b) #1
+  %tmp = load float, float* %b, align 4
+  %tmp1 = load float, float* %call, align 4
+  %add = fadd float %tmp, %tmp1
+  store float %add, float* %a, align 4
+  call void @foo(float* %a, float* %b, float* %call)
+  %tmp2 = load float, float* %b, align 4
+  %tmp3 = load float, float* %call, align 4
+  %add1 = fadd float %tmp2, %tmp3
+  store float %add1, float* %a, align 4
+  ret void
+}
+
+; CHECK: @baz
+; CHECK:  %tmp.i = load float, float* %b, align 4, !alias.scope !6, !noalias !9
+; CHECK:  %tmp1.i = load float, float* %call, align 4, !noalias !11
+; CHECK:  store float %add.i, float* %a, align 4, !alias.scope !9, !noalias !6
+; CHECK:  store float %add1.i, float* %b, align 4, !alias.scope !6, !noalias !9
+; CHECK:  store float %add2.i, float* %call, align 4, !noalias !11
+
+declare float* @func(float*, float*)
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }