tree-ssa-uncprop.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "ggc.h"
#include "basic-block.h"
#include "output.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "domwalk.h"
#include "real.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
struct edge_equivalency
{
tree rhs;
tree lhs;
};
static void
associate_equivalences_with_edges (void)
{
basic_block bb;
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi = bsi_last (bb);
tree stmt;
if (bsi_end_p (bsi))
continue;
stmt = bsi_stmt (bsi);
if (!stmt)
continue;
if (TREE_CODE (stmt) == COND_EXPR)
{
tree cond = COND_EXPR_COND (stmt);
edge true_edge;
edge false_edge;
struct edge_equivalency *equivalency;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
if (TREE_CODE (cond) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
{
equivalency = XNEW (struct edge_equivalency);
equivalency->rhs = constant_boolean_node (1, TREE_TYPE (cond));
equivalency->lhs = cond;
true_edge->aux = equivalency;
equivalency = XNEW (struct edge_equivalency);
equivalency->rhs = constant_boolean_node (0, TREE_TYPE (cond));
equivalency->lhs = cond;
false_edge->aux = equivalency;
}
else if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
if (TREE_CODE (op0) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
&& TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
&& is_gimple_min_invariant (op1))
{
if (TREE_CODE (cond) == EQ_EXPR)
{
equivalency = XNEW (struct edge_equivalency);
equivalency->lhs = op0;
equivalency->rhs = (integer_zerop (op1)
? boolean_false_node
: boolean_true_node);
true_edge->aux = equivalency;
equivalency = XNEW (struct edge_equivalency);
equivalency->lhs = op0;
equivalency->rhs = (integer_zerop (op1)
? boolean_true_node
: boolean_false_node);
false_edge->aux = equivalency;
}
else
{
equivalency = XNEW (struct edge_equivalency);
equivalency->lhs = op0;
equivalency->rhs = (integer_zerop (op1)
? boolean_true_node
: boolean_false_node);
true_edge->aux = equivalency;
equivalency = XNEW (struct edge_equivalency);
equivalency->lhs = op0;
equivalency->rhs = (integer_zerop (op1)
? boolean_false_node
: boolean_true_node);
false_edge->aux = equivalency;
}
}
if (TREE_CODE (op0) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
&& (is_gimple_min_invariant (op1)
|| (TREE_CODE (op1) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
{
if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
&& (TREE_CODE (op1) != REAL_CST
|| REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
continue;
equivalency = XNEW (struct edge_equivalency);
equivalency->lhs = op0;
equivalency->rhs = op1;
if (TREE_CODE (cond) == EQ_EXPR)
true_edge->aux = equivalency;
else
false_edge->aux = equivalency;
}
}
}
if (TREE_CODE (stmt) == SWITCH_EXPR)
{
tree cond = SWITCH_COND (stmt);
if (TREE_CODE (cond) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
{
tree labels = SWITCH_LABELS (stmt);
int i, n_labels = TREE_VEC_LENGTH (labels);
tree *info = XCNEWVEC (tree, n_basic_blocks);
for (i = 0; i < n_labels; i++)
{
tree label = TREE_VEC_ELT (labels, i);
basic_block bb = label_to_block (CASE_LABEL (label));
if (CASE_HIGH (label)
|| !CASE_LOW (label)
|| info[bb->index])
info[bb->index] = error_mark_node;
else
info[bb->index] = label;
}
for (i = 0; i < n_basic_blocks; i++)
{
tree node = info[i];
if (node != NULL
&& node != error_mark_node)
{
tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
struct edge_equivalency *equivalency;
equivalency = XNEW (struct edge_equivalency);
equivalency->rhs = x;
equivalency->lhs = cond;
find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
}
}
free (info);
}
}
}
}
static VEC(tree,heap) *equiv_stack;
static htab_t equiv;
struct equiv_hash_elt
{
tree value;
VEC(tree,heap) *equivalences;
};
static void uncprop_initialize_block (struct dom_walk_data *, basic_block);
static void uncprop_finalize_block (struct dom_walk_data *, basic_block);
static void uncprop_into_successor_phis (struct dom_walk_data *, basic_block);
static hashval_t
equiv_hash (const void *p)
{
tree value = ((struct equiv_hash_elt *)p)->value;
return iterative_hash_expr (value, 0);
}
static int
equiv_eq (const void *p1, const void *p2)
{
tree value1 = ((struct equiv_hash_elt *)p1)->value;
tree value2 = ((struct equiv_hash_elt *)p2)->value;
return operand_equal_p (value1, value2, 0);
}
static void
equiv_free (void *p)
{
struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
VEC_free (tree, heap, elt->equivalences);
free (elt);
}
static void
remove_equivalence (tree value)
{
struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
void **slot;
equiv_hash_elt.value = value;
equiv_hash_elt.equivalences = NULL;
slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
VEC_pop (tree, equiv_hash_elt_p->equivalences);
}
static void
record_equiv (tree value, tree equivalence)
{
struct equiv_hash_elt *equiv_hash_elt;
void **slot;
equiv_hash_elt = XNEW (struct equiv_hash_elt);
equiv_hash_elt->value = value;
equiv_hash_elt->equivalences = NULL;
slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
if (*slot == NULL)
*slot = (void *) equiv_hash_elt;
else
free (equiv_hash_elt);
equiv_hash_elt = (struct equiv_hash_elt *) *slot;
VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
}
static unsigned int
tree_ssa_uncprop (void)
{
struct dom_walk_data walk_data;
basic_block bb;
associate_equivalences_with_edges ();
equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
equiv_stack = VEC_alloc (tree, heap, 2);
calculate_dominance_info (CDI_DOMINATORS);
walk_data.walk_stmts_backward = false;
walk_data.dom_direction = CDI_DOMINATORS;
walk_data.initialize_block_local_data = NULL;
walk_data.before_dom_children_before_stmts = uncprop_initialize_block;
walk_data.before_dom_children_walk_stmts = NULL;
walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = uncprop_finalize_block;
walk_data.global_data = NULL;
walk_data.block_local_data_size = 0;
walk_data.interesting_blocks = NULL;
init_walk_dominator_tree (&walk_data);
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
htab_delete (equiv);
VEC_free (tree, heap, equiv_stack);
FOR_EACH_BB (bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->aux)
{
free (e->aux);
e->aux = NULL;
}
}
}
return 0;
}
static void
uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb ATTRIBUTE_UNUSED)
{
tree value = VEC_pop (tree, equiv_stack);
if (value != NULL)
remove_equivalence (value);
}
static void
uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi = phi_nodes (e->dest);
if (!phi)
continue;
if (e->aux)
{
struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
record_equiv (equiv->rhs, equiv->lhs);
}
for ( ; phi; phi = PHI_CHAIN (phi))
{
tree arg = PHI_ARG_DEF (phi, e->dest_idx);
struct equiv_hash_elt equiv_hash_elt;
void **slot;
if (!is_gimple_min_invariant (arg)
&& SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
continue;
equiv_hash_elt.value = arg;
equiv_hash_elt.equivalences = NULL;
slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
if (slot)
{
struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
int j;
for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
{
tree equiv = VEC_index (tree, elt->equivalences, j);
if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
{
SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
break;
}
}
}
}
if (e->aux)
{
struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
remove_equivalence (equiv->rhs);
}
}
}
static edge
single_incoming_edge_ignoring_loop_edges (basic_block bb)
{
edge retval = NULL;
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
continue;
if (retval)
return NULL;
retval = e;
}
return retval;
}
static void
uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
basic_block bb)
{
basic_block parent;
edge e;
bool recorded = false;
parent = get_immediate_dominator (CDI_DOMINATORS, bb);
if (parent)
{
e = single_incoming_edge_ignoring_loop_edges (bb);
if (e && e->src == parent && e->aux)
{
struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
record_equiv (equiv->rhs, equiv->lhs);
VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
recorded = true;
}
}
if (!recorded)
VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
}
static bool
gate_uncprop (void)
{
return flag_tree_dom != 0;
}
struct tree_opt_pass pass_uncprop =
{
"uncprop",
gate_uncprop,
tree_ssa_uncprop,
NULL,
NULL,
0,
TV_TREE_SSA_UNCPROP,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_verify_ssa,
0
};