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: 158105 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp2617393vqx; Wed, 25 Oct 2023 06:56:22 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGG4eJryxvh/3QQlQCcm/kz87P3eUmX45VA4mnscjNXjaPk7nU/itqo4XdDGVhXi/NyXVFU X-Received: by 2002:ad4:5f07:0:b0:658:997f:79b7 with SMTP id fo7-20020ad45f07000000b00658997f79b7mr19642752qvb.3.1698242182066; Wed, 25 Oct 2023 06:56:22 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1698242182; cv=pass; d=google.com; s=arc-20160816; b=ql1Cn2hgVFTFLaCOAgR54ZlrvavG33usTNGUPpecMcnM1KKMpKm1h47ODWNdjAu6Ty UtqtKoa1LcdFJFPGimFKQeft8iNN6LY9v0ZK2MHXuA6bVgBH8bALrNHDjQsJHHMzrsxi dwspZ+qr2jAW84anILKlkJp5/Zm6NtSa6gvXf3mCkOVB1zkpe3h+LtYobyn9vaWPLLPB ErTYO3n1zjTZpC6mTfy52sJ1Gp23zXda6kY10eg9HI3oDojNU9gv/Q40aBiWK7Yh9ioQ OtndOz7mCoRCstaEiGOLuKaE4LCQ7rXadD8KbwKEo0oIUN8spQH2p+JqVPwl1VrwVzkX Fdjg== 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:subject:from :cc:to:user-agent:mime-version:date:message-id:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=PLbw+/BpTTLcJNmIA0z/51WsqfLqaSUDPUm2flZ8TLk=; fh=ZE6EPE2PZ3ED3Eq5R4AB8kSxxMSuW2qQfXnHfqWWl4c=; b=JVPTCS5pwiQ+XfhDk84SD49vjhMLdAjt3etHDsZ2OhqU+kHDAF5URNH8ZAOyyPqXxm /qoPQZ8bIzyQy2lJ+6OKMlxYgAavEbZKjQgM4mZ0BlMlYDLFg0jVGUwIrTx0JtNeUtWG KQU/vu3UwJ10fYyl3KSB8UpndjSk2iRabSv+x+Of/nnECM2M0ynVtWV7KyN9k3gJ8cDd wafDiA8LIWzMNYliH1Ads9Yvz0r3H0biNGfg2lpYwdc5ztz708Qdkj+V92v+QuN8rAy1 unnbNMQgp+wtIdqi/wio6zEbsJmaKkbFCmhTvBjcw+M8n9xsMmbIaPy2J9y230vP0uGq 8kkQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=cSKv5HIz; 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 q8-20020a05620a024800b0076c8d5c1aeesi7960815qkn.551.2023.10.25.06.56.22 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 25 Oct 2023 06:56:22 -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=cSKv5HIz; 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 CF5F23858421 for ; Wed, 25 Oct 2023 13:56:21 +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-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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780735993943109803 X-GMAIL-MSGID: 1780735993943109803 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;