From e9d297a15d68121ba5bdd5a76ea71c1916180622 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Fri, 29 Sep 2017 12:20:41 -0600 Subject: [PATCH] sbitmap.c (bitmap_bit_in_range_p): New function. * sbitmap.c (bitmap_bit_in_range_p): New function. * sbitmap.h (bitmap_bit_in_range_p): Prototype. * tree-ssa-dse.c (live_bytes_read): New function. (dse_classify_store): Ignore reads of dead bytes. * testsuite/gcc.dg/tree-ssa/ssa-dse-26.c: New test. From-SVN: r253305 --- gcc/ChangeLog | 5 +++ gcc/sbitmap.c | 53 ++++++++++++++++++++++++++++ gcc/sbitmap.h | 2 ++ gcc/testsuite/ChangeLog | 4 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c | 33 ++++++++++++++++++ gcc/tree-ssa-dse.c | 55 ++++++++++++++++++++++++++++++ 6 files changed, 152 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 16c9737..1932390 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,10 @@ 2017-09-29 Jeff Law + * sbitmap.c (bitmap_bit_in_range_p): New function. + * sbitmap.h (bitmap_bit_in_range_p): Prototype. + * tree-ssa-dse.c (live_bytes_read): New function. + (dse_classify_store): Ignore reads of dead bytes. + * config/i386/i386.c (ix86_adjust_stack_and_probe_stack_clash): Fix typos and whitespace errors. * config/i386/predicates.md (address_no_seg_operand): Likewise. diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index c065d13..4bf13a1 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -316,6 +316,59 @@ bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count) bmap->elms[start_word] |= mask; } +/* Return TRUE if any bit between START and END inclusive is set within + the simple bitmap BMAP. Return FALSE otherwise. */ + +bool +bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end) +{ + unsigned int start_word = start / SBITMAP_ELT_BITS; + unsigned int start_bitno = start % SBITMAP_ELT_BITS; + + /* Testing within a word, starting at the beginning of a word. */ + if (start_bitno == 0 && (end - start) < SBITMAP_ELT_BITS) + { + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << (end - start)) - 1; + return (bmap->elms[start_word] & mask) != 0; + } + + unsigned int end_word = end / SBITMAP_ELT_BITS; + unsigned int end_bitno = end % SBITMAP_ELT_BITS; + + /* Testing starts somewhere in the middle of a word. Test up to the + end of the word or the end of the requested region, whichever comes + first. */ + if (start_bitno != 0) + { + unsigned int nbits = ((start_word == end_word) + ? end_bitno - start_bitno + : SBITMAP_ELT_BITS - start_bitno); + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1; + mask <<= start_bitno; + if (bmap->elms[start_word] & mask) + return true; + start_word++; + } + + if (start_word > end_word) + return false; + + /* Now test words at a time until we hit a partial word. */ + unsigned int nwords = (end_word - start_word); + while (nwords) + { + if (bmap->elms[start_word]) + return true; + start_word++; + nwords--; + } + + /* Now handle residuals in the last word. */ + SBITMAP_ELT_TYPE mask + = ((SBITMAP_ELT_TYPE)1 << (SBITMAP_ELT_BITS - end_bitno)) - 1; + return (bmap->elms[start_word] & mask) != 0; +} + #if GCC_VERSION < 3400 /* Table of number of set bits in a character, indexed by value of char. */ static const unsigned char popcount_table[] = diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index ce4d27d..ff52e93 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. If not see * set_difference : bitmap_and_compl * set_disjuction : (not implemented) * set_compare : bitmap_equal_p + * bit_in_range_p : bitmap_bit_in_range_p Some operations on 3 sets that occur frequently in data flow problems are also implemented: @@ -253,6 +254,7 @@ extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); +extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int); extern int bitmap_first_set_bit (const_sbitmap); extern int bitmap_last_set_bit (const_sbitmap); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 94cedb7..890063c 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2017-09-29 Jeff Law + + * testsuite/gcc.dg/tree-ssa/ssa-dse-26.c: New test. + 2017-09-29 Jakub Jelinek P0683R1 - default member initializers for bit-fields diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c new file mode 100644 index 0000000..6605dfe --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c @@ -0,0 +1,33 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse1-details" } */ + +enum constraint_expr_type +{ + SCALAR, DEREF, ADDRESSOF +}; +typedef struct constraint_expr +{ + enum constraint_expr_type type; + unsigned int var; + long offset; +} constraint_expr ; +typedef struct constraint +{ + struct constraint_expr lhs; + struct constraint_expr rhs; +} constraint; +static _Bool +constraint_expr_equal (struct constraint_expr x, struct constraint_expr y) +{ + return x.type == y.type && x.var == y.var && x.offset == y.offset; +} + +_Bool +constraint_equal (struct constraint a, struct constraint b) +{ + return constraint_expr_equal (a.lhs, b.lhs) + && constraint_expr_equal (a.rhs, b.rhs); +} + +/* { dg-final { scan-tree-dump-times "Deleted dead store" 2 "dse1" } } */ + diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 70c8b07..1eca740 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -468,6 +468,36 @@ maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) } } +/* Return TRUE if USE_REF reads bytes from LIVE where live is + derived from REF, a write reference. + + While this routine may modify USE_REF, it's passed by value, not + location. So callers do not see those modifications. */ + +static bool +live_bytes_read (ao_ref use_ref, ao_ref *ref, sbitmap live) +{ + /* We have already verified that USE_REF and REF hit the same object. + Now verify that there's actually an overlap between USE_REF and REF. */ + if (ranges_overlap_p (use_ref.offset, use_ref.size, ref->offset, ref->size)) + { + normalize_ref (&use_ref, ref); + + /* If USE_REF covers all of REF, then it will hit one or more + live bytes. This avoids useless iteration over the bitmap + below. */ + if (use_ref.offset <= ref->offset + && use_ref.offset + use_ref.size >= ref->offset + ref->size) + return true; + + /* Now check if any of the remaining bits in use_ref are set in LIVE. */ + unsigned int start = (use_ref.offset - ref->offset) / BITS_PER_UNIT; + unsigned int end = (use_ref.offset + use_ref.size) / BITS_PER_UNIT; + return bitmap_bit_in_range_p (live, start, end); + } + return true; +} + /* A helper of dse_optimize_stmt. Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate statement *USE_STMT that may prove STMT to be dead. @@ -547,6 +577,31 @@ dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, /* If the statement is a use the store is not dead. */ else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) { + /* Handle common cases where we can easily build a ao_ref + structure for USE_STMT and in doing so we find that the + references hit non-live bytes and thus can be ignored. */ + if (live_bytes && (!gimple_vdef (use_stmt) || !temp)) + { + if (is_gimple_assign (use_stmt)) + { + /* Other cases were noted as non-aliasing by + the call to ref_maybe_used_by_stmt_p. */ + ao_ref use_ref; + ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); + if (valid_ao_ref_for_dse (&use_ref) + && use_ref.base == ref->base + && use_ref.size == use_ref.max_size + && !live_bytes_read (use_ref, ref, live_bytes)) + { + /* If this statement has a VDEF, then it is the + first store we have seen, so walk through it. */ + if (gimple_vdef (use_stmt)) + temp = use_stmt; + continue; + } + } + } + fail = true; BREAK_FROM_IMM_USE_STMT (ui); } -- 2.7.4