[Bug tree-optimization/80153] ivopt generate wrong code

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

Richard Biener  changed:

   What|Removed |Added

 Status|NEW |RESOLVED
  Known to work||7.0.1
 Resolution|--- |FIXED

--- Comment #10 from Richard Biener  ---
Fixed for GCC 7.

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #9 from amker at gcc dot gnu.org ---
Author: amker
Date: Mon Apr 10 16:54:14 2017
New Revision: 246811

URL: https://gcc.gnu.org/viewcvs?rev=246811=gcc=rev
Log:
PR tree-optimization/80153
* tree-ssa-loop-ivopts.c (add_iv_candidate_for_use): Check and 
remove POINTER_PLUS_EXPR's base part directly, rather than through
aff_tree.

Modified:
trunk/gcc/ChangeLog
trunk/gcc/tree-ssa-loop-ivopts.c

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #8 from amker at gcc dot gnu.org ---
Author: amker
Date: Mon Apr 10 16:51:44 2017
New Revision: 246810

URL: https://gcc.gnu.org/viewcvs?rev=246810=gcc=rev
Log:
PR tree-optimization/80153
* tree-affine.c (aff_combination_to_tree): Get base pointer from
the first element of pointer type aff_tree.  Build result expr in
aff_tree's type.
(add_elt_to_tree): Convert to type unconditionally.  Remove other
fold_convert calls.
* tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
(rewrite_use_nonlinear_expr): Check invariant using iv information.
gcc/testsuite
PR tree-optimization/80153
* gcc.c-torture/execute/pr80153.c: New.

Added:
trunk/gcc/testsuite/gcc.c-torture/execute/pr80153.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-affine.c
trunk/gcc/tree-ssa-loop-ivopts.c

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #7 from amker at gcc dot gnu.org ---
Case gcc.dg/tree-ssa/reassoc-19 failed, the ivopt dump before change is:

   [15.00%]:
  goto ; [100.00%]

   [85.00%]:
  _1 = (sizetype) element_8(D);
  _2 = -_1;
  _12 = (unsigned long) element_8(D);
  _11 = -_12;
  _13 = rite_3 + _11;
  rite_9 = _13;
  bar (left_7(D), rite_9, element_8(D));

   [100.00%]:
  # rite_3 = PHI 
  if (rite_3 >= left_7(D))
goto ; [85.00%]
  else
goto ; [15.00%]

   [15.00%]:
  return;

But changed to below after change:
   [15.00%]:
  goto ; [100.00%]

   [85.00%]:
  _1 = (sizetype) element_8(D);
  _2 = -_1;
  _12 = (unsigned long) rite_3;
  _11 = (unsigned long) element_8(D);
  _13 = _12 - _11;
  _14 = (char *) _13;
  rite_9 = _14;
  bar (left_7(D), rite_9, element_8(D));

   [100.00%]:
  # rite_3 = PHI 
  if (rite_3 >= left_7(D))
goto ; [85.00%]
  else
goto ; [15.00%]

   [15.00%]:
  return;

I  don't think this is real regression here, assembly code is the same.  The
additional type conversion is introduced by get_computation_aff.  Though we
have 
utype: char *
ctype: char *
var->typed.type: char *
The function still computes the expression in uutype:
  uutype = unsigned_type_for (utype);
which is unsigned long here.

Actually, given the computation sequence:

  if (common_type != uutype)
aff_combination_convert (aff, uutype);

  aff_combination_scale (_aff, rat);
  aff_combination_add (aff, _aff);

I think type conversion is needed.  Of course, get_computation_aff should not
introduce unnecessary uutype conversion.

[Bug tree-optimization/80153] ivopt generate wrong code

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #6 from rguenther at suse dot de  ---
On Thu, 23 Mar 2017, amker at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153
> 
> --- Comment #5 from amker at gcc dot gnu.org ---
> Seems there is an issue that tree-affine lacks ability differentiating between
> (unsgined)(pointer + offset) and (unsigned)pointer + (unsigned)offset.

Yes, same for (unsigned)int + (unsigned)int and thus integer overflow.

> The current behavior of tree_to_aff_combination always folds type conversion
> into operands, generating exact the same affines for above two expressions:
> 
> {
>   type = unsigned int
>   offset = 6
>   elements = {
> [0] = "oops!\n" * 1,
> [1] = ivtmp.37_10 * 0x
>   }
> }
> 
> While converting affine back to tree, it takes the other way around, always
> generating the latter expression: (unsgined)(pointer + offset).  This causes
> problem.
> 
> IIUC, there are two possible fixes here.  First one is as you mentioned, we
> work conservatively and don't fold type conversion into operands (by not
> stripping nop).  I suspect this could causes serious code generation
> regression.

Yeah.

> The second one is the opposite, we always fold type conversion into operands,
> by keeping strip_nops.  While converting affine back to tree, we generate
> folded expression instead of trying to preserve pointer_plus expression as 
> now.
> I prefer the second one, and understand there is concern since tree affine is
> used in code generation we could lose pointer arithmetic semantic information
> like the pointer_plus expression never overflows/wraps.

