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