------- Comment #31 from jakub at gcc dot gnu dot org 2010-06-04 09:24 ------- Created an attachment (id=20834) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20834&action=view) limit-depth.patch
Quick patch that brings the time down to 1 minute 15 sec. >From the callgrind dump on this testcase, intersect_loc_chains in 5159260x cases calls insert_into_intersection in the first loop (i.e. where the recent patch from this PR helps), then calls 320611x find_loc_in_1pdv. Out of these calls, 75537x it returns NULL and the rest of time it returns non-NULL. When it returns non-NULL, it is possible to return non-NULL without recursion 244863x, with one level of find_loc_in_1pdv recursion 205x and with two level recursion 6x. No successful call in this testcase needs deeper recursion. When not limiting the recursion depth, instead just monitoring it, for all cases where find_loc_in_1pdv returned non-NULL the depth at which return node; is used is at most 2 (0 is just find_loc_in_1pdv call with no recursion) and maximum depth ever recursed for the successful calls is 3. I believe the problem of this testcase is not the cases where find_loc_in_1pdv returns non-NULL. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41371