I think it does that for integer arithmetic already (use unsigned for
all computation) but I may be mistaken...

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #5 from amker at gcc dot gnu.org ---
(In reply to Richard Biener from comment #4)
> The reason for the tree-affine oddity is that IVO calls
> 
> #0  tree_to_aff_combination (expr=, 
> type=, comb=0x7fffd310)
> 
> that is, tree_to_aff_combination with a mismatched expr/type.  For example
> from
> alloc_iv:
> 
> 1174  tree_to_aff_combination (expr, TREE_TYPE (base), );
> 1175  base = fold_convert (TREE_TYPE (base), aff_combination_to_tree
> ());
> 
I think it doesn't matter if we use base's type or expr's type here.  I will
test using consistent types here.

> that's unexpected.  But the problematic case happens where IVO does right:
> 
> Breakpoint 7, tree_to_aff_combination (expr=, 
> type=, comb=0x7fffd4a0)
> 
> but tree_to_aff_combination calls STRIP_NOPS on expr which is (unsigned int)
> "oops!\n" and thus creates the above problematical case itself.
> 
> We can either avoid stripping the nops or deal with the appearant mismatch
> by converting back the elts we add to 'type'.  I think instrumenting to
> see whether we can assert tree_to_aff_combination gets matched types passed
> (so we can eliminate the type arg) would be nice - we certainly can't handle
> all kind of mismatches sanely.
> 
> Then using STRIP_SIGN_NOPS would be safe but IIRC removing sign conversions
> was intentional (though even that might be problematic).  tree-affine was
> really designed for addresses (so type would always be a pointer).
> 
> So sth like the following should better pass bootstrap / test (IVO will
> trigger
> the assert) but it might require adding some "safe" cases to not regress
> code quality (not sure if we have testcases):
> 
> Index: gcc/tree-affine.c
> ===
> --- gcc/tree-affine.c   (revision 246414)
> +++ gcc/tree-affine.c   (working copy)
> @@ -261,12 +261,21 @@ tree_to_aff_combination (tree expr, tree
>HOST_WIDE_INT bitpos, bitsize;
>machine_mode mode;
>int unsignedp, reversep, volatilep;
> +  tree exptype = TREE_TYPE (expr);
>  
> -  STRIP_NOPS (expr);
> +  gcc_checking_assert (tree_nop_conversion_p (type, exptype)
> +  && TYPE_UNSIGNED (type) == TYPE_UNSIGNED (exptype)
> +  && POINTER_TYPE_P (type) == POINTER_TYPE_P (exptype));
> +
> +  STRIP_SIGN_NOPS (expr);
>  
>code = TREE_CODE (expr);
>switch (code)
>  {
> +CASE_CONVERT:
> +  /* Add safe cases.  */
> +  break;
> +
>  case INTEGER_CST:
>aff_combination_const (comb, type, wi::to_widest (expr));
>return;

Seems there is an issue that tree-affine lacks ability differentiating between
(unsgined)(pointer + offset) and (unsigned)pointer + (unsigned)offset.

The current behavior of tree_to_aff_combination always folds type conversion
into operands, generating exact the same affines for above two expressions:

{
  type = unsigned int
  offset = 6
  elements = {
[0] = "oops!\n" * 1,
[1] = ivtmp.37_10 * 0x
  }
}

While converting affine back to tree, it takes the other way around, always
generating the latter expression: (unsgined)(pointer + offset).  This causes
problem.

IIUC, there are two possible fixes here.  First one is as you mentioned, we
work conservatively and don't fold type conversion into operands (by not
stripping nop).  I suspect this could causes serious code generation
regression.
The second one is the opposite, we always fold type conversion into operands,
by keeping strip_nops.  While converting affine back to tree, we generate
folded expression instead of trying to preserve pointer_plus expression as now.
I prefer the second one, and understand there is concern since tree affine is
used in code generation we could lose pointer arithmetic semantic information
like the pointer_plus expression never overflows/wraps.  But, I think we can
afford this, considering possible code generation regression in the other way. 
I think there shouldn't be fundamental difference in code generation given we
have or don't have the pointer_plus information.  More important, IMHO, tree
affine should (only?) be used when trying to explore as many CSE opportunities
as possible by breaking most association order issues, like in IVOPTs.  So,
customer of tree affine should (at least for most cases) use tree-affine in
code generation only when it finds out there is benefit to do so.  If there is
no benefit, IVOPT wouldn't choose the corresponding candidate.  Lastly, this
only affects type conversion of pointer_plus expressions (IVOPTs only because
it uses unsigned type in order to avoid overflow handling), a customer only
builds pointer type tree affine won't be affected.

Testing patch, let's see if there is any fallout.  Thanks

[Bug tree-optimization/80153] ivopt generate wrong code

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #4 from Richard Biener  ---
The reason for the tree-affine oddity is that IVO calls

#0  tree_to_aff_combination (expr=, 
type=, comb=0x7fffd310)

that is, tree_to_aff_combination with a mismatched expr/type.  For example from
alloc_iv:

1174  tree_to_aff_combination (expr, TREE_TYPE (base), );
1175  base = fold_convert (TREE_TYPE (base), aff_combination_to_tree
());

that's unexpected.  But the problematic case happens where IVO does right:

Breakpoint 7, tree_to_aff_combination (expr=, 
type=, comb=0x7fffd4a0)

but tree_to_aff_combination calls STRIP_NOPS on expr which is (unsigned int)
"oops!\n" and thus creates the above problematical case itself.

We can either avoid stripping the nops or deal with the appearant mismatch
by converting back the elts we add to 'type'.  I think instrumenting to
see whether we can assert tree_to_aff_combination gets matched types passed
(so we can eliminate the type arg) would be nice - we certainly can't handle
all kind of mismatches sanely.

Then using STRIP_SIGN_NOPS would be safe but IIRC removing sign conversions
was intentional (though even that might be problematic).  tree-affine was
really designed for addresses (so type would always be a pointer).

So sth like the following should better pass bootstrap / test (IVO will trigger
the assert) but it might require adding some "safe" cases to not regress
code quality (not sure if we have testcases):

Index: gcc/tree-affine.c
===
--- gcc/tree-affine.c   (revision 246414)
+++ gcc/tree-affine.c   (working copy)
@@ -261,12 +261,21 @@ tree_to_aff_combination (tree expr, tree
   HOST_WIDE_INT bitpos, bitsize;
   machine_mode mode;
   int unsignedp, reversep, volatilep;
+  tree exptype = TREE_TYPE (expr);

-  STRIP_NOPS (expr);
+  gcc_checking_assert (tree_nop_conversion_p (type, exptype)
+  && TYPE_UNSIGNED (type) == TYPE_UNSIGNED (exptype)
+  && POINTER_TYPE_P (type) == POINTER_TYPE_P (exptype));
+
+  STRIP_SIGN_NOPS (expr);

   code = TREE_CODE (expr);
   switch (code)
 {
+CASE_CONVERT:
+  /* Add safe cases.  */
+  break;
+
 case INTEGER_CST:
   aff_combination_const (comb, type, wi::to_widest (expr));
   return;

[Bug tree-optimization/80153] ivopt generate wrong code

[palmer at dabbelt dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

--- Comment #3 from Palmer Dabbelt  ---
Thanks for looking at this.

If there's anything I can do to help feel free to ask, but from my understand
this isn't a RISC-V backend problem so I'm not going to put this on my TODO
list unless something changes (or someone corrects me).

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

amker at gcc dot gnu.org changed:

   What|Removed |Added

 CC||rguenth at gcc dot gnu.org

--- Comment #2 from amker at gcc dot gnu.org ---
Hmm, for tree affine:
(gdb) call debug_aff()
{
  type = unsigned int
  offset = 6
  elements = {
[0] = "oops!\n" * 1,
[1] = ivtmp.37_10 * 0x
  }
}

aff_combination_to_tree returns a pointer_plus expression with chanr * type:

(gdb) call debug_generic_expr(arg)
"oops!\n" + (6 - (sizetype) ivtmp.37_10)

(gdb) call debug_tree(arg)
 
BLK
size 
unit size 
align 8 symtab 0 alias set -1 canonical type 0x76ce5dc8 domain

pointer_to_this >
public unsigned SI
size 
unit size 
align 32 symtab 0 alias set -1 canonical type 0x76ce5e70>

arg 0 
readonly constant
arg 0 
readonly constant static "oops!\012\000">>
arg 1  unit size 
align 32 symtab 0 alias set -1 canonical type 0x76c32000
precision 32 min  max >

arg 0 
arg 1 

arg 0 
var 
def_stmt ivtmp.37_10 = PHI 
version 10

But, it really should be:
(unsigned int)"oops!\n" + (6 - (sizetype) ivtmp.37_10)

So, when the expression should be ZERO, GCC proves "oops!\n" + (6 - (sizetype)
ivtmp.37_10) can never be ZERO based on pointer semantics.

CCing Richard for further comments.
In function add_elt_to_tree, there is:
  if (!expr)
{
  if (POINTER_TYPE_P (TREE_TYPE (elt)))
return elt;
  else
return fold_convert (type1, elt);
}
which means we return pointer type expr even it is requested to generate
unsigned type expr.

[Bug tree-optimization/80153] ivopt generate wrong code

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80153

amker at gcc dot gnu.org changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2017-03-22
 CC||amker at gcc dot gnu.org
 Ever confirmed|0   |1

--- Comment #1 from amker at gcc dot gnu.org ---
I can reproduce the issue on AArch64 if specific candidate is chosen. 
Something is wrong, I will investigate it.