From 55994078b6bc51ae62bd4117c6c335b94336137b Mon Sep 17 00:00:00 2001 From: Nathan Sidwell Date: Tue, 2 Nov 2004 09:56:12 +0000 Subject: [PATCH] bitmap.h (bitmap_equal_p): Return bool. * bitmap.h (bitmap_equal_p): Return bool. (bitmap_intersect_p, bitmap_intersect_compl_p): Declare. * bitmap.c (bitmap_equal_p): Return bool. Compare directly. (bitmap_intersect_p, bitmap_intersect_compl_p): New. * flow.c (calculate_global_regs_live): Use bitmap_intersect_p and bitmap_intersect_compl_p. * ifcvt (dead_or_predicable): Likewise. From-SVN: r89981 --- gcc/ChangeLog | 10 ++++++++ gcc/bitmap.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++------ gcc/bitmap.h | 10 +++++++- gcc/flow.c | 48 ++++++++++++++++------------------- gcc/ifcvt.c | 10 +++----- 5 files changed, 116 insertions(+), 43 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f581d1a..87d7e07 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,15 @@ 2004-11-02 Nathan Sidwell + * bitmap.h (bitmap_equal_p): Return bool. + (bitmap_intersect_p, bitmap_intersect_compl_p): Declare. + * bitmap.c (bitmap_equal_p): Return bool. Compare directly. + (bitmap_intersect_p, bitmap_intersect_compl_p): New. + * flow.c (calculate_global_regs_live): Use bitmap_intersect_p and + bitmap_intersect_compl_p. + * ifcvt (dead_or_predicable): Likewise. + +2004-11-02 Nathan Sidwell + PR rtl-optimization/17104 * config/rs6000/rs6000.c (rs6000_emit_move): Don't wrap small loads in zero_extend. diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 0a50d41..c78912b 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -663,20 +663,85 @@ bitmap_operation (bitmap to, bitmap from1, bitmap from2, return changed; } -/* Return true if two bitmaps are identical. */ +/* Return true if two bitmaps are identical. + We do not bother with a check for pointer equality, as that never + occurs in practice. */ -int +bool bitmap_equal_p (bitmap a, bitmap b) { - bitmap_head c; - int ret; + bitmap_element *a_elt; + bitmap_element *b_elt; + unsigned ix; + + for (a_elt = a->first, b_elt = b->first; + a_elt && b_elt; + a_elt = a_elt->next, b_elt = b_elt->next) + { + if (a_elt->indx != b_elt->indx) + return false; + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + if (a_elt->bits[ix] != b_elt->bits[ix]) + return false; + } + return !a_elt && !b_elt; +} + +/* Return true if A AND B is not empty. */ + +bool +bitmap_intersect_p (bitmap a, bitmap b) +{ + bitmap_element *a_elt; + bitmap_element *b_elt; + unsigned ix; + + for (a_elt = a->first, b_elt = b->first; + a_elt && b_elt;) + { + if (a_elt->indx < b_elt->indx) + a_elt = a_elt->next; + else if (b_elt->indx < a_elt->indx) + b_elt = b_elt->next; + else + { + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + if (a_elt->bits[ix] & b_elt->bits[ix]) + return true; + a_elt = a_elt->next; + b_elt = b_elt->next; + } + } + return false; +} - memset (&c, 0, sizeof (c)); - ret = ! bitmap_xor (&c, a, b); - bitmap_clear (&c); +/* Return true if A AND NOT B is not empty. */ - return ret; +bool +bitmap_intersect_compl_p (bitmap a, bitmap b) +{ + bitmap_element *a_elt; + bitmap_element *b_elt; + unsigned ix; + for (a_elt = a->first, b_elt = b->first; + a_elt && b_elt;) + { + if (a_elt->indx < b_elt->indx) + return true; + else if (b_elt->indx < a_elt->indx) + b_elt = b_elt->next; + else + { + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + if (a_elt->bits[ix] & ~b_elt->bits[ix]) + return true; + a_elt = a_elt->next; + b_elt = b_elt->next; + } + } + return a_elt != NULL; } + /* Or into bitmap TO bitmap FROM1 and'ed with the complement of bitmap FROM2. */ diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 67eb9d2..767fafa 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -85,8 +85,16 @@ extern void bitmap_clear (bitmap); extern void bitmap_copy (bitmap, bitmap); /* True if two bitmaps are identical. */ -extern int bitmap_equal_p (bitmap, bitmap); +extern bool bitmap_equal_p (bitmap, bitmap); +/* True if the bitmaps intersect (their AND is non-empty). */ +extern bool bitmap_intersect_p (bitmap, bitmap); + +/* True if the complement of the second intersects the first (their + AND_COMPL is non-empty). */ +extern bool bitmap_intersect_compl_p (bitmap, bitmap); + +/* True if MAP is an empty bitmap. */ #define bitmap_empty_p(MAP) (!(MAP)->first) /* Perform an operation on two bitmaps, yielding a third. */ diff --git a/gcc/flow.c b/gcc/flow.c index 6e599c8..163e5c9 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -1185,38 +1185,32 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags) rescan the block. This wouldn't be necessary if we had precalculated local_live, however with PROP_SCAN_DEAD_CODE local_live is really dependent on live_at_end. */ - CLEAR_REG_SET (tmp); - rescan = bitmap_and_compl (tmp, bb->global_live_at_end, - new_live_at_end); - - if (! rescan) - { - /* If any of the registers in the new live_at_end set are - conditionally set in this basic block, we must rescan. - This is because conditional lifetimes at the end of the - block do not just take the live_at_end set into account, - but also the liveness at the start of each successor - block. We can miss changes in those sets if we only - compare the new live_at_end against the previous one. */ - CLEAR_REG_SET (tmp); - rescan = bitmap_and (tmp, new_live_at_end, - bb->cond_local_set); - } - - if (! rescan) + rescan = bitmap_intersect_compl_p (bb->global_live_at_end, + new_live_at_end); + + if (!rescan) + /* If any of the registers in the new live_at_end set are + conditionally set in this basic block, we must rescan. + This is because conditional lifetimes at the end of the + block do not just take the live_at_end set into + account, but also the liveness at the start of each + successor block. We can miss changes in those sets if + we only compare the new live_at_end against the + previous one. */ + rescan = bitmap_intersect_p (new_live_at_end, + bb->cond_local_set); + + if (!rescan) { /* Find the set of changed bits. Take this opportunity to notice that this set is empty and early out. */ - CLEAR_REG_SET (tmp); - changed = bitmap_xor (tmp, bb->global_live_at_end, - new_live_at_end); - if (! changed) + bitmap_xor (tmp, bb->global_live_at_end, new_live_at_end); + if (bitmap_empty_p (tmp)) continue; - + /* If any of the changed bits overlap with local_set, - we'll have to rescan the block. Detect overlap by - the AND with ~local_set turning off bits. */ - rescan = bitmap_and_compl_into (tmp, bb->local_set); + we'll have to rescan the block. */ + rescan = bitmap_intersect_p (tmp, bb->local_set); } } diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c index 72bb393..a033f35 100644 --- a/gcc/ifcvt.c +++ b/gcc/ifcvt.c @@ -3217,13 +3217,9 @@ dead_or_predicable (basic_block test_bb, basic_block merge_bb, TEST_SET & merge_bb->global_live_at_start are empty. */ - bitmap_ior (tmp, test_set, test_live); - bitmap_and_into (tmp, merge_set); - if (!bitmap_empty_p (tmp)) - fail = 1; - - bitmap_and (tmp, test_set, merge_bb->global_live_at_start); - if (!bitmap_empty_p (tmp)) + if (bitmap_intersect_p (test_set, merge_set) + || bitmap_intersect_p (test_live, merge_set) + || bitmap_intersect_p (test_set, merge_bb->global_live_at_start)) fail = 1; FREE_REG_SET (tmp); -- 2.7.4