[Bug rtl-optimization/34503] New: Issues with constant/copy propagation implementation in gcse.c

[Bug rtl-optimization/34503] New: Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

This is a bug report about quality of implementation issues with the
implementation of constant and copy propagation for RTL, which lives in gcse.c.
 There is a companion bug 33828 for issues with code hoisting.


-- 
           Summary: Issues with constant/copy propagation implementation in
                    gcse.c
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, compile-time-hog
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: steven at gcc dot gnu dot org


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #1 from steven at gcc dot gnu dot org  2007-12-17 08:20 -------
Local const/copy propagation uses cselib, which is too heavy-weight for
something this simple.  The reason for using cselib is that, at the time, we
also tried to do local CSE with cselib.  But this never worked and we ended up
with cselib for just recording constants and copies.  This could be done much
more efficiently with a simple mapping of registers to constants and copies.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-12-17 08:20:21
               date|                            |
            Summary|Issues with constant/copy   |Issues with constant/copy
                   |propagation implementation  |propagation implementation
                   |in gcse.c                   |in gcse.c


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2007-12-17 08:22 -------
When the issue of comment #0 is resolved, local const/copy propagation can make
use of implicit sets.  This would result in more propagations, because the
global cprop pass can pick up the locally propagated implicit sets.


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #3 from steven at gcc dot gnu dot org  2007-12-17 08:30 -------
The global pass uses inefficient local dataflow properties.  Because there is a
local cprop pass before the global one, some constants/copies do not have to be
recorded.  This results in a smaller set of expressions to compute AVAIL for. 
Some experiments I did, showed that the set can be reduced by more than an
order of magnitude for large functions (for example try the idea on
c-common.c).

A register R in defined a load-immediate instruction (i.e. R<-const) in basic
block B should not be recorded if the register is not in LIVE_OUT(B)After local
cprop, the constant is propagated as far as possible within B, and the
definition of R does not reach any uses outside B.  Thus, not recording the
register value cannot result in missed optimizations.

Likewise, if R1 is defined in a copy instruction R1<-R2 in basic block B, and
R1 is not in LIVE_OUT(B), and R2 is also not in LIVE_OUT(B), then recording the
copy cannot result in missed optimizations, because R2 will have been
propagated locally as far as possible already.


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #4 from steven at gcc dot gnu dot org  2007-12-17 08:38 -------
The global cprop pass prefers constants over copies.  Thus, when a copy is
found but a REG_EQUAL note for a constant is found on the same instruction,
only the constant is recorded.  This results in missed copy-propagation
opportunities.  A simple example probably shows best what I mean:

a = ...
if (...)
{
  a = 5;
  b = a; (REG_EQUAL 5}
}
else
{
  b = a;
}
c = b;

GCC will record "b = 5" on one arm of the if-then-else, and "b = a" on the
other.  Because each expression kills the other, "b = a" is lost and GCC would
fail to propagate "a" to give "c = a;".

[ The above example may seem trivial and non-realistic -- but with CSE
disabled, pre tree-ssa compilers actually do fail to optimize this! ]

To fix this, constants and copies have to be tracked simultaneously.


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #5 from steven at gcc dot gnu dot org  2007-12-17 08:41 -------
find_avail_set() uses a list search to find an available set.  If it is called
multiple times for the same register, quadratic behavior results.  This is part
of the issue for bug 19097.  One fix would be to compute bitmaps of expressions
per set register, and then AND in the available expressions on entry of a basic
block.  At most one bit will be set (or at most two bits if constants and
copies are tracked separately).


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #6 from steven at gcc dot gnu dot org  2007-12-17 08:42 -------
I am working on a new implementation of CPROP for GCC 4.4, which tries to solve
the abovementioned issues. The new implementation is also using the DF scan
information instead of compute_sets() and CUIDs.


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

------- Comment #7 from steven at gcc dot gnu dot org  2008-05-24 14:31 -------
I have found a test case for the issue mentioned in comment #4. And it comes
from gcc itself:

static int *free_phinodes[10 - 2]; /* was 'tree' */
static unsigned long free_phinode_count;
void
init_phinodes (void)
{
  int i;
  for (i = 0; i < 10 - 2; i++)
    free_phinodes[i] = ((void *)0);
  free_phinode_count = 0
}

