From patchwork Fri May 13 14:50:08 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1630777 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.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=veGr+zEc; dkim-atps=neutral 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=) 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 (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4L0BRB1DtXz9sFk for ; Sat, 14 May 2022 00:51:01 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E1883395C00A for ; Fri, 13 May 2022 14:50:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E1883395C00A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1652453458; bh=OUVK8gSCEYdnzRDyjFFTmfT06ozuuNfq8i5A1UukoKU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=veGr+zEcb3JvhFx2I+p4burdbbn5eXtOS7uMjENIH5ZeSk/5liGMsJlGDXI1Odw8b T4tKvYOxwni2Y6fEbGQr7yrCUEPnmjjLJcuY2F8ZMHWQWrMvpgo+RzrY7ViRS0P+c4 Mwu48Y9Y84qQOq3AwKQ1bUe58cqmSi1XjPo43+Mc= 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 D2FF4396E432 for ; Fri, 13 May 2022 14:50:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D2FF4396E432 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-465-PtIO5v90P8GaWRslvSB5iA-1; Fri, 13 May 2022 10:50:11 -0400 X-MC-Unique: PtIO5v90P8GaWRslvSB5iA-1 Received: by mail-qv1-f70.google.com with SMTP id u19-20020ad449b3000000b004523cc11b95so7010284qvx.7 for ; Fri, 13 May 2022 07:50:11 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=Fv/tQfzUIFHWQpoUYx5RrJ88kVEFPil/mr/2Gi9fdJM=; b=8KZYfJgIrNmqjiJGtHGPUs/wtZDYwKK8SOwCslv4OhYt37bmW5GF985Vs5V1XDui9/ 7dgrdcvkYaFLCqT3i5SdXmbn9LyVTaH2FzrAa5ISV5YNZxw30ETHOvHcaA2Q4P/wV9Ul 45DpnLO40muEhtAvGaAOEGhMhPo32uzwgwHu16zQZLiktqu/9hOB2s2fif27AQKipcLm rz/Edw/apo8p4mlt5ON1sdshP2Z7Y1u/Ye4bJY9GcCx4nd5FKHsiHGlM9kiHERX99bek M05wf7MHYfQ9k9lStxEaw0hfzfj0I+0Q7ZP0q5feyYzkkxf30iUQhkXKvI2JDyVDs9jd B/ow== X-Gm-Message-State: AOAM532psEKd4Dj/5Q8gBm+0J90Oa1KVXuAOIaWfwlL9PvkyyLqHtlsb 56ROe0yt6xnrOwpYlqddu/y55Y2xx4fwDaUfSDrG+IGG6WMxYTM0f+oLP5iHRLJkanKLmOezYVP AWukJj91ekFXj0v0LOJHZH8hkvtBUlM9ZtLD8ol6nwkyv4/Rn/ECPhE5BBZAl/MsGz3/PgQ== X-Received: by 2002:ac8:578e:0:b0:2f3:ba22:6e79 with SMTP id v14-20020ac8578e000000b002f3ba226e79mr4687530qta.322.1652453410387; Fri, 13 May 2022 07:50:10 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwUSATW4ZiUfdCaB5SfRuG+MMY/oqG5bEYWoPmnkAtjJFUdiW/wvoIDH9Y6saZKFBngNZ/Xxg== X-Received: by 2002:ac8:578e:0:b0:2f3:ba22:6e79 with SMTP id v14-20020ac8578e000000b002f3ba226e79mr4687510qta.322.1652453410081; Fri, 13 May 2022 07:50:10 -0700 (PDT) Received: from ?IPV6:2607:fea8:a261:5e00::94b0? ([2607:fea8:a261:5e00::94b0]) by smtp.gmail.com with ESMTPSA id b6-20020a378006000000b006a007f40477sm1408596qkd.118.2022.05.13.07.50.08 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 13 May 2022 07:50:09 -0700 (PDT) Message-ID: Date: Fri, 13 May 2022 10:50:08 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.0 To: gcc-patches Subject: [COMMITTED] Add a return value to intersect and speed it up. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA 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_LOW, 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.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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch optimizes the multi-range intersect routine for irange. It now has a return value which indicates if the intersection changed the range or not. This can be used to short-circuit updating caches and avoiding additional overheads. It also provides/uses a new routine which returns true is one range is completely contained in/subset of another. over 380 GCC source files:   - in EVRP, this results in a .42% speedup   - in VRP2 its a 1.52% improvement   - in threading its a 0.3% improvement. Furthermore it is also utilized in upcoming changes to avoid extra work when not needed. Bootstraps on x86_64-pc-linux-gnu with no regressions.  pushed. Andrew commit 1d3d7e88aac0db20a4b59044f9b7cd35e847e8d3 Author: Andrew MacLeod Date: Mon May 9 13:20:06 2022 -0400 Add a return value to intersect and speed it up. Return true if the intersection of ranges changed the original value. Speed up the case when there is no change by calling an efficient contains routine. * value-range.cc (irange::legacy_verbose_intersect): Add return value. (irange::irange_contains_p): New. (irange::irange_intersect): Add return value. * value-range.h (class irange): Adjust prototypes. diff --git a/gcc/value-range.cc b/gcc/value-range.cc index 94301b32c37..190d7fb6f22 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1481,7 +1481,7 @@ irange::legacy_verbose_union_ (const irange *other) irange_union (*other); } -void +bool irange::legacy_verbose_intersect (const irange *other) { if (legacy_mode_p ()) @@ -1490,7 +1490,7 @@ irange::legacy_verbose_intersect (const irange *other) { int_range<1> tmp = *other; legacy_intersect (this, &tmp); - return; + return true; } if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1509,17 +1509,17 @@ irange::legacy_verbose_intersect (const irange *other) dump_value_range (dump_file, this); fprintf (dump_file, "\n"); } - return; + return true; } if (other->legacy_mode_p ()) { int_range<2> wider; wider = *other; - irange_intersect (wider); + return irange_intersect (wider); } else - irange_intersect (*other); + return irange_intersect (*other); } // union_ for multi-ranges. @@ -1630,9 +1630,55 @@ irange::irange_union (const irange &r) verify_range (); } -// intersect for multi-ranges. +// Return TRUE if THIS fully contains R. No undefined or varying cases. -void +bool +irange::irange_contains_p (const irange &r) const +{ + gcc_checking_assert (!undefined_p () && !varying_p ()); + gcc_checking_assert (!r.undefined_p () && !varying_p ()); + + // In order for THIS to fully contain R, all of the pairs within R must + // be fully contained by the pairs in this object. + signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); + unsigned ri = 0; + unsigned i = 0; + tree rl = r.m_base[0]; + tree ru = r.m_base[1]; + tree l = m_base[0]; + tree u = m_base[1]; + while (1) + { + // If r is contained within this range, move to the next R + if (wi::ge_p (wi::to_wide (rl), wi::to_wide (l), sign) + && wi::le_p (wi::to_wide (ru), wi::to_wide (u), sign)) + { + // This pair is OK, Either done, or bump to the next. + if (++ri >= r.num_pairs ()) + return true; + rl = r.m_base[ri * 2]; + ru = r.m_base[ri * 2 + 1]; + continue; + } + // Otherwise, check if this's pair occurs before R's. + if (wi::lt_p (wi::to_wide (u), wi::to_wide (rl), sign)) + { + // THere's still at leats one pair of R left. + if (++i >= num_pairs ()) + return false; + l = m_base[i * 2]; + u = m_base[i * 2 + 1]; + continue; + } + return false; + } + return false; +} + + +// Intersect for multi-ranges. Return TRUE if anything changes. + +bool irange::irange_intersect (const irange &r) { gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); @@ -1640,24 +1686,24 @@ irange::irange_intersect (const irange &r) || range_compatible_p (type (), r.type ())); if (undefined_p () || r.varying_p ()) - return; + return false; if (r.undefined_p ()) { set_undefined (); - return; + return true; } if (varying_p ()) { operator= (r); - return; + return true; } if (r.num_pairs () == 1) - { - // R cannot be undefined, use more efficent pair routine. - intersect (r.lower_bound(), r.upper_bound ()); - return; - } + return intersect (r.lower_bound (), r.upper_bound ()); + + // If R fully contains this, then intersection will change nothing. + if (r.irange_contains_p (*this)) + return false; signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); unsigned bld_pair = 0; @@ -1732,21 +1778,25 @@ irange::irange_intersect (const irange &r) if (flag_checking) verify_range (); + + return true; } + // Multirange intersect for a specified wide_int [lb, ub] range. +// Return TRUE if intersect changed anything. -void +bool irange::intersect (const wide_int& lb, const wide_int& ub) { // Undefined remains undefined. if (undefined_p ()) - return; + return false; if (legacy_mode_p ()) { intersect (int_range<1> (type (), lb, ub)); - return; + return true; } tree range_type = type(); @@ -1755,6 +1805,11 @@ irange::intersect (const wide_int& lb, const wide_int& ub) gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb)); gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub)); + // If this range is fuly contained, then intersection will do nothing. + if (wi::ge_p (lower_bound (), lb, sign) + && wi::le_p (upper_bound (), ub, sign)) + return false; + unsigned bld_index = 0; unsigned pair_lim = num_pairs (); for (unsigned i = 0; i < pair_lim; i++) @@ -1793,7 +1848,10 @@ irange::intersect (const wide_int& lb, const wide_int& ub) if (flag_checking) verify_range (); + return true; } + + // Signed 1-bits are strange. You can't subtract 1, because you can't // represent the number 1. This works around that for the invert routine. diff --git a/gcc/value-range.h b/gcc/value-range.h index 90a395f4d73..419860247fc 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -72,7 +72,7 @@ public: // In-place operators. void union_ (const irange &); - void intersect (const irange &); + bool intersect (const irange &); void invert (); // Operator overloads. @@ -97,7 +97,7 @@ public: void set (tree); // DEPRECATED bool equal_p (const irange &) const; // DEPRECATED void legacy_verbose_union_ (const class irange *); // DEPRECATED - void legacy_verbose_intersect (const irange *); // DEPRECATED + bool legacy_verbose_intersect (const irange *); // DEPRECATED protected: irange (tree *, unsigned); @@ -108,9 +108,10 @@ protected: // In-place operators. void irange_union (const irange &); - void irange_intersect (const irange &); + bool irange_intersect (const irange &); void irange_set (tree, tree); void irange_set_anti_range (tree, tree); + bool irange_contains_p (const irange &) const; void normalize_kind (); @@ -134,7 +135,7 @@ private: void irange_set_1bit_anti_range (tree, tree); bool varying_compatible_p () const; - void intersect (const wide_int& lb, const wide_int& ub); + bool intersect (const wide_int& lb, const wide_int& ub); unsigned char m_num_ranges; unsigned char m_max_ranges; ENUM_BITFIELD(value_range_kind) m_kind : 8; @@ -553,13 +554,14 @@ irange::union_ (const irange &r) dump_flags = m_flags; } -inline void +inline bool irange::intersect (const irange &r) { dump_flags_t m_flags = dump_flags; dump_flags &= ~TDF_DETAILS; - irange::legacy_verbose_intersect (&r); + bool ret = irange::legacy_verbose_intersect (&r); dump_flags = m_flags; + return ret; } // Set value range VR to a nonzero range of type TYPE.