From patchwork Tue Oct 24 10:50:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1854305 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org 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 4SF85G06CVz23jl for ; Tue, 24 Oct 2023 21:52:02 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 663C3385734F for ; Tue, 24 Oct 2023 10:51:53 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 9E3EC3857711 for ; Tue, 24 Oct 2023 10:50:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9E3EC3857711 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9E3EC3857711 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=217.140.110.172 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698144659; cv=none; b=VW19AIJSwcC3kOd2IXpq69Rn0OevYJKYEn6MNRvrsQ+872p8aqwLAmgC4gIIbh232zZ2K1jZ4JohRtXTP1rCs/keijQzsbkKvX3SMrNx1YMcPFEzxHIitNQDRL++Ua6hJVyRGHbhpFxRt5f/nM2bcNxNJvLvZHZbFwP0hTBEBIU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698144659; c=relaxed/simple; bh=M+9lqzMBFx085svWvAWZZ6CeNbtpw3ahXKPG9cgPi2Q=; h=From:To:Subject:Date:Message-Id:MIME-Version; b=K81Q/2qpsbYhHq7GswaBQKJC0cyTJms40ViuEw6pgV9tjgrfa6psdcJos+4csedDK+EmzsMCtDYHXg+5zblGsnggZvGy/pIa+g1tNJmzkzbbUG8ZH494dEGCiiRtYndfwpM+D9qvJFLRWLBEX/R7nQO1Hn8BSoOw4gYIhCol8JE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 4A9712F4; Tue, 24 Oct 2023 03:51:30 -0700 (PDT) Received: from e121540-lin.manchester.arm.com (e121540-lin.manchester.arm.com [10.32.110.72]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id B0FB83F64C; Tue, 24 Oct 2023 03:50:48 -0700 (PDT) From: Richard Sandiford To: jlaw@ventanamicro.com, gcc-patches@gcc.gnu.org Cc: Richard Sandiford Subject: [PATCH 5/6] rtl-ssa: Calculate dominance frontiers for the exit block Date: Tue, 24 Oct 2023 11:50:05 +0100 Message-Id: <20231024105006.3337671-6-richard.sandiford@arm.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20231024105006.3337671-1-richard.sandiford@arm.com> References: <20231024105006.3337671-1-richard.sandiford@arm.com> MIME-Version: 1.0 X-Spam-Status: No, score=-23.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, 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 exit block can have multiple predecessors, for example if the function calls __builtin_eh_return. We might then need PHI nodes for values that are live on exit. RTL-SSA uses the normal dominance frontiers approach for calculating where PHI nodes are needed. However, dominannce.cc only calculates dominators for normal blocks, not the exit block. calculate_dominance_frontiers likewise only calculates dominance frontiers for normal blocks. This patch fills in the “missing” frontiers manually. gcc/ * rtl-ssa/internals.h (build_info::exit_block_dominator): New member variable. * rtl-ssa/blocks.cc (build_info::build_info): Initialize it. (bb_walker::bb_walker): Use it, moving the computation of the dominator to... (function_info::process_all_blocks): ...here. (function_info::place_phis): Add dominance frontiers for the exit block. --- gcc/rtl-ssa/blocks.cc | 41 ++++++++++++++++++++++++++--------------- gcc/rtl-ssa/internals.h | 4 ++++ 2 files changed, 30 insertions(+), 15 deletions(-) diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc index 49c0d15b3cf..0ce798e21b7 100644 --- a/gcc/rtl-ssa/blocks.cc +++ b/gcc/rtl-ssa/blocks.cc @@ -47,7 +47,8 @@ function_info::build_info::build_info (unsigned int num_regs, potential_phi_regs (num_regs), bb_phis (num_bb_indices), bb_mem_live_out (num_bb_indices), - bb_to_rpo (num_bb_indices) + bb_to_rpo (num_bb_indices), + exit_block_dominator (nullptr) { last_access.safe_grow_cleared (num_regs + 1); @@ -103,21 +104,8 @@ function_info::bb_walker::bb_walker (function_info *function, build_info &bi) : dom_walker (CDI_DOMINATORS, ALL_BLOCKS, bi.bb_to_rpo.address ()), m_function (function), m_bi (bi), - m_exit_block_dominator (nullptr) + m_exit_block_dominator (bi.exit_block_dominator) { - // ??? There is no dominance information associated with the exit block, - // so work out its immediate dominator using predecessor blocks. We then - // walk the exit block just before popping its immediate dominator. - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn)->preds) - if (m_exit_block_dominator) - m_exit_block_dominator - = nearest_common_dominator (CDI_DOMINATORS, - m_exit_block_dominator, e->src); - else - m_exit_block_dominator = e->src; - // If the exit block is unreachable, process it last. if (!m_exit_block_dominator) m_exit_block_dominator = ENTRY_BLOCK_PTR_FOR_FN (m_function->m_fn); @@ -624,6 +612,19 @@ function_info::place_phis (build_info &bi) bitmap_initialize (&frontiers[i], &bitmap_default_obstack); compute_dominance_frontiers (frontiers.address ()); + // The normal dominance information doesn't calculate dominators for + // the exit block, so we don't get dominance frontiers for them either. + // Calculate them by hand. + for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds) + { + basic_block bb = e->src; + while (bb != bi.exit_block_dominator) + { + bitmap_set_bit (&frontiers[bb->index], EXIT_BLOCK); + bb = get_immediate_dominator (CDI_DOMINATORS, bb); + } + } + // In extreme cases, the number of live-in registers can be much // greater than the number of phi nodes needed in a block (see PR98863). // Try to reduce the number of operations involving live-in sets by using @@ -1264,6 +1265,16 @@ function_info::process_all_blocks () build_info bi (m_num_regs, num_bb_indices); + // ??? There is no dominance information associated with the exit block, + // so work out its immediate dominator using predecessor blocks. + for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds) + if (bi.exit_block_dominator) + bi.exit_block_dominator + = nearest_common_dominator (CDI_DOMINATORS, + bi.exit_block_dominator, e->src); + else + bi.exit_block_dominator = e->src; + calculate_potential_phi_regs (bi); create_ebbs (bi); place_phis (bi); diff --git a/gcc/rtl-ssa/internals.h b/gcc/rtl-ssa/internals.h index 6ed957754e2..e65ba9fe038 100644 --- a/gcc/rtl-ssa/internals.h +++ b/gcc/rtl-ssa/internals.h @@ -135,6 +135,10 @@ public: // The top of this stack records the start of the current block's // section in DEF_STACK. auto_vec old_def_stack_limit; + + // The block that dominates the exit block, or null if the exit block + // is unreachable. + basic_block exit_block_dominator; }; }