From patchwork Wed Feb 4 06:11:03 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexandre Oliva X-Patchwork-Id: 436140 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 851D1140218 for ; Wed, 4 Feb 2015 17:11:42 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=pRP2AwbZSB+CdrgHOXivUnqSDl+xbtjQN15wJII/9jLac1IIOWOEP wsx9hWcyIZ8GZybcFFxiFm/pCnknXxPRrTmef2YwGw5aWXwFi4JjQHrIi9O9EJO8 Wv7uM/ySzpdHyH/zk5XQHvULNDHdhI2qnmxeHpWReZ8cGEjI2b4hDU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=HiZg3qd430kgH/vaAoIg+v0Ts3s=; b=fwY8ZbDcyqkJ0vxSzD/n xI0+5+MpS7WLkOH321FR3b/dJ5PdJTHJl58nqvFZ6N5gF+qPRx7/oWLz1JGhKx7a h+9LeVJRkVhU3+/x0J+tEDDzHZ9qQyUc1FCW6rYS6EpK4ZZyY/RoPrYMptemkwCI fshprca72IkLdXvuWH93M5w= Received: (qmail 11429 invoked by alias); 4 Feb 2015 06:11:13 -0000 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 Received: (qmail 11409 invoked by uid 89); 4 Feb 2015 06:11:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.9 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 04 Feb 2015 06:11:10 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id t146B9r9019214 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL) for ; Wed, 4 Feb 2015 01:11:09 -0500 Received: from freie.home (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t146B7Lj015152 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO) for ; Wed, 4 Feb 2015 01:11:08 -0500 Received: from livre.home (livre.home [172.31.160.2]) by freie.home (8.14.8/8.14.8) with ESMTP id t146B3oN022723; Wed, 4 Feb 2015 04:11:04 -0200 From: Alexandre Oliva To: gcc-patches@gcc.gnu.org Subject: [PR64817-related 2/3] don't alloc rtl when failing to simplify XOR of AND Date: Wed, 04 Feb 2015 04:11:03 -0200 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 We have a problem in simplify_binary_operation_1 that causes memory waste in general, and memory explosion in pathological testcases such as that of PR64817, with large exprs amounting to XOR of AND of XOR of AND of... I believe rtl simplifiers are not supposed to allocate rtl before committing to simplifying the expr at hand. The code that simplies XORs of ANDs, whose second operands are both constants, used to do this. In the pathological rtl resulting from the PR64817 testcases, the recursive attempts to simplify the large exprs with lots of such opportunities end up calling simplify_gen_unary O(2^n) times, where n is the number of XORs in the large expr, each call allocating memory that will ultimately not be used because simplification is not possible. This patch rearranges the simplification so as to avoid the early allocation. First, we attempt to simplify a negated variant of the temporary exprs we used to generate, that avoids the need for simplify_gen_unary and covers the second case in the simplification just as well as the original code. If we take the first case, however, even if the negated version failed to simplify, we know we can simplify the whole thing by combining the constants, so we negate the sub-expression simplified before, or create the non-negated sub-expression only if the negation of its operand simplifies successfully. This should cover all cases we covered before, but without allocating rtl before committing to a simplification. I made a cursory look at the other simplification paths and couldn't find any similar problem in them. This fixes the memory explosion problem in var-tracking exposed by the testcase in patch 1/3 of this series, as well as by the original PR64817 testcase with the fix in patch 1/3. Regstrapped on x86_64-linux-gnu and i686-pc-linux-gnu. Ok to install? for gcc/ChangeLog PR debug/64817 * simplify-rtx.c (simplify_binary_operation_1): Rewrite simplification of XOR of AND to not allocate new rtx before committing to a simplification. --- gcc/simplify-rtx.c | 29 ++++++++++++++++++++++++----- 1 file changed, 24 insertions(+), 5 deletions(-) diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c index 5c9e3bf..bea9ec3 100644 --- a/gcc/simplify-rtx.c +++ b/gcc/simplify-rtx.c @@ -2724,12 +2724,31 @@ simplify_binary_operation_1 (enum rtx_code code, machine_mode mode, HOST_WIDE_INT bval = INTVAL (b); HOST_WIDE_INT cval = INTVAL (c); - rtx na_c - = simplify_binary_operation (AND, mode, - simplify_gen_unary (NOT, mode, a, mode), - c); + /* Instead of computing ~A&C, we compute its negated value, + ~(A|~C). If it yields -1, ~A&C is zero, so we can + optimize for sure. If it does not simplify, we still try + to compute ~A&C below, but since that always allocates + RTL, we don't try that before committing to returning a + simplified expression. */ + rtx n_na_c = simplify_binary_operation (IOR, mode, a, + GEN_INT (~cval)); + if ((~cval & bval) == 0) { + rtx na_c = NULL_RTX; + if (n_na_c) + na_c = simplify_gen_unary (NOT, mode, n_na_c, mode); + else + { + /* If ~A does not simplify, don't bother: we don't + want to simplify 2 operations into 3, and if na_c + were to simplify with na, n_na_c would have + simplified as well. */ + rtx na = simplify_unary_operation (NOT, mode, a, mode); + if (na) + na_c = simplify_gen_binary (AND, mode, na, c); + } + /* Try to simplify ~A&C | ~B&C. */ if (na_c != NULL_RTX) return simplify_gen_binary (IOR, mode, na_c, @@ -2738,7 +2757,7 @@ simplify_binary_operation_1 (enum rtx_code code, machine_mode mode, else { /* If ~A&C is zero, simplify A&(~C&B) | ~B&C. */ - if (na_c == const0_rtx) + if (n_na_c == CONSTM1_RTX (mode)) { rtx a_nc_b = simplify_gen_binary (AND, mode, a, gen_int_mode (~cval & bval,