From patchwork Fri May 13 14:55:29 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1630779 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=g3NvgMix; dkim-atps=neutral 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+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (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 4L0BYL5Yh3z9sFk for ; Sat, 14 May 2022 00:56:21 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 322D5396E477 for ; Fri, 13 May 2022 14:56:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 322D5396E477 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1652453779; bh=n7US1RVDPVC4hBzbcQM6ZiClAqFX0q1vWsS5f5DDuVQ=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=g3NvgMixNfSldQnU9EFXrBMD21dpQBxT2xyKGY66tfPNIlaFu3yfY3niUVgGZI4Z+ Sb5bNWsnABuIBRIq6hLc7SanYtsYCihZRsy6Rnu9P3GFT8u16ODlscPlk9SuSTQ5Dc rMAyeZsi6qdYn6kZiiMH6WG1+E9IwUBwY+5C7U4Q= 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 6596F396E07C for ; Fri, 13 May 2022 14:55:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6596F396E07C 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-657-65ECtJZdOFurIdHaO3oASQ-1; Fri, 13 May 2022 10:55:32 -0400 X-MC-Unique: 65ECtJZdOFurIdHaO3oASQ-1 Received: by mail-qk1-f197.google.com with SMTP id bl27-20020a05620a1a9b00b0069994eeb30cso6522024qkb.11 for ; Fri, 13 May 2022 07:55:32 -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=QpajR4IcIznblW4VJK/WMOaLx0zpMigzGhK+Wl9/408=; b=JO4Q7PKa7mJ1nyZUdzBGkpVOOJCCFLCmvM3MQ3LZfAvamLIwc6nsinyAF1kQ6Tmr+s MLRVPpA2DwvX8r/JPc2tHXAuZljaT4+rRjgSRDCH3MAXYxI857pwR1ad52MvtDGvP24q +JxtcpSTMVMgMHFUrT1lyBfBA0MqHDVxMqN6dYzJogG9lAvochRLJwSXEZrRakaCGSyj +BGeDTVB8+9uUN8bSZTlw6kqk9X0TfrDWCbugbBVEBDa/egoEQLwQysLLwmU1myXwQAY 0GlmIkH6O6qiVbwL/VD0R50y4XSqm28H6EovdiSic+2VmkQ5H7nKGujrBuLknpIQLE+d BEPw== X-Gm-Message-State: AOAM533kZeYTOV7FvR+4uGpftDeMACE+r89xwIoTQ8C3my88BuesbuNl 4dwus9/OBDwThemgQ+RvTmaJGDrMeAjpYXl2a+1l2uR2JymfL0Rt3+L5sgtLoa8qn6RC4GdT80L f8wHgWzW4IylMeJG1SFrMn6vQLzEgnjcKA6/dkmg2Qz/kdv8B85GaGHUDEH34pVrNvTAZqA== X-Received: by 2002:a05:620a:28ca:b0:6a0:a0a9:b2e6 with SMTP id l10-20020a05620a28ca00b006a0a0a9b2e6mr3691635qkp.638.1652453731994; Fri, 13 May 2022 07:55:31 -0700 (PDT) X-Google-Smtp-Source: ABdhPJw+PWlucNVJS4GGdWv1zoWOM4fALwx6PBAT089VGFb4pGQ9d1J574r4uo47uAatJlsXI1FyVg== X-Received: by 2002:a05:620a:28ca:b0:6a0:a0a9:b2e6 with SMTP id l10-20020a05620a28ca00b006a0a0a9b2e6mr3691613qkp.638.1652453731699; Fri, 13 May 2022 07:55:31 -0700 (PDT) Received: from ?IPV6:2607:fea8:a261:5e00::94b0? ([2607:fea8:a261:5e00::94b0]) by smtp.gmail.com with ESMTPSA id a75-20020a37664e000000b006a03cbb1323sm1434877qkc.65.2022.05.13.07.55.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 13 May 2022 07:55:31 -0700 (PDT) Message-ID: <4f2d262b-60c4-d194-565f-58effef1286f@redhat.com> Date: Fri, 13 May 2022 10:55:29 -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] Return a bool result for union, and add performance improvements. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-13.0 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 does the same for union.. adds a return value indicating in the union call changes the range. It adds a routine for efficiency which performs a union between 2 single pairs, the most common case. Improvements are much nominal.. along the 0.1% range, but again, will be utilized by forthcoming changes as well. Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed. commit f3204ce1ae6b97f7e79d633844d61d021da8502e Author: Andrew MacLeod Date: Mon May 9 13:32:31 2022 -0400 Return a bool result for union, and add performance improvements. Union_ returns a boolean indicating if the operation changes the range. Also optimize the common single-pair UNION single-pair case. * gimple-range-edge.cc (calc_switch_ranges): Check union return value. * value-range.cc (irange::legacy_verbose_union_): Add return value. (irange::irange_single_pair_union): New. (irange::irange_union): Add return value. * value-range.h (class irange): Adjust prototypes. diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc index 6caa07c8f02..0bee38ba770 100644 --- a/gcc/gimple-range-edge.cc +++ b/gcc/gimple-range-edge.cc @@ -154,7 +154,9 @@ gimple_outgoing_range::calc_switch_ranges (gswitch *sw) irange *&slot = m_edge_table->get_or_insert (e, &existed); if (existed) { - case_range.union_ (*slot); + // If this doesn't change the value, move on. + if (!case_range.union_ (*slot)) + continue; if (slot->fits_p (case_range)) { *slot = case_range; diff --git a/gcc/value-range.cc b/gcc/value-range.cc index 190d7fb6f22..2e7385aecc2 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1439,9 +1439,10 @@ irange::legacy_union (irange *vr0, const irange *vr1) /* Meet operation for value ranges. Given two value ranges VR0 and VR1, store in VR0 a range that contains both VR0 and VR1. This - may not be the smallest possible such range. */ + may not be the smallest possible such range. + Return TRUE if the original value changes. */ -void +bool irange::legacy_verbose_union_ (const irange *other) { if (legacy_mode_p ()) @@ -1450,7 +1451,7 @@ irange::legacy_verbose_union_ (const irange *other) { int_range<1> tmp = *other; legacy_union (this, &tmp); - return; + return true; } if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1469,16 +1470,16 @@ irange::legacy_verbose_union_ (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 = *other; - irange_union (wider); + return irange_union (wider); } else - irange_union (*other); + return irange_union (*other); } bool @@ -1522,22 +1523,95 @@ irange::legacy_verbose_intersect (const irange *other) return irange_intersect (*other); } +// Perform an efficient union with R when both ranges have only a single pair. +// Excluded are VARYING and UNDEFINED ranges. + +bool +irange::irange_single_pair_union (const irange &r) +{ + gcc_checking_assert (!undefined_p () && !varying_p ()); + gcc_checking_assert (!r.undefined_p () && !varying_p ()); + + signop sign = TYPE_SIGN (TREE_TYPE (m_base[0])); + // Check if current lower bound is also the new lower bound. + if (wi::le_p (wi::to_wide (m_base[0]), wi::to_wide (r.m_base[0]), sign)) + { + // If current upper bound is new upper bound, we're done. + if (wi::le_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign)) + return false; + // Otherwise R has the new upper bound. + // Check for overlap/touching ranges, or single target range. + if (m_max_ranges == 1 + || wi::to_widest (m_base[1]) + 1 >= wi::to_widest (r.m_base[0])) + { + m_base[1] = r.m_base[1]; + if (varying_compatible_p ()) + m_kind = VR_VARYING; + } + else + { + // This is a dual range result. + m_base[2] = r.m_base[0]; + m_base[3] = r.m_base[1]; + m_num_ranges = 2; + } + if (flag_checking) + verify_range (); + return true; + } + + // Set the new lower bound to R's lower bound. + tree lb = m_base[0]; + m_base[0] = r.m_base[0]; + + // If R fully contains THIS range, just set the upper bound. + if (wi::ge_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign)) + m_base[1] = r.m_base[1]; + // Check for overlapping ranges, or target limited to a single range. + else if (m_max_ranges == 1 + || wi::to_widest (r.m_base[1]) + 1 >= wi::to_widest (lb)) + { + // This has the new upper bound, just check for varying. + if (varying_compatible_p ()) + m_kind = VR_VARYING; + } + else + { + // Left with 2 pairs. + m_num_ranges = 2; + m_base[2] = lb; + m_base[3] = m_base[1]; + m_base[1] = r.m_base[1]; + } + if (flag_checking) + verify_range (); + return true; +} + // union_ for multi-ranges. -void +bool irange::irange_union (const irange &r) { gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); if (r.undefined_p () || varying_p ()) - return; + return false; if (undefined_p () || r.varying_p ()) { operator= (r); - return; + return true; } + // Special case one range union one range. + if (m_num_ranges == 1 && r.m_num_ranges == 1) + return irange_single_pair_union (r); + + // If this ranges fully contains R, then we need do nothing. + if (irange_contains_p (r)) + return false; + // Do not worry about merging and such by reserving twice as many // pairs as needed, and then simply sort the 2 ranges into this // intermediate form. @@ -1628,6 +1702,7 @@ irange::irange_union (const irange &r) if (flag_checking) verify_range (); + return true; } // Return TRUE if THIS fully contains R. No undefined or varying cases. diff --git a/gcc/value-range.h b/gcc/value-range.h index 419860247fc..ec59d2e4f23 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -71,7 +71,7 @@ public: bool contains_p (tree) const; // In-place operators. - void union_ (const irange &); + bool union_ (const irange &); bool intersect (const irange &); void invert (); @@ -96,7 +96,7 @@ public: bool may_contain_p (tree) const; // DEPRECATED void set (tree); // DEPRECATED bool equal_p (const irange &) const; // DEPRECATED - void legacy_verbose_union_ (const class irange *); // DEPRECATED + bool legacy_verbose_union_ (const class irange *); // DEPRECATED bool legacy_verbose_intersect (const irange *); // DEPRECATED protected: @@ -107,11 +107,12 @@ protected: tree tree_upper_bound () const; // In-place operators. - void irange_union (const irange &); + bool irange_union (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; + bool irange_single_pair_union (const irange &r); void normalize_kind (); @@ -545,13 +546,14 @@ irange::upper_bound () const return upper_bound (pairs - 1); } -inline void +inline bool irange::union_ (const irange &r) { dump_flags_t m_flags = dump_flags; dump_flags &= ~TDF_DETAILS; - irange::legacy_verbose_union_ (&r); + bool ret = irange::legacy_verbose_union_ (&r); dump_flags = m_flags; + return ret; } inline bool