[llvm-dev] [EXTERNAL] RE: inttoptr and noalias returns
Nikita Popov via llvm-dev
llvm-dev at lists.llvm.org
Fri Apr 16 10:00:40 PDT 2021
On Fri, Apr 16, 2021 at 4:48 PM Joseph Tremoulet via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> > otherwise relies on the incorrect transformation “inttoptr(ptrtoint(x))
> -> x”
>
>
>
> Could you point me to an example/explanation of why that transformation is
> incorrect? It’s not clear to me from the LangRef.
>
>
>
>
>
> > A big issue with LLVM’s static analysis is caching, since everything is
> done lazily. If you want to add something more expensive to BasicAA, you
> need to make sure that information is cached somehow to avoid recomputing
> it a thousand times. Compilation time is quite sensitive to the performance
> of BasicAA.
>
>
>
> The IsCapturedCache in AAQueryInfo is pretty close to what I’m after, but
> I don’t really understand why the code in aliasCheck is using the weaker
> isEscapeSource as opposed to !isNonEscapingLocalObject.
>
>
>
>
>
> > escape pointers just like ptrtoint does
>
>
>
> Yeah, so if the rule for ptrtoint is simply that the source pointer
> escapes, then I’d think we could take advantage of the flip side of that
> and isEscapeSource could return true for inttoptr, without needing
> expensive analysis/caching. But I know this can be a subtle area, so I’m
> not sure that’s the rule. I see [1] that Ryan Taylor added discussing it
> to the agenda for the February AA conference call, I’m curious what the
> outcome of that was.
>
Yes, I believe adding inttoptr to isEscapeSource() should be safe, as any
way to produce an integer from a pointer (via ptrtoint, store+load, icmp)
will have counted as an escape.
Nikita
Thanks,
>
> -Joseph
>
>
>
> 1 - https://lists.llvm.org/pipermail/llvm-dev/2021-February/148671.html
>
>
>
>
>
> *From:* Nuno Lopes <nunoplopes at sapo.pt>
> *Sent:* Thursday, April 15, 2021 6:37 AM
> *To:* Joseph Tremoulet <jotrem at microsoft.com>
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* [EXTERNAL] RE: [llvm-dev] inttoptr and noalias returns
>
>
>
> You’re right that LLVM is very conservative in handling inttoptr. And
> otherwise relies on the incorrect transformation “inttoptr(ptrtoint(x))
> -> x” to get rid of inttoptr.
>
> I agree the store should have been removed in your second example. I guess
> inttoptr is not frequently used, and even less after a bunch of fixes to
> prevent optimizers from creating new ones.
>
>
>
> BasicAA is quite basic, but that’s all LLVM has. The other alias analyses
> in git are either not useful in practice, unfinished or buggy. (I haven’t
> looked into that dir in a couple of years, so things may have changed in
> the meantime).
>
> A big issue with LLVM’s static analysis is caching, since everything is
> done lazily. If you want to add something more expensive to BasicAA, you
> need to make sure that information is cached somehow to avoid recomputing
> it a thousand times. Compilation time is quite sensitive to the performance
> of BasicAA.
>
>
>
> Although there’s no definitive semantics for pointer comparisons yet
> (soonish I hope), LLVM’s behavior implies that pointer comparisons indeed
> escape pointers just like ptrtoint does (except if the two pointers being
> compared are inbounds and point to the same object, and therefore the
> comparison is only around offsets and thus their address doesn’t leak).
>
>
>
> Nuno
>
>
>
>
>
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Joseph
> Tremoulet via llvm-dev
> *Sent:* 02 April 2021 19:26
> *To:* llvm-dev <llvm-dev at lists.llvm.org>
> *Subject:* Re: [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%7Ca920365acb0b45f6dab508d8fffa7870%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637540798542822348%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=VKfQjkO08JeSX4BTRWQ4zyQha%2FWcNfK%2FkAgoamYEJSM%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%7Ca920365acb0b45f6dab508d8fffa7870%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637540798542822348%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=EOiYYW2c3RKk6gRh2qT5tteyUnr0B3xQsBF5fUkLYRA%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%7Ca920365acb0b45f6dab508d8fffa7870%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637540798542832302%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=yBwkhCH%2BhdzS%2BaKWZP9riVgdVo%2F11tQ8tGugy21QPh0%3D&reserved=0>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210416/7b52fec3/attachment.html>
More information about the llvm-dev
mailing list