[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 Bug 58417 depends on bug 58484, which changed state. Bug 58484 Summary: [4.9 Regression] ICE in chrec_fold_plus_1, at tree-chrec.c:272 building 416.gamess http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58484 What|Removed |Added Status|ASSIGNED|RESOLVED Resolution|--- |FIXED
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 Bug 58417 depends on bug 58473, which changed state. Bug 58473 Summary: [4.9 regression] FAIL: ext/random/normal_mv_distribution/cons/default.cc (test for excess errors) http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58473 What|Removed |Added Status|ASSIGNED|RESOLVED Resolution|--- |FIXED
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 Richard Biener changed: What|Removed |Added Status|ASSIGNED|RESOLVED Known to work||4.9.0 Resolution|--- |FIXED --- Comment #8 from Richard Biener --- Fixed on trunk.
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 --- Comment #7 from Richard Biener --- Author: rguenth Date: Wed Sep 18 12:31:45 2013 New Revision: 202700 URL: http://gcc.gnu.org/viewcvs?rev=202700&root=gcc&view=rev Log: 2013-09-18 Richard Biener PR tree-optimization/58417 * tree-chrec.c (chrec_fold_plus_1): Assert that we do not have chrecs with symbols defined in the loop as operands. (chrec_fold_multiply): Likewise. * tree-scalar-evolution.c (interpret_rhs_expr): Instantiate parameters before folding binary operations. (struct instantiate_cache_entry_hasher): Remove. (struct instantiate_cache_type): Use a pointer-map. (instantiate_cache_type::instantiate_cache_type): New function. (instantiate_cache_type::get): Likewise. (instantiate_cache_type::set): Likewise. (instantiate_cache_type::~instantiate_cache_type): Adjust. (get_instantiated_value_entry): Likewise. (global_cache): New global. (instantiate_scev_r, instantiate_scev_poly, instantiate_scev_binary, instantiate_array_ref, instantiate_scev_convert, instantiate_scev_3, instantiate_scev_2, instantiate_scev_1): Do not pass along cache. (instantiate_scev_name): Adjust. (instantiate_scev): Construct global instead of local cache. (resolve_mixers): Likewise. * gcc.dg/torture/pr58417.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/torture/pr58417.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-chrec.c trunk/gcc/tree-scalar-evolution.c
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417
--- Comment #6 from Richard Biener ---
So we want the evolution of sum_11 in the following loop (for a use on the
exit edge):
# i_18 = PHI
# sum_19 = PHI
# prevsum_21 = PHI
foo (sum_19);
_7 = i_18 + -1;
_8 = (long long int) _7;
_9 = arr[i_18];
_10 = _8 * _9;
sum_11 = _10 - prevsum_21;
prevsum_12 = prevsum_21 + _9;
i_13 = i_18 + 1;
if (i_13 <= 5)
goto ;
else
goto ;
:
goto ;
and we compute
_10 = {0, +, _9}_1
_prevsum_21 = {0, +, _9}_1
but that is really meaningless as _9 is not a loop invariant which means that
this two very CHRECs are not "valid" as far as I understand, not valid to
operate on at least.
Thus the following asserts should IMHO hold (and trigger on the testcase
and many others)
Index: gcc/tree-chrec.c
===
--- gcc/tree-chrec.c(revision 202644)
+++ gcc/tree-chrec.c(working copy)
@@ -268,9 +268,14 @@ chrec_fold_plus_1 (enum tree_code code,
switch (TREE_CODE (op0))
{
case POLYNOMIAL_CHREC:
+ gcc_checking_assert
+ (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
+ gcc_checking_assert
+ (!chrec_contains_symbols_defined_in_loop (op1,
+ CHREC_VARIABLE (op1)));
return chrec_fold_plus_poly_poly (code, type, op0, op1);
CASE_CONVERT:
@@ -298,6 +303,9 @@ chrec_fold_plus_1 (enum tree_code code,
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
+ gcc_checking_assert
+ (!chrec_contains_symbols_defined_in_loop (op1,
+ CHREC_VARIABLE (op1)));
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
@@ -396,9 +404,14 @@ chrec_fold_multiply (tree type,
switch (TREE_CODE (op0))
{
case POLYNOMIAL_CHREC:
+ gcc_checking_assert
+ (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
+ gcc_checking_assert
+ (!chrec_contains_symbols_defined_in_loop (op1,
+ CHREC_VARIABLE (op1)));
return chrec_fold_multiply_poly_poly (type, op0, op1);
CASE_CONVERT:
@@ -431,6 +444,9 @@ 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),
as of the recursion we can fix that by making the cache used to guard against
the recursion global (and maybe use instantiate_parameters instead of
resolve_mixers).
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 --- Comment #5 from Richard Biener --- But that eventually causes infinite recursions through instantiate_scev.
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417
Richard Biener changed:
What|Removed |Added
CC||sebpop at gmail dot com
--- Comment #4 from Richard Biener ---
SCCP does "constant propagation" each SSA name at the beginning which is where
it replaces sum_23 with 0. It ends up there through interpret_condition_phi
with respect to loop 0 which analyzes the scalar evolution of
sum_11 in loop 1 to 0 because it simply passes down the loop
#2 0x00c417c2 in interpret_condition_phi (loop=0x76d13320,
condition_phi=)
at /space/rguenther/src/svn/trunk/gcc/tree-scalar-evolution.c:1585
1585(loop, PHI_ARG_DEF (condition_phi, i));
(gdb) l
1580 res = chrec_dont_know;
1581 break;
1582}
1583
1584 branch_chrec = analyze_scalar_evolution
1585(loop, PHI_ARG_DEF (condition_phi, i));
1586
1587 res = chrec_merge (res, branch_chrec);
1588}
that is, this is a loop-closed PHI node, not a "condition PHI". The
SSA edge following code seems to have the same issues.
That is, if an edge into a PHI is coming from an inner loop then we need
to compute the evolution of the PHI arg with respect to that (the definition
loop) and compute the overall effects for that inner loop before using
the result.
Hm, but analyzing sum_11 in loop1 results in
_10 = {0, +, _9}_1
prevsum_21 = {0, +, _9}_1
and thus sum_11 = _10 - prevsum_21 = 0.
Hmm. I don't think that's a valid CHREC (_9 is defined in loop 1). And
indeed resolve_mixers will drop those to scev_not_known. But it doesn't
get to that as we first cancel the thing by doing the minus ...
So,
Index: tree-scalar-evolution.c
===
--- tree-scalar-evolution.c (revision 202619)
+++ tree-scalar-evolution.c (working copy)
@@ -1699,6 +1699,8 @@ interpret_rhs_expr (struct loop *loop, g
chrec2 = analyze_scalar_evolution (loop, rhs2);
chrec1 = chrec_convert (type, chrec1, at_stmt);
chrec2 = chrec_convert (type, chrec2, at_stmt);
+ chrec1 = resolve_mixers (loop, chrec1);
+ chrec2 = resolve_mixers (loop, chrec2);
res = chrec_fold_minus (type, chrec1, chrec2);
break;
fixes this, but ... I suppose we need to do that for each binary/ternary
op and chrec (or just those that call chrec_fold_{plus,minus}).
That said, we cannot hope on such SSA names canceling themselves out
as they may not refer to the same actual value.
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417 Richard Biener changed: What|Removed |Added Status|NEW |ASSIGNED Assignee|unassigned at gcc dot gnu.org |rguenth at gcc dot gnu.org --- Comment #3 from Richard Biener --- I will have a look.
[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58417
Richard Biener changed:
What|Removed |Added
Keywords||wrong-code
Summary|Incorrect optimization |Incorrect optimization in
||SCEV const-prop
Known to fail||4.4.7, 4.5.4, 4.6.4, 4.7.3,
||4.8.1, 4.9.0
--- Comment #2 from Richard Biener ---
C testcase that fails everywhere:
/* { dg-do run } */
long long arr[6] = {0, 1, 2, 3, 4, 5};
extern void abort (void);
void __attribute__((noinline,noclone))
foo (long long sum)
{
asm ("");
}
int main()
{
int i, n = 5;
long long sum = 0, prevsum = 0;
for(i = 1; i <= n; i++)
{
foo (sum);
sum = (i - 1) * arr[i] - prevsum;
prevsum += arr[i];
}
if (sum != 10)
abort ();
return 0;
}
