[InlineFunction] don't add noalias metadata for unknown objects

[shchenz]

Summary

The unidentified objects recognized in getUnderlyingObjects may still alias to the noalias parameter because getUnderlyingObjects may not check deep enough to get the underlying object because of MaxLookup. The real underlying object for the unidentified object may still be the noalias parameter.

Don't add noalias metadata for these unidentified objects.

[nikic]

Please add a test case.

[xbolva00]

in AddAliasScopeMetadata: the default value of MaxLookup is not enough to identify the underlying object, and the alias info added by AddAliasScopeMetadata() is wrong, resulting in wrong schedule decisions in machine-scheduler.

AddAliasScopeMetadata is also buggy then..

[tingwang]

Add test case for this particular issue.

[nikic]

llvm/test/Transforms/Inline/inline-noalias.ll

82 ↗

(On Diff #435051)

This test case looks like it can be minimized further. Do we need any of the alias.scope/noalias metadata in the input IR? I think we're only interested in what inlining adds. All the arithmetic instructions are probably unnecessary as well. You can also switch to opaque pointer IR to avoid unnecessary types and bitcasts.

[nikic]

llvm/test/Transforms/Inline/inline-noalias.ll

82 ↗

(On Diff #435051)

Here is a minimized test case that clearly shows the issue: https://llvm.godbolt.org/z/c8EhMddja

[nikic]

Okay, I think the core problem here is that the code assumes that the underlying object may be either a) an argument, b) an identified function local object or c) an escape source -- in the sense of only being able to alias a noalias argument if it has been captured earlier. This assumption does mostly hold up in practice, because the implementations of getUnderlyingObjects() and CaptureTracking are carefully synchronized (see in particular https://github.com/llvm/llvm-project/blob/20ca739701d7b2e2aa4028f1a7853f6d0fa0c412/llvm/lib/Analysis/ValueTracking.cpp#L4446-L4458). Looking through history, I think it might be synchronized for this specific usage actually. Of course, the assumption doesn't hold up if we stop walking underlying objects early, in which case we may alias without the argument being captured.

So this can be fixed in two ways: Avoid the assumption, or avoid stopping the walk early. For the latter case, something to be careful about is that using MaxLookup=0 also removes infinite loop protection for unreachable code. You'll want to add a test case for that. Likely we'd actually want something like D86669 as the implementation, which does avoid infinite loops.

[tingwang]

In D127202#3565819, @nikic wrote:

Okay, I think the core problem here is that the code assumes that the underlying object may be either a) an argument, b) an identified function local object or c) an escape source -- in the sense of only being able to alias a noalias argument if it has been captured earlier. This assumption does mostly hold up in practice, because the implementations of getUnderlyingObjects() and CaptureTracking are carefully synchronized (see in particular https://github.com/llvm/llvm-project/blob/20ca739701d7b2e2aa4028f1a7853f6d0fa0c412/llvm/lib/Analysis/ValueTracking.cpp#L4446-L4458). Looking through history, I think it might be synchronized for this specific usage actually. Of course, the assumption doesn't hold up if we stop walking underlying objects early, in which case we may alias without the argument being captured.

So this can be fixed in two ways: Avoid the assumption, or avoid stopping the walk early. For the latter case, something to be careful about is that using MaxLookup=0 also removes infinite loop protection for unreachable code. You'll want to add a test case for that. Likely we'd actually want something like D86669 as the implementation, which does avoid infinite loops.

Looks like we need some more check on results from getUnderlyingObjects(). @efriedma proposed check like all_of(Objects, isIdentifiedObject), however there are cases for which object is not able to be identified, not due to the MaxLookup limit. I'm thinking maybe we need to know if walk stopped early or not in AddAliasScopeMetadata() to better handle this situation?

[tingwang]

(1) Conditionally detect early exit during getUnderlyingObjects by invoke getUnderlyingObjects a second time. If we got new pointers, then the first walk had trouble, and be conservative in this case.
(2) Updated using nikic's simple test case.

[tingwang]

llvm/test/Transforms/Inline/inline-noalias.ll

82 ↗

(On Diff #435051)

Thank you! This is much simple indeed!

[tingwang]

I have the feeling that by adding this kind of check, I'm creating another hole which could be escaped by some other case, for example if those objects form a loop, and the loop step could be MaxLookup. I need more understand on code to decide if this check can be escaped or not.

[tingwang]

In D127202#3577012, @tingwang wrote:

I have the feeling that by adding this kind of check, I'm creating another hole which could be escaped by some other case, for example if those objects form a loop, and the loop step could be MaxLookup. I need more understand on code to decide if this check can be escaped or not.

I suspect that the test case which will cause infinite loop in getUnderlyingObjects() when MaxLookup = 0 will escape the proposed check, since we could get identical result from the second walk and hence the infinity. Unfortunately I do not have such case right now to observe...

[shchenz]

llvm/test/Transforms/Coroutines/coro-retcon-resume-values.ll

53 ↗

(On Diff #439309)

The change here seems like another bug fix.

Before the patch:

%2 = bitcast i8* %0 to %f.Frame**

%FramePtr.i1 = load %f.Frame*, %f.Frame** %2, align 8, !alias.scope !3

%input.reload.addr13.i = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr.i1, i64 0, i32 2
%input.reload14.i = load i32, i32* %input.reload.addr13.i, align 4, !noalias !3
%n.val3.reload.addr11.i = getelementptr inbounds %f.Frame, %f.Frame* %FramePtr.i1, i64 0, i32 1
%n.val3.reload12.i = load i32, i32* %n.val3.reload.addr11.i, align 4, !noalias !3

store i32 %sum7.i, i32* %n.val3.reload.addr11.i, align 4, !noalias !3
store i32 4, i32* %input.reload.addr13.i, align 4, !noalias !3

%0 is a noalias argument when do inlining. So before the change all the latter loads/stores are not aliased to the noalias argument %0, but seems it is not right. The base for the loads/stores are exactly %0 which is loaded from a pointer of pointer. The pointer of pointer is casted from %0.

getUnderlyingObjects() can not check underlying object inside loads for now.

[shchenz]

Hi @tingwang thanks for great work for addressing the root cause. As discussed offline, I will try to fix this bug based on your analysis.

Dear reviewers, could you please help to have a look at the current solution. Thanks in advance.

[shchenz]

llvm/test/Transforms/Coroutines/coro-retcon-resume-values.ll

53 ↗

(On Diff #439309)

Please ignore this comments. Seems the analysis is wrong. The latter loads/stores are not load/store from base %0.

So we now lose some alias info but have correct functionality.

[nikic]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1107

This looks overly aggressive to me, and probably loses most of the point of the PointerMayBeCapturedBefore check. We should be classifying objects into isIdentifiedObject and isEscapeSource, where we can use the capture-based logic for isEscapeSource. (It's currently static in BasicAliasAnalysis, but can be exported.)

[shchenz]

address @nikic comment

[shchenz]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1107

Thanks. Updated.

[nikic]

I've landed https://github.com/llvm/llvm-project/commit/54eff7da3c6147451b0fd4defb1421db167dc9c6 and https://github.com/llvm/llvm-project/commit/e523baa664b7fc678aa1c0963980a70af161469d while looking into this, so please rebase over these.

llvm/lib/Transforms/Utils/InlineFunction.cpp

1107

I think the basic logic here is now right. I still find the way the flags are set somewhat confusing though, especially that CanDeriveViaCapture is always set, even for non-escape-sources.

I think something like this would make the different cases clearer: https://gist.github.com/nikic/d900c8b2e901fc9c3ab1eb30650af9c3

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

Do you know why these changes happen? (Just wondering, it looks harmless.)

[shchenz]

address @nikic comments

[shchenz]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1107

Haha, thanks very much. I just uploaded your patch shameless. : )

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

The !noalias metadata is added when do inlining:

define i32 @main() local_unnamed_addr {
  %cont1 = call i8* @f.resume.0(i8* nonnull %.sub, i1 zeroext false)
}

define internal i8* @f.resume.0(i8* noalias nocapture nonnull align 4 dereferenceable(8) %0, i1 zeroext %1) {

  %n.val.reload.addr = bitcast i8* %0 to i32*
  %n.val.reload = load i32, i32* %n.val.reload.addr, align 4
  %inc = add i32 %n.val.reload, 1
  store i32 %inc, i32* %n.val.reload.addr, align 4

  tail call void @print(i32 %inc)
}

Before the change, underlying object %inc = add i32 %n.val.reload, 1 for tail call void @print(i32 %inc) parameter is RequiresNoCaptureBefore and PointerMayBeCapturedBefore() returns false, so there will be noalias metadata added for the function call.

But after the change, underlying object %inc = add i32 %n.val.reload, 1 is treated as a UsesUnknownObject.

Can the add (one operand is a load an the other is a constantInt) be handled in the isEscapeSource()?

[nikic]

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

An add should never be an underlying object, because it's not a pointer.

I believe it gets added due to this code: https://github.com/llvm/llvm-project/blob/9081d3d8097af5e89905faf0ed568ba7e848e8df/llvm/lib/Transforms/Utils/InlineFunction.cpp#L1046-L1052 I don't think the comment there is correct, and we should drop the IsArgMemOnlyCall && check. If a pointer is passed as an integer, then the ptrtoint will already capture it. And https://github.com/llvm/llvm-project/blob/9081d3d8097af5e89905faf0ed568ba7e848e8df/llvm/lib/Transforms/Utils/InlineFunction.cpp#L1111-L1114 will always check for captures for non-argmemonly function calls.

[shchenz]

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

Yes, should I posted another patch to fix this issue? I think this fix should not reply on this patch, right? We can just ignore the non-pointer arguments in the PtrArgs collection phase and PointerMayBeCapturedBefore() will always check captures for the parameter even it is not a pointer for a non-argmemonly function calls.

[nikic]

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

Yeah, sounds good.

[shchenz]

llvm/test/Transforms/Coroutines/coro-retcon-opaque-ptr.ll

38 ↗

(On Diff #439668)

Posted D128529. Thanks.

[shchenz]

Gentle ping.

The impact regression cases are all back in D128529 suggested by @nikic

[nikic]

@shchenz Can you please land D128529 first and then rebase this change?

[shchenz]

This comment was removed by shchenz.

[shchenz]

rebase

[nikic]

LGTM, but the patch description could use an update.

[jeroen.dobbelaere]

llvm/test/Transforms/Inline/inline-noalias-unidentify-object.ll

2

You'll need to add the option to check full lines, otherwise the check on line 17 (store i32...) will still match a store containing a noalias

[shchenz]

llvm/test/Transforms/Inline/inline-noalias-unidentify-object.ll

2

92a3e1b5c9e7ddd1b981393eac391a3745eff9a8 is committed to address this comment.

Sorry, I didn't noticed this comment when I committed the patch, seems we are almost at the same time : )

[jeroen.dobbelaere]

llvm/test/Transforms/Inline/inline-noalias-unidentify-object.ll

2

Thx !

llvm/lib/Transforms/Utils/InlineFunction.cpp

if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
         getUnderlyingObjects(V, Objects, /* LI = */ nullptr);
 
         for (const Value *O : Objects)
           ObjSet.insert(O);
       }
 
       // Figure out if we're derived from anything that is not a noalias
       // argument.
-      bool RequiresNoCaptureBefore = false, UsesAliasingPtr = false;
+      bool RequiresNoCaptureBefore = false, UsesAliasingPtr = false,
+           UsesUnknownObject = false;
       for (const Value *V : ObjSet) {
         // Is this value a constant that cannot be derived from any pointer
         // value (we need to exclude constant expressions, for example, that
         // are formed from arithmetic on global symbols).
         bool IsNonPtrConst = isa<ConstantInt>(V) || isa<ConstantFP>(V) ||
                              isa<ConstantPointerNull>(V) ||
                              isa<ConstantDataVector>(V) || isa<UndefValue>(V);
         if (IsNonPtrConst)
           continue;
 
         // If this is anything other than a noalias argument, then we cannot
         // completely describe the aliasing properties using alias.scope
         // metadata (and, thus, won't add any).
         if (const Argument *A = dyn_cast<Argument>(V)) {
           if (!CB.paramHasAttr(A->getArgNo(), Attribute::NoAlias))
             UsesAliasingPtr = true;
         } else {
           UsesAliasingPtr = true;
         }
 
-        // If this is not some identified function-local object (which cannot
-        // directly alias a noalias argument), or some other argument (which,
-        // by definition, also cannot alias a noalias argument), then we could
-        // alias a noalias argument that has been captured).
-        if (!isa<Argument>(V) && !isIdentifiedFunctionLocal(V))
+        if (isEscapeSource(V)) {
+          // An escape source can only alias with a noalias argument if it has
+          // been captured beforehand.
           RequiresNoCaptureBefore = true;
+        } else if (!isa<Argument>(V) && !isIdentifiedObject(V)) {
+          // If this is neither an escape source, nor some identified object
+          // (which cannot directly alias a noalias argument), nor some other
+          // argument (which, by definition, also cannot alias a noalias
+          // argument), conservatively do not make any assumptions.
+          UsesUnknownObject = true;
         }
+      }
+
+      // Nothing we can do if the used underlying object cannot be reliably
+      // determined.
+      if (UsesUnknownObject)
+        continue;
 
       // A function call can always get captured noalias pointers (via other
       // parameters, globals, etc.).
       if (IsFuncCall && !IsArgMemOnlyCall)
         RequiresNoCaptureBefore = true;
 
       // First, we want to figure out all of the sets with which we definitely
       // don't alias. Iterate over all noalias set, and add those for which:

llvm/test/Transforms/Inline/inline-noalias-unidentify-object.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=inline -enable-noalias-to-md-conversion -S | FileCheck %s
 
 define i32 @caller(ptr %p) {
 ; CHECK-LABEL: @caller(
 ; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata [[META0:![0-9]+]])
 ; CHECK-NEXT:    [[P_8_I:%.*]] = getelementptr i8, ptr [[P:%.*]], i64 8
 ; CHECK-NEXT:    [[V_I:%.*]] = load i32, ptr [[P_8_I]], align 4, !alias.scope !0
 ; CHECK-NEXT:    [[P_1_I:%.*]] = getelementptr i8, ptr [[P]], i64 1
 ; CHECK-NEXT:    [[P_2_I:%.*]] = getelementptr i8, ptr [[P_1_I]], i64 1
 ; CHECK-NEXT:    [[P_3_I:%.*]] = getelementptr i8, ptr [[P_2_I]], i64 1
 ; CHECK-NEXT:    [[P_4_I:%.*]] = getelementptr i8, ptr [[P_3_I]], i64 1
 ; CHECK-NEXT:    [[P_5_I:%.*]] = getelementptr i8, ptr [[P_4_I]], i64 1
 ; CHECK-NEXT:    [[P_6_I:%.*]] = getelementptr i8, ptr [[P_5_I]], i64 1
 ; CHECK-NEXT:    [[P_7_I:%.*]] = getelementptr i8, ptr [[P_6_I]], i64 1
 ; CHECK-NEXT:    [[P_8_ALIAS_I:%.*]] = getelementptr i8, ptr [[P_7_I]], i64 1
-; CHECK-NEXT:    store i32 42, ptr [[P_8_ALIAS_I]], align 4, !noalias !0
+; CHECK-NEXT:    store i32 42, ptr [[P_8_ALIAS_I]], align 4
 ; CHECK-NEXT:    ret i32 [[V_I]]
 ;
   %v = call i32 @callee(ptr %p)
   ret i32 %v
 }
 
 define internal i32 @callee(ptr noalias %p) {
   %p.8 = getelementptr i8, ptr %p, i64 8