Re: asking your advice about bug

Re: asking your advice about bug

[Tobias Grosser]

On 02/03/2014 11:11 AM, Роман Гареев wrote:
>
>
> 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.

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

Re: asking your advice about bug

[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

Re: asking your advice about bug

[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

Re: asking your advice about bug

[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

Re: asking your advice about bug

[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

Re: asking your advice about bug

[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,
> 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
>
> -- --- 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+unsubscribe@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