[llvm-dev] Full restrict support - status update

[Jeroen Dobbelaere via llvm-dev]

Hi all,

## Status:

During the past weeks I have updated the restrict patches with various improvements:
- the ScopedNoAliasAA now also works together with the new pass manager
- the SLPVectorizer now works nice with the noalias support.
- there were some issues with some of the options enabling/disabling full restrict. These have been fixed.
- various smaller enhancements.

Today, I rebased the patches. [1]
Based on the feedback at the 'full restrict' roundtable, I also created a single patch containing all changes. [2]

## Request for testing and feedback:

Extra help with the code review would be great [1].
This includes feedback on the design decisions and naming.

It would also be great if you could just try it out and check the effect on your benchmarks and testcases.
The single patch[2] should make it more convenient to try it out:
- If the full restrict support triggers a problem, I would like to hear about it.
- But, if it works and improves your benchmarks, I also would like to hear about it, either through
phabricator, the llvm mailing list or in private.

## Known issues:

- For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.
- the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
-- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
restrict pointers which have been declared in the same scope.

## Future changes
- Another request that came up during the round table, is to split up the documentation in two parts:
a separate document describing the noalias architecture, and the LangRef, describing the intrinsics.
I'll be working on that in the coming days.

Thanks,

Jeroen Dobbelaere

[1] https://reviews.llvm.org/D68484 [PATCH 01/38] [noalias] LangRef: noalias intrinsics and noalias_sidechannel documentation.
[2] https://reviews.llvm.org/D69542 Full Restrict Support - single patch

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Finkel, Hal J. via llvm-dev]

On 10/28/19 8:12 PM, Jeroen Dobbelaere via llvm-dev wrote:
> Hi all,
>
> ## Status:
>
> During the past weeks I have updated the restrict patches with various improvements:
> - the ScopedNoAliasAA now also works together with the new pass manager
> - the SLPVectorizer now works nice with the noalias support.
> - there were some issues with some of the options enabling/disabling full restrict. These have been fixed.
> - various smaller enhancements.
>
> Today, I rebased the patches. [1]
> Based on the feedback at the 'full restrict' roundtable, I also created a single patch containing all changes. [2]
>
> ## Request for testing and feedback:
>
> Extra help with the code review would be great [1].
> This includes feedback on the design decisions and naming.
>
> It would also be great if you could just try it out and check the effect on your benchmarks and testcases.
> The single patch[2] should make it more convenient to try it out:
> - If the full restrict support triggers a problem, I would like to hear about it.
> - But, if it works and improves your benchmarks, I also would like to hear about it, either through
> phabricator, the llvm mailing list or in private.
>
> ## Known issues:
>
> - For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.
> - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
> -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
> restrict pointers which have been declared in the same scope.

This, we can fix now independent of anything else. We should either fix
the test, if there's a reasonable way to fix it, or we should remove it.
If you can post a patch with an explanation of the problem, that would
be great.

Thanks again,

Hal

>
> ## Future changes
> - Another request that came up during the round table, is to split up the documentation in two parts:
> a separate document describing the noalias architecture, and the LangRef, describing the intrinsics.
> I'll be working on that in the coming days.
>
> Thanks,
>
> Jeroen Dobbelaere
>
> [1] https://reviews.llvm.org/D68484 [PATCH 01/38] [noalias] LangRef: noalias intrinsics and noalias_sidechannel documentation.
> [2] https://reviews.llvm.org/D69542 Full Restrict Support - single patch
>
> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

[Sam Elliott via llvm-dev]

> On 29 Oct 2019, at 4:06 am, Finkel, Hal J. via llvm-dev <llvm...@lists.llvm.org> wrote:
>
> On 10/28/19 8:12 PM, Jeroen Dobbelaere via llvm-dev wrote:
>>
>> - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
>> -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
>> restrict pointers which have been declared in the same scope.
>
>
> This, we can fix now independent of anything else. We should either fix
> the test, if there's a reasonable way to fix it, or we should remove it.
> If you can post a patch with an explanation of the problem, that would
> be great.

