[Bug tree-optimization/55124] New: ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[Bug tree-optimization/55124] New: ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[antoine.balestrat at gmail dot com]

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

             Bug #: 55124
           Summary: ICE in find_or_generate_expression, at
                    tree-ssa-pre.c:2803
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: antoine.balestrat@gmail.com


Using GCC 4.8.0 20121029 :

$ cat daexpr.c
int a, b;
long c;

void f2(void)
{
    unsigned long k = 1;

    foo(b ? k = 0 : 0);

    b = ((c = b) ? (k ? : (c = 0)) : a) * c;
}

void f1(void)
{
    f2();

    a = b | c;
}

$ xgcc -O3 -w daexpr.c
daexpr.c: In function ‘f1’:
daexpr.c:13:6: internal compiler error: in find_or_generate_expression, at
tree-ssa-pre.c:2803
 void f1(void)
      ^
0xb86241 find_or_generate_expression
    ../../srcdir/gcc/tree-ssa-pre.c:2803
0xb863cb create_expression_by_pieces
    ../../srcdir/gcc/tree-ssa-pre.c:2862
0xb86201 find_or_generate_expression
    ../../srcdir/gcc/tree-ssa-pre.c:2800
0xb863cb create_expression_by_pieces
    ../../srcdir/gcc/tree-ssa-pre.c:2862
0xb86f2b insert_into_preds_of_block
    ../../srcdir/gcc/tree-ssa-pre.c:3097
0xb87de3 do_regular_insertion
    ../../srcdir/gcc/tree-ssa-pre.c:3387
0xb8859b insert_aux
    ../../srcdir/gcc/tree-ssa-pre.c:3601
0xb885fe insert_aux
    ../../srcdir/gcc/tree-ssa-pre.c:3611
0xb885fe insert_aux
    ../../srcdir/gcc/tree-ssa-pre.c:3611
0xb886d8 insert
    ../../srcdir/gcc/tree-ssa-pre.c:3634
0xb8bb49 do_pre
    ../../srcdir/gcc/tree-ssa-pre.c:4710
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug tree-optimization/55124] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-10-29
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-29 18:19:50 UTC ---
Mine.

[Bug tree-optimization/55124] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-10-29 19:44:22 UTC ---
Started with http://gcc.gnu.org/viewcvs?view=revision&revision=189321

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.0
            Summary|ICE in                      |[4.8 Regression] ICE in
                   |find_or_generate_expression |find_or_generate_expression
                   |, at tree-ssa-pre.c:2803    |, at tree-ssa-pre.c:2803

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-30 10:18:15 UTC ---
Before the revision we were successfully able to insert

Inserted pretmp_46 = c;
 in predecessor 4
Inserted pretmp_47 = (int) pretmp_46;
 in predecessor 4

while after the revision we ICE.

Simplified testcase:

int a, b;
long c;

static void f2(void)
{
  unsigned long k = 1;

  foo(b ? k = 0 : 0);

  b = ((c = b) ? (k ? : (c = 0)) : a) * c;
}

void f1(void)
{
  f2();

  a = b | c;
}

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
         AssignedTo|rguenth at gcc dot gnu.org  |unassigned at gcc dot
                   |                            |gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-30 10:18:52 UTC ---
Toms, not mine.

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |vries at gcc dot gnu.org
                   |gnu.org                     |

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

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

--- Comment #5 from vries at gcc dot gnu.org 2012-10-30 15:49:42 UTC ---
tentative patch:
...
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c    (revision 192023)
+++ gcc/tree-ssa-pre.c    (working copy)
@@ -1657,6 +1657,16 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1,
         if (result)
           VEC_free (vn_reference_op_s, heap, newoperands);

+        if (result && TREE_CODE (result) == SSA_NAME)
+          {
+        gimple def_stmt = SSA_NAME_DEF_STMT (result);
+        basic_block def_bb = gimple_bb (def_stmt);
+        if (def_bb != pred
+            && !dominated_by_p (CDI_DOMINATORS, pred,
+                    def_bb))
+          return NULL;
+          }
+
         /* We can always insert constants, so if we have a partial
            redundant constant load of another type try to translate it
            to a constant of appropriate type.  */
...

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> 2012-10-30 17:12:46 UTC ---
On Tue, 30 Oct 2012, vries at gcc dot gnu.org wrote:

> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55124
> 
> vries at gcc dot gnu.org changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |rguenth at gcc dot gnu.org
> 
> --- Comment #5 from vries at gcc dot gnu.org 2012-10-30 15:49:42 UTC ---
> tentative patch:
> ...
> Index: gcc/tree-ssa-pre.c
> ===================================================================
> --- gcc/tree-ssa-pre.c    (revision 192023)
> +++ gcc/tree-ssa-pre.c    (working copy)
> @@ -1657,6 +1657,16 @@ phi_translate_1 (pre_expr expr, bitmap_set_t set1,
>          if (result)
>            VEC_free (vn_reference_op_s, heap, newoperands);
> 
> +        if (result && TREE_CODE (result) == SSA_NAME)
> +          {
> +        gimple def_stmt = SSA_NAME_DEF_STMT (result);
> +        basic_block def_bb = gimple_bb (def_stmt);
> +        if (def_bb != pred
> +            && !dominated_by_p (CDI_DOMINATORS, pred,
> +                    def_bb))
> +          return NULL;
> +          }
> +
>          /* We can always insert constants, so if we have a partial
>             redundant constant load of another type try to translate it
>             to a constant of appropriate type.  */
> ...


Err ... certainly not.  result is a value-number, not sth to
be taken literally and its def stmt to be looked up.  See
how clean () removes names from the sets instead.

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|vries at gcc dot gnu.org    |rguenth at gcc dot gnu.org

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2012-11-29 14:35:08 UTC ---
To summarize here, the issue is that PRE insertion (and also expression
clean and dependent_clean, but not really phi-translation) need to process
expression set from leafs (where the dependence tree is formed by the
value-ids of the expressions).  In ancient times this might have been
ensured by sorting expressions after their value-id
(sorted_array_from_bitmap_set), but at least with SCCVN there is no such
thing as a topological value-id assignment.

Thus, the correct fix is indeed to properly sort the expression array
according to expression dependencies.  Which then allows to get rid of
value-ids in SCCVN and compute them lazily in get_expr_value_id.

I'll take over from Tom here again.

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> 2012-11-30 12:33:03 UTC ---
This issue is latent and papered over heavily by find_or_generate_expression
which does

static tree
find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
{
  pre_expr expr = get_or_alloc_expr_for (op);
  unsigned int lookfor = get_expr_value_id (expr);
  pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
  if (leader)
    {
      if (leader->kind == NAME)
        return PRE_EXPR_NAME (leader);
      else if (leader->kind == CONSTANT)
        return PRE_EXPR_CONSTANT (leader);
    }

  /* It must be a complex expression, so generate it recursively.  */
  bitmap exprset = value_expressions[lookfor];
  bitmap_iterator bi;
  unsigned int i;
  EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    {
      pre_expr temp = expression_for_id (i);
      if (temp->kind != NAME)
        return create_expression_by_pieces (block, temp, stmts,
                                            get_expr_type (expr));
    }


thus - it picks some _random_ expression and tries to generate it.
Most of the time it happens to pick the correct one.

In theory - with proper insert ordering - we should never end up
here with no leader, we should never even end up with a complex
leader either!  (in fact bitmap_find_leader should, according to
its documentation, never return a complex leader)

Now, for tree-ssa/ssa-pre-28.c we have

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

  <bb 5>:
  goto <bb 4>;

  <bb 3>:

  <bb 4>:
  # mask_1 = PHI <-2(5), 0(3)>
  result_4 = i_3(D) + 1;
  result_5 = mask_1 & result_4;
  return result_5;

we start to try inserting both i_3(D) + 1 and mask_1 & result_4 (simplified to
0 in bb3!) in bb 5.  But i_3(D) + 1 is neither available in bb3 nor in bb5 so
we don't insert it.  This means upon trying to insert mask_1 & result_4 in
bb 5 we don't find a leader for result_4 because we didn't insert the
expression (we thought it was not profitable or necessary to do so).

Which means insertion works in an awkward way currently.  It seems it should
compute which expressions it likes to insert (and where, and using the
translated expressions) and then add value-dependencies out of that set.
And only in a second step actually perform the insertions (but then in
proper order).

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-03 14:42:46 UTC ---
Ok, instead of rewriting this mess during stage3 I'll re-instantiate the
failure path (but consistently) of expression insertion so that in this case
we defer to a further insert iteration to fixup things.  I have to keep the
odd code for ssa-pre-28.c though to not regress here.

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-04 09:19:25 UTC ---
Author: rguenth
Date: Tue Dec  4 09:19:05 2012
New Revision: 194125

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194125
Log:
2012-12-04  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/55124
    * tree-ssa-pre.c (find_or_generate_expression): Instead of
    ICEing when we are not able to generate an expression defer it
    by signalling failure.  Fix possible wrong-code issue by
    not picking random REFERENCE expressions as fallback.
    (create_component_ref_by_pieces_1): Adjust.  Add failure paths.
    (create_expression_by_pieces): Likewise.
    (insert_into_preds_of_block): When expression generation failed
    for one edge make sure to not insert a PHI node.

    * gcc.dg/torture/pr55124.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr55124.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c

[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-04 09:25:44 UTC ---
Fixed.