[llvm-dev] Delinearization validity checks in DependenceAnalysis

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev

Hi all,

I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
In order for this analysis to produce accurate dependence vectors for multi-dimensional arrays in nested loops, it needs to "delinearize" array element accesses to recover the subscripts in each dimension of the array. I believe that the current implementation of delinearization is based on this paper: http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf.

This paper describes how to delinearize the subscripts, and as a last step it requires certain conditions to be met in order to validate that the delinearized indexes are correct. The `tryDelinearize` function in `DependenceAnalysis.cpp` appears to be checking for cases where these conditions can be validated *at compile time*:

```
// Statically check that the array bounds are in-range. The first subscript we
// don't have a size for and it cannot overflow into another subscript, so is
// always safe. The others need to be 0 <= subscript[i] < bound, for both src
// and dst.
// FIXME: It may be better to record these sizes and add them as constraints
// to the dependency checks.
for (int i = 1; i < size; ++i) {
if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
return false;

if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
return false;

if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
return false;

if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
return false;
}
```

The problem is that in a lot of cases these conditions cannot be proven statically, even though the delinearized indexes are in fact correct. For example consider this simple loop:

```
void foo(int n, int m, int a[][m]) {
for (int i = 0; i < n-1; ++i)
for (int j = 2; j < m; ++j) {
a[i][j] = a[i+1][j-2];
}
}

clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -simplifycfg test.ll -S -o test.simp.ll
opt test.simp.ll -analyze -da
```

will produce:

```
da analyze - none!
da analyze - anti [* *|<]!
da analyze - output [* *]!
```

If the validity checks were not present, the result would be much more accurate dependence vector with accurate dependence distances:

```
da analyze - none!
da analyze - consistent anti [1 -2]!
da analyze - none!
```

In my experience the static validity checks tend to fail in many common cases (involving loops with symbolic bounds). Sometimes this happens because SCEV is not able to simplify the expressions due to presence of type casts and sign/zero extensions, but other times the conditions are just not computable at compile-time.

So far I haven't been able to come up with an example where the validity checks in the current implementation legitimately catch a case of invalid delinearization. I've also disabled these checks and run some tests without finding any failures (other than improvements in the dependence analysis LIT tests).

I also had a quick look at Polly which benefits from delinearization. From what I saw, a much more optimistic approach is taken where the validity checks seem to be avoided.

My questions are:
1. Does anyone have more information about why these validity checks are necessary in the current implementation, perhaps with some examples showing an incorrect delinearization that's possible without those checks?
2. Are there any concerns with putting these validity checks under an option so that we can more easily disable them and experiment? This could also help us improve LIT tests, since some of them have been pessimised to compensate for DA's inability to delinearize, and could fail to catch regressions as a result of bad changes to the data dependence analysis.

Looking forward to your help on this.

Thank you,

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336



_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
Hello

Interestingly, the example you provide works for me so long as either it's a 32bit target, or the array bounds (n and m) are changed to unsigned.

For a bit of history, DA used to have a different delinearisation method based on geps, but it was known to be invalid in same cases and was eventually removed. There was no delinearisation for a while until these checks were fixed, enough to be correct, but not as powerful as they could be. I believe Pollys delinearisation is much more powerful, and can version loops with runtime conditions.

IIRC, the checks are there for cases like this:
void foo(unsigned n, unsigned m, int *a) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      a[i*m + j] = a[i*m + j+2];
    }
}

The "j-2" can underflow into the previous i iterations space. So the distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is perfectly valid in C (I think for the int a[][m] case too).

See this comment for why they were needed and perhaps a better way to fix it:
https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274

Any improvements to the delinearisation code would be most welcome.
Dave




From: llvm-dev <[hidden email]> on behalf of Bardia Mahjour via llvm-dev <[hidden email]>
Sent: 13 May 2019 14:48
To: [hidden email]
Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
 
Hi all,

I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
In order for this analysis to produce accurate dependence vectors for multi-dimensional arrays in nested loops, it needs to "delinearize" array element accesses to recover the subscripts in each dimension of the array. I believe that the current implementation of delinearization is based on this paper: http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf.

This paper describes how to delinearize the subscripts, and as a last step it requires certain conditions to be met in order to validate that the delinearized indexes are correct. The `tryDelinearize` function in `DependenceAnalysis.cpp` appears to be checking for cases where these conditions can be validated *at compile time*:

```
// Statically check that the array bounds are in-range. The first subscript we
// don't have a size for and it cannot overflow into another subscript, so is
// always safe. The others need to be 0 <= subscript[i] < bound, for both src
// and dst.
// FIXME: It may be better to record these sizes and add them as constraints
// to the dependency checks.
for (int i = 1; i < size; ++i) {
if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
return false;

if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
return false;

if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
return false;

if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
return false;
}
```

The problem is that in a lot of cases these conditions cannot be proven statically, even though the delinearized indexes are in fact correct. For example consider this simple loop:

```
void foo(int n, int m, int a[][m]) {
for (int i = 0; i < n-1; ++i)
for (int j = 2; j < m; ++j) {
a[i][j] = a[i+1][j-2];
}
}

clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -simplifycfg test.ll -S -o test.simp.ll
opt test.simp.ll -analyze -da
```

will produce:

```
da analyze - none!
da analyze - anti [* *|<]!
da analyze - output [* *]!
```

If the validity checks were not present, the result would be much more accurate dependence vector with accurate dependence distances:

