Patchwork PR55124 - tentative patch for ICE in PRE

login
register
mail settings
Submitter Tom de Vries
Date Nov. 19, 2012, 2:33 a.m.
Message ID <50A99A80.1020803@mentor.com>
Download mbox | patch
Permalink /patch/199917/
State New
Headers show

Comments

Tom de Vries - Nov. 19, 2012, 2:33 a.m.
Richard,

Consider the PR55124 example test.c:
...
int a, b;
long c;

static void inline
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;
}
...

when compiling with -O2, we're running into the following assertion in pre:
...
test.c:18:1: internal compiler error: in find_or_generate_expression, at
tree-ssa-pre.c:2802
 f1 (void)
 ^
0xcf41d3 find_or_generate_expression
	gcc/tree-ssa-pre.c:2802
0xcf42f6 create_expression_by_pieces
	gcc/tree-ssa-pre.c:2861
0xcf4193 find_or_generate_expression
	gcc/tree-ssa-pre.c:2799
0xcf42f6 create_expression_by_pieces
	gcc/tree-ssa-pre.c:2861
0xcf4e28 insert_into_preds_of_block
	gcc/tree-ssa-pre.c:3096
0xcf5c7d do_regular_insertion
	gcc/tree-ssa-pre.c:3386
...

We're hitting the assert at the end of find_or_generate_expression:
...
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 = VEC_index (bitmap, 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));
    }

  gcc_unreachable ();
}
...

The state in which we're asserting is the following:
...
#5  0x0000000000cf41d4 in find_or_generate_expression (block=0x7ffff6210f08,
op=0x7ffff62384c8, stmts=0x7fffffffdb78) at gcc/tree-ssa-pre.c:2802
2802	  gcc_unreachable ();
(gdb) p block.index
$13 = 4
(gdb) call debug_generic_expr (op)
b.4_3
(gdb) call debug_pre_expr (expr)
b.4_3
(gdb) p lookfor
$11 = 7
(gdb) call debug_bitmap_set (((bb_value_sets_t) ((block)->aux))->avail_out)
debug[0] := { b.4_8 (0012), a.10_13 (0013), _14 (0014), iftmp.5_15 (0015) }
(gdb) p leader
$12 = (pre_expr) 0x0
(gdb) call debug_bitmap ( exprset )
first = 0x21fb058 current = 0x21fb058 indx = 0
	0x21fb058 next = (nil) prev = (nil) indx = 0
		bits = { 22 25 }
(gdb) call debug_pre_expr (expression_for_id (22))
b.4_3
(gdb) call debug_pre_expr (expression_for_id (25))
b.4_31
...
We're trying to find or generate an expr with value-id 0007 in block 4. We can't
find it (there's no leader) and we can't generate it because there are no exprs
with that value that are not names.

Higher up in the call stack and skipping create_expression_by_pieces, the state
is as follows:
...
#7  0x0000000000cf4194 in find_or_generate_expression (block=0x7ffff6210f08,
op=0x7ffff6238558, stmts=0x7fffffffdb78) at gcc/tree-ssa-pre.c:2799
2799						    get_expr_type (expr));
(gdb) call debug_generic_expr (op)
c.6_5
(gdb) call debug_pre_expr (expr)
c.6_5
(gdb) p lookfor
$14 = 9
(gdb) p leader
$15 = (pre_expr) 0x0
(gdb) call debug_bitmap ( exprset )
first = 0x21fb0f8 current = 0x21fb0f8 indx = 0
	0x21fb0f8 next = (nil) prev = (nil) indx = 0
		bits = { 23 24 26 27 }
(gdb) call debug_pre_expr (temp)
{nop_expr,b.4_3}
(gdb) call debug_pre_expr (expression_for_id (23))
c.6_5
(gdb) call debug_pre_expr (expression_for_id (24))
{nop_expr,b.4_3}
(gdb) call debug_pre_expr (expression_for_id (26))
c.6_32
(gdb) call debug_pre_expr (expression_for_id (27))
{mem_ref<0B>,addr_expr<&c>}@.MEM_28
...
We're trying to find or generate an expr with value-id 0009 (in block 4). We
can't find it. We're trying to generate it using {nop_expr,b.4_3}, but as we've
seen above that won't work. The generation using expr 27 would work though.

