From patchwork Thu Jul 22 10:41:17 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1508632 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=uLL/pj2b; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=EWEqLgSi; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GVpsW3Y37z9sXJ for ; Thu, 22 Jul 2021 20:41:33 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2042C398A494 for ; Thu, 22 Jul 2021 10:41:31 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id EBC893858439 for ; Thu, 22 Jul 2021 10:41:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EBC893858439 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id BAC56225F6; Thu, 22 Jul 2021 10:41:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1626950477; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=5UQgExm3GIKZ2Q21Zoy+AuMXpFgnGhgfatx+yJRGsRs=; b=uLL/pj2bx4YgVCwkg9dEwXfPvpcwNorxIq36oSw0FMh+k4VeGF+OHLIWv1UmvC9Iwal45q YLAGPXpFn4sCLotDnfb/Ph2/T3JpGlLhMoOiX+Fh2AImWrOl49vwLdl95j8G3dn4TIRIhC fY73MiiFcSZOf+Yk2BttTnLHWaRoCcc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1626950477; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=5UQgExm3GIKZ2Q21Zoy+AuMXpFgnGhgfatx+yJRGsRs=; b=EWEqLgSi2WM9K4j+DANBguvtL4L/5Yx8RUjV+DLRpJ6LzA28fnDgBahyiTyacMA2Tk0DIX NbPr0xqc5M4P/AAg== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id A172A13DC1; Thu, 22 Jul 2021 10:41:17 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id /JI8Jk1L+WApFQAAMHmgww (envelope-from ); Thu, 22 Jul 2021 10:41:17 +0000 Date: Thu, 22 Jul 2021 12:41:17 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][RFC] tree-optimization/100499 - multiple_of_p bad behavior wrt niter analysis Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, 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: , Cc: bin.cheng@linux.alibaba.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This avoids using multiple_of_p in niter analysis when its behavior to assume the tested expression does not invoke integer overflow produces wrong niter analysis results. For the cases multiple_of_p handles power-of-two values of bottom look safe which should also be the majority of cases we care about in addition to the constant case now handled explicitely. Bootstrapped and tested on x86_64-unknown-linux-gnu. I'm unsure how important a "perfect" solution is (rewriting multiple_of_p), and wonder whether this solution is preferable for now (and especially for branches). I've not yet tried to sanitize multiple_of_p plus use range info to prove no-overflow where TYPE_OVERFLOW_UNDEFINED doesn't tell us immediately. 2021-07-22 Richard Biener PR tree-optimization/100499 * tree-ssa-loop-niter.c (number_of_iterations_ne): Restrict multiple_of_p queries to power-of-two bottoms, handle the all constant case inline. * gcc.dg/torture/pr100499-1.c: New testcase. * gcc.dg/torture/pr100499-2.c: Likewise. --- gcc/testsuite/gcc.dg/torture/pr100499-1.c | 28 +++++++++++++++++++++++ gcc/testsuite/gcc.dg/torture/pr100499-2.c | 16 +++++++++++++ gcc/tree-ssa-loop-niter.c | 8 ++++++- 3 files changed, 51 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-1.c create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-2.c diff --git a/gcc/testsuite/gcc.dg/torture/pr100499-1.c b/gcc/testsuite/gcc.dg/torture/pr100499-1.c new file mode 100644 index 00000000000..97ab6051554 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr100499-1.c @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int32plus } */ + +typedef __UINT16_TYPE__ uint16_t; +static uint16_t g_2823 = 0xEC75L; +static uint16_t g_116 = 0xBC07L; + +static uint16_t +safe_mul_func_uint16_t_u_u(uint16_t ui1, uint16_t ui2) +{ + return ((unsigned int)ui1) * ((unsigned int)ui2); +} + +int main (int argc, char* argv[]) +{ + uint16_t l_2815 = 65535UL; + uint16_t *l_2821 = &g_116; + uint16_t *l_2822 = &g_2823; + +lbl_2826: + l_2815 &= 0x9DEF1EAEL; + if (+(safe_mul_func_uint16_t_u_u(((*l_2821) = l_2815), (--(*l_2822))))) + goto lbl_2826; + + if (g_2823 != 32768) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/torture/pr100499-2.c b/gcc/testsuite/gcc.dg/torture/pr100499-2.c new file mode 100644 index 00000000000..999f931806a --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr100499-2.c @@ -0,0 +1,16 @@ +/* { dg-do run } */ + +unsigned char ag = 55; +unsigned i; +int main() +{ + unsigned char c; + unsigned char a = ag; +d: + c = a-- * 52; + if (c) + goto d; + if (a != 255) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 1b5605c26b8..c6b953c5316 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1050,7 +1050,13 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv, Note, for NE_EXPR, base equals to FINAL is a special case, in which the loop exits immediately, and the iv does not overflow. */ if (!niter->control.no_overflow - && (integer_onep (s) || multiple_of_p (type, c, s))) + && (integer_onep (s) + || (poly_int_tree_p (c) + && multiple_p (wi::to_poly_widest (c), wi::to_poly_widest (s))) + /* ??? multiple_of_p assumes the expression 'c' does not overflow + but that cannot be guaranteed, so we restrict 's' to power of + two values where that should not be an issue. See PR100499. */ + || (integer_pow2p (s) && multiple_of_p (type, c, s)))) { tree t, cond, new_c, relaxed_cond = boolean_false_node;