| 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)); }
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