thr3ads.net - llvm dev - [llvm-dev] inttoptr and noalias returns [Apr 2021]

If this information is useful, please help other people find it:
Share via:

Joseph Tremoulet via llvm-dev

2021-Mar-31 18:08 UTC

[llvm-dev] inttoptr and noalias returns

Hi,

I'm a bit confused about the interaction between inttoptr and noalias, and
would like to better understand our model.

I realize there's a bunch of in-flight work around restrict modeling and
that ptrtoint was on the agenda for last week's AA call.  I'm interested
in understanding both the current state and the thinking/plans for the future. 
And I'm happy for pointers to anywhere this is already written down, I
didn't find it from skimming the AA call minutes or the mailing list
archive, but I could easily have overlooked it, and haven't really dug into
the set of restrict patches (nor do I know where to get a list of those).

I also realize that with aliasing questions there can always be a gap between
what the model says we can infer and how aggressive analyses and optimizations
are about actually making use of those inferences.  Again I'm interested in
both answers (and happy for either).

In the LangRef section on pointer aliasing rules [1], I see

An integer constant other than zero or a pointer value returned from a function
not defined within LLVM may be associated with address ranges allocated through
mechanisms other than those provided by LLVM. Such ranges shall not overlap with
any ranges of addresses allocated by mechanisms provided by LLVM.

And I'm curious what "mechanisms provided by LLVM" for allocation
means.  Alloca, presumably.  Global variables?  Certain intrinsics?  Any
function with a noalias return value?

In the LangRef description of the noalias attribute [2], I see

This indicates that memory locations accessed via pointer values based on the
argument or return value are not also accessed, during the execution of the
function, via pointer values not based on the argument or return value ...  On
function return values, the noalias attribute indicates that the function acts
like a system memory allocation function, returning a pointer to allocated
storage disjoint from the storage for any other object accessible to the caller.

The phrase "the storage for any other object accessible to the caller"
in the noalias description sounds like a broader category than the phrase
"mechanisms provided by LLVM" from the pointer aliasing section, so I
would expect that if the pointer returned from a call to a function with return
attribute noalias does not escape, then loads/stores through it would not alias
loads/stores through a pointer produced by inttoptr.  Am I interpreting that
correctly?

I wrote some snippets [3] to see what the optimizer would do.  Each case has a
store of value 86 via pointer %p that I'd expect dead store elimination to
remove if we think it does not alias the subsequent load via pointer %q (because
immediately after that is another store to %p).
In each case, %q is the result of a call to a function whose return value is
annotated noalias.

When %p is a pointer parameter, I indeed see the optimizer removing the dead
store:
define i8 @test1(i8* %p) {

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this gets removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}

When %p is the result of inttoptr, I do not see the store being removed, and
I'm wondering if this is because of a subtle aliasing rule or an intentional
conservativism in the optimizer or just a blind spot in the analysis:
define i8 @test2(i64 %p_as_int) {
    %p = inttoptr i64 %p_as_int to i8*

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this does not get removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}

When I outline the inttoptr into a separate function, I again see the optimizer
remove the dead store, which again I'm wondering if the difference between
this and the previous case is an intentional subtle point or what.
define i8* @launder(i64 %int) noinline {
  %ptr = inttoptr i64 %int to i8*
  ret i8* %ptr
}

define i8 @test3(i64 %p_as_int) {
    %p = call i8* @launder(i64 %p_as_int)

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this gets removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}



Happy for any insights you can share.

Thanks,
-Joseph

1 - https://llvm.org/docs/LangRef.html#pointeraliasing
2 - https://llvm.org/docs/LangRef.html#parameter-attributes
3 - https://godbolt.org/z/x8e41G33Y


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210331/235f7e64/attachment.html>

Joseph Tremoulet via llvm-dev

2021-Apr-02 18:25 UTC

head link

[llvm-dev] inttoptr and noalias returns

Stepping through this in the debugger, I see this code in BasicAliasAnalysis
doing a check similar to the sort that I would have expected to see proving
NoAlias for this case, but it's not because (ISTM) it's being pretty
conservative:

    // If one pointer is the result of a call/invoke or load and the other is a
    // non-escaping local object within the same function, then we know the
    // object couldn't escape to a point where the call could return it.
    //
    // Note that if the pointers are in different functions, there are a
    // variety of complications. A call with a nocapture argument may still
    // temporary store the nocapture argument's value in a temporary memory
    // location if that memory location doesn't escape. Or it may pass a
    // nocapture value to other functions as long as they don't capture it.
    if (isEscapeSource(O1) &&
        isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache))
      return NoAlias;
    if (isEscapeSource(O2) &&
        isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache))
      return NoAlias;
  }

and

/// Returns true if the pointer is one which would have been considered an
/// escape by isNonEscapingLocalObject.
static bool isEscapeSource(const Value *V) {
  if (isa<CallBase>(V))
    return true;

  if (isa<Argument>(V))
    return true;

  // The load case works because isNonEscapingLocalObject considers all
  // stores to be escapes (it passes true for the StoreCaptures argument
  // to PointerMayBeCaptured).
  if (isa<LoadInst>(V))
    return true;

  return false;
}

Since we have to look through all the uses of O1/O2 (including certain
transitive ones) to prove isNonEscapingLocalObject, an
expensive-but-more-precise analysis could just check if O2/O1 is in that set,
IIUC.  I get why BasicAliasAnalysis isn't the right place to do that.  Is
there some more expensive alias analysis that I could opt into and get that sort
of check?

