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

[mircea.namolaru at inria dot fr]

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

--- Comment #17 from Mircea Namolaru <mircea.namolaru at inria dot fr> ---
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.

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).

I've checked the constraints passed to isl_union_map_compute - see that
wrapping is perfromed. But wrapping requires modulo operation, expressed by
constraints with existential quantifier that may be harder to solve. By
disabling the wrapping, some simple examples that before were stuck in data
dependency computation finish immediately. In what measure is wrapping
necessary ? - as a side-effect it may increase compilation time (that may be
already considerable).