From patchwork Wed Oct 25 13:55:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1855074 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=cSKv5HIz; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SFr7J4DC1z23jh for ; Thu, 26 Oct 2023 00:56:12 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B4D673857C45 for ; Wed, 25 Oct 2023 13:56:09 +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 A212E3858D1E for ; Wed, 25 Oct 2023 13:55:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A212E3858D1E 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 A212E3858D1E 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=1698242159; cv=none; b=WvMs5y9J+B2BqpPobaaM75aClt0U+whGz4igatBCVsuHponkPR7bdmQYAHzS8tfxlZUsXRH706XLVqfMDdAfa5FmnyO3Y7b5YjANNF6ux0n0nEEnleB72FxG/jxwuQzGROgYuWQYzkvb6pBm2vwdHqXBsXwFWELpngyK8mPxcUU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698242159; c=relaxed/simple; bh=UcZWZlD1ADs2u6m9fOpyjA1VuTSZZytCGPOBYUxVeIc=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=wgfYrbELQ/SE1H71/DiP1XzHRw4pOA53upHu+1vx06+55Bqk2LitKSno1lcF7nR0JY1eSu3XKcd7AsDgVnMhWod2vM2ShegC/SEPJCK1DpoBRctA1PnRgLOSetyfgKTOHi1MgxG5uXMmvCuGXOAnKQaKNWSmZqa2i24mznmkLEQ= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1698242157; 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=PLbw+/BpTTLcJNmIA0z/51WsqfLqaSUDPUm2flZ8TLk=; b=cSKv5HIzGjBYhWp4MgMGevbhQbMnV5+Rk08khLlwQGG+dfgTAZM3SnNAV17WE+KHOMPwZg 7gYjTI9c+nYhxTkSIMYI2eLoCPwBAHw8SAg76cEA+Wy2nLQ+8IApsTnR4zfCzSFf3nNA43 8FIMnZfFIM5/46c22FuyUHcaGdROj30= 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.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-679-ijRBAoW8NL2QaQDpZnZWmQ-1; Wed, 25 Oct 2023 09:55:55 -0400 X-MC-Unique: ijRBAoW8NL2QaQDpZnZWmQ-1 Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-6557c921deeso78222916d6.2 for ; Wed, 25 Oct 2023 06:55:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698242154; x=1698846954; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=pTz2c5sKCDNxcIUgPs947297Sc0JqoQPWdCvTEEzo1g=; b=KXC59HvHrEnlbrGcU7PtcOzJW3j0ACbdVorOTjHEiseCCQht73Ru4npWHOFCGpDZPV KAiybr3eTFlqymTjhAQdFDmNkqn7r9luSYKroFRzQ63JkeDjDWQ7catJ0PUkkj5Vr7Rv 20FeA96Pa4cS07lT7ed79S7F3RwUWp87sCo+Ctx5sPigBHrDlX5EmQDMQNvvQgI3x0a0 QOu2Rfw5Obk/xRAEdT8Y9EvB8Jy22RWJzhPhNYQ4OunTlBAPce0aHshjv/BJU5bm2UgR UAlRVgLOcQvt2iNpm8DLQ9cEV+MbkoQa9T77jZXf/3K43OiiCAvYuQC2JwiiSmvGys88 GMAA== X-Gm-Message-State: AOJu0YxdVZz5tmb7oT/U99TRm3gxMyTLd/csXgTVeKF3oZ25um/zgnwE +g3Jn8xxf2qWMHTamnZhAcgHNlWy5gTUNy4SZDS7gq9enaoyh8U9+gLao+sbPoCy1ZLM5Z1B1jN 3MxNMmFNtYCGhypy8E8Um7A6jLVzo9dgd7oeXM5e0f2ivgkbh1lDItENqyT8tLByxwLm+vFuH0G KDOA== X-Received: by 2002:ad4:5746:0:b0:66d:86a7:d611 with SMTP id q6-20020ad45746000000b0066d86a7d611mr21538411qvx.50.1698242154523; Wed, 25 Oct 2023 06:55:54 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFFiLhasMx+PAKz3ctQK+5rBdCgro/MlcRJLrPh/DCOXd+DtmudSTHHgZNy2xwkb3wY3C/sKg== X-Received: by 2002:ad4:5746:0:b0:66d:86a7:d611 with SMTP id q6-20020ad45746000000b0066d86a7d611mr21538394qvx.50.1698242154117; Wed, 25 Oct 2023 06:55:54 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id ew3-20020a0562140aa300b0065d89f4d537sm4407503qvb.45.2023.10.25.06.55.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 25 Oct 2023 06:55:53 -0700 (PDT) Message-ID: Date: Wed, 25 Oct 2023 09:55:52 -0400 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird To: gcc-patches Cc: "hernandez, aldy" From: Andrew MacLeod Subject: [COMMITTED] Faster irange union for appending ranges. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US 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_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Its a common idiom to build a range by unioning other ranges into another one.  If this is done sequentially, those new ranges can be simply appended to the end of the existing range, avoiding some expensive processing fro the general case. This patch identifies and optimizes this situation.  The result is a 2.1% speedup in VRP and a 0.8% speedup in threading, with a overall compile time improvement of 0.14% across the GCC build. Bootstrapped on  x86_64-pc-linux-gnu with no regressions. Pushed. Andrew commit f7dbf6230453c76a19921607601eff968bb70169 Author: Andrew MacLeod Date: Mon Oct 23 14:52:45 2023 -0400 Faster irange union for appending ranges. A common pattern to to append a range to an existing range via union. This optimizes that process. * value-range.cc (irange::union_append): New. (irange::union_): Call union_append when appropriate. * value-range.h (irange::union_append): New prototype. diff --git a/gcc/value-range.cc b/gcc/value-range.cc index f507ec57536..fcf53efa1dd 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1291,6 +1291,45 @@ irange::irange_single_pair_union (const irange &r) return true; } +// Append R to this range, knowing that R occurs after all of these subranges. +// Return TRUE as something must have changed. + +bool +irange::union_append (const irange &r) +{ + // Check if the first range in R is an immmediate successor to the last + // range, ths requiring a merge. + signop sign = TYPE_SIGN (m_type); + wide_int lb = r.lower_bound (); + wide_int ub = upper_bound (); + unsigned start = 0; + if (widest_int::from (ub, sign) + 1 + == widest_int::from (lb, sign)) + { + m_base[m_num_ranges * 2 - 1] = r.m_base[1]; + start = 1; + } + maybe_resize (m_num_ranges + r.m_num_ranges - start); + for ( ; start < r.m_num_ranges; start++) + { + // Merge the last ranges if it exceeds the maximum size. + if (m_num_ranges + 1 > m_max_ranges) + { + m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1]; + break; + } + m_base[m_num_ranges * 2] = r.m_base[start * 2]; + m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1]; + m_num_ranges++; + } + + if (!union_bitmask (r)) + normalize_kind (); + if (flag_checking) + verify_range (); + return true; +} + // Return TRUE if anything changes. bool @@ -1322,6 +1361,11 @@ irange::union_ (const vrange &v) if (m_num_ranges == 1 && r.m_num_ranges == 1) return irange_single_pair_union (r); + signop sign = TYPE_SIGN (m_type); + // Check for an append to the end. + if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign)) + return union_append (r); + // If this ranges fully contains R, then we need do nothing. if (irange_contains_p (r)) return union_bitmask (r); @@ -1340,7 +1384,6 @@ irange::union_ (const vrange &v) // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] auto_vec res (m_num_ranges * 2 + r.m_num_ranges * 2); unsigned i = 0, j = 0, k = 0; - signop sign = TYPE_SIGN (m_type); while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2) { diff --git a/gcc/value-range.h b/gcc/value-range.h index c00b15194c4..e9d81d22cd0 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -339,6 +339,7 @@ private: bool set_range_from_bitmask (); bool intersect (const wide_int& lb, const wide_int& ub); + bool union_append (const irange &r); unsigned char m_num_ranges; bool m_resizable; unsigned char m_max_ranges;