From patchwork Fri Apr 21 11:25:27 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 86251 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp993050vqo; Fri, 21 Apr 2023 04:27:04 -0700 (PDT) X-Google-Smtp-Source: AKy350bFwpy9ASXIhOtCx9OtEldybykQpb69LejN2k0OZklgIxAG/FAcoQqhmASS9ukmn6zrk7SS X-Received: by 2002:aa7:db92:0:b0:506:be3f:ebab with SMTP id u18-20020aa7db92000000b00506be3febabmr4369861edt.22.1682076424281; Fri, 21 Apr 2023 04:27:04 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1682076424; cv=none; d=google.com; s=arc-20160816; b=LUqqqH9Nly5T/jOdfALGW/5W32E9LlnVpvuI8+GF7fh3SQCqUEMFsfXuuPAigLMvUJ 6kAkIPFBdfVPkllM6gcuFaKfZQO2hptEsB4PtAdZAElHIy0+1E7HlklF7vevhcHY1R3E ujGFePvuLwY9Yq+IaSmB4KU1Kj5Lm44qpLSMmV8SM3Q+bXnugCoEF6uR07gX/+HS1uOb cdTSD/W1PNGcJ+n8+7BJSkGBOstu0MhS4eFNMj7yzv93uCgk9jkR8nAHX+mo/LjNUVEF ecY4U0B2Suii2vbcbZXV10Jr3GZ93f6yHZqRfpeMMuU9J1yAEE6Qj/SGlTXj+NF79OoA vTLQ== 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=/4VfgTAxCZzWhotHdU/J39uLy/VfR3XAudXw60Qvv4k=; b=r+seRqcco21ulcjNatCbv+laaUQF1xacogPpt2MmzARXA1NLyM7dO/T/+MaljXxO3l WLa6bjrPV5CEW+ALv3HjhfZixgtbEtcqXz2QsGsot3wMk0P/N7g/SqKzpLbON8tyCob8 CSwzwgDuf29m/4OqcENe1nbPancZDfA+tCdppdeM9NCSizO5+g8dhouDNohTsGKYejs9 Bw3rCIStGxXKiBYgLPlmG1gczVqa2V9g7GU+366YnBLiKqigDx9lKdFzqOM3gv4E2Tl8 ncSt1iBNKt2eR4tPLuRVE394z6b8nprOs5GMoF9C2cgP0vCRQhgzegKd7jATaUJjRuwA Jk9A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SHB0Uj7W; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id f15-20020a05640214cf00b00508da09b7f5si2359874edx.624.2023.04.21.04.27.04 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 21 Apr 2023 04:27:04 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SHB0Uj7W; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 AA8F83857010 for ; Fri, 21 Apr 2023 11:26:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AA8F83857010 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682076401; bh=/4VfgTAxCZzWhotHdU/J39uLy/VfR3XAudXw60Qvv4k=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=SHB0Uj7W25biDucpWFf+mjJpj5Tm3a7hVszZxt0oPjhv28VdeaAOANQpZHje1N8Ym XWTi2NtDnbZ84vkICzQulCLFcXgWuvQS3Gx3CvRpcWMOFT2iG364f6ZVuYKdI+o43i 4y5HrGXJBxyhLVPRzBc6RUYSQkBxIdxsE23Q+DNI= 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 [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 94EA53857722 for ; Fri, 21 Apr 2023 11:25:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 94EA53857722 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 CF60A21976 for ; Fri, 21 Apr 2023 11:25:27 +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 BB76813456 for ; Fri, 21 Apr 2023 11:25:27 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id KaKNLKdyQmQ+EgAAMHmgww (envelope-from ) for ; Fri, 21 Apr 2023 11:25:27 +0000 Date: Fri, 21 Apr 2023 13:25:27 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH 3/3] Use correct CFG orders for DF worklist processing MIME-Version: 1.0 Message-Id: <20230421112527.BB76813456@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 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?1763784968774009023?= X-GMAIL-MSGID: =?utf-8?q?1763784968774009023?= This adjusts the remaining three RPO computes in DF. The DF_FORWARD problems should use a RPO on the forward graph, the DF_BACKWARD problems should use a RPO on the inverted graph. Conveniently now inverted_rev_post_order_compute computes a RPO. We still use post_order_compute and reverse its order for its side-effect of deleting unreachable blocks. This resuls in an overall reduction on visited blocks on cc1files by 5.2%. Because on the reverse CFG most regions are irreducible, there's few cases the number of visited blocks increases. For the set of cc1files I have this is for et-forest.i, graph.i, hwint.i, tree-ssa-dom.i, tree-ssa-loop-ch.i and tree-ssa-threadedge.i. For tree-ssa-dse.i it's off-noise and I've more closely investigated and figured it is really bad luck due to the irreducibility. Bootstrapped and tested on x86_64-unknown-linux-gnu and the series pushed. * df-core.cc (df_analyze): Compute RPO on the reverse graph for DF_BACKWARD problems. (loop_post_order_compute): Rename to ... (loop_rev_post_order_compute): ... this, compute a RPO. (loop_inverted_post_order_compute): Rename to ... (loop_inverted_rev_post_order_compute): ... this, compute a RPO. (df_analyze_loop): Use RPO on the forward graph for DF_FORWARD problems, RPO on the inverted graph for DF_BACKWARD. --- gcc/df-core.cc | 36 ++++++++++++++++++++---------------- 1 file changed, 20 insertions(+), 16 deletions(-) diff --git a/gcc/df-core.cc b/gcc/df-core.cc index 27123645da5..d4812b04a7c 100644 --- a/gcc/df-core.cc +++ b/gcc/df-core.cc @@ -1259,14 +1259,18 @@ df_analyze (void) 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); /* 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]; + df->n_blocks = post_order_compute (df->postorder_inverted, true, true); + for (int i = 0; i < df->n_blocks / 2; ++i) + std::swap (df->postorder_inverted[i], + df->postorder_inverted[df->n_blocks - 1 - i]); + /* For DF_BACKWARD use a RPO on the reverse graph. */ + df->postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + int n = inverted_rev_post_order_compute (cfun, df->postorder); + gcc_assert (n == df->n_blocks); for (int i = 0; i < df->n_blocks; i++) bitmap_set_bit (current_all_blocks, df->postorder[i]); @@ -1305,11 +1309,11 @@ df_analyze (void) Returns the number of blocks which is always loop->num_nodes. */ static int -loop_post_order_compute (int *post_order, class loop *loop) +loop_rev_post_order_compute (int *post_order, class loop *loop) { edge_iterator *stack; int sp; - int post_order_num = 0; + int post_order_num = loop->num_nodes - 1; /* Allocate stack for back-tracking up CFG. */ stack = XNEWVEC (edge_iterator, loop->num_nodes + 1); @@ -1342,13 +1346,13 @@ loop_post_order_compute (int *post_order, class loop *loop) time, check its successors. */ stack[sp++] = ei_start (dest->succs); else - post_order[post_order_num++] = dest->index; + post_order[post_order_num--] = dest->index; } else { if (ei_one_before_end_p (ei) && src != loop_preheader_edge (loop)->src) - post_order[post_order_num++] = src->index; + post_order[post_order_num--] = src->index; if (!ei_one_before_end_p (ei)) ei_next (&stack[sp - 1]); @@ -1359,19 +1363,19 @@ loop_post_order_compute (int *post_order, class loop *loop) free (stack); - return post_order_num; + return loop->num_nodes; } /* 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 int -loop_inverted_post_order_compute (int *post_order, class loop *loop) +loop_inverted_rev_post_order_compute (int *post_order, class loop *loop) { basic_block bb; edge_iterator *stack; int sp; - int post_order_num = 0; + int post_order_num = loop->num_nodes - 1; /* Allocate stack for back-tracking up CFG. */ stack = XNEWVEC (edge_iterator, loop->num_nodes + 1); @@ -1408,13 +1412,13 @@ loop_inverted_post_order_compute (int *post_order, class loop *loop) time, check its predecessors. */ stack[sp++] = ei_start (pred->preds); else - post_order[post_order_num++] = 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[post_order_num++] = bb->index; + post_order[post_order_num--] = bb->index; if (!ei_one_before_end_p (ei)) ei_next (&stack[sp - 1]); @@ -1424,7 +1428,7 @@ loop_inverted_post_order_compute (int *post_order, class loop *loop) } free (stack); - return post_order_num; + return loop->num_nodes; } @@ -1438,8 +1442,8 @@ df_analyze_loop (class loop *loop) df->postorder = XNEWVEC (int, loop->num_nodes); df->postorder_inverted = XNEWVEC (int, loop->num_nodes); - df->n_blocks = loop_post_order_compute (df->postorder, loop); - int n = loop_inverted_post_order_compute (df->postorder_inverted, loop); + df->n_blocks = loop_rev_post_order_compute (df->postorder_inverted, loop); + int n = loop_inverted_rev_post_order_compute (df->postorder, loop); gcc_assert ((unsigned) df->n_blocks == loop->num_nodes); gcc_assert ((unsigned) n == loop->num_nodes);