[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 Thomas Koenig changed: What|Removed |Added Status|WAITING |RESOLVED Resolution|--- |FIXED --- Comment #14 from Thomas Koenig --- Closing, then. If this should ever regress, we'll see it.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #13 from CVS Commits --- The master branch has been updated by Thomas Kथà¤nig : https://gcc.gnu.org/g:905ba62ec96f8469c1085861d9ceec58fbee5709 commit r11-1018-g905ba62ec96f8469c1085861d9ceec58fbee5709 Author: Thomas Koenig Date: Sun Jun 7 10:43:54 2020 +0200 Added test case for a PR which has been fixed in the meantime. gcc/testsuite/ChangeLog: PR tree-optimization/50439 * gfortran.dg/loop_interchange_2.f: New test.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 pthaugen at gcc dot gnu.org changed: What|Removed |Added CC||pthaugen at gcc dot gnu.org --- Comment #12 from pthaugen at gcc dot gnu.org --- I can no longer produce the condition either, with the reduced testcase or 416.gamess. So if you think the correct thing to do is close this bug I'm fine with that.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 Thomas Koenig changed: What|Removed |Added Ever confirmed|0 |1 CC||tkoenig at gcc dot gnu.org Status|UNCONFIRMED |WAITING Last reconfirmed||2020-06-01 --- Comment #11 from Thomas Koenig --- I just stumbled across this, and it seems fixed. Commit the test case and close?
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #10 from William J. Schmidt wschmidt at gcc dot gnu.org 2012-04-09 16:03:27 UTC --- FWIW, my original compile did eventually complete (after 31.5 hours)...
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
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). =
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 William J. Schmidt wschmidt at gcc dot gnu.org changed: What|Removed |Added CC||dberlin at gcc dot gnu.org, ||grosser at gcc dot gnu.org --- Comment #4 from William J. Schmidt wschmidt at gcc dot gnu.org 2012-04-06 12:13:50 UTC --- CCing the Graphite maintainers.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439
bagnara at cs dot unipr.it changed:
What|Removed |Added
CC||bagnara at cs dot unipr.it
--- Comment #5 from bagnara at cs dot unipr.it 2012-04-06 13:49:57 UTC ---
Here is a sketch (100% untested) of what can be done without intervening on the
specification of the function, that is, without giving up. The original
implementation was inefficient, by the way: if one element of the powerset was
found not to be empty, all the other elements were tested anyway instead of
immediately returning false. Whether it is best to try the MIP solver or the
PIP solver first is something to be determined experimentally.
bool
ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps)
{
ppl_dimension_type d;
ppl_Constraint_System_const_iterator_t first, last;
ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
bool has_integer_solutions = false;
/* FIXME: the following values should be determined experimentally. */
unsigned weight = 2;
unsigned weight_increment = 5000;
unsigned timeouts;
if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps))
return true;
while (true)
{
ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, d);
ppl_new_Constraint_System_const_iterator (first);
ppl_new_Constraint_System_const_iterator (last);
ppl_new_Pointset_Powerset_C_Polyhedron_iterator (it);
ppl_new_Pointset_Powerset_C_Polyhedron_iterator (end);
timeouts = 0;
for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
!ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
{
ppl_const_Polyhedron_t ph;
ppl_const_Constraint_System_t pcs;
ppl_Linear_Expression_t le;
ppl_MIP_Problem_t mip;
int ppl_result;
ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, ph);
ppl_Polyhedron_get_constraints (ph, pcs);
/* Try with the MIP solver first. */
ppl_new_Linear_Expression (le);
ppl_new_MIP_Problem (mip, d, pcs, le,
PPL_OPTIMIZATION_MODE_MAXIMIZATION);
ppl_set_deterministic_timeout (weight);
ppl_result = ppl_MIP_Problem_is_satisfiable (mip);
ppl_reset_deterministic_timeout ();
ppl_delete_MIP_Problem (mip);
if (ppl_result == PPL_TIMEOUT_EXCEPTION)
{
/* Deterministic timeout expired: try with the PIP solver. */
ppl_PIP_Problem_t pip;
ppl_Constraint_System_begin (pcs, first);
ppl_Constraint_System_end (pcs, last);
ppl_new_PIP_Problem_from_constraints (pip, d, first, last, 0,
NULL);
ppl_set_deterministic_timeout (weight);
ppl_result = ppl_PIP_Problem_is_satisfiable (pip);
ppl_reset_deterministic_timeout ();
ppl_delete_PIP_Problem (pip);
if (ppl_result == PPL_TIMEOUT_EXCEPTION)
++timeouts;
else if (ppl_result 0)
{
has_integer_solutions = true;
break;
}
}
else if (ppl_result 0)
{
has_integer_solutions = true;
break;
}
}
ppl_delete_Constraint_System_const_iterator (first);
ppl_delete_Constraint_System_const_iterator (last);
ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
/* If there were no timeouts, then we have the answer. */
if (timeouts == 0)
return !has_integer_solutions;
if (weight = UINT_MAX - weight_increment)
weight += weight_increment;
}
}
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #6 from bagnara at cs dot unipr.it 2012-04-06 14:04:09 UTC --- Created attachment 27104 -- http://gcc.gnu.org/bugzilla/attachment.cgi?id=27104 Example alternative implementation for ppl_powerset_is_empty ()
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #7 from bagnara at cs dot unipr.it 2012-04-06 14:06:38 UTC --- (In reply to comment #5) Here is a sketch (100% untested) of what can be done without intervening [...] So untested that I forgot to declare to the MIP problem that all variables are integer. I have attached a file (example1.c) where this is corrected.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #8 from William J. Schmidt wschmidt at gcc dot gnu.org 2012-04-06 19:08:09 UTC --- Roberto, I tried your patch, but got the following error: PPL error code -8 PPL C interface error: ppl_set_deterministic_timeout: the PPL Watchdog library is not enabled. I assume this is a configuration feature for PPL that GCC doesn't enable. I wonder if there are portability concerns here. Graphite maintainers, can you please comment? I'm afraid I know practically nothing about Graphite.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #9 from bagnara at cs dot unipr.it 2012-04-06 19:17:25 UTC --- Pity it is not enabled: it definitely should. Note that the addition of the deterministic timeout facility of the PPL was solicited by the Graphite people. Previously the PPL only supported timeouts based on wall-clock time, which resulted in non-determinism that is unacceptable in GCC.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #1 from William J. Schmidt wschmidt at gcc dot gnu.org 2012-04-05 16:47:32 UTC --- I verified that the looping occurs inside the PPL library, on a call to ppl_PIP_Problem_is_satisfiable. I used ppl_PIP_Problem_ascii_dump to examine the pip variable passed into that routine: external_space_dim: 32 internal_space_dim: 0 input_cs( 38 ) size 33 0 0 162 0 1 0 9 0 1620 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 f -RPI_V -RPI -NNC_V -NNC size 33 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 162 0 1 0 9 0 1620 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 162 0 1 0 9 0 1620 0 0 0 0 0 0 -162 0 -1 0 -9 0 0 0 0 0 0 -1620 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 162 0 1 0 9 0 1620 0 0 0 0 0 0 -162 0 -1 0 -9 0 -1620 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V -RPI -NNC_V -NNC size 33 -1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 6480 0 -162 0 -1 0 -9 0 -1620 0 0 0 0 0 0 162 0 1 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 9 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 8 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 17 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC size 33 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f -RPI_V +RPI -NNC_V -NNC first_pending_constraint: 0 status: PARTIALLY_SATISFIABLE parameters variables( 0 ) initial_context 0 x 0 control_parameters CUTTING_STRATEGY_FIRST PIVOT_ROW_STRATEGY_FIRST big_parameter_dimension: 18446744073709551615 current_solution: BOTTOM It appears we'll need to report this to the PPL folks. I'll get an account over there and point them to this PR.
[Bug tree-optimization/50439] gfortran infinite loop with -floop-interchange
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50439 --- Comment #2 from William J. Schmidt wschmidt at gcc dot gnu.org 2012-04-05 17:06:47 UTC --- Opened a bug report as https://www.cs.unipr.it/mantis/view.php?id=353 against PPL.
