Message ID | 20200303202920.GD2156@tucnak |
---|---|
State | New |
Headers | show |
Series | sccvn: Avoid overflows in push_partial_def | expand |
On Tue, 3 Mar 2020, Jakub Jelinek wrote: > Hi! > > The following patch attempts to avoid dangerous overflows in the various > push_partial_def HOST_WIDE_INT computations. > This is achieved by performing the subtraction offset2i - offseti in > the push_partial_def function and before doing that doing some tweaks. > If a constant store (non-CONSTRUCTOR) is too large (perhaps just > hypothetical case), native_encode_expr would fail for it, but we don't > necessarily need to fail right away, instead we can treat it like > non-constant store and if it is already shadowed, we can ignore it. > Otherwise, if it at most 64-byte and the caller ensured that there is > a range overlap and push_partial_def ensures the load is at most 64-byte, > I think we should be fine, offset (relative to the load) > can be from -64*8+1 to 64*8-1 only and size at most 64*8, so no risks of > overflowing HOST_WIDE_INT computations. > For CONSTRUCTOR (or non-constant) stores, those can be indeed arbitrarily > large, the caller just checks that both the absolute offset and size fit > into signed HWI. But, we store the same bytes in that case over and over > (both in the {} case where it is all 0, and in the hypothetical future case > where we handle in push_partial_def also memset (, 123, )), so we can tweak > the write range for our purposes. For {} store we could just cap it at the > start offset and/or offset+size because all the bits are 0, but I wrote it > in anticipation of the memset case and so the relative offset can now be > down to -7 and similarly size can grow up to 64 bytes + 14 bits, all this > trying to preserve the offset difference % BITS_PER_UNIT or end as well. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? OK. > I've tried to construct a testcase and came with > /* PR tree-optimization/93582 */ > /* { dg-do compile { target lp64 } } */ > > union U { struct A { unsigned long long a : 1, b : 62, c : 1; } a; unsigned long long i; }; > > unsigned long long > foo (char *p) > { > __builtin_memset (p - 0xfffffffffffffffULL, 0, 0xffffffffffffffeULL); > __builtin_memset (p + 1, 0, 0xffffffffffffffeULL); > union U *q = (union U *) (void *) (p - 4); > q->a.b = -1; > return q->i; > } > With this testcase, one can see signed integer overflows in the compiler > without the patch. But unfortunately even with the patch it isn't optimized > as it should. I believe the problem is in: > gimple *def = SSA_NAME_DEF_STMT (ref2); > if (is_gimple_assign (def) > && gimple_assign_rhs_code (def) == POINTER_PLUS_EXPR > && gimple_assign_rhs1 (def) == TREE_OPERAND (base, 0) > && poly_int_tree_p (gimple_assign_rhs2 (def)) > && (wi::to_poly_offset (gimple_assign_rhs2 (def)) > << LOG2_BITS_PER_UNIT).to_shwi (&offset2)) > { > where POINTER_PLUS_EXPR last operand has sizetype type, thus unsigned, > and in the testcase gimple_assign_rhs2 (def) is thus 0xf000000000000001ULL > which multiplied by 8 doesn't fit into signed HWI. If it would be treated > as signed offset instead, it would fit (-0xfffffffffffffffLL, multiplied > by 8 is -0x7ffffffffffffff8LL). Unfortunately with the poly_int obfuscation > I'm not sure how to convert it from unsigned to signed poly_int. mem_ref_offset provides a boiler-plate for this: poly_offset_int::from (wi::to_poly_wide (TREE_OPERAND (t, 1)), SIGNED); Richard. > 2020-03-03 Jakub Jelinek <jakub@redhat.com> > > * tree-ssa-sccvn.c (vn_walk_cb_data::push_partial_def): Add offseti > argument. Change pd argument so that it can be modified. Turn > constant non-CONSTRUCTOR store into non-constant if it is too large. > Adjust offset and size of CONSTRUCTOR or non-constant store to avoid > overflows. > (vn_walk_cb_data::vn_walk_cb_data, vn_reference_lookup_3): Adjust > callers. > > --- gcc/tree-ssa-sccvn.c.jj 2020-03-03 11:20:52.761545034 +0100 > +++ gcc/tree-ssa-sccvn.c 2020-03-03 16:22:49.387657379 +0100 > @@ -1716,7 +1716,7 @@ struct vn_walk_cb_data > else > pd.offset = pos; > pd.size = tz; > - void *r = push_partial_def (pd, 0, 0, prec); > + void *r = push_partial_def (pd, 0, 0, 0, prec); > gcc_assert (r == NULL_TREE); > } > pos += tz; > @@ -1733,8 +1733,9 @@ struct vn_walk_cb_data > } > ~vn_walk_cb_data (); > void *finish (alias_set_type, alias_set_type, tree); > - void *push_partial_def (const pd_data& pd, > - alias_set_type, alias_set_type, HOST_WIDE_INT); > + void *push_partial_def (pd_data pd, > + alias_set_type, alias_set_type, HOST_WIDE_INT, > + HOST_WIDE_INT); > > vn_reference_t vr; > ao_ref orig_ref; > @@ -1817,8 +1818,9 @@ pd_tree_dealloc (void *, void *) > on failure. */ > > void * > -vn_walk_cb_data::push_partial_def (const pd_data &pd, > +vn_walk_cb_data::push_partial_def (pd_data pd, > alias_set_type set, alias_set_type base_set, > + HOST_WIDE_INT offseti, > HOST_WIDE_INT maxsizei) > { > const HOST_WIDE_INT bufsize = 64; > @@ -1831,6 +1833,27 @@ vn_walk_cb_data::push_partial_def (const > || BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN) > return (void *)-1; > > + /* Turn too large constant stores into non-constant stores. */ > + if (CONSTANT_CLASS_P (pd.rhs) && pd.size > bufsize * BITS_PER_UNIT) > + pd.rhs = error_mark_node; > + > + /* And for non-constant or CONSTRUCTOR stores shrink them to only keep at > + most a partial byte before and/or after the region. */ > + if (!CONSTANT_CLASS_P (pd.rhs)) > + { > + if (pd.offset < offseti) > + { > + HOST_WIDE_INT o = ROUND_DOWN (offseti - pd.offset, BITS_PER_UNIT); > + gcc_assert (pd.size > o); > + pd.size -= o; > + pd.offset += o; > + } > + if (pd.size > maxsizei) > + pd.size = maxsizei + ((pd.size - maxsizei) % BITS_PER_UNIT); > + } > + > + pd.offset -= offseti; > + > bool pd_constant_p = (TREE_CODE (pd.rhs) == CONSTRUCTOR > || CONSTANT_CLASS_P (pd.rhs)); > if (partial_defs.is_empty ()) > @@ -2736,9 +2759,9 @@ vn_reference_lookup_3 (ao_ref *ref, tree > { > pd_data pd; > pd.rhs = build_constructor (NULL_TREE, NULL); > - pd.offset = offset2i - offseti; > + pd.offset = offset2i; > pd.size = leni << LOG2_BITS_PER_UNIT; > - return data->push_partial_def (pd, 0, 0, maxsizei); > + return data->push_partial_def (pd, 0, 0, offseti, maxsizei); > } > } > > @@ -2785,11 +2808,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree > by a later def. */ > pd_data pd; > pd.rhs = gimple_assign_rhs1 (def_stmt); > - pd.offset = offset2i - offseti; > + pd.offset = offset2i; > pd.size = size2i; > return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), > ao_ref_base_alias_set (&lhs_ref), > - maxsizei); > + offseti, maxsizei); > } > } > } > @@ -2936,11 +2959,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree > if (TREE_CODE (rhs) == SSA_NAME) > rhs = SSA_VAL (rhs); > pd.rhs = rhs; > - pd.offset = offset2i - offseti; > + pd.offset = offset2i; > pd.size = size2i; > return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), > ao_ref_base_alias_set (&lhs_ref), > - maxsizei); > + offseti, maxsizei); > } > } > } > @@ -3014,11 +3037,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree > { > pd_data pd; > pd.rhs = SSA_VAL (def_rhs); > - pd.offset = offset2i - offseti; > + pd.offset = offset2i; > pd.size = size2i; > return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), > ao_ref_base_alias_set (&lhs_ref), > - maxsizei); > + offseti, maxsizei); > } > } > } > @@ -3154,7 +3177,7 @@ vn_reference_lookup_3 (ao_ref *ref, tree > pd.size = maxsizei; > return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), > ao_ref_base_alias_set (&lhs_ref), > - maxsizei); > + 0, maxsizei); > } > } > > > Jakub > >
--- gcc/tree-ssa-sccvn.c.jj 2020-03-03 11:20:52.761545034 +0100 +++ gcc/tree-ssa-sccvn.c 2020-03-03 16:22:49.387657379 +0100 @@ -1716,7 +1716,7 @@ struct vn_walk_cb_data else pd.offset = pos; pd.size = tz; - void *r = push_partial_def (pd, 0, 0, prec); + void *r = push_partial_def (pd, 0, 0, 0, prec); gcc_assert (r == NULL_TREE); } pos += tz; @@ -1733,8 +1733,9 @@ struct vn_walk_cb_data } ~vn_walk_cb_data (); void *finish (alias_set_type, alias_set_type, tree); - void *push_partial_def (const pd_data& pd, - alias_set_type, alias_set_type, HOST_WIDE_INT); + void *push_partial_def (pd_data pd, + alias_set_type, alias_set_type, HOST_WIDE_INT, + HOST_WIDE_INT); vn_reference_t vr; ao_ref orig_ref; @@ -1817,8 +1818,9 @@ pd_tree_dealloc (void *, void *) on failure. */ void * -vn_walk_cb_data::push_partial_def (const pd_data &pd, +vn_walk_cb_data::push_partial_def (pd_data pd, alias_set_type set, alias_set_type base_set, + HOST_WIDE_INT offseti, HOST_WIDE_INT maxsizei) { const HOST_WIDE_INT bufsize = 64; @@ -1831,6 +1833,27 @@ vn_walk_cb_data::push_partial_def (const || BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN) return (void *)-1; + /* Turn too large constant stores into non-constant stores. */ + if (CONSTANT_CLASS_P (pd.rhs) && pd.size > bufsize * BITS_PER_UNIT) + pd.rhs = error_mark_node; + + /* And for non-constant or CONSTRUCTOR stores shrink them to only keep at + most a partial byte before and/or after the region. */ + if (!CONSTANT_CLASS_P (pd.rhs)) + { + if (pd.offset < offseti) + { + HOST_WIDE_INT o = ROUND_DOWN (offseti - pd.offset, BITS_PER_UNIT); + gcc_assert (pd.size > o); + pd.size -= o; + pd.offset += o; + } + if (pd.size > maxsizei) + pd.size = maxsizei + ((pd.size - maxsizei) % BITS_PER_UNIT); + } + + pd.offset -= offseti; + bool pd_constant_p = (TREE_CODE (pd.rhs) == CONSTRUCTOR || CONSTANT_CLASS_P (pd.rhs)); if (partial_defs.is_empty ()) @@ -2736,9 +2759,9 @@ vn_reference_lookup_3 (ao_ref *ref, tree { pd_data pd; pd.rhs = build_constructor (NULL_TREE, NULL); - pd.offset = offset2i - offseti; + pd.offset = offset2i; pd.size = leni << LOG2_BITS_PER_UNIT; - return data->push_partial_def (pd, 0, 0, maxsizei); + return data->push_partial_def (pd, 0, 0, offseti, maxsizei); } } @@ -2785,11 +2808,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree by a later def. */ pd_data pd; pd.rhs = gimple_assign_rhs1 (def_stmt); - pd.offset = offset2i - offseti; + pd.offset = offset2i; pd.size = size2i; return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), ao_ref_base_alias_set (&lhs_ref), - maxsizei); + offseti, maxsizei); } } } @@ -2936,11 +2959,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree if (TREE_CODE (rhs) == SSA_NAME) rhs = SSA_VAL (rhs); pd.rhs = rhs; - pd.offset = offset2i - offseti; + pd.offset = offset2i; pd.size = size2i; return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), ao_ref_base_alias_set (&lhs_ref), - maxsizei); + offseti, maxsizei); } } } @@ -3014,11 +3037,11 @@ vn_reference_lookup_3 (ao_ref *ref, tree { pd_data pd; pd.rhs = SSA_VAL (def_rhs); - pd.offset = offset2i - offseti; + pd.offset = offset2i; pd.size = size2i; return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), ao_ref_base_alias_set (&lhs_ref), - maxsizei); + offseti, maxsizei); } } } @@ -3154,7 +3177,7 @@ vn_reference_lookup_3 (ao_ref *ref, tree pd.size = maxsizei; return data->push_partial_def (pd, ao_ref_alias_set (&lhs_ref), ao_ref_base_alias_set (&lhs_ref), - maxsizei); + 0, maxsizei); } }