[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

Jakub Jelinek  changed:

   What|Removed |Added

   Target Milestone|6.5 |7.4

--- Comment #19 from Jakub Jelinek  ---
GCC 6 branch is being closed

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #18 from Martin Liška  ---
Good job, tramp3d works now ;)

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

Richard Biener  changed:

   What|Removed |Added

  Known to work||8.0
Summary|[6/7/8  |[6/7 Regression][graphite]
   |Regression][graphite]   |tramp3d-v4 compiled with
   |tramp3d-v4 compiled with|-floop-nest-optimize
   |-floop-nest-optimize|crashes
   |crashes |
  Known to fail||7.2.0

--- Comment #16 from Richard Biener  ---
Fixed on trunk sofar.

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #17 from Richard Biener  ---
Author: rguenth
Date: Fri Sep 15 07:03:02 2017
New Revision: 252780

URL: https://gcc.gnu.org/viewcvs?rev=252780=gcc=rev
Log:
2017-09-15  Richard Biener  

PR tree-optimization/68823
* graphite-scop-detection.c (build_alias_set): If we have a
possible dependence check whether we can handle them by just
looking at the DRs DR_ACCESS_FNs.
(build_scops): If build_alias_set fails, fail the SCOP.

Modified:
trunk/gcc/ChangeLog
trunk/gcc/graphite-scop-detection.c

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #11 from Sebastian Pop  ---
(In reply to Richard Biener from comment #10)
> But then with different number of subscripts (and also likely different
> DR_BASE_OBJECT) you can't do anything with them and have to assume
> dependence.  See initialize_data_dependence_relation:
> 
>   /* If the references do not access the same object, we do not know
>  whether they alias or not.  We do not care about TBAA or alignment
>  info so we can use OEP_ADDRESS_OF to avoid false negatives.
>  But the accesses have to use compatible types as otherwise the
>  built indices would not match.  */
>   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b),
> OEP_ADDRESS_OF)
>   || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),
>   TREE_TYPE (DR_BASE_OBJECT (b
> {
>   DDR_ARE_DEPENDENT (res) = chrec_dont_know;
>   return res;
> 
> not sure how you communicate that to ISL of course...  is it what you
> use "alias-sets" for?  To create extra dependence egdes?

alias-sets differ for two arrays with bases that have been proven to be
different.
If they may point to the same thing, they will have the same number.

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #10 from Richard Biener  ---
(In reply to Sebastian Pop from comment #7)
> (In reply to Martin Liška from comment #5)
> > Created attachment 40662 [details]
> > Isolated graphite dump for miscompiled function
> > 
> > As shown in the dump file, there are dependencies for the problematic stmts:
> > 
> > Adding must write to depedence graph: pdr_121 (write 
> > in gimple stmt: MEM[(Element_t[2] &)_7][0] = _9;
> > data accesses: { S_3[i2] -> [2, o1, 0] : 8*floor((o1)/8) = o1 and
> > 18446744073709551616*floor((8i2 - o1)/18446744073709551616) = 8i2 - o1 and 0
> > <= o1 <= 18446744073709551608 }
> > 
> > Adding read to depedence graph: pdr_124 (read 
> > in gimple stmt: _15 = MEM[(int *)_14];
> > data accesses: { S_6[i1] -> [2, o1] : 18446744073709551616*floor((-8i1 +
> > o1)/18446744073709551616) = -8i1 + o1 and 0 <= o1 <= 18446744073709551608 }
> > 
> > If I understand the notation correctly, both have equal alias set (2). Do
> > you see Sebastian why the dependence is not caught?
> > 
> 
> S_3[i2] -> [2, o1, 0]
> S_6[i1] -> [2, o1]
> 
> we do not detect the dependence because the two arrays do not have the same
> number of subscripts: also on the gimple representation we have
> 
> MEM[(Element_t[2] &)_7][0] = _9;
> vs.
> _15 = MEM[(int *)_14];

But then with different number of subscripts (and also likely different
DR_BASE_OBJECT) you can't do anything with them and have to assume
dependence.  See initialize_data_dependence_relation:

  /* If the references do not access the same object, we do not know
 whether they alias or not.  We do not care about TBAA or alignment
 info so we can use OEP_ADDRESS_OF to avoid false negatives.
 But the accesses have to use compatible types as otherwise the
 built indices would not match.  */
  if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), OEP_ADDRESS_OF)
  || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),
  TREE_TYPE (DR_BASE_OBJECT (b
{
  DDR_ARE_DEPENDENT (res) = chrec_dont_know;
  return res;

not sure how you communicate that to ISL of course...  is it what you
use "alias-sets" for?  To create extra dependence egdes?

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #9 from Sebastian Pop  ---
/* Determines the base object and the list of indices of memory reference
   DR, analyzed in LOOP and instantiated in loop nest NEST.  */

static void
dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)

This function initializes the subscripts with their access functions:
  DR_ACCESS_FNS (dr) = access_fns;

The number of subscripts (or "dimensions") is then the length of that array:
#define DR_NUM_DIMENSIONS(DR)  DR_ACCESS_FNS (DR).length ()

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #8 from Sebastian Pop  ---
The code in fault is called from pdr_add_memory_accesses()
Maybe the problem is in parsing the gimple MEM[] into a data reference.

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #7 from Sebastian Pop  ---
(In reply to Martin Liška from comment #5)
> Created attachment 40662 [details]
> Isolated graphite dump for miscompiled function
> 
> As shown in the dump file, there are dependencies for the problematic stmts:
> 
> Adding must write to depedence graph: pdr_121 (write 
> in gimple stmt: MEM[(Element_t[2] &)_7][0] = _9;
> data accesses: { S_3[i2] -> [2, o1, 0] : 8*floor((o1)/8) = o1 and
> 18446744073709551616*floor((8i2 - o1)/18446744073709551616) = 8i2 - o1 and 0
> <= o1 <= 18446744073709551608 }
> 
> Adding read to depedence graph: pdr_124 (read 
> in gimple stmt: _15 = MEM[(int *)_14];
> data accesses: { S_6[i1] -> [2, o1] : 18446744073709551616*floor((-8i1 +
> o1)/18446744073709551616) = -8i1 + o1 and 0 <= o1 <= 18446744073709551608 }
> 
> If I understand the notation correctly, both have equal alias set (2). Do
> you see Sebastian why the dependence is not caught?
> 

S_3[i2] -> [2, o1, 0]
S_6[i1] -> [2, o1]

we do not detect the dependence because the two arrays do not have the same
number of subscripts: also on the gimple representation we have

MEM[(Element_t[2] &)_7][0] = _9;
vs.
_15 = MEM[(int *)_14];

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #6 from Martin Liška  ---
And I'm also trying to reduce a self-contained test-case.

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #5 from Martin Liška  ---
Created attachment 40662
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=40662=edit
Isolated graphite dump for miscompiled function

As shown in the dump file, there are dependencies for the problematic stmts:

Adding must write to depedence graph: pdr_121 (write 
in gimple stmt: MEM[(Element_t[2] &)_7][0] = _9;
data accesses: { S_3[i2] -> [2, o1, 0] : 8*floor((o1)/8) = o1 and
18446744073709551616*floor((8i2 - o1)/18446744073709551616) = 8i2 - o1 and 0 <=
o1 <= 18446744073709551608 }

Adding read to depedence graph: pdr_124 (read 
in gimple stmt: _15 = MEM[(int *)_14];
data accesses: { S_6[i1] -> [2, o1] : 18446744073709551616*floor((-8i1 +
o1)/18446744073709551616) = -8i1 + o1 and 0 <= o1 <= 18446744073709551608 }

If I understand the notation correctly, both have equal alias set (2). Do you
see Sebastian why the dependence is not caught?

Thanks

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #4 from Sebastian Pop  ---
The data dependence relations are dumped in the output of
-fdump-tree-graphite-all.
graphite-dependences.c contains the code for the data dependence computations.
Looking at the gimple code it seems like a trivial write after write
dependence.

Do we have a reduced testcase for this problem?

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

--- Comment #3 from Martin Liška  ---
Ok, fails with:

g++ -floop-nest-optimize -Ofast -w tramp3d-v4.cpp -fdump-tree-graphite-details
-$ fdbg-cnt=graphite_scop:4

Problem are following side-by-side loops:

[scheduler] original ast:
{
  for (int c0 = 0; c0 <= 2; c0 += 1)
S_3(c0);
  for (int c0 = 0; c0 <= 2; c0 += 1)
S_6(c0);
}

[scheduler] AST generated by isl:
{
  for (int c0 = 0; c0 <= 2; c0 += 1)
S_6(c0);
  for (int c0 = 0; c0 <= 2; c0 += 1)
S_3(c0);
}

which are interchanged. But due to fact that there's a data dependency:

...
   [75.00%]:
  # i_38 = PHI 
  _34 = (sizetype) i_38;
  _12 = _34 * 8;
  _7 =  + _12;
  _8 = s1_4(D) + _12;
  _9 = MEM[(int *)_8];
  MEM[(Element_t[2] &)_7][0] = _9; <- store to retval
  _10 = MEM[(int *)_8 + 4B];
  MEM[(Element_t[2] &)_7][1] = _10;
  i_11 = i_38 + 1;
  if (i_11 == 3)
goto ; [33.33%]
  else
goto ; [66.67%]

   [50.00%]:
  goto ; [100.00%]

   [25.00%]:

   [25.00%]:

   [75.00%]:
  # i_39 = PHI 
  _37 = (sizetype) i_39;
  _35 = _37 * 8;
  _13 = _3(D) + _35;
  _14 =  + _35;
  _15 = MEM[(int *)_14];
  MEM[(Element_t[2] &)_13][0] = _15; <-- load from retval, stored to _3+x
  _16 = MEM[(int *)_14 + 4B];
  MEM[(Element_t[2] &)_13][1] = _16;
  i_17 = i_39 + 1;
  if (i_17 == 3)
goto ; [33.33%]
  else
goto ; [66.67%]

   [50.00%]:
  goto ; [100.00%]
...

return _3(D);

I can work on that, but any hint where such dependency should be caught?

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

Richard Biener  changed:

   What|Removed |Added

   Priority|P4  |P2
   Target Milestone|--- |6.4

--- Comment #2 from Richard Biener  ---
wrong-code shouldn't be P4 even if it is graphite.

[Bug tree-optimization/68823] [6/7 Regression][graphite] tramp3d-v4 compiled with -floop-nest-optimize crashes

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68823

Martin Liška  changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2017-02-02
 CC||marxin at gcc dot gnu.org
Summary|[graphite] tramp3d-v4   |[6/7 Regression][graphite]
   |compiled with   |tramp3d-v4 compiled with
   |-floop-nest-optimize|-floop-nest-optimize
   |crashes |crashes
 Ever confirmed|0   |1

--- Comment #1 from Martin Liška  ---
Confirmed, started with r227567. I've got ISL 0.16.1.