asking your advice about bug

[Роман Гареев]

Dear Graphite contributors,

I am new to Graphite and want to find out if I could work on it. Could you point me to a simple bug, please? I would be very grateful for your advise.

--

Roman Gareev

[Tobias Grosser]

Hi,

maybe this bug seems a good start:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586

A segfault is normally rather easy to debug. If you have problems, I am
very happy to assist.

Cheers,
Tobias

[Roman Gareev]

Thank you for your advice! I've started working on a fix.

--

Roman Gareev

понедельник, 3 февраля 2014 г., 18:41:56 UTC+6 пользователь Tobias написал:

[Tobias Grosser]

On 02/04/2014 07:08 PM, Roman Gareev wrote:
>
>
> Thank you for your advice! I've started working on a fix.

Great. Feel free to ask in case you need some help.

Tobias

[Roman Gareev]

I've found out that this bug appeared in revision 189156 (svn://gcc.gnu.org/svn/gcc/trunk) and similar error message appeared in revision 191757 (svn://gcc.gnu.org/svn/gcc/trunk) (maybe it's because of changes in diagnostic.c). If subtract_commutative_associative_deps, a function located in gcc/graphite-dependences.c, is commented out, the error will disappear . I am trying to find a bug in this function now. Could you please answer a few questions about it?

1) Where can I find the algorithm for finding associative commutative reduction, which was used in subtract_commutative_associative_deps?

2) What is the number returned by isl_union_map_compute_flow? (I haven't found its description in “Integer Set Library: Manual”)

3) I've found the following terms in subtract_commutative_associative_deps: “may accesses”, “must access”. “Integer Set Library: Manual” gives the following definition: «If any of the source accesses are marked as being may accesses, then there will be a dependence to the last must access and to any may access that follows this last must access». Could you please describe their meaning? Are they related to transitively-covered dependences?

--

Roman Gareev

[Sven Verdoolaege]

On Wed, Feb 12, 2014 at 08:51:31AM -0800, Roman Gareev wrote:
> 2) What is the number returned by isl_union_map_compute_flow? (I haven't
> found its description in “Integer Set Library: Manual”)

It's 0 on success and -1 on failure.
Note that if you have questions about isl, you're much better off
asking them on the isl-development group.

> 3) I've found the following terms in subtract_commutative_associative_deps:
> “may accesses”, “must access”. “Integer Set Library: Manual” gives the
> following definition: «If any of the source accesses are marked as being
> may accesses, then there will be a dependence to the last must access and

> to any may access that follows this last must access». *Could you *please describe

> their meaning? Are they related to transitively-covered dependences?

Is this a question about what isl expects as input or
what graphite actually gives it as input?
If the former, then reformulate your question on the isl-development group.

skimo

[Tobias Grosser]

On 02/12/2014 11:51 AM, Roman Gareev wrote:

Hi Roman,

thanks for the quick feedback!

> I've found out that this bug appeared in revision 189156 (svn://gcc.gnu.org/svn/gcc/trunk)
> and similar error message appeared in revision 191757 (svn://gcc.gnu.org/svn/gcc/trunk)
> (maybe it's because of changes in diagnostic.c). If
> subtract_commutative_associative_deps, a function located in
> gcc/graphite-dependences.c, is commented out, the error will disappear . I

> am trying to find a bug in this function now. *Could you *please answer a

> few questions about it?
>
> 1) Where can I find the algorithm for finding associative commutative
> reduction, which was used in subtract_commutative_associative_deps?

It seems as if there is no such description available. This is a problem
by itself and we should probably add documentation about what is going
on. Unfortunately, I did not write the code and I also don't really get
what it is doing. The intuition seems to be that the dependences between
a set of reduction statements are computed and those dependences are
then removed from the overall set of dependences.
This is in general a good idea, but the code could need some
improvements and fixes. Several things look shady here. Here one example

1) We only remove dependences, but we should also add new ones

Let 'a->a' be reduction dependences, then dependences between 'a'
can only be removed in case we add new dependences between 'b1' and all
'a' and all 'a' and 'b2.

b1
|
a -> a -> a
|
b2

This should probably be fixed, but I don't think this is the problem of
the current bug report. In fact, to fix the bug report, I don't even
think we need to understand the full algorithm. The first question to
ask is:

Why are we segfaulting? Which statement is causing the segfault?

