Message ID | 50A99A80.1020803@mentor.com |
---|---|
State | New |
Headers | show |
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
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)); }