/* Remove the appropriate PHI arguments in E's destination block. */
for (phi = phi_nodes (e->dest); phi; phi = next)
{
- next = TREE_CHAIN (phi);
+ next = PHI_CHAIN (phi);
remove_phi_arg (phi, e->src);
}
remove_edge (e);
}
-/* Remove remove the corresponding arguments from the PHI nodes
- in E's destination block and redirect it to DEST. Return redirected edge.
+/* Remove the corresponding arguments from the PHI nodes in E's
+ destination block and redirect it to DEST. Return redirected edge.
The list of removed arguments is stored in PENDING_STMT (e). */
edge
/* Remove the appropriate PHI arguments in E's destination block. */
for (phi = phi_nodes (e->dest); phi; phi = next)
{
- next = TREE_CHAIN (phi);
+ next = PHI_CHAIN (phi);
i = phi_arg_from_edge (phi, e);
if (i < 0)
tree phi;
block_stmt_iterator bsi;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
err |= verify_def (bb, definition_block, PHI_RESULT (phi), phi);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
}
/* Verify the arguments for every PHI node in the block. */
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
err |= verify_phi_args (phi, bb, definition_block);
/* Now verify all the uses and vuses in every statement of the block.
if (SSA_VAR_P (t))
break;
- switch (TREE_CODE (t))
- {
- case ARRAY_REF:
- case COMPONENT_REF:
- case REALPART_EXPR:
- case IMAGPART_EXPR:
- case BIT_FIELD_REF:
- case INDIRECT_REF:
+ if (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR)
+ t = TREE_OPERAND (t, 0);
+ else
+ while (handled_component_p (t))
t = TREE_OPERAND (t, 0);
- break;
-
- default:
- return;
- }
}
if (TREE_CODE (t) == SSA_NAME)
}
}
+/* Replaces VAR with REPL in memory reference expression *X in
+ statement STMT. */
+
+static void
+propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
+{
+ tree new_var, ass_stmt, addr_var;
+ basic_block bb;
+ block_stmt_iterator bsi;
+
+ /* There is nothing special to handle in the other cases. */
+ if (TREE_CODE (repl) != ADDR_EXPR)
+ return;
+ addr_var = TREE_OPERAND (repl, 0);
+
+ while (TREE_CODE (*x) == ARRAY_REF
+ || TREE_CODE (*x) == COMPONENT_REF
+ || TREE_CODE (*x) == BIT_FIELD_REF)
+ x = &TREE_OPERAND (*x, 0);
+
+ if (TREE_CODE (*x) != INDIRECT_REF
+ || TREE_OPERAND (*x, 0) != var)
+ return;
+
+ modify_stmt (stmt);
+ if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
+ {
+ *x = addr_var;
+ mark_new_vars_to_rename (stmt, vars_to_rename);
+ return;
+ }
+
+ /* Frontends sometimes produce expressions like *&a instead of a[0].
+ Create a temporary variable to handle this case. */
+ ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
+ new_var = duplicate_ssa_name (var, ass_stmt);
+ TREE_OPERAND (*x, 0) = new_var;
+ TREE_OPERAND (ass_stmt, 0) = new_var;
+
+ bb = bb_for_stmt (stmt);
+ tree_block_label (bb);
+ bsi = bsi_after_labels (bb);
+ bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
+
+ mark_new_vars_to_rename (stmt, vars_to_rename);
+}
/* Replaces immediate uses of VAR by REPL. */
dataflow_t df;
tree stmt;
stmt_ann_t ann;
+ bool mark_new_vars;
df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
n = num_immediate_uses (df);
for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
if (PHI_ARG_DEF (stmt, j) == var)
{
- PHI_ARG_DEF (stmt, j) = repl;
+ SET_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;
}
get_stmt_operands (stmt);
+ mark_new_vars = false;
if (is_gimple_reg (SSA_NAME_VAR (var)))
{
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
+ propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
+ }
+
uses = USE_OPS (ann);
for (j = 0; j < (int) NUM_USES (uses); j++)
if (USE_OP (uses, j) == var)
- propagate_value (USE_OP_PTR (uses, j), repl);
+ {
+ propagate_value (USE_OP_PTR (uses, j), repl);
+ mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
+ }
}
else
{
propagate_value (V_MAY_DEF_OP_PTR (v_may_defs, j), repl);
}
- modify_stmt (stmt);
-
/* If REPL is a pointer, it may have different memory tags associated
with it. For instance, VAR may have had a name tag while REPL
only had a type tag. In these cases, the virtual operands (if
any) in the statement will refer to different symbols which need
to be renamed. */
- if (POINTER_TYPE_P (TREE_TYPE (repl)))
+ if (mark_new_vars)
mark_new_vars_to_rename (stmt, vars_to_rename);
+ else
+ modify_stmt (stmt);
}
}
-/* Raises value of phi node PHI by joining it with VAL. Processes immediate
- uses of PHI recursively. */
+/* Gets the value VAR is equivalent to according to EQ_TO. */
-static void
-raise_value (tree phi, tree val, tree *eq_to)
+static tree
+get_eq_name (tree *eq_to, tree var)
{
- int i, n;
- tree var = PHI_RESULT (phi), stmt;
- int ver = SSA_NAME_VERSION (var);
- dataflow_t df;
+ unsigned ver;
+ tree val = var;
- if (eq_to[ver] == var)
- return;
+ while (TREE_CODE (val) == SSA_NAME)
+ {
+ ver = SSA_NAME_VERSION (val);
+ if (!eq_to[ver])
+ break;
+
+ val = eq_to[ver];
+ }
- switch (TREE_CODE (val))
+ while (TREE_CODE (var) == SSA_NAME)
{
- case SSA_NAME:
- case REAL_CST:
- case COMPLEX_CST:
- break;
- case INTEGER_CST:
- if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
+ ver = SSA_NAME_VERSION (var);
+ if (!eq_to[ver])
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;
+ var = eq_to[ver];
+ eq_to[ver] = val;
}
- if (eq_to[ver])
+ return val;
+}
+
+/* Checks whether phi node PHI is redundant and if it is, records the ssa name
+ its result is redundant to to EQ_TO array. */
+
+static void
+check_phi_redundancy (tree phi, tree *eq_to)
+{
+ tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
+ unsigned i, ver = SSA_NAME_VERSION (res), n;
+ dataflow_t df;
+
+ /* It is unlikely that such large phi node would be redundant. */
+ if (PHI_NUM_ARGS (phi) > 16)
+ return;
+
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
{
- if (operand_equal_p (eq_to[ver], val, 0))
+ def = PHI_ARG_DEF (phi, i);
+
+ if (TREE_CODE (def) == SSA_NAME)
+ {
+ def = get_eq_name (eq_to, def);
+ if (def == res)
+ continue;
+ }
+
+ if (val
+ && !operand_equal_p (val, def, 0))
return;
- eq_to[ver] = var;
+ val = def;
}
- else
- eq_to[ver] = val;
- df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
+ /* At least one of the arguments should not be equal to the result, or
+ something strange is happening. */
+ if (!val)
+ abort ();
+
+ if (get_eq_name (eq_to, res) == val)
+ return;
+
+ if (!may_propagate_copy (res, val))
+ return;
+
+ eq_to[ver] = val;
+
+ df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
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);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ check_phi_redundancy (stmt, eq_to);
}
}
The most important effect of this pass is to remove degenerate PHI
nodes created by removing unreachable code. */
-static void
+void
kill_redundant_phi_nodes (void)
{
tree *eq_to;
- unsigned i;
+ unsigned i, old_num_ssa_names;
basic_block bb;
- tree phi, t, stmt, var;
-
- /* The EQ_TO array holds the current value of the ssa name in the
- lattice:
-
- top
- / | \
- const variables
- \ | /
- bottom
-
- Bottom is represented by NULL and top by the variable itself.
-
- Once the dataflow stabilizes, we know that the phi nodes we need to keep
- are exactly those with top as their result.
-
- The remaining phi nodes have their uses replaced with their value
- in the lattice and the phi node itself is removed. */
+ tree phi, var, repl, stmt;
+
+ /* The EQ_TO[VER] holds the value by that the ssa name VER should be
+ replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
+ other value, it may be necessary to follow the chain till the final value.
+ We perform path shortening (replacing the entries of the EQ_TO array with
+ heads of these chains) whenever we access the field to prevent quadratic
+ complexity (probably would not occur in practice anyway, but let us play
+ it safe). */
eq_to = xcalloc (num_ssa_names, sizeof (tree));
/* We have had cases where computing immediate uses takes a
a subset of all the SSA_NAMEs instead of computing it for
all of the SSA_NAMEs. */
compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+ old_num_ssa_names = num_ssa_names;
FOR_EACH_BB (bb)
{
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
var = PHI_RESULT (phi);
-
- 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);
-
- /* If the defining statement for this argument is not a
- phi node or the argument is associated with an abnormal
- edge, then we need to recursively start the forward
- dataflow starting with PHI. */
- if (TREE_CODE (stmt) != PHI_NODE
- || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
- {
- eq_to[SSA_NAME_VERSION (t)] = t;
- raise_value (phi, t, eq_to);
- }
- }
+ check_phi_redundancy (phi, eq_to);
}
}
/* Now propagate the values. */
- for (i = 0; i < num_ssa_names; i++)
- if (eq_to[i]
- && eq_to[i] != ssa_name (i))
- replace_immediate_uses (ssa_name (i), eq_to[i]);
+ for (i = 0; i < old_num_ssa_names; i++)
+ {
+ if (!ssa_name (i))
+ continue;
+
+ repl = get_eq_name (eq_to, ssa_name (i));
+ if (repl != ssa_name (i))
+ replace_immediate_uses (ssa_name (i), repl);
+ }
/* And remove the dead phis. */
- for (i = 0; i < num_ssa_names; i++)
- if (eq_to[i]
- && eq_to[i] != ssa_name (i))
- {
- stmt = SSA_NAME_DEF_STMT (ssa_name (i));
- remove_phi_node (stmt, 0, bb_for_stmt (stmt));
- }
+ for (i = 0; i < old_num_ssa_names; i++)
+ {
+ if (!ssa_name (i))
+ continue;
+
+ repl = get_eq_name (eq_to, ssa_name (i));
+ if (repl != ssa_name (i))
+ {
+ stmt = SSA_NAME_DEF_STMT (ssa_name (i));
+ remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
+ }
+ }
free_df ();
free (eq_to);
execute_early_warn_uninitialized ();
FOR_EACH_BB (bb)
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
warn_uninitialized_phi (phi);
}