From patchwork Fri Apr 21 11:24:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 86249 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp992386vqo; Fri, 21 Apr 2023 04:25:39 -0700 (PDT) X-Google-Smtp-Source: AKy350ZaqmiJdRB17XxQtehHIj6FUj4Al6lMTjs04rlbeShpS9orl7XzmH7pc0ljyi99qgXv0IEj X-Received: by 2002:aa7:d606:0:b0:506:be86:2a8d with SMTP id c6-20020aa7d606000000b00506be862a8dmr4361291edr.19.1682076338953; Fri, 21 Apr 2023 04:25:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1682076338; cv=none; d=google.com; s=arc-20160816; b=SDPvWbzpq7B5D5XgjdTkAOUnvJP6Ucz+RK7Pi+BlVYdm1oDAL7fNvCwqNjrxWOzhhP KdYRrCrWtyWCzB09qFl6iRg1odNpGSuXX10/tgajQ91ePLr9dSZFWlY7l7bzmPPBKuEM ySj7fly9wjBjFH7aSjrOJwOLRogifxOex+cGcLdg6R4t9yTIlwkioFxKSRJV20/T8dKG Uao7tRWQCF94vC+22mrxSLbqEX88aodZeNH/dQt6DlRQlRmMU2WtXJJHKc6L1nN1Xcuq kkHhM1KG4nguaVwHIDEX7JhPpI/kvdqaWCL9Os3vuQv8IXXdqCLAa6bmXzb+kHVlHmj8 WQ7g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=sFUzy0edrI2Pq/9gM596YSURFNMWQos2PiLJ1LDXVkM=; b=eytSAPKWMiuwbKbJbH/a7oube5ZQqU0ftvaaOp9TrGXKP+KjI9f8Vjy3QPfxsWvnEK dkdHwyi9no85QZ0hqFVimMy5wxa2IkTpBl4RVCNZKaGe3uxj4M3llICzG640FDw+DIMF nD2igSylpNfzp0kquS07d6pd19dv6RPj/0JqF9+VioAqd5sj35be3/p2vb9QHGufxHtq WVqQgG7OHHDVDCt1Z2VJfN03mtEb9HZhJv+vXZhdvd4EyBLoCzCutu54jv4FfJcbXHs9 ilNSanSubJXvodQziiSvFHzTQHL/dz1tnO6hXcL3aeGo0wkWIO4SYsot0JYXEPtMl/YU UqkQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=b6irh64g; 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=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id c17-20020a056402121100b00501d485862esi3397522edw.426.2023.04.21.04.25.38 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Apr 2023 04:25:38 -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; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=b6irh64g; 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=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4E4AE3857351 for ; Fri, 21 Apr 2023 11:25:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4E4AE3857351 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682076332; bh=sFUzy0edrI2Pq/9gM596YSURFNMWQos2PiLJ1LDXVkM=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=b6irh64g80Kh6F9HnfANJH9bUBWaGUV5fvWS4LtbH6dRtC03cLiYHNtkFvw3LiLp3 On3CDsjaZ7tetLJ+oxFKOmy0UN4SipDLIQFkm2fbWDpQZ+JXbBqVL2VPc6Bd19/pTy +z9f3kz0XV5Swi8corGZ1Cl83vhRPc+j/iCRu1mQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 9E58A3858C83 for ; Fri, 21 Apr 2023 11:24:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9E58A3858C83 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 4254A219D9 for ; Fri, 21 Apr 2023 11:24:46 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 2DD2B13456 for ; Fri, 21 Apr 2023 11:24:46 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id +TPJCX5yQmTiEQAAMHmgww (envelope-from ) for ; Fri, 21 Apr 2023 11:24:46 +0000 Date: Fri, 21 Apr 2023 13:24:45 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/3] change DF to use the proper CFG order for DF_FORWARD problems MIME-Version: 1.0 Message-Id: <20230421112446.2DD2B13456@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1763784878983326081?= X-GMAIL-MSGID: =?utf-8?q?1763784878983326081?= This changes DF to use RPO on the forward graph for DF_FORWARD problems. While that naturally maps to pre_and_rev_postorder_compute we use the existing (wrong) CFG order for DF_BACKWARD problems computed by post_order_compute since that provides the required side-effect of deleting unreachable blocks. The change requires turning the inconsistent vec vs int * back to consistent int *. A followup patch will change the inverted_post_order_compute API and change the DF_BACKWARD problem to use the correct RPO on the backward graph together with statistics I produced last year for the combined effect. Bootstrapped and tested on x86_64-unknown-linux-gnu. * df.h (df_d::postorder_inverted): Change back to int *, clarify comments. * df-core.cc (rest_of_handle_df_finish): Adjust. (df_analyze_1): Likewise. (df_analyze): For DF_FORWARD problems use RPO on the forward graph. Adjust. (loop_inverted_post_order_compute): Adjust API. (df_analyze_loop): Adjust. (df_get_n_blocks): Likewise. (df_get_postorder): Likewise. --- gcc/df-core.cc | 58 ++++++++++++++++++++++++++------------------------ gcc/df.h | 8 +++---- 2 files changed, 34 insertions(+), 32 deletions(-) diff --git a/gcc/df-core.cc b/gcc/df-core.cc index de5cbd0c622..27123645da5 100644 --- a/gcc/df-core.cc +++ b/gcc/df-core.cc @@ -810,7 +810,7 @@ rest_of_handle_df_finish (void) } free (df->postorder); - df->postorder_inverted.release (); + free (df->postorder_inverted); free (df->hard_regs_live_count); free (df); df = NULL; @@ -1207,9 +1207,6 @@ df_analyze_1 (void) { int i; - /* These should be the same. */ - gcc_assert ((unsigned) df->n_blocks == df->postorder_inverted.length ()); - /* We need to do this before the df_verify_all because this is not kept incrementally up to date. */ df_compute_regs_ever_live (false); @@ -1232,8 +1229,8 @@ df_analyze_1 (void) if (dflow->problem->dir == DF_FORWARD) df_analyze_problem (dflow, df->blocks_to_analyze, - df->postorder_inverted.address (), - df->postorder_inverted.length ()); + df->postorder_inverted, + df->n_blocks); else df_analyze_problem (dflow, df->blocks_to_analyze, @@ -1261,10 +1258,15 @@ df_analyze (void) bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack); free (df->postorder); + free (df->postorder_inverted); df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); df->n_blocks = post_order_compute (df->postorder, true, true); - df->postorder_inverted.truncate (0); - inverted_post_order_compute (&df->postorder_inverted); + /* For DF_FORWARD use a RPO on the forward graph. Since we want to + have unreachable blocks deleted use post_order_compute and reverse + the order. */ + df->postorder_inverted = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + for (int i = 0; i < df->n_blocks; ++i) + df->postorder_inverted[i] = df->postorder[df->n_blocks - 1 - i]; for (int i = 0; i < df->n_blocks; i++) bitmap_set_bit (current_all_blocks, df->postorder[i]); @@ -1273,7 +1275,7 @@ df_analyze (void) { /* Verify that POSTORDER_INVERTED only contains blocks reachable from the ENTRY block. */ - for (unsigned int i = 0; i < df->postorder_inverted.length (); i++) + for (int i = 0; i < df->n_blocks; i++) gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i])); } @@ -1283,12 +1285,11 @@ df_analyze (void) if (df->analyze_subset) { bitmap_and_into (df->blocks_to_analyze, current_all_blocks); - df->n_blocks = df_prune_to_subcfg (df->postorder, - df->n_blocks, df->blocks_to_analyze); - unsigned int newlen = df_prune_to_subcfg (df->postorder_inverted.address (), - df->postorder_inverted.length (), - df->blocks_to_analyze); - df->postorder_inverted.truncate (newlen); + unsigned int newlen = df_prune_to_subcfg (df->postorder, df->n_blocks, + df->blocks_to_analyze); + df_prune_to_subcfg (df->postorder_inverted, df->n_blocks, + df->blocks_to_analyze); + df->n_blocks = newlen; BITMAP_FREE (current_all_blocks); } else @@ -1364,14 +1365,13 @@ loop_post_order_compute (int *post_order, class loop *loop) /* Compute the reverse top sort order of the inverted sub-CFG specified by LOOP. Returns the number of blocks which is always loop->num_nodes. */ -static void -loop_inverted_post_order_compute (vec *post_order, class loop *loop) +static int +loop_inverted_post_order_compute (int *post_order, class loop *loop) { basic_block bb; edge_iterator *stack; int sp; - - post_order->reserve_exact (loop->num_nodes); + int post_order_num = 0; /* Allocate stack for back-tracking up CFG. */ stack = XNEWVEC (edge_iterator, loop->num_nodes + 1); @@ -1408,13 +1408,13 @@ loop_inverted_post_order_compute (vec *post_order, class loop *loop) time, check its predecessors. */ stack[sp++] = ei_start (pred->preds); else - post_order->quick_push (pred->index); + post_order[post_order_num++] = pred->index; } else { if (flow_bb_inside_loop_p (loop, bb) && ei_one_before_end_p (ei)) - post_order->quick_push (bb->index); + post_order[post_order_num++] = bb->index; if (!ei_one_before_end_p (ei)) ei_next (&stack[sp - 1]); @@ -1424,6 +1424,7 @@ loop_inverted_post_order_compute (vec *post_order, class loop *loop) } free (stack); + return post_order_num; } @@ -1433,13 +1434,14 @@ void df_analyze_loop (class loop *loop) { free (df->postorder); + free (df->postorder_inverted); df->postorder = XNEWVEC (int, loop->num_nodes); - df->postorder_inverted.truncate (0); + df->postorder_inverted = XNEWVEC (int, loop->num_nodes); df->n_blocks = loop_post_order_compute (df->postorder, loop); - loop_inverted_post_order_compute (&df->postorder_inverted, loop); + int n = loop_inverted_post_order_compute (df->postorder_inverted, loop); gcc_assert ((unsigned) df->n_blocks == loop->num_nodes); - gcc_assert (df->postorder_inverted.length () == loop->num_nodes); + gcc_assert ((unsigned) n == loop->num_nodes); bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack); for (int i = 0; i < df->n_blocks; ++i) @@ -1460,8 +1462,8 @@ df_get_n_blocks (enum df_flow_dir dir) if (dir == DF_FORWARD) { - gcc_assert (df->postorder_inverted.length ()); - return df->postorder_inverted.length (); + gcc_assert (df->postorder_inverted); + return df->n_blocks; } gcc_assert (df->postorder); @@ -1480,8 +1482,8 @@ df_get_postorder (enum df_flow_dir dir) if (dir == DF_FORWARD) { - gcc_assert (df->postorder_inverted.length ()); - return df->postorder_inverted.address (); + gcc_assert (df->postorder_inverted); + return df->postorder_inverted; } gcc_assert (df->postorder); return df->postorder; diff --git a/gcc/df.h b/gcc/df.h index aec2223591a..402657a7076 100644 --- a/gcc/df.h +++ b/gcc/df.h @@ -581,10 +581,10 @@ public: bitmap_head insns_to_delete; bitmap_head insns_to_rescan; bitmap_head insns_to_notes_rescan; - int *postorder; /* The current set of basic blocks - in reverse postorder. */ - vec postorder_inverted; /* The current set of basic blocks - in reverse postorder of inverted CFG. */ + int *postorder; /* The current set of basic blocks in reverse + postorder for DF_BACKWARD problems. */ + int *postorder_inverted; /* The current set of basic blocks in reverse + postorder for DF_FORWARD problems. */ int n_blocks; /* The number of blocks in reverse postorder. */ /* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number