From patchwork Wed Jun 16 15:56:54 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maxim Kuvyrkov X-Patchwork-Id: 55903 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 258101007D2 for ; Thu, 17 Jun 2010 01:57:05 +1000 (EST) Received: (qmail 18659 invoked by alias); 16 Jun 2010 15:57:04 -0000 Received: (qmail 18648 invoked by uid 22791); 16 Jun 2010 15:57:03 -0000 X-SWARE-Spam-Status: No, hits=-2.0 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; Wed, 16 Jun 2010 15:56:58 +0000 Received: (qmail 20966 invoked from network); 16 Jun 2010 15:56:56 -0000 Received: from unknown (HELO ?172.16.1.24?) (maxim@127.0.0.2) by mail.codesourcery.com with ESMTPA; 16 Jun 2010 15:56:56 -0000 Message-ID: <4C18F446.20508@codesourcery.com> Date: Wed, 16 Jun 2010 19:56:54 +0400 From: Maxim Kuvyrkov User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.1.9) Gecko/20100317 Thunderbird/3.0.4 MIME-Version: 1.0 To: Jeff Law , gcc-patches Subject: 0003-Improve-VBEout-computation.patch References: <4C18F225.2040509@codesourcery.com> In-Reply-To: <4C18F225.2040509@codesourcery.com> 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 Code hoisting algorithm from Muchnick, which is the one implemented in GCC, has a quirk in that it does include expressions calculated in basic block in its VBEout set. This seems odd to me; if an expression is calculated in BB and is available at BB's end, then we do want to hoist expressions from BB's successors to the end of BB. This patch implements this. The patch also adds an open-ended comment which describes another possible improvement to the algorithm. OK to apply? Thank you, diff --git a/gcc/gcse.c b/gcc/gcse.c index 00f3841..74986a4 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -4171,13 +4171,52 @@ compute_code_hoist_vbeinout (void) FOR_EACH_BB_REVERSE (bb) { if (bb->next_bb != EXIT_BLOCK_PTR) - sbitmap_intersection_of_succs (hoist_vbeout[bb->index], - hoist_vbein, bb->index); + { + /* ??? Code hoisting algorithm from Muchnick seems to be + overly conservative in considering only those expressions + that are calculated along every path from BB. + E.g., it will not try to optimize the following case: + + 2 + | \ + 3* | + | / + 4 + / \ + 5* 6 + + ;; "*" marks basic blocks that calculate same expression + ;; Ideally, all calculation would be moved to block 2. + + One way to improve the algorith can be to exclude + certain edges from intersection of successors' hoist_vbein's. + + E.g., if a basic block has a fallthru edge that the control + takes with >80% probability, then just copy hoist_vbein + of the destination block to hoist_vbeout of BB. */ + sbitmap_intersection_of_succs (hoist_vbeout[bb->index], + hoist_vbein, bb->index); + + /* ??? Another quirk of Muchnick is that vbeout[BB] does not + include expressions calculated in BB itself and available + at its end. Fix this. */ + sbitmap_a_or_b (hoist_vbeout[bb->index], + hoist_vbeout[bb->index], comp[bb->index]); + } changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index], hoist_vbeout[bb->index], transp[bb->index]); + + /* Enable if debugging VBE data flow problem. */ + if (dump_file && 0) + { + fprintf (dump_file, "vbein (%d): ", bb->index); + dump_sbitmap_file (dump_file, hoist_vbein[bb->index]); + fprintf (dump_file, "vbeout(%d): ", bb->index); + dump_sbitmap_file (dump_file, hoist_vbeout[bb->index]); + } } passes++; @@ -4298,6 +4337,11 @@ hoist_code (void) if (TEST_BIT (hoist_vbeout[bb->index], i) && TEST_BIT (transpout[bb->index], i)) { + /* If an expression is computed in BB and is available at end of + BB, hoist all occurences dominated by BB to BB. */ + if (TEST_BIT (comp[bb->index], i)) + hoistable++; + /* We've found a potentially hoistable expression, now we look at every block BB dominates to see if it computes the expression. */