* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
[not found] <83476.124022609150401789@us-mta-131.us.mimecast.lan>
@ 2024-02-26 14:22 ` Jakub Jelinek
2024-02-26 14:29 ` Richard Biener
0 siblings, 1 reply; 7+ messages in thread
From: Jakub Jelinek @ 2024-02-26 14:22 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On Mon, Feb 26, 2024 at 03:15:02PM +0100, Richard Biener wrote:
> When folding a multiply CHRECs are handled like {a, +, b} * c
> is {a*c, +, b*c} but that isn't generally correct when overflow
> invokes undefined behavior. The following uses unsigned arithmetic
> unless either a is zero or a and b have the same sign.
>
> I've used simple early outs for INTEGER_CSTs and otherwise use
> a range-query since we lack a tree_expr_nonpositive_p.
What about testing
(get_range_pos_neg (CHREC_LEFT (op0))
| get_range_pos_neg (CHREC_RIGHT (op0))) != 3
?
Jakub
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
2024-02-26 14:22 ` [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow Jakub Jelinek
@ 2024-02-26 14:29 ` Richard Biener
2024-02-26 14:45 ` Jakub Jelinek
0 siblings, 1 reply; 7+ messages in thread
From: Richard Biener @ 2024-02-26 14:29 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On Mon, 26 Feb 2024, Jakub Jelinek wrote:
> On Mon, Feb 26, 2024 at 03:15:02PM +0100, Richard Biener wrote:
> > When folding a multiply CHRECs are handled like {a, +, b} * c
> > is {a*c, +, b*c} but that isn't generally correct when overflow
> > invokes undefined behavior. The following uses unsigned arithmetic
> > unless either a is zero or a and b have the same sign.
> >
> > I've used simple early outs for INTEGER_CSTs and otherwise use
> > a range-query since we lack a tree_expr_nonpositive_p.
>
> What about testing
> (get_range_pos_neg (CHREC_LEFT (op0))
> | get_range_pos_neg (CHREC_RIGHT (op0))) != 3
> ?
Ah, didn't know about that. It seems to treat zero as "always
positive", so for 0 and -1 I'd get 3. OK as I check for
zero CHREC_LEFT separately.
I'll note that get_range_pos_neg only asks global range query
and for SSA names (but not sure if range_of_expr handles aribitrary
GENERIC as SCEV tends to have here ...).
Will update the patch, I think any improvement should be done
to get_range_pos_neg (it's a bit odd in behavior for unsigned
but I have only signed things incoming).
Richard.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
2024-02-26 14:29 ` Richard Biener
@ 2024-02-26 14:45 ` Jakub Jelinek
2024-02-26 15:51 ` Michael Matz
0 siblings, 1 reply; 7+ messages in thread
From: Jakub Jelinek @ 2024-02-26 14:45 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On Mon, Feb 26, 2024 at 03:29:30PM +0100, Richard Biener wrote:
> On Mon, 26 Feb 2024, Jakub Jelinek wrote:
>
> > On Mon, Feb 26, 2024 at 03:15:02PM +0100, Richard Biener wrote:
> > > When folding a multiply CHRECs are handled like {a, +, b} * c
> > > is {a*c, +, b*c} but that isn't generally correct when overflow
> > > invokes undefined behavior. The following uses unsigned arithmetic
> > > unless either a is zero or a and b have the same sign.
> > >
> > > I've used simple early outs for INTEGER_CSTs and otherwise use
> > > a range-query since we lack a tree_expr_nonpositive_p.
> >
> > What about testing
> > (get_range_pos_neg (CHREC_LEFT (op0))
> > | get_range_pos_neg (CHREC_RIGHT (op0))) != 3
> > ?
>
> Ah, didn't know about that. It seems to treat zero as "always
> positive", so for 0 and -1 I'd get 3. OK as I check for
> zero CHREC_LEFT separately.
The function has been used where one cares about the possible values
of the sign bit, so 0 in that case is 0 sign bit.
If you want to differentiate between negative, 0 and positive and allow
non-positive with non-positive or non-negative with non-negative together,
then it isn't the right function to call (unless we add tracking if the
value can be zero, return bitmask with 3 bits rather than 2 and adjust
all callers).
> I'll note that get_range_pos_neg only asks global range query
> and for SSA names (but not sure if range_of_expr handles aribitrary
> GENERIC as SCEV tends to have here ...).
I think range_of_expr should handle usual GENERIC trees and punt on stuff it
doesn't handle. And your patch was using ranger from current pass while
get_range_pos_neg uses always the global ranges (it is usually used during
expansion where the pass doesn't have its ranger instance).
Though, if you don't ask for range on a particular statement, it doesn't
really matter and is just a global range query.
> Will update the patch, I think any improvement should be done
> to get_range_pos_neg (it's a bit odd in behavior for unsigned
> but I have only signed things incoming).
For unsigned if it always returned 1, it would be quite useless, there would
be no point for the caller to call it in that case.
Jakub
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
2024-02-26 14:45 ` Jakub Jelinek
@ 2024-02-26 15:51 ` Michael Matz
2024-02-26 15:56 ` Jakub Jelinek
0 siblings, 1 reply; 7+ messages in thread
From: Michael Matz @ 2024-02-26 15:51 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Biener, gcc-patches
Hello,
On Mon, 26 Feb 2024, Jakub Jelinek wrote:
> > Will update the patch, I think any improvement should be done
> > to get_range_pos_neg (it's a bit odd in behavior for unsigned
> > but I have only signed things incoming).
>
> For unsigned if it always returned 1, it would be quite useless, there would
> be no point for the caller to call it in that case.
Which seems to make sense for a function called ...pos_neg on unsigned
types. I would expect calling it to be useless and always return "yep,
non-negative, why did you ask?".
Ciao,
Michael.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
2024-02-26 15:51 ` Michael Matz
@ 2024-02-26 15:56 ` Jakub Jelinek
0 siblings, 0 replies; 7+ messages in thread
From: Jakub Jelinek @ 2024-02-26 15:56 UTC (permalink / raw)
To: Michael Matz; +Cc: Richard Biener, gcc-patches
On Mon, Feb 26, 2024 at 04:51:08PM +0100, Michael Matz wrote:
> On Mon, 26 Feb 2024, Jakub Jelinek wrote:
>
> > > Will update the patch, I think any improvement should be done
> > > to get_range_pos_neg (it's a bit odd in behavior for unsigned
> > > but I have only signed things incoming).
> >
> > For unsigned if it always returned 1, it would be quite useless, there would
> > be no point for the caller to call it in that case.
>
> Which seems to make sense for a function called ...pos_neg on unsigned
> types. I would expect calling it to be useless and always return "yep,
> non-negative, why did you ask?".
The callers heavily rely on it doing for unsigned types what it does now
and it matches what the function comment says.
If you have a suggestion for a different name that wouldn't be much longer
than the current one, it can be renamed.
get_msb_range?
Except it doesn't return a range for the most significant bit, but a bitmask
which values are possible.
Jakub
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
[not found] <20240226141510.C27103858C33@sourceware.org>
@ 2024-02-26 16:02 ` Jakub Jelinek
0 siblings, 0 replies; 7+ messages in thread
From: Jakub Jelinek @ 2024-02-26 16:02 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On Mon, Feb 26, 2024 at 03:15:02PM +0100, Richard Biener wrote:
> When folding a multiply CHRECs are handled like {a, +, b} * c
> is {a*c, +, b*c} but that isn't generally correct when overflow
> invokes undefined behavior. The following uses unsigned arithmetic
> unless either a is zero or a and b have the same sign.
>
> I've used simple early outs for INTEGER_CSTs and otherwise use
> a range-query since we lack a tree_expr_nonpositive_p.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> I'm not sure it's worth using ranger, there might be also more
> cases where the integer multiply is OK, say when abs (A) > abs (B).
> But also {-2, +, 2}, but not for {1, +, -1} for example.
So, given that we found that get_range_pos_neg is not what you want,
I think the patch is ok, except a minor nit
> @@ -428,10 +434,41 @@ chrec_fold_multiply (tree type,
> if (integer_zerop (op1))
> return build_int_cst (type, 0);
>
> - return build_polynomial_chrec
> - (CHREC_VARIABLE (op0),
> - chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
> - chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
> + /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
> + same sign or CHREC_LEFT is zero then folding the multiply into
> + the addition does not have the same behavior on overflow. Use
> + unsigned arithmetic in that case. */
> + value_range rl, rr;
> + if (!ANY_INTEGRAL_TYPE_P (type)
> + || TYPE_OVERFLOW_WRAPS (type)
> + || integer_zerop (CHREC_LEFT (op0))
> + || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
> + && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
> + && (tree_int_cst_sgn (CHREC_LEFT (op0))
> + == tree_int_cst_sgn (CHREC_RIGHT (op0))))
> + || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
> + && !rl.undefined_p ()
> + && (rl.nonpositive_p () || rl.nonnegative_p ())
> + && get_range_query (cfun)->range_of_expr (rr, CHREC_RIGHT (op0))
> + && !rr.undefined_p ()
> + && ((rl.nonpositive_p () && rr.nonpositive_p ())
> + || (rl.nonnegative_p () && rr.nonnegative_p ()))))
> + return build_polynomial_chrec
> + (CHREC_VARIABLE (op0),
> + chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
> + chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
> + else
> + {
> + tree utype = unsigned_type_for (type);
> + op1 = chrec_convert_rhs (utype, op1);
> + tree tem = build_polynomial_chrec
> + (CHREC_VARIABLE (op0),
> + chrec_fold_multiply
> + (utype, chrec_convert_rhs (utype, CHREC_LEFT (op0)), op1),
> + chrec_fold_multiply
> + (utype, chrec_convert_rhs (utype, CHREC_RIGHT (op0)), op1));
> + return chrec_convert_rhs (type, tem);
When you touch these, can you please rewrite it to more readable code with
temporaries, instead of the ugly calls with ( on different line from the
function name?
{
tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
return build_polynomial_chrec (CHREC_VARIABLE (op0),
left, right);
}
and
tree left = chrec_convert_rhs (utype, CHREC_LEFT (op0));
left = chrec_fold_multiply (utype, left, op1);
tree right = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
right = chrec_fold_multiply (utype, right, op1);
tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
left, right);
return chrec_convert_rhs (type, tem);
?
Jakub
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow
@ 2024-02-26 14:15 Richard Biener
0 siblings, 0 replies; 7+ messages in thread
From: Richard Biener @ 2024-02-26 14:15 UTC (permalink / raw)
To: gcc-patches; +Cc: Jakub Jelinek
When folding a multiply CHRECs are handled like {a, +, b} * c
is {a*c, +, b*c} but that isn't generally correct when overflow
invokes undefined behavior. The following uses unsigned arithmetic
unless either a is zero or a and b have the same sign.
I've used simple early outs for INTEGER_CSTs and otherwise use
a range-query since we lack a tree_expr_nonpositive_p.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
I'm not sure it's worth using ranger, there might be also more
cases where the integer multiply is OK, say when abs (A) > abs (B).
But also {-2, +, 2}, but not for {1, +, -1} for example.
OK?
Thanks,
Richard.
PR tree-optimization/114074
* tree-chrec.h (chrec_convert_rhs): Default at_stmt arg to NULL.
* tree-chrec.cc (chrec_fold_multiply): Canonicalize inputs.
Handle poly vs. non-poly multiplication correctly with respect
to undefined behavior on overflow.
* gcc.dg/torture/pr114074.c: New testcase.
* gcc.dg/pr68317.c: Adjust expected location of diagnostic.
---
gcc/testsuite/gcc.dg/pr68317.c | 4 +-
gcc/testsuite/gcc.dg/torture/pr114074.c | 27 +++++++++++++
gcc/tree-chrec.cc | 53 ++++++++++++++++++++-----
gcc/tree-chrec.h | 2 +-
4 files changed, 72 insertions(+), 14 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/pr114074.c
diff --git a/gcc/testsuite/gcc.dg/pr68317.c b/gcc/testsuite/gcc.dg/pr68317.c
index bd053a7522b..06cd2e1da9c 100644
--- a/gcc/testsuite/gcc.dg/pr68317.c
+++ b/gcc/testsuite/gcc.dg/pr68317.c
@@ -12,8 +12,8 @@ foo ()
{
int32_t index = 0;
- for (index; index <= 10; index--) // expected warning here
+ for (index; index <= 10; index--) /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */
/* Result of the following multiply will overflow
when converted to signed int32_t. */
- bar ((0xcafe + index) * 0xdead); /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */
+ bar ((0xcafe + index) * 0xdead);
}
diff --git a/gcc/testsuite/gcc.dg/torture/pr114074.c b/gcc/testsuite/gcc.dg/torture/pr114074.c
new file mode 100644
index 00000000000..336e97673c3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr114074.c
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+
+int a, b, d;
+
+__attribute__((noipa)) void
+foo (void)
+{
+ ++d;
+}
+
+int
+main ()
+{
+ for (a = 0; a > -3; a -= 2)
+ {
+ int c = a;
+ b = __INT_MAX__ - 3000;
+ a = ~c * b;
+ foo ();
+ if (!a)
+ break;
+ a = c;
+ }
+ if (d != 2)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
index 61456fe1141..1b1023f68af 100644
--- a/gcc/tree-chrec.cc
+++ b/gcc/tree-chrec.cc
@@ -38,6 +38,8 @@ along with GCC; see the file COPYING3. If not see
#include "gimple.h"
#include "tree-ssa-loop.h"
#include "dumpfile.h"
+#include "value-range.h"
+#include "value-query.h"
#include "tree-scalar-evolution.h"
/* Extended folder for chrecs. */
@@ -404,6 +406,10 @@ chrec_fold_multiply (tree type,
|| automatically_generated_chrec_p (op1))
return chrec_fold_automatically_generated_operands (op0, op1);
+ if (TREE_CODE (op0) != POLYNOMIAL_CHREC
+ && TREE_CODE (op1) == POLYNOMIAL_CHREC)
+ std::swap (op0, op1);
+
switch (TREE_CODE (op0))
{
case POLYNOMIAL_CHREC:
@@ -428,10 +434,41 @@ chrec_fold_multiply (tree type,
if (integer_zerop (op1))
return build_int_cst (type, 0);
- return build_polynomial_chrec
- (CHREC_VARIABLE (op0),
- chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
- chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
+ /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
+ same sign or CHREC_LEFT is zero then folding the multiply into
+ the addition does not have the same behavior on overflow. Use
+ unsigned arithmetic in that case. */
+ value_range rl, rr;
+ if (!ANY_INTEGRAL_TYPE_P (type)
+ || TYPE_OVERFLOW_WRAPS (type)
+ || integer_zerop (CHREC_LEFT (op0))
+ || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
+ && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
+ && (tree_int_cst_sgn (CHREC_LEFT (op0))
+ == tree_int_cst_sgn (CHREC_RIGHT (op0))))
+ || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
+ && !rl.undefined_p ()
+ && (rl.nonpositive_p () || rl.nonnegative_p ())
+ && get_range_query (cfun)->range_of_expr (rr, CHREC_RIGHT (op0))
+ && !rr.undefined_p ()
+ && ((rl.nonpositive_p () && rr.nonpositive_p ())
+ || (rl.nonnegative_p () && rr.nonnegative_p ()))))
+ return build_polynomial_chrec
+ (CHREC_VARIABLE (op0),
+ chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
+ chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
+ else
+ {
+ tree utype = unsigned_type_for (type);
+ op1 = chrec_convert_rhs (utype, op1);
+ tree tem = build_polynomial_chrec
+ (CHREC_VARIABLE (op0),
+ chrec_fold_multiply
+ (utype, chrec_convert_rhs (utype, CHREC_LEFT (op0)), op1),
+ chrec_fold_multiply
+ (utype, chrec_convert_rhs (utype, CHREC_RIGHT (op0)), op1));
+ return chrec_convert_rhs (type, tem);
+ }
}
CASE_CONVERT:
@@ -449,13 +486,7 @@ chrec_fold_multiply (tree type,
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
- gcc_checking_assert
- (!chrec_contains_symbols_defined_in_loop (op1,
- CHREC_VARIABLE (op1)));
- return build_polynomial_chrec
- (CHREC_VARIABLE (op1),
- chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
- chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
+ gcc_unreachable ();
CASE_CONVERT:
if (tree_contains_chrecs (op1, NULL))
diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index e3a5ba55885..8003eb53a39 100644
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -63,7 +63,7 @@ extern tree chrec_fold_plus (tree, tree, tree);
extern tree chrec_fold_minus (tree, tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL);
-extern tree chrec_convert_rhs (tree, tree, gimple *);
+extern tree chrec_convert_rhs (tree, tree, gimple * = NULL);
extern tree chrec_convert_aggressive (tree, tree, bool *);
/* Operations. */
--
2.35.3
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2024-02-26 16:02 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <83476.124022609150401789@us-mta-131.us.mimecast.lan>
2024-02-26 14:22 ` [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow Jakub Jelinek
2024-02-26 14:29 ` Richard Biener
2024-02-26 14:45 ` Jakub Jelinek
2024-02-26 15:51 ` Michael Matz
2024-02-26 15:56 ` Jakub Jelinek
[not found] <20240226141510.C27103858C33@sourceware.org>
2024-02-26 16:02 ` Jakub Jelinek
2024-02-26 14:15 Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).