This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Improve `noalias` deduction based on memory information
Needs ReviewPublic

Authored by jdoerfert on Jan 26 2020, 2:00 AM.

Details

Summary

We now use memory behavior and memory location information to deduce

`noalias` for (call site) arguments. The key idea is that `noalias`
does not prevent aliases but accesses that would cause a race if
executed concurrently.

We do this in two ways:

[(1) At the call site] If the callee will not access "unknown" memory
locations we can look at the global and argument locations that are
accessed and determine if the call site operand aliases with the globals
or the call site operands associated with the arguments. If not,
`noalias` can be deduced.

[(2) In the callee] No matter what accesses the callee contains, if we
know the ones that happen for a given call site do not alias with an
argument the associated call site operand is `noalias`.

Diff Detail

Event Timeline

jdoerfert created this revision.Jan 26 2020, 2:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 26 2020, 2:00 AM

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

xbolva00 added inline comments.
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-02-01-ReturnAttrs.ll
22 ↗(On Diff #240424)

What happens here? We lost nocapture.

jdoerfert marked an inline comment as done.Jan 26 2020, 10:03 AM
jdoerfert added inline comments.
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-02-01-ReturnAttrs.ll
22 ↗(On Diff #240424)

We did not lose information ;)

On call sites we do not automatically derive every attribute, it is generally not needed. Before, we needed to know if the attribute was nocapture so we derived it for the call site as well. Now, we can get the noalias on %x in @deref without the nocapture so it is not manifested here. If you query it via the llvm API you would get it anyway because we marked the argument in @deref.

xbolva00 added inline comments.Jan 26 2020, 10:23 AM
llvm/test/Transforms/Attributor/ArgumentPromotion/2008-02-01-ReturnAttrs.ll
22 ↗(On Diff #240424)

Ah, true. Thanks!

jdoerfert updated this revision to Diff 240770.Jan 27 2020, 9:22 PM

Second try, cleaner approach and more powerful

jdoerfert updated this revision to Diff 240771.Jan 27 2020, 9:26 PM

Update the tests as well

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

jdoerfert edited the summary of this revision. (Show Details)Feb 9 2020, 1:18 AM
jdoerfert updated this revision to Diff 243441.Feb 9 2020, 1:19 AM
jdoerfert edited the summary of this revision. (Show Details)

rebase

baziotis added inline comments.Feb 14 2020, 7:16 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2838–2840

Why do we know that?

2858

Maybe doc here (?) It looks similar to the above but some things I think would be good to be mentioned like why do we test for globals here.

2871

Maybe you want *Ptr here. Also maybe conditioned on Ptr (like above).

jdoerfert marked 3 inline comments as done.Feb 14 2020, 7:32 PM
jdoerfert added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
2838–2840

If we have already noalias (or an alloca) we know we do not alias any access in the scope not derived from this pointer. Since globals cannot be derived from a noalias pointer (in a way that would be problematic here) or in any way from an alloca, we know the global does not alias the pointer.

2858

Will write a doc :)

2871

Will do that.

jdoerfert updated this revision to Diff 244914.Feb 16 2020, 9:29 PM
jdoerfert marked 3 inline comments as done.

Addressed comments

uenoku added inline comments.Feb 17 2020, 3:03 AM
llvm/lib/Transforms/IPO/Attributor.cpp
2769

Don't we need to look at constant memories?

2830–2837

Please make a helper for

if(!AAR) AAR = ..
bool IsAliasing = !AAR | !AAR->isNoAlias(..);
2924

How about NO_MALLOCED_MEM?

baziotis added inline comments.Feb 17 2020, 3:28 AM
llvm/lib/Transforms/IPO/Attributor.cpp
2838–2840

Thanks for the explanation! The parts "a scope is derived from a pointer" (e.g. in the scope not derived from this pointer) are still unclear to me. What do I miss? Is there a specific part of code / doc I can read?

2858

Thanks!

2871

Ty!

baziotis added inline comments.Feb 17 2020, 3:35 AM
llvm/lib/Transforms/IPO/Attributor.cpp
2769

So, no malloced memory?

2924

Why not check for malloced memory? Although I think this goes along with your comment about constant memories.

uenoku added a comment.EditedFeb 17 2020, 3:40 AM

And I have a question.

define i32 @f1(i32* %p, i32* %q){
entry:
  %0 = load i32, i32* %q
  %1 = load i32, i32* %p
  %add = add nsw i32 %1, %0
  ret i32 %add
}

define i32 @f2(i32* nocapture readonly %p) {
entry:
  %call = tail call i32 @f1(i32* %p, i32* %p)
  ret i32 %call
}

In this case, %call = tail call i32 @f1(i32* noalias %p, i32* noalias %p) is deduced because they have only "read-read" dependencies.
I agree that this is a sound deduction since there is no write. (I know Rust compiler is doing similar things)

However, looking back to the definition of noalias in LangRef, I think this annotation violates the definition. Is it allowed conventionally?

uenoku added inline comments.Feb 17 2020, 3:47 AM
llvm/lib/Transforms/IPO/Attributor.cpp
2769

I think malloced memory cannot be seen from the caller so we don't have to care about here.

2924

I think malloced mem cannot be accessed from the caller but constant memory can be accessed.

jdoerfert marked 3 inline comments as done.Feb 17 2020, 7:15 AM
jdoerfert added a subscriber: hfinkel.

And I have a question.

define i32 @f1(i32* %p, i32* %q){
entry:
  %0 = load i32, i32* %q
  %1 = load i32, i32* %p
  %add = add nsw i32 %1, %0
  ret i32 %add
}

define i32 @f2(i32* nocapture readonly %p) {
entry:
  %call = tail call i32 @f1(i32* %p, i32* %p)
  ret i32 %call
}

In this case, %call = tail call i32 @f1(i32* noalias %p, i32* noalias %p) is deduced because they have only "read-read" dependencies.
I agree that this is a sound deduction since there is no write. (I know Rust compiler is doing similar things)

However, looking back to the definition of noalias in LangRef, I think this annotation violates the definition. Is it allowed conventionally?

If this would violate the LangRef we would have a problem. I don't think it does but I think we need to make that explicit. I'll talk to @hfinkel and come back with lang ref patch or a revised version of this ;)

