isl_tab_basic_set_non_trivial_lexmin: do not add cuts for all variables
authorTobias Grosser <tobias@grosser.es>
Sat, 18 Feb 2012 15:13:23 +0000 (16:13 +0100)
committerSven Verdoolaege <skimo@kotnet.org>
Sun, 19 Feb 2012 17:29:52 +0000 (18:29 +0100)
commitb57971ad29e2acff5e02e6849d86b5b401c44759
tree06fb9819f8ddb7720d049d771460626876170954
parent089560ea6e901100ec4505b2b9341af84a0b0728
isl_tab_basic_set_non_trivial_lexmin: do not add cuts for all variables

We found a test case where adding cuts for all variables can increase
the time of the scheduling algorithm significantly (from ms to never
seen terminating). Even though we did not understand the problem
entirely, the intuition we have is the following:

When using isl_tab_basic_set_non_trivial_lexmin, the ILP problem is
(usually) not empty, but infinite. Adding all cuts, seems to increase
the objective function only in very small steps. Adding only one cut at
a time allows us to increase it with a step as big as possible.

This patch does not change the behaviour when calling
check_integer_feasible.  In case we're calling cut_to_integer_lexmin
from check_integer_feasible, if it takes a long time to compute, then
it's "usually" because the context is empty and it's just taking a long
time for us to discover that it's empty. We believe in that case it
could still make sense to add all cuts.

This patch was tested on polybench 2.0 with Polly and minimal fusion.
On the larger kernels, it could not solve any infinite scheduling time
problems, but it was able to speed up one test case by 2x and did not
yield increased scheduling time for the other test cases.

Signed-off-by: Tobias Grosser <tobias@grosser.es>
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_tab_pip.c
isl_test.c