From patchwork Fri Nov 3 17:14:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 161373 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:8f47:0:b0:403:3b70:6f57 with SMTP id j7csp1193653vqu; Fri, 3 Nov 2023 10:15:02 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEYEOZNOlFfh0lMAdIUrmAbEfc7z736OFW43pyqdqsh4VlXFsjQh1EjyA0UCzVxyUR2bCD0 X-Received: by 2002:a05:6214:1313:b0:656:4712:af9f with SMTP id pn19-20020a056214131300b006564712af9fmr30804653qvb.13.1699031702047; Fri, 03 Nov 2023 10:15:02 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1699031702; cv=pass; d=google.com; s=arc-20160816; b=no/+q5of8dyOd13UuNV9x10KMCV/Yb0LSEN03b4/gBySC2a3SB6y13g1egwzp9Rb9w 9g9fjVSTZEVTgA5vnqzFhl8rE4TbX4KaVzcDpCb3JdByOTXrq+PRXSFqxLRCHcUpCrs4 FuwCIcXhGbGCVlB2qBmrjFfZZhMeAHUA2tWyUeZI+QFGeIvMWIIutZrWqOrIES1UQham xXVqgUSP7WulOQ/RnUAlTt0PrvFLxxl3x8Yk5B9/bo67quPceLMAyjki1SVIUBCLYKSi QBADlSddu+107aeiCgpBIx2PoTYFrSJ3dNN4DZI83+q70qrAMN8wwcA6vVX6M0dFvS/H 38sQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-language:cc:to:subject :from:user-agent:mime-version:date:message-id:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=fq4wYQhUTE4dY8E5JFCTVPK6n+99rI1wwEp2uVVUqdw=; fh=ZE6EPE2PZ3ED3Eq5R4AB8kSxxMSuW2qQfXnHfqWWl4c=; b=D6LCIh9CIby3YcY/HP8NmiFcjiVNosgp+kJcIXRcYeIUwk3Ipo6GKZEnnwI39e6/sK k9LjOo9sI+AkVv7RR+3gPHCWrFg7PFzlPpcdm8YJ1/JgFT0aXdoDta7CJFx2OQ65R87v vy5hlqM7i8hUQT3iZsuFlHSzlbdIEsSlGgyXG4POzAbmK/RR3yv6+CKaeLSPjFE2OIle sL8i0RJdOH6hLqUo32ELvr1Jo12koBqbGSg9QnffsiAhqjfWTTwSWFjTR6Ud5qzjJXuH 0d4s1y38kRIPer1y35TIXZcn9wmjJERozMFnvrik7szEedIs71FMZ093N+pBOCCZ8ovJ coNw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b="N/kUg73i"; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id t17-20020a0cea31000000b0066cf06339basi1755700qvp.234.2023.11.03.10.15.01 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 03 Nov 2023 10:15:02 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b="N/kUg73i"; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6E8223858C01 for ; Fri, 3 Nov 2023 17:14:59 +0000 (GMT) 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 B402D3858281 for ; Fri, 3 Nov 2023 17:14:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B402D3858281 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org B402D3858281 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699031674; cv=none; b=MPAyGWNRdD9t2ENxpsfMOnVH5UUxKr5bgaMEqQ8n5CInpsQRr+MXs+X6J4RRJB6E2Rb7IG8TE5+Ew+cerKRrynf89vV014WRSyrIu9TUStc4qUznn22CspkMotYzRtYvuVHJMMwt6MqYxRMTVMQDC5kCxHnGTmt8PfYdSR50YeY= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699031674; c=relaxed/simple; bh=dzTmfHduYH8j0JfMd28DCa16ynB/YVaG6hofHqOv7lo=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=M5W0J3ZsGPpg+yhf40UdM3/+WM/bho7J5Mcw4v23h/m8p6YDVQ1lD2uiRKjiaCVk6d6Tg41wGHQ6lp24muuQC9LE1rzXYBQ/x3MrtHgbNZnNExLGxjS0FScBxfDeNYBIx2SZsmbrNLBHOd+GyYfM9zoPFXSO3J8fa1VR13MLa/s= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1699031664; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=fq4wYQhUTE4dY8E5JFCTVPK6n+99rI1wwEp2uVVUqdw=; b=N/kUg73iK2vlbdY2olPIFGTUkCpoPDsmE8/2cfzw76XOowbmwT3NaApMmgAEHLCu9hu/eV NTaAvM+97iNe2KhH9vkLOWw8PkElQzHTO4DVOdyaIY0rBidJn6j4t1vy31lefMT3mYIcsG 9+DsaOAyViaJU2lxYkFte9pDBUhbw8k= Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-662-JAMReFgZMC2DbzhwxAq74w-1; Fri, 03 Nov 2023 13:14:22 -0400 X-MC-Unique: JAMReFgZMC2DbzhwxAq74w-1 Received: by mail-qk1-f198.google.com with SMTP id af79cd13be357-7788fa5f1b0so237770185a.2 for ; Fri, 03 Nov 2023 10:14:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699031661; x=1699636461; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ObEiCN69fpuWatiqaUMsH0pf5cEjCD2S0KLjJLFsM9E=; b=PD5j3+zzNtIIsJB0v7pCUkF13A99FilrfsnMDG3AdNs0H/oM3hCXSOrziACXs2ikF8 C90NXreY33edJiiW09i014o3V9+mCEinIhKRlX9tyjZq8DpdCX0JApTuiP3oR8F9XFQn 8ibPE+C2Rv2s4h9jk/oAuuNm1BXMc84fPPhTMfO5ldzVEu9AV1jnWOk7MpxgW61hOBjr N8XqpCTocZjfsD64LCkq7Mi5dA4virMSdtiuYAi5WCl60neasgn8pXucSCtslyUr/Ib6 4OddF0w1iG3LuIak0jkb1oo5FjNRZG/e/PM1Ee73LP51MNfgJthfi2AiPa8TSxY+Y35v tCcg== X-Gm-Message-State: AOJu0YzUaPGN4NVAAjqZcVejqADoYzoMjPGlWiYC4CsXGCnmnSJWykjY n0Fotln+ylezIQSp67cfoiJCwgE3Ex6hJiDpBkue3+klAX53ix4SrCHIFumJG4J8MK9A/5jKDgr 3Hz9E5awditCJA4oIdSwIN9fxcDKJn/tiUpcGNowF3DRaxFXSuQVzjwcpeTdQ8y8ZX15hFAB8/1 ocGA== X-Received: by 2002:a37:c24a:0:b0:775:9c99:122e with SMTP id j10-20020a37c24a000000b007759c99122emr20292458qkm.71.1699031661325; Fri, 03 Nov 2023 10:14:21 -0700 (PDT) X-Received: by 2002:a37:c24a:0:b0:775:9c99:122e with SMTP id j10-20020a37c24a000000b007759c99122emr20292433qkm.71.1699031660890; Fri, 03 Nov 2023 10:14:20 -0700 (PDT) Received: from ?IPV6:2607:fea8:51dd:2b00::18c7? ([2607:fea8:51dd:2b00::18c7]) by smtp.gmail.com with ESMTPSA id j22-20020a05620a411600b0077402573fb4sm886248qko.124.2023.11.03.10.14.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Nov 2023 10:14:20 -0700 (PDT) Message-ID: <14b069dc-711f-4643-97a0-b64142017f24@redhat.com> Date: Fri, 3 Nov 2023 13:14:19 -0400 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: Andrew MacLeod Subject: [COMMITTED 1/2] Remove simple ranges from trailing zero bitmasks. To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.7 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_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1781563866097699414 X-GMAIL-MSGID: 1781563866097699414 WHen we set bitmasks indicating known zero or one bits, we see some "obvious" things once in a while that are easy to prevent. ie unsigned int [2, +INF] MASK 0xfffffffe VALUE 0x1 the range [2, 2] is obviously impossible since the final bit must be a one.   This doesn't usually cause us too much trouble, but the subsequent patch triggers some more interesting situations in which it helps to remove the obvious ranges when we have  mask that is trailing zeros. Its too much of a performance impact to constantly be checking the range every time we set the bitmask, but it turns out that if we simply try to take care of it during intersection operations (which happen at most key times, like changing an existing value), the impact is pretty minimal.. like 0.6% of VRP. This patch looks for trailing zeros in the mask, and replaces the low end range covered by those bits with those bits from the value field. Bootstraps on build-x86_64-pc-linux-gnu with no regressions. Pushed. Andrew From b20f1dce46fb8bb1b142e9087530e546a40edec8 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 31 Oct 2023 11:51:34 -0400 Subject: [PATCH 1/2] Remove simple ranges from trailing zero bitmasks. During the intersection operation, it can be helpful to remove any low-end ranges when the bitmask has trailing zeros. This prevents obviously incorrect ranges from appearing without requiring a bitmask check. * value-range.cc (irange_bitmask::adjust_range): New. (irange::intersect_bitmask): Call adjust_range. * value-range.h (irange_bitmask::adjust_range): New prototype. --- gcc/value-range.cc | 30 ++++++++++++++++++++++++++++++ gcc/value-range.h | 2 ++ 2 files changed, 32 insertions(+) diff --git a/gcc/value-range.cc b/gcc/value-range.cc index fcf53efa1dd..a1e72c78f8b 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1857,6 +1857,35 @@ irange::get_bitmask_from_range () const return irange_bitmask (wi::zero (prec), min | xorv); } +// Remove trailing ranges that this bitmask indicates can't exist. + +void +irange_bitmask::adjust_range (irange &r) const +{ + if (unknown_p () || r.undefined_p ()) + return; + + int_range_max range; + tree type = r.type (); + int prec = TYPE_PRECISION (type); + // If there are trailing zeros, create a range representing those bits. + gcc_checking_assert (m_mask != 0); + int z = wi::ctz (m_mask); + if (z) + { + wide_int ub = (wi::one (prec) << z) - 1; + range = int_range<5> (type, wi::zero (prec), ub); + // Then remove the specific value these bits contain from the range. + wide_int value = m_value & ub; + range.intersect (int_range<2> (type, value, value, VR_ANTI_RANGE)); + // Inverting produces a list of ranges which can be valid. + range.invert (); + // And finally select R from only those valid values. + r.intersect (range); + return; + } +} + // If the the mask can be trivially converted to a range, do so and // return TRUE. @@ -2002,6 +2031,7 @@ irange::intersect_bitmask (const irange &r) if (!set_range_from_bitmask ()) normalize_kind (); + m_bitmask.adjust_range (*this); if (flag_checking) verify_range (); return true; diff --git a/gcc/value-range.h b/gcc/value-range.h index e9d81d22cd0..84f65ffb591 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -139,6 +139,8 @@ public: void verify_mask () const; void dump (FILE *) const; + void adjust_range (irange &r) const; + // Convenience functions for nonzero bitmask compatibility. wide_int get_nonzero_bits () const; void set_nonzero_bits (const wide_int &bits); -- 2.41.0 From patchwork Fri Nov 3 17:14:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 161374 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:8f47:0:b0:403:3b70:6f57 with SMTP id j7csp1193834vqu; Fri, 3 Nov 2023 10:15:16 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHOVDPquF/ABydYophRKddlcotS9fVtFr1DLP82vc4zz1sXI+jYqaU0C0mbEO9G4HULzCcs X-Received: by 2002:ac8:5d88:0:b0:41c:dc6c:c86f with SMTP id d8-20020ac85d88000000b0041cdc6cc86fmr27957319qtx.47.1699031716317; Fri, 03 Nov 2023 10:15:16 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1699031716; cv=pass; d=google.com; s=arc-20160816; b=hl+TWRwwkm+xpBg2XNMlnpSRVTQ6mZ5t1B0xumg8dFrNZRAbVxE4fv4t0Tf/3/V4De vpzEarmmLT5EInyxVvJ+/dx8yUdbAd3HBXXPH0OrKd0e9RCTF681aKC5a720UfnchSLl VzdcrxLyDBHhGY6qpqFf+rzJCTOdT30AbVOVzp4TKs2Y+bCVhMqRLE8oT2WNkPd2oUmT ezuIIcCe+pZMP6fsjiseGIuxYU4conQypvkux9bWPCPiqQqx85ymTTOAleKKLE3aIC/t kxf9vopeaMGafvWDxpVDqi1duKT6QbrLzpa74UQzkNtURxuNkVEjmBJ5DclVS9+lS0i3 z3JA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-language:cc:to:subject :from:user-agent:mime-version:date:message-id:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=uZhAN9qvyXMebYefkzUkyAXx5B9fgNwxa4/umc+ZRoM=; fh=ZE6EPE2PZ3ED3Eq5R4AB8kSxxMSuW2qQfXnHfqWWl4c=; b=bHtutjywa2cYGTMm9p5dPrueiiB7Ehml2jysnRduFjJiUP012PIsjh/CaEfa7SrUe4 rnatcM+IW6V6MLeWdnK36KJe5mdzwCTGch8GS5M3SzeI15swezd/7ssoP1g8J4iT499x LbV/5ZiwKWy5HBvQRZQiZDx0xPVIIroJeBu3maiJK+RQ2rpGGCfi48gJq8YsOmsatbyf 1gUSMQcVLVENiKqJdSgtCZXu2ZDkDAdrUCsTjzco6veWhpOtt/vVFnlOb0MmphM6KzV/ 9Lx+WjHUvShEMZrzLAyfMCGCxdNr6b4Z5eJ2uPMdajB4eAXJPGTKOth/yrh23ejQtAc0 ISxw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=Oyhg8Z0Q; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id g16-20020ac85d50000000b004196484117esi1847559qtx.73.2023.11.03.10.15.16 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 03 Nov 2023 10:15:16 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=Oyhg8Z0Q; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A80ED3857715 for ; Fri, 3 Nov 2023 17:15:12 +0000 (GMT) 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 363333858C00 for ; Fri, 3 Nov 2023 17:14:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 363333858C00 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 363333858C00 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699031687; cv=none; b=heu0TGX0d2aPdSd92sGJPPl7EWPGlY7X0G5tOHCdrZjOTFonKnXq0IREhsxPHY2JZnArZbkICuI33ZTal3ssAO9XPNGm8kULMtJOrCswIuWHr1MypKA9fdA9IgJr0Wj0Tbq4bJZOd7hR61pSlr91aCn1JkQiV8K4vLb5I8J0VMk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699031687; c=relaxed/simple; bh=nYbtsTE5ceH2AOJ+WupxNRsohRUujpRrFXU0C6E6e/Q=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=qwBjfLf6+2tcsGYP4sXFwE7sAd7o/lhXld+ZkWxOoQJqC1tSg9MRJUdcWWvUbNMCHh3l/2kYOBDfMR/L5b/ziJLXF3AwtHw4YUUAa71iDOP5xWqNl0rnHg5sdl+5wz0x7Zf74Id43bx7a+AjjhKl3P5ujbTw4FFFOf3L9XNpixE= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1699031676; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=uZhAN9qvyXMebYefkzUkyAXx5B9fgNwxa4/umc+ZRoM=; b=Oyhg8Z0QMlK1FJ3cBW7SHbTDRyjkIrGViOQVkTi2SAO/KeM/arAzMvzFoz6TZx5Bex3jk1 dS32K13CMW3/sU9BN4s2z2GqVOhKZETtJRqz5iwMNf+HVLWsaS6C18IOQ24GVAg7bGmJzd TOXTlYOUu0LwvIcqU0iLB7ytxCr5zEU= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-93-ezwmgzSOMVKmoV7STbYMnw-1; Fri, 03 Nov 2023 13:14:35 -0400 X-MC-Unique: ezwmgzSOMVKmoV7STbYMnw-1 Received: by mail-qk1-f197.google.com with SMTP id af79cd13be357-778a738a523so235717885a.0 for ; Fri, 03 Nov 2023 10:14:35 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699031673; x=1699636473; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=+Wk3cA99kER6DIc8UC04YCO9p7d1oNtDexWwv+FX1t4=; b=Yt3kRJgeu+aloI0NsoYyNzhz7DVslOla6NRYrhISvtMc65LQxDVjN6IWnyw4a78J7R YdHgk8IUh1gM5Tp+g0+GWciEiOKdpVopTVGObaGSyqU4YkGo0lJI7N6DX0L3FbFCASwb HXUvTccqDelZTm0tXteyx59eo8YgA0jMPtnPSk9tZZYCd6my5NH8/vjmWe118zWtnt/q LwDrbIlI7SYKm47ptZQhx2beZ3vn9p+XTwo3m9ofH8xm6tKJo7k6LhWArnQcqQ3Jqpip zGeefzcjoC8kbAxpEm5N2lQ9OQ3mqxVAUwasEBtCqlJpfJxK6BfcS452RYT3Nam/bowX TUTQ== X-Gm-Message-State: AOJu0YxQ90RwfZ8S42jAU0pGOSZVwDdY5HkyE/KqYG4yBShotwzU9dF+ 2fYMRO+3OvSX0nZXU6k62MP+m3EWD+p0EgseZowQSSK9xaZ5pf2eRexmp4Q4EuhJCVLzqWeG6+h BbCohl9e2zQhsPM52t+Qzs9T9WSYD8eC5B9ljea87U1SeXJigO5J1UAiXxeP0zl+F76jhRaW6ZJ Og3w== X-Received: by 2002:a05:620a:191a:b0:76d:9f64:f638 with SMTP id bj26-20020a05620a191a00b0076d9f64f638mr25415402qkb.51.1699031673675; Fri, 03 Nov 2023 10:14:33 -0700 (PDT) X-Received: by 2002:a05:620a:191a:b0:76d:9f64:f638 with SMTP id bj26-20020a05620a191a00b0076d9f64f638mr25415380qkb.51.1699031673268; Fri, 03 Nov 2023 10:14:33 -0700 (PDT) Received: from ?IPV6:2607:fea8:51dd:2b00::18c7? ([2607:fea8:51dd:2b00::18c7]) by smtp.gmail.com with ESMTPSA id j22-20020a05620a411600b0077402573fb4sm886248qko.124.2023.11.03.10.14.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Nov 2023 10:14:32 -0700 (PDT) Message-ID: <9134381d-fb7e-4422-9435-d2709d109a36@redhat.com> Date: Fri, 3 Nov 2023 13:14:32 -0400 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: Andrew MacLeod Subject: [COMMITTED 2/2] PR tree-optimization/111766 - Adjust operators equal and not_equal to check bitmasks against constants To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.8 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_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1781563880481059153 X-GMAIL-MSGID: 1781563880481059153 When we compare a range against a constant for equality or inequality, there is currently no attempt made to utilize the known bits. This patch adds a method to the irange_bitmask class to ask if a specific value satisfies the known bit pattern.  Operators equal and not_equal then utilize it when comparing to a constant eliiminating a class of cases we don;t currently get. ie. if (x & 1) return; if (x == 97657) foo() will eliminate the call to foo, even though we do not remove all the odd numbers from the range.  THe bit pattern comparison for   [irange] unsigned int [0, 0] [2, +INF] MASK 0xfffffffe VALUE 0x1  will indicate that any even constants will be false. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From eb899fee35b8326b2105c04f58fd58bbdeca9d3b Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 25 Oct 2023 09:46:50 -0400 Subject: [PATCH 2/2] Adjust operators equal and not_equal to check bitmasks against constants Check to see if a comparison to a constant can be determined to always be not-equal based on the bitmask. PR tree-optimization/111766 gcc/ * range-op.cc (operator_equal::fold_range): Check constants against the bitmask. (operator_not_equal::fold_range): Ditto. * value-range.h (irange_bitmask::member_p): New. gcc/testsuite/ * gcc.dg/pr111766.c: New. --- gcc/range-op.cc | 20 ++++++++++++++++---- gcc/testsuite/gcc.dg/pr111766.c | 13 +++++++++++++ gcc/value-range.h | 14 ++++++++++++++ 3 files changed, 43 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr111766.c diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 33b193be7d0..6137f2aeed3 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -931,8 +931,9 @@ operator_equal::fold_range (irange &r, tree type, // We can be sure the values are always equal or not if both ranges // consist of a single value, and then compare them. - if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) - && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) + bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ()); + bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ()); + if (op1_const && op2_const) { if (wi::eq_p (op1.lower_bound (), op2.upper_bound())) r = range_true (type); @@ -947,6 +948,11 @@ operator_equal::fold_range (irange &r, tree type, tmp.intersect (op2); if (tmp.undefined_p ()) r = range_false (type); + // Check if a constant cannot satisfy the bitmask requirements. + else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ())) + r = range_false (type); + else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ())) + r = range_false (type); else r = range_true_and_false (type); } @@ -1033,8 +1039,9 @@ operator_not_equal::fold_range (irange &r, tree type, // We can be sure the values are always equal or not if both ranges // consist of a single value, and then compare them. - if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) - && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) + bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ()); + bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ()); + if (op1_const && op2_const) { if (wi::ne_p (op1.lower_bound (), op2.upper_bound())) r = range_true (type); @@ -1049,6 +1056,11 @@ operator_not_equal::fold_range (irange &r, tree type, tmp.intersect (op2); if (tmp.undefined_p ()) r = range_true (type); + // Check if a constant cannot satisfy the bitmask requirements. + else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ())) + r = range_true (type); + else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ())) + r = range_true (type); else r = range_true_and_false (type); } diff --git a/gcc/testsuite/gcc.dg/pr111766.c b/gcc/testsuite/gcc.dg/pr111766.c new file mode 100644 index 00000000000..c27a029c772 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr111766.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int +foo3n(int c, int bb) +{ + if ((bb & ~3)!=0) __builtin_unreachable(); // bb = [0,3] + if ((bb & 1)==0) __builtin_unreachable(); // bb&1 == 0 // [0],[3] + if(bb == 2) __builtin_trap(); + return bb; +} + +/* { dg-final { scan-tree-dump-not "trap" "evrp" } } */ diff --git a/gcc/value-range.h b/gcc/value-range.h index 84f65ffb591..330e6f70c6b 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -139,6 +139,7 @@ public: void verify_mask () const; void dump (FILE *) const; + bool member_p (const wide_int &val) const; void adjust_range (irange &r) const; // Convenience functions for nonzero bitmask compatibility. @@ -202,6 +203,19 @@ irange_bitmask::set_nonzero_bits (const wide_int &bits) verify_mask (); } +// Return TRUE if val could be a valid value with this bitmask. + +inline bool +irange_bitmask::member_p (const wide_int &val) const +{ + if (unknown_p ()) + return true; + wide_int res = m_mask & val; + if (m_value != 0) + res |= ~m_mask & m_value; + return res == val; +} + inline bool irange_bitmask::operator== (const irange_bitmask &src) const { -- 2.41.0