From patchwork Wed Sep 25 10:51:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1989292 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=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=R0UpRO/m; dkim=pass header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=+iaklBjT; dkim=pass (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=R0UpRO/m; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=+iaklBjT; 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 4XDD7s4n7tz1xt5 for ; Wed, 25 Sep 2024 20:52:09 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D881B3858C31 for ; Wed, 25 Sep 2024 10:52:07 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2a07:de40:b251:101:10:150:64:2]) by sourceware.org (Postfix) with ESMTPS id 4532C3858D26 for ; Wed, 25 Sep 2024 10:51:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4532C3858D26 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 4532C3858D26 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:2 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727261499; cv=none; b=EQG1dGUsJnLUlbAEo24v7tghO8cH0SwLZ22Q+NGaFFoVMOQqfQqAk0Sn6C86k0RDASvI67duVmLdRGxJcg7YSm3njNOcnXPrOBor9/W6mQrBHL18DwgAL7LV5VdhNnanWfXFCjZ6Ndxs3Dl1VuX4fgObHXCL4+AW2miuow9hfyE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727261499; c=relaxed/simple; bh=W39rs5/6RHT8meaS6DxSyxt/OJW8l5NXHvi7r/ScDH4=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=YqQ28cwCQbQqBIU0eqT/55qQ/Y+sK1WY4vRm/kVCr5sq47pmmoM1BrabTOIph6xvZYjf8bHq2V3D+Wl6p/PIqJcGm2LWFLRIW9rcneo4XHXWirCNweD00ARBmx/SzGv1edmh1KeFvgY81pRLi+2vIDaNElPtvWejN6w9f3oGfhc= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from murzim.nue2.suse.org (unknown [10.168.4.243]) (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 smtp-out2.suse.de (Postfix) with ESMTPS id 07F791F44F; Wed, 25 Sep 2024 10:51:36 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727261496; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=xZteXnIANZjdKIfchOaH4zYItbvgRDiglOZeZ2mMCdw=; b=R0UpRO/m1d1Z5Mv49yj310tnIzoIYt0o3wwJpnQhQIn5GCv67/7+w2KEQVM5jteE1hr85q rA/p2MnPbzEJhNtE6wIwfLLUHaq0dDAmCxJRf/mocPI3wfCoddj/axEEFDTdhzFJzsXqIl g8R48eNzSmh4WPFpquJHg3B+lFum7yM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727261496; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=xZteXnIANZjdKIfchOaH4zYItbvgRDiglOZeZ2mMCdw=; b=+iaklBjTZUZAu0TyWuSLDhMWXXmPNgfdWl24MLcWAjIM2eG8JAPIZg07xu36jc9tCRRgId ohVsqqXJDafPYkBg== Authentication-Results: smtp-out2.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1727261496; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=xZteXnIANZjdKIfchOaH4zYItbvgRDiglOZeZ2mMCdw=; b=R0UpRO/m1d1Z5Mv49yj310tnIzoIYt0o3wwJpnQhQIn5GCv67/7+w2KEQVM5jteE1hr85q rA/p2MnPbzEJhNtE6wIwfLLUHaq0dDAmCxJRf/mocPI3wfCoddj/axEEFDTdhzFJzsXqIl g8R48eNzSmh4WPFpquJHg3B+lFum7yM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1727261496; h=from:from:reply-to:date:date:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=xZteXnIANZjdKIfchOaH4zYItbvgRDiglOZeZ2mMCdw=; b=+iaklBjTZUZAu0TyWuSLDhMWXXmPNgfdWl24MLcWAjIM2eG8JAPIZg07xu36jc9tCRRgId ohVsqqXJDafPYkBg== Date: Wed, 25 Sep 2024 12:51:35 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: amacleod@redhat.com Subject: [PATCH] tree-optimization/114855 - speed up dom_oracle::register_transitives MIME-Version: 1.0 X-Spam-Score: -1.51 X-Spamd-Result: default: False [-1.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; MISSING_MID(2.50)[]; NEURAL_HAM_LONG(-0.71)[-0.712]; NEURAL_HAM_SHORT(-0.20)[-0.999]; MIME_GOOD(-0.10)[text/plain]; MISSING_XM_UA(0.00)[]; RCVD_COUNT_ZERO(0.00)[0]; ARC_NA(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; FROM_HAS_DN(0.00)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; TO_DN_NONE(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[murzim.nue2.suse.org:helo] X-Spam-Level: X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, MISSING_MID, SPF_HELO_NONE, SPF_PASS, 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 Message-Id: <20240925105207.D881B3858C31@sourceware.org> dom_oracle::register_transitives contains an unbound dominator walk which for the testcase in PR114855 dominates the profile. I've also noticed odd behavior in the case when set_one_relation returns NULL, we'd then completely abort processing other relations. The following fixes the latter by continuing searching and fixes the unbound work done by assigning a constant work budget to the loop, bounding the number of dominators visited but also the number of relations processed. This gets both dom_oracle::register_transitives and get_immediate_dominator off the profile. I'll note that we're still doing an unbound dominator walk via equiv_set in find_equiv_dom at the start of the function and when we register a relation that also looks up the same way. At least for the testcase at hand this isn't an issue. I've wondered whether instead of having a per-BB bitmap of names we have a relation for in that BB having a bitmap per SSA name of which BBs have a relation for it would be a way to avoid all those walks. Bootstrapped and tested on x86_64-unknown-linux-gnu. OK for trunk? Thanks, Richard. PR tree-optimization/114855 * params.opt (--param transitive-relations-work-bound): New. * doc/invoke.texi (--param transitive-relations-work-bound): Document. * value-relation.cc (dom_oracle::register_transitives): Do not stop processing relations when a registration attempt did not register a new relation. Assing an overall work budget, bounding the dominator walk and the number of relations processed. --- gcc/doc/invoke.texi | 3 +++ gcc/params.opt | 4 ++++ gcc/value-relation.cc | 47 ++++++++++++++++++++++++++----------------- 3 files changed, 35 insertions(+), 19 deletions(-) diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index bdbbea53666..bd1208a62ee 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -17144,6 +17144,9 @@ in the outgoing range calculator. @item relation-block-limit Maximum number of relations the oracle will register in a basic block. +@item transitive-relations-work-bound +Work bound when discovering transitive relations from existing relations. + @item min-pagesize Minimum page size for warning purposes. diff --git a/gcc/params.opt b/gcc/params.opt index 949b4754498..a08e4c1042d 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -924,6 +924,10 @@ outgoing range calculator. Common Joined UInteger Var(param_relation_block_limit) Init(200) IntegerRange(0, 9999) Param Optimization Maximum number of relations the oracle will register in a basic block. +-param=transitive-relations-work-bound= +Common Joined UInteger Var(param_transitive_relations_work_bound) Init(256) IntegerRange(0, 9999) Param Optimization +Work bound when discovering transitive relations from existing relations. + -param=rpo-vn-max-loop-depth= Common Joined UInteger Var(param_rpo_vn_max_loop_depth) Init(7) IntegerRange(2, 65536) Param Optimization Maximum depth of a loop nest to fully value-number optimistically. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index d6ad2dd984f..b01e2953188 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1204,7 +1204,13 @@ dom_oracle::register_transitives (basic_block root_bb, const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb); const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb); - for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + const unsigned work_budget = param_transitive_relations_work_bound; + unsigned avail_budget = work_budget; + for (bb = root_bb; bb; + /* Advancing to the next immediate dominator eats from the budget, + if none is left after that there's no point to continue. */ + bb = (--avail_budget > 0 + ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr)) { int bbi = bb->index; if (bbi >= (int)m_relations.length()) @@ -1247,27 +1253,30 @@ dom_oracle::register_transitives (basic_block root_bb, // Ignore if both NULL (not relevant relation) or the same, if (r1 == r2) - continue; + ; - // Any operand not an equivalence, just take the real operand. - if (!r1) - r1 = relation.op1 (); - if (!r2) - r2 = relation.op2 (); - - value_relation nr (relation.kind (), r1, r2); - if (nr.apply_transitive (*ptr)) + else { - if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ())) - return; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " Registering transitive relation "); - nr.dump (dump_file); - fputc ('\n', dump_file); - } + // Any operand not an equivalence, just take the real operand. + if (!r1) + r1 = relation.op1 (); + if (!r2) + r2 = relation.op2 (); + + value_relation nr (relation.kind (), r1, r2); + if (nr.apply_transitive (*ptr) + && set_one_relation (root_bb, nr.kind (), + nr.op1 (), nr.op2 ())) + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Registering transitive relation "); + nr.dump (dump_file); + fputc ('\n', dump_file); + } } - + /* Processed one relation, abort if we've eaten up our budget. */ + if (--avail_budget == 0) + return; } } }