tree-optimization/110243 - kill off IVOPTs split_offset
Checks
Commit Message
IVOPTs has strip_offset which suffers from the same issues regarding
integer overflow that split_constant_offset did but the latter was
fixed quite some time ago. The following implements strip_offset
in terms of split_constant_offset, removing the redundant and
incorrect implementation.
The implementations are not exactly the same, strip_offset relies
on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
simply assumes those do not happen and truncates them. By
the same means strip_offset also handles POLY_INT_CSTs but
split_constant_offset does not. Massaging the latter to
behave like strip_offset in those cases might be the way to go?
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Comments?
Thanks,
Richard.
PR tree-optimization/110243
* tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
(strip_offset): Make it a wrapper around split_constant_offset.
* gcc.dg/torture/pr110243.c: New testcase.
---
gcc/testsuite/gcc.dg/torture/pr110243.c | 22 +++
gcc/tree-ssa-loop-ivopts.cc | 182 ++----------------------
2 files changed, 32 insertions(+), 172 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/pr110243.c
Comments
On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
> IVOPTs has strip_offset which suffers from the same issues regarding
> integer overflow that split_constant_offset did but the latter was
> fixed quite some time ago. The following implements strip_offset
> in terms of split_constant_offset, removing the redundant and
> incorrect implementation.
>
> The implementations are not exactly the same, strip_offset relies
> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
> simply assumes those do not happen and truncates them. By
> the same means strip_offset also handles POLY_INT_CSTs but
> split_constant_offset does not. Massaging the latter to
> behave like strip_offset in those cases might be the way to go?
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> Comments?
>
> Thanks,
> Richard.
>
> PR tree-optimization/110243
> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
> (strip_offset): Make it a wrapper around split_constant_offset.
>
> * gcc.dg/torture/pr110243.c: New testcase.
Your call -- IMHO you know this code far better than I.
jeff
Jeff Law <jeffreyalaw@gmail.com> writes:
> On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
>> IVOPTs has strip_offset which suffers from the same issues regarding
>> integer overflow that split_constant_offset did but the latter was
>> fixed quite some time ago. The following implements strip_offset
>> in terms of split_constant_offset, removing the redundant and
>> incorrect implementation.
>>
>> The implementations are not exactly the same, strip_offset relies
>> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
>> simply assumes those do not happen and truncates them. By
>> the same means strip_offset also handles POLY_INT_CSTs but
>> split_constant_offset does not. Massaging the latter to
>> behave like strip_offset in those cases might be the way to go?
>>
>> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>>
>> Comments?
>>
>> Thanks,
>> Richard.
>>
>> PR tree-optimization/110243
>> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
>> (strip_offset): Make it a wrapper around split_constant_offset.
>>
>> * gcc.dg/torture/pr110243.c: New testcase.
> Your call -- IMHO you know this code far better than I.
+1, but LGTM FWIW. I couldn't see anything obvious (and valid)
that split_offset_1 handles and split_constant_offset doesn't.
Thanks,
Richard
On Mon, 19 Jun 2023, Richard Sandiford wrote:
> Jeff Law <jeffreyalaw@gmail.com> writes:
> > On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
> >> IVOPTs has strip_offset which suffers from the same issues regarding
> >> integer overflow that split_constant_offset did but the latter was
> >> fixed quite some time ago. The following implements strip_offset
> >> in terms of split_constant_offset, removing the redundant and
> >> incorrect implementation.
> >>
> >> The implementations are not exactly the same, strip_offset relies
> >> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
> >> simply assumes those do not happen and truncates them. By
> >> the same means strip_offset also handles POLY_INT_CSTs but
> >> split_constant_offset does not. Massaging the latter to
> >> behave like strip_offset in those cases might be the way to go?
> >>
> >> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >>
> >> Comments?
> >>
> >> Thanks,
> >> Richard.
> >>
> >> PR tree-optimization/110243
> >> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
> >> (strip_offset): Make it a wrapper around split_constant_offset.
> >>
> >> * gcc.dg/torture/pr110243.c: New testcase.
> > Your call -- IMHO you know this code far better than I.
>
> +1, but LGTM FWIW. I couldn't see anything obvious (and valid)
> that split_offset_1 handles and split_constant_offset doesn't.
I think it's only the INTEGER_CST vs. ptrdiff_tree_p where the
latter (used in split_offset_1) handles POLY_INT_CSTs. split_offset
also computes the offset in poly_int64 and checks it fits
(to some extent) while split_constant_offset simply converts all
INTEGER_CSTs to ssizetype because it knows it starts from addresses
only.
An alternative fix would have been to rewrite signed arithmetic
to unsigned in strip_offset_1.
I wonder if we want to change split_constant_offset to record the
offset in a poly_int64 and have a wrapper converting it back to
a tree for data-ref analysis. Then we can at least put
cst_and_fits_in_hwi checks in the code? The code also tracks
a range so it doesn't look like handling POLY_INT_CSTs is easy
there - do you remember whether that was important for IVOPTs?
Thanks,
Richard.
Richard Biener <rguenther@suse.de> writes:
> On Mon, 19 Jun 2023, Richard Sandiford wrote:
>
>> Jeff Law <jeffreyalaw@gmail.com> writes:
>> > On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
>> >> IVOPTs has strip_offset which suffers from the same issues regarding
>> >> integer overflow that split_constant_offset did but the latter was
>> >> fixed quite some time ago. The following implements strip_offset
>> >> in terms of split_constant_offset, removing the redundant and
>> >> incorrect implementation.
>> >>
>> >> The implementations are not exactly the same, strip_offset relies
>> >> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
>> >> simply assumes those do not happen and truncates them. By
>> >> the same means strip_offset also handles POLY_INT_CSTs but
>> >> split_constant_offset does not. Massaging the latter to
>> >> behave like strip_offset in those cases might be the way to go?
>> >>
>> >> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>> >>
>> >> Comments?
>> >>
>> >> Thanks,
>> >> Richard.
>> >>
>> >> PR tree-optimization/110243
>> >> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
>> >> (strip_offset): Make it a wrapper around split_constant_offset.
>> >>
>> >> * gcc.dg/torture/pr110243.c: New testcase.
>> > Your call -- IMHO you know this code far better than I.
>>
>> +1, but LGTM FWIW. I couldn't see anything obvious (and valid)
>> that split_offset_1 handles and split_constant_offset doesn't.
>
> I think it's only the INTEGER_CST vs. ptrdiff_tree_p where the
> latter (used in split_offset_1) handles POLY_INT_CSTs. split_offset
> also computes the offset in poly_int64 and checks it fits
> (to some extent) while split_constant_offset simply converts all
> INTEGER_CSTs to ssizetype because it knows it starts from addresses
> only.
>
> An alternative fix would have been to rewrite signed arithmetic
> to unsigned in strip_offset_1.
>
> I wonder if we want to change split_constant_offset to record the
> offset in a poly_int64 and have a wrapper converting it back to
> a tree for data-ref analysis.
Sounds a good idea if it's easily doable.
> Then we can at least put cst_and_fits_in_hwi checks in the code?
What would they be protecting against, if we're dealing with
address arithmetic?
> The code also tracks a range so it doesn't look like handling
> POLY_INT_CSTs is easy there - do you remember whether that was
> important for IVOPTs?
Got to admit that:
tree
strip_offset (tree expr, poly_uint64_pod *offset)
{
poly_int64 off;
tree core = strip_offset_1 (expr, false, false, &off);
if (!off.is_constant ())
{
core = expr;
off = 0;
}
*offset = off;
return core;
}
doesn't seem to trigger any testsuite failures from a quick test
(but not a full regtest).
Thanks,
Richard
On Tue, 20 Jun 2023, Richard Sandiford wrote:
> Richard Biener <rguenther@suse.de> writes:
> > On Mon, 19 Jun 2023, Richard Sandiford wrote:
> >
> >> Jeff Law <jeffreyalaw@gmail.com> writes:
> >> > On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
> >> >> IVOPTs has strip_offset which suffers from the same issues regarding
> >> >> integer overflow that split_constant_offset did but the latter was
> >> >> fixed quite some time ago. The following implements strip_offset
> >> >> in terms of split_constant_offset, removing the redundant and
> >> >> incorrect implementation.
> >> >>
> >> >> The implementations are not exactly the same, strip_offset relies
> >> >> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
> >> >> simply assumes those do not happen and truncates them. By
> >> >> the same means strip_offset also handles POLY_INT_CSTs but
> >> >> split_constant_offset does not. Massaging the latter to
> >> >> behave like strip_offset in those cases might be the way to go?
> >> >>
> >> >> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >> >>
> >> >> Comments?
> >> >>
> >> >> Thanks,
> >> >> Richard.
> >> >>
> >> >> PR tree-optimization/110243
> >> >> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
> >> >> (strip_offset): Make it a wrapper around split_constant_offset.
> >> >>
> >> >> * gcc.dg/torture/pr110243.c: New testcase.
> >> > Your call -- IMHO you know this code far better than I.
> >>
> >> +1, but LGTM FWIW. I couldn't see anything obvious (and valid)
> >> that split_offset_1 handles and split_constant_offset doesn't.
> >
> > I think it's only the INTEGER_CST vs. ptrdiff_tree_p where the
> > latter (used in split_offset_1) handles POLY_INT_CSTs. split_offset
> > also computes the offset in poly_int64 and checks it fits
> > (to some extent) while split_constant_offset simply converts all
> > INTEGER_CSTs to ssizetype because it knows it starts from addresses
> > only.
> >
> > An alternative fix would have been to rewrite signed arithmetic
> > to unsigned in strip_offset_1.
> >
> > I wonder if we want to change split_constant_offset to record the
> > offset in a poly_int64 and have a wrapper converting it back to
> > a tree for data-ref analysis.
>
> Sounds a good idea if it's easily doable.
>
> > Then we can at least put cst_and_fits_in_hwi checks in the code?
>
> What would they be protecting against, if we're dealing with
> address arithmetic?
While tree-data-ref.cc deals with address arithmetic only IVOPTs
at least also runs it on general IVs, for example for uses
in the exit condition.
Adding the following to strip_offset
gcc_assert (POINTER_TYPE_P (TREE_TYPE (expr))
|| (INTEGRAL_TYPE_P (TREE_TYPE (expr))
&& TYPE_PRECISION (TREE_TYPE (expr)) <= TYPE_PRECISION
(sizetype)));
runs into ICEs when testing a 32bit target.
But IVOPTs only makes use of the computed offset when it strips
it off address uses. But what I only now realized is that
IVOPTs strip_offset is also used by loop distribution.
I'm going to split the patch in two at least to make these things
more obvious before changing the implementation.
> > The code also tracks a range so it doesn't look like handling
> > POLY_INT_CSTs is easy there - do you remember whether that was
> > important for IVOPTs?
>
> Got to admit that:
>
> tree
> strip_offset (tree expr, poly_uint64_pod *offset)
> {
> poly_int64 off;
> tree core = strip_offset_1 (expr, false, false, &off);
> if (!off.is_constant ())
> {
> core = expr;
> off = 0;
> }
> *offset = off;
> return core;
> }
>
> doesn't seem to trigger any testsuite failures from a quick test
> (but not a full regtest).
I see.
Thanks,
Richard.
On Wed, 21 Jun 2023, Richard Biener wrote:
> On Tue, 20 Jun 2023, Richard Sandiford wrote:
>
> > Richard Biener <rguenther@suse.de> writes:
> > > On Mon, 19 Jun 2023, Richard Sandiford wrote:
> > >
> > >> Jeff Law <jeffreyalaw@gmail.com> writes:
> > >> > On 6/16/23 06:34, Richard Biener via Gcc-patches wrote:
> > >> >> IVOPTs has strip_offset which suffers from the same issues regarding
> > >> >> integer overflow that split_constant_offset did but the latter was
> > >> >> fixed quite some time ago. The following implements strip_offset
> > >> >> in terms of split_constant_offset, removing the redundant and
> > >> >> incorrect implementation.
> > >> >>
> > >> >> The implementations are not exactly the same, strip_offset relies
> > >> >> on ptrdiff_tree_p to fend off too large offsets while split_constant_offset
> > >> >> simply assumes those do not happen and truncates them. By
> > >> >> the same means strip_offset also handles POLY_INT_CSTs but
> > >> >> split_constant_offset does not. Massaging the latter to
> > >> >> behave like strip_offset in those cases might be the way to go?
> > >> >>
> > >> >> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> > >> >>
> > >> >> Comments?
> > >> >>
> > >> >> Thanks,
> > >> >> Richard.
> > >> >>
> > >> >> PR tree-optimization/110243
> > >> >> * tree-ssa-loop-ivopts.cc (strip_offset_1): Remove.
> > >> >> (strip_offset): Make it a wrapper around split_constant_offset.
> > >> >>
> > >> >> * gcc.dg/torture/pr110243.c: New testcase.
> > >> > Your call -- IMHO you know this code far better than I.
> > >>
> > >> +1, but LGTM FWIW. I couldn't see anything obvious (and valid)
> > >> that split_offset_1 handles and split_constant_offset doesn't.
> > >
> > > I think it's only the INTEGER_CST vs. ptrdiff_tree_p where the
> > > latter (used in split_offset_1) handles POLY_INT_CSTs. split_offset
> > > also computes the offset in poly_int64 and checks it fits
> > > (to some extent) while split_constant_offset simply converts all
> > > INTEGER_CSTs to ssizetype because it knows it starts from addresses
> > > only.
> > >
> > > An alternative fix would have been to rewrite signed arithmetic
> > > to unsigned in strip_offset_1.
> > >
> > > I wonder if we want to change split_constant_offset to record the
> > > offset in a poly_int64 and have a wrapper converting it back to
> > > a tree for data-ref analysis.
> >
> > Sounds a good idea if it's easily doable.
> >
> > > Then we can at least put cst_and_fits_in_hwi checks in the code?
> >
> > What would they be protecting against, if we're dealing with
> > address arithmetic?
>
> While tree-data-ref.cc deals with address arithmetic only IVOPTs
> at least also runs it on general IVs, for example for uses
> in the exit condition.
>
> Adding the following to strip_offset
>
> gcc_assert (POINTER_TYPE_P (TREE_TYPE (expr))
> || (INTEGRAL_TYPE_P (TREE_TYPE (expr))
> && TYPE_PRECISION (TREE_TYPE (expr)) <= TYPE_PRECISION
> (sizetype)));
>
> runs into ICEs when testing a 32bit target.
>
> But IVOPTs only makes use of the computed offset when it strips
> it off address uses. But what I only now realized is that
> IVOPTs strip_offset is also used by loop distribution.
>
> I'm going to split the patch in two at least to make these things
> more obvious before changing the implementation.
Hmm, but still split_constant_offset for example does
case MULT_EXPR:
if (TREE_CODE (op1) != INTEGER_CST)
return false;
split_constant_offset (op0, &var0, &off0, &op0_range, cache, limit);
op1_range.set (TREE_TYPE (op1), wi::to_wide (op1), wi::to_wide
(op1));
*off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
if (!compute_distributive_range (type, op0_range, code, op1_range,
off, result_range))
return false;
*var = fold_build2 (MULT_EXPR, sizetype, var0,
fold_convert (sizetype, op1));
so *var is affected as well since we might truncate op1 here. In
fact we at the end do
if (INTEGRAL_TYPE_P (type))
*var = fold_convert (sizetype, *var);
so truncate things (the API is documented to do that).
The issue in the PR the change is fixing is that we end up with
an expression that overflows but uses signed arithmetic and so
we miscompile it later. IIRC the fixes to split_constant_offset
always were that the sum of the base + offset wasn't equal to
the original expression, right?
Richard.
Richard Biener <rguenther@suse.de> writes:
> The issue in the PR the change is fixing is that we end up with
> an expression that overflows but uses signed arithmetic and so
> we miscompile it later. IIRC the fixes to split_constant_offset
> always were that the sum of the base + offset wasn't equal to
> the original expression, right?
Yeah, that's right. (sizetype)(INT_MIN - foo) was split into
(sizetype)INT_MIN + (sizetype)(-foo), and so we ended up with
((sizetype)INT_MIN)*2 rather than 0 for foo==INT_MIN.
Unfortunately, it looks like a lot of the discussion happened on
irc (my fault) and I didn't keep logs.
Thanks,
Richard
new file mode 100644
@@ -0,0 +1,22 @@
+/* { dg-do run } */
+/* { dg-require-effective-target lp64 } */
+
+#define X 1100000000
+unsigned char a;
+long b = X;
+int c[9][1];
+unsigned d;
+static long *e = &b, *f = &b;
+int g() {
+ if (a && a <= '9')
+ return '0';
+ if (a)
+ return 10;
+ return -1;
+}
+int main() {
+ d = 0;
+ for (; (int)*f -(X-1) + d < 9; d++)
+ c[g() + (int)*f + ((int)*e - X) -(X-1) + d]
+ [0] = 0;
+}
@@ -2772,183 +2772,21 @@ find_interesting_uses (struct ivopts_data *data, basic_block *body)
}
}
-/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR
- is true, assume we are inside an address. If TOP_COMPREF is true, assume
- we are at the top-level of the processed address. */
-
-static tree
-strip_offset_1 (tree expr, bool inside_addr, bool top_compref,
- poly_int64 *offset)
-{
- tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step;
- enum tree_code code;
- tree type, orig_type = TREE_TYPE (expr);
- poly_int64 off0, off1;
- HOST_WIDE_INT st;
- tree orig_expr = expr;
-
- STRIP_NOPS (expr);
-
- type = TREE_TYPE (expr);
- code = TREE_CODE (expr);
- *offset = 0;
-
- switch (code)
- {
- case POINTER_PLUS_EXPR:
- case PLUS_EXPR:
- case MINUS_EXPR:
- op0 = TREE_OPERAND (expr, 0);
- op1 = TREE_OPERAND (expr, 1);
-
- op0 = strip_offset_1 (op0, false, false, &off0);
- op1 = strip_offset_1 (op1, false, false, &off1);
-
- *offset = (code == MINUS_EXPR ? off0 - off1 : off0 + off1);
- if (op0 == TREE_OPERAND (expr, 0)
- && op1 == TREE_OPERAND (expr, 1))
- return orig_expr;
-
- if (integer_zerop (op1))
- expr = op0;
- else if (integer_zerop (op0))
- {
- if (code == MINUS_EXPR)
- expr = fold_build1 (NEGATE_EXPR, type, op1);
- else
- expr = op1;
- }
- else
- expr = fold_build2 (code, type, op0, op1);
-
- return fold_convert (orig_type, expr);
-
- case MULT_EXPR:
- op1 = TREE_OPERAND (expr, 1);
- if (!cst_and_fits_in_hwi (op1))
- return orig_expr;
-
- op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset_1 (op0, false, false, &off0);
- if (op0 == TREE_OPERAND (expr, 0))
- return orig_expr;
-
- *offset = off0 * int_cst_value (op1);
- if (integer_zerop (op0))
- expr = op0;
- else
- expr = fold_build2 (MULT_EXPR, type, op0, op1);
-
- return fold_convert (orig_type, expr);
-
- case ARRAY_REF:
- case ARRAY_RANGE_REF:
- if (!inside_addr)
- return orig_expr;
-
- step = array_ref_element_size (expr);
- if (!cst_and_fits_in_hwi (step))
- break;
-
- st = int_cst_value (step);
- op1 = TREE_OPERAND (expr, 1);
- op1 = strip_offset_1 (op1, false, false, &off1);
- *offset = off1 * st;
-
- if (top_compref
- && integer_zerop (op1))
- {
- /* Strip the component reference completely. */
- op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
- *offset += off0;
- return op0;
- }
- break;
-
- case COMPONENT_REF:
- {
- tree field;
-
- if (!inside_addr)
- return orig_expr;
-
- tmp = component_ref_field_offset (expr);
- field = TREE_OPERAND (expr, 1);
- if (top_compref
- && cst_and_fits_in_hwi (tmp)
- && cst_and_fits_in_hwi (DECL_FIELD_BIT_OFFSET (field)))
- {
- HOST_WIDE_INT boffset, abs_off;
-
- /* Strip the component reference completely. */
- op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0);
- boffset = int_cst_value (DECL_FIELD_BIT_OFFSET (field));
- abs_off = abs_hwi (boffset) / BITS_PER_UNIT;
- if (boffset < 0)
- abs_off = -abs_off;
-
- *offset = off0 + int_cst_value (tmp) + abs_off;
- return op0;
- }
- }
- break;
-
- case ADDR_EXPR:
- op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset_1 (op0, true, true, &off0);
- *offset += off0;
-
- if (op0 == TREE_OPERAND (expr, 0))
- return orig_expr;
-
- expr = build_fold_addr_expr (op0);
- return fold_convert (orig_type, expr);
-
- case MEM_REF:
- /* ??? Offset operand? */
- inside_addr = false;
- break;
-
- default:
- if (ptrdiff_tree_p (expr, offset) && maybe_ne (*offset, 0))
- return build_int_cst (orig_type, 0);
- return orig_expr;
- }
-
- /* Default handling of expressions for that we want to recurse into
- the first operand. */
- op0 = TREE_OPERAND (expr, 0);
- op0 = strip_offset_1 (op0, inside_addr, false, &off0);
- *offset += off0;
-
- if (op0 == TREE_OPERAND (expr, 0)
- && (!op1 || op1 == TREE_OPERAND (expr, 1)))
- return orig_expr;
-
- expr = copy_node (expr);
- TREE_OPERAND (expr, 0) = op0;
- if (op1)
- TREE_OPERAND (expr, 1) = op1;
-
- /* Inside address, we might strip the top level component references,
- thus changing type of the expression. Handling of ADDR_EXPR
- will fix that. */
- expr = fold_convert (orig_type, expr);
-
- return expr;
-}
-
/* Strips constant offsets from EXPR and stores them to OFFSET. */
tree
strip_offset (tree expr, poly_uint64_pod *offset)
{
- poly_int64 off;
- tree core = strip_offset_1 (expr, false, false, &off);
- *offset = off;
- return core;
+ tree core, toff;
+ split_constant_offset (expr, &core, &toff);
+ gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (toff)));
+ if (tree_fits_poly_int64_p (toff))
+ {
+ *offset = tree_to_poly_int64 (toff);
+ return core;
+ }
+ *offset = 0;
+ return expr;
}
/* Returns variant of TYPE that can be used as base for different uses.