Again higher up in the call stack and skipping create_expression_by_pieces, the
state is as follows:
...
(gdb) up
#9  0x0000000000cf4e29 in insert_into_preds_of_block (block=0x7ffff6210f70,
exprnum=19, avail=0x22102e0) at gcc/tree-ssa-pre.c:3096
3096							   &stmts, type);
(gdb) l
3091	      eprime = VEC_index (pre_expr, avail, pred->dest_idx);
3092	
3093	      if (eprime->kind != NAME && eprime->kind != CONSTANT)
3094		{
3095		  builtexpr = create_expression_by_pieces (bprime, eprime,
3096							   &stmts, type);
(gdb) p block.index
$17 = 5
(gdb) call debug_pre_expr (expr)
{convert_expr,c.7_16}
(gdb) p val
$18 = 8
(gdb) call debug_pre_expr (eprime)
{convert_expr,c.6_5}
(gdb) call get_expr_value_id (eprime)
$16 = 26
...
So we're trying to insert expr {convert_expr,c.6_5} with value-id 0026 into
block 4. The expr is the phi-translation of expr {convert_expr,c.7_16} with
value-id 0008 in block 5.

One of the reasons why we're inserting the phi-translation of expr
{convert_expr,c.7_16} in block 4 is because it's a member of ANTIC_IN[5]:
...
ANTIC_IN[5] := { iftmp.5_18 (0018), {mem_ref<0B>,addr_expr<&c>}@.MEM_23 (0016),
{nop_expr,c.7_16} (0017), {mult_expr,_17,iftmp.5_18} (0019),
{nop_expr,_19} (0020), {convert_expr,c.7_16} (0008),
{bit_ior_expr,_4,b.11_20} (0010) }
...
A requirement for an expr to be in ANTIC_IN is that that it's either 'a live
temporary or a non-simple expression whose operands are represented in the
anti-leader set'. The operand is c.7_16, which has value id 0016, as we can see
here:
...
tmp_gen[5] := { c.7_16 (0016), _17 (0017), _19 (0019), b.11_20 (0020), _4
(0008), a.2_6 (0010) }
...
And it has this representation in ANTIC_IN[5] in expr
{mem_ref<0B>,addr_expr<&c>}@.MEM_23. So that looks ok.

The order in which we traverse ANTIC_IN[5] in do_regular_insertion is this:
...
(gdb) call debug_pre_expr ( exprs.vec_[0] )
{convert_expr,c.7_16}
(gdb) call debug_pre_expr ( exprs.vec_[1] )
{bit_ior_expr,_4,b.11_20}
(gdb) call debug_pre_expr ( exprs.vec_[2] )
{mem_ref<0B>,addr_expr<&c>}@.MEM_23
(gdb) call debug_pre_expr ( exprs.vec_[3] )
{nop_expr,c.7_16}
(gdb) call debug_pre_expr ( exprs.vec_[4] )
iftmp.5_18
(gdb) call debug_pre_expr ( exprs.vec_[5] )
{mult_expr,_17,iftmp.5_18}
(gdb) call debug_pre_expr ( exprs.vec_[6] )
{nop_expr,_19}
...

The order is indeed in increasing value-id order:
...
(gdb) call get_expr_value_id ( exprs.vec_[0] )
$11 = 8
(gdb) call get_expr_value_id ( exprs.vec_[1] )
$12 = 10
(gdb) call get_expr_value_id ( exprs.vec_[2] )
$13 = 16
(gdb) call get_expr_value_id ( exprs.vec_[3] )
$14 = 17
(gdb) call get_expr_value_id ( exprs.vec_[4] )
$15 = 18
(gdb) call get_expr_value_id ( exprs.vec_[5] )
$16 = 19
(gdb) call get_expr_value_id ( exprs.vec_[6] )
$17 = 20
...

But the operand of the first expr {convert_expr,c.7_16} has value-id 0016, which
corresponds to the 3rd expr {mem_ref<0B>,addr_expr<&c>}@.MEM_23. So if I
understand the intended topological sort correctly, this is in the wrong order,
we should be processing the 3rd element before the first element. I'm not quite
sure this is the root cause of the problem though.

Assuming for the moment that the order is correct, I've written a tentative
patch that fixes the assert, simply by predicting whether
create_expression_by_pieces will succeed or not, and to skip those calls that
will fail in find_or_generate_expression. The patch has only been tested with a
tree-ssa.exp testrun, but no issues found there.

Do you think this patch is the way to fix this ICE, or is it the order of
generation that needs fixing, or is the problem yet something else?

Thanks,
- Tom
Richard Guenther - Nov. 27, 2012, 12:41 p.m.
On Mon, Nov 19, 2012 at 3:33 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Richard,
>
> Consider the PR55124 example test.c:
> ...
> int a, b;
> long c;
>
> static void inline
> 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;
> }
> ...
>
> when compiling with -O2, we're running into the following assertion in pre:
> ...
> test.c:18:1: internal compiler error: in find_or_generate_expression, at
> tree-ssa-pre.c:2802
>  f1 (void)
>  ^
> 0xcf41d3 find_or_generate_expression
>         gcc/tree-ssa-pre.c:2802
> 0xcf42f6 create_expression_by_pieces
>         gcc/tree-ssa-pre.c:2861
> 0xcf4193 find_or_generate_expression
>         gcc/tree-ssa-pre.c:2799
> 0xcf42f6 create_expression_by_pieces
>         gcc/tree-ssa-pre.c:2861
> 0xcf4e28 insert_into_preds_of_block
>         gcc/tree-ssa-pre.c:3096
> 0xcf5c7d do_regular_insertion
>         gcc/tree-ssa-pre.c:3386
> ...
>
> We're hitting the assert at the end of find_or_generate_expression:
> ...
> 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 = VEC_index (bitmap, 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));
>     }
>
>   gcc_unreachable ();
> }
> ...
>
> The state in which we're asserting is the following:
> ...
> #5  0x0000000000cf41d4 in find_or_generate_expression (block=0x7ffff6210f08,
> op=0x7ffff62384c8, stmts=0x7fffffffdb78) at gcc/tree-ssa-pre.c:2802
> 2802      gcc_unreachable ();
> (gdb) p block.index
> $13 = 4
> (gdb) call debug_generic_expr (op)
> b.4_3
> (gdb) call debug_pre_expr (expr)
> b.4_3
> (gdb) p lookfor
> $11 = 7
> (gdb) call debug_bitmap_set (((bb_value_sets_t) ((block)->aux))->avail_out)
> debug[0] := { b.4_8 (0012), a.10_13 (0013), _14 (0014), iftmp.5_15 (0015) }
> (gdb) p leader
> $12 = (pre_expr) 0x0
> (gdb) call debug_bitmap ( exprset )
> first = 0x21fb058 current = 0x21fb058 indx = 0
>         0x21fb058 next = (nil) prev = (nil) indx = 0
>                 bits = { 22 25 }
> (gdb) call debug_pre_expr (expression_for_id (22))
> b.4_3
> (gdb) call debug_pre_expr (expression_for_id (25))
> b.4_31
> ...
> We're trying to find or generate an expr with value-id 0007 in block 4. We can't
> find it (there's no leader) and we can't generate it because there are no exprs
> with that value that are not names.
>
> Higher up in the call stack and skipping create_expression_by_pieces, the state
> is as follows:
> ...
> #7  0x0000000000cf4194 in find_or_generate_expression (block=0x7ffff6210f08,
> op=0x7ffff6238558, stmts=0x7fffffffdb78) at gcc/tree-ssa-pre.c:2799
> 2799                                                get_expr_type (expr));
> (gdb) call debug_generic_expr (op)
> c.6_5
> (gdb) call debug_pre_expr (expr)
> c.6_5
> (gdb) p lookfor
> $14 = 9
> (gdb) p leader
> $15 = (pre_expr) 0x0
> (gdb) call debug_bitmap ( exprset )
> first = 0x21fb0f8 current = 0x21fb0f8 indx = 0
>         0x21fb0f8 next = (nil) prev = (nil) indx = 0
>                 bits = { 23 24 26 27 }
> (gdb) call debug_pre_expr (temp)
> {nop_expr,b.4_3}
> (gdb) call debug_pre_expr (expression_for_id (23))
> c.6_5
> (gdb) call debug_pre_expr (expression_for_id (24))
> {nop_expr,b.4_3}
> (gdb) call debug_pre_expr (expression_for_id (26))
> c.6_32
> (gdb) call debug_pre_expr (expression_for_id (27))
> {mem_ref<0B>,addr_expr<&c>}@.MEM_28
> ...
> We're trying to find or generate an expr with value-id 0009 (in block 4). We
> can't find it. We're trying to generate it using {nop_expr,b.4_3}, but as we've
> seen above that won't work. The generation using expr 27 would work though.
>
> Again higher up in the call stack and skipping create_expression_by_pieces, the
> state is as follows:
> ...
> (gdb) up
> #9  0x0000000000cf4e29 in insert_into_preds_of_block (block=0x7ffff6210f70,
> exprnum=19, avail=0x22102e0) at gcc/tree-ssa-pre.c:3096
> 3096                                                       &stmts, type);
> (gdb) l
> 3091          eprime = VEC_index (pre_expr, avail, pred->dest_idx);
> 3092
> 3093          if (eprime->kind != NAME && eprime->kind != CONSTANT)
> 3094            {
> 3095              builtexpr = create_expression_by_pieces (bprime, eprime,
> 3096                                                       &stmts, type);
> (gdb) p block.index
> $17 = 5
> (gdb) call debug_pre_expr (expr)
> {convert_expr,c.7_16}
> (gdb) p val
> $18 = 8
> (gdb) call debug_pre_expr (eprime)
> {convert_expr,c.6_5}
> (gdb) call get_expr_value_id (eprime)
> $16 = 26
> ...
> So we're trying to insert expr {convert_expr,c.6_5} with value-id 0026 into
> block 4. The expr is the phi-translation of expr {convert_expr,c.7_16} with
> value-id 0008 in block 5.
>
> One of the reasons why we're inserting the phi-translation of expr
> {convert_expr,c.7_16} in block 4 is because it's a member of ANTIC_IN[5]:
> ...
> ANTIC_IN[5] := { iftmp.5_18 (0018), {mem_ref<0B>,addr_expr<&c>}@.MEM_23 (0016),
> {nop_expr,c.7_16} (0017), {mult_expr,_17,iftmp.5_18} (0019),
> {nop_expr,_19} (0020), {convert_expr,c.7_16} (0008),
> {bit_ior_expr,_4,b.11_20} (0010) }
> ...
> A requirement for an expr to be in ANTIC_IN is that that it's either 'a live
> temporary or a non-simple expression whose operands are represented in the
> anti-leader set'. The operand is c.7_16, which has value id 0016, as we can see
> here:
> ...
> tmp_gen[5] := { c.7_16 (0016), _17 (0017), _19 (0019), b.11_20 (0020), _4
> (0008), a.2_6 (0010) }
> ...
> And it has this representation in ANTIC_IN[5] in expr
> {mem_ref<0B>,addr_expr<&c>}@.MEM_23. So that looks ok.
>
> The order in which we traverse ANTIC_IN[5] in do_regular_insertion is this:
> ...
> (gdb) call debug_pre_expr ( exprs.vec_[0] )
> {convert_expr,c.7_16}
> (gdb) call debug_pre_expr ( exprs.vec_[1] )
> {bit_ior_expr,_4,b.11_20}
> (gdb) call debug_pre_expr ( exprs.vec_[2] )
> {mem_ref<0B>,addr_expr<&c>}@.MEM_23
> (gdb) call debug_pre_expr ( exprs.vec_[3] )
> {nop_expr,c.7_16}
> (gdb) call debug_pre_expr ( exprs.vec_[4] )
> iftmp.5_18
> (gdb) call debug_pre_expr ( exprs.vec_[5] )
> {mult_expr,_17,iftmp.5_18}
> (gdb) call debug_pre_expr ( exprs.vec_[6] )
> {nop_expr,_19}
> ...
>
> The order is indeed in increasing value-id order:
> ...
> (gdb) call get_expr_value_id ( exprs.vec_[0] )
> $11 = 8
> (gdb) call get_expr_value_id ( exprs.vec_[1] )
> $12 = 10
> (gdb) call get_expr_value_id ( exprs.vec_[2] )
> $13 = 16
> (gdb) call get_expr_value_id ( exprs.vec_[3] )
> $14 = 17
> (gdb) call get_expr_value_id ( exprs.vec_[4] )
> $15 = 18
> (gdb) call get_expr_value_id ( exprs.vec_[5] )
> $16 = 19
> (gdb) call get_expr_value_id ( exprs.vec_[6] )
> $17 = 20
> ...
>
> But the operand of the first expr {convert_expr,c.7_16} has value-id 0016, which
> corresponds to the 3rd expr {mem_ref<0B>,addr_expr<&c>}@.MEM_23. So if I
> understand the intended topological sort correctly, this is in the wrong order,
> we should be processing the 3rd element before the first element. I'm not quite
> sure this is the root cause of the problem though.
>
> Assuming for the moment that the order is correct, I've written a tentative
> patch that fixes the assert, simply by predicting whether
> create_expression_by_pieces will succeed or not, and to skip those calls that
> will fail in find_or_generate_expression. The patch has only been tested with a
> tree-ssa.exp testrun, but no issues found there.
>
> Do you think this patch is the way to fix this ICE, or is it the order of
> generation that needs fixing, or is the problem yet something else?

This looks like an ordering issue.  But rather in what value-numbers were
assigned to the expressions, not the sorting itself.  I suppose it may
result from your vitrual operand numbering changes and compute_avail
doing

                  case VN_REFERENCE:
                    {
                      vn_reference_t ref;
                      vn_reference_lookup (gimple_assign_rhs1 (stmt),
                                           gimple_vuse (stmt),
                                           VN_WALK, &ref);

which valueizes the VUSE here?

Richard.

> Thanks,
> - Tom

Patch

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 192023)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -2760,6 +2760,72 @@ 
   return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
 }
 
