From patchwork Sun Nov 25 13:44:01 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Steven Bosscher X-Patchwork-Id: 201545 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 D08CC2C0040 for ; Mon, 26 Nov 2012 00:44:55 +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=1354455896; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: MIME-Version:Received:From:Date:Message-ID:Subject:To:Cc: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=VP45qgR vdpzNp3cEXH7JfP82Nhs=; b=bVL2SyCEbyBuqOPy00qcNbZNRjFiuNMU8dnD4JG PwuFfBHtbFIbUplIntx0/o1OYGtD05NsV55F0phr/p/YwB+e/vWGu6GY/z8/DGF8 QNZ+LJesY3Tgx542mJICSDcQkYfYJ6mZrptbw6ExGAFU/kZPylTlrfdGfhEIt3zF m0jw= 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:MIME-Version:Received:From:Date:Message-ID:Subject:To:Cc:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=xbYBZzzWA7sPCbvnlQ9+chFbvNxeMefrKN1WRjout/jJVGA8Mi3CQzbI+Su6pd wWoAlJYm4FZ5QOLqGTYMS7w8nInL7/x+1+cSGUPiZB52CNwYeGC739Q5GzKgsE4g 4x+Q/qgDr4VUH3M0L2B4MsGt5HbhkFzS8x1T3ahhJQEoM=; Received: (qmail 5325 invoked by alias); 25 Nov 2012 13:44:49 -0000 Received: (qmail 5314 invoked by uid 22791); 25 Nov 2012 13:44:48 -0000 X-SWARE-Spam-Status: No, hits=-4.4 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, TW_CF X-Spam-Check-By: sourceware.org Received: from mail-la0-f47.google.com (HELO mail-la0-f47.google.com) (209.85.215.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 25 Nov 2012 13:44:43 +0000 Received: by mail-la0-f47.google.com with SMTP id u2so7971614lag.20 for ; Sun, 25 Nov 2012 05:44:42 -0800 (PST) Received: by 10.152.132.3 with SMTP id oq3mr8149356lab.18.1353851082054; Sun, 25 Nov 2012 05:44:42 -0800 (PST) MIME-Version: 1.0 Received: by 10.112.88.99 with HTTP; Sun, 25 Nov 2012 05:44:01 -0800 (PST) From: Steven Bosscher Date: Sun, 25 Nov 2012 14:44:01 +0100 Message-ID: Subject: [patch] reorg.c janitor patch 3: remove rare_destination() To: GCC Patches Cc: Eric Botcazou 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, reorg.c:rare_destination() tries to determine whether a given insn is a likely destination of a branch. To make this determination, it walks the insns chain from insn and stops at barriers, labels, return insns, or if more than 10 jumps have been followed. The function is supposed to return 2 for noreturn calls, 1 for return, and 0 otherwise. But a quick experiment shows that the function doesn't work that way at all: 1. for all non-label, non-jump, non-barrier insns the function reaches the default case of the loop, which results in "return 1". 2. for labels, the function returns 0. 3. for most jump insns, the function returns 0, predicting jumps-to-jumps as likely -- but cfgcleanup has almost always already cleaned up such cases and the remaining jumps-to-jumps are usually not likely. 4. The combination of the above 3 points results in the fall-through path being predicted as a rare destination and the branch path as a more likely destination. It should be the other way around, if basic block reordering has done its job properly. 5. the only case that does work is the no-return call case, where the function stops at a BARRIER which must be for a no-return call because the function doesn't scan past jump insn (it follows jumps instead). However, this case is already handled in mostly_true_jump when it looks at REG_BR_PROB (which is a more reliable source of branch probabilities for all other cases as well). Given its apparent broken state and the better results reorg almost always gets in mostly_true_jump() from REG_BR_PROB or from determining that a jump goes forward or backward, I propose to remove rare_destination(). Built&tested a cross to mips-elf. OK for trunk? Ciao! Steven Index: reorg.c =================================================================== --- reorg.c (revision 193787) +++ reorg.c (working copy) @@ -187,7 +187,6 @@ static void note_delay_statistics (int, int); static rtx optimize_skip (rtx); #endif static int get_jump_flags (rtx, rtx); -static int rare_destination (rtx); static int mostly_true_jump (rtx, rtx); static rtx get_branch_condition (rtx, rtx); static int condition_dominates_p (rtx, rtx); @@ -905,54 +904,6 @@ get_jump_flags (rtx insn, rtx label) return flags; } -/* Return 1 if INSN is a destination that will be branched to rarely (the - return point of a function); return 2 if DEST will be branched to very - rarely (a call to a function that doesn't return). Otherwise, - return 0. */ - -static int -rare_destination (rtx insn) -{ - int jump_count = 0; - rtx next; - - for (; insn && !ANY_RETURN_P (insn); insn = next) - { - if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE) - insn = XVECEXP (PATTERN (insn), 0, 0); - - next = NEXT_INSN (insn); - - switch (GET_CODE (insn)) - { - case CODE_LABEL: - return 0; - case BARRIER: - /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We - don't scan past JUMP_INSNs, so any barrier we find here must - have been after a CALL_INSN and hence mean the call doesn't - return. */ - return 2; - case JUMP_INSN: - if (ANY_RETURN_P (PATTERN (insn))) - return 1; - else if (simplejump_p (insn) - && jump_count++ < 10) - next = JUMP_LABEL (insn); - else - return 0; - - default: - break; - } - } - - /* If we got here it means we hit the end of the function. So this - is an unlikely destination. */ - - return 1; -} - /* Return truth value of the statement that this branch is mostly taken. If we think that the branch is extremely likely to be taken, we return 2. If the branch is slightly more likely to be @@ -966,7 +918,6 @@ mostly_true_jump (rtx jump_insn, rtx condition) { rtx target_label = JUMP_LABEL (jump_insn); rtx note; - int rare_dest, rare_fallthrough; /* If branch probabilities are available, then use that number since it always gives a correct answer. */ @@ -985,25 +936,6 @@ mostly_true_jump (rtx jump_insn, rtx condition) return -1; } - /* Look at the relative rarities of the fallthrough and destination. If - they differ, we can predict the branch that way. */ - rare_dest = rare_destination (target_label); - rare_fallthrough = rare_destination (NEXT_INSN (jump_insn)); - - switch (rare_fallthrough - rare_dest) - { - case -2: - return -1; - case -1: - return 0; - case 0: - break; - case 1: - return 1; - case 2: - return 2; - } - /* If we couldn't figure out what this jump was, assume it won't be taken. This should be rare. */ if (condition == 0)