diff options
| -rw-r--r-- | gcc/ChangeLog | 17 | ||||
| -rw-r--r-- | gcc/cfgloop.c | 11 | ||||
| -rw-r--r-- | gcc/flow.c | 131 | ||||
| -rw-r--r-- | gcc/function.h | 8 |
4 files changed, 149 insertions, 18 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7b1551883dd..eb1a9be39eb 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2005-02-19 Steven Bosscher <stevenb@suse.de> + + PR middle-end/19698 + * function.h (struct function): New field `max_loop_depth'. + * cfgloop.c (establish_preds): Update maximum loop depth seen so far. + (flow_loops_find): Reset the max loop depth count before finding loops. + * flow.c (MAX_LIVENESS_ROUNDS): New constant. + (update_life_info_in_dirty_blocks): Remove 2002-05-28 workaround. + (calculate_global_regs_live): Make sure the loop will terminate + when the initial sets are not empty. + 2005-02-19 Zack Weinberg <zack@codesourcery.com> * mklibgcc.in: If libgcc_eh.a would be empty, put a dummy @@ -125,8 +136,8 @@ 2005-02-18 Andrew Pinski <pinskia@physics.uc.edu> PR middle-end/20030 - * fold-const.c (fold_indirect_ref_1): Use the correct index for zero access, - the lower bound of the array type if it exists. + * fold-const.c (fold_indirect_ref_1): Use the correct index for zero + access, the lower bound of the array type if it exists. 2005-02-18 Alexandre Oliva <aoliva@redhat.com> @@ -764,7 +775,7 @@ * libgcc2.c (__divsc3, __divdc3, __divxc3, __divtc3, __mulsc3, __muldc3, __mulxc3, __multc3): New. * libgcc2.h: Declare them. - * libgcc-std.ver: Export them. + * libgcc-std.ver: Export them. * mklibgcc.in (lib2funcs): Build them. 2005-02-11 Steven Bosscher <stevenb@suse.de> diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 4fb687c1ab6..40a6de489cc 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "rtl.h" #include "hard-reg-set.h" #include "obstack.h" +#include "function.h" #include "basic-block.h" #include "toplev.h" #include "cfgloop.h" @@ -510,6 +511,10 @@ establish_preds (struct loop *loop) struct loop *ploop, *father = loop->outer; loop->depth = father->depth + 1; + + /* Remember the current loop depth if it is the largest seen so far. */ + cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth); + if (loop->pred) free (loop->pred); loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); @@ -819,6 +824,10 @@ flow_loops_find (struct loops *loops, int flags) memset (loops, 0, sizeof *loops); + /* We are going to recount the maximum loop depth, + so throw away the last count. */ + cfun->max_loop_depth = 0; + /* Taking care of this degenerate case makes the rest of this code simpler. */ if (n_basic_blocks == 0) @@ -1213,7 +1222,7 @@ remove_bb_from_loops (basic_block bb) loop->pred[i]->num_nodes--; bb->loop_father = NULL; bb->loop_depth = 0; - } +} /* Finds nearest common ancestor in loop tree for given loops. */ struct loop * diff --git a/gcc/flow.c b/gcc/flow.c index 503dc0dcdb3..172541d2fa5 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -165,6 +165,11 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #endif #endif +/* This is the maximum number of times we process any given block if the + latest loop depth count is smaller than this number. Only used for the + failure strategy to avoid infinite loops in calculate_global_regs_live. */ +#define MAX_LIVENESS_ROUNDS 20 + /* Nonzero if the second flow pass has completed. */ int flow2_completed; @@ -729,21 +734,10 @@ update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags sbitmap_zero (update_life_blocks); FOR_EACH_BB (bb) { - if (extent == UPDATE_LIFE_LOCAL) + if (bb->flags & BB_DIRTY) { - if (bb->flags & BB_DIRTY) - { - SET_BIT (update_life_blocks, bb->index); - n++; - } - } - else - { - /* ??? Bootstrap with -march=pentium4 fails to terminate - with only a partial life update. */ SET_BIT (update_life_blocks, bb->index); - if (bb->flags & BB_DIRTY) - n++; + n++; } } @@ -1010,6 +1004,9 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) { basic_block *queue, *qhead, *qtail, *qend, bb; regset tmp, new_live_at_end, invalidated_by_call; + regset registers_made_dead; + bool failure_strategy_required = false; + int *block_accesses; /* The registers that are modified within this in block. */ regset *local_sets; @@ -1030,6 +1027,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) tmp = ALLOC_REG_SET (®_obstack); new_live_at_end = ALLOC_REG_SET (®_obstack); invalidated_by_call = ALLOC_REG_SET (®_obstack); + registers_made_dead = ALLOC_REG_SET (®_obstack); /* Inconveniently, this is only readily available in hard reg set form. */ for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) @@ -1070,6 +1068,8 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) } } + block_accesses = xcalloc (last_basic_block, sizeof (int)); + /* We clean aux when we remove the initially-enqueued bbs, but we don't enqueue ENTRY and EXIT initially, so clean them upfront and unconditionally. */ @@ -1095,7 +1095,41 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) from GLOBAL_LIVE_AT_START. In the former case, the register could go away only if it disappeared from GLOBAL_LIVE_AT_START for one of the successor blocks. By induction, that cannot - occur. */ + occur. + + ??? This reasoning doesn't work if we start from non-empty initial + GLOBAL_LIVE_AT_START sets. And there are actually two problems: + 1) Updating may not terminate (endless oscillation). + 2) Even if it does (and it usually does), the resulting information + may be inaccurate. Consider for example the following case: + + a = ...; + while (...) {...} -- 'a' not mentioned at all + ... = a; + + If the use of 'a' is deleted between two calculations of liveness + information and the initial sets are not cleared, the information + about a's liveness will get stuck inside the loop and the set will + appear not to be dead. + + We do not attempt to solve 2) -- the information is conservatively + correct (i.e. we never claim that something live is dead) and the + amount of optimization opportunities missed due to this problem is + not significant. + + 1) is more serious. In order to fix it, we monitor the number of times + each block is processed. Once one of the blocks has been processed more + times than the maximum number of rounds, we use the following strategy: + When a register disappears from one of the sets, we add it to a MAKE_DEAD + set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and + add the blocks with changed sets into the queue. Thus we are guaranteed + to terminate (the worst case corresponds to all registers in MADE_DEAD, + in which case the original reasoning above is valid), but in general we + only fix up a few offending registers. + + The maximum number of rounds for computing liveness is the largest of + MAX_LIVENESS_ROUNDS and the latest loop depth count for this function. */ + while (qhead != qtail) { int rescan, changed; @@ -1108,6 +1142,17 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) qhead = queue; bb->aux = NULL; + /* Should we start using the failure strategy? */ + if (bb != ENTRY_BLOCK_PTR) + { + int max_liveness_rounds = + MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth); + + block_accesses[bb->index]++; + if (block_accesses[bb->index] > max_liveness_rounds) + failure_strategy_required = true; + } + /* Begin by propagating live_at_start from the successor blocks. */ CLEAR_REG_SET (new_live_at_end); @@ -1263,6 +1308,62 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end)) continue; + if (failure_strategy_required) + { + /* Get the list of registers that were removed from the + bb->global_live_at_start set. */ + bitmap_and_compl (tmp, bb->global_live_at_start, + new_live_at_end); + if (!bitmap_empty_p (tmp)) + { + bool pbb_changed; + basic_block pbb; + + /* It should not happen that one of registers we have + removed last time is disappears again before any other + register does. */ + pbb_changed = bitmap_ior_into (registers_made_dead, tmp); + gcc_assert (pbb_changed); + + /* Now remove the registers from all sets. */ + FOR_EACH_BB (pbb) + { + pbb_changed = false; + + pbb_changed + |= bitmap_and_compl_into (pbb->global_live_at_start, + registers_made_dead); + pbb_changed + |= bitmap_and_compl_into (pbb->global_live_at_end, + registers_made_dead); + if (!pbb_changed) + continue; + + /* Note the (possible) change. */ + if (blocks_out) + SET_BIT (blocks_out, pbb->index); + + /* Makes sure to really rescan the block. */ + if (local_sets[pbb->index - (INVALID_BLOCK + 1)]) + { + FREE_REG_SET (local_sets[pbb->index - (INVALID_BLOCK + 1)]); + FREE_REG_SET (cond_local_sets[pbb->index - (INVALID_BLOCK + 1)]); + local_sets[pbb->index - (INVALID_BLOCK + 1)] = 0; + } + + /* Add it to the queue. */ + if (pbb->aux == NULL) + { + *qtail++ = pbb; + if (qtail == qend) + qtail = queue; + pbb->aux = pbb; + } + } + continue; + } + } /* end of failure_strategy_required */ + COPY_REG_SET (bb->global_live_at_start, new_live_at_end); } @@ -1284,6 +1385,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) FREE_REG_SET (tmp); FREE_REG_SET (new_live_at_end); FREE_REG_SET (invalidated_by_call); + FREE_REG_SET (registers_made_dead); if (blocks_out) { @@ -1303,6 +1405,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) } } + free (block_accesses); free (queue); free (cond_local_sets); free (local_sets); diff --git a/gcc/function.h b/gcc/function.h index f760075c638..ef0f55a4c38 100644 --- a/gcc/function.h +++ b/gcc/function.h @@ -284,12 +284,20 @@ struct function GTY(()) int no_debugging_symbols; rtvec original_arg_vector; tree original_decl_initial; + /* Highest label number in current function. */ int inl_max_label_num; /* Function sequence number for profiling, debugging, etc. */ int funcdef_no; + /* For flow.c. */ + + /* Highest loop depth seen so far in loop analysis. Used in flow.c + for the "failure strategy" when doing liveness analysis starting + with non-empty initial sets. */ + int max_loop_depth; + /* For md files. */ /* tm.h can use this to store whatever it likes. */ |