diff options
| -rw-r--r-- | gcc/ChangeLog | 9 | ||||
| -rw-r--r-- | gcc/df.c | 414 |
2 files changed, 263 insertions, 160 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index e6ec65b..2450132 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2001-11-25 Daniel Berlin <dan@cgsoftware.com> + + * df.c: Add prototypes for hybrid_search_bitmap and + hybrid_search_sbitmap. + (hybrid_search_bitmap): New function. + (hybrid_search_sbitmap): New function. + (iterative_dataflow_sbitmap): Change to use hybrid_search_sbitmap. + (iterative_dataflow_bitmap): Ditto. + 2001-11-25 Stephane Carrez <Stephane.Carrez@worldnet.fr> * config/m68hc11/m68hc11.md (peephole2): New peephole2 to optimize @@ -301,6 +301,16 @@ static void df_ru_transfer_function PARAMS ((int, int *, bitmap, bitmap, bitmap, bitmap, void *)); static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap, bitmap, bitmap, void *)); +static void hybrid_search_bitmap PARAMS ((basic_block, bitmap *, bitmap *, + bitmap *, bitmap *, enum df_flow_dir, + enum df_confluence_op, + transfer_function_bitmap, + sbitmap, sbitmap, void *)); +static void hybrid_search_sbitmap PARAMS ((basic_block, sbitmap *, sbitmap *, + sbitmap *, sbitmap *, enum df_flow_dir, + enum df_confluence_op, + transfer_function_sbitmap, + sbitmap, sbitmap, void *)); static inline bool read_modify_subreg_p PARAMS ((rtx)); @@ -1014,7 +1024,6 @@ df_uses_record (df, loc, ref_type, bb, insn, flags) { RTX_CODE code; rtx x; - retry: x = *loc; if (!x) @@ -1928,7 +1937,6 @@ df_luids_set (df, blocks) return total; } - /* Perform dataflow analysis using existing DF structure for blocks within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */ static void @@ -3588,82 +3596,32 @@ debug_df_chain (link) fputc ('\n', stderr); } -/* gen = GEN set. - kill = KILL set. - in, out = Filled in by function. - blocks = Blocks to analyze. - dir = Dataflow direction. - conf_op = Confluence operation. - transfun = Transfer function. - order = Order to iterate in. (Should map block numbers -> order) - data = Whatever you want. It's passed to the transfer function. - - This function will perform iterative bitvector dataflow, producing - the in and out sets. Even if you only want to perform it for a - small number of blocks, the vectors for in and out must be large - enough for *all* blocks, because changing one block might affect - others. However, it'll only put what you say to analyze on the - initial worklist. - - For forward problems, you probably want to pass in a mapping of - block number to rc_order (like df->inverse_rc_map). -*/ - -void -iterative_dataflow_sbitmap (in, out, gen, kill, blocks, - dir, conf_op, transfun, order, data) - sbitmap *in, *out, *gen, *kill; - bitmap blocks; +/* Hybrid search algorithm from "Implementation Techniques for + Efficient Data-Flow Analysis of Large Programs". */ +static void +hybrid_search_bitmap (block, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data) + basic_block block; + bitmap *in, *out, *gen, *kill; enum df_flow_dir dir; enum df_confluence_op conf_op; - transfer_function_sbitmap transfun; - int *order; + transfer_function_bitmap transfun; + sbitmap visited; + sbitmap pending; void *data; { int changed; - int i; - fibheap_t worklist; - sbitmap onqueue; - basic_block bb; - onqueue = sbitmap_alloc (n_basic_blocks); - sbitmap_zero (onqueue); - worklist = fibheap_new (); - EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, - { - fibheap_insert (worklist, order[i], (void *) i); - SET_BIT (onqueue, i); - if (dir == FORWARD) - { - sbitmap_copy (out[i], gen[i]); - } - else - { - sbitmap_copy (in[i], gen[i]); - } - - }); - while (!fibheap_empty (worklist)) + int i = block->index; + edge e; + basic_block bb= block; + SET_BIT (visited, block->index); + if (TEST_BIT (pending, block->index)) { - edge e; - i = (int) fibheap_extract_min (worklist); - changed = 0; - bb = BASIC_BLOCK (i); - RESET_BIT (onqueue, i); if (dir == FORWARD) { /* Calculate <conf_op> of predecessor_outs */ - for (e = bb->pred; e != 0; e = e->pred_next) - { - if (e->src == ENTRY_BLOCK_PTR) - { - sbitmap_zero (in[i]); - continue; - } - sbitmap_copy (in[i], out[e->src->index]); - break; - } - if (e == 0) - sbitmap_zero (in[i]); + bitmap_zero (in[i]); for (e = bb->pred; e != 0; e = e->pred_next) { if (e->src == ENTRY_BLOCK_PTR) @@ -3671,10 +3629,10 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks, switch (conf_op) { case UNION: - sbitmap_a_or_b (in[i], in[i], out[e->src->index]); + bitmap_a_or_b (in[i], in[i], out[e->src->index]); break; case INTERSECTION: - sbitmap_a_and_b (in[i], in[i], out[e->src->index]); + bitmap_a_and_b (in[i], in[i], out[e->src->index]); break; } } @@ -3682,7 +3640,7 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks, else { /* Calculate <conf_op> of successor ins */ - sbitmap_zero (out[i]); + bitmap_zero(out[i]); for (e = bb->succ; e != 0; e = e->succ_next) { if (e->dest == EXIT_BLOCK_PTR) @@ -3690,104 +3648,91 @@ iterative_dataflow_sbitmap (in, out, gen, kill, blocks, switch (conf_op) { case UNION: - sbitmap_a_or_b (out[i], out[i], in[e->dest->index]); + bitmap_a_or_b (out[i], out[i], in[e->dest->index]); break; case INTERSECTION: - sbitmap_a_and_b (out[i], out[i], in[e->dest->index]); + bitmap_a_and_b (out[i], out[i], in[e->dest->index]); break; } } } /* Common part */ (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data); - + RESET_BIT (pending, i); if (changed) { if (dir == FORWARD) { for (e = bb->succ; e != 0; e = e->succ_next) { - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i) continue; - if (!TEST_BIT (onqueue, e->dest->index)) - { - SET_BIT (onqueue, e->dest->index); - fibheap_insert (worklist, - order[e->dest->index], - (void *)e->dest->index); - } + SET_BIT (pending, e->dest->index); } } else { for (e = bb->pred; e != 0; e = e->pred_next) { - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i) continue; - if (!TEST_BIT (onqueue, e->src->index)) - { - SET_BIT (onqueue, e->src->index); - fibheap_insert (worklist, - order[e->src->index], - (void *)e->src->index); - } - + SET_BIT (pending, e->src->index); } } } } - sbitmap_free (onqueue); - fibheap_delete (worklist); - + if (dir == FORWARD) + { + for (e = bb->succ; e != 0; e = e->succ_next) + { + if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i) + continue; + if (!TEST_BIT (visited, e->dest->index)) + hybrid_search_bitmap (e->dest, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + } + else + { + for (e = bb->pred; e != 0; e = e->pred_next) + { + if (e->src == ENTRY_BLOCK_PTR || e->src->index == i) + continue; + if (!TEST_BIT (visited, e->src->index)) + hybrid_search_bitmap (e->src, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + } } -/* Exactly the same as iterative_dataflow_sbitmap, except it works on - bitmaps instead */ -void -iterative_dataflow_bitmap (in, out, gen, kill, blocks, - dir, conf_op, transfun, order, data) - bitmap *in, *out, *gen, *kill; - bitmap blocks; + + +/* Hybrid search for sbitmaps, rather than bitmaps. */ +static void +hybrid_search_sbitmap (block, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data) + basic_block block; + sbitmap *in, *out, *gen, *kill; enum df_flow_dir dir; enum df_confluence_op conf_op; - transfer_function_bitmap transfun; - int *order; + transfer_function_sbitmap transfun; + sbitmap visited; + sbitmap pending; void *data; { int changed; - int i; - fibheap_t worklist; - sbitmap onqueue; - basic_block bb; - - onqueue = sbitmap_alloc (n_basic_blocks); - sbitmap_zero (onqueue); - worklist = fibheap_new (); - EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, - { - fibheap_insert (worklist, order[i], (void *) i); - SET_BIT (onqueue, i); - if (dir == FORWARD) - { - bitmap_copy (out[i], gen[i]); - } - else - { - bitmap_copy (in[i], gen[i]); - } - - }); - while (!fibheap_empty (worklist)) - { - edge e; - i = (int) fibheap_extract_min (worklist); - changed = 0; - bb = BASIC_BLOCK (i); - RESET_BIT (onqueue, i); - + int i = block->index; + edge e; + basic_block bb= block; + SET_BIT (visited, block->index); + if (TEST_BIT (pending, block->index)) + { if (dir == FORWARD) { /* Calculate <conf_op> of predecessor_outs */ - bitmap_zero (in[i]); + sbitmap_zero (in[i]); for (e = bb->pred; e != 0; e = e->pred_next) { if (e->src == ENTRY_BLOCK_PTR) @@ -3795,10 +3740,10 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks, switch (conf_op) { case UNION: - bitmap_a_or_b (in[i], in[i], out[e->src->index]); + sbitmap_a_or_b (in[i], in[i], out[e->src->index]); break; case INTERSECTION: - bitmap_a_and_b (in[i], in[i], out[e->src->index]); + sbitmap_a_and_b (in[i], in[i], out[e->src->index]); break; } } @@ -3806,7 +3751,7 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks, else { /* Calculate <conf_op> of successor ins */ - bitmap_zero(out[i]); + sbitmap_zero(out[i]); for (e = bb->succ; e != 0; e = e->succ_next) { if (e->dest == EXIT_BLOCK_PTR) @@ -3814,53 +3759,202 @@ iterative_dataflow_bitmap (in, out, gen, kill, blocks, switch (conf_op) { case UNION: - bitmap_a_or_b (out[i], out[i], in[e->dest->index]); + sbitmap_a_or_b (out[i], out[i], in[e->dest->index]); break; case INTERSECTION: - bitmap_a_and_b (out[i], out[i], in[e->dest->index]); + sbitmap_a_and_b (out[i], out[i], in[e->dest->index]); break; } } } /* Common part */ (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data); - + RESET_BIT (pending, i); if (changed) { if (dir == FORWARD) { for (e = bb->succ; e != 0; e = e->succ_next) { - if (e->dest == EXIT_BLOCK_PTR) + if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i) continue; - if (!TEST_BIT (onqueue, e->dest->index)) - { - SET_BIT (onqueue, e->dest->index); - fibheap_insert (worklist, - order[e->dest->index], - (void *)e->dest->index); - } + SET_BIT (pending, e->dest->index); } } else { for (e = bb->pred; e != 0; e = e->pred_next) { - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i) continue; - if (!TEST_BIT (onqueue, e->src->index)) - { - SET_BIT (onqueue, e->src->index); - fibheap_insert (worklist, - order[e->src->index], - (void *)e->src->index); - } - + SET_BIT (pending, e->src->index); } } } } - sbitmap_free (onqueue); + if (dir == FORWARD) + { + for (e = bb->succ; e != 0; e = e->succ_next) + { + if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i) + continue; + if (!TEST_BIT (visited, e->dest->index)) + hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + } + else + { + for (e = bb->pred; e != 0; e = e->pred_next) + { + if (e->src == ENTRY_BLOCK_PTR || e->src->index == i) + continue; + if (!TEST_BIT (visited, e->src->index)) + hybrid_search_sbitmap (e->src, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + } +} + + + + +/* gen = GEN set. + kill = KILL set. + in, out = Filled in by function. + blocks = Blocks to analyze. + dir = Dataflow direction. + conf_op = Confluence operation. + transfun = Transfer function. + order = Order to iterate in. (Should map block numbers -> order) + data = Whatever you want. It's passed to the transfer function. + + This function will perform iterative bitvector dataflow, producing + the in and out sets. Even if you only want to perform it for a + small number of blocks, the vectors for in and out must be large + enough for *all* blocks, because changing one block might affect + others. However, it'll only put what you say to analyze on the + initial worklist. + + For forward problems, you probably want to pass in a mapping of + block number to rc_order (like df->inverse_rc_map). +*/ +void +iterative_dataflow_sbitmap (in, out, gen, kill, blocks, + dir, conf_op, transfun, order, data) + sbitmap *in, *out, *gen, *kill; + bitmap blocks; + enum df_flow_dir dir; + enum df_confluence_op conf_op; + transfer_function_sbitmap transfun; + int *order; + void *data; +{ + int i; + fibheap_t worklist; + basic_block bb; + sbitmap visited, pending; + pending = sbitmap_alloc (n_basic_blocks); + visited = sbitmap_alloc (n_basic_blocks); + sbitmap_zero (pending); + sbitmap_zero (visited); + worklist = fibheap_new (); + EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, + { + fibheap_insert (worklist, order[i], (void *) i); + SET_BIT (pending, i); + if (dir == FORWARD) + sbitmap_copy (out[i], gen[i]); + else + sbitmap_copy (in[i], gen[i]); + }); + while (sbitmap_first_set_bit (pending) != -1) + { + while (!fibheap_empty (worklist)) + { + i = (int) fibheap_extract_min (worklist); + bb = BASIC_BLOCK (i); + if (!TEST_BIT (visited, bb->index)) + hybrid_search_sbitmap (bb, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + if (sbitmap_first_set_bit (pending) != -1) + { + EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, + { + fibheap_insert (worklist, order[i], (void *) i); + }); + sbitmap_zero (visited); + } + else + { + break; + } + } + sbitmap_free (pending); + sbitmap_free (visited); fibheap_delete (worklist); - +} + +/* Exactly the same as iterative_dataflow_sbitmap, except it works on + bitmaps instead */ +void +iterative_dataflow_bitmap (in, out, gen, kill, blocks, + dir, conf_op, transfun, order, data) + bitmap *in, *out, *gen, *kill; + bitmap blocks; + enum df_flow_dir dir; + enum df_confluence_op conf_op; + transfer_function_bitmap transfun; + int *order; + void *data; +{ + int i; + fibheap_t worklist; + basic_block bb; + sbitmap visited, pending; + pending = sbitmap_alloc (n_basic_blocks); + visited = sbitmap_alloc (n_basic_blocks); + sbitmap_zero (pending); + sbitmap_zero (visited); + worklist = fibheap_new (); + EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, + { + fibheap_insert (worklist, order[i], (void *) i); + SET_BIT (pending, i); + if (dir == FORWARD) + bitmap_copy (out[i], gen[i]); + else + bitmap_copy (in[i], gen[i]); + }); + while (sbitmap_first_set_bit (pending) != -1) + { + while (!fibheap_empty (worklist)) + { + i = (int) fibheap_extract_min (worklist); + bb = BASIC_BLOCK (i); + if (!TEST_BIT (visited, bb->index)) + hybrid_search_bitmap (bb, in, out, gen, kill, dir, + conf_op, transfun, visited, pending, + data); + } + if (sbitmap_first_set_bit (pending) != -1) + { + EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, + { + fibheap_insert (worklist, order[i], (void *) i); + }); + sbitmap_zero (visited); + } + else + { + break; + } + } + sbitmap_free (pending); + sbitmap_free (visited); + fibheap_delete (worklist); } |