```
da analyze - none!
da analyze - consistent anti [1 -2]!
da analyze - none!
```

In my experience the static validity checks tend to fail in many common cases (involving loops with symbolic bounds). Sometimes this happens because SCEV is not able to simplify the expressions due to presence of type casts and sign/zero extensions, but other times the conditions are just not computable at compile-time.

So far I haven't been able to come up with an example where the validity checks in the current implementation legitimately catch a case of invalid delinearization. I've also disabled these checks and run some tests without finding any failures (other than improvements in the dependence analysis LIT tests).

I also had a quick look at Polly which benefits from delinearization. From what I saw, a much more optimistic approach is taken where the validity checks seem to be avoided.

My questions are:
1. Does anyone have more information about why these validity checks are necessary in the current implementation, perhaps with some examples showing an incorrect delinearization that's possible without those checks?
2. Are there any concerns with putting these validity checks under an option so that we can more easily disable them and experiment? This could also help us improve LIT tests, since some of them have been pessimised to compensate for DA's inability to delinearize, and could fail to catch regressions as a result of bad changes to the data dependence analysis.

Looking forward to your help on this.

Thank you,

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev

Hi David,

Thank you very much for your response.

I also get correct results for my example (for a 64-bit target) if the upper bounds are changed to unsigned. The reason is simply because clang zero-extends `m` for address calculations but sign-extends it for the loop upper bound. This prevents SCEV from canceling out the 'm' term from the difference expression that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to i64))<nsw>)`. While we cannot reduce expressions of this form in general, it does pose a sever limitation for the vast majority of cases where the loop upper bound is non-negative.

Regarding your example, I'm not sure I fully understand the concern and I would appreciate it if you could clarify that for me. My understanding is that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as provided, has an out-of-bound access to start with. To avoid this out-bound access one would need to change the upper bound of the j-loop to be 'm-2'. Interestingly, if we do that, the current validity checks start to pass and we get [0 2] as the dependence vector. Here's a slightly modified version of your example that I tried:

```
typedef unsigned long long TT;
void foo(TT n, TT m, int *a) {
for (TT i = 0; i < n; ++i)
for (TT j = 0; j < m-2; ++j) {
a[i*m + j] = a[i*m + j+2];
}
}
```

If the concern is that the actual intended shape of the array may have been something other than a[n][m], and that we are indexing it such that the accesses are in-bound with respect to the memory of the whole array but not with respect to individual dimensions, then I'm not sure we can reason about *any* delinearization statically (except for the limited cases where the bounds are compile-time known).

Am I misunderstanding the issue?

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336



Inactive hide details for David Green ---2019/05/14 02:50:27 PM---Hello Interestingly, the example you provide works for me so David Green ---2019/05/14 02:50:27 PM---Hello Interestingly, the example you provide works for me so long as either it's a 32bit target, or

From: David Green <[hidden email]>
To: "[hidden email]" <[hidden email]>, Bardia Mahjour <[hidden email]>
Cc: nd <[hidden email]>
Date: 2019/05/14 02:50 PM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis





Hello

Interestingly, the example you provide works for me so long as either it's a 32bit target, or the array bounds (n and m) are changed to unsigned.

For a bit of history, DA used to have a different delinearisation method based on geps, but it was known to be invalid in same cases and was eventually removed. There was no delinearisation for a while until these checks were fixed, enough to be correct, but not as powerful as they could be. I believe Pollys delinearisation is much more powerful, and can version loops with runtime conditions.

IIRC, the checks are there for cases like this:
void foo(unsigned n, unsigned m, int *a) {
 for (int i = 0; i < n; ++i)
   for (int j = 0; j < m; ++j) {
     a[i*m + j] = a[i*m + j+2];
   }
}

The "j-2" can underflow into the previous i iterations space. So the distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is perfectly valid in C (I think for the int a[][m] case too).

See this comment for why they were needed and perhaps a better way to fix it:
https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274

Any improvements to the delinearisation code would be most welcome.
Dave




From: llvm-dev <[hidden email]> on behalf of Bardia Mahjour via llvm-dev <[hidden email]>
Sent: 13 May 2019 14:48
To: [hidden email]
Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
 
Hi all,

I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
In order for this analysis to produce accurate dependence vectors for multi-dimensional arrays in nested loops, it needs to "delinearize" array element accesses to recover the subscripts in each dimension of the array. I believe that the current implementation of delinearization is based on this paper:
http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf.

This paper describes how to delinearize the subscripts, and as a last step it requires certain conditions to be met in order to validate that the delinearized indexes are correct. The `tryDelinearize` function in `DependenceAnalysis.cpp` appears to be checking for cases where these conditions can be validated *at compile time*:

```
// Statically check that the array bounds are in-range. The first subscript we
// don't have a size for and it cannot overflow into another subscript, so is
// always safe. The others need to be 0 <= subscript[i] < bound, for both src
// and dst.
// FIXME: It may be better to record these sizes and add them as constraints
// to the dependency checks.
for (int i = 1; i < size; ++i) {
if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
return false;

if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
return false;

if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
return false;

if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
return false;
}
```

The problem is that in a lot of cases these conditions cannot be proven statically, even though the delinearized indexes are in fact correct. For example consider this simple loop:

```
void foo(int n, int m, int a[][m]) {
for (int i = 0; i < n-1; ++i)
for (int j = 2; j < m; ++j) {
a[i][j] = a[i+1][j-2];
}
}

clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -simplifycfg test.ll -S -o test.simp.ll
opt test.simp.ll -analyze -da
```

will produce:

```
da analyze - none!
da analyze - anti [* *|<]!
da analyze - output [* *]!
```

If the validity checks were not present, the result would be much more accurate dependence vector with accurate dependence distances:

```
da analyze - none!
da analyze - consistent anti [1 -2]!
da analyze - none!
```

In my experience the static validity checks tend to fail in many common cases (involving loops with symbolic bounds). Sometimes this happens because SCEV is not able to simplify the expressions due to presence of type casts and sign/zero extensions, but other times the conditions are just not computable at compile-time.

So far I haven't been able to come up with an example where the validity checks in the current implementation legitimately catch a case of invalid delinearization. I've also disabled these checks and run some tests without finding any failures (other than improvements in the dependence analysis LIT tests).

I also had a quick look at Polly which benefits from delinearization. From what I saw, a much more optimistic approach is taken where the validity checks seem to be avoided.

My questions are:
1. Does anyone have more information about why these validity checks are necessary in the current implementation, perhaps with some examples showing an incorrect delinearization that's possible without those checks?
2. Are there any concerns with putting these validity checks under an option so that we can more easily disable them and experiment? This could also help us improve LIT tests, since some of them have been pessimised to compensate for DA's inability to delinearize, and could fail to catch regressions as a result of bad changes to the data dependence analysis.

Looking forward to your help on this.

Thank you,

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336







_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
On 05/15, Bardia Mahjour via llvm-dev wrote:

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```
>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).
In the example above, it works statically, doesn't it? Generally, if
loop bounds and access functions are "in-sync", it should work statically.
It does not if you do use different/multiple unknown values
(parameters) or confuse Scalar Evolution (different types).

> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To: "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc: nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
> https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_llvm_llvm-2Dproject_commit_d143c65de3c884d09197da279d2f04f094efaf15-23diff-2D57473b376037dd3637516348b9b02556L3274&d=DwIFAw&c=jf_iaSHvJObTbx-siA1ZOg&r=aihobyOnVzXW7OPSK1-NiSYQkq7oP3ZSUVc4BemvrVo&m=46eKxI_sFjjeBzn7X-OLXSEUwHN-HVCD16TF9OuyIqc&s=adPvJDhPtFMlaTWihZmvWjXqFUFHDnzcV84oaDGlryM&e=
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
> https://urldefense.proofpoint.com/v2/url?u=http-3A__web.cse.ohio-2Dstate.edu_-7Epouchet.2_doc_ics-2Darticle.15a.pdf&d=DwIFAw&c=jf_iaSHvJObTbx-siA1ZOg&r=aihobyOnVzXW7OPSK1-NiSYQkq7oP3ZSUVc4BemvrVo&m=46eKxI_sFjjeBzn7X-OLXSEUwHN-HVCD16TF9OuyIqc&s=nraVp9R56UlYi0We27kmGSjZGnM296r0HFpbRR62Fzs&e=
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>


> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