llvm/lib/Transforms/IPO/Attributor.cpp
2769

Correct. Constant memory does not change, so it's the read only argument again. Malloced memory, local memory, inaccessible memory, cannot "alias" with the arguments we pass at the call site by design.

2838–2840

I think the actually relevant documentation is https://en.cppreference.com/w/c/language/restrict

2924

Constant memory is read only, read-read argument. Malloced memory is memory that was returned by a noalias function. It does not alias anything not derived from that pointer. If the call was made in this function (the callee wrt AANoAliasCallSiteArgument) then it cannot alias an argument of this function since they were around before the call was made :)

And I have a question.

define i32 @f1(i32* %p, i32* %q){
entry:
  %0 = load i32, i32* %q
  %1 = load i32, i32* %p
  %add = add nsw i32 %1, %0
  ret i32 %add
}

define i32 @f2(i32* nocapture readonly %p) {
entry:
  %call = tail call i32 @f1(i32* %p, i32* %p)
  ret i32 %call
}

In this case, %call = tail call i32 @f1(i32* noalias %p, i32* noalias %p) is deduced because they have only "read-read" dependencies.
I agree that this is a sound deduction since there is no write. (I know Rust compiler is doing similar things)

However, looking back to the definition of noalias in LangRef, I think this annotation violates the definition. Is it allowed conventionally?

If this would violate the LangRef we would have a problem. I don't think it does but I think we need to make that explicit. I'll talk to @hfinkel and come back with lang ref patch or a revised version of this ;)

I think that this is probably a good idea, but I think that we need a short RFC on this. We should have some visibility on this issue before we update the LangRef in this regard.

baziotis added inline comments.Feb 20 2020, 5:25 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2838–2840

Thanks, I hadn't seen that comment.

The lang ref patch landed. I need to rebase this but I was hoping someone could take another look now.