Bug 38926

Confirmed.  PRE doesn't find a leader for a NAME (!?) when inserting {nop_expr,g_2.7_47}.

Subject: Re:  [4.4 Regression] ice in 
	find_or_generate_expression, at tree-ssa-pre.c:2769

names should be self-leaders.
Sounds like a set bitmap messup somewhere or an equality function gone
bad or something.
i'll take a look

On Wed, Jan 21, 2009 at 5:13 AM, rguenth at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #1 from rguenth at gcc dot gnu dot org  2009-01-21 10:13 -------
> Confirmed.  PRE doesn't find a leader for a NAME (!?) when inserting
> {nop_expr,g_2.7_47}.
>
>
> --
>
> rguenth at gcc dot gnu dot org changed:
>
>           What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                 CC|                            |dberlin at gcc dot gnu dot
>                   |                            |org
>             Status|UNCONFIRMED                 |NEW
>          Component|c                           |tree-optimization
>     Ever Confirmed|0                           |1
>  GCC build triplet|i686-pc-linux-gnu           |
>   GCC host triplet|i686-pc-linux-gnu           |
>  GCC target triplet|i686-pc-linux-gnu           |
>           Keywords|                            |ice-on-valid-code
>   Last reconfirmed|0000-00-00 00:00:00         |2009-01-21 10:13:21
>               date|                            |
>            Summary|ice in                      |[4.4 Regression] ice in
>                   |find_or_generate_expression,|find_or_generate_expression,
>                   |at tree-ssa-pre.c:2769      |at tree-ssa-pre.c:2769
>   Target Milestone|---                         |4.4.0
>            Version|unknown                     |4.4.0
>
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38926
>
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug, or are watching someone who is.
>

Smaller testcase:

unsigned foo (int _si1, unsigned _si2)
{
  return _si1 > 0 && _si1 > 2147483647 - _si2;
}

unsigned bar (unsigned _left, int _right)
{
  return (unsigned) _right >= 8 ? 1 : _left >> _right;
}

unsigned g_2;
unsigned g_67;
unsigned g_111;
volatile unsigned g_162;

int func_62 (unsigned p_63)
{
  p_63 = g_2 & g_67;
  if (g_2)
    ;
  else if (p_63)
    return 1;
  g_67 = bar (p_63, g_2);
  return 0;
}

void func_1 (void)
{
  if (g_2)
    for (; g_2 <= -16; g_2 = foo (g_2, 1))
      {
        for (; g_162; g_162)
          func_62 (func_62 (0));
        if (g_111)
          return;
      }
}

void crc32 (int);

void baz (void)
{
  func_1 ();
  crc32 (g_2);
}

static inline int foo (unsigned _si1)
{
  if (_si1 != 0)
    if (_si1 > 2147483647)
      return 1;
  return 0;
}

static inline unsigned bar (unsigned _left, int _right)
{
  return (unsigned) _right >= 8 ? 1 : _left >> _right;
}

unsigned g_2;
unsigned g_67;
volatile unsigned g_162;

static inline int func_62 (unsigned p_63)
{
  p_63 = g_2 & g_67;
  if (g_2)
    ;
  else if (p_63)
    return 1;
  g_67 = bar (p_63, g_2);
  return 0;
}

unsigned baz (void)
{
  if (g_2)
    for (; g_2 <= -16; g_2 = foo (g_2))
      {
        for (; g_162; g_162)
          func_62 (func_62 (0));
        if (g_67)
          break;
      }
  return g_2;
}


The only difference between -O2 and -O3 is that PPRE is enabled which is
what somehow triggers the ICE.

We try to insert {nop_expr,g_2.7_58} in bb 41

<bb 18>:
  # g_67_22 = PHI <g_67_63(39), g_67_44(D)(24)>
  # g_2.7_58 = PHI <g_2.11_10(39), g_2.7_1(24)>
  # g_2_59 = PHI <g_2_48(39), g_2_43(D)(24)>
  # VUSE <g_162_45(D)>
  g_162.9_61 ={v} g_162;
  if (g_162.9_61 != 0)
    goto <bb 41>;
  else
    goto <bb 42>;

