From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 6C0CA3858C53 for ; Thu, 24 Aug 2023 15:47:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6C0CA3858C53 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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 7B1F621890; Thu, 24 Aug 2023 15:47:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1692892040; h=from:from: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: in-reply-to:in-reply-to:references:references; bh=NQf6kqjDUUV2/bNeN7CQPRazA2bbX5S/XlP2MgmtZPE=; b=NqgC84jalplYkeF4NPLgPNR/s+GNq33CUkoEtl6uA0SZO2as4rHufE2dWtC9Rq4w6nh/15 5BIeBDgAXTh0iAVsvUV9y/PoGV7iOiIjhBhSLfzKkbhxlzeNa4phJU/H4pzqvApPJNB6zU dwH+AVwz31hp9RSXeYc9Rl33jh3q7Oo= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1692892040; h=from:from: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: in-reply-to:in-reply-to:references:references; bh=NQf6kqjDUUV2/bNeN7CQPRazA2bbX5S/XlP2MgmtZPE=; b=wMTwx6DPhQNgQVbUyQC1b2XEBz1gZhkeZQ+JwpxpjeV2OtD6qjYbWTeRPhLQ7OsOMPc5yB hc5woyVsafTHUpAQ== 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 5E92B132F2; Thu, 24 Aug 2023 15:47:20 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id i2kUF4h752SDSwAAMHmgww (envelope-from ); Thu, 24 Aug 2023 15:47:20 +0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [RFC] gimple ssa: SCCP - A new PHI optimization pass Date: Thu, 24 Aug 2023 17:47:09 +0200 Message-Id: <084BC52B-00DE-4496-8B85-9211C3AD8394@suse.de> References: Cc: Gcc-patches , mjambor@suse.cz, hubicka@ucw.cz In-Reply-To: To: fkastl@suse.cz X-Mailer: iPhone Mail (20G75) X-Spam-Status: No, score=-11.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_PASS,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 List-Id: > Am 24.08.2023 um 17:07 schrieb Filip Kastl : >=20 > =EF=BB=BFHi, >=20 > As a part of my bachelor thesis under the supervision of Honza (Jan Hubick= a), I > implemented a new PHI elimination algorithm into GCC. The algorithm is > described in the following article: >=20 > Braun, M., Buchwald, S., Hack, S., Lei=C3=9Fa, 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 >=20 > 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 m= ore. > This email contains a patch with the pass and with the placement in passes= .def > we used to measure this. >=20 > Do you think that the pass is worthy of inclusion into upstream GCC? What a= re > some things that I should change? Should I try to put the pass in differen= t > places in passes.def? The most obvious places would be right after SSA construction and before RTL= expansion. Can you provide measurements for those positions? Can the pass= somehow be used as part of propagations like during value numbering? Richard=20 > 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 wit= h > that name (any suggestions?) > - Add a comment into sccp.cc explaining the algorithm >=20 > I successfully bootstrapped and tested GCC with the patch applied (with th= e > commit 3b691e0190c6e7291f8a52e1e14d8293a28ff4ce checked out).=20 >=20 > 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 stan= dard > 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 mark= ed > (2). Honza also did measurements with profile feedback and got even bigger= > percentages. >=20 > 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 >=20 > 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 >=20 > 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 >=20 > 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 >=20 > 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 >=20 > 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 >=20 > Here is the patch: >=20 > -- >8 -- >=20 > 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) >=20 > Strongly-connected copy propagation (SCCP) pass >=20 > 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. >=20 > SCCP uses an algorithm from this article: > Braun, M., Buchwald, S., Hack, S., Lei=C3=9Fa, 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 >=20 > cleanup_after_replace and cleanup_after_all_replaces_done >=20 > 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. >=20 > Signed-off-by: Filip Kastl >=20 > gcc/ChangeLog: >=20 > * 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 >=20 > 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 =3D \ > 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 p= ut on > + Tarjan stack. > + closed DFS has backtracked through vertex. At this point, vertex d= oesn'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) =3D=3D GIMPLE_PHI) > + { > + gphi *phi =3D 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 =3D 0; i < gimple_phi_num_args (phi); i++) > + { > + tree op =3D gimple_phi_arg_def (phi, i); > + if (TREE_CODE (op) =3D=3D SSA_NAME && > + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) > + { > + return false; > + } > + } > + > + return true; > + } > + > + if (gimple_code (stmt) !=3D 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 cop= y. */ > + if (gimple_store_p (stmt) || gimple_assign_load_p (stmt)) > + { > + return false; > + } > + > + if (!gimple_assign_single_p (stmt)) > + { > + return false; > + } > + > + tree lhs =3D 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 =3D 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, tarja= n > + 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 =3D unvisited; > + v.index =3D 0; > + v.lowlink =3D 0; > + v.stmt =3D 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) !=3D SSA_NAME) > + return; /* Skip any neighbor that isn't an SSA name. */ > + > + gimple *neigh_stmt =3D SSA_NAME_DEF_STMT (neigh_tree); > + > + /* Skip neighbors outside the induced subgraph that Tarjan currently wo= rks > + with. */ > + if (!tarjan_is_using (neigh_stmt)) > + return; > + unsigned neigh_vxnum =3D tarjan_vxnum (neigh_stmt); > + > + gcc_checking_assert (stmt_may_generate_copy (neigh_stmt)); > + > + vstate neigh_state =3D vs[neigh_vxnum].state; > + vstate parent_state =3D vs[parent_vxnum].state; > + if (parent_state =3D=3D 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 =3D std::min (vs[parent_vxnum].lowlink, > + vs[neigh_vxnum].index); > + break; > + case in_scc: > + /* Ignore these edges. */ > + break; > + } > + } > + else if (parent_state =3D=3D 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 =3D=3D closed) > + { > + vs[parent_vxnum].lowlink =3D std::min (vs[parent_vxnum].lowlink, > + vs[neigh_vxnum].lowlink); > + } > + } > +} > + > +/* Nonrecursive implementation of Tarjan's algorithm for computing strong= ly > + connected components in a graph. Statements are vertices. Edges lead f= rom a > + copy stmt p using another copy stmt q to the stmt being used (p -> q w= hen 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 =3D 0; > + > + auto_vec vs =3D tarjan_stmts_to_vertices (copy_stmts); > + > + /* Mark the subgraph induced by 'copy_stmts' and index it by vxnums. */= > + unsigned i; > + for (i =3D 0; i < vs.length (); i++) > + { > + gimple *stmt =3D vs[i].stmt; > + tarjan_set_using (stmt); > + tarjan_set_vxnum (stmt, i); > + } > + > + /* Put all vertices on worklist. */ > + for (i =3D 0; i < vs.length (); i++) > + { > + worklist.safe_push (i); > + } > + > + /* Worklist loop. */ > + while (!worklist.is_empty ()) > + { > + unsigned i =3D worklist.pop(); > + gimple *stmt =3D vs[i].stmt; > + vstate state =3D vs[i].state; > + > + if (state =3D=3D unvisited) > + { > + vs[i].state =3D vopen; > + > + /* Assign index to this vertex. */ > + vs[i].index =3D curr_index; > + vs[i].lowlink =3D 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 =3D=3D vopen) > + { > + vs[i].state =3D closed; > + } > + > + /* Visit neighbors of this vertex. */ > + tree op; > + gphi *phi; > + switch (gimple_code (stmt)) > + { > + case GIMPLE_PHI: > + phi =3D as_a (stmt); > + unsigned j; > + for (j =3D 0; j < gimple_phi_num_args (phi); j++) > + { > + op =3D gimple_phi_arg_def (phi, j); > + tarjan_visit_neighbor (op, i, vs, worklist); > + } > + break; > + case GIMPLE_ASSIGN: > + op =3D 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 =3D=3D vopen && vs[i].lowlink =3D=3D vs[i].index) > + { > + vec scc =3D vNULL; > + > + unsigned j; > + do > + { > + j =3D stack.pop(); > + scc.safe_push (vs[j].stmt); > + vs[j].state =3D in_scc; > + } > + while (j !=3D i); > + > + sccs.safe_push (scc); > + } > + } > + > + if (!stack.is_empty ()) > + { > + gcc_unreachable(); > + } > + > + /* Clear copy stmts' 'using' flags. */ > + for (vertex v : vs) > + { > + gimple *s =3D v.stmt; > + tarjan_clear_using (s); > + } > + > + return sccs; > +} > + > +static void > +replace_use_by (tree get_replaced, tree replace_by, bitmap need_eh_cleanu= p, > + 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 =3D false; > + bool can_make_abnormal_goto =3D false; > + if (is_gimple_call (use_stmt)) > + { > + was_noreturn =3D gimple_call_noreturn_p (use_stmt); > + can_make_abnormal_goto =3D 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 =3D gimple_assign_rhs1 (use_stmt); > + > + if (TREE_CODE (rhs) =3D=3D ADDR_EXPR) > + recompute_tree_invariant_for_addr_expr (rhs); > + } > + > + /* Cleanup. */ > + gimple_stmt_iterator gsi =3D 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 =3D 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 =3D gsi_start_phis (bb); !gsi_end_p (pi);) > + { > + gphi *phi =3D pi.phi (); > + tree ssa_name =3D 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 &sc= c_set, > + bool &is_inner, tree &last_outer_op) > +{ > + bool op_in_scc =3D false; > + > + if (TREE_CODE (op) =3D=3D SSA_NAME) > + { > + gimple *op_stmt =3D SSA_NAME_DEF_STMT (op); > + if (scc_set.contains (op_stmt)) > + op_in_scc =3D true; > + } > + > + if (!op_in_scc) > + { > + outer_ops.add (op); > + last_outer_op =3D op; > + is_inner =3D false; > + } > +} > + > +/* Apply Braun et al.'s algorithm on a given set of statements. Treat cop= y > + statements as PHI functions with a single argument. > + Main function of this pass. */ > + > +static void > +sccp_propagate (auto_vec ©_stmts) > +{ > + auto_vec> worklist; > + worklist =3D tarjan_compute_sccs (copy_stmts); > + > + /* Prepare data structs for cleanup after stmt modification. */ > + bitmap need_eh_cleanup =3D BITMAP_ALLOC (NULL); > + bitmap need_ab_cleanup =3D BITMAP_ALLOC (NULL); > + vec stmts_to_fixup =3D vNULL; > + > + while (!worklist.is_empty ()) > + { > + vec scc =3D worklist.pop (); > + > + auto_vec inner; > + hash_set outer_ops; > + tree last_outer_op =3D 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 =3D true; > + > + gphi *phi; > + tree op; > + switch (gimple_code (stmt)) > + { > + case GIMPLE_PHI: > + phi =3D as_a (stmt); > + unsigned j; > + for (j =3D 0; j < gimple_phi_num_args (phi); j++) > + { > + op =3D gimple_phi_arg_def (phi, j); > + sccp_visit_op (op, outer_ops, scc_set, is_inner, > + last_outer_op); > + } > + break; > + case GIMPLE_ASSIGN: > + op =3D 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 () =3D=3D 1) > + { > + /* The only operand in outer_ops. */ > + tree outer_op =3D 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 =3D 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 =3D gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *s =3D gsi_stmt (gsi); > + if (stmt_may_generate_copy (s)) > + result.safe_push (s); > + } > + > + gphi_iterator pi; > + for (pi =3D gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + { > + gimple *s =3D 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 =3D gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple* stmt =3D gsi_stmt (gsi); > + tarjan_clear_using (stmt); > + } > + > + gphi_iterator pi; > + for (pi =3D gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + { > + gimple *stmt =3D 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 =3D > +{ > + 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 =3D 0; > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gphi_iterator pi; > + for (pi =3D 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 =3D get_all_stmt_may_generate_copy (); > + sccp_propagate (stmts); > + finalize_sccp (); > + > + // DEBUG > + if (dump_file) > + { > + int phis =3D 0; > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gphi_iterator pi; > + for (pi =3D 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::co= ntext *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) >=20 > return 0; > } > + > +void > +cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap need_eh_cle= anup, > + bitmap need_ab_cleanup, vec stmts_to_fixup, > + bool can_make_abnormal_goto, bool was_noreturn) > +{ > + basic_block bb =3D 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 =3D gimple_assign_rhs1 (stmt); > + > + if (TREE_CODE (rhs) =3D=3D 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 =3D 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, bitm= ap > + need_ab_cleanup, vec > + stms_to_fixup); >=20 > /* Public interface into the SSA propagation engine. Clients should inher= it > from this class and provide their own visitors. */ > --=20 > 2.41.0 >=20