From patchwork Fri Aug 9 19:18:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1971075 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=FKViregB; 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 4WgYdL3n6Rz1yYl for ; Sat, 10 Aug 2024 05:19:50 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B8E74385DDE3 for ; Fri, 9 Aug 2024 19:19:48 +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.133.124]) by sourceware.org (Postfix) with ESMTP id D0BF5385DDE6 for ; Fri, 9 Aug 2024 19:18:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D0BF5385DDE6 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 D0BF5385DDE6 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1723231129; cv=none; b=pIMa5q1Snr79tamSgdSJKOdRqLXTIVLhEwUJ3vjmNmvTKmwDkWpAAC5WgvmWVXRaZ3eeYRn4UTIHUs6m7GRwAz6hOwybvI24reiMLzgAhtWk1idTyQDeNhhcE4GDZ91IGWdXSnB3zm+h/toHQS8gNSTyGy0TBAFgd4YMTFyhpyE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1723231129; c=relaxed/simple; bh=i4SbBQDhZf8TGbujGGtwPPO4MSP4BGfMUVBE1oAh/g8=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=uTHpiTVMigo+k79GaUuN6jGEK7IxTRK3JtynZizJBgx8PHfvLr9TKJ6igxDeWJFh9QuOyyqoCbSQu7hjJ+zhtG44JU6SJ6rvsqP0mBcIofFebgU1wOmCsjhvg0D69yAaHEhjtnUyNXLkpV418bS3d/HXDJWfPeBDuWurc+IPJM0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1723231127; 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=7xe/n3Gk+NYhr7csqLvi9Gnv1YUZs6Fcb3Odeo0ToWM=; b=FKViregBwXLh1GyI3S2WIDZUI65XpkyCcE8ZGe9jqNHGflEwK46xsBSwOaz3+inABBOkDa LnTRrFc3Knlu+6l36jIax0ZTYSV58C0LPxXXonDlt0xJLlMIGlXexHBWTrppnTD4ffnTaF h7xs6oPydhCZ3SuuKUnLBbnmyetUPvE= 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-688-6L9kKtubPhmrbI3x0Tr2qw-1; Fri, 09 Aug 2024 15:18:44 -0400 X-MC-Unique: 6L9kKtubPhmrbI3x0Tr2qw-1 Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-6b79d65bff8so30752356d6.1 for ; Fri, 09 Aug 2024 12:18:44 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723231123; x=1723835923; 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=sSTGWB9Zd5wjTZDHzKsKSOqZFLA2aD8oP+BJWt6lrdU=; b=femhzAKP9rwmduA1ZjnfQtWWyoDjZEmKNbsazrX1wJDcTWq3iGj1C2rIq1lfGmsUVG JjbELk+lIp4thsxVIZznfWFHXj5wSM9ej/oTQeP6iwoOeBWvdsYa70iXCXig7qzRc9Ax mPyhxxhEII6OxPQdj8teJkaVG1r0CRTeXbtqHAnsOyVtzBQNCm96MhMpQpSDrLH1GBUH nR/wW0dGqK3Ez8n9i6qsQGbqaL1zV7DXUj1/wDGIh1pVjD3OiSXPZ03nABWkNkPqO1n7 qxzrv0m/QT72E1O2dGQqXCB+woP/Rmf9pKjv1dUM3IF+3qVRZAWqh6Vzwfy5WZ2Vi2V2 U9bQ== X-Gm-Message-State: AOJu0YxAqOFjgn+1Q0Kw9SGGe6BohnZ12W/DEHYRYRozzjDYb60RYbok 1DVo8uD4WYAtBF2Q4rHVXRs/jFhgDu1RZpFUHQvPk9F1A7Qc7zvySxRyOdk68bMIc0nRRGO/Rjj yC7snTDURbR9gSAUL6bQxhRFLSM3byHn0RLvUVrjsC1J6KKVwtPVLqk4UQxNihTwDcZ8dGdryPa gG8kvi4nIuJnRRc0vUj3C9BPZLp3evvasEgVhF4t8= X-Received: by 2002:a05:6214:4599:b0:6b7:9401:bb7b with SMTP id 6a1803df08f44-6bd78e18736mr32001326d6.23.1723231122874; Fri, 09 Aug 2024 12:18:42 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEDlp/Ai7JaoHgCqRn40gIR9gNUANFSKvHNipsNMGgkXvXl6CxvtGODN43dvPf+eLuQFgnSNA== X-Received: by 2002:a05:6214:4599:b0:6b7:9401:bb7b with SMTP id 6a1803df08f44-6bd78e18736mr32001076d6.23.1723231122382; Fri, 09 Aug 2024 12:18:42 -0700 (PDT) Received: from ?IPV6:2607:fea8:51de:a700::8c44? ([2607:fea8:51de:a700::8c44]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-6bd82c80132sm887906d6.42.2024.08.09.12.18.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 09 Aug 2024 12:18:41 -0700 (PDT) Message-ID: Date: Fri, 9 Aug 2024 15:18:40 -0400 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird To: gcc-patches Cc: "hernandez, aldy" , Richard Biener From: Andrew MacLeod Subject: [COMMITTED 2/2] PR tree-optimization/114855 - Adjust rangers recomputation depth based on the number of BBs. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.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_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 The other place a lot of time is being spent is in the recomputation section. We have a depth limit parameter (ranger-recompuation-depth) which defaults to 5, and specifies the number of statements back we will look to recompute.. this allows us to recompute some relatively complicated things. Again, when the CFG is very large, this testcase shows that this can be very expensive, and we should probably prune that down as the CFG grows.  This patch reduces the specified recomputation depth value by one for every 4096 blocks in the CFG.  Which means for any testcase over about 16,000  basic blocks, we will only look at recomputing single statements.  This helps to reduce the appearance of quadratic-ness. Original time at -O1 was 1506 seconds, with 1215 seconds spent in DOM. The previous patch dropped it to 846 seconds total, with 589 seconds spent in DOM.  thats about a 50% reduction in DOM. This patch drops the time to a total of 416 seconds, with 214 being spent in DOM, so overal about a 90% time reduction in DOM for this test case. Then vast majority of time remaining is spent recalculating edges. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 9e4da946c4263a4c89d5fc365b3c97ae244c5018 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 8 Aug 2024 16:37:28 -0400 Subject: [PATCH 2/2] Adjust rangers recomputation depth based on the number of BBs. As the number of block increase, recomputations can become more expensive. Adjust the depth limit to avoid excessive compile time. PR tree-optimization/114855 * gimple-range-gori.cc (gori_compute::gori_compute): Adjust ranger_recompute_depth limit based on the number of BBs. (gori_compute::may_recompute_p): Use previosuly calculated value. * gimple-range-gori.h (gori_compute::m_recompute_depth): New. --- gcc/gimple-range-gori.cc | 12 ++++++++---- gcc/gimple-range-gori.h | 1 + 2 files changed, 9 insertions(+), 4 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index a31e3be65f7..f2e2b5049aa 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -567,6 +567,13 @@ gori_compute::gori_compute (gori_map &map, int not_executable_flag, m_bool_one = range_true (); if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI)) tracer.enable_trace (); + + // Reduce maximum recompute depth based on the size of the CFG to avoid + // excessive compuations in large CFGs. + m_recompute_depth = (int) param_ranger_recompute_depth + - (int) last_basic_block_for_fn (cfun) / 4096; + if (m_recompute_depth < 1) + m_recompute_depth = 1; } gori_compute::~gori_compute () @@ -1327,10 +1334,7 @@ gori_compute::may_recompute_p (tree name, basic_block bb, int depth) { // -1 indicates a default param, convert it to the real default. if (depth == -1) - { - depth = (int)param_ranger_recompute_depth; - gcc_checking_assert (depth >= 1); - } + depth = m_recompute_depth; bool res = m_map.is_export_p (dep1, bb); if (res || depth <= 1) diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 11019e38471..97e051cd317 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -206,6 +206,7 @@ private: range_tracer tracer; int m_not_executable_flag; + int m_recompute_depth; }; // These APIs are used to query GORI if there are ranges generated on an edge. -- 2.45.0