signature.asc (235 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev

Hi Johannes,

> In the example above, it works statically, doesn't it?

Yes, that example works statically, and the delinearization appears correct to me. What I'm looking for though, is an example showing that delinearization produces invalid subscripts that are rightfully caught by the validity checks.

> if loop bounds and access functions are "in-sync", it should work statically. It does not if you do use different/multiple unknown values (parameters) or confuse Scalar Evolution (different types).

In practice, many (if not most) loops will have some sort of type-conversion on 64-bit targets which prevent SCEV simplifications that are necessary to prove the validity conditions at compile-time. That's a big problem for loop optimizations.

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336



Inactive hide details for "Doerfert, Johannes" ---2019/05/15 03:21:23 PM---On 05/15, Bardia Mahjour via llvm-dev wrote: > Regar"Doerfert, Johannes" ---2019/05/15 03:21:23 PM---On 05/15, Bardia Mahjour via llvm-dev wrote: > Regarding your example, I'm not sure I fully understa

From: "Doerfert, Johannes" <[hidden email]>
To: Bardia Mahjour <[hidden email]>
Cc: David Green <[hidden email]>, "[hidden email]" <[hidden email]>, nd <[hidden email]>
Date: 2019/05/15 03:21 PM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis





On 05/15, Bardia Mahjour via llvm-dev wrote:

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```
>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).

In the example above, it works statically, doesn't it? Generally, if
loop bounds and access functions are "in-sync", it should work statically.
It does not if you do use different/multiple unknown values
(parameters) or confuse Scalar Evolution (different types).

> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To: "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc: nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
>
https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
>
http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>



> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]
[attachment "signature.asc" deleted by Bardia Mahjour/Toronto/IBM]




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
In reply to this post by Amara Emerson via llvm-dev
Hello

Under the proviso that it's been a while since I looked into any of these things...

On 05/15, Bardia Mahjour via llvm-dev wrote:
> I also get correct results for my example (for a 64-bit target) if the upper
> bounds are changed to unsigned. The reason is simply because clang zero-extends
> `m` for address calculations but sign-extends it for the loop upper bound. This
> prevents SCEV from canceling out the 'm' term from the difference expression
> that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)`. While we cannot reduce expressions of this form in general, it
> does pose a sever limitation for the vast majority of cases where the loop
> upper bound is non-negative.
>

There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```
Sure, but is wouldn't be invalid from C to use the "for (TT j = 0; j < m; ++j)" bound, so long as the size of the object passed through to "a" was large enough that it didn't overflow. We don't have enough information to prove this won't happen, so unfortunately we need to be a conservative.

So this loop:

void test(int * A, signed N, int M)
{
    for(int i = 1; i < N; i+=1) {
        for(int j = 0; j < M; j+=1) {
            A[i*M + j] = 2;
            A[i*M + j - 1] = 4;
        }
    }
}

Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).
>
> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To:   "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc:   nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject:      [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
>  https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_llvm_llvm-2Dproject_commit_d143c65de3c884d09197da279d2f04f094efaf15-23diff-2D57473b376037dd3637516348b9b02556L3274&d=DwIFAw&c=jf_iaSHvJObTbx-siA1ZOg&r=aihobyOnVzXW7OPSK1-NiSYQkq7oP3ZSUVc4BemvrVo&m=46eKxI_sFjjeBzn7X-OLXSEUwHN-HVCD16TF9OuyIqc&s=adPvJDhPtFMlaTWihZmvWjXqFUFHDnzcV84oaDGlryM&e=
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
>  https://urldefense.proofpoint.com/v2/url?u=http-3A__web.cse.ohio-2Dstate.edu_-7Epouchet.2_doc_ics-2Darticle.15a.pdf&d=DwIFAw&c=jf_iaSHvJObTbx-siA1ZOg&r=aihobyOnVzXW7OPSK1-NiSYQkq7oP3ZSUVc4BemvrVo&m=46eKxI_sFjjeBzn7X-OLXSEUwHN-HVCD16TF9OuyIqc&s=nraVp9R56UlYi0We27kmGSjZGnM296r0HFpbRR62Fzs&e=
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>


> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]
   
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

da3.c (720 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
In reply to this post by Amara Emerson via llvm-dev
Am Mo., 13. Mai 2019 um 08:49 Uhr schrieb Bardia Mahjour via llvm-dev
<[hidden email]>:
> I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for multi-dimensional arrays in nested loops, it needs to "delinearize" array element accesses to recover the subscripts in each dimension of the array. I believe that the current implementation of delinearization is based on this paper: http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf.

> 1. Does anyone have more information about why these validity checks are necessary in the current implementation, perhaps with some examples showing an incorrect delinearization that's possible without those checks?

Think of an array A[2][2] and two accesses:

A[1][0] = value;
use(A[0][2]);

The subscript of the second is out-of-range and will be evaluated to
the same address as A[1][0]. A dependence-analysis that assumes that
different subscripts means different addresses will not catch the
dependence between the two statements.

Polly implements the FIXME: It assumes that all accesses are
in-bounds, but will execute the original code if this is not the case.
A runtime check testing for the condition decides whether the
optimized (whose assumptions turned out to be wrong) or original code
is going to be executed.


> 2. Are there any concerns with putting these validity checks under an option so that we can more easily disable them and experiment? This could also help us improve LIT tests, since some of them have been pessimised to compensate for DA's inability to delinearize, and could fail to catch regressions as a result of bad changes to the data dependence analysis.

You can upload a patch for this and I don't see issues as long as by
default the safety checks are enabled. However, if you just want to
evaluate, why not just implement it in your local branch?


Michael
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
In reply to this post by Amara Emerson via llvm-dev

Hi David,

Sorry for my delayed response.

> There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

It looks like SCEV already tries to simplify identically sign and zero extended terms in an expression. However expressions that contain mix of sex and zex like this: `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)`
cannot be simplified unless we can assume that %m is never negative. Although in practice %m will not be negative in most cases, the compiler cannot prove that at compile-time so I don't think we can "improve" SCEV to catch these cases.


> So this loop:


> void test(int * A, signed N, int M)
> {
>    for(int i = 1; i < N; i+=1) {
>        for(int j = 0; j < M; j+=1) {
>            A[i*M + j] = 2;
>            A[i*M + j - 1] = 4;
>        }
>    }
> }
> Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

Without the delinearization validity checks, the access functions A[i*M + j] and A[i*M + j - 1] would get delinearized as follows:

SrcSCEV = {{((4 * %M) + %A)<nsw>,+,(4 * %M)}<%for.body>,+,4}<%for.body4>
DstSCEV = {{(-4 + (4 * %M) + %A),+,(4 * %M)}<%for.body>,+,4}<%for.body4>

SrcSubscripts: {1,+,1}<%for.body>{0,+,1}<%for.body4>
DstSubscripts: {1,+,1}<%for.body>{-1,+,1}<%for.body4> delinearized
subscript 0
src = {1,+,1}<%for.body>
dst = {1,+,1}<%for.body>
class = 1
loops = {1}
subscript 1
src = {0,+,1}<%for.body4>
dst = {-1,+,1}<%for.body4>
class = 1
loops = {2}
Separable = {0 1}
Coupled = {}

Why is this not a valid delinearization? The fact that the {-1,+,1} subscript goes out of bounds with respect to the second dimension is a problem that originates from the user code (and can be fixed by initializing j to 1 instead of 0). It is not a problem introduced by delinearization. Nevertheless delinearization validity checks fail because they find that the subscript in the second dimension could be negative and think that we didn't delinearize correctly.

Do you have any objections to adding an option to disable these checks, at least for the test cases where we know the delinearization would be correct, but cannot be guaranteed by the compiler?

Do we still need the validity step in the delinearization algorithm, if we could guarantee that the array size parameters collected (guessed) in the first step of the algorithm are in fact the correct array dimensions?



Inactive hide details for David Green ---2019/05/16 03:50:55 PM---Hello Under the proviso that it's been a while since I lookedDavid Green ---2019/05/16 03:50:55 PM---Hello Under the proviso that it's been a while since I looked into any of these things...

From: David Green <[hidden email]>
To: "Doerfert, Johannes" <[hidden email]>, Bardia Mahjour <[hidden email]>
Cc: "[hidden email]" <[hidden email]>, nd <[hidden email]>
Date: 2019/05/16 03:50 PM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis




Hello

Under the proviso that it's been a while since I looked into any of these things...

On 05/15, Bardia Mahjour via llvm-dev wrote:
> I also get correct results for my example (for a 64-bit target) if the upper
> bounds are changed to unsigned. The reason is simply because clang zero-extends
> `m` for address calculations but sign-extends it for the loop upper bound. This
> prevents SCEV from canceling out the 'm' term from the difference expression
> that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)`. While we cannot reduce expressions of this form in general, it
> does pose a sever limitation for the vast majority of cases where the loop
> upper bound is non-negative.
>