> 2) What is the number returned by isl_union_map_compute_flow? (I haven't
> found its description in “Integer Set Library: Manual”)
>
> 3) I've found the following terms in subtract_commutative_associative_deps:
> “may accesses”, “must access”. “Integer Set Library: Manual” gives the
> following definition: «If any of the source accesses are marked as being
> may accesses, then there will be a dependence to the last must access and

> to any may access that follows this last must access». *Could you *please describe

> their meaning? Are they related to transitively-covered dependences?

Thanks Sven for answering those.

Tobias

[Roman Gareev]

Hi Tobias,

thanks for the answer!

I think that the segfault is being caused by NULL arguments being passed to compute_deps by loop_level_carries_dependences. This is causing an assignment of NULL values to the following parameters of compute_deps: must_raw_no_source, may_raw_no_source, must_war_no_source, may_war_no_source, must_waw_no_source, may_waw_no_source. They are being passed to subtract_commutative_associative_deps and dereferenced in the following statements:

*must_raw_no_source = isl_union_map_subtract (*must_raw_no_source, x_must_raw_no_source);

*may_raw_no_source = isl_union_map_subtract (*may_raw_no_source, x_may_raw_no_source);

*must_war_no_source = isl_union_map_subtract (*must_war_no_source, x_must_war_no_source);

*may_war_no_source = isl_union_map_subtract (*may_war_no_source, x_may_war_no_source);

*must_waw_no_source = isl_union_map_subtract (*must_waw_no_source, x_must_waw_no_source);

*may_waw_no_source = isl_union_map_subtract (*may_waw_no_source, x_may_waw_no_source);

This is the reason of segfault. (All functions mentioned above are located in gcc/graphite-dependences.c)

I think that this can be solved by the addition to subtract_commutative_associative_deps of NULL checking of the following variables: must_raw_no_source, may_raw_no_source, must_war_no_source, may_war_no_source, must_waw_no_source, may_waw_no_source. I've implemented this in the patch, which can be found below.

Tested x86_64-unknown-linux-gnu, applying to revisions 189156, 207802 (svn://gcc.gnu.org/svn/gcc/trunk) and 207802 (svn://gcc.gnu.org/svn/gcc/branches/ibm/gcc-4_8-branch)

Thanks for your answers and advice, Sven!

--

Roman Gareev

[Tobias Grosser]

On 02/17/2014 06:50 PM, Roman Gareev wrote:
>
>
> Hi Tobias,
>
>
> thanks for the answer!

Hi Roman,

sorry for missing this mail.

>
> I think that the segfault is being caused by NULL arguments being passedto compute_deps

> by loop_level_carries_dependences. *This is **causing **an* *assignment of**
> NULL values to the following parameters of **compute_deps:* must_raw_no_source,

> may_raw_no_source, must_war_no_source, may_war_no_source,
> must_waw_no_source, may_waw_no_source. They are being passed to subtract_commutative_associative_deps
> and dereferenced in the following statements:
>
>
> *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
> x_must_raw_no_source);
>
>
> *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
> x_may_raw_no_source);
>
>
> *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
> x_must_war_no_source);
>
>
> *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
> x_may_war_no_source);
>
>
> *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
> x_must_waw_no_source);
>
>
> *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
> x_may_waw_no_source);
>
> This is the reason of segfault. (All functions mentioned above are located
> in gcc/graphite-dependences.c)
>

Interesting analysis.

> I think that this can be solved by the addition to
> subtract_commutative_associative_deps of NULL checking of the following
> variables: must_raw_no_source, may_raw_no_source, must_war_no_source,
> may_war_no_source, must_waw_no_source, may_waw_no_source. I've implemented
> this in the patch, which can be found below.

Yes, this would be a 'solution'. However, I am in fact surprised that
those variables are NULL at all. Do you have an idea why this is the
case? Understanding this would help to understand if the patch you
propose is actually the right solution or if it is just hiding a
previous bug.

Cheers,
Tobias

[Roman Gareev]

Yes, this would be a 'solution'. However, I am in fact surprised that
those variables are NULL at all. Do you have an idea why this is the
case? Understanding this would help to understand if the patch you
propose is actually the right solution or if it is just hiding a
previous bug.    

Hi Tobias,

After consideration of almost all the code in gcc/graphite-dependences.c,
I think that the NULL arguments being passed to compute_deps are appropriate
for loop_level_carries_dependences.

In my opinion, loop_level_carries_dependences uses the following algorithm
to determine if the loop at the level DEPTH carries dependences:

