From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id D8A87385841C; Wed, 15 Feb 2023 10:13:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D8A87385841C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1676455994; bh=y2yEzjACU8utvCZxrvCqkBv56J0O3CwQgZ032xQw46A=; h=From:To:Subject:Date:From; b=y385v29yrgPD0rhS/lm6HiEyBYHNKFhZvDBIML+XJxwcP1kxaQ5j8lTAooCcZ9XWG zlpKo7yI9cjhCQv0iHpCpEOhQebikLiz8G7ZZN4XmHEFVTcbuthGKmnjJAJkK7oT0n mZvWwbdzuTlg6yfzipJup5c5BQPgvE7fdGqdkC2c= MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="utf-8" From: Filip Kastl To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/pheeck/heads/sccp)] stuck: how to iterate over gphi arguments of PHI X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: 4fb1427f2ed0ee6dcf6bf4c15e8c718572e1caaa X-Git-Newrev: b83f0f39bc1ebbadfa261d8931bbbaf6b0c9b9d6 Message-Id: <20230215101314.D8A87385841C@sourceware.org> Date: Wed, 15 Feb 2023 10:13:14 +0000 (GMT) List-Id: https://gcc.gnu.org/g:b83f0f39bc1ebbadfa261d8931bbbaf6b0c9b9d6 commit b83f0f39bc1ebbadfa261d8931bbbaf6b0c9b9d6 Author: Filip Kastl Date: Wed Jul 6 12:04:54 2022 +0200 stuck: how to iterate over gphi arguments of PHI Diff: --- gcc/sccp.cc | 114 ++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 65 insertions(+), 49 deletions(-) diff --git a/gcc/sccp.cc b/gcc/sccp.cc index 45cb8bfbfed..752ecdbc649 100644 --- a/gcc/sccp.cc +++ b/gcc/sccp.cc @@ -36,7 +36,7 @@ along with GCC; see the file COPYING3. If not see #include "libiberty.h" #include -// Tohle jsem naimportoval kvuli num_ssa_names +// TODO Imported for global var num_ssa_names to work #include "backend.h" #include "cfghooks.h" #include "ssa.h" @@ -56,7 +56,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" -struct vertex // Variables from Tarjan's SCC algorithm +/* Variable from Tarjan's SCC algorithm */ +struct vertex { bool visited; bool is_on_stack; @@ -64,8 +65,10 @@ struct vertex // Variables from Tarjan's SCC algorithm 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. +/* 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; @@ -77,6 +80,14 @@ init_sccp (void) vertices = XCNEWVEC (vertex, num_ssa_names); } +/* Free structures used for sccp. */ + +static void +finalize_sscp (void) +{ + // TODO +} + /* TODO */ static void @@ -92,35 +103,61 @@ tarjan_assign_index (unsigned vnum) static void tarjan_update_lowlink (unsigned vnum, unsigned new_lowlink) { - unsigned old_lowlink = vertices[vnum].lowlink. - vertices[vnum].lowlink = min (old_lowlink, new_lowlink); + 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. */ static void -tarjan_strongconnect (unsigned vnum) +tarjan_strongconnect (gphi *phi) { + tree foo = gimple_vdef (phi); // TODO Name. Do I want vuse? + unsigned vnum = SSA_NAME_VERSION (foo); + tarjan_assign_index (vnum); - vec_safe_push (tarjan_stack, vnum); + tarjan_stack.safe_push (vnum); vertices[vnum].is_on_stack = true; - for (neigh_vnum) // TODO Iterate over neighbours (arguments of PHI) + unsigned i; + for (i = 0; i < gimple_phi_num_args (phi); i++) { - if (!vertices[neigh_vnum].visited) + 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) { - tarjan_strongconnect (neigh_vnum); - tarjan_update_lowlink (vnum, vertices[neigh_vnum].lowlink); + // TODO Will the next line work? Implicit gimple* -> gphi* + tarjan_strongconnect (stmt); + tarjan_update_lowlink (vnum, vertices[op_vnum].lowlink); } - else if (vertices[neigh_vnum].is_on_stack) + else if (vertices[op_vnum].is_on_stack) { - tarjan_update_lowlink (vnum, vertices[neigh_vnum].index); + tarjan_update_lowlink (vnum, vertices[op_vnum].index); } } if (vertices[vnum].lowlink == vertices[vnum].index) { - // TODO + vec *new_scc = new vec(); + + 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); + + tarjan_sccs.safe_push (new_scc); } } @@ -129,6 +166,7 @@ tarjan_strongconnect (unsigned vnum) static void tarjan_compute_sccs (void) { + basic_block bb; FOR_EACH_BB_FN (bb, cfun) { gphi_iterator pi; @@ -136,41 +174,18 @@ tarjan_compute_sccs (void) for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) { gphi *phi = pi.phi (); + tree foo = gimple_vdef (phi); // TODO Name + unsigned vnum = SSA_NAME_VERSION (foo); // TODO Filtrovat stmts jako v copyprop - int ver = SSA_NAME_VERSION (phi); - if (!vertices[ver].visited) + if (!vertices[vnum].visited) { - tarjan_strongconnect (ver); + tarjan_strongconnect (phi); } } } } - -/* TODO Smaz. */ - -static void -debug_reachable_phi(gimple* phi) -{ - debug_gimple_stmt (phi); - - unsigned int i; - for (i = 0; i < gimple_phi_num_args (phi); i++) - { - tree op = gimple_phi_arg_def (phi, i); - // TODO Nerozbije se tohle někdy? - gimple *stmt = SSA_NAME_DEF_STMT (op); - int ver = SSA_NAME_VERSION (op); - if (gimple_code (stmt) == GIMPLE_PHI && - !bitmap_bit_p (visited, ver)) - { - bitmap_set_bit (visited, ver); - debug_reachable_phi (stmt); - } - } -} - -/* TODO Popisek passu */ +/* TODO Pass description. */ namespace { @@ -195,27 +210,28 @@ public: {} /* opt_pass methods: */ - virtual bool gate (function *) { return true; } // TODO Rozhodovat, jestli pass pustit + virtual bool gate (function *) { return true; } // TODO virtual unsigned int execute (function *); }; // class pass_sccp unsigned pass_sccp::execute (function *) { - basic_block bb; init_sccp (); - vec> *sccs = tarjan_compute_sccs (); + tarjan_compute_sccs (); - for (vec scc : *sccs) + for (vec *scc : tarjan_sccs) { - for (unsigned phi : scc) + for (unsigned phi : *scc) { std::cerr << phi << std::endl; } std::cerr << std::endl; } - return 0; // TODO Co tu mam vracet? + finalize_sscp (); + + return 0; // TODO What should I return? } } // anon namespace