When compiling this on powerpc-unknown-elf with r135815 and with the options
"-O2 -fdump-rtl-gcse1-slim", I get the following RTL at the end of the GCSE
pass:

   37 NOTE_INSN_BASIC_BLOCK
   36 NOTE_INSN_FUNCTION_BEG
   39 r164:SI=high(`*.LANCHOR0')
   40 r166:SI=r164:SI+low(`*.LANCHOR0')
      REG_DEAD: r164:SI
      REG_EQUAL: `*.LANCHOR0'
   75 r153:SI=r166:SI
      REG_EQUAL: `*.LANCHOR0'
   73 r165:SI=r166:SI+0x20
      REG_DEAD: r167:SI
      REG_EQUAL: const(`*.LANCHOR0'+0x20)
L46:
   42 NOTE_INSN_BASIC_BLOCK
   43 r156:SI=0x0
   44 [r153:SI]=r156:SI
      REG_EQUAL: 0x0
   45 r153:SI=r153:SI+0x4
   71 r157:SI=r166:SI
      REG_EQUAL: `*.LANCHOR0'
   50 r160:CC=cmp(r153:SI,r165:SI)
      REG_EQUAL: cmp(r153:SI,const(`*.LANCHOR0'+0x20))
   51 pc={(r160:CC!=0x0)?L46:pc}
      REG_DEAD: r160:CC
      REG_BR_PROB: 0x222e
   52 NOTE_INSN_BASIC_BLOCK
   56 [r157:SI+0x20]=r156:SI
      REG_DEAD: r157:SI
      REG_DEAD: r156:SI
      REG_EQUAL: 0x0

This is the dump *after* CPROP2, so the post-PRE-GCSE const/copy pass has run. 
Note the REG_EQUAL note on insn 71: "r157:SI=r166:SI {REG_EQUAL:
`*.LANCHOR0'}". This is a reg-reg copy insn, but CPROP2 does not record the
copy.  Instead it records that r157 is equal to the REG_EQUAL note value.  The
result is that CPROP2 fails to copy propagate r166 into insn 56 (where r157
reaches and dies, so the copy propagation would eliminate r157).


-- 


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu dot org]

-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thomas.preudhomme at arm dot com

--- Comment #8 from Steven Bosscher <steven at gcc dot gnu.org> ---
Patch for comment #4 is proposed by Thomas Preud'homme with minor changes:

https://gcc.gnu.org/ml/gcc-patches/2015-03/msg01048.html
https://gcc.gnu.org/ml/gcc-patches/2015-03/msg01170.html

[Bug rtl-optimization/34503] Issues with constant/copy propagation implementation in gcse.c

[thopre01 at gcc dot gnu.org]

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

--- Comment #9 from Thomas Preud'homme <thopre01 at gcc dot gnu.org> ---
Author: thopre01
Date: Fri Apr 24 04:49:34 2015
New Revision: 222398

URL: https://gcc.gnu.org/viewcvs?rev=222398&root=gcc&view=rev
Log:
2015-04-24  Thomas Preud'homme  <thomas.preudhomme@arm.com>
            Steven Bosscher <steven@gcc.gnu.org>

    gcc/
    PR rtl-optimization/34503
    * cprop.c (cprop_reg_p): New.
    (hash_scan_set): Use above function to check if register can be
    propagated.
    (find_avail_set): Return up to two sets, one whose source is a
    register and one whose source is a constant.  Sets are returned in an
    array passed as parameter rather than as a return value.
    (cprop_insn): Use a do while loop rather than a goto.  Try each of the
    sets returned by find_avail_set, starting with the one whose source is
    a constant. Use cprop_reg_p to check if register can be propagated.
    (do_local_cprop): Use cprop_reg_p to check if register can be
    propagated.
    (implicit_set_cond_p): Likewise.

    gcc/testsuite/
    PR rtl-optimization/34503
    * gcc.target/arm/pr64616.c: New file.

Added:
    trunk/gcc/testsuite/gcc.target/arm/pr64616.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cprop.c
    trunk/gcc/testsuite/ChangeLog