From patchwork Wed Oct 6 14:54:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1537182 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=asXyHzWi; 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 (ip-8-43-85-97.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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4HPcwy4CbYz9t0p for ; Thu, 7 Oct 2021 01:56:50 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5A1D33857C58 for ; Wed, 6 Oct 2021 14:56:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5A1D33857C58 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1633532208; bh=WCGwzDg4xlY5z1NqMa9it/d3fJ9zY2+18ewdFkWW1bI=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=asXyHzWimkByYxTem6uZ722NA5QxMRF8WwhMoZNotqwvnaTHnm9m9C+brtAfbGDJv 09gOshGvSo972vscJdYQLvp4TvgR2jwEqLxP/ZtWxAXcWVpP5XBalyBP0Tl3yLIdie x0fxUR84Nj4QQVkBrZpKtDxinRTK2mgOn1NGyAu4= 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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 9CB4E3857C71 for ; Wed, 6 Oct 2021 14:54:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9CB4E3857C71 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-519-v6aqTpYZN8qZV-icbKdrOw-1; Wed, 06 Oct 2021 10:54:09 -0400 X-MC-Unique: v6aqTpYZN8qZV-icbKdrOw-1 Received: by mail-qt1-f200.google.com with SMTP id n1-20020a05622a11c100b002a749aace38so2483245qtk.4 for ; Wed, 06 Oct 2021 07:54:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language; bh=WCGwzDg4xlY5z1NqMa9it/d3fJ9zY2+18ewdFkWW1bI=; b=ZfvG5IhzV91dZ8i2DvkZt4MC1igy0asJKCcKZwUHnfJSg31JrD9Ws/5X1Y5ScXXMsb NHljvjr3pUAzS5868GmtIXRnkK+2Z6mu1OCDAhtg3/iWkZuVQskzCPlbUJywO0cEt0+6 gd3x0lT7arQ8Tp8GTXCFSaLDOFwt1IbYQw7FWV1yzzr0uX0r94pHFdpuygcmibwfgNxX Q0FQm7V5pyIEWjyrXPXhZttpuf03/P/d66Y6syBSL0I/50kiYEBeeJrj6VyxHb892XIr ADTKFEIQqMRBQuCoFLAwXF6XxwLOg4U9brdWuoD9mtSCdKzPvpaw+UgHe7RvJfD+mFAz ja4g== X-Gm-Message-State: AOAM531JS/dpbglWGLlySUdDVzybru7HgH3OA4x9Spf4IHw8X0j3z6vd 2oL7RSKzh/DHxcXPYdKguakUiCA5jgpyY5awSQyLIy3O4QYNvQ1P4KEyoulYensLoIXRWENs9lO 1CNsGLpp8/c8XQGhUGw== X-Received: by 2002:a37:6cc6:: with SMTP id h189mr19983365qkc.321.1633532048745; Wed, 06 Oct 2021 07:54:08 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwGA8jXZVICEnKZyqjCNUzpqbraKTi3Sor5IKVVOhs1PckHdt54qNm5HrjfsZNK3XdViX7kyQ== X-Received: by 2002:a37:6cc6:: with SMTP id h189mr19983347qkc.321.1633532048562; Wed, 06 Oct 2021 07:54:08 -0700 (PDT) Received: from [192.168.0.102] ([104.219.123.55]) by smtp.gmail.com with ESMTPSA id v7sm11634286qkd.41.2021.10.06.07.54.06 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 06 Oct 2021 07:54:07 -0700 (PDT) To: gcc-patches , Aldy Hernandez Subject: [COMMITTED] Add range intersect with 2 wide-ints. Message-ID: Date: Wed, 6 Oct 2021 10:54:05 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.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_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, 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: , 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 provides an intersect to irange which accepts a wide_int lower and upper bound instead of an irange. This both prevents us from having to creates trees when we needs a temporary irange of single bounds. This is also a bit more efficient as we can do the intersect directly in the sub-range vector of the destination irange (which we can't do as easily in the general case). As a result, I've changed the general intersect routine to call this if the other irange has only a single pair.  I've also changed the 3 caller locations I could find which are amenable to this change. Over a set of 380 GCC source files, it produces a nominal 0.8% speedup in EVRP. All 4 patch sets combined produce a 50% speedup in EVRP. I'm also looking at something similar for intersect which is both a more expensive operation, and of course, more complicated. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From ad451b020a24fe7111e668f8c41a3ba648104569 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 4 Oct 2021 15:30:44 -0400 Subject: [PATCH 4/4] Add range intersect with 2 wide-ints. Add a more efficent intersect using a lower/upper bound single pair of wide_ints. * gimple-range-cache.cc (non_null_ref::adjust_range): Call new intersect routine. * gimple-range-fold.cc (adjust_pointer_diff_expr): Ditto. (adjust_imagpart_expr): Ditto. * value-range.cc (irange::irange_intersect): Call new routine if RHS is a single pair. (irange::intersect): New wide_int version. * value-range.h (class irange): New prototype. --- gcc/gimple-range-cache.cc | 6 ++-- gcc/gimple-range-fold.cc | 14 +++----- gcc/value-range.cc | 69 +++++++++++++++++++++++++++++++++++++++ gcc/value-range.h | 1 + 4 files changed, 78 insertions(+), 12 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 91dd5a5c087..7d994798e52 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -105,9 +105,9 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb, // Check if pointers have any non-null dereferences. if (non_null_deref_p (name, bb, search_dom)) { - int_range<2> nz; - nz.set_nonzero (TREE_TYPE (name)); - r.intersect (nz); + // Remove zero from the range. + unsigned prec = TYPE_PRECISION (TREE_TYPE (name)); + r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED)); return true; } return false; diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index bb09b751a4e..ed2fbe121cf 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -360,12 +360,9 @@ adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) && integer_zerop (gimple_call_arg (call, 1))) { tree max = vrp_val_max (ptrdiff_type_node); - wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); - tree expr_type = gimple_range_type (diff_stmt); - tree range_min = build_zero_cst (expr_type); - tree range_max = wide_int_to_tree (expr_type, wmax - 1); - int_range<2> r (range_min, range_max); - res.intersect (r); + unsigned prec = TYPE_PRECISION (TREE_TYPE (max)); + wide_int wmaxm1 = wi::to_wide (max, prec) - 1; + res.intersect (wi::zero (prec), wmaxm1); } } @@ -405,9 +402,8 @@ adjust_imagpart_expr (irange &res, const gimple *stmt) tree cst = gimple_assign_rhs1 (def_stmt); if (TREE_CODE (cst) == COMPLEX_CST) { - tree imag = TREE_IMAGPART (cst); - int_range<2> tmp (imag, imag); - res.intersect (tmp); + wide_int imag = wi::to_wide (TREE_IMAGPART (cst)); + res.intersect (imag, imag); } } } diff --git a/gcc/value-range.cc b/gcc/value-range.cc index f113fd7c905..147c4b04c1d 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1648,6 +1648,8 @@ void irange::irange_intersect (const irange &r) { gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); + gcc_checking_assert (undefined_p () || r.undefined_p () + || range_compatible_p (type (), r.type ())); if (undefined_p () || r.varying_p ()) return; @@ -1662,6 +1664,13 @@ irange::irange_intersect (const irange &r) return; } + if (r.num_pairs () == 1) + { + // R cannot be undefined, use more efficent pair routine. + intersect (r.lower_bound(), r.upper_bound ()); + return; + } + signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); unsigned bld_pair = 0; unsigned bld_lim = m_max_ranges; @@ -1737,6 +1746,66 @@ irange::irange_intersect (const irange &r) verify_range (); } +// Multirange intersect for a specified wide_int [lb, ub] range. + +void +irange::intersect (const wide_int& lb, const wide_int& ub) +{ + // Undefined remains undefined. + if (undefined_p ()) + return; + + if (legacy_mode_p ()) + { + intersect (int_range<1> (type (), lb, ub)); + return; + } + + tree range_type = type(); + signop sign = TYPE_SIGN (range_type); + + gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb)); + gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub)); + + unsigned bld_index = 0; + unsigned pair_lim = num_pairs (); + for (unsigned i = 0; i < pair_lim; i++) + { + tree pairl = m_base[i * 2]; + tree pairu = m_base[i * 2 + 1]; + // Once UB is less than a pairs lower bound, we're done. + if (wi::lt_p (ub, wi::to_wide (pairl), sign)) + break; + // if LB is greater than this pairs upper, this pair is excluded. + if (wi::lt_p (wi::to_wide (pairu), lb, sign)) + continue; + + // Must be some overlap. Find the highest of the lower bounds, + // and set it + if (wi::gt_p (lb, wi::to_wide (pairl), sign)) + m_base[bld_index * 2] = wide_int_to_tree (range_type, lb); + else + m_base[bld_index * 2] = pairl; + + // ...and choose the lower of the upper bounds and if the base pair + // has the lower upper bound, need to check next pair too. + if (wi::lt_p (ub, wi::to_wide (pairu), sign)) + { + m_base[bld_index++ * 2 + 1] = wide_int_to_tree (range_type, ub); + break; + } + else + m_base[bld_index++ * 2 + 1] = pairu; + } + + m_num_ranges = bld_index; + + m_kind = VR_RANGE; + normalize_kind (); + + if (flag_checking) + verify_range (); +} // 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 39e8f3bcdee..ff6c0a6176d 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -73,6 +73,7 @@ public: // In-place operators. void union_ (const irange &); void intersect (const irange &); + void intersect (const wide_int& lb, const wide_int& ub); void invert (); // Operator overloads. -- 2.17.2