There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```

Sure, but is wouldn't be invalid from C to use the "for (TT j = 0; j < m; ++j)" bound, so long as the size of the object passed through to "a" was large enough that it didn't overflow. We don't have enough information to prove this won't happen, so unfortunately we need to be a conservative.

So this loop:

void test(int * A, signed N, int M)
{
   for(int i = 1; i < N; i+=1) {
       for(int j = 0; j < M; j+=1) {
           A[i*M + j] = 2;
           A[i*M + j - 1] = 4;
       }
   }
}

Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).
>
> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To:   "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc:   nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject:      [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
>  
https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
>  
http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>



> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]
   [attachment "da3.c" deleted by Bardia Mahjour/Toronto/IBM]




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
Hello

Yes, I agree that the SCEV cannot be simplified.  Is my understanding correct that it is passed to a function like "isKnownNegative"? Which could still be able to prove is always true.

The delinearisation may be valid, depending on exactly how you define delinearisation (under what conditions it should be giving results). It would be invalid for DA to return a dependency of [0 >] though. The code is perfectly valid from the C or llvm-ir specifications and we can't change the meaning of it just because we don't like it :)  One of the observable effects of the program is the last values written into A, and unroll-and-jam will reorder the stores if it does not understand it is unsafe, leading to different output. i.e a mis-compile. C isn't very friendly to us here, and llvm is linearising the access. 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.

I'm not sure about just disabling the checks, at least without some other way of keeping the results correct. Having a debug option probably wouldn't hurt, but I'm not sure about turning it on for tests if it reduces the test coverage. Other people may have different opinions though.

Any improvements to DA in general would be excellent, and it has a lot of room for improvement.
Dave





From: Bardia Mahjour
Sent: 22 May 2019 18:09
To: David Green
Cc: Doerfert, Johannes; [hidden email]; nd
Subject: Re: Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis
 

Hi David,

Sorry for my delayed response.

> There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

It looks like SCEV already tries to simplify identically sign and zero extended terms in an expression. However expressions that contain mix of sex and zex like this: `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)` cannot be simplified unless we can assume that %m is never negative. Although in practice %m will not be negative in most cases, the compiler cannot prove that at compile-time so I don't think we can "improve" SCEV to catch these cases.


> So this loop:
> void test(int * A, signed N, int M)
> {
>    for(int i = 1; i < N; i+=1) {
>        for(int j = 0; j < M; j+=1) {
>            A[i*M + j] = 2;
>            A[i*M + j - 1] = 4;
>        }
>    }
> }
> Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.
Without the delinearization validity checks, the access functions A[i*M + j] and A[i*M + j - 1] would get delinearized as follows:

SrcSCEV = {{((4 * %M) + %A)<nsw>,+,(4 * %M)}<%for.body>,+,4}<%for.body4>
DstSCEV = {{(-4 + (4 * %M) + %A),+,(4 * %M)}<%for.body>,+,4}<%for.body4>

SrcSubscripts: {1,+,1}<%for.body>{0,+,1}<%for.body4>
DstSubscripts: {1,+,1}<%for.body>{-1,+,1}<%for.body4> delinearized
subscript 0
src = {1,+,1}<%for.body>
dst = {1,+,1}<%for.body>
class = 1
loops = {1}
subscript 1
src = {0,+,1}<%for.body4>
dst = {-1,+,1}<%for.body4>
class = 1
loops = {2}
Separable = {0 1}
Coupled = {}

Why is this not a valid delinearization? The fact that the {-1,+,1} subscript goes out of bounds with respect to the second dimension is a problem that originates from the user code (and can be fixed by initializing j to 1 instead of 0). It is not a problem introduced by delinearization. Nevertheless delinearization validity checks fail because they find that the subscript in the second dimension could be negative and think that we didn't delinearize correctly.

Do you have any objections to adding an option to disable these checks, at least for the test cases where we know the delinearization would be correct, but cannot be guaranteed by the compiler?

Do we still need the validity step in the delinearization algorithm, if we could guarantee that the array size parameters collected (guessed) in the first step of the algorithm are in fact the correct array dimensions?



David Green ---2019/05/16 03:50:55 PM---Hello Under the proviso that it's been a while since I looked into any of these things...

From: David Green <[hidden email]>
To: "Doerfert, Johannes" <[hidden email]>, Bardia Mahjour <[hidden email]>
Cc: "[hidden email]" <[hidden email]>, nd <[hidden email]>
Date: 2019/05/16 03:50 PM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis





Hello

Under the proviso that it's been a while since I looked into any of these things...

On 05/15, Bardia Mahjour via llvm-dev wrote:
> I also get correct results for my example (for a 64-bit target) if the upper
> bounds are changed to unsigned. The reason is simply because clang zero-extends
> `m` for address calculations but sign-extends it for the loop upper bound. This
> prevents SCEV from canceling out the 'm' term from the difference expression
> that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)`. While we cannot reduce expressions of this form in general, it
> does pose a sever limitation for the vast majority of cases where the loop
> upper bound is non-negative.
>

