From patchwork Tue Nov 30 09:26:13 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 48274 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 502BD385C40B for ; Tue, 30 Nov 2021 09:26:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 502BD385C40B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638264410; bh=s0FEXVoRDFo0Zh0ObvUJ4EIx6iBs9aqkH/WmjXoPBYE=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=OXIT8r9bpiDNOdGlAchdcY9V1KqRZQMXcjIoJMjOI5Bu3sJ/yRzBR8Nzw9d8PaZq7 hzL+vR3gytftHI9Wb12aBp8BSZ5vxJP3GDoTqFfObyOaqBq5CXJJ0FNV7gu2SoAn6L 8EPBQ63JBkn4kbf8skcL9JjRno+1zWHkmn+JsSe8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id B66493857C63 for ; Tue, 30 Nov 2021 09:26:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B66493857C63 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-554-ER0WVk-1NdmcpB1mBBvnaQ-1; Tue, 30 Nov 2021 04:26:18 -0500 X-MC-Unique: ER0WVk-1NdmcpB1mBBvnaQ-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 181AE1B2C996; Tue, 30 Nov 2021 09:26:18 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.194.188]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 9F72610013D6; Tue, 30 Nov 2021 09:26:17 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.16.1/8.16.1) with ESMTPS id 1AU9QESQ2926105 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 30 Nov 2021 10:26:15 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.16.1/8.16.1/Submit) id 1AU9QDXN2926104; Tue, 30 Nov 2021 10:26:13 +0100 Date: Tue, 30 Nov 2021 10:26:13 +0100 To: Richard Biener Subject: [PATCH] simplify-rtx: Punt on simplify_associative_operation with large operands [PR102356] Message-ID: <20211130092613.GL2646553@tucnak> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-5.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jakub Jelinek via Gcc-patches From: Jakub Jelinek Reply-To: Jakub Jelinek Cc: gcc-patches@gcc.gnu.org Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hi! Seems simplify_associate_operation is quadratic, which isn't a big deal for use during combine and other similar RTL passes, because those never try to combine expressions from more than a few instructions and because those instructions need to be recognized the machine description also bounds how many expressions can appear in there. var-tracking has depth limits only for some cases and unlimited depth for the vt_expand_loc though: /* This is the value used during expansion of locations. We want it to be unbounded, so that variables expanded deep in a recursion nest are fully evaluated, so that their values are cached correctly. We avoid recursion cycles through other means, and we don't unshare RTL, so excess complexity is not a problem. */ #define EXPR_DEPTH (INT_MAX) /* We use this to keep too-complex expressions from being emitted as location notes, and then to debug information. Users can trade compile time for ridiculously complex expressions, although they're seldom useful, and they may often have to be discarded as not representable anyway. */ #define EXPR_USE_DEPTH (param_max_vartrack_expr_depth) IMO for very large expressions it isn't worth trying to reassociate though, in fact e.g. for the new testcase below keeping it as is has bigger chance of generating smaller debug info which the dwarf2out.c part of the change tries to achieve - if a binary operation has the same operands, we can use DW_OP_dup and not bother computing the possibly large operand again. This patch punts if the associate operands contain together more than 64 same operations, which can happen only during var-tracking. During bootstrap/regtest on x86_64-linux and i686-linux, this triggers only on the new testcase and on gcc.dg/torture/pr88597.c. I think given the 16 element static buffer in subrtx_iterator::array_type it shouldn't slow down the common case of small expressions, but have been wondering whether we shouldn't have some in_vartrack global flag or guard it with (current_pass && strcmp (current_pass->name, "vartrack") == 0). Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? Another possibility to deal with the power expressions in debug info would be to introduce some new RTL operation for the pow{,i} (x, n) case, allow that solely in debug insns and expand those into DWARF using a loop. But that seems like quite a lot of work for something rarely used (especially when powi for larger n is only useful for 0 and 1 inputs because anything else overflows). 2021-11-30 Jakub Jelinek PR rtl-optimization/102356 * simplify-rtx.c: Include rtl-iter.h. (simplify_associative_operation): Don't reassociate very large expressions with 64 or more CODE subrtxes in the operands. * dwarf2out.c (mem_loc_descriptor): Optimize binary operation with both operands the same using DW_OP_dup. * gcc.dg/pr102356.c: New test. Jakub --- gcc/simplify-rtx.c.jj 2021-11-05 00:43:22.576624649 +0100 +++ gcc/simplify-rtx.c 2021-11-29 19:46:29.674750656 +0100 @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. #include "selftest-rtl.h" #include "rtx-vector-builder.h" #include "rtlanal.h" +#include "rtl-iter.h" /* Simplification and canonicalization of RTL. */ @@ -2263,9 +2264,40 @@ simplify_context::simplify_associative_o { rtx tem; + if (GET_CODE (op0) == code || GET_CODE (op1) == code) + { + /* During vartrack, the expressions can grow arbitrarily large. + Reassociation isn't really useful for larger expressions + and can be very compile time expensive. */ + unsigned count = 0; + subrtx_iterator::array_type array; + FOR_EACH_SUBRTX (iter, array, op0, NONCONST) + { + const_rtx x = *iter; + if (GET_CODE (x) == code) + { + if (count++ >= 64) + return NULL_RTX; + } + else + iter.skip_subrtxes (); + } + FOR_EACH_SUBRTX (iter, array, op1, NONCONST) + { + const_rtx x = *iter; + if (GET_CODE (x) == code) + { + if (count++ >= 64) + return NULL_RTX; + } + else + iter.skip_subrtxes (); + } + } + /* Linearize the operator to the left. */ if (GET_CODE (op1) == code) { /* "(a op b) op (c op d)" becomes "((a op b) op c) op d)". */ if (GET_CODE (op0) == code) { --- gcc/dwarf2out.c.jj 2021-11-29 14:24:14.053634713 +0100 +++ gcc/dwarf2out.c 2021-11-29 19:44:54.192113401 +0100 @@ -16363,6 +16363,15 @@ mem_loc_descriptor (rtx rtl, machine_mod do_binop: op0 = mem_loc_descriptor (XEXP (rtl, 0), mode, mem_mode, VAR_INIT_STATUS_INITIALIZED); + if (XEXP (rtl, 0) == XEXP (rtl, 1)) + { + if (op0 == 0) + break; + mem_loc_result = op0; + add_loc_descr (&mem_loc_result, new_loc_descr (DW_OP_dup, 0, 0)); + add_loc_descr (&mem_loc_result, new_loc_descr (op, 0, 0)); + break; + } op1 = mem_loc_descriptor (XEXP (rtl, 1), mode, mem_mode, VAR_INIT_STATUS_INITIALIZED); --- gcc/testsuite/gcc.dg/pr102356.c.jj 2021-11-29 19:57:47.061075856 +0100 +++ gcc/testsuite/gcc.dg/pr102356.c 2021-11-29 19:57:26.852364489 +0100 @@ -0,0 +1,33 @@ +/* PR rtl-optimization/102356 */ +/* { dg-do compile { target int32plus } } */ +/* { dg-options "-O3 -g" } */ + +signed char a = 0; +unsigned char b = 9; +unsigned long long c = 0xF1FBFC17225F7A57ULL; +int d = 0x3A6667C6; + +unsigned char +foo (unsigned int x) +{ + unsigned int *e = &x; + if ((c /= ((0 * (*e *= b)) <= 0))) + ; + for (d = 9; d > 2; d -= 2) + { + c = -2; + do + if ((*e *= *e)) + { + a = 4; + do + { + a -= 3; + if ((*e *= *e)) + b = 9; + } + while (a > 2); + } + while (c++); + } +}