This function uses compute_deps for finding RAW, WAR and WAW dependences
of all basic blocks in the body of the given loop. Subsequently, it tries to determine
presence of these dependences at the given level. I think that it tries to find loop-independent
dependences [1] in carries_deps. Therefore it maps the relation of dependences
to the relation of the corresponding time-stamps and intersects the result with the relation
in which all the inputs before DEPTH occur at the same time as the output, and the input
at DEPTH occurs before output. I might be wrong, but I suppose that no_source
dependences are unnecessary for this algorithm.

1. N. Vasilache, A. Cohen, C. Bastoul, and S. Girbal. Violated dependence analysis.
In ACM Intl. Conf. on Supercomputing (ICS'06), Cairns, Australia, June 2006.

--
Roman Gareev

[Tobias Grosser]

On 03/02/2014 08:06 PM, Roman Gareev wrote:
>
>>
>> Yes, this would be a 'solution'. However, I am in fact surprised that
>> those variables are NULL at all. Do you have an idea why this is the
>> case? Understanding this would help to understand if the patch you
>> propose is actually the right solution or if it is just hiding a
>> previous bug.
>>
>
> Hi Tobias,
>
> After consideration of almost all the code in gcc/graphite-dependences.c,
> I think that the NULL arguments being passed to compute_deps are
> appropriate
> for loop_level_carries_dependences.

I slowly come to the same conclusion. Thanks a lot for digging deeper
into this.

> In my opinion, loop_level_carries_dependences uses the following algorithm
> to determine if the loop at the level DEPTH carries dependences:
>
> This function uses compute_deps for finding RAW, WAR and WAW dependences
> of all basic blocks in the body of the given loop. Subsequently, it tries
> to determine presence of these dependences at the given level. I think that it tries to
> find loop-independent
> dependences [1] in carries_deps. Therefore it maps the relation of
> dependences
> to the relation of the corresponding time-stamps and intersects the result
> with the relation
> in which all the inputs before DEPTH occur at the same time as the output,
> and the input
> at DEPTH occurs before output.

Yes, it checks if all dependences are carried by outer loops already. If
the intersection is not empty, some dependences are carried by the DEPTH
we currently check and the loop is consequently not parallel.

> I might be wrong, but I suppose that
> no_source

> dependences are *unnecessary* for this algorithm.

Yes, this analysis is very correct.

In that light, I believe your previous patch is correct. I will review
it and we can probably commit it. Thanks for working on this!

Tobias

[Tobias Grosser]

On 02/17/2014 06:50 PM, Roman Gareev wrote:
>
>

> Hi Tobias,
>
>
> thanks for the answer!
>
>
> I think that the segfault is being caused by NULL arguments being passedto compute_deps

> by loop_level_carries_dependences.*This is **causing **an* *assignment of**
> NULL values to the following parameters of **compute_deps:* must_raw_no_source,

> -- --- You received this message because you are subscribed to the
> Google Groups "GCC GRAPHITE" group. To unsubscribe from this group and
> stop receiving emails from it, send an email to
> gcc-graphite...@googlegroups.com. For more options, visit
> https://groups.google.com/groups/opt_out.
>
>
> patch
>
>
> diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c
> index b0f8680..002e3d1 100644
> --- a/gcc/graphite-dependences.c
> +++ b/gcc/graphite-dependences.c
> @@ -424,24 +424,83 @@ subtract_commutative_associative_deps (scop_p scop,
> &x_may_waw_no_source);
> gcc_assert (res == 0);
>
> - *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
> - *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
> - *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
> - x_must_raw_no_source);
> - *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
> - x_may_raw_no_source);
> - *must_war = isl_union_map_subtract (*must_war, x_must_war);
> - *may_war = isl_union_map_subtract (*may_war, x_may_war);
> - *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
> - x_must_war_no_source);
> - *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
> - x_may_war_no_source);
> - *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
> - *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
> - *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
> - x_must_waw_no_source);
> - *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
> - x_may_waw_no_source);
> + if (must_raw)
> + *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);
> + else
> + isl_union_map_free (x_must_raw);
> +
> + if (may_raw)
> + *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);
> + else
> + isl_union_map_free (x_may_raw);

In my understanding, it is sufficient to guard the no_source statements, no?

> +
> + if (must_raw_no_source)
> + {
> + *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,
> + x_must_raw_no_source);
> + }
> + else
> + isl_union_map_free (x_must_raw_no_source);

