llvm dev - May 2019 - Delinearization validity checks in DependenceAnalysis

[CC bollu, mferguson, shil]

Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <
bmahjour at ca.ibm.com>:
> Thanks David and Michael for the clarification.
>
> I think I understand the rational behind those checks in delinearization
> now.
>
> > Some other languages have stronger guarantees about their array
> dimensions accesses being in range. But this being a flat C array, there is
> nothing out-of-bounds going on.
>
> Hmm...perhaps some information about these guarantees can come from the IR
> that the front-ends produce. I'm wondering if the 'inrange'
keyword (or
> maybe a new keyword) can be used for this purpose?
>
If the source is C/C++, the inrange keyword cannot be used because of the
language's semantics (see below).

Also, GetElementPtr will always only work with constant-sized array. A
student from last year's GSoC (CC'd) is working on such an extension
(with
intended use by Chapel).

I had a discussion about this syntax with some C standard experts and
there
> seems to be disagreements on whether an out-of-bound access with respect to
> an individual dimension is defined behaviour or not. I do not mean to start
> that discussion here, especially because there may be code in the field
> relying on certain interpretation of the standard, but just want to mention
> that option-control maybe a good way to deal with complications like this.
>
For clarification: In C, subscripts themselves have no semantics, they are
defined as syntactic sugar:

C18, 6.5.2.1,  §2
> The definition of the subscript operator[] is that E1[E2] is identical to(
*((E1)+(E2)))

Using arithmetic properties, &A[1][0] == (char*)A + 2 == &A[0][2] (for
an
array declared "*char* A[2][2]"). The indirection operator (*) is only
undefined if it yields to an access to an invalid address (C18, note 104).

Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190524/79ba0fd6/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190524/79ba0fd6/attachment-0001.gif>

On Fri, May 24, 2019 at 3:55 PM Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> [CC bollu, mferguson, shil]
>
> Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <
> bmahjour at ca.ibm.com>:
>
>> Thanks David and Michael for the clarification.
>>
>> I think I understand the rational behind those checks in
delinearization
>> now.
>>
>> > Some other languages have stronger guarantees about their array
>> dimensions accesses being in range. But this being a flat C array,
there is
>> nothing out-of-bounds going on.
>>
>> Hmm...perhaps some information about these guarantees can come from the
>> IR that the front-ends produce. I'm wondering if the
'inrange' keyword (or
>> maybe a new keyword) can be used for this purpose?
>>
>
> If the source is C/C++, the inrange keyword cannot be used because of the
> language's semantics (see below).
>
> Also, GetElementPtr will always only work with constant-sized array. A
> student from last year's GSoC (CC'd) is working on such an
extension (with
> intended use by Chapel).
>
> I had a discussion about this syntax with some C standard experts and
>> there seems to be disagreements on whether an out-of-bound access with
>> respect to an individual dimension is defined behaviour or not. I do
not
>> mean to start that discussion here, especially because there may be
code in
>> the field relying on certain interpretation of the standard, but just
want
>> to mention that option-control maybe a good way to deal with
complications
>> like this.
>>
>
> For clarification: In C, subscripts themselves have no semantics, they are
> defined as syntactic sugar:
>
> C18, 6.5.2.1,  §2
> > The definition of the subscript operator[] is that E1[E2] is identical
> to(*((E1)+(E2)))
>
> Using arithmetic properties, &A[1][0] == (char*)A + 2 == &A[0][2]
(for an
> array declared "*char* A[2][2]"). The indirection operator (*) is
only
> undefined if it yields to an access to an invalid address (C18, note 104).
>
Yes, the addresses are equal, but you make a point of talking about the
indirection operator.
Subclause 6.5.6 says: If the result points one past the last element of the
array object, it shall not be used as the operand of a unary * operator
that is evaluated.

&A[0][2] produces a result that points one past the last element of the
array A[0].

>
> Michael
>
> _______________________________________________
> 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/20190524/b56bc87e/attachment.html>

Hello,

After Sahil's GSoC 2018 project on integrating Chapel into Polly
<http://pollylabs.org/gsoc2018/Compiling-Chapel-with-Polly-and-LLVM.html>,
and running into similar issues with delinearization multiple times before,
we began drafting up an RFC to introduce these kinds of
"multidimensional accesses" directly into LLVM to lower languages such
as
Fortran which have these "multi-dimensional" semantics.

The RFC is still work-in-progress, but feedback would be appreciated. We're
trying to work out some of the rough edges out before posting it.

Thanks,
~Siddharth.


On Sat, May 25, 2019 at 12:31 AM Hubert Tong via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Fri, May 24, 2019 at 3:55 PM Michael Kruse via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> [CC bollu, mferguson, shil]
>>
>> Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <
>> bmahjour at ca.ibm.com>:
>>
>>> Thanks David and Michael for the clarification.
>>>
>>> I think I understand the rational behind those checks in
delinearization
>>> now.
>>>
>>> > Some other languages have stronger guarantees about their
array
>>> dimensions accesses being in range. But this being a flat C array,
there is
>>> nothing out-of-bounds going on.
>>>
>>> Hmm...perhaps some information about these guarantees can come from
the
>>> IR that the front-ends produce. I'm wondering if the
'inrange' keyword (or
>>> maybe a new keyword) can be used for this purpose?
>>>
>>
>> If the source is C/C++, the inrange keyword cannot be used because of
the
>> language's semantics (see below).
>>
>> Also, GetElementPtr will always only work with constant-sized array. A
>> student from last year's GSoC (CC'd) is working on such an
extension (with
>> intended use by Chapel).
>>
>> I had a discussion about this syntax with some C standard experts and
>>> there seems to be disagreements on whether an out-of-bound access
with
>>> respect to an individual dimension is defined behaviour or not. I
do not
>>> mean to start that discussion here, especially because there may be
code in
>>> the field relying on certain interpretation of the standard, but
just want
>>> to mention that option-control maybe a good way to deal with
complications
>>> like this.
>>>
>>
>> For clarification: In C, subscripts themselves have no semantics, they
>> are defined as syntactic sugar:
>>
>> C18, 6.5.2.1,  §2
>> > The definition of the subscript operator[] is that E1[E2] is
identical
>> to(*((E1)+(E2)))
>>
>> Using arithmetic properties, &A[1][0] == (char*)A + 2 ==
&A[0][2] (for an
>> array declared "*char* A[2][2]"). The indirection operator
(*) is only
>> undefined if it yields to an access to an invalid address (C18, note
104).
>>
> Yes, the addresses are equal, but you make a point of talking about the
> indirection operator.
> Subclause 6.5.6 says: If the result points one past the last element of
> the array object, it shall not be used as the operand of a unary * operator
> that is evaluated.
>
> &A[0][2] produces a result that points one past the last element of the
> array A[0].
>
>
>>
>> Michael
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
> _______________________________________________
> 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/20190529/764a08ae/attachment.html>