I’m wary of updating the test itself, as someone may re-vendor the GCC C torture suite, undoing those edits. However, we already exclude some tests in the GCC torture suite because they rely on UB. Having inspected pr38212.c, I am happy to add this test to the list of excluded tests with the explanation provided. I’ll commit that change today.

Sam

--
Sam Elliott
Software Developer - LLVM
lowRISC CIC
--

[David Greene via llvm-dev]

Jeroen Dobbelaere via llvm-dev <llvm...@lists.llvm.org> writes:

> - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
> -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
> restrict pointers which have been declared in the same scope.

What's the failure mode? Wrong answers or compiler abort? If the
latter, it would be nice if LLVM could emit a warning about illegal use
of restrict. Longer term, a RestrictSanitizer would be really helpful.

-David

[Roman Lebedev via llvm-dev]

On Tue, Oct 29, 2019 at 9:26 PM David Greene via llvm-dev
<llvm...@lists.llvm.org> wrote:
>
> Jeroen Dobbelaere via llvm-dev <llvm...@lists.llvm.org> writes:
>
> > - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
> > -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
> > restrict pointers which have been declared in the same scope.
>
> What's the failure mode? Wrong answers or compiler abort? If the
> latter,

> it would be nice if LLVM could emit a warning about illegal use
> of restrict. Longer term, a RestrictSanitizer would be really helpful.

Yes :)
I would think it would not require any runtime (think - asan/msan) support,
so i'm not sure why it could not be a part of UBSan proper.
In other words i'd like to *tentatively* claim this,
i may be interested to look into it, after the restrict support lands :)

> -David
Roman

[Finkel, Hal J. via llvm-dev]

On 10/29/19 2:25 PM, Roman Lebedev via llvm-dev wrote:
> On Tue, Oct 29, 2019 at 9:26 PM David Greene via llvm-dev
> <llvm...@lists.llvm.org> wrote:
>> Jeroen Dobbelaere via llvm-dev <llvm...@lists.llvm.org> writes:
>>
>>> - the 'SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-pr38212.test' in the 'test-suite' fails:
>>> -- the test is wrong as it triggers undefined behavior: it reads and writes the same object through 2 different
>>> restrict pointers which have been declared in the same scope.
>> What's the failure mode? Wrong answers or compiler abort? If the
>> latter,
>> it would be nice if LLVM could emit a warning about illegal use
>> of restrict. Longer term, a RestrictSanitizer would be really helpful.
> Yes :)
> I would think it would not require any runtime (think - asan/msan) support,
> so i'm not sure why it could not be a part of UBSan proper.
> In other words i'd like to *tentatively* claim this,
> i may be interested to look into it, after the restrict support lands :)

Great.

I'm not sure, however, how you do this without a runtime and shadow
memory. You need to add some dynamic data-flow analysis to determine
which pointers are based on which restrict-qualified pointers. This, in
addition to in-function instrumentation, needs some side channel to deal
with function calls (because you need to pass this information across
the function-call interface and it's not clear to me that changing the
ABI is generally practical) and values stored in memory (which likely
need shadow member). Then, for each byte of memory, you need to keep
track of which have been accessed by pointers based on
restrict-qualified pointers, which restrict-qualified pointers, and
appropriately clear out that data when the associated restrict-qualified
pointer goes out of scope.

 -Hal

>
>> -David
> Roman
>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm...@lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

[Jeroen Dobbelaere via llvm-dev]

> -----Original Message-----
> From: David Greene <gre...@obbligato.org>
[...]
> What's the failure mode? Wrong answers or compiler abort? If the
> latter, it would be nice if LLVM could emit a warning about illegal use
> of restrict. Longer term, a RestrictSanitizer would be really helpful.
>
> -David

The compiler produces code that does not do what the testcase expects it to do.
This particular case could be detected and warned for at compile time (after inlining and constant propagation).

Greetings,

Jeroen

[Finkel, Hal J. via llvm-dev]

