tree-ssa-uncprop.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "fold-const.h"
#include "cfganal.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "domwalk.h"
#include "tree-hash-traits.h"
#include "tree-ssa-live.h"
#include "tree-ssa-coalesce.h"

Include dependency graph for tree-ssa-uncprop.cc:

Data Structures
struct	edge_equivalency
class	uncprop_dom_walker

Typedefs
typedef hash_map< tree_operand_hash, auto_vec< tree > >	val_ssa_equiv_t

Functions
static void	associate_equivalences_with_edges (void)
static void	uncprop_into_successor_phis (basic_block)
static void	remove_equivalence (tree value)
static void	record_equiv (tree value, tree equivalence)
gimple_opt_pass *	make_pass_uncprop (gcc::context *ctxt)

Variables
val_ssa_equiv_t *	val_ssa_equiv

Typedef Documentation

val_ssa_equiv_t

typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t

Translating out of SSA sometimes requires inserting copies and
constant initializations on edges to eliminate PHI nodes.

In some cases those copies and constant initializations are
redundant because the target already has the value on the
RHS of the assignment.

We previously tried to catch these cases after translating
out of SSA form.  However, that code often missed cases.  Worse
yet, the cases it missed were also often missed by the RTL
optimizers.  Thus the resulting code had redundant instructions.

This pass attempts to detect these situations before translating
out of SSA form.

The key concept that this pass is built upon is that these
redundant copies and constant initializations often occur
due to constant/copy propagating equivalences resulting from
COND_EXPRs and SWITCH_EXPRs.

We want to do those propagations as they can sometimes allow
the SSA optimizers to do a better job.  However, in the cases
where such propagations do not result in further optimization,
we would like to "undo" the propagation to avoid the redundant
copies and constant initializations.

This pass works by first associating equivalences with edges in
the CFG.  For example, the edge leading from a SWITCH_EXPR to
its associated CASE_LABEL will have an equivalency between
SWITCH_COND and the value in the case label.

Once we have found the edge equivalences, we proceed to walk
the CFG in dominator order.  As we traverse edges we record
equivalences associated with those edges we traverse.

When we encounter a PHI node, we walk its arguments to see if we
have an equivalence for the PHI argument.  If so, then we replace
the argument.

Equivalences are looked up based on their value (think of it as
the RHS of an assignment).   A value may be an SSA_NAME or an
invariant.  We may have several SSA_NAMEs with the same value,
so with each value we have a list of SSA_NAMEs that have the
same value.   

Function Documentation

associate_equivalences_with_edges()

static void associate_equivalences_with_edges ( void )

static

This routine finds and records edge equivalences for every edge
in the CFG.

When complete, each edge that creates an equivalency will have an
EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
The caller is responsible for freeing the AUX fields.   

References BASIC_BLOCK_FOR_FN, CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, constant_boolean_node(), dconst0, error_mark_node, extract_true_false_edges_from_block(), find_edge(), fold_convert, FOR_EACH_BB_FN, free(), ggc_alloc(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), gsi_end_p(), gsi_last_bb(), gsi_stmt(), HONOR_SIGNED_ZEROS(), i, basic_block_def::index, integer_onep(), integer_zerop(), is_gimple_min_invariant(), label_to_block(), last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, real_equal(), ssa_name_has_boolean_range(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TREE_CODE, TREE_REAL_CST, and TREE_TYPE.

make_pass_uncprop()

gimple_opt_pass * make_pass_uncprop

(

gcc::context *

ctxt

)

References ggc_alloc().

record_equiv()

static void record_equiv ( tree value, tree equivalence )

static

Record EQUIVALENCE = VALUE into our hash table.   

References hash_map< KeyId, Value, Traits >::get_or_insert(), and val_ssa_equiv.

Referenced by uncprop_dom_walker::before_dom_children(), and uncprop_into_successor_phis().

remove_equivalence()

static void remove_equivalence ( tree value )

static

Remove the most recently recorded equivalency for VALUE.   

References hash_map< KeyId, Value, Traits >::get(), and val_ssa_equiv.

Referenced by uncprop_dom_walker::after_dom_children(), and uncprop_into_successor_phis().

uncprop_into_successor_phis()

static void uncprop_into_successor_phis ( basic_block bb )

static

Unpropagate values from PHI nodes in successor blocks of BB.   

References FOR_EACH_EDGE, hash_map< KeyId, Value, Traits >::get(), ggc_alloc(), gimple_can_coalesce_p(), gimple_seq_empty_p(), gsi_end_p(), gsi_next(), gsi_start(), gsi_stmt(), is_gimple_min_invariant(), PHI_ARG_DEF, phi_nodes(), PHI_RESULT, phis, record_equiv(), remove_equivalence(), SET_PHI_ARG_DEF, basic_block_def::succs, and val_ssa_equiv.

Referenced by uncprop_dom_walker::before_dom_children().

Variable Documentation

val_ssa_equiv

val_ssa_equiv_t* val_ssa_equiv

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.   

Referenced by record_equiv(), remove_equivalence(), and uncprop_into_successor_phis().