| Message ID | 20131025091925.GG30970@tucnak.zalov.cz |
|---|---|
| State | New |
| Headers | show |
On Fri, 25 Oct 2013, Jakub Jelinek wrote: > Hi! > > tree-ssa-ccp.c already computes which bits are known to be zero, but > we preserve that info only for pointers and not for integers. > This patch changes SSA_NAME_RANGE_INFO, so we preserve that info even for > integers. The bitmask is also computed from range info. > There are no users of this besides ccp itself right now, but I'm working > on using that info e.g. in the vectorizer. > > I had to tweak one testcase, because it relied on one of the two warnings > being emitted during VRP1 and one during VRP2, but because of the range info > derived nonzero_bits we now manage to optimize away the second test during > CCP3, which doesn't have -Wtype-limits warnings. If it would be too > important to keep warning even there, I guess it could check get_range_info > when folding a condition to 0/1 and warn if the rhs isn't in the lhs' range. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? > > During the development of the patch I had there code to not only > use get_range_info if otherwise returning VARYING, but also > if it was already constant, but that failed bootstrap miserably: > > It was something along the lines of: > > ++ /* If get_nonzero_bits tells us some bits > ++ have to be zero and they aren't, something > ++ went wrong. Only bits in value where val.mask > ++ has zeroes (i.e. valid bit from CCP), mask has ones > ++ (don't care about bits outside of precision) and > ++ has zeroes in nonzero_bits (guaranteed to be zero) > ++ should be verified to be zero. */ > ++ double_int valv = tree_to_double_int (val.value); > ++ gcc_assert ((valv & ~val.mask > ++ & ~nonzero_bits & mask).is_zero ()); > ++ if (!(valv & ~nonzero_bits & mask).is_zero ()) > ++ val.value = double_int_to_tree (TREE_TYPE (lhs), > ++ valv & nonzero_bits); > ++ if (nonzero_bits.is_zero ()) > ++ val.mask = double_int_zero; > ++ else > ++ val.mask = val.mask & (nonzero_bits | ~mask); > > The problem was that during the iteration when only a subset of the edges > were executable it sometimes failed the assertion, dunno if that is > the result of the nonzero bits info in this case coming from completely > different algorithm (from VRP ranges) and that simply until the CCP > iterations settle it can be wrong, so just to be safe in that case I'm > adding the info only in ccp_finalize (and the new nonzero_bits mask with > the old one). From what I could see, the range info on that testcase looked > just fine, the nonzero_bits derived from it too, if desirable, I can try to > cook up a small testcase showing that (reduce from libgcov.c that exhibited > that). Surely you can't rely on CCP and VRP compute exactly the same nonzero_bits. As you don't record/compute zero_bits you can't tell whether a not set bit in nonzer_bits is "don't know" or if it is "zero". And you cannot do an assert during iteration (during iteration optimistically 'wrong' values can disappear). During CCP iteration the rule is that bits may only be added to mask (and obviously the constant itself on a CONSTANT lattice value may not change). More comments inline > 2013-10-24 Jakub Jelinek <jakub@redhat.com> > > * gimple-pretty-print.c (dump_ssaname_info): Print newline also > in case of VR_VARYING. Print get_nonzero_bits if not all ones. > * tree-ssanames.h (struct range_info_def): Add nonzero_bits field. > (set_nonzero_bits, get_nonzero_bits): New prototypes. > * tree-ssa-ccp.c (get_default_value): Use get_range_info to see if > a default def isn't partially constant. > (ccp_finalize): If after IPA, set_range_info if integral SSA_NAME > is known to be partially zero. > (evaluate_stmt): If we'd return otherwise VARYING, use get_range_info > to see if a default def isn't partially constant. > * tree-ssanames.c (set_range_info): Initialize nonzero_bits upon > creation of a range, if VR_RANGE, try to improve nonzero_bits from > the range. > (set_nonzero_bits, get_nonzero_bits): New functions. > > * g++.dg/warn/pr33738.C (main): Initialize a2 again to make sure > we warn about it already during VRP1 pass. > > --- gcc/gimple-pretty-print.c.jj 2013-10-23 14:43:12.000000000 +0200 > +++ gcc/gimple-pretty-print.c 2013-10-24 17:26:59.650945232 +0200 > @@ -1731,7 +1731,7 @@ dump_ssaname_info (pretty_printer *buffe > if (!POINTER_TYPE_P (TREE_TYPE (node)) > && SSA_NAME_RANGE_INFO (node)) > { > - double_int min, max; > + double_int min, max, nonzero_bits; > value_range_type range_type = get_range_info (node, &min, &max); > > if (range_type == VR_VARYING) > @@ -1744,8 +1744,20 @@ dump_ssaname_info (pretty_printer *buffe > pp_printf (buffer, ", "); > pp_double_int (buffer, max, TYPE_UNSIGNED (TREE_TYPE (node))); > pp_printf (buffer, "]"); > - newline_and_indent (buffer, spc); > } > + nonzero_bits = get_nonzero_bits (node); > + if (nonzero_bits != double_int_minus_one > + && (nonzero_bits > + != double_int::mask (TYPE_PRECISION (TREE_TYPE (node))))) > + { > + pp_string (buffer, " NONZERO "); > + sprintf (pp_buffer (buffer)->digit_buffer, > + HOST_WIDE_INT_PRINT_DOUBLE_HEX, > + (unsigned HOST_WIDE_INT) nonzero_bits.high, > + nonzero_bits.low); > + pp_string (buffer, pp_buffer (buffer)->digit_buffer); > + } > + newline_and_indent (buffer, spc); > } > } > > --- gcc/tree-ssanames.h.jj 2013-09-27 15:42:44.000000000 +0200 > +++ gcc/tree-ssanames.h 2013-10-24 15:52:53.765955605 +0200 > @@ -52,6 +52,8 @@ struct GTY (()) range_info_def { > double_int min; > /* Maximum for value range. */ > double_int max; > + /* Non-zero bits - bits not set are guaranteed to be always zero. */ > + double_int nonzero_bits; > }; > > > @@ -68,10 +70,11 @@ struct GTY (()) range_info_def { > enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; > > /* Sets the value range to SSA. */ > -extern void set_range_info (tree ssa, double_int min, double_int max); > +extern void set_range_info (tree, double_int, double_int); > /* Gets the value range from SSA. */ > -extern enum value_range_type get_range_info (tree name, double_int *min, > - double_int *max); > +extern enum value_range_type get_range_info (tree, double_int *, double_int *); > +extern void set_nonzero_bits (tree, double_int); > +extern double_int get_nonzero_bits (tree); > extern void init_ssanames (struct function *, int); > extern void fini_ssanames (void); > extern void ssanames_print_statistics (void); > --- gcc/tree-ssa-ccp.c.jj 2013-10-23 14:43:15.000000000 +0200 > +++ gcc/tree-ssa-ccp.c 2013-10-24 21:16:48.673330359 +0200 > @@ -260,6 +260,19 @@ get_default_value (tree var) > { > val.lattice_val = VARYING; > val.mask = double_int_minus_one; > + if (flag_tree_bit_ccp) > + { > + double_int nonzero_bits = get_nonzero_bits (var); > + double_int mask > + = double_int::mask (TYPE_PRECISION (TREE_TYPE (var))); > + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) > + { > + val.lattice_val = CONSTANT; > + val.value = build_zero_cst (TREE_TYPE (var)); > + /* CCP wants the bits above precision set. */ > + val.mask = nonzero_bits | ~mask; > + } Factor this out to commonize with code in evaluate_stmt > + } > } > } > else if (is_gimple_assign (stmt)) > @@ -828,7 +841,8 @@ ccp_finalize (void) > do_dbg_cnt (); > > /* Derive alignment and misalignment information from partially > - constant pointers in the lattice. */ > + constant pointers in the lattice or nonzero bits from partially > + constant integers. */ > for (i = 1; i < num_ssa_names; ++i) > { > tree name = ssa_name (i); > @@ -836,7 +850,11 @@ ccp_finalize (void) > unsigned int tem, align; > > if (!name > - || !POINTER_TYPE_P (TREE_TYPE (name))) > + || (!POINTER_TYPE_P (TREE_TYPE (name)) > + && (!INTEGRAL_TYPE_P (TREE_TYPE (name)) > + /* Don't record nonzero bits before IPA to avoid > + using too much memory. */ > + || first_pass_instance))) > continue; > > val = get_value (name); > @@ -844,13 +862,24 @@ ccp_finalize (void) > || TREE_CODE (val->value) != INTEGER_CST) > continue; > > - /* Trailing constant bits specify the alignment, trailing value > - bits the misalignment. */ > - tem = val->mask.low; > - align = (tem & -tem); > - if (align > 1) > - set_ptr_info_alignment (get_ptr_info (name), align, > - TREE_INT_CST_LOW (val->value) & (align - 1)); > + if (POINTER_TYPE_P (TREE_TYPE (name))) > + { > + /* Trailing mask bits specify the alignment, trailing value > + bits the misalignment. */ > + tem = val->mask.low; > + align = (tem & -tem); > + if (align > 1) > + set_ptr_info_alignment (get_ptr_info (name), align, > + (TREE_INT_CST_LOW (val->value) > + & (align - 1))); > + } > + else > + { > + double_int nonzero_bits = val->mask; > + nonzero_bits = nonzero_bits | tree_to_double_int (val->value); > + nonzero_bits &= get_nonzero_bits (name); This looks odd to me - shouldn't it be simply nonzero_bits = ~val->mask & tree_to_double_int (val->value); ? &= of get_nonzero_bits either is not necessary or shows the lattice is unnecessarily conservative because you apply it too early during propagation? > + set_nonzero_bits (name, nonzero_bits); > + } > } > > /* Perform substitutions based on the known constant values. */ > @@ -1671,6 +1700,25 @@ evaluate_stmt (gimple stmt) > is_constant = (val.lattice_val == CONSTANT); > } > > + if (flag_tree_bit_ccp > + && !is_constant ^^^ ah, so if the bit-CCP part figured out a set of known bits then you don't do anything here while in fact you can still remove bits from mask with get_nonzero_bits info. Thanks, Richard. > + && likelyvalue != UNDEFINED > + && gimple_get_lhs (stmt) > + && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME) > + { > + tree lhs = gimple_get_lhs (stmt); > + double_int nonzero_bits = get_nonzero_bits (lhs); > + double_int mask = double_int::mask (TYPE_PRECISION (TREE_TYPE (lhs))); > + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) > + { > + val.lattice_val = CONSTANT; > + val.value = build_zero_cst (TREE_TYPE (lhs)); > + /* CCP wants the bits above precision set. */ > + val.mask = nonzero_bits | ~mask; > + is_constant = true; > + } > + } > + > if (!is_constant) > { > /* The statement produced a nonconstant value. If the statement > --- gcc/tree-ssanames.c.jj 2013-10-23 14:43:16.000000000 +0200 > +++ gcc/tree-ssanames.c 2013-10-24 17:32:22.127281080 +0200 > @@ -189,11 +189,30 @@ set_range_info (tree name, double_int mi > { > ri = ggc_alloc_cleared_range_info_def (); > SSA_NAME_RANGE_INFO (name) = ri; > + ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name))); > } > > /* Set the values. */ > ri->min = min; > ri->max = max; > + > + /* If it is a range, try to improve nonzero_bits from the min/max. */ > + if (min.cmp (max, TYPE_UNSIGNED (TREE_TYPE (name))) != 1) > + { > + int prec = TYPE_PRECISION (TREE_TYPE (name)); > + double_int xorv; > + > + min = min.zext (prec); > + max = max.zext (prec); > + xorv = min ^ max; > + if (xorv.high) > + xorv = double_int::mask (2 * HOST_BITS_PER_WIDE_INT > + - clz_hwi (xorv.high)); > + else if (xorv.low) > + xorv = double_int::mask (HOST_BITS_PER_WIDE_INT > + - clz_hwi (xorv.low)); > + ri->nonzero_bits = ri->nonzero_bits & (min | xorv); > + } > } > > > @@ -233,6 +252,47 @@ get_range_info (tree name, double_int *m > return range_type; > } > > +/* Change non-zero bits bitmask of NAME. */ > + > +void > +set_nonzero_bits (tree name, double_int mask) > +{ > + gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > + if (SSA_NAME_RANGE_INFO (name) == NULL) > + set_range_info (name, > + tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))), > + tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name)))); > + range_info_def *ri = SSA_NAME_RANGE_INFO (name); > + ri->nonzero_bits > + = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name))); > +} > + > +/* Return a double_int with potentially non-zero bits in SSA_NAME > + NAME, or double_int_minus_one if unknown. */ > + > +double_int > +get_nonzero_bits (tree name) > +{ > + if (POINTER_TYPE_P (TREE_TYPE (name))) > + { > + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); > + if (pi && pi->align) > + { > + double_int al = double_int::from_uhwi (pi->align - 1); > + return ((double_int::mask (TYPE_PRECISION (TREE_TYPE (name))) & ~al) > + | double_int::from_uhwi (pi->misalign)); > + } > + return double_int_minus_one; > + } > + > + range_info_def *ri = SSA_NAME_RANGE_INFO (name); > + if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) > + > 2 * HOST_BITS_PER_WIDE_INT)) > + return double_int_minus_one; > + > + return ri->nonzero_bits; > +} > + > /* We no longer need the SSA_NAME expression VAR, release it so that > it may be reused. > > --- gcc/testsuite/g++.dg/warn/pr33738.C.jj 2010-05-04 12:02:18.000000000 +0200 > +++ gcc/testsuite/g++.dg/warn/pr33738.C 2013-10-25 08:52:24.052881493 +0200 > @@ -18,6 +18,7 @@ int main() { > if (a2 == -1) { // { dg-warning "always false due" } > link_error (); > } > + a2 = static_cast<Alpha>(GetM1()); > if (-1 == a2) { // { dg-warning "always false due" } > link_error (); > } > > Jakub > >
--- gcc/gimple-pretty-print.c.jj 2013-10-23 14:43:12.000000000 +0200 +++ gcc/gimple-pretty-print.c 2013-10-24 17:26:59.650945232 +0200 @@ -1731,7 +1731,7 @@ dump_ssaname_info (pretty_printer *buffe if (!POINTER_TYPE_P (TREE_TYPE (node)) && SSA_NAME_RANGE_INFO (node)) { - double_int min, max; + double_int min, max, nonzero_bits; value_range_type range_type = get_range_info (node, &min, &max); if (range_type == VR_VARYING) @@ -1744,8 +1744,20 @@ dump_ssaname_info (pretty_printer *buffe pp_printf (buffer, ", "); pp_double_int (buffer, max, TYPE_UNSIGNED (TREE_TYPE (node))); pp_printf (buffer, "]"); - newline_and_indent (buffer, spc); } + nonzero_bits = get_nonzero_bits (node); + if (nonzero_bits != double_int_minus_one + && (nonzero_bits + != double_int::mask (TYPE_PRECISION (TREE_TYPE (node))))) + { + pp_string (buffer, " NONZERO "); + sprintf (pp_buffer (buffer)->digit_buffer, + HOST_WIDE_INT_PRINT_DOUBLE_HEX, + (unsigned HOST_WIDE_INT) nonzero_bits.high, + nonzero_bits.low); + pp_string (buffer, pp_buffer (buffer)->digit_buffer); + } + newline_and_indent (buffer, spc); } } --- gcc/tree-ssanames.h.jj 2013-09-27 15:42:44.000000000 +0200 +++ gcc/tree-ssanames.h 2013-10-24 15:52:53.765955605 +0200 @@ -52,6 +52,8 @@ struct GTY (()) range_info_def { double_int min; /* Maximum for value range. */ double_int max; + /* Non-zero bits - bits not set are guaranteed to be always zero. */ + double_int nonzero_bits; }; @@ -68,10 +70,11 @@ struct GTY (()) range_info_def { enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ -extern void set_range_info (tree ssa, double_int min, double_int max); +extern void set_range_info (tree, double_int, double_int); /* Gets the value range from SSA. */ -extern enum value_range_type get_range_info (tree name, double_int *min, - double_int *max); +extern enum value_range_type get_range_info (tree, double_int *, double_int *); +extern void set_nonzero_bits (tree, double_int); +extern double_int get_nonzero_bits (tree); extern void init_ssanames (struct function *, int); extern void fini_ssanames (void); extern void ssanames_print_statistics (void); --- gcc/tree-ssa-ccp.c.jj 2013-10-23 14:43:15.000000000 +0200 +++ gcc/tree-ssa-ccp.c 2013-10-24 21:16:48.673330359 +0200 @@ -260,6 +260,19 @@ get_default_value (tree var) { val.lattice_val = VARYING; val.mask = double_int_minus_one; + if (flag_tree_bit_ccp) + { + double_int nonzero_bits = get_nonzero_bits (var); + double_int mask + = double_int::mask (TYPE_PRECISION (TREE_TYPE (var))); + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) + { + val.lattice_val = CONSTANT; + val.value = build_zero_cst (TREE_TYPE (var)); + /* CCP wants the bits above precision set. */ + val.mask = nonzero_bits | ~mask; + } + } } } else if (is_gimple_assign (stmt)) @@ -828,7 +841,8 @@ ccp_finalize (void) do_dbg_cnt (); /* Derive alignment and misalignment information from partially - constant pointers in the lattice. */ + constant pointers in the lattice or nonzero bits from partially + constant integers. */ for (i = 1; i < num_ssa_names; ++i) { tree name = ssa_name (i); @@ -836,7 +850,11 @@ ccp_finalize (void) unsigned int tem, align; if (!name - || !POINTER_TYPE_P (TREE_TYPE (name))) + || (!POINTER_TYPE_P (TREE_TYPE (name)) + && (!INTEGRAL_TYPE_P (TREE_TYPE (name)) + /* Don't record nonzero bits before IPA to avoid + using too much memory. */ + || first_pass_instance))) continue; val = get_value (name); @@ -844,13 +862,24 @@ ccp_finalize (void) || TREE_CODE (val->value) != INTEGER_CST) continue; - /* Trailing constant bits specify the alignment, trailing value - bits the misalignment. */ - tem = val->mask.low; - align = (tem & -tem); - if (align > 1) - set_ptr_info_alignment (get_ptr_info (name), align, - TREE_INT_CST_LOW (val->value) & (align - 1)); + if (POINTER_TYPE_P (TREE_TYPE (name))) + { + /* Trailing mask bits specify the alignment, trailing value + bits the misalignment. */ + tem = val->mask.low; + align = (tem & -tem); + if (align > 1) + set_ptr_info_alignment (get_ptr_info (name), align, + (TREE_INT_CST_LOW (val->value) + & (align - 1))); + } + else + { + double_int nonzero_bits = val->mask; + nonzero_bits = nonzero_bits | tree_to_double_int (val->value); + nonzero_bits &= get_nonzero_bits (name); + set_nonzero_bits (name, nonzero_bits); + } } /* Perform substitutions based on the known constant values. */ @@ -1671,6 +1700,25 @@ evaluate_stmt (gimple stmt) is_constant = (val.lattice_val == CONSTANT); } + if (flag_tree_bit_ccp + && !is_constant + && likelyvalue != UNDEFINED + && gimple_get_lhs (stmt) + && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME) + { + tree lhs = gimple_get_lhs (stmt); + double_int nonzero_bits = get_nonzero_bits (lhs); + double_int mask = double_int::mask (TYPE_PRECISION (TREE_TYPE (lhs))); + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) + { + val.lattice_val = CONSTANT; + val.value = build_zero_cst (TREE_TYPE (lhs)); + /* CCP wants the bits above precision set. */ + val.mask = nonzero_bits | ~mask; + is_constant = true; + } + } + if (!is_constant) { /* The statement produced a nonconstant value. If the statement --- gcc/tree-ssanames.c.jj 2013-10-23 14:43:16.000000000 +0200 +++ gcc/tree-ssanames.c 2013-10-24 17:32:22.127281080 +0200 @@ -189,11 +189,30 @@ set_range_info (tree name, double_int mi { ri = ggc_alloc_cleared_range_info_def (); SSA_NAME_RANGE_INFO (name) = ri; + ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name))); } /* Set the values. */ ri->min = min; ri->max = max; + + /* If it is a range, try to improve nonzero_bits from the min/max. */ + if (min.cmp (max, TYPE_UNSIGNED (TREE_TYPE (name))) != 1) + { + int prec = TYPE_PRECISION (TREE_TYPE (name)); + double_int xorv; + + min = min.zext (prec); + max = max.zext (prec); + xorv = min ^ max; + if (xorv.high) + xorv = double_int::mask (2 * HOST_BITS_PER_WIDE_INT + - clz_hwi (xorv.high)); + else if (xorv.low) + xorv = double_int::mask (HOST_BITS_PER_WIDE_INT + - clz_hwi (xorv.low)); + ri->nonzero_bits = ri->nonzero_bits & (min | xorv); + } } @@ -233,6 +252,47 @@ get_range_info (tree name, double_int *m return range_type; } +/* Change non-zero bits bitmask of NAME. */ + +void +set_nonzero_bits (tree name, double_int mask) +{ + gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); + if (SSA_NAME_RANGE_INFO (name) == NULL) + set_range_info (name, + tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))), + tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name)))); + range_info_def *ri = SSA_NAME_RANGE_INFO (name); + ri->nonzero_bits + = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name))); +} + +/* Return a double_int with potentially non-zero bits in SSA_NAME + NAME, or double_int_minus_one if unknown. */ + +double_int +get_nonzero_bits (tree name) +{ + if (POINTER_TYPE_P (TREE_TYPE (name))) + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); + if (pi && pi->align) + { + double_int al = double_int::from_uhwi (pi->align - 1); + return ((double_int::mask (TYPE_PRECISION (TREE_TYPE (name))) & ~al) + | double_int::from_uhwi (pi->misalign)); + } + return double_int_minus_one; + } + + range_info_def *ri = SSA_NAME_RANGE_INFO (name); + if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) + > 2 * HOST_BITS_PER_WIDE_INT)) + return double_int_minus_one; + + return ri->nonzero_bits; +} + /* We no longer need the SSA_NAME expression VAR, release it so that it may be reused. --- gcc/testsuite/g++.dg/warn/pr33738.C.jj 2010-05-04 12:02:18.000000000 +0200 +++ gcc/testsuite/g++.dg/warn/pr33738.C 2013-10-25 08:52:24.052881493 +0200 @@ -18,6 +18,7 @@ int main() { if (a2 == -1) { // { dg-warning "always false due" } link_error (); } + a2 = static_cast<Alpha>(GetM1()); if (-1 == a2) { // { dg-warning "always false due" } link_error (); }