On 10/29/19 5:16 PM, Jeroen Dobbelaere via llvm-dev wrote:
>
>> -----Original Message-----
>> From: David Greene <gre...@obbligato.org>
> [...]
>> What's the failure mode? Wrong answers or compiler abort? If the
>> latter, it would be nice if LLVM could emit a warning about illegal use
>> of restrict. Longer term, a RestrictSanitizer would be really helpful.
>>
>> -David
> The compiler produces code that does not do what the testcase expects it to do.
> This particular case could be detected and warned for at compile time (after inlining and constant propagation).

We can also certainly consider adding optimization remarks in to
generate this kind of information as well.

 -Hal

>
> Greetings,
>
> Jeroen
>
> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

[Alexey Zhikhartsev via llvm-dev]

Hi Jeroen,

Thank you very much for the great work, it is much appreciated.

> - For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.

Do you have plans to work on this in the near future? Do you know how much work it is and if there are significant hurdles?

Thanks,

Alexey

[Jeroen Dobbelaere via llvm-dev]

Hi Alexey,

 

Adding llvm-ir bitcode support means adding/adapting the tags for LOAD/STORE instructions and adding

the support for the noalias_sidechannel at the right places.

 

I had a short attempt to implement it when preparing the public patches, but I am not familiar with that

part of the llvm code. When I noticed that it would take a lot longer than anticipated, I postponed it.

Also because it is likely that the way how the noalias_sidechannel was added to LoadInst/StoreInst might

change.

 

At this moment, I am not planning to work on this. For the current implementation, there might be

a number of possibilities for adding support :

  - maybe 2 new tags are needed (FUNC_CODE_INST_{LOAD_NOALIAS,STORE_NOALIAS})

  - or maybe it is sufficient to add the noalias_sidechannels as extra operands and look at the number of

     operands to see if they are present or not

  - or maybe it is sufficient to look at the number of operands, and the noalias_sidechannel operand should

    be added with an extra bit, indicating if it is really there or not...

 

Greetings,

 

Jeroen Dobbelaere

 

 

From: Alexey Zhikhartsev <alexey....@gmail.com>
Sent: Thursday, October 31, 2019 16:21
To: Jeroen Dobbelaere <dob...@synopsys.com>
Cc: llvm...@lists.llvm.org
Subject: Re: [llvm-dev] Full restrict support - status update

 

Hi Jeroen,

 

Thank you very much for the great work, it is much appreciated.

 

> - For now, there is still no llvm-ir bitcode support for the load/store noalias_sidechannel argument.

 

Do you have plans to work on this in the near future? Do you know how much work it is and if there are significant hurdles?

 

Thanks,

Alexey

 

[...]

[Alexey Zhikhartsev via llvm-dev]

Thanks, Jeroen.

We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?

Best,

Alexey

[Jeroen Dobbelaere via llvm-dev]

Hi Alexey,

>From: Alexey Zhikhartsev
[..]
> We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?

Yes, I think that the lack of bitcode support will prevent it.

During the Developers meeting, I also talked with Hal and Johannes.
They had some extra remarks:
- (1) the restrict implementation deserves a separate document. (I am working on that one)
- (2) they don't like the naming of 'noalias_sidechannel'.
- (3) they also have some other mechanisms in mind to add the 'sidechannel' to the load/store instructions
(and maybe to function calls, intrinsics; currently that is handled through llvm.noalias.arg.guard)

For (2) and (3), I am waiting for a proposal from them ;)

Greetings,

Jeroen Dobbelaere

[Doerfert, Johannes via llvm-dev]

Apologies for the delay.

On 11/06, Jeroen Dobbelaere wrote:
> >From: Alexey Zhikhartsev
> [..]
> > We would love to see your patches merged as soon as possible, so I was wondering: do you think the lack of bitcode support will prevent that from happening?
>
> Yes, I think that the lack of bitcode support will prevent it.
>
> During the Developers meeting, I also talked with Hal and Johannes.
> They had some extra remarks:
> - (1) the restrict implementation deserves a separate document. (I am working on that one)
> - (2) they don't like the naming of 'noalias_sidechannel'.
> - (3) they also have some other mechanisms in mind to add the 'sidechannel' to the load/store instructions
> (and maybe to function calls, intrinsics; currently that is handled through llvm.noalias.arg.guard)
>
> For (2) and (3), I am waiting for a proposal from them ;)

