Lack of capability to represent arbitrary alias dependent information
HI,
GCC adds runtime alias checks for data references in passes like
vectorizer, it would be very useful to pass along the runtime alias
dependent information to later passes. Given below expample:
int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
{
int k, x;
for (k = 0; k < len; k++)
{
c[k] = a[k-1] + b[k-1];
if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
if (c[k] < v) c[k] = v;
}
return 0;
}
After vectorizer's runtime alias check, we know that c doesn't alias
to a/b/d/e arrays. This enables dead store elimination for c array.
The question is how to pass the information to dse (or predcom, etc.).
So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
that. The fundamental issue is MR_DEPENDENCE_* can only represent
alias relations between references in a strong connected component of
dependence graph, while in most cases (like this one) the dependence
graph is not SCC. In general, if we have below dependence graph:
Dependence Graph: G
V: {x(write), y(write), a(read), b(read)}
E:
Since a and b are reads, we don't need to know the relations between a
and b; also it's possible to have any dependence relation between x
and y. In this case, we can't assign x, a and b into one clique. We
can't assign x and y into different clique either because they both
are not-aliasing to a/b. As a matter of fact, we need a way to
represent arbitrary dependence graph, rather than SCC only.
So any suggestions?
Thanks,
bin
Re: Lack of capability to represent arbitrary alias dependent information
On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng wrote:
> HI,
> GCC adds runtime alias checks for data references in passes like
> vectorizer, it would be very useful to pass along the runtime alias
> dependent information to later passes. Given below expample:
>
> int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
> {
> int k, x;
> for (k = 0; k < len; k++)
> {
> c[k] = a[k-1] + b[k-1];
> if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
> if (c[k] < v) c[k] = v;
> }
>
> return 0;
> }
> After vectorizer's runtime alias check, we know that c doesn't alias
> to a/b/d/e arrays. This enables dead store elimination for c array.
> The question is how to pass the information to dse (or predcom, etc.).
> So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
> that. The fundamental issue is MR_DEPENDENCE_* can only represent
> alias relations between references in a strong connected component of
> dependence graph, while in most cases (like this one) the dependence
> graph is not SCC. In general, if we have below dependence graph:
> Dependence Graph: G
> V: {x(write), y(write), a(read), b(read)}
> E:
>
>
>
> Since a and b are reads, we don't need to know the relations between a
> and b; also it's possible to have any dependence relation between x
> and y. In this case, we can't assign x, a and b into one clique. We
> can't assign x and y into different clique either because they both
> are not-aliasing to a/b. As a matter of fact, we need a way to
> represent arbitrary dependence graph, rather than SCC only.
> So any suggestions?
The "simplest" solution is to assign the same BASE to those.
This is how restrict works to record dependence on not restrict
marked pointers or decls.
So it's not just SCCs but slightly more powerful (but only very
slightly).
Richard.
> Thanks,
> bin
Re: Lack of capability to represent arbitrary alias dependent information
On Mon, Jun 12, 2017 at 10:15 AM, Richard Biener
wrote:
> On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng wrote:
>> HI,
>> GCC adds runtime alias checks for data references in passes like
>> vectorizer, it would be very useful to pass along the runtime alias
>> dependent information to later passes. Given below expample:
>>
>> int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
>> {
>> int k, x;
>> for (k = 0; k < len; k++)
>> {
>> c[k] = a[k-1] + b[k-1];
>> if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
>> if (c[k] < v) c[k] = v;
>> }
>>
>> return 0;
>> }
>> After vectorizer's runtime alias check, we know that c doesn't alias
>> to a/b/d/e arrays. This enables dead store elimination for c array.
>> The question is how to pass the information to dse (or predcom, etc.).
>> So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
>> that. The fundamental issue is MR_DEPENDENCE_* can only represent
>> alias relations between references in a strong connected component of
>> dependence graph, while in most cases (like this one) the dependence
>> graph is not SCC. In general, if we have below dependence graph:
>> Dependence Graph: G
>> V: {x(write), y(write), a(read), b(read)}
>> E:
>>
>>
>>
>> Since a and b are reads, we don't need to know the relations between a
>> and b; also it's possible to have any dependence relation between x
>> and y. In this case, we can't assign x, a and b into one clique. We
>> can't assign x and y into different clique either because they both
>> are not-aliasing to a/b. As a matter of fact, we need a way to
>> represent arbitrary dependence graph, rather than SCC only.
>> So any suggestions?
>
> The "simplest" solution is to assign the same BASE to those.
>
> This is how restrict works to record dependence on not restrict
> marked pointers or decls.
Yes, right. I missed the base part. In this case, the dependence
info can well model runtime alias information.
Thanks,
bin
>
> So it's not just SCCs but slightly more powerful (but only very
> slightly).
>
> Richard.
>
>> Thanks,
>> bin
Re: Lack of capability to represent arbitrary alias dependent information
On Mon, Jun 12, 2017 at 11:46 AM, Bin.Cheng wrote:
> On Mon, Jun 12, 2017 at 10:15 AM, Richard Biener
> wrote:
>> On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng wrote:
>>> HI,
>>> GCC adds runtime alias checks for data references in passes like
>>> vectorizer, it would be very useful to pass along the runtime alias
>>> dependent information to later passes. Given below expample:
>>>
>>> int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
>>> {
>>> int k, x;
>>> for (k = 0; k < len; k++)
>>> {
>>> c[k] = a[k-1] + b[k-1];
>>> if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
>>> if (c[k] < v) c[k] = v;
>>> }
>>>
>>> return 0;
>>> }
>>> After vectorizer's runtime alias check, we know that c doesn't alias
>>> to a/b/d/e arrays. This enables dead store elimination for c array.
>>> The question is how to pass the information to dse (or predcom, etc.).
>>> So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
>>> that. The fundamental issue is MR_DEPENDENCE_* can only represent
>>> alias relations between references in a strong connected component of
>>> dependence graph, while in most cases (like this one) the dependence
>>> graph is not SCC. In general, if we have below dependence graph:
>>> Dependence Graph: G
>>> V: {x(write), y(write), a(read), b(read)}
>>> E:
>>>
>>>
>>>
>>> Since a and b are reads, we don't need to know the relations between a
>>> and b; also it's possible to have any dependence relation between x
>>> and y. In this case, we can't assign x, a and b into one clique. We
>>> can't assign x and y into different clique either because they both
>>> are not-aliasing to a/b. As a matter of fact, we need a way to
>>> represent arbitrary dependence graph, rather than SCC only.
>>> So any suggestions?
>>
>> The "simplest" solution is to assign the same BASE to those.
>>
>> This is how restrict works to record dependence on not restrict
>> marked pointers or decls.
> Yes, right. I missed the base part. In this case, the dependence
> info can well model runtime alias information.
Hmm, my bad being over-optimistic. So here is the mode: After fusing
all SCCs, the condition to model fused dependence graph using
clique/base is below:
For each connected component of the fused graph, the diameter of the
connected component is no larger than 2. I believe this is true for
majority cases, but full proof is complicated. Specially, it might be
not always true in case of restrict pointers. I will think about if
we can only handle simplest cases.
Thanks,
bin
>
> Thanks,
> bin
>>
>> So it's not just SCCs but slightly more powerful (but only very
>> slightly).
>>
>> Richard.
>>
>>> Thanks,
>>> bin
Re: Lack of capability to represent arbitrary alias dependent information
On Mon, Jun 12, 2017 at 2:00 PM, Bin.Cheng wrote:
> On Mon, Jun 12, 2017 at 11:46 AM, Bin.Cheng wrote:
>> On Mon, Jun 12, 2017 at 10:15 AM, Richard Biener
>> wrote:
>>> On Mon, Jun 12, 2017 at 11:02 AM, Bin.Cheng wrote:
HI,
GCC adds runtime alias checks for data references in passes like
vectorizer, it would be very useful to pass along the runtime alias
dependent information to later passes. Given below expample:
int foo (int *a, int *b, int *c, int *d, int *e, int len, int v)
{
int k, x;
for (k = 0; k < len; k++)
{
c[k] = a[k-1] + b[k-1];
if ((x = d[k-1] + e[k-1]) > c[k]) c[k] = x;
if (c[k] < v) c[k] = v;
}
return 0;
}
After vectorizer's runtime alias check, we know that c doesn't alias
to a/b/d/e arrays. This enables dead store elimination for c array.
The question is how to pass the information to dse (or predcom, etc.).
So far MR_DEPENDENCE_* is suggested, but I found it's not capable of
that. The fundamental issue is MR_DEPENDENCE_* can only represent
alias relations between references in a strong connected component of
dependence graph, while in most cases (like this one) the dependence
graph is not SCC. In general, if we have below dependence graph:
Dependence Graph: G
V: {x(write), y(write), a(read), b(read)}
E:
Since a and b are reads, we don't need to know the relations between a
and b; also it's possible to have any dependence relation between x
and y. In this case, we can't assign x, a and b into one clique. We
can't assign x and y into different clique either because they both
are not-aliasing to a/b. As a matter of fact, we need a way to
represent arbitrary dependence graph, rather than SCC only.
So any suggestions?
>>>
>>> The "simplest" solution is to assign the same BASE to those.
>>>
>>> This is how restrict works to record dependence on not restrict
>>> marked pointers or decls.
>> Yes, right. I missed the base part. In this case, the dependence
>> info can well model runtime alias information.
> Hmm, my bad being over-optimistic. So here is the mode: After fusing
> all SCCs, the condition to model fused dependence graph using
> clique/base is below:
> For each connected component of the fused graph, the diameter of the
> connected component is no larger than 2. I believe this is true for
> majority cases, but full proof is complicated. Specially, it might be
> not always true in case of restrict pointers. I will think about if
> we can only handle simplest cases.
I expect we can exactly handle the cases you could map to restrict.
The model was really developed for restrict and with the goal to have
O(n) size complexity to store non-dependences for n references
(which is quite ambitious ;)). Inside the loop pipeline we'd in theory
have the option to keep computed data dependences, at least
across a few passes. OTOH we basically gave up doing that for SCEV
and thus most passes clear the SCEV cache for the fear of corrupting it.
Richard.
> Thanks,
> bin
>>
>> Thanks,
>> bin
>>>
>>> So it's not just SCCs but slightly more powerful (but only very
>>> slightly).
>>>
>>> Richard.
>>>
Thanks,
bin
GCC 6.3 vs 6.3.1 - whats the difference? Is 6.3.1 an unofficial secret GCC release?
A lot of Linux distributions have gcc 6.3.1 available, or even preinstalled. However, I am not able to find any info about 6.3.1 at the official GCC pages at gnu org. Please tell, is 6.3.1 an unofficial secret GCC release? What is the difference between 6.3 and 6.3.1, any changelog?
Re: GCC 6.3 vs 6.3.1 - whats the difference? Is 6.3.1 an unofficial secret GCC release?
On June 12, 2017 8:37:37 PM GMT+02:00, info rmer wrote: >A lot of Linux distributions have gcc 6.3.1 available, or even >preinstalled. >However, I am not able to find any info about 6.3.1 at the official GCC >pages at gnu org. >Please tell, is 6.3.1 an unofficial secret GCC release? >What is the difference between 6.3 and 6.3.1, any changelog? 6.3.1 is the version GCC reports for snapshots off the GCC 6 branch between the 6.3 and the upcoming 6.4 release. It's basically 6.3 with additional patches. Richard.
Re: GCC 6.3 vs 6.3.1 - whats the difference? Is 6.3.1 an unofficial secret GCC release?
On 12 June 2017 at 19:37, info rmer wrote: > A lot of Linux distributions have gcc 6.3.1 available, or even preinstalled. > However, I am not able to find any info about 6.3.1 at the official GCC pages > at gnu org. See https://gcc.gnu.org/develop.html#num_scheme
Re: GCC 6.3 vs 6.3.1 - whats the difference? Is 6.3.1 an unofficial secret GCC release?
12.06.2017, 21:41, "Richard Biener" : > > 6.3.1 is the version GCC reports for snapshots off the GCC 6 branch between > the 6.3 and the upcoming 6.4 release. It's basically 6.3 with additional > patches. > > Richard. > Thank you very much. Is there any way to obtain the source code for this 6.3.1 version? Or is it unknown - at what point of GCC 6 branch development the distro maintainers have cloned their GCC? 13.06.2017, 01:39, "Jonathan Wakely" : > On 12 June 2017 at 19:37, info rmer wrote: >> A lot of Linux distributions have gcc 6.3.1 available, or even preinstalled. >> However, I am not able to find any info about 6.3.1 at the official GCC >> pages at gnu org. > > See https://gcc.gnu.org/develop.html#num_scheme Sadly this num_scheme link does not contain any mention to 6.3.1 ___ > On June 12, 2017 8:37:37 PM GMT+02:00, info rmer > wrote: >> A lot of Linux distributions have gcc 6.3.1 available, or even >> preinstalled. >> However, I am not able to find any info about 6.3.1 at the official GCC >> pages at gnu org. >> Please tell, is 6.3.1 an unofficial secret GCC release? >> What is the difference between 6.3 and 6.3.1, any changelog?
Re: GCC 6.3 vs 6.3.1 - whats the difference? Is 6.3.1 an unofficial secret GCC release?
On Tue, Jun 13, 2017 at 09:01:41AM +0300, info rmer wrote: > 12.06.2017, 21:41, "Richard Biener" : > > > > 6.3.1 is the version GCC reports for snapshots off the GCC 6 branch > > between the 6.3 and the upcoming 6.4 release. It's basically 6.3 with > > additional patches. > > > > Richard. > > > > Thank you very much. Is there any way to obtain the source code for this > 6.3.1 version? There is no single 6.3.1 version, 6.3.1 is any snapshot between 6.3 and 6.4, either (rarely) one of the many weekly snapshots from ftp://gcc.gnu.org/pub/gcc/snapshots/, or (much more often) just a snapshot from SVN or git. Plus often the distro versions of GCC contain additional patches. BTW, the version is often also accompanied with a date and additional details like: gcc version 6.3.1 20161221 (Red Hat 6.3.1-1) (GCC) so you also know quickly at least the date at which the upstream snapshot was merged. > Or is it unknown - at what point of GCC 6 branch development the distro > maintainers have cloned their GCC? If for whatever reason you need to have details on this, you need to look at what actually is included and see if there is any metadata (e.g. SVN revision or git hash) from where this was taken. Some distros also use vendor branches in upstream SVN or git or their own repositories with additional changes which are periodically synced from the upstream release branch. E.g. for Fedora in gcc.spec file there is a SVN revision number and details how to check out the snapshot from branches/redhat/gcc-N-branch and the commit messages on that branch (or svn:mergeinfo property on .) tell you what revisions from corresponding upstream branches/gcc-N-branch have been merged in. > 13.06.2017, 01:39, "Jonathan Wakely" : > > On 12 June 2017 at 19:37, info rmer wrote: > >> A lot of Linux distributions have gcc 6.3.1 available, or even > >> preinstalled. > >> However, I am not able to find any info about 6.3.1 at the official GCC > >> pages at gnu org. > > > > See https://gcc.gnu.org/develop.html#num_scheme > > Sadly this num_scheme link does not contain any mention to 6.3.1 Why should it? It explains the numbering scheme, which applies equally to any other numbers (5+). Jakub