<bb 42>:
  goto <bb 13>;

<bb 41>:
  goto <bb 4>;

The original avail_out computation says

exp_gen[41] := {  }
tmp_gen[41] := {  }
avail_out[41] := { g_2.7_1 (0002), g_2.7_58 (0030), g_162.9_61 (0032) }

(correct)

but at the point of insertion we instead have

debug[0] := { g_2.7_1 (0002), g_162.9_61 (0032), pretmp.23_38 (0046), prephitmp.24_23 (0044), prephitmp.29_66 (0037) }

so we replaced some value here, but with a different value-number.

This happens in

              /* Note that we need to value_replace both NEW_SETS, and
                 AVAIL_OUT. For both the case of NEW_SETS, the value may be
                 represented by some non-simple expression here that we want
                 to replace it with.  */
              FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
                {
                  pre_expr expr = expression_for_id (i);
                  bitmap_value_replace_in_set (NEW_SETS (block), expr);
                  bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
                }

where I see us replacing in

debug[0] := { g_2.7_1 (0002), g_2.7_58 (0030), g_162.9_61 (0032), pretmp.23_38 (0046), prephitmp.24_23 (0044), prephitmp.29_66 (0037) }

with expr prephitmp.29_66 (0037)

with the above result.  The expression set for 0037 at that point is

debug[0] := { g_2.7_58 (0030), {g_2} (0037), pretmp.23_2 (0037), prephitmp.29_66 (0037) }

where for some weird reason g_2.7_58 (0030) is in it (!?).

Happens here:

  /* If the PHI node is already available, use it.  */
  if ((res = vn_phi_lookup (phi)) != NULL_TREE)
    {
      gimple_stmt_iterator gsi = gsi_for_stmt (phi);
      remove_phi_node (&gsi, true);
      release_defs (phi);
      add_to_value (val, get_or_alloc_expr_for_name (res));

we add g_2.7_58 to 0037 here even though get_expr_value_id returns 0030.  I
vaguely remember adding that code ...

So we are about to insert a duplicate PHI node but for a different value number.

I can trivially avoid the ICE, but I wonder if that (missed optimization?) is
bad or not ...

Patch in testing.

Subject: Bug 38926

Author: rguenth
Date: Wed Jan 28 12:14:09 2009
New Revision: 143725

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=143725
Log:
2009-01-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/38926
	* tree-ssa-pre.c (add_to_value): Assert we add only expressions
	with the correct value id to a value.
	(do_regular_insertion): Use the value number of edoubleprime
	for the value number of the expr.

	Revert
	2008-08-21  Richard Guenther  <rguenther@suse.de>
  
        * tree-ssa-pre.c (insert_into_preds_of_block): Before inserting
        a PHI ask VN if it is already available.
        * tree-ssa-sccvn.h (vn_phi_lookup): Declare.
        * tree-ssa-sccvn.c (vn_phi_lookup): Export.

	* gcc.c-torture/compile/pr38926.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/pr38926.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c
    trunk/gcc/tree-ssa-sccvn.c
    trunk/gcc/tree-ssa-sccvn.h

Fixed.

Subject: Bug 38926

Author: hjl
Date: Thu Jan 29 17:06:01 2009
New Revision: 143762

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=143762
Log:
2009-01-29  H.J. Lu  <hongjiu.lu@intel.com>

	Backport from mainline:
	2009-01-29  Steve Ellcey  <sje@cup.hp.com>

	PR middle-end/38857
	* gcc.c-torture/compile/pr38857.c: New test.

	2009-01-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/38926
	* gcc.c-torture/compile/pr38926.c: New testcase.

Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.c-torture/compile/pr38857.c
      - copied unchanged from r143760, trunk/gcc/testsuite/gcc.c-torture/compile/pr38857.c
    branches/gcc-4_3-branch/gcc/testsuite/gcc.c-torture/compile/pr38926.c
      - copied unchanged from r143759, trunk/gcc/testsuite/gcc.c-torture/compile/pr38926.c
Modified:
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog

*** Bug 39017 has been marked as a duplicate of this bug. ***