There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```
Sure, but is wouldn't be invalid from C to use the "for (TT j = 0; j < m; ++j)" bound, so long as the size of the object passed through to "a" was large enough that it didn't overflow. We don't have enough information to prove this won't happen, so unfortunately we need to be a conservative.

So this loop:

void test(int * A, signed N, int M)
{
   for(int i = 1; i < N; i+=1) {
       for(int j = 0; j < M; j+=1) {
           A[i*M + j] = 2;
           A[i*M + j - 1] = 4;
       }
   }
}

Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).
>
> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To:   "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc:   nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject:      [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
>  https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
>  http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>


> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]
   [attachment "da3.c" deleted by Bardia Mahjour/Toronto/IBM]



_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

graycol.gif (144 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev

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?

> Think of an array A[2][2] and two accesses:
> A[1][0] = value;
> use(A[0][2]);
> The subscript of the second is out-of-range and will be evaluated to
> the same address as A[1][0]. A dependence-analysis that assumes that
> different subscripts means different addresses will not catch the
> dependence between the two statements.


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.

The debug option I had in mind would leave the checks in place by default. I do not intend to decrease the test coverage either. Hopefully the option can actually help us increase test coverage for cases that are currently failing to produce accurate dependence vectors due to the validity conditions being unknown at compile-time. I'll post a patch for review soon.

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336



Inactive hide details for David Green ---2019/05/22 06:01:31 PM---Hello Yes, I agree that the SCEV cannot be simplified.  Is myDavid Green ---2019/05/22 06:01:31 PM---Hello Yes, I agree that the SCEV cannot be simplified. Is my understanding correct that it is passe

From: David Green <[hidden email]>
To: Bardia Mahjour <[hidden email]>
Cc: "Doerfert, Johannes" <[hidden email]>, "[hidden email]" <[hidden email]>, nd <[hidden email]>
Date: 2019/05/22 06:01 PM
Subject: [EXTERNAL] Re: Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis





Hello

Yes, I agree that the SCEV cannot be simplified.  Is my understanding correct that it is passed to a function like "isKnownNegative"? Which could still be able to prove is always true.

The delinearisation may be valid, depending on exactly how you define delinearisation (under what conditions it should be giving results). It would be invalid for DA to return a dependency of [0 >] though. The code is perfectly valid from the C or llvm-ir specifications and we can't change the meaning of it just because we don't like it :)  One of the observable effects of the program is the last values written into A, and unroll-and-jam will reorder the stores if it does not understand it is unsafe, leading to different output. i.e a mis-compile. C isn't very friendly to us here, and llvm is linearising the access. 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.

I'm not sure about just disabling the checks, at least without some other way of keeping the results correct. Having a debug option probably wouldn't hurt, but I'm not sure about turning it on for tests if it reduces the test coverage. Other people may have different opinions though.

Any improvements to DA in general would be excellent, and it has a lot of room for improvement.
Dave





From: Bardia Mahjour
Sent: 22 May 2019 18:09
To: David Green
Cc: Doerfert, Johannes; [hidden email]; nd
Subject: Re: Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis
 

Hi David,

Sorry for my delayed response.

> There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

It looks like SCEV already tries to simplify identically sign and zero extended terms in an expression. However expressions that contain mix of sex and zex like this: `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)` cannot be simplified unless we can assume that %m is never negative. Although in practice %m will not be negative in most cases, the compiler cannot prove that at compile-time so I don't think we can "improve" SCEV to catch these cases.


> So this loop:
> void test(int * A, signed N, int M)
> {
>    for(int i = 1; i < N; i+=1) {
>        for(int j = 0; j < M; j+=1) {
>            A[i*M + j] = 2;
>            A[i*M + j - 1] = 4;
>        }
>    }
> }
> Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

Without the delinearization validity checks, the access functions A[i*M + j] and A[i*M + j - 1] would get delinearized as follows:

SrcSCEV = {{((4 * %M) + %A)<nsw>,+,(4 * %M)}<%for.body>,+,4}<%for.body4>
DstSCEV = {{(-4 + (4 * %M) + %A),+,(4 * %M)}<%for.body>,+,4}<%for.body4>

SrcSubscripts: {1,+,1}<%for.body>{0,+,1}<%for.body4>
DstSubscripts: {1,+,1}<%for.body>{-1,+,1}<%for.body4> delinearized
subscript 0
src = {1,+,1}<%for.body>
dst = {1,+,1}<%for.body>
class = 1
loops = {1}
subscript 1
src = {0,+,1}<%for.body4>
dst = {-1,+,1}<%for.body4>
class = 1
loops = {2}
Separable = {0 1}
Coupled = {}

Why is this not a valid delinearization? The fact that the {-1,+,1} subscript goes out of bounds with respect to the second dimension is a problem that originates from the user code (and can be fixed by initializing j to 1 instead of 0). It is not a problem introduced by delinearization. Nevertheless delinearization validity checks fail because they find that the subscript in the second dimension could be negative and think that we didn't delinearize correctly.

Do you have any objections to adding an option to disable these checks, at least for the test cases where we know the delinearization would be correct, but cannot be guaranteed by the compiler?

Do we still need the validity step in the delinearization algorithm, if we could guarantee that the array size parameters collected (guessed) in the first step of the algorithm are in fact the correct array dimensions?



David Green ---2019/05/16 03:50:55 PM---Hello Under the proviso that it's been a while since I looked into any of these things...

From: David Green <[hidden email]>
To: "Doerfert, Johannes" <[hidden email]>, Bardia Mahjour <[hidden email]>
Cc: "[hidden email]" <[hidden email]>, nd <[hidden email]>
Date: 2019/05/16 03:50 PM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis





Hello

Under the proviso that it's been a while since I looked into any of these things...

On 05/15, Bardia Mahjour via llvm-dev wrote:
> I also get correct results for my example (for a 64-bit target) if the upper
> bounds are changed to unsigned. The reason is simply because clang zero-extends
> `m` for address calculations but sign-extends it for the loop upper bound. This
> prevents SCEV from canceling out the 'm' term from the difference expression
> that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to
> i64))<nsw>)`. While we cannot reduce expressions of this form in general, it
> does pose a sever limitation for the vast majority of cases where the loop
> upper bound is non-negative.
>