Could you remove the '{' '}' around the first statement?

> +
> + if (may_raw_no_source)
> + {
> + *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,
> + x_may_raw_no_source);
> + }
> + else
> + isl_union_map_free (x_may_raw_no_source);

Could you remove the '{' '}' around the first statement?

> + if (must_war)
> + *must_war = isl_union_map_subtract (*must_war, x_must_war);
> + else
> + isl_union_map_free (x_must_war);
> +
> + if (may_war)
> + *may_war = isl_union_map_subtract (*may_war, x_may_war);
> + else
> + isl_union_map_free (x_may_war);

Those do not seem to be necessary, no?

> +
> + if (must_war_no_source)
> + {
> + *must_war_no_source = isl_union_map_subtract (*must_war_no_source,
> + x_must_war_no_source);
> + }
> + else
> + isl_union_map_free (x_must_war_no_source);
> +
> + if (may_war_no_source)
> + {
> + *may_war_no_source = isl_union_map_subtract (*may_war_no_source,
> + x_may_war_no_source);
> + }
> + else
> + isl_union_map_free (x_may_war_no_source);

Could you remove the '{' '}' around the first statement?

> +
> + if (must_waw)
> + *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);
> + else
> + isl_union_map_free (x_must_waw);
> +
> + if (may_waw)
> + *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);
> + else
> + isl_union_map_free (x_may_waw);

Those do not seem to be necessary, no?

> +
> + if (must_waw_no_source)
> + {
> + *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,
> + x_must_waw_no_source);
> + }
> + else
> + isl_union_map_free (x_must_waw_no_source);
> +
> + if (may_waw_no_source)
> + {
> + *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,
> + x_may_waw_no_source);
> + }
> + else
> + isl_union_map_free (x_may_waw_no_source);

Could you remove the '{' '}' around the first statement?

Otherwise, the patch looks good.

To commit this patch, could you please provide a ChangeLog entry as well
as a commit message that _briefly_ describes the findings mentioned in
you last email and submit this patch to gcc-patches?

Thanks again,
Tobias

[Roman Gareev]

Hi Tobias,

thank you very much for your help!

In my understanding, it is sufficient to guard the no_source statements, no?  

Yes, they are unnecessary. I thought that it could help to prevent must_raw, may_raw, 

must_war, may_war, must_waw, may_waw from being dereferenced in case of NULL values. 

Now I see that it can hide potential bug and it is better to remove them. 

A copy of the submitted patch can be found in the next mail.

--

Roman Gareev

[Roman Gareev]

This patch fixes the following bug:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586.
The segfault is caused by NULL arguments passed to compute_deps by
loop_level_carries_dependences.
This causes an assignment of NULL values to the no_source parameters
of compute_deps.
They are passed to subtract_commutative_associative_deps and dereferenced.

However, this NULL arguments are appropriate for the algorithm used
in loop_level_carries_dependences. It uses compute_deps

for finding RAW, WAR and WAW dependences of all basic blocks
in the body of the given loop. Subsequently, it tries to
determine presence of these dependences at the given level.

Therefore it maps the relation of the dependences to the relation

of the corresponding time-stamps and intersects the result with

the relation in which all the inputs before the DEPTH occur at the
same time as the output, and the input at the DEPTH occurs before output.

If the intersection is not empty, some dependences are carried
by the DEPTH we currently check and the loop is consequently not parallel.

This patch tries to avoid the problem by addition to
subtract_commutative_associative_deps
of NULL checking of the no_source statements.

Tested x86_64-unknown-linux-gnu, applying to 4.8.3 and trunk.

2014-03-07 Roman Gareev <garee...@gmail.com>

                gcc/
                * graphite-dependences.c (subtract_commutative_associative_deps):
                Add NULL checking of the following variables:

                must_raw_no_source, may_raw_no_source,
                must_war_no_source, may_war_no_source,
                must_waw_no_source, may_waw_no_source.

                gcc/testsuite/gfortran.dg/graphite/graphite.exp: Run corresponding
                tests in new mode.

                gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f: New testcase.

diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c

index b0f8680..f382233 100644

--- a/gcc/graphite-dependences.c

+++ b/gcc/graphite-dependences.c

@@ -426,22 +426,48 @@ subtract_commutative_associative_deps (scop_p scop,

 

  *must_raw = isl_union_map_subtract (*must_raw, x_must_raw);

  *may_raw = isl_union_map_subtract (*may_raw, x_may_raw);

- *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,

-      x_must_raw_no_source);

