From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id 6B3163853814; Fri, 1 Jul 2022 15:53:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6B3163853814 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)] wip first version of tarjan's scc algorithm X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: 6636fc691288342e56e7d446e6ede7f97a60f7b3 X-Git-Newrev: 3262c36a38ad6d6272db36a84bbf112d4153e42f Message-Id: <20220701155328.6B3163853814@sourceware.org> Date: Fri, 1 Jul 2022 15:53:28 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Jul 2022 15:53:28 -0000 https://gcc.gnu.org/g:3262c36a38ad6d6272db36a84bbf112d4153e42f commit 3262c36a38ad6d6272db36a84bbf112d4153e42f Author: Filip Kastl Date: Fri Jul 1 17:51:42 2022 +0200 wip first version of tarjan's scc algorithm Diff: --- gcc/sccp.cc | 111 ++++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 94 insertions(+), 17 deletions(-) diff --git a/gcc/sccp.cc b/gcc/sccp.cc index 42763a565e1..45cb8bfbfed 100644 --- a/gcc/sccp.cc +++ b/gcc/sccp.cc @@ -32,9 +32,11 @@ along with GCC; see the file COPYING3. If not see #include #include "gimple-pretty-print.h" -#include "bitmap.h" -#include "sbitmap.h" +#include "vec.h" +#include "libiberty.h" +#include +// Tohle jsem naimportoval kvuli num_ssa_names #include "backend.h" #include "cfghooks.h" #include "ssa.h" @@ -54,20 +56,101 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" -/* TODO Smaz. */ -static sbitmap visited; +struct vertex // Variables from Tarjan's SCC algorithm +{ + bool visited; + bool is_on_stack; + unsigned index; + unsigned lowlink; +} + +static *vertices; // Each SSA name ~ vertex. Indexed by SSA version number. +static vec> tarjan_sccs; // Each SCC is a vector of version nums. +static vec tarjan_stack; +static unsigned tarjan_index = 0; /* Initialize structures used for sccp. */ static void init_sccp (void) { - visited = sbitmap_alloc (num_ssa_names); + vertices = XCNEWVEC (vertex, num_ssa_names); +} + +/* TODO */ + +static void +tarjan_assign_index (unsigned vnum) +{ + vertices[vnum].index = tarjan_index; + vertices[vnum].lowlink = tarjan_index; + tarjan_index++; +} + +/* TODO */ + +static void +tarjan_update_lowlink (unsigned vnum, unsigned new_lowlink) +{ + unsigned old_lowlink = vertices[vnum].lowlink. + vertices[vnum].lowlink = min (old_lowlink, new_lowlink); } +/* Tarjan SCC algorithm subprocedure. */ + +static void +tarjan_strongconnect (unsigned vnum) +{ + tarjan_assign_index (vnum); + vec_safe_push (tarjan_stack, vnum); + vertices[vnum].is_on_stack = true; + + for (neigh_vnum) // TODO Iterate over neighbours (arguments of PHI) + { + if (!vertices[neigh_vnum].visited) + { + tarjan_strongconnect (neigh_vnum); + tarjan_update_lowlink (vnum, vertices[neigh_vnum].lowlink); + } + else if (vertices[neigh_vnum].is_on_stack) + { + tarjan_update_lowlink (vnum, vertices[neigh_vnum].index); + } + } + + if (vertices[vnum].lowlink == vertices[vnum].index) + { + // TODO + } +} + +/* Runs Tarjan's SCC algorithm on PHIs. Fills out tarjan_sccs. */ + +static void +tarjan_compute_sccs (void) +{ + 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 (); + // TODO Filtrovat stmts jako v copyprop + int ver = SSA_NAME_VERSION (phi); + if (!vertices[ver].visited) + { + tarjan_strongconnect (ver); + } + } + } +} + + /* TODO Smaz. */ -static void debug_reachable_phi(gimple* phi) +static void +debug_reachable_phi(gimple* phi) { debug_gimple_stmt (phi); @@ -120,22 +203,16 @@ unsigned pass_sccp::execute (function *) { basic_block bb; - init_sccp (); + vec> *sccs = tarjan_compute_sccs (); - FOR_EACH_BB_FN (bb, cfun) + for (vec scc : *sccs) { - gphi_iterator pi; - - for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + for (unsigned phi : scc) { - gphi *phi = pi.phi (); - // TODO Filtrovat stmts jako v copyprop - // Ale to asi budu muset filtrovat stmts, ne phi - bitmap_clear (visited); - debug_reachable_phi (phi); - std::cerr << std::endl; // Blank line + std::cerr << phi << std::endl; } + std::cerr << std::endl; } return 0; // TODO Co tu mam vracet?