PR55124 - tentative patch for ICE in PRE

[Tom de Vries]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr55124-tentative.patch
Type: text/x-patch
Size: 2346 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20121119/6edb2763/attachment.bin>