From patchwork Fri Jul 8 03:20:04 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitrios Apostolou X-Patchwork-Id: 103751 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 83FA9B6F54 for ; Fri, 8 Jul 2011 13:20:32 +1000 (EST) Received: (qmail 19281 invoked by alias); 8 Jul 2011 03:20:29 -0000 Received: (qmail 19260 invoked by uid 22791); 8 Jul 2011 03:20:26 -0000 X-SWARE-Spam-Status: No, hits=-1.6 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, T_RP_MATCHES_RCVD, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mailout-de.gmx.net (HELO mailout-de.gmx.net) (213.165.64.23) by sourceware.org (qpsmtpd/0.43rc1) with SMTP; Fri, 08 Jul 2011 03:20:08 +0000 Received: (qmail invoked by alias); 08 Jul 2011 03:20:06 -0000 Received: from mon.egee-see.org (EHLO [139.91.70.93]) [139.91.70.93] by mail.gmx.net (mp003) with SMTP; 08 Jul 2011 05:20:06 +0200 Date: Fri, 8 Jul 2011 06:20:04 +0300 (EEST) From: Dimitrios Apostolou To: gcc-patches@gcc.gnu.org cc: Paolo Bonzini , Steven Bosscher Subject: [df-scan.c] Optimise DF_REFs ordering in collection_rec, use HARD_REG_SETs instead of bitmaps Message-ID: User-Agent: Alpine 2.02 (LNX 1266 2009-07-14) MIME-Version: 1.0 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 Hello list, The attached patch does two things for df_get_call_refs(): * First it uses HARD_REG_SETs for defs_generated and regs_invalidated_by_call, instead of bitmaps. Replacing in total more than 400K calls (for my testcase) to bitmap_bit_p() with the much faster TEST_HARD_REG_BIT, reduces the total instruction count from about 13M to 1.5M. * Second it produces the REFs in REGNO order, which is important to keep the collection_rec sorted most times, and avoid expensive calls to qsort(). Thanks to Paolo Bonzini for idea and mentoring. The second part makes a big difference if accompanied with another patch in df_insn_refs_collect(). I'll post a followup patch, that is unfortunately unstable for some of my tests, so I'd appreciate any comments. Thanks, Dimitris === modified file 'gcc/df-scan.c' --- gcc/df-scan.c 2011-02-02 20:08:06 +0000 +++ gcc/df-scan.c 2011-07-08 01:28:55 +0000 @@ -3317,20 +3317,56 @@ int flags) { rtx note; - bitmap_iterator bi; - unsigned int ui; bool is_sibling_call; unsigned int i; df_ref def; - bitmap_head defs_generated; + HARD_REG_SET defs_generated; - bitmap_initialize (&defs_generated, &df_bitmap_obstack); + CLEAR_HARD_REG_SET(defs_generated); /* Do not generate clobbers for registers that are the result of the call. This causes ordering problems in the chain building code depending on which def is seen first. */ FOR_EACH_VEC_ELT (df_ref, collection_rec->def_vec, i, def) - bitmap_set_bit (&defs_generated, DF_REF_REGNO (def)); + SET_HARD_REG_BIT (defs_generated, DF_REF_REGNO (def)); + + is_sibling_call = SIBLING_CALL_P (insn_info->insn); + + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { + if (i == STACK_POINTER_REGNUM) + /* The stack ptr is used (honorarily) by a CALL insn. */ + df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], + NULL, bb, insn_info, DF_REF_REG_USE, + DF_REF_CALL_STACK_USAGE | flags); + else if (global_regs[i]) + { + /* Calls to const functions cannot access any global registers and + calls to pure functions cannot set them. All other calls may + reference any of the global registers, so they are recorded as + used. */ + if (!RTL_CONST_CALL_P (insn_info->insn)) + { + df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], + NULL, bb, insn_info, DF_REF_REG_USE, flags); + if (!RTL_PURE_CALL_P (insn_info->insn)) + df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], + NULL, bb, insn_info, DF_REF_REG_DEF, flags); + } + } + /* TODO HARD_REG_SET set intersection! */ + else /* !global_regs[i] */ + /* track Caller-Saved registers */ + if (TEST_HARD_REG_BIT(regs_invalidated_by_call, i) + && !TEST_HARD_REG_BIT (defs_generated, i) + && (!is_sibling_call + || !bitmap_bit_p (df->exit_block_uses, i) + || refers_to_regno_p (i, i+1, + crtl->return_rtx, NULL))) + df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], + NULL, bb, insn_info, DF_REF_REG_DEF, + DF_REF_MAY_CLOBBER | flags); + } /* Record the registers used to pass arguments, and explicitly noted as clobbered. */ @@ -3345,7 +3381,7 @@ if (REG_P (XEXP (XEXP (note, 0), 0))) { unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0)); - if (!bitmap_bit_p (&defs_generated, regno)) + if (!TEST_HARD_REG_BIT (defs_generated, regno)) df_defs_record (collection_rec, XEXP (note, 0), bb, insn_info, flags); } @@ -3355,40 +3391,6 @@ } } - /* The stack ptr is used (honorarily) by a CALL insn. */ - df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[STACK_POINTER_REGNUM], - NULL, bb, insn_info, DF_REF_REG_USE, - DF_REF_CALL_STACK_USAGE | flags); - - /* Calls to const functions cannot access any global registers and calls to - pure functions cannot set them. All other calls may reference any of the - global registers, so they are recorded as used. */ - if (!RTL_CONST_CALL_P (insn_info->insn)) - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (global_regs[i]) - { - df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], - NULL, bb, insn_info, DF_REF_REG_USE, flags); - if (!RTL_PURE_CALL_P (insn_info->insn)) - df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], - NULL, bb, insn_info, DF_REF_REG_DEF, flags); - } - - is_sibling_call = SIBLING_CALL_P (insn_info->insn); - EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, ui, bi) - { - if (!global_regs[ui] - && (!bitmap_bit_p (&defs_generated, ui)) - && (!is_sibling_call - || !bitmap_bit_p (df->exit_block_uses, ui) - || refers_to_regno_p (ui, ui+1, - crtl->return_rtx, NULL))) - df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[ui], - NULL, bb, insn_info, DF_REF_REG_DEF, - DF_REF_MAY_CLOBBER | flags); - } - - bitmap_clear (&defs_generated); return; }