I would like to see the restrict support be merged but, as Jeroen
mentions above, I feel there are two design choices we have to
overthink. Here are short descriptions to get some feedback from the
community:

(A) Naming and restriction

The name "sidechannel" is unfortunate, it has various negative
connotations, e.g., the release notes that read:
"LLVM 10.0 now has sidechannel support for your restrict pointer"
will raise a lot of follow up questions.

What I think we actually do, and what we should call it, is "provenance"
tracking.

Now beyond the pure renaming of "sidechannel" into "provenance" (or sth.
similar) I want us to decouple provenance tracking from the noalias
logic. Noalias/restrict is one use case in which (pointer) provenance
information is useful but not the only one. If we add some mechanism to
track provenance, let's make it generic and reusable. Note that the
basic ideas are not much different to what the noalias RFC proposed.
The major difference would be that we have provenance information and if
that originates in an `llvm.restrict.decl` call we can use it for
(no)alias queries.



(B) Using operand bundles

Right now, loads and stores are treated differently and given a new
operand. Then there are intrinsics to decode other kinds of information.
As an alternative, we could allow operand bundles on all instructions
and use them to tie information to an instruction. The "sidechannel"
operand of a load would then look something like:
load i32* %p [ "ptr_provenance"(%p_decl) ]
and for a store we could have
store i32** %p.addr, i32* %p [ "ptr_provenance"(%p_decl) ]

The benefit is that we do not change the operand count (which causes a
lot of noise) but we still have to make sure ptr/value uses are not
confused with operand bundle uses. We can attach the information to more
than load/store instructions, also to remove the need for some of the
intrinsics.


Please let me know what you think!

Cheers,
Johannes

[Jeroen Dobbelaere via llvm-dev]

Hi Johannes et al,

"provenance" might indeed be a good name.

There is a big difference between a restrict declaration, and a restrict usage:
- the declaration intrinsic (llvm.noalias.decl) is used to track in the cfg the location
where the restrict variable was declared. This is important to handle code motion,
merging, duplication in a correct way (inlining, loop unrolling, ...)
- the restrict usage intrinsics (llvm.noalias and llvm.side.noalias) are used to indicate
that from that point on, restrict (noalias) properties are introduced for that pointer.
They can exist without an associated 'llvm.noalias.decl' (when the declaration is outside
the function.)
Given that, I assume that you mean 'llvm.provenance.noalias' (~ llvm.side.noalias) instead
of 'llvm.restrict.decl'.

>
>
>
> (B) Using operand bundles
>
> Right now, loads and stores are treated differently and given a new
> operand. Then there are intrinsics to decode other kinds of information.
> As an alternative, we could allow operand bundles on all instructions
> and use them to tie information to an instruction. The "sidechannel"
> operand of a load would then look something like:
> load i32* %p [ "ptr_provenance"(%p_decl) ]
> and for a store we could have
> store i32** %p.addr, i32* %p [ "ptr_provenance"(%p_decl) ]
>
> The benefit is that we do not change the operand count (which causes a
> lot of noise) but we still have to make sure ptr/value uses are not
> confused with operand bundle uses. We can attach the information to more
> than load/store instructions, also to remove the need for some of the
> intrinsics.

To me, operand bundles sound to be more or less equivalent to the current
solution. It might also make the 'instruction cloning' easier, if we can omit the
'ptr_provenance' there. The change of the number of operands caused some
noise, but it is the changes in the amount of 'uses' of a pointer that refer to the
same instruction that caused the most problems. Especially when that instruction
was going to be erased. Operand bundles will still need those code changes.
(like in parts of D68516 and D68518)

As the 'Call' instruction already supports operand bundles, it could eliminate the need
for the 'llvm.noalias.arg.guard' intrinsic, which combines the normal pointer with the
side channel (aka provenance). But, after inlining, we still need to put that information
somewhere. Or it should be propagated during inlining.
Care must be taken not to lose that information when the 'call' is changed by optimizations
as, after inlining, that might result in wrong alias analysis conclusions.

Are you thinking of "operand bundles" support for just LoadInst/StoreInst, or for all
instructions ?

