From patchwork Thu Aug 24 15:07:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Filip Kastl X-Patchwork-Id: 136844 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6358:9d9b:b0:139:fa0d:b2d with SMTP id d27csp171044rwo; Thu, 24 Aug 2023 08:07:56 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFkYyHmKYgpVLZRhEUSwzZDv98xux5IxbBkyJuCLzQzT5eLbR07lpFT1rWa9osTY85eq8ws X-Received: by 2002:a17:906:32d3:b0:9a1:8a54:145f with SMTP id k19-20020a17090632d300b009a18a54145fmr9128172ejk.40.1692889676214; Thu, 24 Aug 2023 08:07:56 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1692889676; cv=none; d=google.com; s=arc-20160816; b=NM4eILd+jA4w5rFwWs7Q7XZ4Qf0QKogu3WmuAQH6pjrRkmta3bSHTgQTwYo4oC6XMd tQy/TZLzynLho5saMTXuomafKKfTxPMJQ+2APJilHATvdSiXpUc7ys4FkneDkOYsUGQS UyPrfvhhkrVqlo6IT3zxT/l6UHcoEteHA9A6Sxbxu1U/KACNyrPe9p/QcJbwzFzS7oOQ 5AbPDA0P949c8+gm8pCUL8iXNLW4kdt5EA0KPZ9sXrhYHDWSs4cj1zs5lGaIOXJEGCXx B5DXelsaX8f5oT+q2SqDTROp9FX2bf0KjEOVUn56/9kR37mbvOCZAH/0t46V5xY1tc1b fWEg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:content-disposition:mime-version :message-id:subject:cc:to:from:date:dkim-signature:dkim-signature :dmarc-filter:delivered-to; bh=fZzFl65TAmklwKjQQsnuBl4UlsCRX9rDYaF3zRdqd5I=; fh=PSRXF+gcUawGsZEw3DtUm2yz/QDGDPc/I/j0nFaMaL8=; b=HFfpxHDrRCqD93iOi8NBBj0tCOrF1ohLuQWCb7YfmdQkdgNO1CVPi+taDXlmf2IEvF bs97pfu2nCSeSirLld8XDPeYpaAsuITjBXCk8syvQdmma8ijAzT/B4WaOcSvHZLEAc5d QsFzfvMR/GXFCz5Y9XkYvzfSUfV8AsUonag84XocVT0iqOrBXAFDqRbw9HNbPtZX7vL0 ojscLBYPcLUUpAEtY5gytxYLePtTFNOBdzIxlHvBB3q+OFc1i+V25praqRNhx66799ox IXHlo+IZATuCvDwtictpRcJNjbksP/zXavfjs2nF3MAqXEZMzbNXs4kkoVGHHI6HtM8C L6kg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@suse.cz header.s=susede2_rsa header.b=0wrKRmVZ; dkim=neutral (no key) header.i=@gcc.gnu.org header.b=qBiN1OWL; 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" Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id qh25-20020a170906ecb900b0098df03ffa69si10799593ejb.421.2023.08.24.08.07.55 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 24 Aug 2023 08:07:56 -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=@suse.cz header.s=susede2_rsa header.b=0wrKRmVZ; dkim=neutral (no key) header.i=@gcc.gnu.org header.b=qBiN1OWL; 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" Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6903F38555A3 for ; Thu, 24 Aug 2023 15:07:48 +0000 (GMT) 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 2D8C43858C53 for ; Thu, 24 Aug 2023 15:07:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2D8C43858C53 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz 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 1424A21980; Thu, 24 Aug 2023 15:07:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1692889631; h=from:from:reply-to:reply-to:date:date:message-id:message-id:to:to: cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=fZzFl65TAmklwKjQQsnuBl4UlsCRX9rDYaF3zRdqd5I=; b=0wrKRmVZlRQeDbZ6UQhBiK8klnoi/ka3iC8NR/qPFaaocI1+uvrcSVOU1eUb6RFXeARNEp WCABh3NeHvIxfMmeFSECjIqSETQTgcMJ1qZUSp8Fxx5pr5MAln/Vu7nLvmjTSiyrFNEiYV LfS4pg52vpPCqJ6nfSiZGaRqitZEvIo= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1692889631; h=from:from:reply-to:reply-to:date:date:message-id:message-id:to:to: cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=fZzFl65TAmklwKjQQsnuBl4UlsCRX9rDYaF3zRdqd5I=; b=qBiN1OWLH5EhMES3A7nsxGtI/IkuoGEkpqflUYv1UJukmNrM8DAhfU9HfFWKAaPTDskk47 PVmOftd/3F9ovVBw== 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 06E581336F; Thu, 24 Aug 2023 15:07:11 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id tZGoAR9y52R6OAAAMHmgww (envelope-from ); Thu, 24 Aug 2023 15:07:11 +0000 Date: Thu, 24 Aug 2023 17:07:10 +0200 From: Filip Kastl To: Gcc-patches Cc: mjambor@suse.cz, hubicka@ucw.cz, rguenther@suse.de Subject: [RFC] gimple ssa: SCCP - A new PHI optimization pass Message-ID: MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_LOTSOFHASH, KAM_SHORT, SPF_HELO_NONE, SPF_SOFTFAIL, 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: fkastl@suse.cz Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1775123485123656131 X-GMAIL-MSGID: 1775123485123656131 Hi, As a part of my bachelor thesis under the supervision of Honza (Jan Hubicka), I implemented a new PHI elimination algorithm into GCC. The algorithm is described in the following article: Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. (2013). Simple and Efficient Construction of Static Single Assignment Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 In the article the PHI elimination algorithm is only considered a part of another algorithm. However, with Honza we tried running the algorithm as a standalone pass and found that there is a surprisingly big number of PHI functions it is able to remove -- sometimes even ~13% of PHI functions or more. This email contains a patch with the pass and with the placement in passes.def we used to measure this. Do you think that the pass is worthy of inclusion into upstream GCC? What are some things that I should change? Should I try to put the pass in different places in passes.def? Things I already know I'd like to change: - Split the patch into two (one for sccp, one for the utility functions) - Change the name SCCP to something else since there already is a pass with that name (any suggestions?) - Add a comment into sccp.cc explaining the algorithm I successfully bootstrapped and tested GCC with the patch applied (with the commit 3b691e0190c6e7291f8a52e1e14d8293a28ff4ce checked out). Here are my measurements. I measured the number of PHIs before the PHI elimination algorithm was run and after it was run. I measured on the standard 2017 benchmarks with -O3. Since the pass is present in passes.def twice, results of the first run are marked (1) and results of the second are marked (2). Honza also did measurements with profile feedback and got even bigger percentages. 500.perlbench_r Started with (1) 30287 Ended with (1) 26188 Removed PHI % (1) 13.53385941162875161000 Started with (2) 38005 Ended with (2) 37897 Removed PHI % (2) .28417313511380081600 502.gcc_r Started with (1) 148187 Ended with (1) 140292 Removed PHI % (1) 5.32772780338356266100 Started with (2) 211479 Ended with (2) 210635 Removed PHI % (2) .39909399987705635100 505.mcf_r Started with (1) 341 Ended with (1) 303 Removed PHI % (1) 11.14369501466275659900 Started with (2) 430 Ended with (2) 426 Removed PHI % (2) .93023255813953488400 523.xalancbmk_r Started with (1) 62514 Ended with (1) 57785 Removed PHI % (1) 7.56470550596666346800 Started with (2) 132561 Ended with (2) 131726 Removed PHI % (2) .62989868815111533600 531.deepsjeng_r Started with (1) 1388 Ended with (1) 1250 Removed PHI % (1) 9.94236311239193083600 Started with (2) 1887 Ended with (2) 1879 Removed PHI % (2) .42395336512983571900 541.leela_r Started with (1) 3332 Ended with (1) 2994 Removed PHI % (1) 10.14405762304921968800 Started with (2) 4372 Ended with (2) 4352 Removed PHI % (2) .45745654162854528900 Here is the patch: -- >8 -- This patch introduces two things: - A new PHI elimination pass (major) - New utility functions for passes that replace one ssa name with a different one (minor) Strongly-connected copy propagation (SCCP) pass The PHI elimination pass is a lightweight optimization pass based on strongly-connected components. Some set of PHIs may be redundant because the PHIs only refer to each other or to a single value from outside the set. This pass finds and eliminates these sets. As a bonus the pass also does some basic copy propagation because it considers a copy statement to be a PHI with a single argument. SCCP uses an algorithm from this article: Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. (2013). Simple and Efficient Construction of Static Single Assignment Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 cleanup_after_replace and cleanup_after_all_replaces_done Whenever you replace all uses of an ssa name by a different ssa name, some GCC internal structures have to be updated. To streamline this process, the patch adds the cleanup_after_replace function that should be called after an ssa name is replaced by a different one and the cleanup_after_all_replaces_done that should be called before a pass that replaced one or more ssa names exits. The SCCP pass uses these functions. Signed-off-by: Filip Kastl gcc/ChangeLog: * Makefile.in: Added sccp pass. * passes.def: Added sccp pass to early and late optimizations. * tree-pass.h (make_pass_sccp): Added sccp pass. * tree-ssa-propagate.cc (cleanup_after_replace): New function. (cleanup_after_all_replaces_done): New function. * tree-ssa-propagate.h (cleanup_after_replace): New function. (cleanup_after_all_replaces_done): New function. * sccp.cc: New file. --- gcc/Makefile.in | 1 + gcc/passes.def | 2 + gcc/sccp.cc | 722 ++++++++++++++++++++++++++++++++++++++ gcc/tree-pass.h | 1 + gcc/tree-ssa-propagate.cc | 62 ++++ gcc/tree-ssa-propagate.h | 7 + 6 files changed, 795 insertions(+) create mode 100644 gcc/sccp.cc diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 78779546459..7c34eb6ceda 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1706,6 +1706,7 @@ OBJS = \ tree-ssa-forwprop.o \ tree-ssa-ifcombine.o \ tree-ssa-live.o \ + sccp.o \ tree-ssa-loop-ch.o \ tree-ssa-loop-im.o \ tree-ssa-loop-ivcanon.o \ diff --git a/gcc/passes.def b/gcc/passes.def index ef5a21afe49..4c94f9cec8b 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -96,6 +96,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); NEXT_PASS (pass_phiopt, true /* early_p */); + NEXT_PASS (pass_sccp); NEXT_PASS (pass_tail_recursion); NEXT_PASS (pass_if_to_switch); NEXT_PASS (pass_convert_switch); @@ -271,6 +272,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_tsan); NEXT_PASS (pass_dse, true /* use DR analysis */); NEXT_PASS (pass_dce); + NEXT_PASS (pass_sccp); /* Pass group that runs when 1) enabled, 2) there are loops in the function. Make sure to run pass_fix_loops before to discover/remove loops before running the gate function diff --git a/gcc/sccp.cc b/gcc/sccp.cc new file mode 100644 index 00000000000..86a79303902 --- /dev/null +++ b/gcc/sccp.cc @@ -0,0 +1,722 @@ +/* Strongly connected copy propagation pass for the GNU compiler. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Filip Kastl + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "vec.h" +#include "hash-set.h" +#include +#include "ssa-iterators.h" +#include "gimple-fold.h" +#include "gimplify.h" +#include "tree-cfg.h" +#include "tree-ssa-propagate.h" + +/* State of vertex during tarjan computation. + + unvisited Vertex hasn't yet been popped from worklist. + vopen DFS has visited vertex for the first time. Vertex has been put on + Tarjan stack. + closed DFS has backtracked through vertex. At this point, vertex doesn't + have any unvisited neighbors. + in_scc Vertex has been popped from tarjan stack. */ + +enum vstate +{ + unvisited, + vopen, + closed, + in_scc +}; + +/* Information about a vertex used by tarjan. */ + +struct vertex +{ + vstate state; + unsigned index; + unsigned lowlink; + gimple* stmt; +}; + +static bool +stmt_may_generate_copy (gimple *stmt) +{ + if (gimple_code (stmt) == GIMPLE_PHI) + { + gphi *phi = as_a (stmt); + + /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */ + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi))) + { + return false; + } + + unsigned i; + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + tree op = gimple_phi_arg_def (phi, i); + if (TREE_CODE (op) == SSA_NAME && + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) + { + return false; + } + } + + return true; + } + + if (gimple_code (stmt) != GIMPLE_ASSIGN) + { + return false; + } + + /* If the statement has volatile operands, it won't generate a + useful copy. */ + if (gimple_has_volatile_ops (stmt)) + { + return false; + } + + /* Statements with loads and/or stores will never generate a useful copy. */ + if (gimple_store_p (stmt) || gimple_assign_load_p (stmt)) + { + return false; + } + + if (!gimple_assign_single_p (stmt)) + { + return false; + } + + tree lhs = gimple_assign_lhs (stmt); + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + { + return false; + } + + /* If the assignment is from a constant it generates a useful copy. */ + if (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) + { + return true; + } + + /* Otherwise, the only statements that generate useful copies are + assignments whose single SSA use doesn't flow through abnormal + edges. */ + tree rhs = single_ssa_tree_operand (stmt, SSA_OP_USE); + + if (!is_gimple_val (gimple_assign_rhs1 (stmt))) + { + return false; + } + + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) + { + return false; + } + + if (!rhs) + { + return false; + } + + return true; +} + +/* Set 'using' flag of gimple statement to true. + If the flag isn't set, tarjan will ignore the statement. */ + +static void +tarjan_set_using (gimple* stmt) +{ + gimple_set_plf (stmt, GF_PLF_1, true); +} + +/* Clear 'using' flag of gimple statement to false. */ + +static void +tarjan_clear_using (gimple* stmt) +{ + gimple_set_plf (stmt, GF_PLF_1, false); +} + +/* Return value of 'using' flag of gimple statement. */ + +static bool +tarjan_is_using (gimple* stmt) +{ + return gimple_plf (stmt, GF_PLF_1); +} + +/* Set 'vxnum' (vertex number) of statement. Before computing SCCs, tarjan + assigns unique vxnums to statements that it will use. */ + +static void +tarjan_set_vxnum (gimple* stmt, unsigned num) +{ + gimple_set_uid (stmt, num); +} + +/* Return 'vxnum' (vertex number) of statement. */ + +static unsigned +tarjan_vxnum (gimple* stmt) +{ + return gimple_uid (stmt); +} + +/* Create and initialize vertex struct for each given statement. */ + +static auto_vec +tarjan_stmts_to_vertices (auto_vec &stmts) +{ + auto_vec result; + for (gimple *stmt : stmts) + { + vertex v; + v.state = unvisited; + v.index = 0; + v.lowlink = 0; + v.stmt = stmt; + + result.safe_push (v); + } + return result; +} + +static void +tarjan_visit_neighbor (tree neigh_tree, unsigned parent_vxnum, + auto_vec &vs, auto_vec &worklist) +{ + if (TREE_CODE (neigh_tree) != SSA_NAME) + return; /* Skip any neighbor that isn't an SSA name. */ + + gimple *neigh_stmt = SSA_NAME_DEF_STMT (neigh_tree); + + /* Skip neighbors outside the induced subgraph that Tarjan currently works + with. */ + if (!tarjan_is_using (neigh_stmt)) + return; + unsigned neigh_vxnum = tarjan_vxnum (neigh_stmt); + + gcc_checking_assert (stmt_may_generate_copy (neigh_stmt)); + + vstate neigh_state = vs[neigh_vxnum].state; + vstate parent_state = vs[parent_vxnum].state; + if (parent_state == vopen) /* We're currently opening parent. */ + { + /* Put unvisited neighbors on worklist. Update lowlink of parent + vertex according to indices of neighbors present on stack. */ + switch (neigh_state) + { + case unvisited: + worklist.safe_push (neigh_vxnum); + break; + case vopen: + case closed: + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, + vs[neigh_vxnum].index); + break; + case in_scc: + /* Ignore these edges. */ + break; + } + } + else if (parent_state == closed) /* We're currently closing parent. */ + { + /* Update lowlink of parent vertex according to lowlinks of + children of parent (in terms of DFS tree). */ + if (neigh_state == closed) + { + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, + vs[neigh_vxnum].lowlink); + } + } +} + +/* Nonrecursive implementation of Tarjan's algorithm for computing strongly + connected components in a graph. Statements are vertices. Edges lead from a + copy stmt p using another copy stmt q to the stmt being used (p -> q when q + is operand of p). + + Considers only the subgraph induced by given statements. */ + +static auto_vec> +tarjan_compute_sccs (auto_vec ©_stmts) +{ + auto_vec> sccs; + auto_vec worklist; /* DFS stack. */ + auto_vec stack; /* Tarjan stack. */ + unsigned curr_index = 0; + + auto_vec vs = tarjan_stmts_to_vertices (copy_stmts); + + /* Mark the subgraph induced by 'copy_stmts' and index it by vxnums. */ + unsigned i; + for (i = 0; i < vs.length (); i++) + { + gimple *stmt = vs[i].stmt; + tarjan_set_using (stmt); + tarjan_set_vxnum (stmt, i); + } + + /* Put all vertices on worklist. */ + for (i = 0; i < vs.length (); i++) + { + worklist.safe_push (i); + } + + /* Worklist loop. */ + while (!worklist.is_empty ()) + { + unsigned i = worklist.pop(); + gimple *stmt = vs[i].stmt; + vstate state = vs[i].state; + + if (state == unvisited) + { + vs[i].state = vopen; + + /* Assign index to this vertex. */ + vs[i].index = curr_index; + vs[i].lowlink = curr_index; + curr_index++; + + /* Put vertex on stack and also on worklist to be closed later. */ + stack.safe_push (i); + worklist.safe_push (i); + } + else if (state == vopen) + { + vs[i].state = closed; + } + + /* Visit neighbors of this vertex. */ + tree op; + gphi *phi; + switch (gimple_code (stmt)) + { + case GIMPLE_PHI: + phi = as_a (stmt); + unsigned j; + for (j = 0; j < gimple_phi_num_args (phi); j++) + { + op = gimple_phi_arg_def (phi, j); + tarjan_visit_neighbor (op, i, vs, worklist); + } + break; + case GIMPLE_ASSIGN: + op = gimple_assign_rhs1 (stmt); + tarjan_visit_neighbor (op, i, vs, worklist); + break; + default: + gcc_unreachable (); + } + + /* If we've just closed a root vertex of an scc, pop scc from stack. */ + if (state == vopen && vs[i].lowlink == vs[i].index) + { + vec scc = vNULL; + + unsigned j; + do + { + j = stack.pop(); + scc.safe_push (vs[j].stmt); + vs[j].state = in_scc; + } + while (j != i); + + sccs.safe_push (scc); + } + } + + if (!stack.is_empty ()) + { + gcc_unreachable(); + } + + /* Clear copy stmts' 'using' flags. */ + for (vertex v : vs) + { + gimple *s = v.stmt; + tarjan_clear_using (s); + } + + return sccs; +} + +static void +replace_use_by (tree get_replaced, tree replace_by, bitmap need_eh_cleanup, + bitmap need_ab_cleanup, vec stmts_to_fixup) +{ + /* Replace each occurence of 'get_replaced' by 'replace_by'. */ + use_operand_p use_p; + imm_use_iterator iter; + gimple *use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, iter, get_replaced) + { + bool was_noreturn = false; + bool can_make_abnormal_goto = false; + if (is_gimple_call (use_stmt)) + { + was_noreturn = gimple_call_noreturn_p (use_stmt); + can_make_abnormal_goto = stmt_can_make_abnormal_goto (use_stmt); + } + + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, unshare_expr (replace_by)); + + /* Recompute tree invariant. */ + if (gimple_assign_single_p (use_stmt)) + { + tree rhs = gimple_assign_rhs1 (use_stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + /* Cleanup. */ + gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); + fold_stmt (&gsi); + gimple_set_modified (gsi_stmt (gsi), true); + cleanup_after_replace (use_stmt, gsi_stmt (gsi), need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup, + can_make_abnormal_goto, was_noreturn); + } +} + +/* Modify all usages of PHIs in a given SCC to instead reference a given + variable. */ + +static void +replace_scc_by_value (vec scc, tree replace_by, bitmap + need_eh_cleanup, bitmap need_ab_cleanup, vec + stmts_to_fixup) +{ + // DEBUG + if (dump_file) + { + fprintf (dump_file, "Replacing SCC of length %d\n", scc.length ()); + } + + for (gimple *stmt : scc) + { + tree get_replaced = gimple_get_lhs (stmt); + replace_use_by (get_replaced, replace_by, need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup); + } +} + +/* Remove all PHIs with zero uses. */ + +static void +remove_zero_uses_phis () +{ + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi);) + { + gphi *phi = pi.phi (); + tree ssa_name = gimple_phi_result (phi); + if (has_zero_uses (ssa_name)) + { + /* Note that remove_phi_node() also frees SSA name. */ + remove_phi_node (&pi, true); + } + else + gsi_next (&pi); + } + } +} + +static void +sccp_visit_op (tree op, hash_set &outer_ops, hash_set &scc_set, + bool &is_inner, tree &last_outer_op) +{ + bool op_in_scc = false; + + if (TREE_CODE (op) == SSA_NAME) + { + gimple *op_stmt = SSA_NAME_DEF_STMT (op); + if (scc_set.contains (op_stmt)) + op_in_scc = true; + } + + if (!op_in_scc) + { + outer_ops.add (op); + last_outer_op = op; + is_inner = false; + } +} + +/* Apply Braun et al.'s algorithm on a given set of statements. Treat copy + statements as PHI functions with a single argument. + Main function of this pass. */ + +static void +sccp_propagate (auto_vec ©_stmts) +{ + auto_vec> worklist; + worklist = tarjan_compute_sccs (copy_stmts); + + /* Prepare data structs for cleanup after stmt modification. */ + bitmap need_eh_cleanup = BITMAP_ALLOC (NULL); + bitmap need_ab_cleanup = BITMAP_ALLOC (NULL); + vec stmts_to_fixup = vNULL; + + while (!worklist.is_empty ()) + { + vec scc = worklist.pop (); + + auto_vec inner; + hash_set outer_ops; + tree last_outer_op = NULL_TREE; + + /* Prepare hash set of PHIs in scc to query later. */ + hash_set scc_set; + for (gimple *stmt : scc) + { + scc_set.add (stmt); + } + + for (gimple *stmt : scc) + { + bool is_inner = true; + + gphi *phi; + tree op; + switch (gimple_code (stmt)) + { + case GIMPLE_PHI: + phi = as_a (stmt); + unsigned j; + for (j = 0; j < gimple_phi_num_args (phi); j++) + { + op = gimple_phi_arg_def (phi, j); + sccp_visit_op (op, outer_ops, scc_set, is_inner, + last_outer_op); + } + break; + case GIMPLE_ASSIGN: + op = gimple_assign_rhs1 (stmt); + sccp_visit_op (op, outer_ops, scc_set, is_inner, + last_outer_op); + break; + default: + gcc_unreachable (); + } + + if (is_inner) + { + inner.safe_push (stmt); + } + } + + if (outer_ops.elements () == 1) + { + /* The only operand in outer_ops. */ + tree outer_op = last_outer_op; + + replace_scc_by_value (scc, outer_op, need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup); + } + else if (outer_ops.elements () > 1) + { + /* Add inner sccs to worklist. */ + auto_vec> inner_sccs = tarjan_compute_sccs (inner); + for (vec inner_scc : inner_sccs) + { + worklist.safe_push (inner_scc); + } + } + else + { + gcc_unreachable (); + } + + scc.release (); + } + + cleanup_after_all_replaces_done (need_eh_cleanup, need_ab_cleanup, + stmts_to_fixup); + + /* Remove data structs for cleanup after stmt modification. */ + BITMAP_FREE (need_eh_cleanup); + BITMAP_FREE (need_ab_cleanup); + stmts_to_fixup.release (); + + /* We want to remove dead MEM PHIs because memory is in FUD SSA and the dead + PHIs would break the FUD property. */ + remove_zero_uses_phis (); +} + +/* Return all statements in cfun that may be useful. */ + +static auto_vec +get_all_stmt_may_generate_copy (void) +{ + auto_vec result; + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *s = gsi_stmt (gsi); + if (stmt_may_generate_copy (s)) + result.safe_push (s); + } + + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + { + gimple *s = pi.phi (); + if (stmt_may_generate_copy (s)) + result.safe_push (s); + } + } + + return result; +} + +/* Called when pass execution starts. */ + +static void +init_sccp (void) +{ + // Clear 'tarjan using' flag on all statements + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple* stmt = gsi_stmt (gsi); + tarjan_clear_using (stmt); + } + + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + { + gimple *stmt = pi.phi (); + tarjan_clear_using (stmt); + } + } +} + +/* Called before pass execution ends. */ + +static void +finalize_sccp (void) +{ + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_purge_dead_eh_edges (bb); + } +} + +namespace { + +const pass_data pass_data_sccp = +{ + GIMPLE_PASS, /* type */ + "sccp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_NONE, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ +}; + +class pass_sccp : public gimple_opt_pass +{ +public: + pass_sccp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_sccp, ctxt) + {} + + /* opt_pass methods: */ + virtual bool gate (function *) { return true; } + virtual unsigned int execute (function *); + opt_pass * clone () final override { return new pass_sccp (m_ctxt); } +}; // class pass_sccp + +unsigned +pass_sccp::execute (function *) +{ + // DEBUG + if (dump_file) + { + int phis = 0; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + phis++; + } + fprintf (dump_file, "Started with %d PHIs\n", phis); + } + + init_sccp (); + auto_vec stmts = get_all_stmt_may_generate_copy (); + sccp_propagate (stmts); + finalize_sccp (); + + // DEBUG + if (dump_file) + { + int phis = 0; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + phis++; + } + fprintf (dump_file, "Ended with %d PHIs\n", phis); + } + + return 0; +} + +} // anon namespace + +gimple_opt_pass * +make_pass_sccp (gcc::context *ctxt) +{ + return new pass_sccp (ctxt); +} diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 57865cdfc42..ac1d8848c25 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -398,6 +398,7 @@ extern gimple_opt_pass *make_pass_iv_optimize (gcc::context *ctxt); extern gimple_opt_pass *make_pass_tree_loop_done (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_sccp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); diff --git a/gcc/tree-ssa-propagate.cc b/gcc/tree-ssa-propagate.cc index cb68b419b8c..f70240dcd2f 100644 --- a/gcc/tree-ssa-propagate.cc +++ b/gcc/tree-ssa-propagate.cc @@ -1297,3 +1297,65 @@ clean_up_loop_closed_phi (function *fun) return 0; } + +void +cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap need_eh_cleanup, + bitmap need_ab_cleanup, vec stmts_to_fixup, + bool can_make_abnormal_goto, bool was_noreturn) +{ + basic_block bb = stmt->bb; + + /* If we cleaned up EH information from the statement, + remove EH edges. */ + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) + bitmap_set_bit (need_eh_cleanup, bb->index); + + /* If we turned a call with possible abnormal control transfer + into one that doesn't, remove abnormal edges. */ + if (can_make_abnormal_goto + && !stmt_can_make_abnormal_goto (stmt)) + bitmap_set_bit (need_ab_cleanup, bb->index); + + /* If we turned a not noreturn call into a noreturn one + schedule it for fixup. */ + if (!was_noreturn + && is_gimple_call (stmt) + && gimple_call_noreturn_p (stmt)) + stmts_to_fixup.safe_push (stmt); + + if (gimple_assign_single_p (stmt)) + { + tree rhs = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + update_stmt_if_modified (stmt); +} + +void +cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap + need_ab_cleanup, vec stmts_to_fixup) +{ + if (!bitmap_empty_p (need_eh_cleanup)) + gimple_purge_all_dead_eh_edges (need_eh_cleanup); + if (!bitmap_empty_p (need_ab_cleanup)) + gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); + + /* Fixup stmts that became noreturn calls. This may require splitting + blocks and thus isn't possible during the dominator walk. Do this + in reverse order so we don't inadvertedly remove a stmt we want to + fixup by visiting a dominating now noreturn call first. */ + while (!stmts_to_fixup.is_empty ()) + { + gimple *stmt = stmts_to_fixup.pop (); + if (dump_file && dump_flags & TDF_DETAILS) + { + fprintf (dump_file, "Fixing up noreturn call "); + print_gimple_stmt (dump_file, stmt, 0); + fprintf (dump_file, "\n"); + } + fixup_noreturn_call (stmt); + } +} diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h index 29bde37add9..a645baeacf4 100644 --- a/gcc/tree-ssa-propagate.h +++ b/gcc/tree-ssa-propagate.h @@ -72,6 +72,13 @@ extern void propagate_value (use_operand_p, tree); extern void replace_exp (use_operand_p, tree); extern void propagate_tree_value (tree *, tree); extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree); +extern void cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap + need_eh_cleanup, bitmap need_ab_cleanup, + vec stmts_to_fixup, bool + can_make_abnormal_goto, bool was_noreturn); +extern void cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap + need_ab_cleanup, vec + stms_to_fixup); /* Public interface into the SSA propagation engine. Clients should inherit from this class and provide their own visitors. */