[Bug tree-optimization/59121] [4.8/4.9 Regression] endless loop with -O2 -floop-parallelize-all

[grosser at gcc dot gnu.org]

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

--- Comment #18 from Tobias Grosser <grosser at gcc dot gnu.org> ---
(In reply to Mircea Namolaru from comment #17)
> Yes, data dependencies computation is expensive in the polyehdral model
> and it could take considerable time - but it is worrying that in too many
> cases fails to provide (after a few hours left running, when I stop it) an
> answer for very simple programs. I will ckeck with the isl people if this is
> the expected behaviour of the isl_union_map_compute_flow (this is the
> function where the data dependency computation is stuck) and how (and if)
> they could help us.

I would like to state that data-dependence calculation is not inherently more
complex in the polyhedral mode. In fact, any simple data-dependence test that
exists could be implemented in our polyhedral checker to speed up the common
case if really necessary. We did not do this, as for such simple cases the
dependence analysis is normally very fast. In the general case, dependence
solving is inherently complex (equivalent to ILP programming -> NP-complete),
and we can
not do better anyway.

Though for the most cases of slowdown, we could probably do better. For this it
is
necessary to understand why a certain case is slow. Hence, it is important to
look into the dependence problem we are trying to solve and see why we can not
solve it quickly. The problem may be inherently complex, but there may also be
a simple fix.

> Many Fortran programs with loops having no-constants bounds and
> n-dimensional arrays (n>=3) may be affected by this problem and may work
> only for small
> dimensions of the arrays. 
> The problem touches especially Fortran, that uses
> linearized accesses to multi-dimensional arrays - this creates patterns 
> leading to this problem (in this example we have an array acc of dimension
> 55,48,49 and the array access acc(j,k,l) is transformed to acc(j + 55*k +
> 2640*l).

So what exactly makes the problem difficult? Without understanding this, it is
very difficult to predict in which situations the dependence analysis will be
slow.

> I've checked the constraints passed to isl_union_map_compute

You mean isl_union_map_compute_flow()

> - see that
> wrapping is perfromed. But wrapping requires modulo operation, expressed by
> constraints with existential quantifier that may be harder to solve.

This is an interesting observation. Instead of modeling the modulo wrapping,
we could assume it does not exist and just add a run-time check around
the kernel that ensures that we only execute kernels where we know this is the
case.

> By
> disabling the wrapping, some simple examples that before were stuck in data
> dependency computation finish immediately.

Nice.

> In what measure is wrapping
> necessary ? - as a side-effect it may increase compilation time (that may be
> already considerable).

In some cases additions/multiplications have defined the semantics in case of
overflow as the computation being performed modulo the size of the type. This
case rarely happens, but in case we want to be correct, we can not just ignore
it.

Cheers,
Tobias