From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id 4336E3858004; Wed, 15 Feb 2023 10:13:40 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4336E3858004 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1676456020; bh=XPojCqIXMa5qGBHyQGsjNNON6QqLaXCjuvi0wsxr9c0=; h=From:To:Subject:Date:From; b=UyHuCHuGtjXscU8vUMOPnlreNLXf27fFXofrOVCYL2HixeIyA6P+q0jvPljI8BjgD EgUCNzKz5VJge1CyNSkNAOIAXda9P5A+oK+Dxb9cP7DuxiGG6JfBMfG+CaX38pjqGk gLt6lHp0SVy727MU39ankXMY32ngMle1iJhmf4Ow= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Filip Kastl To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/pheeck/heads/sccp)] rewrote sccp tarjan to be nonrecursive; needs debug X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: 04d728098cf3f86e3168a76a927c36ac86a13b62 X-Git-Newrev: e59faa6cb1a53640b0ad69ad66c5f5e831305c57 Message-Id: <20230215101340.4336E3858004@sourceware.org> Date: Wed, 15 Feb 2023 10:13:40 +0000 (GMT) List-Id: https://gcc.gnu.org/g:e59faa6cb1a53640b0ad69ad66c5f5e831305c57 commit e59faa6cb1a53640b0ad69ad66c5f5e831305c57 Author: Filip Kastl Date: Thu Jul 21 13:34:34 2022 +0200 rewrote sccp tarjan to be nonrecursive; needs debug Diff: --- gcc/sccp.cc | 336 ++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 238 insertions(+), 98 deletions(-) diff --git a/gcc/sccp.cc b/gcc/sccp.cc index 0b32287317b..d33f0337e8c 100644 --- a/gcc/sccp.cc +++ b/gcc/sccp.cc @@ -58,135 +58,288 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" -/* Variable from Tarjan's SCC algorithm. */ struct vertex { bool visited; bool is_on_stack; unsigned index; unsigned lowlink; -} + gphi* stmt; +}; -/* Each SSA name corresponds to a vertex. Indexed by SSA version number. */ -static *vertices; -/* Each SCC is a vector of version nums. */ -static vec> tarjan_sccs; -static vec tarjan_stack; -static unsigned tarjan_index = 0; +static unsigned +min (unsigned x, unsigned y) +{ + if (x < y) + return x; + else + return y; +} -/* Initialize structures used for sccp. */ +static void +tarjan_set_using (gimple* stmt) +{ + gimple_set_plf (stmt, GF_PLF_1, true); +} static void -init_sccp (void) +tarjan_clear_using (gimple* stmt) { - vertices = XCNEWVEC (vertex, num_ssa_names); + gimple_set_plf (stmt, GF_PLF_1, false); } -/* Free structures used for sccp. */ +static bool +tarjan_is_using (gimple* stmt) +{ + return gimple_plf (stmt, GF_PLF_1); +} static void -finalize_sccp (void) +tarjan_set_phinum (gphi* phi, unsigned num) { - XDELETEVEC (vertices); + gimple_set_uid (phi, num); } -/* TODO */ +static unsigned +tarjan_phinum (gphi* phi) +{ + return gimple_uid (phi); +} static void -tarjan_assign_index (unsigned vnum) +init_sccp (void) { - vertices[vnum].index = tarjan_index; - vertices[vnum].lowlink = tarjan_index; - vertices[vnum].visited = true; - tarjan_index++; + // 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); + } + } } -/* TODO */ - static void -tarjan_update_lowlink (unsigned vnum, unsigned new_lowlink) +finalize_sccp (void) { - unsigned old_lowlink = vertices[vnum].lowlink; - if (old_lowlink < new_lowlink) - vertices[vnum].lowlink = old_lowlink; - else - vertices[vnum].lowlink = new_lowlink; } -/* Tarjan SCC algorithm subprocedure. */ +/* Return vector of all PHI functions available to this pass that aren't + abnormal. */ -static void -tarjan_strongconnect (gphi *phi) +static vec +get_all_normal_phis (void) { - tree foo = gimple_get_lhs (phi); // TODO foo - unsigned vnum = SSA_NAME_VERSION (foo); + vec result = vNULL; - tarjan_assign_index (vnum); - tarjan_stack.safe_push (vnum); - vertices[vnum].is_on_stack = true; + 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)) + { + gphi *phi = pi.phi (); + tree ssa_name = gimple_phi_result (phi); + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name)) + continue; + result.safe_push (phi); + } + } + + return result; +} +static vec +tarjan_phis_to_vertices (vec phis) +{ + vec result = vNULL; + for (gphi *phi : phis) + { + vertex v; + v.visited = false; + v.is_on_stack = false; + v.index = 0; + v.lowlink = 0; + v.stmt = phi; + + result.safe_push (v); + } + return result; +} + +static vec> +tarjan_compute_sccs (vec phis) +{ + vec> sccs = vNULL; + vec worklist = vNULL; + unsigned curr_index = 0; + + vec vs = tarjan_phis_to_vertices (phis); + + /* Assign phinums and set PHI functions' 'using' flag. */ unsigned i; - for (i = 0; i < gimple_phi_num_args (phi); i++) + for (i = 0; i < vs.length (); i++) + { + gphi *phi = vs[i].stmt; + tarjan_set_using (phi); + tarjan_set_phinum (phi, i); + } + + /* Put all vertices on worklist. */ + for (i = 0; i < vs.length (); i++) + { + worklist.safe_push (i); + } + + /* Worklist loop. */ + while (!worklist.is_empty ()) { - tree op = gimple_phi_arg_def (phi, i); - // TODO Is there a case where the next line won't work? - gimple *stmt = SSA_NAME_DEF_STMT (op); - if (gimple_code (stmt) != GIMPLE_PHI) - continue; - - unsigned op_vnum = SSA_NAME_VERSION (op); - if (!vertices[op_vnum].visited) + unsigned i = worklist.pop(); + + if (!vs[i].visited) { - // TODO Will the next line work? - tarjan_strongconnect (as_a (stmt)); - tarjan_update_lowlink (vnum, vertices[op_vnum].lowlink); + gphi *phi = vs[i].stmt; + + /* Assign index to this vertex. */ + vs[i].index = curr_index; + vs[i].lowlink = curr_index; + curr_index++; + + /* Put this vertex back on worklist. */ + worklist.safe_push (i); + + /* Put not yet visited children of vertex on worklist and update + lowlink of this vertex according to lowlinks of children on stack. */ + unsigned j; + for (j = 0; j < gimple_phi_num_args (phi); j++) + { + tree op_ssa = gimple_phi_arg_def (phi, i); + gimple *op_stmt = SSA_NAME_DEF_STMT (op_ssa); + + /* Skip any operand that isn't a vertex we're using. */ + if (!tarjan_is_using (op_stmt)) + continue; + + gphi *op_phi = dyn_cast (op_stmt); + if (op_phi == NULL) + /* Only PHI functions have the 'using' flags set. */ + gcc_unreachable (); + + unsigned op_i = tarjan_phinum (op_phi); + if (!vs[op_i].visited) + { + worklist.safe_push (op_i); + } + else if (vs[op_i].is_on_stack) + { + vs[i].lowlink = min (vs[i].lowlink, vs[op_i].index); + } + } } - else if (vertices[op_vnum].is_on_stack) + else if (vs[i].is_on_stack) // TODO This check is redundant { - tarjan_update_lowlink (vnum, vertices[op_vnum].index); + vec scc = vNULL; + + /* Put vertex back on stack/worklist. */ + worklist.safe_push (i); + + /* Pop scc from stack/worklist. */ + unsigned j; + do + { + j = worklist.pop(); + scc.safe_push (vs[j].stmt); + vs[j].is_on_stack = false; + } + while (vs[j].lowlink != vs[j].index); + + sccs.safe_push (scc); } } - if (vertices[vnum].lowlink == vertices[vnum].index) + /* Clear PHI functions' 'using' flags. */ + for (vertex v : vs) { - vec new_scc = vNULL; + gphi *phi = v.stmt; + tarjan_clear_using (phi); + } - unsigned stack_vnum; - do /* There will always be at least 1 vertex on stack. */ - { - stack_vnum = tarjan_stack.pop (); - vertices[stack_vnum].is_on_stack = false; - new_scc.safe_push (stack_vnum); - } - while (stack_vnum != vnum); + return sccs; +} - tarjan_sccs.safe_push (new_scc); +static void +replace_scc_by_value (vec scc, tree v) +{ + for (gphi *phi : scc) + { + // DEBUG + tree ssa_name = gimple_get_lhs (phi); + unsigned vnum_get_replaced = SSA_NAME_VERSION (ssa_name); + unsigned vnum_replaced_by = SSA_NAME_VERSION (v); + std::cerr << "Replacing " << vnum_get_replaced << " by " << + vnum_replaced_by << std::endl; + // TODO Remove phi statement and free ssa name + // TODO Replace occurences of phi with v } } -/* Runs Tarjan's SCC algorithm on PHIs. Fills out tarjan_sccs. */ +static void remove_redundant_phis (vec phis); // TODO Where to put + // declaration? static void -tarjan_compute_sccs (void) +process_scc (vec scc) { - basic_block bb; - FOR_EACH_BB_FN (bb, cfun) - { - gphi_iterator pi; + vec inner = vNULL; + vec outer_ops = vNULL; - for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + for (gphi *phi : scc) + { + bool is_inner = true; + + unsigned i; + for (i = 0; i < gimple_phi_num_args (phi); i++) { - gphi *phi = pi.phi (); - tree foo = gimple_get_lhs (phi); // TODO foo - //fprintf (dump_file, "ahoj\n"); // DEBUG, use -fdump-tree-sccp - //debug_tree (foo); // DEBUG - unsigned vnum = SSA_NAME_VERSION (foo); - // TODO Filtrovat stmts jako v copyprop? - if (!vertices[vnum].visited) + tree op = gimple_phi_arg_def (phi, i); + gimple *op_stmt = SSA_NAME_DEF_STMT (op); + + // Check if operand is a phi from scc (TODO Efficiency) + bool op_in_scc = false; + for (gphi *foo : scc) + { + if (op_stmt == foo) + op_in_scc = true; + } + + if (!op_in_scc) { - tarjan_strongconnect (phi); + outer_ops.safe_push (op); + is_inner = false; } } + + if (is_inner) + { + inner.safe_push (phi); + } + } + + // TODO if == 0 -> unreachable? + if (outer_ops.length () == 1) + replace_scc_by_value (scc, outer_ops.pop()); + else if (outer_ops.length () > 1) + remove_redundant_phis (inner); +} + +static void +remove_redundant_phis (vec phis) +{ + vec> sccs = tarjan_compute_sccs (phis); + for (vec scc : sccs) + { + process_scc (scc); } } @@ -222,35 +375,22 @@ public: unsigned pass_sccp::execute (function *) { - // DEBUG - /* - basic_block bb; - FOR_EACH_BB_FN (bb, cfun) - { - debug_bb (bb); - gphi_iterator pi; - std::cerr << "PHI LIST" << std::endl; - for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) - { - gphi *phi = pi.phi (); - debug_gimple_stmt (phi); - } - std::cerr << std::endl << std::endl; - } - */ - init_sccp (); - tarjan_compute_sccs (); + vec> sccs = tarjan_compute_sccs (get_all_normal_phis ()); - std::cerr << "ahoj" << std::endl; - for (vec scc : tarjan_sccs) + std::cerr << "function:" << std::endl; + for (vec scc : sccs) { - for (unsigned phi : scc) + std::cerr << "scc:" << std::endl; + for (gphi *phi : scc) { - std::cerr << phi << std::endl; + tree ssa_name = gimple_phi_result (phi); + unsigned vnum = SSA_NAME_VERSION (ssa_name); + std::cerr << vnum << std::endl; } std::cerr << std::endl; } + std::cerr << std::endl; finalize_sccp ();