- *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,

-     x_may_raw_no_source);

+

+ if (must_raw_no_source)

+  *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source,

+          x_must_raw_no_source);

+ else

+  isl_union_map_free (x_must_raw_no_source);

+

+ if (may_raw_no_source)

+  *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source,

+         x_may_raw_no_source);

+ else

+  isl_union_map_free (x_may_raw_no_source);

+

  *must_war = isl_union_map_subtract (*must_war, x_must_war);

  *may_war = isl_union_map_subtract (*may_war, x_may_war);

- *must_war_no_source = isl_union_map_subtract (*must_war_no_source,

-      x_must_war_no_source);

- *may_war_no_source = isl_union_map_subtract (*may_war_no_source,

-     x_may_war_no_source);

+

+ if (must_war_no_source)

+  *must_war_no_source = isl_union_map_subtract (*must_war_no_source,

+          x_must_war_no_source);

+ else

+  isl_union_map_free (x_must_war_no_source);

+

+ if (may_war_no_source)

+  *may_war_no_source = isl_union_map_subtract (*may_war_no_source,

+         x_may_war_no_source);

+ else

+  isl_union_map_free (x_may_war_no_source);

+

  *must_waw = isl_union_map_subtract (*must_waw, x_must_waw);

  *may_waw = isl_union_map_subtract (*may_waw, x_may_waw);

- *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,

-      x_must_waw_no_source);

- *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,

-     x_may_waw_no_source);

+

+ if (must_waw_no_source)

+  *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source,

+          x_must_waw_no_source);

+ else

+  isl_union_map_free (x_must_waw_no_source);

+

+ if (may_waw_no_source)

+  *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source,

+         x_may_waw_no_source);

+ else

+  isl_union_map_free (x_may_waw_no_source);

       }

 

   isl_union_map_free (original);

diff --git a/gcc/testsuite/gfortran.dg/graphite/graphite.exp b/gcc/testsuite/gfortran.dg/graphite/graphite.exp

index c3aad13..3833e43 100644

--- a/gcc/testsuite/gfortran.dg/graphite/graphite.exp

+++ b/gcc/testsuite/gfortran.dg/graphite/graphite.exp

@@ -44,6 +44,7 @@ set interchange_files [lsort [glob -nocomplain $srcdir/$subdir/interchange-*.\[f

 set scop_files        [lsort [glob -nocomplain $srcdir/$subdir/scop-*.\[fF\]{,90,95,03,08} ] ]

 set run_id_files      [lsort [glob -nocomplain $srcdir/$subdir/run-id-*.\[fF\]{,90,95,03,08} ] ]

 set vect_files        [lsort [glob -nocomplain $srcdir/$subdir/vect-*.\[fF\]{,90,95,03,08} ] ]

+set parallelize_files [lsort [glob -nocomplain $srcdir/$subdir/parallelize-all-*.\[fF\]{,90,95,03,08} ] ]

 

 # Tests to be compiled.

 set dg-do-what-default compile

@@ -51,6 +52,7 @@ gfortran-dg-runtest $scop_files        "-O2 -fgraphite -fdump-tree-graphite-all"

 gfortran-dg-runtest $id_files          "-O2 -fgraphite-identity -ffast-math"

 gfortran-dg-runtest $interchange_files "-O2 -floop-interchange -fno-loop-block -fno-loop-strip-mine -ffast-math -fdump-tree-graphite-all"

 gfortran-dg-runtest $block_files       "-O2 -floop-block -fno-loop-strip-mine -fno-loop-interchange -ffast-math -fdump-tree-graphite-all"

+gfortran-dg-runtest $parallelize_files "-Ofast  -floop-parallelize-all"

 

 # Vectorizer tests, to be run or compiled, depending on target capabilities.

 if [check_vect_support_and_set_flags] {

diff --git a/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f b/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f

new file mode 100644

index 0000000..e1156f8

--- /dev/null

+++ b/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f

@@ -0,0 +1,9 @@

+      subroutine subsm ( n, x, xp, xx)

+      integer        n, m, x(n),xp(n), xx(n), gg(n), dd_p

+      do 55 i=1, n

+         dd_p  = dd_p + (x(i) - xx(i))*gg(i)

+ 55   continue

+      if ( dd_p .gt. 0  ) then

+         call dcopy( n, xp, 1, x, 1 )

+      endif

+      end