+static bool
+can_create_expression_by_pieces (pre_expr expr, basic_block block);
+
+static bool
+can_create_op_by_pieces (tree op, basic_block block)
+{
+  if (op && TREE_CODE (op) == SSA_NAME)
+    {
+      unsigned int value_id = VN_INFO (op)->value_id;
+      pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), value_id);
+      if (leader
+	  && (leader->kind == NAME
+	      || leader->kind == CONSTANT))
+	return true;
+
+      bitmap exprset = VEC_index (bitmap, value_expressions, value_id);
+      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
+	      && can_create_expression_by_pieces (temp, block))
+	    return true;
+	}
+      return false;
+    }
+  return true;
+}
+
+static bool
+can_create_expression_by_pieces (pre_expr expr, basic_block block)
+{
+  switch (expr->kind)
+    {
+    case NARY:
+      {
+	unsigned int i;
+	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
+	for (i = 0; i < nary->length; i++)
+	  if (!can_create_op_by_pieces (nary->op[i], block))
+	    return false;
+	return true;
+      }
+      break;
+    case REFERENCE:
+      {
+	vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
+	vn_reference_op_t vro;
+	unsigned int i;
+
+	FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro)
+	  {
+	    if (!can_create_op_by_pieces (vro->op0, block)
+		|| !can_create_op_by_pieces (vro->op1, block)
+		|| !can_create_op_by_pieces (vro->op2, block))
+	      return false;
+	  }
+	return true;
+      }
+    default:
+      break;
+    }
+  return false;
+}
+
 /* Find a leader for an expression, or generate one using
    create_expression_by_pieces if it's ANTIC but
    complex.
@@ -2794,7 +2860,8 @@ 
   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     {
       pre_expr temp = expression_for_id (i);
-      if (temp->kind != NAME)
+      if (temp->kind != NAME
+	  && can_create_expression_by_pieces (temp, block))
 	return create_expression_by_pieces (block, temp, stmts,
 					    get_expr_type (expr));
     }