There are already some function like isKnownPredicate that attempt to deal with some of this is DA. Can we extend the other for these cases? Perhaps with some extra information that we have that SCEV would in general not know, or do something extra that it would not compute. Or ideally can we just improve SCEV to get this right?

> Regarding your example, I'm not sure I fully understand the concern and I
> would appreciate it if you could clarify that for me. My understanding is
> that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as
> provided, has an out-of-bound access to start with. To avoid this out-bound
> access one would need to change the upper bound of the j-loop to be 'm-2'.
> Interestingly, if we do that, the current validity checks start to pass and
> we get [0 2] as the dependence vector. Here's a slightly modified version
> of your example that I tried:
>
> ```
> typedef unsigned long long TT;
> void foo(TT n, TT m, int *a) {
>   for (TT i = 0; i < n; ++i)
>     for (TT j = 0; j < m-2; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
> ```

Sure, but is wouldn't be invalid from C to use the "for (TT j = 0; j < m; ++j)" bound, so long as the size of the object passed through to "a" was large enough that it didn't overflow. We don't have enough information to prove this won't happen, so unfortunately we need to be a conservative.

So this loop:

void test(int * A, signed N, int M)
{
   for(int i = 1; i < N; i+=1) {
       for(int j = 0; j < M; j+=1) {
           A[i*M + j] = 2;
           A[i*M + j - 1] = 4;
       }
   }
}

Needs to not get the dependency vector [0 >], otherwise unroll and jam might think it was safe to reorder (unroll and jam) and miscompile the code.

