[PATCH PR80153]Always generate folded type conversion in tree-affine

[PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin Cheng]

[-- Attachment #1: Type: text/plain, Size: 1395 bytes --]

Hi,
This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset, 
even worse, it always returns the former expression in aff_combination_tree, which
is wrong if the original expression has the latter form.  The patch resolves the issue
by always returning the latter form expression, i.e, always trying to generate folded
expression.  Also as analyzed in comment, I think this change won't result in substantial
code gen difference.  
I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
Well, I think the changed behavior is correct, but for case the original pointer candidate
is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
Bootstrap and test on x86_64 and AArch64.  Is it OK?

2017-03-27  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/80153
	* tree-affine.c (add_elt_to_tree): Convert to type as required
	by function's parameter.
	* tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
	(get_computation_aff): Use utype directly for original candidate.

gcc/testsuite/ChangeLog
2017-03-27  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/80153
	* gcc.c-torture/execute/pr80153.c: New.

[-- Attachment #2: pr80153-20170327.txt --]
[-- Type: text/plain, Size: 2585 bytes --]

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
new file mode 100644
index 0000000..3eed578
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/80153 */
+
+void check (int, int, int) __attribute__((noinline));
+void check (int c, int c2, int val)
+{
+  if (!val) {
+    __builtin_abort();
+  }
+}
+
+static const char *buf;
+static int l, i;
+
+void _fputs(const char *str)  __attribute__((noinline));
+void _fputs(const char *str)
+{
+  buf = str;
+  i = 0;
+  l = __builtin_strlen(buf);
+}
+
+char _fgetc() __attribute__((noinline));
+char _fgetc()
+{
+  char val = buf[i];
+  i++;
+  if (i > l)
+    return -1;
+  else
+    return val;
+}
+
+static const char *string = "oops!\n";
+
+int main(void)
+{
+  int i;
+  int c;
+
+  _fputs(string);
+
+  for (i = 0; i < __builtin_strlen(string); i++) {
+    c = _fgetc();
+    check(c, string[i], c == string[i]);
+  }
+
+  return 0;
+}
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index e620eea..b10b1aa 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -391,6 +391,8 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
       elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
       scale = 1;
     }
+  else
+    elt = fold_convert (type, elt);
 
   if (scale == 1)
     {
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 8dc65881..fa993ab 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step,
       || contain_complex_addr_expr (expr))
     {
       aff_tree comb;
-      tree_to_aff_combination (expr, TREE_TYPE (base), &comb);
+      tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
       base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
     }
 
@@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop,
      overflows, as all the arithmetics will in the end be performed in UUTYPE
      anyway.  */
   common_type = determine_common_wider_type (&ubase, &cbase);
+  /* We don't need to compute in UUTYPE if this is the original candidate,
+     and candidate/use have the same (pointer) type.  */
+  if (ctype == utype && common_type == utype
+      && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype)
+      && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
+    uutype = utype;
 
   /* use = ubase - ratio * cbase + ratio * var.  */
   tree_to_aff_combination (ubase, common_type, aff);

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Richard Biener]

On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
> even worse, it always returns the former expression in aff_combination_tree, which
> is wrong if the original expression has the latter form.  The patch resolves the issue
> by always returning the latter form expression, i.e, always trying to generate folded
> expression.  Also as analyzed in comment, I think this change won't result in substantial
> code gen difference.
> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
> Well, I think the changed behavior is correct, but for case the original pointer candidate
> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

Hmm.  What is the desired goal?  To have all elts added have
comb->type as type?  Then
the type passed to add_elt_to_tree is redundant with comb->type.  It
looks like it
is always passed comb->type now.

ISTR from past work in this area that it was important for pointer
combinations to allow
both pointer and sizetype elts at least.

Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
elt is sizetype now, not of pointer type.  As said above, we are
trying to maintain
both pointer and sizetype elts with like:

  if (scale == 1)
    {
      if (!expr)
        {
          if (POINTER_TYPE_P (TREE_TYPE (elt)))
            return elt;
          else
            return fold_convert (type1, elt);
        }

where your earilier fold to type would result in not all cases handled the same
(depending whether scale was -1 for example).

Thus - shouldn't we simply drop the type argument (or rather the comb one?
that wide_int_ext_for_comb looks weird given we get a widest_int as input
and all the other wide_int_ext_for_comb calls around).

And unconditionally convert to type, simplifying the rest of the code?

Richard.


> 2017-03-27  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/80153
>         * tree-affine.c (add_elt_to_tree): Convert to type as required
>         by function's parameter.
>         * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>         (get_computation_aff): Use utype directly for original candidate.
>
> gcc/testsuite/ChangeLog
> 2017-03-27  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/80153
>         * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 3979 bytes --]

On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>> even worse, it always returns the former expression in aff_combination_tree, which
>> is wrong if the original expression has the latter form.  The patch resolves the issue
>> by always returning the latter form expression, i.e, always trying to generate folded
>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>> code gen difference.
>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>
Thanks for reviewing.
> Hmm.  What is the desired goal?  To have all elts added have
> comb->type as type?  Then
> the type passed to add_elt_to_tree is redundant with comb->type.  It
> looks like it
> is always passed comb->type now.
Yes, except pointer type comb->type, elts are converted to comb->type
with this patch.
The redundant type is removed in updated patch.

>
> ISTR from past work in this area that it was important for pointer
> combinations to allow
> both pointer and sizetype elts at least.
Yes, It's still important to allow different types for pointer and
offset in pointer type comb.
I missed a pointer type check condition in the patch, fixed in updated patch.
>
> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
> elt is sizetype now, not of pointer type.  As said above, we are
> trying to maintain
> both pointer and sizetype elts with like:
>
>   if (scale == 1)
>     {
>       if (!expr)
>         {
>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>             return elt;
>           else
>             return fold_convert (type1, elt);
>         }
>
> where your earilier fold to type would result in not all cases handled the same
> (depending whether scale was -1 for example).
IIUC, it doesn't matter.  For comb->type being pointer type, the
behavior remains the same.
For comb->type being unsigned T, this elt is converted to ptr_offtype,
rather than unsigned T,
this doesn't matter because ptr_offtype and unsigned T are equal to
each other, otherwise
tree_to_aff_combination shouldn't distribute it as a single elt.
Anyway, this is addressed in updated patch by checking pointer
comb->type additionally.
BTW, I think "scale==-1" case is a simple heuristic differentiating
pointer_base and offset.

>
> Thus - shouldn't we simply drop the type argument (or rather the comb one?
> that wide_int_ext_for_comb looks weird given we get a widest_int as input
> and all the other wide_int_ext_for_comb calls around).
>
> And unconditionally convert to type, simplifying the rest of the code?
As said, for pointer type comb, we need to keep current behavior; for
other cases,
unconditionally convert to comb->type is the goal.

Bootstrap and test on x86_64 and AArch64.  Is this version OK?

Thanks,
bin

2017-03-28  Bin Cheng  <bin.cheng@arm.com>

    PR tree-optimization/80153
    * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
    of parameter COMB.  Convert elt to type of COMB it COMB is not of
    pointer type.
    (aff_combination_to_tree): Update calls to add_elt_to_tree.
    * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
    (get_computation_aff): Use utype directly for original candidate.

gcc/testsuite/ChangeLog
2017-03-28  Bin Cheng  <bin.cheng@arm.com>

    PR tree-optimization/80153
    * gcc.c-torture/execute/pr80153.c: New.

[-- Attachment #2: pr80153-20170328.txt --]
[-- Type: text/plain, Size: 6897 bytes --]

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
new file mode 100644
index 0000000..3eed578
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/80153 */
+
+void check (int, int, int) __attribute__((noinline));
+void check (int c, int c2, int val)
+{
+  if (!val) {
+    __builtin_abort();
+  }
+}
+
+static const char *buf;
+static int l, i;
+
+void _fputs(const char *str)  __attribute__((noinline));
+void _fputs(const char *str)
+{
+  buf = str;
+  i = 0;
+  l = __builtin_strlen(buf);
+}
+
+char _fgetc() __attribute__((noinline));
+char _fgetc()
+{
+  char val = buf[i];
+  i++;
+  if (i > l)
+    return -1;
+  else
+    return val;
+}
+
+static const char *string = "oops!\n";
+
+int main(void)
+{
+  int i;
+  int c;
+
+  _fputs(string);
+
+  for (i = 0; i < __builtin_strlen(string); i++) {
+    c = _fgetc();
+    check(c, string[i], c == string[i]);
+  }
+
+  return 0;
+}
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index e620eea..a7f0b6a 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -370,27 +370,28 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
   aff_combination_elt (comb, type, expr);
 }
 
-/* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
+/* Creates EXPR + ELT * SCALE in COMB's type.  EXPR is taken from affine
    combination COMB.  */
 
 static tree
-add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
-		 aff_tree *comb ATTRIBUTE_UNUSED)
+add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in,
+		 aff_tree *comb)
 {
   enum tree_code code;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
 
   widest_int scale = wide_int_ext_for_comb (scale_in, comb);
 
   if (scale == -1
+      && POINTER_TYPE_P (comb->type)
       && POINTER_TYPE_P (TREE_TYPE (elt)))
     {
       elt = convert_to_ptrofftype (elt);
       elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
       scale = 1;
     }
+  else if (!POINTER_TYPE_P (comb->type))
+    elt = fold_convert (comb->type, elt);
 
   if (scale == 1)
     {
@@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 	  if (POINTER_TYPE_P (TREE_TYPE (elt)))
 	    return elt;
 	  else
-	    return fold_convert (type1, elt);
+	    return fold_convert (type, elt);
 	}
 
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
 	return fold_build_pointer_plus (expr, elt);
       if (POINTER_TYPE_P (TREE_TYPE (elt)))
 	return fold_build_pointer_plus (elt, expr);
-      return fold_build2 (PLUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
     }
 
   if (scale == -1)
     {
       if (!expr)
-	return fold_build1 (NEGATE_EXPR, type1,
-			    fold_convert (type1, elt));
+	return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
 
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
 	{
@@ -422,14 +421,12 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 	  elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
 	  return fold_build_pointer_plus (expr, elt);
 	}
-      return fold_build2 (MINUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
     }
 
-  elt = fold_convert (type1, elt);
+  elt = fold_convert (type, elt);
   if (!expr)
-    return fold_build2 (MULT_EXPR, type1, elt,
-			wide_int_to_tree (type1, scale));
+    return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
 
   if (wi::neg_p (scale))
     {
@@ -439,15 +436,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
   else
     code = PLUS_EXPR;
 
-  elt = fold_build2 (MULT_EXPR, type1, elt,
-		     wide_int_to_tree (type1, scale));
+  elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
   if (POINTER_TYPE_P (TREE_TYPE (expr)))
     {
       if (code == MINUS_EXPR)
-        elt = fold_build1 (NEGATE_EXPR, type1, elt);
+        elt = fold_build1 (NEGATE_EXPR, type, elt);
       return fold_build_pointer_plus (expr, elt);
     }
-  return fold_build2 (code, type1, expr, elt);
+  return fold_build2 (code, type, expr, elt);
 }
 
 /* Makes tree from the affine combination COMB.  */
@@ -455,22 +451,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 tree
 aff_combination_to_tree (aff_tree *comb)
 {
-  tree type = comb->type;
   tree expr = NULL_TREE;
   unsigned i;
   widest_int off, sgn;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
 
   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 
   for (i = 0; i < comb->n; i++)
-    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
-			    comb);
+    expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb);
 
   if (comb->rest)
-    expr = add_elt_to_tree (expr, type, comb->rest, 1, comb);
+    expr = add_elt_to_tree (expr, comb->rest, 1, comb);
 
   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
      unsigned.  */
@@ -484,8 +476,7 @@ aff_combination_to_tree (aff_tree *comb)
       off = comb->offset;
       sgn = 1;
     }
-  return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn,
-			  comb);
+  return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb);
 }
 
 /* Copies the tree elements of COMB to ensure that they are not shared.  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 8dc65881..fa993ab 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step,
       || contain_complex_addr_expr (expr))
     {
       aff_tree comb;
-      tree_to_aff_combination (expr, TREE_TYPE (base), &comb);
+      tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
       base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
     }
 
@@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop,
      overflows, as all the arithmetics will in the end be performed in UUTYPE
      anyway.  */
   common_type = determine_common_wider_type (&ubase, &cbase);
+  /* We don't need to compute in UUTYPE if this is the original candidate,
+     and candidate/use have the same (pointer) type.  */
+  if (ctype == utype && common_type == utype
+      && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype)
+      && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
+    uutype = utype;
 
   /* use = ubase - ratio * cbase + ratio * var.  */
   tree_to_aff_combination (ubase, common_type, aff);

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Richard Biener]

On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>> Hi,
>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>> even worse, it always returns the former expression in aff_combination_tree, which
>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>> by always returning the latter form expression, i.e, always trying to generate folded
>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>> code gen difference.
>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>
> Thanks for reviewing.
>> Hmm.  What is the desired goal?  To have all elts added have
>> comb->type as type?  Then
>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>> looks like it
>> is always passed comb->type now.
> Yes, except pointer type comb->type, elts are converted to comb->type
> with this patch.
> The redundant type is removed in updated patch.
>
>>
>> ISTR from past work in this area that it was important for pointer
>> combinations to allow
>> both pointer and sizetype elts at least.
> Yes, It's still important to allow different types for pointer and
> offset in pointer type comb.
> I missed a pointer type check condition in the patch, fixed in updated patch.
>>
>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>> elt is sizetype now, not of pointer type.  As said above, we are
>> trying to maintain
>> both pointer and sizetype elts with like:
>>
>>   if (scale == 1)
>>     {
>>       if (!expr)
>>         {
>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>             return elt;
>>           else
>>             return fold_convert (type1, elt);
>>         }
>>
>> where your earilier fold to type would result in not all cases handled the same
>> (depending whether scale was -1 for example).
> IIUC, it doesn't matter.  For comb->type being pointer type, the
> behavior remains the same.
> For comb->type being unsigned T, this elt is converted to ptr_offtype,
> rather than unsigned T,
> this doesn't matter because ptr_offtype and unsigned T are equal to
> each other, otherwise
> tree_to_aff_combination shouldn't distribute it as a single elt.
> Anyway, this is addressed in updated patch by checking pointer
> comb->type additionally.
> BTW, I think "scale==-1" case is a simple heuristic differentiating
> pointer_base and offset.
>
>>
>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>> and all the other wide_int_ext_for_comb calls around).
>>
>> And unconditionally convert to type, simplifying the rest of the code?
> As said, for pointer type comb, we need to keep current behavior; for
> other cases,
> unconditionally convert to comb->type is the goal.
>
> Bootstrap and test on x86_64 and AArch64.  Is this version OK?

@@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
const widest_int &scale_in,
          if (POINTER_TYPE_P (TREE_TYPE (elt)))
            return elt;
          else
-           return fold_convert (type1, elt);
+           return fold_convert (type, elt);
        }

the conversion should already have been done.  For non-pointer comb->type
it has been converted to type by your patch.  For pointer-type comb->type
it should be either pointer type or ptrofftype ('type') already as well.

That said, can we do sth like

@@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t

   widest_int scale = wide_int_ext_for_comb (scale_in, comb);

+  if (! POINTER_TYPE_P (comb->type))
+    elt = fold_convert (comb->type, elt);
+  else
+    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
+               || types_compatible_p (TREE_TYPE (elt), type1));
+
   if (scale == -1
       && POINTER_TYPE_P (TREE_TYPE (elt)))
     {

that is clearly do the conversion at the start in a way the state
of elt is more clear?

Richard.



> Thanks,
> bin
>
> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>
>     PR tree-optimization/80153
>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>     pointer type.
>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>     (get_computation_aff): Use utype directly for original candidate.
>
> gcc/testsuite/ChangeLog
> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>
>     PR tree-optimization/80153
>     * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 5824 bytes --]

On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>> Hi,
>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>> code gen difference.
>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>
>> Thanks for reviewing.
>>> Hmm.  What is the desired goal?  To have all elts added have
>>> comb->type as type?  Then
>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>> looks like it
>>> is always passed comb->type now.
>> Yes, except pointer type comb->type, elts are converted to comb->type
>> with this patch.
>> The redundant type is removed in updated patch.
>>
>>>
>>> ISTR from past work in this area that it was important for pointer
>>> combinations to allow
>>> both pointer and sizetype elts at least.
>> Yes, It's still important to allow different types for pointer and
>> offset in pointer type comb.
>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>
>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>> elt is sizetype now, not of pointer type.  As said above, we are
>>> trying to maintain
>>> both pointer and sizetype elts with like:
>>>
>>>   if (scale == 1)
>>>     {
>>>       if (!expr)
>>>         {
>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>             return elt;
>>>           else
>>>             return fold_convert (type1, elt);
>>>         }
>>>
>>> where your earilier fold to type would result in not all cases handled the same
>>> (depending whether scale was -1 for example).
>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>> behavior remains the same.
>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>> rather than unsigned T,
>> this doesn't matter because ptr_offtype and unsigned T are equal to
>> each other, otherwise
>> tree_to_aff_combination shouldn't distribute it as a single elt.
>> Anyway, this is addressed in updated patch by checking pointer
>> comb->type additionally.
>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>> pointer_base and offset.
>>
>>>
>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>> and all the other wide_int_ext_for_comb calls around).
>>>
>>> And unconditionally convert to type, simplifying the rest of the code?
>> As said, for pointer type comb, we need to keep current behavior; for
>> other cases,
>> unconditionally convert to comb->type is the goal.
>>
>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>
> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
> const widest_int &scale_in,
>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>             return elt;
>           else
> -           return fold_convert (type1, elt);
> +           return fold_convert (type, elt);
>         }
>
> the conversion should already have been done.  For non-pointer comb->type
> it has been converted to type by your patch.  For pointer-type comb->type
> it should be either pointer type or ptrofftype ('type') already as well.
>
> That said, can we do sth like
>
> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>
>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>
> +  if (! POINTER_TYPE_P (comb->type))
> +    elt = fold_convert (comb->type, elt);
> +  else
> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
> +               || types_compatible_p (TREE_TYPE (elt), type1));
Hmm, this assert can be broken since we do STRIP_NOPS converting to
aff_tree. It's not compatible for signed and unsigned integer types.
Also, with this patch, we can even support elt of short type in a
unsigned long comb, though this is useless.

> +
>    if (scale == -1
>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>      {
>
> that is clearly do the conversion at the start in a way the state
> of elt is more clear?
Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
after bootstrap/test?

Thanks,
bin
>
> Richard.
>
>
>
>> Thanks,
>> bin
>>
>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>     PR tree-optimization/80153
>>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>>     pointer type.
>>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>>     (get_computation_aff): Use utype directly for original candidate.
>>
>> gcc/testsuite/ChangeLog
>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>     PR tree-optimization/80153
>>     * gcc.c-torture/execute/pr80153.c: New.

[-- Attachment #2: pr80153-20170330.txt --]
[-- Type: text/plain, Size: 6837 bytes --]

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
new file mode 100644
index 0000000..3eed578
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/80153 */
+
+void check (int, int, int) __attribute__((noinline));
+void check (int c, int c2, int val)
+{
+  if (!val) {
+    __builtin_abort();
+  }
+}
+
+static const char *buf;
+static int l, i;
+
+void _fputs(const char *str)  __attribute__((noinline));
+void _fputs(const char *str)
+{
+  buf = str;
+  i = 0;
+  l = __builtin_strlen(buf);
+}
+
+char _fgetc() __attribute__((noinline));
+char _fgetc()
+{
+  char val = buf[i];
+  i++;
+  if (i > l)
+    return -1;
+  else
+    return val;
+}
+
+static const char *string = "oops!\n";
+
+int main(void)
+{
+  int i;
+  int c;
+
+  _fputs(string);
+
+  for (i = 0; i < __builtin_strlen(string); i++) {
+    c = _fgetc();
+    check(c, string[i], c == string[i]);
+  }
+
+  return 0;
+}
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index e620eea..3ec9263 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -370,20 +370,22 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
   aff_combination_elt (comb, type, expr);
 }
 
-/* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
+/* Creates EXPR + ELT * SCALE in COMB's type.  EXPR is taken from affine
    combination COMB.  */
 
 static tree
-add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
-		 aff_tree *comb ATTRIBUTE_UNUSED)
+add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in,
+		 aff_tree *comb)
 {
   enum tree_code code;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
 
   widest_int scale = wide_int_ext_for_comb (scale_in, comb);
 
+  /* Convert elt unconditionally if comb is not pointer type.  */
+  if (!POINTER_TYPE_P (comb->type))
+    elt = fold_convert (comb->type, elt);
+
   if (scale == -1
       && POINTER_TYPE_P (TREE_TYPE (elt)))
     {
@@ -394,27 +396,21 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 
   if (scale == 1)
     {
+      /* Elt is of correct type already.  */
       if (!expr)
-	{
-	  if (POINTER_TYPE_P (TREE_TYPE (elt)))
-	    return elt;
-	  else
-	    return fold_convert (type1, elt);
-	}
+	return elt;
 
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
 	return fold_build_pointer_plus (expr, elt);
       if (POINTER_TYPE_P (TREE_TYPE (elt)))
 	return fold_build_pointer_plus (elt, expr);
-      return fold_build2 (PLUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
     }
 
   if (scale == -1)
     {
       if (!expr)
-	return fold_build1 (NEGATE_EXPR, type1,
-			    fold_convert (type1, elt));
+	return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
 
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
 	{
@@ -422,14 +418,12 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 	  elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
 	  return fold_build_pointer_plus (expr, elt);
 	}
-      return fold_build2 (MINUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
     }
 
-  elt = fold_convert (type1, elt);
+  elt = fold_convert (type, elt);
   if (!expr)
-    return fold_build2 (MULT_EXPR, type1, elt,
-			wide_int_to_tree (type1, scale));
+    return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
 
   if (wi::neg_p (scale))
     {
@@ -439,15 +433,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
   else
     code = PLUS_EXPR;
 
-  elt = fold_build2 (MULT_EXPR, type1, elt,
-		     wide_int_to_tree (type1, scale));
+  elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
   if (POINTER_TYPE_P (TREE_TYPE (expr)))
     {
       if (code == MINUS_EXPR)
-        elt = fold_build1 (NEGATE_EXPR, type1, elt);
+        elt = fold_build1 (NEGATE_EXPR, type, elt);
       return fold_build_pointer_plus (expr, elt);
     }
-  return fold_build2 (code, type1, expr, elt);
+  return fold_build2 (code, type, expr, elt);
 }
 
 /* Makes tree from the affine combination COMB.  */
@@ -455,22 +448,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 tree
 aff_combination_to_tree (aff_tree *comb)
 {
-  tree type = comb->type;
   tree expr = NULL_TREE;
   unsigned i;
   widest_int off, sgn;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
 
   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 
   for (i = 0; i < comb->n; i++)
-    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
-			    comb);
+    expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb);
 
   if (comb->rest)
-    expr = add_elt_to_tree (expr, type, comb->rest, 1, comb);
+    expr = add_elt_to_tree (expr, comb->rest, 1, comb);
 
   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
      unsigned.  */
@@ -484,8 +473,7 @@ aff_combination_to_tree (aff_tree *comb)
       off = comb->offset;
       sgn = 1;
     }
-  return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn,
-			  comb);
+  return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb);
 }
 
 /* Copies the tree elements of COMB to ensure that they are not shared.  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 8dc65881..fa993ab 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step,
       || contain_complex_addr_expr (expr))
     {
       aff_tree comb;
-      tree_to_aff_combination (expr, TREE_TYPE (base), &comb);
+      tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
       base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
     }
 
@@ -3787,6 +3787,12 @@ get_computation_aff (struct loop *loop,
      overflows, as all the arithmetics will in the end be performed in UUTYPE
      anyway.  */
   common_type = determine_common_wider_type (&ubase, &cbase);
+  /* We don't need to compute in UUTYPE if this is the original candidate,
+     and candidate/use have the same (pointer) type.  */
+  if (ctype == utype && common_type == utype
+      && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype)
+      && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
+    uutype = utype;
 
   /* use = ubase - ratio * cbase + ratio * var.  */
   tree_to_aff_combination (ubase, common_type, aff);

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Richard Biener]

On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>> Hi,
>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>> code gen difference.
>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>
>>> Thanks for reviewing.
>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>> comb->type as type?  Then
>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>> looks like it
>>>> is always passed comb->type now.
>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>> with this patch.
>>> The redundant type is removed in updated patch.
>>>
>>>>
>>>> ISTR from past work in this area that it was important for pointer
>>>> combinations to allow
>>>> both pointer and sizetype elts at least.
>>> Yes, It's still important to allow different types for pointer and
>>> offset in pointer type comb.
>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>
>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>> trying to maintain
>>>> both pointer and sizetype elts with like:
>>>>
>>>>   if (scale == 1)
>>>>     {
>>>>       if (!expr)
>>>>         {
>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>             return elt;
>>>>           else
>>>>             return fold_convert (type1, elt);
>>>>         }
>>>>
>>>> where your earilier fold to type would result in not all cases handled the same
>>>> (depending whether scale was -1 for example).
>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>> behavior remains the same.
>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>> rather than unsigned T,
>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>> each other, otherwise
>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>> Anyway, this is addressed in updated patch by checking pointer
>>> comb->type additionally.
>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>> pointer_base and offset.
>>>
>>>>
>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>> and all the other wide_int_ext_for_comb calls around).
>>>>
>>>> And unconditionally convert to type, simplifying the rest of the code?
>>> As said, for pointer type comb, we need to keep current behavior; for
>>> other cases,
>>> unconditionally convert to comb->type is the goal.
>>>
>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>
>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>> const widest_int &scale_in,
>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>             return elt;
>>           else
>> -           return fold_convert (type1, elt);
>> +           return fold_convert (type, elt);
>>         }
>>
>> the conversion should already have been done.  For non-pointer comb->type
>> it has been converted to type by your patch.  For pointer-type comb->type
>> it should be either pointer type or ptrofftype ('type') already as well.
>>
>> That said, can we do sth like
>>
>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>
>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>
>> +  if (! POINTER_TYPE_P (comb->type))
>> +    elt = fold_convert (comb->type, elt);
>> +  else
>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>> +               || types_compatible_p (TREE_TYPE (elt), type1));
> Hmm, this assert can be broken since we do STRIP_NOPS converting to
> aff_tree. It's not compatible for signed and unsigned integer types.
> Also, with this patch, we can even support elt of short type in a
> unsigned long comb, though this is useless.
>
>> +
>>    if (scale == -1
>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>      {
>>
>> that is clearly do the conversion at the start in a way the state
>> of elt is more clear?
> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
> after bootstrap/test?

-      return fold_build2 (PLUS_EXPR, type1,
-                         expr, fold_convert (type1, elt));
+      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));

folding not needed(?)

-       return fold_build1 (NEGATE_EXPR, type1,
-                           fold_convert (type1, elt));
+       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));

likewise.

-      return fold_build2 (MINUS_EXPR, type1,
-                         expr, fold_convert (type1, elt));
+      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));

likewise.

Ok with removing those and re-testing.

Thanks,
Richard.

> Thanks,
> bin
>>
>> Richard.
>>
>>
>>
>>> Thanks,
>>> bin
>>>
>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>
>>>     PR tree-optimization/80153
>>>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>>>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>>>     pointer type.
>>>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>>>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>>>     (get_computation_aff): Use utype directly for original candidate.
>>>
>>> gcc/testsuite/ChangeLog
>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>
>>>     PR tree-optimization/80153
>>>     * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>> Hi,
>>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>>> code gen difference.
>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>
>>>> Thanks for reviewing.
>>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>>> comb->type as type?  Then
>>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>>> looks like it
>>>>> is always passed comb->type now.
>>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>>> with this patch.
>>>> The redundant type is removed in updated patch.
>>>>
>>>>>
>>>>> ISTR from past work in this area that it was important for pointer
>>>>> combinations to allow
>>>>> both pointer and sizetype elts at least.
>>>> Yes, It's still important to allow different types for pointer and
>>>> offset in pointer type comb.
>>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>>
>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>>> trying to maintain
>>>>> both pointer and sizetype elts with like:
>>>>>
>>>>>   if (scale == 1)
>>>>>     {
>>>>>       if (!expr)
>>>>>         {
>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>             return elt;
>>>>>           else
>>>>>             return fold_convert (type1, elt);
>>>>>         }
>>>>>
>>>>> where your earilier fold to type would result in not all cases handled the same
>>>>> (depending whether scale was -1 for example).
>>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>>> behavior remains the same.
>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>>> rather than unsigned T,
>>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>>> each other, otherwise
>>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>>> Anyway, this is addressed in updated patch by checking pointer
>>>> comb->type additionally.
>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>>> pointer_base and offset.
>>>>
>>>>>
>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>>> and all the other wide_int_ext_for_comb calls around).
>>>>>
>>>>> And unconditionally convert to type, simplifying the rest of the code?
>>>> As said, for pointer type comb, we need to keep current behavior; for
>>>> other cases,
>>>> unconditionally convert to comb->type is the goal.
>>>>
>>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>>
>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>>> const widest_int &scale_in,
>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>             return elt;
>>>           else
>>> -           return fold_convert (type1, elt);
>>> +           return fold_convert (type, elt);
>>>         }
>>>
>>> the conversion should already have been done.  For non-pointer comb->type
>>> it has been converted to type by your patch.  For pointer-type comb->type
>>> it should be either pointer type or ptrofftype ('type') already as well.
>>>
>>> That said, can we do sth like
>>>
>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>>
>>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>>
>>> +  if (! POINTER_TYPE_P (comb->type))
>>> +    elt = fold_convert (comb->type, elt);
>>> +  else
>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>> Hmm, this assert can be broken since we do STRIP_NOPS converting to
>> aff_tree. It's not compatible for signed and unsigned integer types.
>> Also, with this patch, we can even support elt of short type in a
>> unsigned long comb, though this is useless.
>>
>>> +
>>>    if (scale == -1
>>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>>      {
>>>
>>> that is clearly do the conversion at the start in a way the state
>>> of elt is more clear?
>> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
>> after bootstrap/test?
>
> -      return fold_build2 (PLUS_EXPR, type1,
> -                         expr, fold_convert (type1, elt));
> +      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
>
> folding not needed(?)
>
> -       return fold_build1 (NEGATE_EXPR, type1,
> -                           fold_convert (type1, elt));
> +       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
>
> likewise.
>
> -      return fold_build2 (MINUS_EXPR, type1,
> -                         expr, fold_convert (type1, elt));
> +      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
>
> likewise.
>
> Ok with removing those and re-testing.
Hmm, I thought twice about the simplification, there are cases not
properly handled:
>>> +  if (! POINTER_TYPE_P (comb->type))
>>> +    elt = fold_convert (comb->type, elt);
>>> +  else
>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
This is not enough, for pointer type comb, if elt is the offset part,
we could return signed integer type elt without folding.  Though this
shouldn't be an issue because it's always converted to ptr_offtype in
building pointer_plus, it's better not to create such expressions in
the first place.  Check condition for unconditionally converting elt
should be improved as:
>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>> +    elt = fold_convert (comb->type, elt);

With this change, folds can be removed as you suggested.  I will test
new patch for this.

Thanks,
bin
>
> Thanks,
> Richard.
>
>> Thanks,
>> bin
>>>
>>> Richard.
>>>
>>>
>>>
>>>> Thanks,
>>>> bin
>>>>
>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>     PR tree-optimization/80153
>>>>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>>>>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>>>>     pointer type.
>>>>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>>>>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>>>>     (get_computation_aff): Use utype directly for original candidate.
>>>>
>>>> gcc/testsuite/ChangeLog
>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>     PR tree-optimization/80153
>>>>     * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>>>> <richard.guenther@gmail.com> wrote:
>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>>> Hi,
>>>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>>>> code gen difference.
>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>>
>>>>> Thanks for reviewing.
>>>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>>>> comb->type as type?  Then
>>>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>>>> looks like it
>>>>>> is always passed comb->type now.
>>>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>>>> with this patch.
>>>>> The redundant type is removed in updated patch.
>>>>>
>>>>>>
>>>>>> ISTR from past work in this area that it was important for pointer
>>>>>> combinations to allow
>>>>>> both pointer and sizetype elts at least.
>>>>> Yes, It's still important to allow different types for pointer and
>>>>> offset in pointer type comb.
>>>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>>>
>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>>>> trying to maintain
>>>>>> both pointer and sizetype elts with like:
>>>>>>
>>>>>>   if (scale == 1)
>>>>>>     {
>>>>>>       if (!expr)
>>>>>>         {
>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>             return elt;
>>>>>>           else
>>>>>>             return fold_convert (type1, elt);
>>>>>>         }
>>>>>>
>>>>>> where your earilier fold to type would result in not all cases handled the same
>>>>>> (depending whether scale was -1 for example).
>>>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>>>> behavior remains the same.
>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>>>> rather than unsigned T,
>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>>>> each other, otherwise
>>>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>>>> Anyway, this is addressed in updated patch by checking pointer
>>>>> comb->type additionally.
>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>>>> pointer_base and offset.
>>>>>
>>>>>>
>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>>>> and all the other wide_int_ext_for_comb calls around).
>>>>>>
>>>>>> And unconditionally convert to type, simplifying the rest of the code?
>>>>> As said, for pointer type comb, we need to keep current behavior; for
>>>>> other cases,
>>>>> unconditionally convert to comb->type is the goal.
>>>>>
>>>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>>>
>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>>>> const widest_int &scale_in,
>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>             return elt;
>>>>           else
>>>> -           return fold_convert (type1, elt);
>>>> +           return fold_convert (type, elt);
>>>>         }
>>>>
>>>> the conversion should already have been done.  For non-pointer comb->type
>>>> it has been converted to type by your patch.  For pointer-type comb->type
>>>> it should be either pointer type or ptrofftype ('type') already as well.
>>>>
>>>> That said, can we do sth like
>>>>
>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>>>
>>>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>>>
>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>> +    elt = fold_convert (comb->type, elt);
>>>> +  else
>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to
>>> aff_tree. It's not compatible for signed and unsigned integer types.
>>> Also, with this patch, we can even support elt of short type in a
>>> unsigned long comb, though this is useless.
>>>
>>>> +
>>>>    if (scale == -1
>>>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>      {
>>>>
>>>> that is clearly do the conversion at the start in a way the state
>>>> of elt is more clear?
>>> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
>>> after bootstrap/test?
>>
>> -      return fold_build2 (PLUS_EXPR, type1,
>> -                         expr, fold_convert (type1, elt));
>> +      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
>>
>> folding not needed(?)
>>
>> -       return fold_build1 (NEGATE_EXPR, type1,
>> -                           fold_convert (type1, elt));
>> +       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
>>
>> likewise.
>>
>> -      return fold_build2 (MINUS_EXPR, type1,
>> -                         expr, fold_convert (type1, elt));
>> +      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
>>
>> likewise.
>>
>> Ok with removing those and re-testing.
> Hmm, I thought twice about the simplification, there are cases not
> properly handled:
>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>> +    elt = fold_convert (comb->type, elt);
>>>> +  else
>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
> This is not enough, for pointer type comb, if elt is the offset part,
> we could return signed integer type elt without folding.  Though this
> shouldn't be an issue because it's always converted to ptr_offtype in
> building pointer_plus, it's better not to create such expressions in
> the first place.  Check condition for unconditionally converting elt
> should be improved as:
>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>> +    elt = fold_convert (comb->type, elt);

Hmm, precisely as:
>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>> +    elt = fold_convert (type, elt);

>
> With this change, folds can be removed as you suggested.  I will test
> new patch for this.
>
> Thanks,
> bin
>>
>> Thanks,
>> Richard.
>>
>>> Thanks,
>>> bin
>>>>
>>>> Richard.
>>>>
>>>>
>>>>
>>>>> Thanks,
>>>>> bin
>>>>>
>>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>>
>>>>>     PR tree-optimization/80153
>>>>>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>>>>>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>>>>>     pointer type.
>>>>>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>>>>>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>>>>>     (get_computation_aff): Use utype directly for original candidate.
>>>>>
>>>>> gcc/testsuite/ChangeLog
>>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>>
>>>>>     PR tree-optimization/80153
>>>>>     * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Richard Biener]

On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>>>> Hi,
>>>>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>>>>> code gen difference.
>>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>>>
>>>>>> Thanks for reviewing.
>>>>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>>>>> comb->type as type?  Then
>>>>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>>>>> looks like it
>>>>>>> is always passed comb->type now.
>>>>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>>>>> with this patch.
>>>>>> The redundant type is removed in updated patch.
>>>>>>
>>>>>>>
>>>>>>> ISTR from past work in this area that it was important for pointer
>>>>>>> combinations to allow
>>>>>>> both pointer and sizetype elts at least.
>>>>>> Yes, It's still important to allow different types for pointer and
>>>>>> offset in pointer type comb.
>>>>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>>>>
>>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>>>>> trying to maintain
>>>>>>> both pointer and sizetype elts with like:
>>>>>>>
>>>>>>>   if (scale == 1)
>>>>>>>     {
>>>>>>>       if (!expr)
>>>>>>>         {
>>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>>             return elt;
>>>>>>>           else
>>>>>>>             return fold_convert (type1, elt);
>>>>>>>         }
>>>>>>>
>>>>>>> where your earilier fold to type would result in not all cases handled the same
>>>>>>> (depending whether scale was -1 for example).
>>>>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>>>>> behavior remains the same.
>>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>>>>> rather than unsigned T,
>>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>>>>> each other, otherwise
>>>>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>>>>> Anyway, this is addressed in updated patch by checking pointer
>>>>>> comb->type additionally.
>>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>>>>> pointer_base and offset.
>>>>>>
>>>>>>>
>>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>>>>> and all the other wide_int_ext_for_comb calls around).
>>>>>>>
>>>>>>> And unconditionally convert to type, simplifying the rest of the code?
>>>>>> As said, for pointer type comb, we need to keep current behavior; for
>>>>>> other cases,
>>>>>> unconditionally convert to comb->type is the goal.
>>>>>>
>>>>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>>>>
>>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>>>>> const widest_int &scale_in,
>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>             return elt;
>>>>>           else
>>>>> -           return fold_convert (type1, elt);
>>>>> +           return fold_convert (type, elt);
>>>>>         }
>>>>>
>>>>> the conversion should already have been done.  For non-pointer comb->type
>>>>> it has been converted to type by your patch.  For pointer-type comb->type
>>>>> it should be either pointer type or ptrofftype ('type') already as well.
>>>>>
>>>>> That said, can we do sth like
>>>>>
>>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>>>>
>>>>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>>>>
>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>> +    elt = fold_convert (comb->type, elt);
>>>>> +  else
>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to
>>>> aff_tree. It's not compatible for signed and unsigned integer types.
>>>> Also, with this patch, we can even support elt of short type in a
>>>> unsigned long comb, though this is useless.
>>>>
>>>>> +
>>>>>    if (scale == -1
>>>>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>      {
>>>>>
>>>>> that is clearly do the conversion at the start in a way the state
>>>>> of elt is more clear?
>>>> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
>>>> after bootstrap/test?
>>>
>>> -      return fold_build2 (PLUS_EXPR, type1,
>>> -                         expr, fold_convert (type1, elt));
>>> +      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
>>>
>>> folding not needed(?)
>>>
>>> -       return fold_build1 (NEGATE_EXPR, type1,
>>> -                           fold_convert (type1, elt));
>>> +       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
>>>
>>> likewise.
>>>
>>> -      return fold_build2 (MINUS_EXPR, type1,
>>> -                         expr, fold_convert (type1, elt));
>>> +      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
>>>
>>> likewise.
>>>
>>> Ok with removing those and re-testing.
>> Hmm, I thought twice about the simplification, there are cases not
>> properly handled:
>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>> +    elt = fold_convert (comb->type, elt);
>>>>> +  else
>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>> This is not enough, for pointer type comb, if elt is the offset part,
>> we could return signed integer type elt without folding.  Though this
>> shouldn't be an issue because it's always converted to ptr_offtype in
>> building pointer_plus, it's better not to create such expressions in
>> the first place.  Check condition for unconditionally converting elt
>> should be improved as:
>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>> +    elt = fold_convert (comb->type, elt);
>
> Hmm, precisely as:
>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>> +    elt = fold_convert (type, elt);

Yeah, that looks good to me.

>>
>> With this change, folds can be removed as you suggested.  I will test
>> new patch for this.
>>
>> Thanks,
>> bin
>>>
>>> Thanks,
>>> Richard.
>>>
>>>> Thanks,
>>>> bin
>>>>>
>>>>> Richard.
>>>>>
>>>>>
>>>>>
>>>>>> Thanks,
>>>>>> bin
>>>>>>
>>>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>>>
>>>>>>     PR tree-optimization/80153
>>>>>>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE.  Use type
>>>>>>     of parameter COMB.  Convert elt to type of COMB it COMB is not of
>>>>>>     pointer type.
>>>>>>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>>>>>>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>>>>>>     (get_computation_aff): Use utype directly for original candidate.
>>>>>>
>>>>>> gcc/testsuite/ChangeLog
>>>>>> 2017-03-28  Bin Cheng  <bin.cheng@arm.com>
>>>>>>
>>>>>>     PR tree-optimization/80153
>>>>>>     * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

On Thu, Mar 30, 2017 at 2:34 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
>>>>> <richard.guenther@gmail.com> wrote:
>>>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>>>>> Hi,
>>>>>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>>>>>> code gen difference.
>>>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>>>>
>>>>>>> Thanks for reviewing.
>>>>>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>>>>>> comb->type as type?  Then
>>>>>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>>>>>> looks like it
>>>>>>>> is always passed comb->type now.
>>>>>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>>>>>> with this patch.
>>>>>>> The redundant type is removed in updated patch.
>>>>>>>
>>>>>>>>
>>>>>>>> ISTR from past work in this area that it was important for pointer
>>>>>>>> combinations to allow
>>>>>>>> both pointer and sizetype elts at least.
>>>>>>> Yes, It's still important to allow different types for pointer and
>>>>>>> offset in pointer type comb.
>>>>>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>>>>>
>>>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>>>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>>>>>> trying to maintain
>>>>>>>> both pointer and sizetype elts with like:
>>>>>>>>
>>>>>>>>   if (scale == 1)
>>>>>>>>     {
>>>>>>>>       if (!expr)
>>>>>>>>         {
>>>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>>>             return elt;
>>>>>>>>           else
>>>>>>>>             return fold_convert (type1, elt);
>>>>>>>>         }
>>>>>>>>
>>>>>>>> where your earilier fold to type would result in not all cases handled the same
>>>>>>>> (depending whether scale was -1 for example).
>>>>>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>>>>>> behavior remains the same.
>>>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>>>>>> rather than unsigned T,
>>>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>>>>>> each other, otherwise
>>>>>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>>>>>> Anyway, this is addressed in updated patch by checking pointer
>>>>>>> comb->type additionally.
>>>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>>>>>> pointer_base and offset.
>>>>>>>
>>>>>>>>
>>>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>>>>>> and all the other wide_int_ext_for_comb calls around).
>>>>>>>>
>>>>>>>> And unconditionally convert to type, simplifying the rest of the code?
>>>>>>> As said, for pointer type comb, we need to keep current behavior; for
>>>>>>> other cases,
>>>>>>> unconditionally convert to comb->type is the goal.
>>>>>>>
>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>>>>>
>>>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>>>>>> const widest_int &scale_in,
>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>             return elt;
>>>>>>           else
>>>>>> -           return fold_convert (type1, elt);
>>>>>> +           return fold_convert (type, elt);
>>>>>>         }
>>>>>>
>>>>>> the conversion should already have been done.  For non-pointer comb->type
>>>>>> it has been converted to type by your patch.  For pointer-type comb->type
>>>>>> it should be either pointer type or ptrofftype ('type') already as well.
>>>>>>
>>>>>> That said, can we do sth like
>>>>>>
>>>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>>>>>
>>>>>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>>>>>
>>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>>> +    elt = fold_convert (comb->type, elt);
>>>>>> +  else
>>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to
>>>>> aff_tree. It's not compatible for signed and unsigned integer types.
>>>>> Also, with this patch, we can even support elt of short type in a
>>>>> unsigned long comb, though this is useless.
>>>>>
>>>>>> +
>>>>>>    if (scale == -1
>>>>>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>      {
>>>>>>
>>>>>> that is clearly do the conversion at the start in a way the state
>>>>>> of elt is more clear?
>>>>> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
>>>>> after bootstrap/test?
>>>>
>>>> -      return fold_build2 (PLUS_EXPR, type1,
>>>> -                         expr, fold_convert (type1, elt));
>>>> +      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
>>>>
>>>> folding not needed(?)
>>>>
>>>> -       return fold_build1 (NEGATE_EXPR, type1,
>>>> -                           fold_convert (type1, elt));
>>>> +       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
>>>>
>>>> likewise.
>>>>
>>>> -      return fold_build2 (MINUS_EXPR, type1,
>>>> -                         expr, fold_convert (type1, elt));
>>>> +      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
>>>>
>>>> likewise.
>>>>
>>>> Ok with removing those and re-testing.
>>> Hmm, I thought twice about the simplification, there are cases not
>>> properly handled:
>>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>>> +    elt = fold_convert (comb->type, elt);
>>>>>> +  else
>>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>> This is not enough, for pointer type comb, if elt is the offset part,
>>> we could return signed integer type elt without folding.  Though this
>>> shouldn't be an issue because it's always converted to ptr_offtype in
>>> building pointer_plus, it's better not to create such expressions in
>>> the first place.  Check condition for unconditionally converting elt
>>> should be improved as:
>>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>> +    elt = fold_convert (comb->type, elt);
>>
>> Hmm, precisely as:
>>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>> +    elt = fold_convert (type, elt);
>
> Yeah, that looks good to me.
>
Turned out it's more subtle than expected.  Here is the latest version
patch which I think makes aff_tree's type semantics more clear.
Detailed comment is added in tree-affine.h describing its semantics.

/* This aff_tree represents fully folded expression in a distributed way.
   For example, tree expression:
     (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4)
   can be represented as aff_tree like:
     {
       type = unsigned long
       offset = 0
       elts[0] = A * 1
       elts[1] = B * 4
       elts[2] = C * 4
       elts[3] = D * 8
     }
   Note aff_tree has (root) type which is type of the original expression,
   elements can have their own types which are different to aff_tree's.  In
   general, elements' type is type of folded sub-expression, and with NOP
   type conversion stripped.  For example, elts[0] has type of A, which is
   type of STRIP_NOPS ((sizetype) A).

   Given aff_tree represents folded form of the original tree expression,
   it lacks ability to track whether the original form is of folded form
   or non-folded form.  For example, both tree expressions:
     (unsigned)((int)A + (int)B)
     (unsigned)(int)A + (unsigned)(int)B
   have the same aff_tree repsentation.  This imposes restrictions on this
   facility, i.e, we need to be conservative and always generate the latter
   form when converting aff_tree back to tree expression.  This implies all
   elements need to be converted to aff_tree's type before converting.

   Always generating folded expr could lead to information loss because we
   can no longer know that (int)A + (int)B doesn't overflow.  As a result,
   we should avoid using aff_tree in code generation directly.  It should
   be used when we want to explore CSE opportunities by breaking most
   associations.  It can be then used in code generation if there will be
   benefit.

   It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree
   has pointer type accordingly.  Such aff_tree is special in two ways:
     1) It has a base element which is the original base pointer.  Other
elements belong to offset part of the original expression.  When
converting back to tree, other elements need to be converted to
ptr_offtype, rather than pointer type.
     2) In aff_tree computation, base element can be eliminated, it's the
user's responsibility to convert the rest aff_tree to ptr_offtype.
The rest aff_tree stands for offset part expression, no longer the
POINTER_PLUS_EXPR.  */

As an real example, use of aff_tree in add_iv_candidate_for_use breaks
above semantics.  It needs to convert aff_tree to ptr_offtype after
removing pointer element.  Here I simply choose not to use aff_tree
since it's unnecessary.

Bootstrap and test on x86_64 and AArch64.  Is this version OK?

Thanks,
bin
2017-04-04  Bin Cheng  <bin.cheng@arm.com>

    PR tree-optimization/80153
    * tree-affine.h (struct aff_tree): Add comment.
    * tree-affine.c (add_elt_to_tree): Remove parameter TYPE, and use
    parameter COMB's type instead.  Preserve elt's pointer type if it
    is the base pointer of a pointer type COMB.
    (aff_combination_to_tree): Update calls to add_elt_to_tree.
    * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
    (add_iv_candidate_for_use): Check and remove POINTER_PLUS_EXPR's
    base part directly, rather than through aff_tree.
    (get_computation_aff): Use utype directly for original candidate.

gcc/testsuite/ChangeLog
2017-04-04  Bin Cheng  <bin.cheng@arm.com>

    PR tree-optimization/80153
    * gcc.c-torture/execute/pr80153.c: New.

Re: [PATCH PR80153]Always generate folded type conversion in tree-affine

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 11915 bytes --]

And the patch..



On Wed, Apr 5, 2017 at 8:25 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Thu, Mar 30, 2017 at 2:34 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Thu, Mar 30, 2017 at 3:20 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Thu, Mar 30, 2017 at 2:18 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>> On Thu, Mar 30, 2017 at 1:44 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>>> On Thu, Mar 30, 2017 at 2:03 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>>> On Thu, Mar 30, 2017 at 11:37 AM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Wed, Mar 29, 2017 at 5:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>>>>> On Tue, Mar 28, 2017 at 1:34 PM, Richard Biener
>>>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>>>> On Tue, Mar 28, 2017 at 2:01 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>>>>>>> Hi,
>>>>>>>>>> This patch is to fix PR80153.  As analyzed in the PR, root cause is tree_affine lacks
>>>>>>>>>> ability differentiating (unsigned)(ptr + offset) and (unsigned)ptr + (unsigned)offset,
>>>>>>>>>> even worse, it always returns the former expression in aff_combination_tree, which
>>>>>>>>>> is wrong if the original expression has the latter form.  The patch resolves the issue
>>>>>>>>>> by always returning the latter form expression, i.e, always trying to generate folded
>>>>>>>>>> expression.  Also as analyzed in comment, I think this change won't result in substantial
>>>>>>>>>> code gen difference.
>>>>>>>>>> I also need to adjust get_computation_aff for test case gcc.dg/tree-ssa/reassoc-19.c.
>>>>>>>>>> Well, I think the changed behavior is correct, but for case the original pointer candidate
>>>>>>>>>> is chosen, it should be unnecessary to compute in uutype.  Also this adjustment only
>>>>>>>>>> generates (unsigned)(pointer + offset) which is generated by tree-affine.c.
>>>>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>>>>>>
>>>>>>>> Thanks for reviewing.
>>>>>>>>> Hmm.  What is the desired goal?  To have all elts added have
>>>>>>>>> comb->type as type?  Then
>>>>>>>>> the type passed to add_elt_to_tree is redundant with comb->type.  It
>>>>>>>>> looks like it
>>>>>>>>> is always passed comb->type now.
>>>>>>>> Yes, except pointer type comb->type, elts are converted to comb->type
>>>>>>>> with this patch.
>>>>>>>> The redundant type is removed in updated patch.
>>>>>>>>
>>>>>>>>>
>>>>>>>>> ISTR from past work in this area that it was important for pointer
>>>>>>>>> combinations to allow
>>>>>>>>> both pointer and sizetype elts at least.
>>>>>>>> Yes, It's still important to allow different types for pointer and
>>>>>>>> offset in pointer type comb.
>>>>>>>> I missed a pointer type check condition in the patch, fixed in updated patch.
>>>>>>>>>
>>>>>>>>> Your change is incomplete I think, for the scale == -1 and POINTER_TYPE_P case
>>>>>>>>> elt is sizetype now, not of pointer type.  As said above, we are
>>>>>>>>> trying to maintain
>>>>>>>>> both pointer and sizetype elts with like:
>>>>>>>>>
>>>>>>>>>   if (scale == 1)
>>>>>>>>>     {
>>>>>>>>>       if (!expr)
>>>>>>>>>         {
>>>>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>>>>             return elt;
>>>>>>>>>           else
>>>>>>>>>             return fold_convert (type1, elt);
>>>>>>>>>         }
>>>>>>>>>
>>>>>>>>> where your earilier fold to type would result in not all cases handled the same
>>>>>>>>> (depending whether scale was -1 for example).
>>>>>>>> IIUC, it doesn't matter.  For comb->type being pointer type, the
>>>>>>>> behavior remains the same.
>>>>>>>> For comb->type being unsigned T, this elt is converted to ptr_offtype,
>>>>>>>> rather than unsigned T,
>>>>>>>> this doesn't matter because ptr_offtype and unsigned T are equal to
>>>>>>>> each other, otherwise
>>>>>>>> tree_to_aff_combination shouldn't distribute it as a single elt.
>>>>>>>> Anyway, this is addressed in updated patch by checking pointer
>>>>>>>> comb->type additionally.
>>>>>>>> BTW, I think "scale==-1" case is a simple heuristic differentiating
>>>>>>>> pointer_base and offset.
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Thus - shouldn't we simply drop the type argument (or rather the comb one?
>>>>>>>>> that wide_int_ext_for_comb looks weird given we get a widest_int as input
>>>>>>>>> and all the other wide_int_ext_for_comb calls around).
>>>>>>>>>
>>>>>>>>> And unconditionally convert to type, simplifying the rest of the code?
>>>>>>>> As said, for pointer type comb, we need to keep current behavior; for
>>>>>>>> other cases,
>>>>>>>> unconditionally convert to comb->type is the goal.
>>>>>>>>
>>>>>>>> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>>>>>>>
>>>>>>> @@ -399,22 +400,20 @@ add_elt_to_tree (tree expr, tree type, tree elt,
>>>>>>> const widest_int &scale_in,
>>>>>>>           if (POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>>             return elt;
>>>>>>>           else
>>>>>>> -           return fold_convert (type1, elt);
>>>>>>> +           return fold_convert (type, elt);
>>>>>>>         }
>>>>>>>
>>>>>>> the conversion should already have been done.  For non-pointer comb->type
>>>>>>> it has been converted to type by your patch.  For pointer-type comb->type
>>>>>>> it should be either pointer type or ptrofftype ('type') already as well.
>>>>>>>
>>>>>>> That said, can we do sth like
>>>>>>>
>>>>>>> @@ -384,6 +395,12 @@ add_elt_to_tree (tree expr, tree type, t
>>>>>>>
>>>>>>>    widest_int scale = wide_int_ext_for_comb (scale_in, comb);
>>>>>>>
>>>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>>>> +    elt = fold_convert (comb->type, elt);
>>>>>>> +  else
>>>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>>>>> Hmm, this assert can be broken since we do STRIP_NOPS converting to
>>>>>> aff_tree. It's not compatible for signed and unsigned integer types.
>>>>>> Also, with this patch, we can even support elt of short type in a
>>>>>> unsigned long comb, though this is useless.
>>>>>>
>>>>>>> +
>>>>>>>    if (scale == -1
>>>>>>>        && POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>>      {
>>>>>>>
>>>>>>> that is clearly do the conversion at the start in a way the state
>>>>>>> of elt is more clear?
>>>>>> Yes, thanks.  V3 patch attached (with gcc_assert removed).  Is it ok
>>>>>> after bootstrap/test?
>>>>>
>>>>> -      return fold_build2 (PLUS_EXPR, type1,
>>>>> -                         expr, fold_convert (type1, elt));
>>>>> +      return fold_build2 (PLUS_EXPR, type, expr, fold_convert (type, elt));
>>>>>
>>>>> folding not needed(?)
>>>>>
>>>>> -       return fold_build1 (NEGATE_EXPR, type1,
>>>>> -                           fold_convert (type1, elt));
>>>>> +       return fold_build1 (NEGATE_EXPR, type, fold_convert (type, elt));
>>>>>
>>>>> likewise.
>>>>>
>>>>> -      return fold_build2 (MINUS_EXPR, type1,
>>>>> -                         expr, fold_convert (type1, elt));
>>>>> +      return fold_build2 (MINUS_EXPR, type, expr, fold_convert (type, elt));
>>>>>
>>>>> likewise.
>>>>>
>>>>> Ok with removing those and re-testing.
>>>> Hmm, I thought twice about the simplification, there are cases not
>>>> properly handled:
>>>>>>> +  if (! POINTER_TYPE_P (comb->type))
>>>>>>> +    elt = fold_convert (comb->type, elt);
>>>>>>> +  else
>>>>>>> +    gcc_assert (POINTER_TYPE_P (TREE_TYPE (elt))
>>>>>>> +               || types_compatible_p (TREE_TYPE (elt), type1));
>>>> This is not enough, for pointer type comb, if elt is the offset part,
>>>> we could return signed integer type elt without folding.  Though this
>>>> shouldn't be an issue because it's always converted to ptr_offtype in
>>>> building pointer_plus, it's better not to create such expressions in
>>>> the first place.  Check condition for unconditionally converting elt
>>>> should be improved as:
>>>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>> +    elt = fold_convert (comb->type, elt);
>>>
>>> Hmm, precisely as:
>>>>>>> +  if (! POINTER_TYPE_P (comb->type) || !POINTER_TYPE_P (TREE_TYPE (elt)))
>>>>>>> +    elt = fold_convert (type, elt);
>>
>> Yeah, that looks good to me.
>>
> Turned out it's more subtle than expected.  Here is the latest version
> patch which I think makes aff_tree's type semantics more clear.
> Detailed comment is added in tree-affine.h describing its semantics.
>
> /* This aff_tree represents fully folded expression in a distributed way.
>    For example, tree expression:
>      (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4)
>    can be represented as aff_tree like:
>      {
>        type = unsigned long
>        offset = 0
>        elts[0] = A * 1
>        elts[1] = B * 4
>        elts[2] = C * 4
>        elts[3] = D * 8
>      }
>    Note aff_tree has (root) type which is type of the original expression,
>    elements can have their own types which are different to aff_tree's.  In
>    general, elements' type is type of folded sub-expression, and with NOP
>    type conversion stripped.  For example, elts[0] has type of A, which is
>    type of STRIP_NOPS ((sizetype) A).
>
>    Given aff_tree represents folded form of the original tree expression,
>    it lacks ability to track whether the original form is of folded form
>    or non-folded form.  For example, both tree expressions:
>      (unsigned)((int)A + (int)B)
>      (unsigned)(int)A + (unsigned)(int)B
>    have the same aff_tree repsentation.  This imposes restrictions on this
>    facility, i.e, we need to be conservative and always generate the latter
>    form when converting aff_tree back to tree expression.  This implies all
>    elements need to be converted to aff_tree's type before converting.
>
>    Always generating folded expr could lead to information loss because we
>    can no longer know that (int)A + (int)B doesn't overflow.  As a result,
>    we should avoid using aff_tree in code generation directly.  It should
>    be used when we want to explore CSE opportunities by breaking most
>    associations.  It can be then used in code generation if there will be
>    benefit.
>
>    It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree
>    has pointer type accordingly.  Such aff_tree is special in two ways:
>      1) It has a base element which is the original base pointer.  Other
> elements belong to offset part of the original expression.  When
> converting back to tree, other elements need to be converted to
> ptr_offtype, rather than pointer type.
>      2) In aff_tree computation, base element can be eliminated, it's the
> user's responsibility to convert the rest aff_tree to ptr_offtype.
> The rest aff_tree stands for offset part expression, no longer the
> POINTER_PLUS_EXPR.  */
>
> As an real example, use of aff_tree in add_iv_candidate_for_use breaks
> above semantics.  It needs to convert aff_tree to ptr_offtype after
> removing pointer element.  Here I simply choose not to use aff_tree
> since it's unnecessary.
>
> Bootstrap and test on x86_64 and AArch64.  Is this version OK?
>
> Thanks,
> bin
> 2017-04-04  Bin Cheng  <bin.cheng@arm.com>
>
>     PR tree-optimization/80153
>     * tree-affine.h (struct aff_tree): Add comment.
>     * tree-affine.c (add_elt_to_tree): Remove parameter TYPE, and use
>     parameter COMB's type instead.  Preserve elt's pointer type if it
>     is the base pointer of a pointer type COMB.
>     (aff_combination_to_tree): Update calls to add_elt_to_tree.
>     * tree-ssa-loop-ivopts.c (alloc_iv): Pass in consistent types.
>     (add_iv_candidate_for_use): Check and remove POINTER_PLUS_EXPR's
>     base part directly, rather than through aff_tree.
>     (get_computation_aff): Use utype directly for original candidate.
>
> gcc/testsuite/ChangeLog
> 2017-04-04  Bin Cheng  <bin.cheng@arm.com>
>
>     PR tree-optimization/80153
>     * gcc.c-torture/execute/pr80153.c: New.

[-- Attachment #2: pr80153-20170404.txt --]
[-- Type: text/plain, Size: 11405 bytes --]

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr80153.c b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
new file mode 100644
index 0000000..3eed578
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr80153.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/80153 */
+
+void check (int, int, int) __attribute__((noinline));
+void check (int c, int c2, int val)
+{
+  if (!val) {
+    __builtin_abort();
+  }
+}
+
+static const char *buf;
+static int l, i;
+
+void _fputs(const char *str)  __attribute__((noinline));
+void _fputs(const char *str)
+{
+  buf = str;
+  i = 0;
+  l = __builtin_strlen(buf);
+}
+
+char _fgetc() __attribute__((noinline));
+char _fgetc()
+{
+  char val = buf[i];
+  i++;
+  if (i > l)
+    return -1;
+  else
+    return val;
+}
+
+static const char *string = "oops!\n";
+
+int main(void)
+{
+  int i;
+  int c;
+
+  _fputs(string);
+
+  for (i = 0; i < __builtin_strlen(string); i++) {
+    c = _fgetc();
+    check(c, string[i], c == string[i]);
+  }
+
+  return 0;
+}
diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c
index e620eea..83c2c6b 100644
--- a/gcc/tree-affine.c
+++ b/gcc/tree-affine.c
@@ -370,66 +370,54 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
   aff_combination_elt (comb, type, expr);
 }
 
-/* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
+/* Creates EXPR + ELT * SCALE in COMB's type.  EXPR is taken from affine
    combination COMB.  */
 
 static tree
-add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
-		 aff_tree *comb ATTRIBUTE_UNUSED)
+add_elt_to_tree (tree expr, tree elt, const widest_int &scale_in,
+		 aff_tree *comb)
 {
   enum tree_code code;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
-
+  /* Result type for this elt.  */
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
   widest_int scale = wide_int_ext_for_comb (scale_in, comb);
 
-  if (scale == -1
-      && POINTER_TYPE_P (TREE_TYPE (elt)))
-    {
-      elt = convert_to_ptrofftype (elt);
-      elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
-      scale = 1;
-    }
+  /* Preserve elt's pointer type only if below conditions are satisfied:
+       1) the result expression is of pointer type;
+       2) scale is 1;
+       3) expr is not of pointer type.
+     For all other cases, force it to result type.  */
+  if (scale != 1
+      || !POINTER_TYPE_P (comb->type)
+      || !POINTER_TYPE_P (TREE_TYPE (elt))
+      || (expr != NULL_TREE && POINTER_TYPE_P (TREE_TYPE (expr))))
+    elt = fold_convert (type, elt);
 
   if (scale == 1)
     {
       if (!expr)
-	{
-	  if (POINTER_TYPE_P (TREE_TYPE (elt)))
-	    return elt;
-	  else
-	    return fold_convert (type1, elt);
-	}
-
+	return elt;
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
 	return fold_build_pointer_plus (expr, elt);
       if (POINTER_TYPE_P (TREE_TYPE (elt)))
 	return fold_build_pointer_plus (elt, expr);
-      return fold_build2 (PLUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+
+      return fold_build2 (PLUS_EXPR, type, expr, elt);
     }
 
   if (scale == -1)
     {
       if (!expr)
-	return fold_build1 (NEGATE_EXPR, type1,
-			    fold_convert (type1, elt));
-
+	return fold_build1 (NEGATE_EXPR, type, elt);
       if (POINTER_TYPE_P (TREE_TYPE (expr)))
-	{
-	  elt = convert_to_ptrofftype (elt);
-	  elt = fold_build1 (NEGATE_EXPR, TREE_TYPE (elt), elt);
-	  return fold_build_pointer_plus (expr, elt);
-	}
-      return fold_build2 (MINUS_EXPR, type1,
-			  expr, fold_convert (type1, elt));
+	return fold_build_pointer_plus (expr,
+					fold_build1 (NEGATE_EXPR, type, elt));
+
+      return fold_build2 (MINUS_EXPR, type, expr, elt);
     }
 
-  elt = fold_convert (type1, elt);
   if (!expr)
-    return fold_build2 (MULT_EXPR, type1, elt,
-			wide_int_to_tree (type1, scale));
+    return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
 
   if (wi::neg_p (scale))
     {
@@ -439,15 +427,14 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
   else
     code = PLUS_EXPR;
 
-  elt = fold_build2 (MULT_EXPR, type1, elt,
-		     wide_int_to_tree (type1, scale));
+  elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
   if (POINTER_TYPE_P (TREE_TYPE (expr)))
     {
       if (code == MINUS_EXPR)
-        elt = fold_build1 (NEGATE_EXPR, type1, elt);
+        elt = fold_build1 (NEGATE_EXPR, type, elt);
       return fold_build_pointer_plus (expr, elt);
     }
-  return fold_build2 (code, type1, expr, elt);
+  return fold_build2 (code, type, expr, elt);
 }
 
 /* Makes tree from the affine combination COMB.  */
@@ -455,22 +442,18 @@ add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in,
 tree
 aff_combination_to_tree (aff_tree *comb)
 {
-  tree type = comb->type;
   tree expr = NULL_TREE;
   unsigned i;
   widest_int off, sgn;
-  tree type1 = type;
-  if (POINTER_TYPE_P (type))
-    type1 = sizetype;
+  tree type = POINTER_TYPE_P (comb->type) ? sizetype : comb->type;
 
   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
 
   for (i = 0; i < comb->n; i++)
-    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
-			    comb);
+    expr = add_elt_to_tree (expr, comb->elts[i].val, comb->elts[i].coef, comb);
 
   if (comb->rest)
-    expr = add_elt_to_tree (expr, type, comb->rest, 1, comb);
+    expr = add_elt_to_tree (expr, comb->rest, 1, comb);
 
   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
      unsigned.  */
@@ -484,8 +467,7 @@ aff_combination_to_tree (aff_tree *comb)
       off = comb->offset;
       sgn = 1;
     }
-  return add_elt_to_tree (expr, type, wide_int_to_tree (type1, off), sgn,
-			  comb);
+  return add_elt_to_tree (expr, wide_int_to_tree (type, off), sgn, comb);
 }
 
 /* Copies the tree elements of COMB to ensure that they are not shared.  */
diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h
index b8eb8cc..5b84aef 100644
--- a/gcc/tree-affine.h
+++ b/gcc/tree-affine.h
@@ -37,6 +37,52 @@ struct aff_comb_elt
   widest_int coef;
 };
 
+/* This aff_tree represents fully folded expression in a distributed way.
+   For example, tree expression:
+     (unsigned long)(A + ((sizetype)((integer)B + C) + (sizetype)D * 2) * 4)
+   can be represented as aff_tree like:
+     {
+       type = unsigned long
+       offset = 0
+       elts[0] = A * 1
+       elts[1] = B * 4
+       elts[2] = C * 4
+       elts[3] = D * 8
+     }
+   Note aff_tree has (root) type which is type of the original expression,
+   elements can have their own types which are different to aff_tree's.  In
+   general, elements' type is type of folded sub-expression, and with NOP
+   type conversion stripped.  For example, elts[0] has type of A, which is
+   type of STRIP_NOPS ((sizetype) A).
+
+   Given aff_tree represents folded form of the original tree expression,
+   it lacks ability to track whether the original form is of folded form
+   or non-folded form.  For example, both tree expressions:
+     (unsigned)((int)A + (int)B)
+     (unsigned)(int)A + (unsigned)(int)B
+   have the same aff_tree repsentation.  This imposes restrictions on this
+   facility, i.e, we need to be conservative and always generate the latter
+   form when converting aff_tree back to tree expression.  This implies all
+   elements need to be converted to aff_tree's type before converting.
+
+   Always generating folded expr could lead to information loss because we
+   can no longer know that (int)A + (int)B doesn't overflow.  As a result,
+   we should avoid using aff_tree in code generation directly.  It should
+   be used when we want to explore CSE opportunities by breaking most
+   associations.  It can be then used in code generation if there will be
+   benefit.
+
+   It's possible to represent POINTER_PLUS_EXPR in aff_tree, the aff_tree
+   has pointer type accordingly.  Such aff_tree is special in two ways:
+     1) It has a base element which is the original base pointer.  Other
+	elements belong to offset part of the original expression.  When
+	converting back to tree, other elements need to be converted to
+	ptr_offtype, rather than pointer type.
+     2) In aff_tree computation, base element can be eliminated, it's the
+	user's responsibility to convert the rest aff_tree to ptr_offtype.
+	The rest aff_tree stands for offset part expression, no longer the
+	POINTER_PLUS_EXPR.  */
+
 struct aff_tree
 {
   /* Type of the result of the combination.  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 8dc65881..666f885 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1171,7 +1171,7 @@ alloc_iv (struct ivopts_data *data, tree base, tree step,
       || contain_complex_addr_expr (expr))
     {
       aff_tree comb;
-      tree_to_aff_combination (expr, TREE_TYPE (base), &comb);
+      tree_to_aff_combination (expr, TREE_TYPE (expr), &comb);
       base = fold_convert (TREE_TYPE (base), aff_combination_to_tree (&comb));
     }
 
@@ -3335,41 +3335,20 @@ add_iv_candidate_for_use (struct ivopts_data *data, struct iv_use *use)
     }
 
   /* Record common candidate with base_object removed in base.  */
-  if (iv->base_object != NULL)
+  base = iv->base;
+  STRIP_NOPS (base);
+  if (iv->base_object != NULL && TREE_CODE (base) == POINTER_PLUS_EXPR)
     {
-      unsigned i;
-      aff_tree aff_base;
-      tree step, base_object = iv->base_object;
+      tree step = iv->step;
 
-      base = iv->base;
-      step = iv->step;
-      STRIP_NOPS (base);
       STRIP_NOPS (step);
-      STRIP_NOPS (base_object);
-      tree_to_aff_combination (base, TREE_TYPE (base), &aff_base);
-      for (i = 0; i < aff_base.n; i++)
-	{
-	  if (aff_base.elts[i].coef != 1)
-	    continue;
-
-	  if (operand_equal_p (aff_base.elts[i].val, base_object, 0))
-	    break;
-	}
-      if (i < aff_base.n)
-	{
-	  aff_combination_remove_elt (&aff_base, i);
-	  base = aff_combination_to_tree (&aff_base);
-	  basetype = TREE_TYPE (base);
-	  if (POINTER_TYPE_P (basetype))
-	    basetype = sizetype;
-
-	  step = fold_convert (basetype, step);
-	  record_common_cand (data, base, step, use);
-	  /* Also record common candidate with offset stripped.  */
-	  base = strip_offset (base, &offset);
-	  if (offset)
-	    record_common_cand (data, base, step, use);
-	}
+      base = TREE_OPERAND (base, 1);
+      step = fold_convert (sizetype, step);
+      record_common_cand (data, base, step, use);
+      /* Also record common candidate with offset stripped.  */
+      base = strip_offset (base, &offset);
+      if (offset)
+	record_common_cand (data, base, step, use);
     }
 
   /* At last, add auto-incremental candidates.  Make such variables
@@ -3787,6 +3766,12 @@ get_computation_aff (struct loop *loop,
      overflows, as all the arithmetics will in the end be performed in UUTYPE
      anyway.  */
   common_type = determine_common_wider_type (&ubase, &cbase);
+  /* We don't need to compute in UUTYPE if this is the original candidate,
+     and candidate/use have the same (pointer) type.  */
+  if (ctype == utype && common_type == utype
+      && POINTER_TYPE_P (utype) && TYPE_UNSIGNED (utype)
+      && cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
+    uutype = utype;
 
   /* use = ubase - ratio * cbase + ratio * var.  */
   tree_to_aff_combination (ubase, common_type, aff);