From patchwork Thu Nov 29 12:14:37 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: 202729 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 AF1EF2C0086 for ; Thu, 29 Nov 2012 23:15:18 +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=1354796118; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=RxcLeQuVzWoCD9Lr8ou8G9KM8Wo=; b=VyVJNhCDwKqYZMI8EC2myJgAtIv7Mtya5nuve6ItRdhE5rQ8HVil4xDXyOiOv2 45gGOkC0+8QZpgQh4YopGS6BqWWswG9yaya8egLCyGyYkmTQdmk9KejdkaxMGmb4 fJLwrn0RUW+yapnLqDkRNav3oi4lnwiOm+hAq3z8lr8W0= 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:References:In-Reply-To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=fH7/UxqtZew36WT+e/lUPu5DfZqCc+a6I1HsRr/erq+NFEajbMhY7vb54T/EfY i0PLsAvQb7Yz0GHhNSGGWRw8xHupY3D+kovX4LBwasXUg/oco8gHrA2nXn1hddUT VMvpST8LKxpNA6mSUtwy4DV9ougPxLhWohX5GpkhuKPM0=; Received: (qmail 9573 invoked by alias); 29 Nov 2012 12:15:04 -0000 Received: (qmail 9510 invoked by uid 22791); 29 Nov 2012 12:15:02 -0000 X-SWARE-Spam-Status: No, hits=-4.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_THREADED, 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; Thu, 29 Nov 2012 12:14:47 +0000 Received: from svr-orw-exc-10.mgc.mentorg.com ([147.34.98.58]) by relay1.mentorg.com with esmtp id 1Te30v-0000cj-OK from Tom_deVries@mentor.com ; Thu, 29 Nov 2012 04:14:45 -0800 Received: from SVR-IES-FEM-01.mgc.mentorg.com ([137.202.0.104]) by SVR-ORW-EXC-10.mgc.mentorg.com with Microsoft SMTPSVC(6.0.3790.4675); Thu, 29 Nov 2012 04:14:45 -0800 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.1.289.1; Thu, 29 Nov 2012 12:14:43 +0000 Message-ID: <50B751AD.5030504@mentor.com> Date: Thu, 29 Nov 2012 13:14:37 +0100 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: Richard Biener CC: Tom de Vries , "gcc-patches@gcc.gnu.org" Subject: Re: PR55124 - tentative patch for ICE in PRE References: <50A99A80.1020803@mentor.com> <50B61A1A.50305@codesourcery.com> In-Reply-To: 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 On 29/11/12 11:26, Richard Biener wrote: > I'm continuing trying to move value-ids back to PRE land. Your patch > would be nice in a form that verifies the order is indeed topological, > maybe you can re-work it in a way that does this in > sorted_array_from_bitmap_set in a ENABLE_CHECKING piece? Richard, These are my current patches, tested together with tree-ssa.exp. The first patch checks the topological order in sorted_array_from_bitmap_set. Testing only this one with tree-ssa.exp gives 400 failures. Btw, I'm not 100% sure if this patch checks the required order. It's clear what topological order means if there is one expression per value. I've ran tree-ssa.exp with an assert that the number of expressions and values in the bitmap_set is equal in sorted_array_from_bitmap_set, and that passed, so that seems to be the case generally, but I don't know if that's by design. If there are more expressions with the same value, this patch is a 'weak' check, meaning a value is considered available if one expression with that value is available. A 'strong' check would consider a value available if all expressions with that value are available. I can imagine doing clean on a strongly or weakly ordered array could give different results. The second patch calculates value_id during pre. If you're working on the value_id part, I'll stop here. Thanks, - Tom 2012-11-29 Tom de Vries * tree-ssa-pre.c (sorted_array_from_bitmap_set): Use EXECUTE_IF_AND_IN_BITMAP instead of EXECUTE_IF_SET_IN_BITMAP. Check sort result ifdef ENABLE_CHECKING. Check if the sorted array has the same number of expressions as the bitmap_set. Index: gcc/tree-ssa-sccvn.c =================================================================== --- gcc/tree-ssa-sccvn.c (revision 193497) +++ gcc/tree-ssa-sccvn.c (working copy) @@ -3967,8 +3967,8 @@ /* Set the value ids in the valid hash tables. */ -static void -set_hashtable_value_ids (void) +void +vn_set_hashtable_value_ids (void) { htab_iterator hi; vn_nary_op_t vno; @@ -4000,7 +4000,6 @@ { size_t i; tree param; - bool changed = true; default_vn_walk_kind = default_vn_walk_kind_; @@ -4029,45 +4028,6 @@ } } - /* Initialize the value ids. */ - - for (i = 1; i < num_ssa_names; ++i) - { - tree name = ssa_name (i); - vn_ssa_aux_t info; - if (!name) - continue; - info = VN_INFO (name); - if (info->valnum == name - || info->valnum == VN_TOP) - info->value_id = get_next_value_id (); - else if (is_gimple_min_invariant (info->valnum)) - info->value_id = get_or_alloc_constant_value_id (info->valnum); - } - - /* Propagate until they stop changing. */ - while (changed) - { - changed = false; - for (i = 1; i < num_ssa_names; ++i) - { - tree name = ssa_name (i); - vn_ssa_aux_t info; - if (!name) - continue; - info = VN_INFO (name); - if (TREE_CODE (info->valnum) == SSA_NAME - && info->valnum != name - && info->value_id != VN_INFO (info->valnum)->value_id) - { - changed = true; - info->value_id = VN_INFO (info->valnum)->value_id; - } - } - } - - set_hashtable_value_ids (); - if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Value numbers:\n"); Index: gcc/tree-ssa-sccvn.h =================================================================== --- gcc/tree-ssa-sccvn.h (revision 193497) +++ gcc/tree-ssa-sccvn.h (working copy) @@ -184,6 +184,7 @@ extern vn_ssa_aux_t VN_INFO_GET (tree); tree vn_get_expr_for (tree); bool run_scc_vn (vn_lookup_kind); +void vn_set_hashtable_value_ids (void); void free_scc_vn (void); tree vn_nary_op_lookup (tree, vn_nary_op_t *); tree vn_nary_op_lookup_stmt (gimple, vn_nary_op_t *); Index: gcc/tree-ssa-pre.c =================================================================== --- gcc/tree-ssa-pre.c (revision 193497) +++ gcc/tree-ssa-pre.c (working copy) @@ -573,7 +573,61 @@ *slot = new_pair; } +/* Assign a value_id to OP, if it needs one. */ +static void +assign_value_id (tree op) +{ + tree valnum; + + if (TREE_CODE (op) != SSA_NAME + || VN_INFO (op)->value_id != 0) + return; + + valnum = VN_INFO (op)->valnum; + /* Check if op is unkown. */ + if (valnum == VN_TOP) + return; + + /* Handle case that op is a constant. */ + if (TREE_CODE (valnum) != SSA_NAME) + { + VN_INFO (op)->value_id = get_or_alloc_constant_value_id (valnum); + return; + } + + if (VN_INFO (valnum)->value_id != 0) + /* Copy the value_id from the valuation. */ + VN_INFO (op)->value_id = VN_INFO (valnum)->value_id; + else + { + /* Op has no value_id, and it's valuation has no value_id. Allocate + one. */ + VN_INFO (op)->value_id = get_next_value_id (); + + /* If necessary, copy new value_id to the valuation. */ + if (valnum != op) + { + VN_INFO (valnum)->value_id = VN_INFO (op)->value_id; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to ssa_name ", + VN_INFO (op)->value_id); + print_generic_expr (dump_file, valnum, 0); + fprintf (dump_file, "\n"); + } + } + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to ssa_name ", + VN_INFO (op)->value_id); + print_generic_expr (dump_file, op, 0); + fprintf (dump_file, "\n"); + } +} + /* Add expression E to the expression set of value id V. */ static void @@ -614,6 +668,8 @@ static unsigned int get_expr_value_id (pre_expr expr) { + unsigned int value_id; + switch (expr->kind) { case CONSTANT: @@ -628,14 +684,21 @@ return id; } case NAME: - return VN_INFO (PRE_EXPR_NAME (expr))->value_id; + value_id = VN_INFO (PRE_EXPR_NAME (expr))->value_id; + gcc_assert (value_id != 0 || + VN_INFO (PRE_EXPR_NAME (expr))->valnum == VN_TOP); + return value_id; case NARY: - return PRE_EXPR_NARY (expr)->value_id; + value_id = PRE_EXPR_NARY (expr)->value_id; + break; case REFERENCE: - return PRE_EXPR_REFERENCE (expr)->value_id; + value_id = PRE_EXPR_REFERENCE (expr)->value_id; + break; default: gcc_unreachable (); } + gcc_assert (value_id != 0); + return value_id; } /* Return a SCCVN valnum (SSA name or constant) for the PRE value-id VAL. */ @@ -718,6 +781,9 @@ unsigned int i, j; bitmap_iterator bi, bj; VEC(pre_expr, heap) *result; +#ifdef ENABLE_CHECKING + bitmap values_done = BITMAP_ALLOC (NULL); +#endif /* Pre-allocate roughly enough space for the array. */ result = VEC_alloc (pre_expr, heap, bitmap_count_bits (&set->values)); @@ -735,13 +801,70 @@ If this is somehow a significant lose for some cases, we can choose which set to walk based on the set size. */ bitmap exprset = VEC_index (bitmap, value_expressions, i); - EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj) + EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, j, bj) { - if (bitmap_bit_p (&set->expressions, j)) - VEC_safe_push (pre_expr, heap, result, expression_for_id (j)); - } + pre_expr expr = expression_for_id (j); + VEC_safe_push (pre_expr, heap, result, expr); + +#ifdef ENABLE_CHECKING + switch (expr->kind) + { + case NARY: + { + vn_nary_op_t nary = PRE_EXPR_NARY (expr); + unsigned int k; + for (k = 0; k < nary->length; k++) + { + tree op = nary->op[k]; + if (TREE_CODE (op) != SSA_NAME) + continue; + unsigned int v = VN_INFO (op)->value_id; + if (!bitmap_bit_p (values_done, v) + && bitmap_bit_p (&set->values, v)) + gcc_unreachable (); + } + } + break; + + case REFERENCE: + { + vn_reference_t ref = PRE_EXPR_REFERENCE (expr); + vn_reference_op_t vro; + + unsigned int k; + FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, k, vro) + { + tree ops[3] = { vro->op0, vro->op1, vro->op2}; + unsigned int l; + for (l = 0; l < 3; l++) + { + tree op = ops[l]; + if (op == NULL_TREE + || TREE_CODE (op) != SSA_NAME) + continue; + unsigned int v = VN_INFO (op)->value_id; + if (!bitmap_bit_p (values_done, v) + && bitmap_bit_p (&set->values, v)) + gcc_unreachable (); + } + } + } + break; + + default: + break; + } + + bitmap_set_bit (values_done, get_expr_value_id (expr)); +#endif + } } + gcc_assert (bitmap_count_bits (&set->expressions) + == VEC_length (pre_expr, result)); +#ifdef ENABLE_CHECKING + BITMAP_FREE (values_done); +#endif return result; } @@ -1526,6 +1649,12 @@ return constant; get_or_alloc_expression_id (expr); } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to pre_expr ", new_val_id); + print_pre_expr (dump_file, expr); + fprintf (dump_file, " with id %u\n", expr->id); + } add_to_value (new_val_id, expr); } return expr; @@ -1726,6 +1855,12 @@ return constant; get_or_alloc_expression_id (expr); } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to pre_expr ", new_val_id); + print_pre_expr (dump_file, expr); + fprintf (dump_file, " with id %u\n", expr->id); + } add_to_value (new_val_id, expr); } VEC_free (vn_reference_op_s, heap, newoperands); @@ -2932,6 +3067,14 @@ VN_INFO_GET (forcedname)->valnum = forcedname; VN_INFO (forcedname)->value_id = get_next_value_id (); nameexpr = get_or_alloc_expr_for_name (forcedname); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to pre_expr ", + VN_INFO (forcedname)->value_id); + print_pre_expr (dump_file, nameexpr); + fprintf (dump_file, " with id %u\n", nameexpr->id); + } + add_to_value (VN_INFO (forcedname)->value_id, nameexpr); bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); @@ -3657,26 +3800,17 @@ make_values_for_phi (gimple phi, basic_block block) { tree result = gimple_phi_result (phi); - unsigned i; /* We have no need for virtual phis, as they don't represent actual computations. */ if (virtual_operand_p (result)) return; + assign_value_id (result); pre_expr e = get_or_alloc_expr_for_name (result); add_to_value (get_expr_value_id (e), e); bitmap_value_insert_into_set (AVAIL_OUT (block), e); bitmap_insert_into_set (PHI_GEN (block), e); - for (i = 0; i < gimple_phi_num_args (phi); ++i) - { - tree arg = gimple_phi_arg_def (phi, i); - if (TREE_CODE (arg) == SSA_NAME) - { - e = get_or_alloc_expr_for_name (arg); - add_to_value (get_expr_value_id (e), e); - } - } } /* Compute the AVAIL set for all basic blocks. @@ -3710,6 +3844,7 @@ || virtual_operand_p (name)) continue; + assign_value_id (name); e = get_or_alloc_expr_for_name (name); add_to_value (get_expr_value_id (e), e); bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e); @@ -3775,8 +3910,8 @@ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) { + assign_value_id (op); pre_expr e = get_or_alloc_expr_for_name (op); - add_to_value (get_expr_value_id (e), e); bitmap_insert_into_set (TMP_GEN (block), e); bitmap_value_insert_into_set (AVAIL_OUT (block), e); @@ -3800,6 +3935,7 @@ vn_reference_t ref; pre_expr result = NULL; VEC(vn_reference_op_s, heap) *ops = NULL; + bool assigned_value_id = false; /* We can value number only calls to real functions. */ if (gimple_call_internal_p (stmt)) @@ -3826,10 +3962,24 @@ result->kind = REFERENCE; result->id = 0; PRE_EXPR_REFERENCE (result) = ref; + if (ref->value_id == 0) + { + assign_value_id (ref->result); + ref->value_id = VN_INFO (ref->result)->value_id; + assigned_value_id = true; + } get_or_alloc_expression_id (result); add_to_value (get_expr_value_id (result), result); bitmap_value_insert_into_set (EXP_GEN (block), result); + if (assigned_value_id + && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to pre_expr ", + get_expr_value_id (result)); + print_pre_expr (dump_file, result); + fprintf (dump_file, " with id %u\n", result->id); + } } continue; } @@ -3837,6 +3987,7 @@ case GIMPLE_ASSIGN: { pre_expr result = NULL; + bool assigned_value_id = false; switch (vn_get_stmt_kind (stmt)) { case VN_NARY: @@ -3866,6 +4017,12 @@ result->kind = NARY; result->id = 0; PRE_EXPR_NARY (result) = nary; + if (nary->value_id == 0) + { + assign_value_id (nary->result); + nary->value_id = VN_INFO (nary->result)->value_id; + assigned_value_id = true; + } break; } @@ -3907,6 +4064,12 @@ result->kind = REFERENCE; result->id = 0; PRE_EXPR_REFERENCE (result) = ref; + if (ref->value_id == 0) + { + assign_value_id (ref->result); + ref->value_id = VN_INFO (ref->result)->value_id; + assigned_value_id = true; + } break; } @@ -3915,6 +4078,14 @@ } get_or_alloc_expression_id (result); + if (assigned_value_id + && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "assigned value id %u to pre_expr ", + get_expr_value_id (result)); + print_pre_expr (dump_file, result); + fprintf (dump_file, " with id %u\n", result->id); + } add_to_value (get_expr_value_id (result), result); bitmap_value_insert_into_set (EXP_GEN (block), result); continue; @@ -3933,6 +4104,30 @@ } free (worklist); + + /* Propagate value-ids until they stop changing. */ + bool changed = true; + while (changed) + { + changed = false; + for (i = 1; i < num_ssa_names; ++i) + { + tree name = ssa_name (i); + vn_ssa_aux_t info; + if (!name) + continue; + info = VN_INFO (name); + if (TREE_CODE (info->valnum) == SSA_NAME + && info->valnum != name + && info->value_id != VN_INFO (info->valnum)->value_id) + { + changed = true; + info->value_id = VN_INFO (info->valnum)->value_id; + } + } + } + + vn_set_hashtable_value_ids (); } @@ -4589,6 +4784,17 @@ } } BITMAP_FREE (worklist); + + /* Release SSA names we just created to have leaders in + get_representative_for but never ended up using. */ + for (i = 0; i < num_ssa_names; ++i) + { + tree name = ssa_name (i); + if (name + && !SSA_NAME_IS_DEFAULT_DEF (name) + && gimple_nop_p (SSA_NAME_DEF_STMT (name))) + release_ssa_name (name); + } }