>
> If the concern is that the actual intended shape of the array may have been
> something other than a[n][m], and that we are indexing it such that the
> accesses are in-bound with respect to the memory of the whole array but not
> with respect to individual dimensions, then I'm not sure we can reason
> about *any* delinearization statically (except for the limited cases where
> the bounds are compile-time known).
>
> Am I misunderstanding the issue?
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>
> From: David Green <[hidden email]>
> To:   "[hidden email]" <[hidden email]>, Bardia
>             Mahjour <[hidden email]>
> Cc:   nd <[hidden email]>
> Date: 2019/05/14 02:50 PM
> Subject:      [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in
>             DependenceAnalysis
>
>
>
> Hello
>
> Interestingly, the example you provide works for me so long as either it's
> a 32bit target, or the array bounds (n and m) are changed to unsigned.
>
> For a bit of history, DA used to have a different delinearisation method
> based on geps, but it was known to be invalid in same cases and was
> eventually removed. There was no delinearisation for a while until these
> checks were fixed, enough to be correct, but not as powerful as they could
> be. I believe Pollys delinearisation is much more powerful, and can version
> loops with runtime conditions.
>
> IIRC, the checks are there for cases like this:
> void foo(unsigned n, unsigned m, int *a) {
>   for (int i = 0; i < n; ++i)
>     for (int j = 0; j < m; ++j) {
>       a[i*m + j] = a[i*m + j+2];
>     }
> }
>
> The "j-2" can underflow into the previous i iterations space. So the
> distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is
> perfectly valid in C (I think for the int a[][m] case too).
>
> See this comment for why they were needed and perhaps a better way to fix
> it:
>  
https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274
>
>
> Any improvements to the delinearisation code would be most welcome.
> Dave
>
>
>
>
> From: llvm-dev <[hidden email]> on behalf of Bardia
> Mahjour via llvm-dev <[hidden email]>
> Sent: 13 May 2019 14:48
> To: [hidden email]
> Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis
>
> Hi all,
>
> I have been looking at the `DependenceAnalysis` pass in
> `llvm/include/llvm/Analysis/DependenceAnalysis.h`.
> In order for this analysis to produce accurate dependence vectors for
> multi-dimensional arrays in nested loops, it needs to "delinearize" array
> element accesses to recover the subscripts in each dimension of the array.
> I believe that the current implementation of delinearization is based on
> this paper:
>  
http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf
> .
>
> This paper describes how to delinearize the subscripts, and as a last step
> it requires certain conditions to be met in order to validate that the
> delinearized indexes are correct. The `tryDelinearize` function in
> `DependenceAnalysis.cpp` appears to be checking for cases where these
> conditions can be validated *at compile time*:
>
> ```
> // Statically check that the array bounds are in-range. The first subscript
> we
> // don't have a size for and it cannot overflow into another subscript, so
> is
> // always safe. The others need to be 0 <= subscript[i] < bound, for both
> src
> // and dst.
> // FIXME: It may be better to record these sizes and add them as
> constraints
> // to the dependency checks.
> for (int i = 1; i < size; ++i) {
> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
> return false;
>
> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
> return false;
>
> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
> return false;
>
> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
> return false;
> }
> ```
>
> The problem is that in a lot of cases these conditions cannot be proven
> statically, even though the delinearized indexes are in fact correct. For
> example consider this simple loop:
>
> ```
> void foo(int n, int m, int a[][m]) {
> for (int i = 0; i < n-1; ++i)
> for (int j = 2; j < m; ++j) {
> a[i][j] = a[i+1][j-2];
> }
> }
>
> clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
> opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
> -simplifycfg test.ll -S -o test.simp.ll
> opt test.simp.ll -analyze -da
> ```
>
> will produce:
>
> ```
> da analyze - none!
> da analyze - anti [* *|<]!
> da analyze - output [* *]!
> ```
>
> If the validity checks were not present, the result would be much more
> accurate dependence vector with accurate dependence distances:
>
> ```
> da analyze - none!
> da analyze - consistent anti [1 -2]!
> da analyze - none!
> ```
>
> In my experience the static validity checks tend to fail in many common
> cases (involving loops with symbolic bounds). Sometimes this happens
> because SCEV is not able to simplify the expressions due to presence of
> type casts and sign/zero extensions, but other times the conditions are
> just not computable at compile-time.
>
> So far I haven't been able to come up with an example where the validity
> checks in the current implementation legitimately catch a case of invalid
> delinearization. I've also disabled these checks and run some tests without
> finding any failures (other than improvements in the dependence analysis
> LIT tests).
>
> I also had a quick look at Polly which benefits from delinearization. From
> what I saw, a much more optimistic approach is taken where the validity
> checks seem to be avoided.
>
> My questions are:
> 1. Does anyone have more information about why these validity checks are
> necessary in the current implementation, perhaps with some examples showing
> an incorrect delinearization that's possible without those checks?
> 2. Are there any concerns with putting these validity checks under an
> option so that we can more easily disable them and experiment? This could
> also help us improve LIT tests, since some of them have been pessimised to
> compensate for DA's inability to delinearize, and could fail to catch
> regressions as a result of bad changes to the data dependence analysis.
>
> Looking forward to your help on this.
>
> Thank you,
>
> Bardia Mahjour
> Compiler Optimizations
> Hydra Squad Lead
> IBM Toronto Software Lab
> [hidden email] (905) 413-2336
>
>
>
>
>



> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

[hidden email]
   [attachment "da3.c" deleted by Bardia Mahjour/Toronto/IBM]


[attachment "graycol.gif" deleted by Bardia Mahjour/Toronto/IBM]




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
[CC bollu, mferguson, shil]

Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <[hidden email]>:

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
 

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

graycol.gif (142 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
On Fri, May 24, 2019 at 3:55 PM Michael Kruse via llvm-dev <[hidden email]> wrote:
[CC bollu, mferguson, shil]

Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <[hidden email]>:

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev
Hello,

After Sahil's GSoC 2018 project on integrating Chapel into Polly, 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 <[hidden email]> wrote:
On Fri, May 24, 2019 at 3:55 PM Michael Kruse via llvm-dev <[hidden email]> wrote:
[CC bollu, mferguson, shil]

Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <[hidden email]>:

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis

Amara Emerson via llvm-dev

Hi Siddharth,

I'd be interested in taking a look at your proposal once it becomes available.

Thanks,

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
[hidden email] (905) 413-2336



Inactive hide details for Siddharth Bhat via llvm-dev ---2019/05/29 04:46:57 AM---Hello, After Sahil's GSoC 2018 project on intSiddharth Bhat via llvm-dev ---2019/05/29 04:46:57 AM---Hello, After Sahil's GSoC 2018 project on integrating Chapel into Polly

From: Siddharth Bhat via llvm-dev <[hidden email]>
To: Hubert Tong <[hidden email]>
Cc: "[hidden email]" <[hidden email]>, SAHIL GIRISH YERAWAR <[hidden email]>, nd <[hidden email]>, Michael Ferguson <[hidden email]>
Date: 2019/05/29 04:46 AM
Subject: [EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis
Sent by: "llvm-dev" <[hidden email]>





Hello,

After Sahil's GSoC 2018 project on integrating Chapel into Polly, 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 <[hidden email]> wrote:
    On Fri, May 24, 2019 at 3:55 PM Michael Kruse via llvm-dev <[hidden email]> wrote:
    [CC bollu, mferguson, shil]

    Am Do., 23. Mai 2019 um 17:13 Uhr schrieb Bardia Mahjour <[hidden email]>:
      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
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
    _______________________________________________
    LLVM Developers mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev_______________________________________________
    LLVM Developers mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev