Fix PR/46200 -- ivopt bug in test condition cost computation

Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

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

Hi, please review the patch attached. Regression and some performance
test is under going.

Thanks,

David


2010-10-29  Xinliang David Li  <davidxl@google.com>

	PR target/46200
	* tree-ssa-loop-ivopts.c (get_computation_cost_at):
	Adjust cbase if the use stmt is after iv update.

[-- Attachment #2: ivopt_46200.p --]
[-- Type: text/x-pascal, Size: 1702 bytes --]

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 166032)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -4027,6 +4027,8 @@ get_computation_cost_at (struct ivopts_d
   STRIP_NOPS (cbase);
   ctype = TREE_TYPE (cbase);
 
+  stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
+
   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
      or ratio == 1, it is better to handle this like
 
@@ -4045,8 +4047,24 @@ get_computation_cost_at (struct ivopts_d
     }
   else if (ratio == 1)
     {
+      tree real_cbase = cbase;
+
+      /* Check to see if any adjustment is needed.  */
+      if (cstepi == 0 && stmt_is_after_inc)
+        {
+          aff_tree real_cbase_aff;
+          aff_tree cstep_aff;
+
+          tree_to_aff_combination (cbase, TREE_TYPE (real_cbase),
+                                   &real_cbase_aff);
+          tree_to_aff_combination (cstep, TREE_TYPE (cstep), &cstep_aff);
+
+          aff_combination_add (&real_cbase_aff, &cstep_aff);
+          real_cbase = aff_combination_to_tree (&real_cbase_aff);
+        }
+
       cost = difference_cost (data,
-			      ubase, cbase,
+			      ubase, real_cbase,
 			      &symbol_present, &var_present, &offset,
 			      depends_on);
       cost.cost /= avg_loop_niter (data->current_loop);
@@ -4088,7 +4106,6 @@ get_computation_cost_at (struct ivopts_d
 
   /* If we are after the increment, the value of the candidate is higher by
      one iteration.  */
-  stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
   if (stmt_is_after_inc)
     offset -= ratio * cstepi;
 

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Zdenek Dvorak]

Hi,

> Hi, please review the patch attached. Regression and some performance
> test is under going.

it would be more consistent to either avoid using aff_combination functions
in get_computation_cost_at completely, or rewrite it to use aff_combination
instead of the current difference_cost/... functions (however, the latter
would probably lead to somewhat slower compilation time).  The patch should
also include a testcase for the problem.

Thanks for working on this,

Zdenek

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

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

On Sat, Oct 30, 2010 at 12:30 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> Hi, please review the patch attached. Regression and some performance
>> test is under going.
>
> it would be more consistent to either avoid using aff_combination functions
> in get_computation_cost_at completely, or rewrite it to use aff_combination
> instead of the current difference_cost/... functions (however, the latter
> would probably lead to somewhat slower compilation time).  The patch should
> also include a testcase for the problem.

I agree -- the code for cost computation should match (or probably
share with) code in the rewrite functions -- however that is a much
larger task than is needed for this PR.

I added a test case (marked with x86 target as ivopt are very target
sensitive). Regression test and minimal perf testing went ok.

Ok to checkin?

Thanks,

David

(test case change log)

010-10-31  Xinliang David Li  <davidxl@google.com>

        PR target/46200
        * g++.dg/tree-ssa/ivopts-2.C: New test.






>
> Thanks for working on this,
>
> Zdenek
>

[-- Attachment #2: ivopt_46200_2.p --]
[-- Type: application/octet-stream, Size: 2294 bytes --]

Index: gcc/testsuite/g++.dg/tree-ssa/ivopts-2.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/ivopts-2.C	(revision 0)
+++ gcc/testsuite/g++.dg/tree-ssa/ivopts-2.C	(revision 0)
@@ -0,0 +1,11 @@
+/* { dg-do compile { target { i?86-*-* x86_64-*-*  } } } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+void test (int *b, int *e, int stride)
+  {
+    for (int *p = b; p != e; p += stride)
+      *p = 1;
+  }
+
+/* { dg-final { scan-tree-dump-times "PHI <p" 1 "ivopts"} } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 166032)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -4027,6 +4027,8 @@ get_computation_cost_at (struct ivopts_d
   STRIP_NOPS (cbase);
   ctype = TREE_TYPE (cbase);
 
+  stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
+
   /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
      or ratio == 1, it is better to handle this like
 
@@ -4045,8 +4047,24 @@ get_computation_cost_at (struct ivopts_d
     }
   else if (ratio == 1)
     {
+      tree real_cbase = cbase;
+
+      /* Check to see if any adjustment is needed.  */
+      if (cstepi == 0 && stmt_is_after_inc)
+        {
+          aff_tree real_cbase_aff;
+          aff_tree cstep_aff;
+
+          tree_to_aff_combination (cbase, TREE_TYPE (real_cbase),
+                                   &real_cbase_aff);
+          tree_to_aff_combination (cstep, TREE_TYPE (cstep), &cstep_aff);
+
+          aff_combination_add (&real_cbase_aff, &cstep_aff);
+          real_cbase = aff_combination_to_tree (&real_cbase_aff);
+        }
+
       cost = difference_cost (data,
-			      ubase, cbase,
+			      ubase, real_cbase,
 			      &symbol_present, &var_present, &offset,
 			      depends_on);
       cost.cost /= avg_loop_niter (data->current_loop);
@@ -4088,7 +4106,6 @@ get_computation_cost_at (struct ivopts_d
 
   /* If we are after the increment, the value of the candidate is higher by
      one iteration.  */
-  stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
   if (stmt_is_after_inc)
     offset -= ratio * cstepi;
 

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

Can I get an explicit OK :) ?

Thanks,

David

On Sun, Oct 31, 2010 at 11:59 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Sat, Oct 30, 2010 at 12:30 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
>> Hi,
>>
>>> Hi, please review the patch attached. Regression and some performance
>>> test is under going.
>>
>> it would be more consistent to either avoid using aff_combination functions
>> in get_computation_cost_at completely, or rewrite it to use aff_combination
>> instead of the current difference_cost/... functions (however, the latter
>> would probably lead to somewhat slower compilation time).  The patch should
>> also include a testcase for the problem.
>
> I agree -- the code for cost computation should match (or probably
> share with) code in the rewrite functions -- however that is a much
> larger task than is needed for this PR.
>
> I added a test case (marked with x86 target as ivopt are very target
> sensitive). Regression test and minimal perf testing went ok.
>
> Ok to checkin?
>
> Thanks,
>
> David
>
> (test case change log)
>
> 010-10-31  Xinliang David Li  <davidxl@google.com>
>
>        PR target/46200
>        * g++.dg/tree-ssa/ivopts-2.C: New test.
>
>
>
>
>
>
>>
>> Thanks for working on this,
>>
>> Zdenek
>>
>

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Zdenek Dvorak]

Hi,

> >> Hi, please review the patch attached. Regression and some performance
> >> test is under going.
> >
> > it would be more consistent to either avoid using aff_combination functions
> > in get_computation_cost_at completely, or rewrite it to use aff_combination
> > instead of the current difference_cost/... functions (however, the latter
> > would probably lead to somewhat slower compilation time).  The patch should
> > also include a testcase for the problem.
> 
> I agree -- the code for cost computation should match (or probably
> share with) code in the rewrite functions -- however that is a much
> larger task than is needed for this PR.
> 
> I added a test case (marked with x86 target as ivopt are very target
> sensitive). Regression test and minimal perf testing went ok.

OK,

Zdenek

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

Submitted as r166280.

Thanks,

David

On Wed, Nov 3, 2010 at 3:27 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> >> Hi, please review the patch attached. Regression and some performance
>> >> test is under going.
>> >
>> > it would be more consistent to either avoid using aff_combination functions
>> > in get_computation_cost_at completely, or rewrite it to use aff_combination
>> > instead of the current difference_cost/... functions (however, the latter
>> > would probably lead to somewhat slower compilation time).  The patch should
>> > also include a testcase for the problem.
>>
>> I agree -- the code for cost computation should match (or probably
>> share with) code in the rewrite functions -- however that is a much
>> larger task than is needed for this PR.
>>
>> I added a test case (marked with x86 target as ivopt are very target
>> sensitive). Regression test and minimal perf testing went ok.
>
> OK,
>
> Zdenek
>
>
>

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[H.J. Lu]

On Fri, Oct 29, 2010 at 1:28 PM, Xinliang David Li <davidxl@google.com> wrote:
> Hi, please review the patch attached. Regression and some performance
> test is under going.
>
> Thanks,
>
> David
>
>
> 2010-10-29  Xinliang David Li  <davidxl@google.com>
>
>        PR target/46200
>        * tree-ssa-loop-ivopts.c (get_computation_cost_at):
>        Adjust cbase if the use stmt is after iv update.
>

This patch may have caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316

You need to build a 32bit gcc to reproduce it. I am using

CC="gcc -m32" CXX="g++ -m32"  configure  i686-linux

on Fedora 16/Intel64 to build 32bit GCC.


-- 
H.J.

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[H.J. Lu]

On Fri, Nov 5, 2010 at 1:32 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Oct 29, 2010 at 1:28 PM, Xinliang David Li <davidxl@google.com> wrote:
>> Hi, please review the patch attached. Regression and some performance
>> test is under going.
>>
>> Thanks,
>>
>> David
>>
>>
>> 2010-10-29  Xinliang David Li  <davidxl@google.com>
>>
>>        PR target/46200
>>        * tree-ssa-loop-ivopts.c (get_computation_cost_at):
>>        Adjust cbase if the use stmt is after iv update.
>>
>
> This patch may have caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316
>

I was wrong. Ignore it.

-- 
H.J.

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[H.J. Lu]

On Fri, Nov 5, 2010 at 1:40 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Nov 5, 2010 at 1:32 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
>> On Fri, Oct 29, 2010 at 1:28 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> Hi, please review the patch attached. Regression and some performance
>>> test is under going.
>>>
>>> Thanks,
>>>
>>> David
>>>
>>>
>>> 2010-10-29  Xinliang David Li  <davidxl@google.com>
>>>
>>>        PR target/46200
>>>        * tree-ssa-loop-ivopts.c (get_computation_cost_at):
>>>        Adjust cbase if the use stmt is after iv update.
>>>
>>
>> This patch may have caused:
>>
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316
>>
>
> I was wrong. Ignore it.

Ooops. I was right. This is the cause/


-- 
H.J.

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

Sorry for the late reply -- reproduced. It is likely some bug
triggered by this change. I will take a look.

David

On Fri, Nov 5, 2010 at 1:32 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Oct 29, 2010 at 1:28 PM, Xinliang David Li <davidxl@google.com> wrote:
>> Hi, please review the patch attached. Regression and some performance
>> test is under going.
>>
>> Thanks,
>>
>> David
>>
>>
>> 2010-10-29  Xinliang David Li  <davidxl@google.com>
>>
>>        PR target/46200
>>        * tree-ssa-loop-ivopts.c (get_computation_cost_at):
>>        Adjust cbase if the use stmt is after iv update.
>>
>
> This patch may have caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316
>
> You need to build a 32bit gcc to reproduce it. I am using
>
> CC="gcc -m32" CXX="g++ -m32"  configure  i686-linux
>
> on Fedora 16/Intel64 to build 32bit GCC.
>
>
> --
> H.J.
>

Re: Fix PR/46200 -- ivopt bug in test condition cost computation

[Xinliang David Li]

I have no idea why my patch would have affected it, but this seems to
be a problem in double_int overflow in tree-vrp. I will send out a
patch shortly.

David

On Fri, Nov 5, 2010 at 1:32 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Fri, Oct 29, 2010 at 1:28 PM, Xinliang David Li <davidxl@google.com> wrote:
>> Hi, please review the patch attached. Regression and some performance
>> test is under going.
>>
>> Thanks,
>>
>> David
>>
>>
>> 2010-10-29  Xinliang David Li  <davidxl@google.com>
>>
>>        PR target/46200
>>        * tree-ssa-loop-ivopts.c (get_computation_cost_at):
>>        Adjust cbase if the use stmt is after iv update.
>>
>
> This patch may have caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46316
>
> You need to build a 32bit gcc to reproduce it. I am using
>
> CC="gcc -m32" CXX="g++ -m32"  configure  i686-linux
>
> on Fedora 16/Intel64 to build 32bit GCC.
>
>
> --
> H.J.
>