[Alina Sbirlea via llvm-dev]

Hi Johannes et al,

Trying to revive this discussion, as the restrict support is relevant for one of our teams.

Thank you,

Alina

[Finkel, Hal J. via llvm-dev]

Hi, everyone,

We've had a number of discussions recently, including on the Flang technical call, about potential improvements to LLVM's alias analysis to support handling restrict and restrict-like semantics.

We would like to try having a call to discuss these issues further. Please, if you're interested in joining, indicate your availability (prior to the end of this week):

  https://doodle.com/poll/evhwr2eyfvcf8ib3

Thanks again,

Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

---

From: llvm-dev <llvm-dev...@lists.llvm.org> on behalf of Alina Sbirlea via llvm-dev <llvm...@lists.llvm.org>
Sent: Monday, May 11, 2020 9:49 AM
To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>
Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

Subject: Re: [llvm-dev] Full restrict support - status update

[Finkel, Hal J. via llvm-dev]

Thanks to everyone who participated in the poll. The time that maximizes availability is:

  Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC.

I'll send out meeting information shortly.

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

---

From: llvm-dev <llvm-dev...@lists.llvm.org> on behalf of Finkel, Hal J. via llvm-dev <llvm...@lists.llvm.org>
Sent: Wednesday, May 13, 2020 11:14 AM
To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>

Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

Subject: [llvm-dev] LLVM Alias Analysis Technical Call - Doodle Poll

 

[Finkel, Hal J. via llvm-dev]

To join our call on Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC please use this information:

Meeting URL

https://bluejeans.com/643493129?src=join_info

Meeting ID

643 493 129

Want to dial in from a phone?

Dial one of the following numbers:

+1.312.216.0325 (US (Chicago))

+1.408.740.7256 (US (San Jose))

+1.866.226.4650 (US Toll Free)

