Full restrict support - status update

Project Infrastructure LLVM Dev List Archives
21

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
tislam@ca.ibm.com (905) 413-3190

graycol.gif"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

22

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
tislam@ca.ibm.com (905) 413-3190

graycol.gifTarique 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

23

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

24

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:

25

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

26

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

27

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).

Meeting URL
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 - ) 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

28

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

29

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

30

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

31

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