This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Supefluous phi removal
Hello,
> For kill_redundant_phi_nodes, it seems to me you ought to document the code
> a little. Specifically I think documenting how EQ_TO is used would be wise,
> particularly the case when it indicates that a PHI should not be eliminated
> and a copy should not be propagated.
here is the piece of patch with comments extended.
Zdenek
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.180
diff -c -3 -p -r1.1.4.180 tree-ssa.c
*** tree-ssa.c 19 Dec 2003 07:01:36 -0000 1.1.4.180
--- tree-ssa.c 6 Jan 2004 11:04:33 -0000
*************** tree_ssa_useless_type_conversion (tree e
*** 3575,3578 ****
--- 3575,3779 ----
return false;
}
+ /* Replaces immediate uses of VAR by REPL. */
+
+ static void
+ replace_immediate_uses (tree var, tree repl)
+ {
+ use_optype uses;
+ vuse_optype vuses;
+ vdef_optype vdefs;
+ int i, j, n;
+ dataflow_t df;
+ tree stmt;
+
+ df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+ n = num_immediate_uses (df);
+
+ for (i = 0; i < n; i++)
+ {
+ stmt = immediate_use (df, i);
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
+ if (PHI_ARG_DEF (stmt, j) == var)
+ {
+ PHI_ARG_DEF (stmt, j) = repl;
+ if (TREE_CODE (repl) == SSA_NAME
+ && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
+ }
+
+ continue;
+ }
+
+ get_stmt_operands (stmt);
+ if (is_gimple_reg (SSA_NAME_VAR (var)))
+ {
+ uses = STMT_USE_OPS (stmt);
+ for (j = 0; j < (int) NUM_USES (uses); j++)
+ if (USE_OP (uses, j) == var)
+ *USE_OP_PTR (uses, j) = repl;
+ }
+ else
+ {
+ vuses = STMT_VUSE_OPS (stmt);
+ for (j = 0; j < (int) NUM_VUSES (vuses); j++)
+ if (VUSE_OP (vuses, j) == var)
+ *VUSE_OP_PTR (vuses, j) = repl;
+
+ vdefs = STMT_VDEF_OPS (stmt);
+ for (j = 0; j < (int) NUM_VDEFS (vdefs); j++)
+ if (VDEF_OP (vdefs, j) == var)
+ *VDEF_OP_PTR (vdefs, j) = repl;
+ }
+ modify_stmt (stmt);
+ }
+ }
+
+ /* Raises value of phi node PHI by joining it VAL. Processes immediate uses
+ of the phi recursively. */
+
+ static void
+ raise_value (tree phi, tree val, tree *eq_to)
+ {
+ int i, n;
+ tree var = PHI_RESULT (phi), stmt;
+ int ver = SSA_NAME_VERSION (var);
+ dataflow_t df;
+
+ if (eq_to[ver] == var)
+ return;
+
+ switch (TREE_CODE (val))
+ {
+ case SSA_NAME:
+ case REAL_CST:
+ case COMPLEX_CST:
+ break;
+ case INTEGER_CST:
+ if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
+ break;
+
+ default:
+ /* Do not propagate pointer constants. This might require folding
+ things like *&foo and rewriting the ssa, which is not worth the
+ trouble. */
+ val = var;
+ }
+
+ if (eq_to[ver])
+ {
+ if (operand_equal_p (eq_to[ver], val, 0))
+ return;
+
+ eq_to[ver] = var;
+ }
+ else
+ eq_to[ver] = val;
+
+ df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+ n = num_immediate_uses (df);
+
+ for (i = 0; i < n; i++)
+ {
+ stmt = immediate_use (df, i);
+
+ if (TREE_CODE (stmt) != PHI_NODE)
+ continue;
+
+ raise_value (stmt, eq_to[ver], eq_to);
+ }
+ }
+
+ /* Removes redundant phi nodes (i.e. such that all their arguments are
+ equivalent), copy propagating the results. Just a trivial copy/const
+ propagation pass over phi nodes.
+
+ Most importantly this kills degenerated phi nodes that are created by
+ removing an unreachable code. */
+
+ void
+ kill_redundant_phi_nodes (void)
+ {
+ tree *eq_to, *def;
+ unsigned i, ver, aver;
+ basic_block bb;
+ tree phi, t, stmt, var;
+
+ eq_to = xcalloc (highest_ssa_version, sizeof (tree));
+ def = xcalloc (highest_ssa_version, sizeof (tree));
+ compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+
+ /* A dataflow over latice
+ top
+ / | \
+ constants variables
+ \ | /
+ bottom
+
+ eq_to[ssa_version] is the current value of the ssa name in the lattice. Bottom is
+ represented by NULL, top by the variable itself.
+
+ Once the dataflow stabilizes, we know that the phi nodes we need to keep are exactly
+ those for that their result is top. The remaining variables must be equivalent to
+ one of the top ones, their uses are replaced with it and the phi nodes defining them
+ are removed. */
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ {
+ var = PHI_RESULT (phi);
+ ver = SSA_NAME_VERSION (var);
+ def[ver] = var;
+
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ {
+ t = PHI_ARG_DEF (phi, i);
+
+ if (TREE_CODE (t) != SSA_NAME)
+ {
+ raise_value (phi, t, eq_to);
+ continue;
+ }
+
+ stmt = SSA_NAME_DEF_STMT (t);
+ aver = SSA_NAME_VERSION (t);
+ def[aver] = t;
+
+ if (TREE_CODE (stmt) != PHI_NODE
+ /* Prevent copy propagation into arguments of phi nodes
+ corresponding to abnormal edges, by setting their
+ value to top. */
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
+ {
+ eq_to[aver] = t;
+ raise_value (phi, t, eq_to);
+ }
+ }
+ }
+ }
+
+ /* Now replace the uses of eliminated ssa names. */
+ for (i = 0; i < highest_ssa_version; i++)
+ if (eq_to[i]
+ && eq_to[i] != def[i])
+ replace_immediate_uses (def[i], eq_to[i]);
+
+ /* And remove the dead phis. */
+ for (i = 0; i < highest_ssa_version; i++)
+ if (eq_to[i]
+ && eq_to[i] != def[i])
+ {
+ stmt = SSA_NAME_DEF_STMT (def[i]);
+ remove_phi_node (stmt, 0, bb_for_stmt (stmt));
+ }
+
+ free_df ();
+ free (eq_to);
+ free (def);
+ }
+
#include "gt-tree-ssa.h"