(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?

Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

On our agenda, we'll have:

 1. Scalability challenges and other issues discovered with the current infrastructure (especially, perhaps, with the noalias metadata).

 2. Proposed solutions: progress, outstanding challenges, how to make progress going forward.

We'll formulate the detailed agenda and take notes from the call using this Google doc: https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

A summary will then be sent to the mailing list after the call. If you would like to add items to the agenda, please edit the document (or reply to this email).

Thanks again,

Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

---

From: Finkel, Hal J. <hfi...@anl.gov>
Sent: Monday, May 18, 2020 10:24 AM
To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>; Finkel, Hal J. <hfi...@anl.gov>

Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

Subject: Re: LLVM Alias Analysis Technical Call - Doodle Poll

 

[Tarique Islam via llvm-dev]

Hi Hal,

Thanks very much for scheduling the LLVM Alias Analysis Technical Call. I have added more details to the Google document.

Regards,
Tarique Islam
XL Fortran Compiler Development
IBM Toronto Software Lab
tis...@ca.ibm.com (905) 413-3190



"Finkel, Hal J. via llvm-dev" ---2020-05-18 12:41:56 PM---To join our call on Thursday, May 28th @ 9-10 AM central time / 2-3 PM UTC please use this informati

https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev_______________________________________________

LLVM Developers mailing list
llvm...@lists.llvm.org

https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev 

[Finkel, Hal J. via llvm-dev]

Great, thanks!

Are you planning on just talking about these things with slides? Do we have other things to which we can link for people to read?

-Hal

Hal Finkel

Lead, Compiler Technology and Programming Languages

Leadership Computing Facility

Argonne National Laboratory

---

From: Tarique Islam <tis...@ca.ibm.com>
Sent: Thursday, May 21, 2020 8:19:31 AM
To: Finkel, Hal J. <hfi...@anl.gov>
Cc: Alina Sbirlea <alina....@gmail.com>; Doerfert, Johannes <jdoe...@anl.gov>; Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; llvm...@lists.llvm.org <llvm...@lists.llvm.org>
Subject: RE: [llvm-dev] LLVM Alias Analysis Technical Call - Doodle Poll

 

[Tarique Islam via llvm-dev]

Hi Hal,

If it is okay with the group, we can start looking into the LLVM codebase for Metadata operations and discuss about the technical details related to the scalability. In that case, we can start with the following.

    ./llvm/include/llvm/IR/Metadata.h
    ./llvm/lib/IR/Metadata.cpp
    ./llvm/lib/Analysis/ScopedNoAliasAA.cpp

If needed, we can present some slides for a quick recap of the alias representation.

Regarding the hierarchical representation, we can start with your patch for scoped-noalias metadata.
https://github.com/llvm/llvm-project/commit/9414665a3b0bd525f84d76e24048ca60ebe6c710

Regards,
Tarique Islam
XL Fortran Compiler Development
IBM Toronto Software Lab
tis...@ca.ibm.com (905) 413-3190

"Finkel, Hal J." ---2020-05-21 12:15:42 PM---Great, thanks! Are you planning on just talking about these things with slides? Do we have other thi

[Tarique Islam via llvm-dev]

Two additional references for the discussion.

1. (IBM) Represent Fortran alias information in LLVM IR - http://lists.llvm.org/pipermail/llvm-dev/2020-April/140945.html
2. (Jeroen et al.) RFC: Full 'restrict' support in LLVM - https://lists.llvm.org/pipermail/llvm-dev/2019-October/135672.html

Regards,
Tarique Islam
XL Fortran Compiler Development
IBM Toronto Software Lab
tis...@ca.ibm.com (905) 413-3190

Tarique Islam via llvm-dev ---2020-05-25 08:34:18 PM---Hi Hal, If it is okay with the group, we can start looking into the LLVM codebase

[Finkel, Hal J. via llvm-dev]

Hi, everyone,

Just a quick reminder, this call starts in approximately 1.5 hours.

At the present time, our agenda has:

• Scalability challenges and other issues discovered with the current infrastructure (especially, perhaps, with the noalias metadata).

• Issue #1: MDNode::intersect uses O(n^2) algorithm. The operation does not scale for large NoAlias sets.
  

• Issue #2: ScopedNoAliasAAResult::mayAliasInScopes includes overhead (per query) of partitioning the input set based on the domain metadata.

• Issue #3: Memory footprint of the flattened Alias.Scope or NoAlias set can be large.

• Issue #4: correctness: current implementation has problems after inlining in a loop.  

• Proposed solutions: progress, outstanding challenges, how to make progress going forward.

• Proposal #1: (Related to both Issue #1 and Issue #2) In the MDNode class, pre-partition the set of Metadata operands where each partition is an ordered set of Metadata operands belonging to a specific domain.
  

• Proposal #2: (Related to Issue #3) Design a hierarchical representation for the metadata operands in Alias.Scope and NoAlias sets.

• Proposal #3: https://reviews.llvm.org/D68484 provides the infrastructure to fix issue #4. It might also help with issue #1 and issue #3 as it makes it possible to share scopes.

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

From: Finkel, Hal J. <hfi...@anl.gov>

Sent: Monday, May 18, 2020 11:40 AM

To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>
Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

[Finkel, Hal J. via llvm-dev]

Hi, everyone,

We had a great call last month, and progress is definitely being made on several fronts. The notes from our last call are available here:

  https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit#heading=h.vpxs8lkuxy79

and, also, pasted below.

DOODLE POLL:

As we discussed on our last call, I would like to schedule a regular call to discuss alias-analysis issues within LLVM. I've put together an initial Doodle poll to pick a time for this call: https://doodle.com/poll/9iqfaqttvvic5rfp

Please fill out this poll with the understanding that the meeting will recur every four weeks. If you're interested in participating, but none of the times on the poll would work for you, please let me know.

Notes from our last call:

****

• Scalability challenges and other issues discovered with the current infrastructure (especially, perhaps, with the noalias metadata).
  

• Issue #1: MDNode::intersect uses O(n^2) algorithm. The operation does not scale for large NoAlias sets.

• Issue #2: ScopedNoAliasAAResult::mayAliasInScopes includes overhead (per query) of partitioning the input set based on the domain metadata.

• Issue #3: Memory footprint of the flattened Alias.Scope or NoAlias set can be large.

• Issue #4: correctness: current implementation has problems after inlining in a loop.  

Notes:

• Jeroen notes that he has not observed scalability issues with the
  “full restrict” implementation.

• Michael notes that part of the scalability challenge comes from the fact that the noalias scheme marks all those things with which you don’t alias, but for restrict-like pointers, that’s the default for everything in that scope.

• Tarique notes that there may still be a need for AA from the frontend, e.g., for Fortran, above what the C-like restrict provides.

• Eric asks if anyone is considering a ground-up design to support Fortran?

• Troy notes that we would prefer one representation to cover Fortran, C, etc. Fortran is, in some sense, simpler than C/C++. Also notes that language-specific AA can be a useful technique as well.

• Johannes notes that other languages, e.g., Rust, can also benefit, and we might need something where we can have universes, negated aliasing edges, etc.

• Michael notes that we can chain AA, and so it’s possible to have something more domain specific.

• Hal notes that if we have language-specific MD, we need to figure out how to maintain it (otherwise, all of the passes will drop it, but maintaining it means that enough of the semantics must be available). Jeroen notes that reusing in-tree passes maximally reuses correct implementation in combination with loop unrolling, etc.

• Proposed solutions: progress, outstanding challenges, how to make progress going forward.
  

• Proposal #1: (Related to both Issue #1 and Issue #2) In the MDNode class, pre-partition the set of Metadata operands where each partition is an ordered set of Metadata operands belonging to a specific domain.

• Proposal #2: (Related to Issue #3) Design a hierarchical representation for the metadata operands in Alias.Scope and NoAlias sets.

• Proposal #3: https://reviews.llvm.org/D68484 provides the infrastructure to fix issue #4. It might also help with issue #1 and issue #3 as it makes it possible to share scopes.
  

Notes

• Tarique presented challenges with the current prototype, including that there’s currently no way to differentiate noalias MD from other kinds of metadata, so it’s hard to keep a useful cache in the generic MDNode implementation.

• Jeroen presented some slides on the full-restrict implementation, noted how this scheme might solve/mitigate some of the scalability challenges associated with the pure-metadata solution.

• The full-restrict implementation is being used, and Jerone is currently updating this implementation based on feedback from that usage, he also will update the implementation to use provenance instead of sidechannel and repost.

• Johannes notes that we need more reviewers for this patch set.

****

Thanks again,

Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

From: llvm-dev <llvm-dev...@lists.llvm.org> on behalf of Finkel, Hal J. via llvm-dev <llvm...@lists.llvm.org>

Sent: Thursday, May 28, 2020 7:35 AM

To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>
Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

Subject: Re: [llvm-dev] LLVM Alias Analysis Technical Call - Doodle Poll

 

[Chris Lattner via llvm-dev]

Thanks for sharing this Hal.

Random thought - with the goal of increasing cross-pollination, it might be useful to invite someone from the MLIR world who has been working on it MemoryEffects design to give a talk or share some thoughts.  It is a more general and quite different approach than LLVM’s alias analysis implementation.

It looks like River, Mehdi, Lei, and Jacques have all been involved in it, but I don’t know to what level.

-Chris

[River Riddle via llvm-dev]

The memory effects design is ever so slightly orthogonal to alias analysis. I've been largely following along to the discussion on alias analysis in LLVM to determine how we should model it in MLIR. There are obviously some different things to consider, especially given that MLIR needs to be a bit more general(from an infrastructure standpoint, and not necessarily an algorithmic standpoint). What is in-tree right now for aliasing, i.e. resources, is really more of a placeholder than a long term solution. Would love to chat sometime though. I've just been waiting for the alias redesign discussions in LLVM to get a bit further before jumping in.

-- River

[Hal Finkel via llvm-dev]

Thanks, everyone. It looks like we do have a time that works for almost everyone.

Let's plan to meet on Tuesday, July 14th @ 12-1 central time / 10-11 pacific time / 6-7pm in London, and at that time on Tuesday every four weeks.

Please use the Google doc linked below to add agenda items for the next call (or, if you cannot access a Google doc, send me a note and I'll add them for you).

https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

Meeting URL
https://bluejeans.com/101176001?src=join_info

Meeting ID
101 176 001

Want to dial in from a phone?

Dial one of the following numbers:
+1.312.216.0325 (US (Chicago))
+1.408.740.7256 (US (San Jose))
+1.866.226.4650 (US Toll Free)
(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?
Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

Thanks again,

Hal

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

[Finkel, Hal J. via llvm-dev]

Hi, everyone,

A quick reminder: This call will start in approximately four hours. See below for how to join. On our current agenda:

Agenda

• Full restrict patch

• Observation and clarification

• Issues encountered

• Speed up in intersection code - O(nlog(n))

• Calling Verifier after LoopVectorize pass?

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

---

From: llvm-dev <llvm-dev...@lists.llvm.org> on behalf of Hal Finkel via llvm-dev <llvm...@lists.llvm.org>
Sent: Friday, June 26, 2020 9:48 AM

To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>
Cc: llvm...@lists.llvm.org <llvm...@lists.llvm.org>; Doerfert, Johannes <jdoe...@anl.gov>

Subject: Re: [llvm-dev] LLVM Alias Analysis Technical Call - New Doodle Poll

 

Thanks, everyone. It looks like we do have a time that works for almost everyone.

Let's plan to meet on Tuesday, July 14th @ 12-1 central time / 10-11 pacific time / 6-7pm in London, and at that time on Tuesday every four weeks.

Please use the Google doc linked below to add agenda items for the next call (or, if you cannot access a Google doc, send me a note and I'll add them for you).

https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

Meeting URL
https://bluejeans.com/101176001?src=join_info

Meeting ID
101 176 001

Want to dial in from a phone?

Dial one of the following numbers:
+1.312.216.0325 (US (Chicago))
+1.408.740.7256 (US (San Jose))
+1.866.226.4650 (US Toll Free)
(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?
Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

Thanks again,

Hal

[Finkel, Hal J. via llvm-dev]

A quick reminder: We'll have this month's call starting in about 1.25 hours.

Our agenda is:

Agenda

• [Tarique] Discussion on Jeroen’s idea on “Using full restrict to map sets of variables to a universe” in the context of Fortran aliasing.

• [Jeroen] Discussion on what is missing/needed to go forward

• Any feedback on the base infrastructure ?

• Llvm-ir bitcode support

• Recent rebase

• Review plan

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

From: Finkel, Hal J. <hfi...@anl.gov>

Sent: Tuesday, July 14, 2020 8:09 AM
To: Jeroen Dobbelaere <Jeroen.D...@synopsys.com>; Alina Sbirlea <alina....@gmail.com>; Finkel, Hal J. <hfi...@anl.gov>

[Hal Finkel via llvm-dev]

To supplement my reminder below, the notes document and call-in information are:

https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

Meeting URL
https://bluejeans.com/101176001?src=join_info

Meeting ID
101 176 001

Want to dial in from a phone?

Dial one of the following numbers:
+1.312.216.0325 (US (Chicago))
+1.408.740.7256 (US (San Jose))
+1.866.226.4650 (US Toll Free)
(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?
Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

Thanks again,

Hal

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Finkel, Hal J. via llvm-dev]

Hi, everyone,

A quick reminder, we'll have our next alias-analysis call in 30 minutes. See details on joining below.

Current Agenda:

• [Jeroen] Status of the Full Restrict Patches:

• Llvm-ir bitcode support has been added

• Rebased (to September 7, 2020) and updated patches have been published

• I did not get any objections on my request about the high level approach

• Proposal: start actively reviewing the changes, starting with the first 5 or 6 patches

the notes document and call-in information are:

https://docs.google.com/document/d/1ybwEKDVtIbhIhK50qYtwKsL50K-NvB6LfuBsfepBZ9Y/edit?usp=sharing

Meeting URL
https://bluejeans.com/101176001?src=join_info

Meeting ID
101 176 001

Want to dial in from a phone?

Dial one of the following numbers:
+1.312.216.0325 (US (Chicago))
+1.408.740.7256 (US (San Jose))
+1.866.226.4650 (US Toll Free)
(see all numbers - https://www.bluejeans.com/premium-numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?
Dial: bjn.vc or 199.48.152.152 and enter your meeting ID & passcode

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory