From patchwork Tue Nov 17 22:01:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1401879 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=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=C2Y2qp/X; dkim-atps=neutral Received: from sourceware.org (unknown [8.43.85.97]) (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 4CbKfC0dzkz9s1l for ; Wed, 18 Nov 2020 09:01:36 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 746EE3973058; Tue, 17 Nov 2020 22:01:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 746EE3973058 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1605650492; bh=5hMoafJFbQV0uz7hSCM9pXPmisGEnwomQlc8mvBfwz0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=C2Y2qp/XZWsYONeW4D6VSGZH4N3opif1wEj5F2C4PvncaI94RCGHJ5J4HFgOu+zgJ J2BBFHEu7sBrNA/J7NXpteyDBIZ31npRTPLp2/OJ9WW2+LnI4Ce/f0bFbqJrJBS859 mO0o7yGaASGyjt9bQuAAy8oBgPVklCjCr/EVRGkM= 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 [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id A40FB386F427 for ; Tue, 17 Nov 2020 22:01:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org A40FB386F427 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-302-sRUu6UNKPmO-jxZ0AVM20Q-1; Tue, 17 Nov 2020 17:01:25 -0500 X-MC-Unique: sRUu6UNKPmO-jxZ0AVM20Q-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 307AE1075627 for ; Tue, 17 Nov 2020 22:01:24 +0000 (UTC) Received: from [10.10.118.73] (ovpn-118-73.rdu2.redhat.com [10.10.118.73]) by smtp.corp.redhat.com (Postfix) with ESMTP id 6C9F06EF44; Tue, 17 Nov 2020 22:01:23 +0000 (UTC) To: gcc-patches Subject: [PATCH] recognize implied ranges for modulo. Message-ID: Date: Tue, 17 Nov 2020 17:01:22 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" PR 91029 observes when  a % b > 0 && b >= 0, then a has an implied range of  a >=0.  likewise a % b < 0 implies a range of a <= 0. This patch is a good example of how range-ops can be leveraged to solve problems. It simply implements operator_trunc_mod::op1_range()  to solve for 'A' when the LHS and 'b' are known to be within the specified ranges.    I also added a a test case to show folding of conditions based on that. Bootstrapped on x86_64-pc-linux-gnu, no regressions.  pushed. Andrew commit 1e27e7a582a9b86bcf86f5c103cd947672746e97 Author: Andrew MacLeod Date: Tue Nov 17 14:47:58 2020 -0500 recognize implied ranges for modulo. implement op1_range for modulo with implied positive and negative ranges. gcc/ PR tree-optimization/91029 * range-op.cc (operator_trunc_mod::op1_range): New. gcc/testsuite/ * gcc.dg/pr91029.c: New. diff --git a/gcc/range-op.cc b/gcc/range-op.cc index d0adc95527a..f37796cac70 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -2634,6 +2634,9 @@ public: const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_trunc_mod; void @@ -2680,6 +2683,31 @@ operator_trunc_mod::wi_fold (irange &r, tree type, value_range_with_overflow (r, type, new_lb, new_ub); } +bool +operator_trunc_mod::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const +{ + // PR 91029. Check for signed truncation with op2 >= 0. + if (TYPE_SIGN (type) == SIGNED && wi::ge_p (op2.lower_bound (), 0, SIGNED)) + { + unsigned prec = TYPE_PRECISION (type); + // if a & b >=0 , then a >= 0. + if (wi::ge_p (lhs.lower_bound (), 0, SIGNED)) + { + r = value_range (type, wi::zero (prec), wi::max_value (prec, SIGNED)); + return true; + } + // if a & b < 0 , then a <= 0. + if (wi::lt_p (lhs.upper_bound (), 0, SIGNED)) + { + r = value_range (type, wi::min_value (prec, SIGNED), wi::zero (prec)); + return true; + } + } + return false; +} + class operator_logical_not : public range_operator { diff --git a/gcc/testsuite/gcc.dg/pr91029.c b/gcc/testsuite/gcc.dg/pr91029.c new file mode 100644 index 00000000000..8a4134c5d96 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr91029.c @@ -0,0 +1,47 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void kill (void); +int xx; + +void f1 (int i) +{ + if ((i % 7) == 3) + { + xx = (i < 0); + if (xx) + kill (); + } +} + +void f2 (int i) +{ + if ((i % 7) >= 0) + { + xx = (i < 0); + if (xx) + kill (); + } +} + +void f3 (int i) +{ + if ((i % 7) == -3) + { + xx = (i > 0); + if (xx) + kill (); + } +} + +void f4 (int i) +{ + if ((i % 7) < 0) + { + xx = (i > 0); + if (xx) + kill (); + } +} + +/* { dg-final { scan-tree-dump-not "kill" "evrp" } } */