Re: [patch] Fix segfault caused by spurious constant overflow
On Mon, Jun 3, 2019 at 12:38 PM Eric Botcazou wrote: > > > Hmm, ISTR we had such mitigations in place (or have) elsewhere keying > > on the most significant bit set instead of power-of-two. But your case > > likely recurses and runs into the extract_multiv limiting to eventually > > stop, even for (N + 4) * 8, right? If so shouldn't we prevent this > > even for !TYPE_OVERFLOW_WRAPS? Also > > > > + && !(tree_fits_shwi_p (c) > > + && exact_log2 (absu_hwi (tree_to_shwi (c))) > 0)) > > > > is better written as > > > >&& exact_log2 (wi::to_wide (c)) > 0 > > It turns out that pow2p_hwi can be used instead and is cheaper, so I have > changed both extract_muldiv_1 and fold_plusminus_mult_expr to using it. OK, thanks. Richard. > > * fold-const.c (extract_muldiv_1) : Do not distribute a > multiplication by a power-of-two value. > (fold_plusminus_mult_expr): Use pow2p_hwi to detect a power-of-two > value > and turn the modulo operation into a masking operation. > > -- > Eric Botcazou
Re: [patch] Fix segfault caused by spurious constant overflow
> Hmm, ISTR we had such mitigations in place (or have) elsewhere keying
> on the most significant bit set instead of power-of-two. But your case
> likely recurses and runs into the extract_multiv limiting to eventually
> stop, even for (N + 4) * 8, right? If so shouldn't we prevent this
> even for !TYPE_OVERFLOW_WRAPS? Also
>
> + && !(tree_fits_shwi_p (c)
> + && exact_log2 (absu_hwi (tree_to_shwi (c))) > 0))
>
> is better written as
>
>&& exact_log2 (wi::to_wide (c)) > 0
It turns out that pow2p_hwi can be used instead and is cheaper, so I have
changed both extract_muldiv_1 and fold_plusminus_mult_expr to using it.
* fold-const.c (extract_muldiv_1) : Do not distribute a
multiplication by a power-of-two value.
(fold_plusminus_mult_expr): Use pow2p_hwi to detect a power-of-two value
and turn the modulo operation into a masking operation.
--
Eric BotcazouIndex: fold-const.c
===
--- fold-const.c (revision 271694)
+++ fold-const.c (working copy)
@@ -6475,8 +6475,12 @@ extract_muldiv_1 (tree t, tree c, enum t
apply the distributive law to commute the multiply and addition
if the multiplication of the constants doesn't overflow
and overflow is defined. With undefined overflow
- op0 * c might overflow, while (op0 + orig_op1) * c doesn't. */
- if (code == MULT_EXPR && TYPE_OVERFLOW_WRAPS (ctype))
+ op0 * c might overflow, while (op0 + orig_op1) * c doesn't.
+ But fold_plusminus_mult_expr would factor back any power-of-two
+ value so do not distribute in the first place in this case. */
+ if (code == MULT_EXPR
+ && TYPE_OVERFLOW_WRAPS (ctype)
+ && !(tree_fits_shwi_p (c) && pow2p_hwi (absu_hwi (tree_to_shwi (c)
return fold_build2 (tcode, ctype,
fold_build2 (code, ctype,
fold_convert (ctype, op0),
@@ -7124,14 +7128,13 @@ fold_plusminus_mult_expr (location_t loc
/* No identical multiplicands; see if we can find a common
power-of-two factor in non-power-of-two multiplies. This
can help in multi-dimensional array access. */
- else if (tree_fits_shwi_p (arg01)
- && tree_fits_shwi_p (arg11))
+ else if (tree_fits_shwi_p (arg01) && tree_fits_shwi_p (arg11))
{
- HOST_WIDE_INT int01, int11, tmp;
+ HOST_WIDE_INT int01 = tree_to_shwi (arg01);
+ HOST_WIDE_INT int11 = tree_to_shwi (arg11);
+ HOST_WIDE_INT tmp;
bool swap = false;
tree maybe_same;
- int01 = tree_to_shwi (arg01);
- int11 = tree_to_shwi (arg11);
/* Move min of absolute values to int11. */
if (absu_hwi (int01) < absu_hwi (int11))
@@ -7144,7 +7147,10 @@ fold_plusminus_mult_expr (location_t loc
else
maybe_same = arg11;
- if (exact_log2 (absu_hwi (int11)) > 0 && int01 % int11 == 0
+ unsigned HOST_WIDE_INT factor = absu_hwi (int11);
+ if (factor > 1
+ && pow2p_hwi (factor)
+ && (int01 & (factor - 1)) == 0
/* The remainder should not be a constant, otherwise we
end up folding i * 4 + 2 to (i * 2 + 1) * 2 which has
increased the number of multiplications necessary. */
Re: [patch] Fix segfault caused by spurious constant overflow
> Hmm, ISTR we had such mitigations in place (or have) elsewhere keying > on the most significant bit set instead of power-of-two. fold_plusminus_mult_expr only factors out for power-of-two: if (exact_log2 (absu_hwi (int11)) > 0 && int01 % int11 == 0 /* The remainder should not be a constant, otherwise we end up folding i * 4 + 2 to (i * 2 + 1) * 2 which has increased the number of multiplications necessary. */ && TREE_CODE (arg10) != INTEGER_CST) > But your case > likely recurses and runs into the extract_multiv limiting to eventually > stop, even for (N + 4) * 8, right? Yes, it oscillates between extract_multiv and fold_plusminus_mult_expr until reaching the maximal depth. > If so shouldn't we prevent this even for !TYPE_OVERFLOW_WRAPS? Also > > + && !(tree_fits_shwi_p (c) > + && exact_log2 (absu_hwi (tree_to_shwi (c))) > 0)) The code only distributes for TYPE_OVERFLOW_WRAPS though: /* The last case is if we are a multiply. In that case, we can apply the distributive law to commute the multiply and addition if the multiplication of the constants doesn't overflow and overflow is defined. With undefined overflow op0 * c might overflow, while (op0 + orig_op1) * c doesn't. */ if (code == MULT_EXPR && TYPE_OVERFLOW_WRAPS (ctype)) return fold_build2 (tcode, ctype, fold_build2 (code, ctype, fold_convert (ctype, op0), fold_convert (ctype, c)), op1); > is better written as > >&& exact_log2 (wi::to_wide (c)) > 0 > > not sure why the sizetype constant for you fits in a signed HWI > or you need to compute its absolute value. Eventually you > need to use wi::abs(wide_int::from (wi::to_wide (c), TYPE_PRECISION > (TREE_TYPE (c)), SIGNED)) > or so. This is just mirrored on what fold_plusminus_mult_expr does. -- Eric Botcazou
Re: [patch] Fix segfault caused by spurious constant overflow
On Fri, May 31, 2019 at 11:56 AM Eric Botcazou wrote: > > Hi, > > this is a regression present for 32-bit targets on mainline and 9 branch only, > but the underlying issue dates back from the removal of the TYPE_IS_SIZETYPE > machinery. Since the removal of this machinery, there is an internal conflict > for sizetype: it's an unsigned type so with wrap-around semantics on overflow > but overflow nevertheless needs to be tracked for it in order to avoid buffer > overflows for large objects. > > The constant folder contains various tricks to that effect and the Ada front- > end even more so, because VLAs are first-class citizens in the language and > their lower bound is not necessarily 0. In particular, you need to be able to > distinguish large constants in sizetype from small negative constants turned > into even larger constants, because the latter appear in the length of e.g.: > > type Arr is array (2 .. N) of Long_Long_Integer; > > This works when the expressions haven't been too much mangled by the constant > folder and here we have a counter-example for 32-bit targets. Starting with: > > (N + 4294967295) * 8 > > which is the sizetype expression of the size of Arr in bytes, extract_muldiv_1 > distributes the multiplication: > > N * 8 + 4294967288 > > and, immediately after, fold_plusminus_mult_expr factors it back: > > (N + 536870911) * 8 > > At this point, there is no way for gigi to tell that it's the expression of a > simple array with no overflow in sight because the 536870911 constant is large > but not large enough, so gigi flags it as overflowing for small values of N. > > I don't see any other way out than disabling the back-and-forth mathematical > game played by the constant folder in this case, which very likely brings no > benefit in practice, hence the proposed fix. > > Tested on x86_64-suse-linux, OK for the mainline and 9 branch? Hmm, ISTR we had such mitigations in place (or have) elsewhere keying on the most significant bit set instead of power-of-two. But your case likely recurses and runs into the extract_multiv limiting to eventually stop, even for (N + 4) * 8, right? If so shouldn't we prevent this even for !TYPE_OVERFLOW_WRAPS? Also + && !(tree_fits_shwi_p (c) + && exact_log2 (absu_hwi (tree_to_shwi (c))) > 0)) is better written as && exact_log2 (wi::to_wide (c)) > 0 not sure why the sizetype constant for you fits in a signed HWI or you need to compute its absolute value. Eventually you need to use wi::abs(wide_int::from (wi::to_wide (c), TYPE_PRECISION (TREE_TYPE (c)), SIGNED)) or so. Thanks, Richard. > > 2019-05-31 Eric Botcazou > > * fold-const.c (extract_muldiv_1) : Do not distribute a > multiplication by a power-of-two value. > > > 2019-05-31 Eric Botcazou > > * gnat.dg/specs/discr6.ads: New test. > > -- > Eric Botcazou
[patch] Fix segfault caused by spurious constant overflow
Hi,
this is a regression present for 32-bit targets on mainline and 9 branch only,
but the underlying issue dates back from the removal of the TYPE_IS_SIZETYPE
machinery. Since the removal of this machinery, there is an internal conflict
for sizetype: it's an unsigned type so with wrap-around semantics on overflow
but overflow nevertheless needs to be tracked for it in order to avoid buffer
overflows for large objects.
The constant folder contains various tricks to that effect and the Ada front-
end even more so, because VLAs are first-class citizens in the language and
their lower bound is not necessarily 0. In particular, you need to be able to
distinguish large constants in sizetype from small negative constants turned
into even larger constants, because the latter appear in the length of e.g.:
type Arr is array (2 .. N) of Long_Long_Integer;
This works when the expressions haven't been too much mangled by the constant
folder and here we have a counter-example for 32-bit targets. Starting with:
(N + 4294967295) * 8
which is the sizetype expression of the size of Arr in bytes, extract_muldiv_1
distributes the multiplication:
N * 8 + 4294967288
and, immediately after, fold_plusminus_mult_expr factors it back:
(N + 536870911) * 8
At this point, there is no way for gigi to tell that it's the expression of a
simple array with no overflow in sight because the 536870911 constant is large
but not large enough, so gigi flags it as overflowing for small values of N.
I don't see any other way out than disabling the back-and-forth mathematical
game played by the constant folder in this case, which very likely brings no
benefit in practice, hence the proposed fix.
Tested on x86_64-suse-linux, OK for the mainline and 9 branch?
2019-05-31 Eric Botcazou
* fold-const.c (extract_muldiv_1) : Do not distribute a
multiplication by a power-of-two value.
2019-05-31 Eric Botcazou
* gnat.dg/specs/discr6.ads: New test.
--
Eric BotcazouIndex: fold-const.c
===
--- fold-const.c (revision 271694)
+++ fold-const.c (working copy)
@@ -6475,8 +6475,13 @@ extract_muldiv_1 (tree t, tree c, enum t
apply the distributive law to commute the multiply and addition
if the multiplication of the constants doesn't overflow
and overflow is defined. With undefined overflow
- op0 * c might overflow, while (op0 + orig_op1) * c doesn't. */
- if (code == MULT_EXPR && TYPE_OVERFLOW_WRAPS (ctype))
+ op0 * c might overflow, while (op0 + orig_op1) * c doesn't.
+ But fold_plusminus_mult_expr would factor back any power-of-two
+ value so do not distribute in the first place in this case. */
+ if (code == MULT_EXPR
+ && TYPE_OVERFLOW_WRAPS (ctype)
+ && !(tree_fits_shwi_p (c)
+ && exact_log2 (absu_hwi (tree_to_shwi (c))) > 0))
return fold_build2 (tcode, ctype,
fold_build2 (code, ctype,
fold_convert (ctype, op0),
-- { dg-do compile }
package Discr6 is
subtype Index_T is Integer range 0 .. 15;
type Arr is array (Index_T range <> ) of Long_Long_Integer;
type Rec2 (Size : Index_T := 2) is record
A : Arr (2 .. Size);
end record;
type Rec3 (D : Boolean := False) is record
R : Rec2;
case D is
when False=> null;
when True => I : Integer;
end case;
end record;
end Discr6;
