From patchwork Mon Apr 4 01:44:52 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Froyd X-Patchwork-Id: 89572 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 85527B6FB5 for ; Mon, 4 Apr 2011 11:45:10 +1000 (EST) Received: (qmail 1923 invoked by alias); 4 Apr 2011 01:45:06 -0000 Received: (qmail 1890 invoked by uid 22791); 4 Apr 2011 01:45:03 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 04 Apr 2011 01:44:58 +0000 Received: (qmail 18569 invoked from network); 4 Apr 2011 01:44:56 -0000 Received: from unknown (HELO codesourcery.com) (froydnj@127.0.0.2) by mail.codesourcery.com with ESMTPA; 4 Apr 2011 01:44:56 -0000 Date: Sun, 3 Apr 2011 21:44:52 -0400 From: Nathan Froyd To: gcc-patches@gcc.gnu.org Subject: [PATCH] cleanup gcse.c:canon_modify_mem_list Message-ID: <20110404014451.GA16239@nightcrawler> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) X-IsSubscribed: yes 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 The patch below converts gcse.c:canon_modify_mem_list to hold VECs instead of EXPR_LIST rtxes. I am ambivalent about the use of VECs in canon_modify_mem_list; they will waste some memory compared to the linked list scheme present before, though I'm not sure how much. It would depend on the average chain length, etc. I'm happy to use an linked list datastructure instead, allocated out of an alloc_pool (better statistics!) or even gcse's private obstack if folks think that would be better. Moving things out of GC memory and eliminating a use of EXPR_LIST has to be considered a good thing, though... Doing this required addressing an odd little comment in record_last_mem_set_info: if (CALL_P (insn)) { /* Note that traversals of this loop (other than for free-ing) will break after encountering a CALL_INSN. So, there's no need to insert a pair of items, as canon_list_insert does. */ canon_modify_mem_list[bb] = alloc_INSN_LIST (insn, canon_modify_mem_list[bb]); bitmap_set_bit (blocks_with_calls, bb); } This is all well and good, except that the only real traversal of canon_modify_mem_list (compute_transp) doesn't check for CALL_INSNs. Instead, it has: EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, blocks_with_calls, 0, bb_index, bi) { rtx list_entry = canon_modify_mem_list[bb_index]; while (list_entry) { rtx dest, dest_addr; /* LIST_ENTRY must be an INSN of some kind that sets memory. Examine each hunk of memory that is modified. */ dest = XEXP (list_entry, 0); list_entry = XEXP (list_entry, 1); dest_addr = XEXP (list_entry, 0); Notice that since bits in blocks_with_calls are set if we find a CALL_INSN, we'll never examine canon_modify_mem_list for such blocks. Hence we can dispense with the spurious consing in record_last_mem_set_info. Tested on x86_64-unknown-linux-gnu. OK to commit? -Nathan * gcse.c (modify_pair): Define. Define a VEC of it. (canon_modify_mem_list): Convert to an array of VECs. (free_insn_expr_list_list): Delete. (clear_modify_mem_tables): Call VEC_free instead. (record_last_mem_set_info): Don't modify canon_modify_mem_list. (alloc_gcse_mem): Adjust for canon_modify_mem_list change. (canon_list_insert, compute_transp): Likewise. --- gcc/gcse.c | 79 +++++++++++++++++++++-------------------------------------- 1 files changed, 28 insertions(+), 51 deletions(-) diff --git a/gcc/gcse.c b/gcc/gcse.c index a1de61f..d6a4db4 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -385,8 +385,18 @@ static regset reg_set_bitmap; static rtx * modify_mem_list; static bitmap modify_mem_list_set; -/* This array parallels modify_mem_list, but is kept canonicalized. */ -static rtx * canon_modify_mem_list; +typedef struct modify_pair_s +{ + rtx dest; /* A MEM. */ + rtx dest_addr; /* The canonical address of `dest'. */ +} modify_pair; + +DEF_VEC_O(modify_pair); +DEF_VEC_ALLOC_O(modify_pair,heap); + +/* This array parallels modify_mem_list, except that it stores MEMs + being set and their canonicalized memory addresses. */ +static VEC(modify_pair,heap) **canon_modify_mem_list; /* Bitmap indexed by block numbers to record which blocks contain function calls. */ @@ -478,7 +488,6 @@ static void invalidate_any_buried_refs (rtx); static void compute_ld_motion_mems (void); static void trim_ld_motion_mems (void); static void update_ld_motion_stores (struct expr *); -static void free_insn_expr_list_list (rtx *); static void clear_modify_mem_tables (void); static void free_modify_mem_tables (void); static rtx gcse_emit_move_after (rtx, rtx, rtx); @@ -587,7 +596,8 @@ alloc_gcse_mem (void) /* Allocate array to keep a list of insns which modify memory in each basic block. */ modify_mem_list = GCNEWVEC (rtx, last_basic_block); - canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block); + canon_modify_mem_list = GCNEWVEC (VEC(modify_pair,heap) *, + last_basic_block); modify_mem_list_set = BITMAP_ALLOC (NULL); blocks_with_calls = BITMAP_ALLOC (NULL); } @@ -1435,6 +1445,7 @@ canon_list_insert (rtx dest ATTRIBUTE_UNUSED, const_rtx unused1 ATTRIBUTE_UNUSED { rtx dest_addr, insn; int bb; + modify_pair *pair; while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == ZERO_EXTRACT @@ -1453,10 +1464,9 @@ canon_list_insert (rtx dest ATTRIBUTE_UNUSED, const_rtx unused1 ATTRIBUTE_UNUSED insn = (rtx) v_insn; bb = BLOCK_FOR_INSN (insn)->index; - canon_modify_mem_list[bb] = - alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]); - canon_modify_mem_list[bb] = - alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]); + pair = VEC_safe_push (modify_pair, heap, canon_modify_mem_list[bb], NULL); + pair->dest = dest; + pair->dest_addr = dest_addr; } /* Record memory modification information for INSN. We do not actually care @@ -1474,14 +1484,7 @@ record_last_mem_set_info (rtx insn) bitmap_set_bit (modify_mem_list_set, bb); if (CALL_P (insn)) - { - /* Note that traversals of this loop (other than for free-ing) - will break after encountering a CALL_INSN. So, there's no - need to insert a pair of items, as canon_list_insert does. */ - canon_modify_mem_list[bb] = - alloc_INSN_LIST (insn, canon_modify_mem_list[bb]); - bitmap_set_bit (blocks_with_calls, bb); - } + bitmap_set_bit (blocks_with_calls, bb); else note_stores (PATTERN (insn), canon_list_insert, (void*) insn); } @@ -1609,26 +1612,6 @@ compute_hash_table (struct hash_table_d *table) /* Expression tracking support. */ -/* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node - types may be mixed. */ - -static void -free_insn_expr_list_list (rtx *listp) -{ - rtx list, next; - - for (list = *listp; list ; list = next) - { - next = XEXP (list, 1); - if (GET_CODE (list) == EXPR_LIST) - free_EXPR_LIST_node (list); - else - free_INSN_LIST_node (list); - } - - *listp = NULL; -} - /* Clear canon_modify_mem_list and modify_mem_list tables. */ static void clear_modify_mem_tables (void) @@ -1639,7 +1622,7 @@ clear_modify_mem_tables (void) EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi) { free_INSN_LIST_list (modify_mem_list + i); - free_insn_expr_list_list (canon_modify_mem_list + i); + VEC_free (modify_pair, heap, canon_modify_mem_list[i]); } bitmap_clear (modify_mem_list_set); bitmap_clear (blocks_with_calls); @@ -1710,25 +1693,19 @@ compute_transp (const_rtx x, int indx, sbitmap *bmap) blocks_with_calls, 0, bb_index, bi) { - rtx list_entry = canon_modify_mem_list[bb_index]; + VEC(modify_pair,heap) *list + = canon_modify_mem_list[bb_index]; + modify_pair *pair; + unsigned ix; - while (list_entry) + FOR_EACH_VEC_ELT_REVERSE (modify_pair, list, ix, pair) { - rtx dest, dest_addr; - - /* LIST_ENTRY must be an INSN of some kind that sets memory. - Examine each hunk of memory that is modified. */ - - dest = XEXP (list_entry, 0); - list_entry = XEXP (list_entry, 1); - dest_addr = XEXP (list_entry, 0); + rtx dest = pair->dest; + rtx dest_addr = pair->dest_addr; if (canon_true_dependence (dest, GET_MODE (dest), dest_addr, x, NULL_RTX, rtx_addr_varies_p)) - { - RESET_BIT (bmap[bb_index], indx); - } - list_entry = XEXP (list_entry, 1); + RESET_BIT (bmap[bb_index], indx); } } }