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: 157379 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1853036vqx; Tue, 24 Oct 2023 03:52:06 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEE7zYOUWP0CGa2qHhlY3IXGlPnoVcN9QJJT+Q87WdO4I4EvW04SNLdgsYRYSqNpdtAVBOK X-Received: by 2002:ac8:7f0b:0:b0:40a:fc6a:e87b with SMTP id f11-20020ac87f0b000000b0040afc6ae87bmr15401268qtk.22.1698144726124; Tue, 24 Oct 2023 03:52:06 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1698144726; cv=pass; d=google.com; s=arc-20160816; b=qf0QH1wnMduVdVwVCIGeHNGfhXG2YS8KRagtF+wCCFv2rWreUNbTuGVbbT8MZSNIiv ORYQxexdL59khmqhLqtqD7Y8SVHb49QX8pUMmMVqGoLTwyV6mTq+wTWBZ7nySxsgU02N Db/CQ3VaTVtl90RS5+P0n2+f4bZyj0GxLTuHPi59n36PN6yEAzGjInIq7b5biI73u3Ls AD0bUqKT2pvcPae7xwyWAGkVKHMoNzcIVyLuc7kTO475eGYzgn/cbK22qMX09ACrob0y A3j2rgovo1g5OFhfYHPjkzKNDZ7Xascf4WbGBfXNN/LdIHetnzstXO8z6wDfrRJFsGVw tEbQ== 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-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:arc-filter:dmarc-filter:delivered-to; bh=zT3LMhqzK9lDvcsu2PAInQG+mUavHJnGN6Ps2F0UwAM=; fh=WSfZ840Wi6BqtTz8VZjapJ1yCCJ9QRCfxSVxwOS9rLc=; b=tK80jtu2fRfYkHOfoBaH8H6nDeRILqkWJDI9+FqY31KqArxGzjKOEPlZRHQqqofz4G do01vt8aZM8EHyObogVqYUPkkvJwCfLfeQh92JimUw0VvSmXBES8RKfbOOhaZgKMy3pJ D6OIVEXTiDxSbR0Iro28Gjz9OazNLVxYpjLc4O9ClClYfvhVMEeiaUQUPXFdoqYh+Sfz n2JD+FJwMJ9qJYoP8LvEEKiwemIzUx7TGgCGkt1J4s2XJLxCTu8dTzTcW43FNt2Q1BRt KDisJ8ZCvBQ0A/NACZeu0JSKadqxspTh/Qg6Zkv1ka7sS9CJzxuSl/qYHmbk8iMk6PQj GIgQ== ARC-Authentication-Results: i=2; mx.google.com; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=arm.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id t37-20020a05622a182500b00417ccac55acsi6461348qtc.641.2023.10.24.03.52.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 03:52:06 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=arm.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E0F9F3858288 for ; Tue, 24 Oct 2023 10:52:05 +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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780633804264354210 X-GMAIL-MSGID: 1780633804264354210 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; }; }