Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
Richard Biener 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
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
On Wed, 21 Jun 2023, Richard Biener wrote: > On Tue, 20 Jun 2023, Richard Sandiford wrote: > > > Richard Biener writes: > > > On Mon, 19 Jun 2023, Richard Sandiford wrote: > > > > > >> Jeff Law 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.
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
On Tue, 20 Jun 2023, Richard Sandiford wrote: > Richard Biener writes: > > On Mon, 19 Jun 2023, Richard Sandiford wrote: > > > >> Jeff Law 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.
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
Richard Biener writes: > On Mon, 19 Jun 2023, Richard Sandiford wrote: > >> Jeff Law 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
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
On Mon, 19 Jun 2023, Richard Sandiford wrote: > Jeff Law 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.
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
Jeff Law 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
Re: [PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
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
[PATCH] tree-optimization/110243 - kill off IVOPTs split_offset
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 diff --git a/gcc/testsuite/gcc.dg/torture/pr110243.c b/gcc/testsuite/gcc.dg/torture/pr110243.c new file mode 100644 index 000..07dffd95d4d --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr110243.c @@ -0,0 +1,22 @@ +/* { dg-do run } */ +/* { dg-require-effective-target lp64 } */ + +#define X 11 +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; +} diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index 6fbd2d59318..a03764072a4 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -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_fit