This improves var-tracking dataflow convergence by using post order on the inverted CFG - which is appropriate for forward dataflow problems. This haves compile-time spent in var-tracking for PR45364 (it also improves other testcases, but that one seems to be the best case).
For this to pass bootstrap I had to fix PR59890, two latent bugs with the recently added local_get_addr_cache. Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk? Thanks, Richard. 2014-01-20 Richard Biener <rguent...@suse.de> PR rtl-optimization/45364 PR rtl-optimization/59890 * var-tracking.c (local_get_addr_clear_given_value): Handle already cleared slot. (val_reset): Handle not allocated local_get_addr_cache. (vt_find_locations): Use post-order on the inverted CFG. Index: gcc/var-tracking.c =================================================================== *** gcc/var-tracking.c (revision 206808) --- gcc/var-tracking.c (working copy) *************** static bool *** 2481,2487 **** local_get_addr_clear_given_value (const void *v ATTRIBUTE_UNUSED, void **slot, void *x) { ! if (vt_get_canonicalize_base ((rtx)*slot) == x) *slot = NULL; return true; } --- 2481,2488 ---- local_get_addr_clear_given_value (const void *v ATTRIBUTE_UNUSED, void **slot, void *x) { ! if (*slot != NULL ! && vt_get_canonicalize_base ((rtx)*slot) == x) *slot = NULL; return true; } *************** val_reset (dataflow_set *set, decl_or_va *** 2501,2507 **** gcc_assert (var->n_var_parts == 1); ! if (var->onepart == ONEPART_VALUE) { rtx x = dv_as_value (dv); void **slot; --- 2502,2509 ---- gcc_assert (var->n_var_parts == 1); ! if (var->onepart == ONEPART_VALUE ! && local_get_addr_cache != NULL) { rtx x = dv_as_value (dv); void **slot; *************** vt_find_locations (void) *** 6934,6945 **** bool success = true; timevar_push (TV_VAR_TRACKING_DATAFLOW); ! /* Compute reverse completion order of depth first search of the CFG so that the data-flow runs faster. */ ! rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS); bb_order = XNEWVEC (int, last_basic_block_for_fn (cfun)); ! pre_and_rev_post_order_compute (NULL, rc_order, false); ! for (i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; i++) bb_order[rc_order[i]] = i; free (rc_order); --- 6936,6947 ---- bool success = true; timevar_push (TV_VAR_TRACKING_DATAFLOW); ! /* Compute reverse top sord order of the inverted CFG so that the data-flow runs faster. */ ! rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); bb_order = XNEWVEC (int, last_basic_block_for_fn (cfun)); ! int num = inverted_post_order_compute (rc_order); ! for (i = 0; i < num; i++) bb_order[rc_order[i]] = i; free (rc_order);