[Bug tree-optimization/23286] missed fully redundant expression

["rguenth at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org>]

------- Comment #26 from rguenth at gcc dot gnu dot org  2010-01-17 12:34 -------
Created an attachment (id=19634)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19634&action=view)
updated patch

I updated the patch to apply to current trunk.

I also notice that on the testcase for PR21485 comment #36:

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-pre" } */

long
NumSift (long *array, int b, unsigned long k)
{
  if (b)
    if (array[k] < array[k + 1L])
      ++k;
  return array[k];
}

/* There should be two loads left.  */

/* { dg-final { scan-tree-dump-times "= \\\*" 2 "pre" } } */
/* { dg-final { cleanup-tree-dump "pre" } } */


we properly hoist array[k] before if (b) but still insert on the else edge
of that branch for eliminating a partial redundancy (and elimination doesn't
remove that again because the value-numbers of the inserted expressions are
not equal).

This is because while we put hoisted expressions into AVAIL_OUT of the
block we inserted to we do not propagate this to its successors so
PRE insertion does not find leaders for it.

In this case, starting from

<bb 2>:
  if (b_2(D) != 0)
    goto <bb 3>;
  else
    goto <bb 6>;

<bb 6>:
  goto <bb 5>;

<bb 3>:
  D.1955_4 = k_3(D) * 4;
  D.1956_6 = array_5(D) + D.1955_4;
  D.1957_7 = *D.1956_6;
  k_8 = k_3(D) + 1;
  D.1959_9 = k_8 * 4;
  D.1960_10 = array_5(D) + D.1959_9;
  D.1961_11 = *D.1960_10;
  if (D.1957_7 < D.1961_11)
    goto <bb 4>;
  else
    goto <bb 7>;

<bb 7>:
  goto <bb 5>;

<bb 4>:

<bb 5>:
  # k_1 = PHI <k_3(D)(6), k_3(D)(7), k_8(4)>
  D.1955_13 = k_1 * 4;
  D.1956_14 = array_5(D) + D.1955_13;
  D.1964_15 = *D.1956_14;
  return D.1964_15;

we hoist into block 2 and then PRE-insert for block 5, in pred 6 the
expressions are not yet available.  In reality
they are available but they didn't go through NEW set processing yet.

I wonder if we have to extend NEW set processing to either cover
immediate dominators of dominators or succs with single preds we
hoisted to (no idea if either would confuse PRE though).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #16803|0                           |1
        is obsolete|                            |


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