[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[xinliangli at gmail dot com]

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

--- Comment #5 from davidxl <xinliangli at gmail dot com> ---
Alternative approach -- introduce a special forward propagation before or after
the ivopt to get rid of the redundant iv. This propagation needs to propagate
through header phi.

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[amker at gcc dot gnu.org]

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

--- Comment #6 from amker at gcc dot gnu.org ---
Author: amker
Date: Tue Dec 10 06:31:41 2013
New Revision: 205848

URL: http://gcc.gnu.org/viewcvs?rev=205848&root=gcc&view=rev
Log:

    PR tree-optimization/41488
    * tree-ssa-loop-ivopts.c (add_old_iv_candidates): Don't add cand
    for PEELED_CHREC kind IV.
    * tree-scalar-evolution.c: Include necessary header files.
    (peeled_chrec_map, simplify_peeled_chrec): New.
    (analyze_evolution_in_loop): New static variable.
    Call simplify_peeled_chrec.
    (scev_initialize): Initialize peeled_chrec_map.
    (scev_reset, scev_finalize): Reset and release peeled_chrec_map.

    PR tree-optimization/41488
    * gcc.dg/tree-ssa/scev-7.c: New test.
    * gcc.dg/pr41488.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/pr41488.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/scev-7.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[amker at gcc dot gnu.org]

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

--- Comment #7 from amker at gcc dot gnu.org ---
Author: amker
Date: Wed Dec 11 00:58:35 2013
New Revision: 205880

URL: http://gcc.gnu.org/viewcvs?rev=205880&root=gcc&view=rev
Log:

    Reverted:
    2013-12-10  Bin Cheng  <bin.cheng@arm.com>
    PR tree-optimization/41488
    * tree-ssa-loop-ivopts.c (add_old_iv_candidates): Don't add cand
    for PEELED_CHREC kind IV.
    * tree-scalar-evolution.c: Include necessary header files.
    (peeled_chrec_map, simplify_peeled_chrec): New.
    (analyze_evolution_in_loop): New static variable.
    Call simplify_peeled_chrec.
    (scev_initialize): Initialize peeled_chrec_map.
    (scev_reset, scev_finalize): Reset and release peeled_chrec_map.

    Reverted:
    2013-12-10  Bin Cheng  <bin.cheng@arm.com>
    PR tree-optimization/41488
    * gcc.dg/tree-ssa/scev-7.c: New test.
    * gcc.dg/pr41488.c: New test.


Removed:
    trunk/gcc/testsuite/gcc.dg/pr41488.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/scev-7.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[amker at gcc dot gnu.org]

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

--- Comment #8 from amker at gcc dot gnu.org ---
Author: amker
Date: Fri Dec 13 11:36:22 2013
New Revision: 205959

URL: http://gcc.gnu.org/viewcvs?rev=205959&root=gcc&view=rev
Log:

    PR tree-optimization/58296
    PR tree-optimization/41488
    * tree-scalar-evolution.c: Include necessary header files.
    (simplify_peeled_chrec): New function.
    (analyze_evolution_in_loop): New static variable.
    Call simplify_peeled_chrec.
    * tree-ssa-loop-ivopts.c (mark_bivs): Don't mark peeled IV as biv.
    (add_old_iv_candidates): Don't add candidate for peeled IV.
    * tree-affine.h (aff_combination_zero_p): New function.

    PR tree-optimization/58296
    PR tree-optimization/41488
    * gcc.dg/tree-ssa/scev-7.c: New test.
    * gcc.dg/pr41488.c: New test.
    * g++.dg/pr59445.C: New test.


Added:
    trunk/gcc/testsuite/g++.dg/pr59445.C
    trunk/gcc/testsuite/gcc.dg/pr41488.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/scev-7.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-affine.h
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[ktkachov at gcc dot gnu.org]

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

ktkachov at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ktkachov at gcc dot gnu.org

--- Comment #9 from ktkachov at gcc dot gnu.org ---
Hi Bin,

I'm seeing tree-ssa/scev-7.c failing on arm

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |law at redhat dot com
         Resolution|---                         |FIXED

--- Comment #10 from Jeffrey A. Law <law at redhat dot com> ---
ktkachov,

It seems to be working fine for me with my arm-eabi cross compiler.  Perhaps
you could provide some more details:

make check-gcc RUNTESTFLAGS="tree-ssa.exp=scev-7.c"
[ ... ]

In the gcc.sum file I've got:

Running /home/gcc/GIT/gcc/gcc/testsuite/gcc.dg/tree-ssa/tree-ssa.exp ...
PASS: gcc.dg/tree-ssa/scev-7.c (test for excess errors)
PASS: gcc.dg/tree-ssa/scev-7.c scan-tree-dump-times sccp "Simplify PEELED_CHREC
into POLYNOMIAL_CHREC" 1

AFAICT, this issue has been resolved.

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[ktkachov at gcc dot gnu.org]

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

--- Comment #11 from ktkachov at gcc dot gnu.org ---
(In reply to Jeffrey A. Law from comment #10)
> ktkachov,
> 
> It seems to be working fine for me with my arm-eabi cross compiler.  Perhaps
> you could provide some more details:
> 
> make check-gcc RUNTESTFLAGS="tree-ssa.exp=scev-7.c"
> [ ... ]
> 
> In the gcc.sum file I've got:
> 
> Running /home/gcc/GIT/gcc/gcc/testsuite/gcc.dg/tree-ssa/tree-ssa.exp ...
> PASS: gcc.dg/tree-ssa/scev-7.c (test for excess errors)
> PASS: gcc.dg/tree-ssa/scev-7.c scan-tree-dump-times sccp "Simplify
> PEELED_CHREC into POLYNOMIAL_CHREC" 1
> 
> AFAICT, this issue has been resolved.

You're right, seems I had an inconsistent build tree state. It passes for me
now as well with a clean build. Sorry for the noise.

[Bug tree-optimization/41488] New: IVOpts cannot coalesce multiple induction variables

[rahul at icerasemi dot com]

Using GCC 4.4.1 release version and compiling the following test with

gcc -O2 -fdump-tree-all

struct struct_t {
  int* data;
};

void testAutoIncStruct (struct struct_t* sp, int start, int end) {
    int i;
    for (i = 0; i+start < end; i++)
      {
        sp->data[i+start] = 0;
      }
}

IVOpts dump shows induction variables (start and ivtmp.32) cannot be coalesced

testAutoIncStruct (struct struct_t * sp, int start, int end) {
  unsigned int D.1283;
  unsigned int D.1284;
  int D.1282;
  unsigned int ivtmp.32;
  int * pretmp.17;
  int i;
  int * D.1245;
  unsigned int D.1244;
  unsigned int D.1243;

<bb 2>:
  if (start_3(D) < end_5(D))
    goto <bb 3>;
  else
    goto <bb 6>;

<bb 3>:
  pretmp.17_22 = sp_6(D)->data;
  D.1282_23 = start_3(D) + 1;
  ivtmp.32_25 = (unsigned int) D.1282_23;
  D.1283_27 = (unsigned int) end_5(D);
  D.1284_28 = D.1283_27 + 1;

<bb 4>:
  # start_20 = PHI <start_4(5), start_3(D)(3)>
  # ivtmp.32_7 = PHI <ivtmp.32_24(5), ivtmp.32_25(3)>
  D.1243_9 = (unsigned int) start_20;
  D.1244_10 = D.1243_9 * 4;
  D.1245_11 = pretmp.17_22 + D.1244_10;
  *D.1245_11 = 0;
  start_26 = (int) ivtmp.32_7;
  start_4 = start_26;
  ivtmp.32_24 = ivtmp.32_7 + 1;
  if (ivtmp.32_24 != D.1284_28)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  goto <bb 4>;

<bb 6>:
  return;

}

The problem arises from expression "i + start" being identified as a common
expression between the header and the latch. This seems to creates an extra
induction variable and a PHI in the latch. If we disable tree FRE and tree copy
propagation with

gcc -O2 -fno-tree-fre -fno-tree-copy-prop

We get

<bb 3>:
  pretmp.17_23 = sp_6(D)->data;
  D.1287_27 = (unsigned int) end_5(D);
  D.1288_28 = (unsigned int) start_3(D);
  D.1289_29 = D.1287_27 - D.1288_28;
  D.1290_30 = (int) D.1289_29;

<bb 4>:
  # i_20 = PHI <i_12(5), 0(3)>
  D.1241_7 = pretmp.17_23;
  D.1284_26 = (unsigned int) start_3(D);
  D.1285_25 = (unsigned int) i_20;
  D.1286_24 = D.1284_26 + D.1285_25;
  MEM[base: pretmp.17_23, index: D.1286_24, step: 4] = 0;
  i_12 = i_20 + 1;
  if (i_12 != D.1290_30)
    goto <bb 5>;
  else
    goto <bb 6>;

The induction variable and the memory reference is now correctly identified.


-- 
           Summary: IVOpts cannot coalesce multiple induction variables
           Product: gcc
           Version: 4.4.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rahul at icerasemi dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[rahul at icerasemi dot com]

------- Comment #1 from rahul at icerasemi dot com  2009-09-28 12:45 -------
See http://gcc.gnu.org/ml/gcc/2009-09/msg00432.html for some followup.


-- 


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

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-09-28 15:30 -------
Confirmed.  Another way is to move loop header copying before FRE.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2009-09-28 15:30:54
               date|                            |


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

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-09-30 13:17 -------
The issue here is that loop header copying creates a new induction variable
by moving the use before the definition of D.2708_4 = start_3(D) + i_12.

So it just does what we teach PRE not to do ...


-- 


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

[Bug tree-optimization/41488] IVOpts cannot coalesce multiple induction variables

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-11-06 10:04 -------
*** Bug 41954 has been marked as a duplicate of this bug. ***


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinliangli at gmail dot com


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