Alternatively, following the logic that we can assume isEscapeSource for loads
because we treat stores as escapes, is there room to assume isEscapeSource for
inttoptrs because we treat ptrtoints, and things that let you subtly intify
pointers such as certain compares, as escapes?

Thanks,
-Joseph


From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Joseph
Tremoulet via llvm-dev
Sent: Wednesday, March 31, 2021 2:09 PM
To: llvm-dev <llvm-dev at lists.llvm.org>
Subject: [EXTERNAL] [llvm-dev] inttoptr and noalias returns

Hi,

I'm a bit confused about the interaction between inttoptr and noalias, and
would like to better understand our model.

I realize there's a bunch of in-flight work around restrict modeling and
that ptrtoint was on the agenda for last week's AA call.  I'm interested
in understanding both the current state and the thinking/plans for the future. 
And I'm happy for pointers to anywhere this is already written down, I
didn't find it from skimming the AA call minutes or the mailing list
archive, but I could easily have overlooked it, and haven't really dug into
the set of restrict patches (nor do I know where to get a list of those).

I also realize that with aliasing questions there can always be a gap between
what the model says we can infer and how aggressive analyses and optimizations
are about actually making use of those inferences.  Again I'm interested in
both answers (and happy for either).

In the LangRef section on pointer aliasing rules [1], I see

An integer constant other than zero or a pointer value returned from a function
not defined within LLVM may be associated with address ranges allocated through
mechanisms other than those provided by LLVM. Such ranges shall not overlap with
any ranges of addresses allocated by mechanisms provided by LLVM.

And I'm curious what "mechanisms provided by LLVM" for allocation
means.  Alloca, presumably.  Global variables?  Certain intrinsics?  Any
function with a noalias return value?

In the LangRef description of the noalias attribute [2], I see

This indicates that memory locations accessed via pointer values based on the
argument or return value are not also accessed, during the execution of the
function, via pointer values not based on the argument or return value ...  On
function return values, the noalias attribute indicates that the function acts
like a system memory allocation function, returning a pointer to allocated
storage disjoint from the storage for any other object accessible to the caller.

The phrase "the storage for any other object accessible to the caller"
in the noalias description sounds like a broader category than the phrase
"mechanisms provided by LLVM" from the pointer aliasing section, so I
would expect that if the pointer returned from a call to a function with return
attribute noalias does not escape, then loads/stores through it would not alias
loads/stores through a pointer produced by inttoptr.  Am I interpreting that
correctly?

I wrote some snippets [3] to see what the optimizer would do.  Each case has a
store of value 86 via pointer %p that I'd expect dead store elimination to
remove if we think it does not alias the subsequent load via pointer %q (because
immediately after that is another store to %p).
In each case, %q is the result of a call to a function whose return value is
annotated noalias.

When %p is a pointer parameter, I indeed see the optimizer removing the dead
store:
define i8 @test1(i8* %p) {

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this gets removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}

When %p is the result of inttoptr, I do not see the store being removed, and
I'm wondering if this is because of a subtle aliasing rule or an intentional
conservativism in the optimizer or just a blind spot in the analysis:
define i8 @test2(i64 %p_as_int) {
    %p = inttoptr i64 %p_as_int to i8*

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this does not get removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}

When I outline the inttoptr into a separate function, I again see the optimizer
remove the dead store, which again I'm wondering if the difference between
this and the previous case is an intentional subtle point or what.
define i8* @launder(i64 %int) noinline {
  %ptr = inttoptr i64 %int to i8*
  ret i8* %ptr
}

define i8 @test3(i64 %p_as_int) {
    %p = call i8* @launder(i64 %p_as_int)

    %q = call i8* @allocate()
    store i8 86, i8* %p ; <-- this gets removed
    %result = load i8, i8* %q
    store i8 0, i8* %p
    ret i8 %result
}



Happy for any insights you can share.

Thanks,
-Joseph

1 -
https://llvm.org/docs/LangRef.html#pointeraliasing<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fllvm.org%2Fdocs%2FLangRef.html%23pointeraliasing&data=04%7C01%7Cjotrem%40microsoft.com%7Ce772dc1fd7ee4665003b08d8f47007eb%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637528109307055170%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=iQ4uHRskXvviDCAzX1otuyuii9FhnmkYO8z5YkHI0y0%3D&reserved=0>
2 -
https://llvm.org/docs/LangRef.html#parameter-attributes<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fllvm.org%2Fdocs%2FLangRef.html%23parameter-attributes&data=04%7C01%7Cjotrem%40microsoft.com%7Ce772dc1fd7ee4665003b08d8f47007eb%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637528109307055170%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=uDsHa3L12nNt7y5fK1GU36D%2BflL7RmQIW8X2gkhbM%2Fo%3D&reserved=0>
3 -
https://godbolt.org/z/x8e41G33Y<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgodbolt.org%2Fz%2Fx8e41G33Y&data=04%7C01%7Cjotrem%40microsoft.com%7Ce772dc1fd7ee4665003b08d8f47007eb%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637528109307065126%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=j8cZ0Stb%2F%2BRZMe%2FNotzuvJTz%2FjDUJBqLixbXp0WRBH0%3D&reserved=0>


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210402/c0b09f03/attachment.html>

llvm dev - Apr 2021 - inttoptr and noalias returns

[llvm-dev] inttoptr and noalias returns

[llvm-dev] inttoptr and noalias returns