From patchwork Mon Nov 19 02:33:36 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 199917 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id C72182C0097 for ; Mon, 19 Nov 2012 13:33:56 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1353897237; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=+vE2zmu8A26GJ2+BdDg3N9GCrMA=; b=IoeVqFbja8MLAP0 t6NY1FPotgRa0J++9httzZP/ZAV0TZPSc0/nSddJ3juyf2q7MPGn1obo+8qz0vey KcfcCAOjlPgzaByuo/JdPlgX23QfnyrVV0P5J1d/16wCUqkSF/kIEwb2//HcIX6N VaupCissWgmHP3b2RhSBdCi6+qz0= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=RUsiwyU3bnJ1K3sKslYbU46A584oPo1ePGSoC+kBNDOICZQT63sUmMnOQffV3V 1lliQ9NcEsADLS6pH+76seciE7r/PkZRIrsRjuhk1f05Jhq6Q4/kFVHw2NbNjDnO Ic3oGPTEmQap+tx/tXm52zoS5KpmvBAkiPavp3JZ9fKWo=; Received: (qmail 4861 invoked by alias); 19 Nov 2012 02:33:53 -0000 Received: (qmail 4843 invoked by uid 22791); 19 Nov 2012 02:33:52 -0000 X-SWARE-Spam-Status: No, hits=-3.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 19 Nov 2012 02:33:46 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1TaHBB-0002J3-0P from Tom_deVries@mentor.com ; Sun, 18 Nov 2012 18:33:45 -0800 Received: from SVR-IES-FEM-02.mgc.mentorg.com ([137.202.0.106]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Sun, 18 Nov 2012 18:33:44 -0800 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-02.mgc.mentorg.com (137.202.0.106) with Microsoft SMTP Server id 14.1.289.1; Mon, 19 Nov 2012 02:33:42 +0000 Message-ID: <50A99A80.1020803@mentor.com> Date: Mon, 19 Nov 2012 03:33:36 +0100 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121011 Thunderbird/16.0.1 MIME-Version: 1.0 To: Richard Biener CC: "gcc-patches@gcc.gnu.org" Subject: PR55124 - tentative patch for ICE in PRE Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 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)); }