[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange

["wschmidt at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-04-06 12:09:47 UTC ---
PPL administrator "bagnara" was very helpful in investigating this.

The PPL code is not actually looping, but simply is taking a very long time to
analyze a large input set.  The "PIP problem" has no integer solutions, and
this algorithm has a difficult time determining that.

bagnara also indicated that GCC is not using ppl_PIP_Problem_is_satisfiable
correctly.  Following are his comments:

================================================================================
I have checked the GCC sources. The problem is that
ppl_PIP_Problem_is_satisfiable() and several other functions that involve
algorithms of exponential complexity are used unguarded. The right thing to do
is to use the deterministic timeout facility of the PPL. See
ppl-0.11.2/interfaces/C/tests/weightwatch1.c for an example using the C
interface.

Moreover, there appears to be a design problem in functions such as

/* Checks for integer feasibility: returns true when the powerset
   polyhedron PS has no integer solutions. */
bool
ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps);

The output of such a function should be a tristate: (1) there are integer
solutions; (2) there are no integer solutions; (3) don't know (it was not
possible to decide the question due to time/space limitations).

Alternatively, one could change the name and the specification:

/* Checks for integer feasibility: returns true when the powerset
   polyhedron PS has no integer solutions; returns false if PS
   has integer solutions or the analysis was inconclusive. */
bool
ppl_powerset_is_definitely_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps);

Concerning the implementation, besides using the deterministic timeout facility
of the PPL, you should also use MIP_Problem in addition to PIP_Problem: try the
second one with timeout; upon timeout try the first one. For the specific
testcase, MIP_Problem immediately answers that there are no integer solutions
(it is easy to come up with testcases where MIP_Problem takes a lot of time and
PIP_Problem does much better). 
=============================================================================