/* Routines for discovering and unpropagating edge equivalences.
- Copyright (C) 2005, 2007, 2008, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2005-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "tree.h"
+#include "gimple.h"
+#include "hard-reg-set.h"
+#include "ssa.h"
+#include "alias.h"
+#include "fold-const.h"
+#include "stor-layout.h"
#include "flags.h"
#include "tm_p.h"
-#include "basic-block.h"
-#include "function.h"
-#include "tree-flow.h"
+#include "cfganal.h"
+#include "internal-fn.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
#include "domwalk.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
+#include "tree-hash-traits.h"
/* The basic structure describing an equivalency created by traversing
an edge. Traversing the edge effectively means that we can assume
/* Walk over each block. If the block ends with a control statement,
then it might create a useful equivalence. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi = gsi_last_bb (bb);
gimple stmt;
the sign of a variable compared against zero. If
we're honoring signed zeros, then we cannot record
this value unless we know that the value is nonzero. */
- if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
+ if (HONOR_SIGNED_ZEROS (op0)
&& (TREE_CODE (op1) != REAL_CST
|| REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
continue;
target block creates an equivalence. */
else if (gimple_code (stmt) == GIMPLE_SWITCH)
{
- tree cond = gimple_switch_index (stmt);
+ gswitch *switch_stmt = as_a <gswitch *> (stmt);
+ tree cond = gimple_switch_index (switch_stmt);
if (TREE_CODE (cond) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
{
- int i, n_labels = gimple_switch_num_labels (stmt);
- tree *info = XCNEWVEC (tree, last_basic_block);
+ int i, n_labels = gimple_switch_num_labels (switch_stmt);
+ tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
/* Walk over the case label vector. Record blocks
which are reached by a single case label which represents
a single value. */
for (i = 0; i < n_labels; i++)
{
- tree label = gimple_switch_label (stmt, i);
+ tree label = gimple_switch_label (switch_stmt, i);
basic_block bb = label_to_block (CASE_LABEL (label));
if (CASE_HIGH (label)
/* Now walk over the blocks to determine which ones were
marked as being reached by a useful case label. */
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
{
tree node = info[i];
equivalency = XNEW (struct edge_equivalency);
equivalency->rhs = x;
equivalency->lhs = cond;
- find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
+ find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
+ equivalency;
}
}
free (info);
so with each value we have a list of SSA_NAMEs that have the
same value. */
-/* As we enter each block we record the value for any edge equivalency
- leading to this block. If no such edge equivalency exists, then we
- record NULL. These equivalences are live until we leave the dominator
- subtree rooted at the block where we record the equivalency. */
-static vec<tree> equiv_stack;
-
-/* Global hash table implementing a mapping from invariant values
- to a list of SSA_NAMEs which have the same value. We might be
- able to reuse tree-vn for this code. */
-static htab_t equiv;
/* Main structure for recording equivalences into our hash table. */
struct equiv_hash_elt
vec<tree> equivalences;
};
-static void uncprop_enter_block (struct dom_walk_data *, basic_block);
-static void uncprop_leave_block (struct dom_walk_data *, basic_block);
-static void uncprop_into_successor_phis (basic_block);
-
-/* Hashing and equality routines for the hash table. */
+/* Value to ssa name equivalence hashtable helpers. */
-static hashval_t
-equiv_hash (const void *p)
+struct val_ssa_equiv_hash_traits : simple_hashmap_traits <tree_operand_hash>
{
- tree const value = ((const struct equiv_hash_elt *)p)->value;
- return iterative_hash_expr (value, 0);
-}
-
-static int
-equiv_eq (const void *p1, const void *p2)
-{
- tree value1 = ((const struct equiv_hash_elt *)p1)->value;
- tree value2 = ((const struct equiv_hash_elt *)p2)->value;
-
- return operand_equal_p (value1, value2, 0);
-}
+ template<typename T> static inline void remove (T &);
+};
/* Free an instance of equiv_hash_elt. */
-static void
-equiv_free (void *p)
+template<typename T>
+inline void
+val_ssa_equiv_hash_traits::remove (T &elt)
{
- struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
- elt->equivalences.release ();
- free (elt);
+ elt.m_value.release ();
}
+/* Global hash table implementing a mapping from invariant values
+ to a list of SSA_NAMEs which have the same value. We might be
+ able to reuse tree-vn for this code. */
+static hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> *val_ssa_equiv;
+
+static void uncprop_into_successor_phis (basic_block);
+
/* Remove the most recently recorded equivalency for VALUE. */
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.create (0);
-
- slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
-
- equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
- equiv_hash_elt_p->equivalences.pop ();
+ val_ssa_equiv->get (value)->pop ();
}
/* Record EQUIVALENCE = VALUE into our hash table. */
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.create (0);
-
- 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;
-
- equiv_hash_elt->equivalences.safe_push (equivalence);
+ val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
}
-/* Main driver for un-cprop. */
-
-static unsigned int
-tree_ssa_uncprop (void)
+class uncprop_dom_walker : public dom_walker
{
- struct dom_walk_data walk_data;
- basic_block bb;
-
- associate_equivalences_with_edges ();
-
- /* Create our global data structures. */
- equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
- equiv_stack.create (2);
-
- /* We're going to do a dominator walk, so ensure that we have
- dominance information. */
- calculate_dominance_info (CDI_DOMINATORS);
-
- /* Setup callbacks for the generic dominator tree walker. */
- walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.initialize_block_local_data = NULL;
- walk_data.before_dom_children = uncprop_enter_block;
- walk_data.after_dom_children = uncprop_leave_block;
- walk_data.global_data = NULL;
- walk_data.block_local_data_size = 0;
+public:
+ uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
- /* Now initialize the dominator walker. */
- init_walk_dominator_tree (&walk_data);
+ virtual void before_dom_children (basic_block);
+ virtual void after_dom_children (basic_block);
- /* Recursively walk the dominator tree undoing unprofitable
- constant/copy propagations. */
- walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
-
- /* Finalize and clean up. */
- fini_walk_dominator_tree (&walk_data);
-
- /* EQUIV_STACK should already be empty at this point, so we just
- need to empty elements out of the hash table, free EQUIV_STACK,
- and cleanup the AUX field on the edges. */
- htab_delete (equiv);
- equiv_stack.release ();
- 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;
-}
+private:
+ /* As we enter each block we record the value for any edge equivalency
+ leading to this block. If no such edge equivalency exists, then we
+ record NULL. These equivalences are live until we leave the dominator
+ subtree rooted at the block where we record the equivalency. */
+ auto_vec<tree, 2> m_equiv_stack;
+};
/* We have finished processing the dominator children of BB, perform
any finalization actions in preparation for leaving this node in
the dominator tree. */
-static void
-uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb ATTRIBUTE_UNUSED)
+void
+uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
{
/* Pop the topmost value off the equiv stack. */
- tree value = equiv_stack.pop ();
+ tree value = m_equiv_stack.pop ();
/* If that value was non-null, then pop the topmost equivalency off
its equivalency stack. */
gimple phi = gsi_stmt (gsi);
tree arg = PHI_ARG_DEF (phi, e->dest_idx);
tree res = PHI_RESULT (phi);
- struct equiv_hash_elt equiv_hash_elt;
- void **slot;
- /* If the argument is not an invariant, and refers to the same
- underlying variable as the PHI result, then there's no
- point in un-propagating the argument. */
+ /* If the argument is not an invariant and can be potentially
+ coalesced with the result, then there's no point in
+ un-propagating the argument. */
if (!is_gimple_min_invariant (arg)
- && (SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
- && TREE_TYPE (arg) == TREE_TYPE (res)))
+ && gimple_can_coalesce_p (arg, res))
continue;
/* Lookup this argument's value in the hash table. */
- equiv_hash_elt.value = arg;
- equiv_hash_elt.equivalences.create (0);
- slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
-
- if (slot)
+ vec<tree> *equivalences = val_ssa_equiv->get (arg);
+ if (equivalences)
{
- struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
- int j;
-
/* Walk every equivalence with the same value. If we find
- one with the same underlying variable as the PHI result,
+ one that can potentially coalesce with the PHI rsult,
then replace the value in the argument with its equivalent
SSA_NAME. Use the most recent equivalence as hopefully
that results in shortest lifetimes. */
- for (j = elt->equivalences.length () - 1; j >= 0; j--)
+ for (int j = equivalences->length () - 1; j >= 0; j--)
{
- tree equiv = elt->equivalences[j];
+ tree equiv = (*equivalences)[j];
- if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (res)
- && TREE_TYPE (equiv) == TREE_TYPE (res))
+ if (gimple_can_coalesce_p (equiv, res))
{
SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
break;
return retval;
}
-static void
-uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
+void
+uncprop_dom_walker::before_dom_children (basic_block bb)
{
basic_block parent;
edge e;
struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
record_equiv (equiv->rhs, equiv->lhs);
- equiv_stack.safe_push (equiv->rhs);
+ m_equiv_stack.safe_push (equiv->rhs);
recorded = true;
}
}
if (!recorded)
- equiv_stack.safe_push (NULL_TREE);
+ m_equiv_stack.safe_push (NULL_TREE);
uncprop_into_successor_phis (bb);
}
-static bool
-gate_uncprop (void)
+namespace {
+
+const pass_data pass_data_uncprop =
{
- return flag_tree_dom != 0;
+ GIMPLE_PASS, /* type */
+ "uncprop", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SSA_UNCPROP, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_uncprop : public gimple_opt_pass
+{
+public:
+ pass_uncprop (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_uncprop, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_uncprop (m_ctxt); }
+ virtual bool gate (function *) { return flag_tree_dom != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_uncprop
+
+unsigned int
+pass_uncprop::execute (function *fun)
+{
+ basic_block bb;
+
+ associate_equivalences_with_edges ();
+
+ /* Create our global data structures. */
+ val_ssa_equiv
+ = new hash_map<tree, vec<tree>, val_ssa_equiv_hash_traits> (1024);
+
+ /* We're going to do a dominator walk, so ensure that we have
+ dominance information. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Recursively walk the dominator tree undoing unprofitable
+ constant/copy propagations. */
+ uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
+
+ /* we just need to empty elements out of the hash table, and cleanup the
+ AUX field on the edges. */
+ delete val_ssa_equiv;
+ val_ssa_equiv = NULL;
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (e->aux)
+ {
+ free (e->aux);
+ e->aux = NULL;
+ }
+ }
+ }
+ return 0;
}
-struct gimple_opt_pass pass_uncprop =
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_uncprop (gcc::context *ctxt)
{
- {
- GIMPLE_PASS,
- "uncprop", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_uncprop, /* gate */
- tree_ssa_uncprop, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_SSA_UNCPROP, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa /* todo_flags_finish */
- }
-};
+ return new pass_uncprop (ctxt);
+}
projects / platform / upstream / gcc.git / blobdiff