From patchwork Mon Nov 26 14:28:43 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 201704 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 6572D2C008C for ; Tue, 27 Nov 2012 01:29:05 +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=1354544946; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:Subject:Message-ID:MIME-Version:Content-Type: Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=XoHJMhxEuxVktcW62T751o2pYF8=; b=DVsRmT8Jk3qpD0E V3EoiUhrTq755y/AXVWEtA8/RfsmU1V7OMnJXwTp0/joq7mpa9EjRBXBHnFRGe3k 0B1CBIFUMG/D7wBt5biozDLjviGKsUb2PUkzZ+DjWGpqGcqnnLsbLwA3hEjRILj4 yjEvee4HGqcvCqwWpPVyUebJIwNQ= 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:Date:From:To:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=Te4vZAEDmZWnxLSAaCm6lA7EStbOlGgkzaqJSalAisBsAF6reCAjWVOogXM5bX J7shBhvwYoYBYofxf5h4cIr1+LkN2ab4g2aw6GuolNzTMoVBuNIPyxjB9dzcJq81 OLzx9GgVZeuo8uHfpeaXAasdE/GSTgv0ebMsukxmTXvEA=; Received: (qmail 18808 invoked by alias); 26 Nov 2012 14:28:59 -0000 Received: (qmail 18797 invoked by uid 22791); 26 Nov 2012 14:28:58 -0000 X-SWARE-Spam-Status: No, hits=-6.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, RCVD_IN_HOSTKARMA_W, RP_MATCHES_RCVD, SPF_HELO_PASS, TW_TX X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 26 Nov 2012 14:28:48 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id qAQESlUu015683 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 26 Nov 2012 09:28:47 -0500 Received: from redhat.com (ovpn-116-24.ams2.redhat.com [10.36.116.24]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id qAQESheL003905 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) for ; Mon, 26 Nov 2012 09:28:46 -0500 Date: Mon, 26 Nov 2012 15:28:43 +0100 From: Marek Polacek To: GCC Patches Subject: [PATCH] Don't bypass blocks with multiple latch edges (PR middle-end/54838) Message-ID: <20121126142843.GH17362@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) 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 In this PR, for the C testcase, in .cse1 we have: ENTRY | | 2 | | +-------- 4 ----------+ | / \ | | / \ | | 6 5 | | /\ |\ | | / \ | \ | | 7 3 | 8 | | | | | /\ / +---|----| | / \ / | --10 9/ | -/ EXIT-/ (3->4 and 9->4 are back edges). Now, in bypass_block, when we're trying to bypass BB 4, we iterate over BB 4's incoming edges, then we're iterating over reg_use_table (registers used in insn). Here we call set = find_bypass_set (regno, e->src->index); but since it returns non-NULL value, redirect_edge_and_branch_force later redirects edges and BB 4 is gone. We then end up with Redirecting fallthru edge 3->4 to 6 JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 1 [0x1]) Bypass edge from 3->4 to 6 Redirecting fallthru edge 9->4 to 5 JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3]) Bypass edge from 9->4 to 5 i.e., it is assumed that in one reg there "are" two constants, that can't be right, right?! I've tried to fix this by not redirecting edges (thus bypassing block) if BB has more incoming latch edges and the hash table has more different SRC rtxs with the same hash value. FWIW, the table looks like the below: SET hash table (11 buckets, 3 entries) Index 0 (hash value 4) (reg:SI 59 [ D.1735 ]) := (const_int 1 [0x1]) Index 1 (hash value 5) (reg/v/f:DI 60 [ b ]) := (const_int 0 [0]) Index 2 (hash value 4) (reg:SI 59 [ D.1735 ]) := (const_int 3 [0x3]) (Only not bypassing BB when it has more latch edges would work too, but I'm afraid it could pessimize stuff somewhere else.) I've also changed some zeros into NULLs for pointers. Also, as folowup, we could get rid of may_be_loop_header variable completely, at one place where it is used we can use just 'n_latches > 0'. And add the C++ TC as well. Regtested/bootstrapped on x86_64-linux, ok for trunk? 2012-11-26 Marek Polacek PR middle-end/54838 * cprop.c (only_one_const_p): New function. (find_bypass_set): New parameter. Conditionally call only_one_const_p. Use NULL instead of 0. (bypass_block): Adjust caller. Determine number of latch edges. (n_latches): New variable. * gcc.dg/pr54838.c: New test. Marek --- gcc/cprop.c.mp 2012-11-26 12:13:08.631193625 +0100 +++ gcc/cprop.c 2012-11-26 14:41:32.864034283 +0100 @@ -1429,14 +1429,26 @@ find_implicit_sets (void) static int bypass_last_basic_block; +/* Determine whether there is only one constant SRC rtx in the hash table + for REGNO. Here we assume that for the same hash value there won't be + more entries with the same SRC rtx. Return true if there is only one + constant, false otherwise. */ + +static bool +only_one_const_p (int regno) +{ + struct expr *set = lookup_set (regno, &set_hash_table); + return next_set (regno, set) == NULL; +} + /* Find a set of REGNO to a constant that is available at the end of basic block BB. Return NULL if no such set is found. Based heavily upon find_avail_set. */ static struct expr * -find_bypass_set (int regno, int bb) +find_bypass_set (int regno, int bb, bool multiple_latches) { - struct expr *result = 0; + struct expr *result = NULL; for (;;) { @@ -1450,9 +1462,15 @@ find_bypass_set (int regno, int bb) set = next_set (regno, set); } - if (set == 0) + if (set == NULL) break; + /* If there are more latch edges coming to the BB, we need to + make sure that for the same hash value there aren't + more constants. */ + if (multiple_latches && !only_one_const_p (regno)) + return NULL; + src = set->src; if (cprop_constant_p (src)) result = set; @@ -1502,6 +1520,7 @@ bypass_block (basic_block bb, rtx setcc, int may_be_loop_header; unsigned removed_p; unsigned i; + unsigned n_latches; edge_iterator ei; insn = (setcc != NULL) ? setcc : jump; @@ -1514,12 +1533,12 @@ bypass_block (basic_block bb, rtx setcc, find_used_regs (&XEXP (note, 0), NULL); may_be_loop_header = false; + n_latches = 0; FOR_EACH_EDGE (e, ei, bb->preds) if (e->flags & EDGE_DFS_BACK) - { - may_be_loop_header = true; - break; - } + n_latches++; + + may_be_loop_header = n_latches > 0; change = 0; for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) @@ -1557,7 +1576,7 @@ bypass_block (basic_block bb, rtx setcc, struct expr *set; rtx src, new_rtx; - set = find_bypass_set (regno, e->src->index); + set = find_bypass_set (regno, e->src->index, n_latches > 1); if (! set) continue; --- gcc/testsuite/gcc.dg/pr54838.c.mp 2012-11-26 14:48:43.783980854 +0100 +++ gcc/testsuite/gcc.dg/pr54838.c 2012-11-26 14:49:51.051158719 +0100 @@ -0,0 +1,24 @@ +/* PR middle-end/54838 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-forward-propagate -ftracer" } */ + +void bar (void); + +void +foo (void *b, int *c) +{ +again: + switch (*c) + { + case 1: + if (!b) + { + bar (); + return; + } + goto again; + case 3: + if (!b) + goto again; + } +}