/* SSA Dominator optimizations for trees
- Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
#include "tm_p.h"
#include "ggc.h"
#include "basic-block.h"
+#include "cfgloop.h"
#include "output.h"
#include "errors.h"
#include "expr.h"
#include "domwalk.h"
#include "real.h"
#include "tree-pass.h"
+#include "tree-ssa-propagate.h"
#include "langhooks.h"
/* This file implements optimizations on the dominator tree. */
+
+/* Structure for recording edge equivalences as well as any pending
+ edge redirections during the dominator optimizer.
+
+ Computing and storing the edge equivalences instead of creating
+ them on-demand can save significant amounts of time, particularly
+ for pathological cases involving switch statements.
+
+ These structures live for a single iteration of the dominator
+ optimizer in the edge's AUX field. At the end of an iteration we
+ free each of these structures and update the AUX field to point
+ to any requested redirection target (the code for updating the
+ CFG and SSA graph for edge redirection expects redirection edge
+ targets to be in the AUX field for each edge. */
+
+struct edge_info
+{
+ /* If this edge creates a simple equivalence, the LHS and RHS of
+ the equivalence will be stored here. */
+ tree lhs;
+ tree rhs;
+
+ /* Traversing an edge may also indicate one or more particular conditions
+ are true or false. The number of recorded conditions can vary, but
+ can be determined by the condition's code. So we have an array
+ and its maximum index rather than use a varray. */
+ tree *cond_equivalences;
+ unsigned int max_cond_equivalences;
+
+ /* If we can thread this edge this field records the new target. */
+ edge redirection_target;
+};
+
+
/* Hash table with expressions made available during the renaming process.
When an assignment of the form X_i = EXPR is found, the statement is
stored in this table. If the same expression EXPR is later found on the
in this table. */
static htab_t avail_exprs;
+/* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
+ expressions it enters into the hash table along with a marker entry
+ (null). When we finish processing the block, we pop off entries and
+ remove the expressions from the global hash table until we hit the
+ marker. */
+static VEC(tree_on_heap) *avail_exprs_stack;
+
+/* Stack of trees used to restore the global currdefs to its original
+ state after completing optimization of a block and its dominator children.
+
+ An SSA_NAME indicates that the current definition of the underlying
+ variable should be set to the given SSA_NAME.
+
+ A _DECL node indicates that the underlying variable has no current
+ definition.
+
+ A NULL node is used to mark the last node associated with the
+ current block. */
+static VEC(tree_on_heap) *block_defs_stack;
+
+/* Stack of statements we need to rescan during finalization for newly
+ exposed variables.
+
+ Statement rescanning must occur after the current block's available
+ expressions are removed from AVAIL_EXPRS. Else we may change the
+ hash code for an expression and be unable to find/remove it from
+ AVAIL_EXPRS. */
+static VEC(tree_on_heap) *stmts_to_rescan;
+
/* Structure for entries in the expression hash table.
This requires more memory for the hash table entries, but allows us
have to perform in lookup_avail_expr and finally it allows us to
significantly reduce the number of calls into the hashing routine
itself. */
+
struct expr_hash_elt
{
/* The value (lhs) of this expression. */
hashval_t hash;
};
-/* Table of constant values and copies indexed by SSA name. When the
- renaming pass finds an assignment of a constant (X_i = C) or a copy
- assignment from another SSA variable (X_i = Y_j), it creates a mapping
- between X_i and the RHS in this table. This mapping is used later on,
- when renaming uses of X_i. If an assignment to X_i is found in this
- table, instead of using X_i, we use the RHS of the statement stored in
- this table (thus performing very simplistic copy and constant
- propagation). */
-static varray_type const_and_copies;
+/* Stack of dest,src pairs that need to be restored during finalization.
+
+ A NULL entry is used to mark the end of pairs which need to be
+ restored during finalization of this block. */
+static VEC(tree_on_heap) *const_and_copies_stack;
/* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
know their exact value. */
static bitmap nonzero_vars;
+/* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
+ when the current block is finalized.
+
+ A NULL entry is used to mark the end of names needing their
+ entry in NONZERO_VARS cleared during finalization of this block. */
+static VEC(tree_on_heap) *nonzero_vars_stack;
+
/* Track whether or not we have changed the control flow graph. */
static bool cfg_altered;
+/* Bitmap of blocks that have had EH statements cleaned. We should
+ remove their dead edges eventually. */
+static bitmap need_eh_cleanup;
+
/* Statistics for dominator optimizations. */
struct opt_stats_d
{
long num_re;
};
+static struct opt_stats_d opt_stats;
+
/* Value range propagation record. Each time we encounter a conditional
of the form SSA_NAME COND CONST we create a new vrp_element to record
how the condition affects the possible values SSA_NAME may have.
- Each record contains the condition tested (COND), and the the range of
+ Each record contains the condition tested (COND), and the range of
values the variable may legitimately have if COND is true. Note the
range of values may be a smaller range than COND specifies if we have
recorded other ranges for this variable. Each record also contains the
optimizations are not performed.
Note carefully we do not propagate information through each statement
- in the block. ie, if we know variable X has a value defined of
+ in the block. i.e., if we know variable X has a value defined of
[0, 25] and we encounter Y = X + 1, we do not track a value range
for Y (which would be [1, 26] if we cared). Similarly we do not
constrain values as we encounter narrowing typecasts, etc. */
basic_block bb;
};
-static struct opt_stats_d opt_stats;
-
-/* This virtual array holds pairs of edges which describe a scheduled
- edge redirection from jump threading.
+/* A hash table holding value range records (VRP_ELEMENTs) for a given
+ SSA_NAME. We used to use a varray indexed by SSA_NAME_VERSION, but
+ that gets awful wasteful, particularly since the density objects
+ with useful information is very low. */
+static htab_t vrp_data;
- The first entry in each pair is the edge we are going to redirect.
-
- The second entry in each pair is the edge leading to our final
- destination block. By providing this as an edge rather than the
- final target block itself we can correctly handle redirections
- when the target block had PHIs which required edge insertions/splitting
- to remove the PHIs. */
-static GTY(()) varray_type redirection_edges;
+/* An entry in the VRP_DATA hash table. We record the variable and a
+ varray of VRP_ELEMENT records associated with that variable. */
+struct vrp_hash_elt
+{
+ tree var;
+ varray_type records;
+};
-/* A virtual array holding value range records for the variable identified
- by the index, SSA_VERSION. */
-static varray_type vrp_data;
+/* Array of variables which have their values constrained by operations
+ in this basic block. We use this during finalization to know
+ which variables need their VRP data updated. */
-/* Datastructure for block local data used during the dominator walk.
- We maintain a stack of these as we recursively walk down the
- dominator tree. */
+/* Stack of SSA_NAMEs which had their values constrained by operations
+ in this basic block. During finalization of this block we use this
+ list to determine which variables need their VRP data updated.
-struct dom_walk_block_data
-{
- /* Array of all the expressions entered into the global expression
- hash table by this block. During finalization we use this array to
- know what expressions to remove from the global expression hash
- table. */
- varray_type avail_exprs;
-
- /* Array of dest, src pairs that need to be restored during finalization
- into the global const/copies table during finalization. */
- varray_type const_and_copies;
-
- /* Similarly for the nonzero state of variables that needs to be
- restored during finalization. */
- varray_type nonzero_vars;
-
- /* Array of statements we need to rescan during finalization for newly
- exposed variables. */
- varray_type stmts_to_rescan;
-
- /* Array of variables which have their values constrained by operations
- in this basic block. We use this during finalization to know
- which variables need their VRP data updated. */
- varray_type vrp_variables;
-
- /* Array of tree pairs used to restore the global currdefs to its
- original state after completing optimization of a block and its
- dominator children. */
- varray_type block_defs;
-};
+ A NULL entry marks the end of the SSA_NAMEs associated with this block. */
+static VEC(tree_on_heap) *vrp_variables_stack;
struct eq_expr_value
{
static void optimize_stmt (struct dom_walk_data *,
basic_block bb,
block_stmt_iterator);
-static inline tree get_value_for (tree, varray_type table);
-static inline void set_value_for (tree, tree, varray_type table);
-static tree lookup_avail_expr (tree, varray_type *, bool);
-static struct eq_expr_value get_eq_expr_value (tree, int, varray_type *,
- basic_block, varray_type *);
+static tree lookup_avail_expr (tree, bool);
+static hashval_t vrp_hash (const void *);
+static int vrp_eq (const void *, const void *);
static hashval_t avail_expr_hash (const void *);
+static hashval_t real_avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
-static void record_cond (tree, tree, varray_type *);
-static void record_const_or_copy (tree, tree, varray_type *);
-static void record_equality (tree, tree, varray_type *);
-static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
- stmt_ann_t, bool);
+static void record_cond (tree, tree);
+static void record_const_or_copy (tree, tree);
+static void record_equality (tree, tree);
+static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);
static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
- tree, stmt_ann_t, int);
-static tree simplify_cond_and_lookup_avail_expr (tree, varray_type *,
- stmt_ann_t, int);
-static tree simplify_switch_and_lookup_avail_expr (tree, varray_type *,
- stmt_ann_t, int);
+ tree, int);
+static tree simplify_cond_and_lookup_avail_expr (tree, stmt_ann_t, int);
+static tree simplify_switch_and_lookup_avail_expr (tree, int);
static tree find_equivalent_equality_comparison (tree);
-static void record_range (tree, basic_block, varray_type *);
+static void record_range (tree, basic_block);
static bool extract_range_from_cond (tree, tree *, tree *, int *);
-static void record_equivalences_from_phis (struct dom_walk_data *, basic_block);
-static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
- basic_block);
+static void record_equivalences_from_phis (basic_block);
+static void record_equivalences_from_incoming_edge (basic_block);
static bool eliminate_redundant_computations (struct dom_walk_data *,
tree, stmt_ann_t);
-static void record_equivalences_from_stmt (tree, varray_type *, varray_type *,
- int, stmt_ann_t);
+static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
static void thread_across_edge (struct dom_walk_data *, edge);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
-static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
- basic_block, bool);
static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
-static void cprop_into_phis (struct dom_walk_data *, basic_block);
-static void remove_local_expressions_from_table (varray_type locals,
- unsigned limit,
- htab_t table);
-static void restore_vars_to_original_value (varray_type locals,
- unsigned limit,
- varray_type table);
-static void restore_currdefs_to_original_value (varray_type locals,
- unsigned limit);
-static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
-static void redirect_edges_and_update_ssa_graph (varray_type);
+static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
+static void remove_local_expressions_from_table (void);
+static void restore_vars_to_original_value (void);
+static void restore_currdefs_to_original_value (void);
+static void register_definitions_for_stmt (tree);
+static edge single_incoming_edge_ignoring_loop_edges (basic_block);
+static void restore_nonzero_vars_to_original_value (void);
+static inline bool unsafe_associative_fp_binop (tree);
/* Local version of fold that doesn't introduce cruft. */
/* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
may have been added by fold, and "useless" type conversions that might
now be apparent due to propagation. */
- STRIP_MAIN_TYPE_NOPS (t);
STRIP_USELESS_TYPE_CONVERSION (t);
return t;
}
-/* Return the value associated with variable VAR in TABLE. */
+/* Allocate an EDGE_INFO for edge E and attach it to E.
+ Return the new EDGE_INFO structure. */
-static inline tree
-get_value_for (tree var, varray_type table)
+static struct edge_info *
+allocate_edge_info (edge e)
{
- return VARRAY_TREE (table, SSA_NAME_VERSION (var));
-}
+ struct edge_info *edge_info;
-/* Associate VALUE to variable VAR in TABLE. */
+ edge_info = xcalloc (1, sizeof (struct edge_info));
-static inline void
-set_value_for (tree var, tree value, varray_type table)
-{
- VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
+ e->aux = edge_info;
+ return edge_info;
}
-/* REDIRECTION_EDGES contains edge pairs where we want to revector the
- destination of the first edge to the destination of the second edge.
-
- These redirections may significantly change the SSA graph since we
- allow redirection through blocks with PHI nodes and blocks with
- real instructions in some cases.
-
- This routine will perform the requested redirections and incrementally
- update the SSA graph.
-
- Note in some cases requested redirections may be ignored as they can
- not be safely implemented. */
+/* Free all EDGE_INFO structures associated with edges in the CFG.
+ If a particular edge can be threaded, copy the redirection
+ target from the EDGE_INFO structure into the edge's AUX field
+ as required by code to update the CFG and SSA graph for
+ jump threading. */
static void
-redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
+free_all_edge_infos (void)
{
- basic_block tgt, bb;
- tree phi;
- unsigned int i;
- size_t old_num_referenced_vars = num_referenced_vars;
- bitmap virtuals_to_rename = BITMAP_XMALLOC ();
-
- /* First note any variables which we are going to have to take
- out of SSA form as well as any virtuals which need updating. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- block_stmt_iterator bsi;
- edge e;
- basic_block tgt;
- tree phi;
-
- e = VARRAY_EDGE (redirection_edges, i);
- tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
- /* All variables referenced in PHI nodes we bypass must be
- renamed. */
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
- if (is_gimple_reg (PHI_RESULT (phi)))
- bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
- else
- bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
- }
-
- /* Any variables set by statements at the start of the block we
- are bypassing must also be taken our of SSA form. */
- for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
- {
- unsigned int j;
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
- tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann = stmt_ann (stmt);
-
- if (TREE_CODE (stmt) == COND_EXPR)
- break;
-
- get_stmt_operands (stmt);
-
- defs = DEF_OPS (ann);
- for (j = 0; j < NUM_DEFS (defs); j++)
- {
- tree op = SSA_NAME_VAR (DEF_OP (defs, j));
- bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
- }
-
- v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
- for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
- {
- tree op = V_MAY_DEF_RESULT (v_may_defs, j);
- bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
- }
-
- v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
- for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
- {
- tree op = V_MUST_DEF_OP (v_must_defs, j);
- bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
- }
- }
-
- /* Finally, any variables in PHI nodes at our final destination
- must also be taken our of SSA form. */
- for (phi = phi_nodes (tgt); phi; phi = TREE_CHAIN (phi))
- {
- tree result = SSA_NAME_VAR (PHI_RESULT (phi));
-
- if (is_gimple_reg (PHI_RESULT (phi)))
- bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
- else
- bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
- }
- }
-
- /* Take those selected variables out of SSA form. This must be
- done before we start redirecting edges. */
- if (bitmap_first_set_bit (vars_to_rename) >= 0)
- rewrite_vars_out_of_ssa (vars_to_rename);
-
- /* The out of SSA translation above may split the edge from
- E->src to E->dest. This could potentially cause us to lose
- an assignment leading to invalid warnings about uninitialized
- variables or incorrect code.
-
- Luckily, we can detect this by looking at the last statement
- in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
- the edge was split and instead of E, we want E->dest->succ. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- edge e = VARRAY_EDGE (redirection_edges, i);
- tree last = last_stmt (e->dest);
-
- if (last
- && TREE_CODE (last) != COND_EXPR
- && TREE_CODE (last) != SWITCH_EXPR)
- {
- e = e->dest->succ;
-
-#ifdef ENABLE_CHECKING
- /* There should only be a single successor if the
- original edge was split. */
- if (e->succ_next)
- abort ();
-#endif
- /* Replace the edge in REDIRECTION_EDGES for the
- loop below. */
- VARRAY_EDGE (redirection_edges, i) = e;
- }
- }
-
- /* If we created any new variables as part of the out-of-ssa
- translation, then any jump threads must be invalidated if they
- bypass a block in which we skipped instructions.
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
- This is necessary as instructions which appeared to be NOPS
- may be necessary after the out-of-ssa translation. */
- if (num_referenced_vars != old_num_referenced_vars)
+ FOR_EACH_BB (bb)
{
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- block_stmt_iterator bsi;
- edge e;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ struct edge_info *edge_info = e->aux;
- e = VARRAY_EDGE (redirection_edges, i);
- for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
+ if (edge_info)
{
- tree stmt = bsi_stmt (bsi);
-
- if (IS_EMPTY_STMT (stmt)
- || TREE_CODE (stmt) == LABEL_EXPR)
- continue;
-
- if (TREE_CODE (stmt) == COND_EXPR)
- break;
-
- /* Invalidate the jump thread. */
- VARRAY_EDGE (redirection_edges, i) = NULL;
- VARRAY_EDGE (redirection_edges, i + 1) = NULL;
- break;
+ e->aux = edge_info->redirection_target;
+ if (edge_info->cond_equivalences)
+ free (edge_info->cond_equivalences);
+ free (edge_info);
}
}
}
-
- /* Now redirect the edges. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
- {
- basic_block src;
- edge e;
-
- e = VARRAY_EDGE (redirection_edges, i);
- if (!e)
- continue;
-
- tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
-
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
- e->src->index, e->dest->index, tgt->index);
-
- src = e->src;
-
- e = redirect_edge_and_branch (e, tgt);
- PENDING_STMT (e) = NULL_TREE;
-
- /* Updating the dominance information would be nontrivial. */
- free_dominance_info (CDI_DOMINATORS);
-
- if ((dump_file && (dump_flags & TDF_DETAILS))
- && e->src != src)
- fprintf (dump_file, " basic block %d created\n",
- e->src->index);
-
- cfg_altered = true;
- }
-
- VARRAY_CLEAR (redirection_edges);
-
- for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
- {
- bitmap_set_bit (vars_to_rename, i);
- var_ann (referenced_var (i))->out_of_ssa_tag = 0;
- }
-
- bitmap_a_or_b (vars_to_rename, vars_to_rename, virtuals_to_rename);
-
- /* We must remove any PHIs for virtual variables that we are going to
- re-rename. Hopefully we'll be able to simply update these incrementally
- soon. */
- FOR_EACH_BB (bb)
- {
- tree next;
-
- for (phi = phi_nodes (bb); phi; phi = next)
- {
- tree result = PHI_RESULT (phi);
-
- next = TREE_CHAIN (phi);
-
- if (bitmap_bit_p (virtuals_to_rename,
- var_ann (SSA_NAME_VAR (result))->uid))
- remove_phi_node (phi, NULL, bb);
- }
- }
- BITMAP_XFREE (virtuals_to_rename);
}
/* Jump threading, redundancy elimination and const/copy propagation.
- Optimize function FNDECL based on a walk through the dominator tree.
-
This pass may expose new symbols that need to be renamed into SSA. For
every new symbol exposed, its corresponding bit will be set in
- VARS_TO_RENAME.
-
- PHASE indicates which dump file from the DUMP_FILES array to use when
- dumping debugging information. */
+ VARS_TO_RENAME. */
static void
tree_ssa_dominator_optimize (void)
{
- basic_block bb;
struct dom_walk_data walk_data;
unsigned int i;
+ struct loops loops_info;
+
+ memset (&opt_stats, 0, sizeof (opt_stats));
for (i = 0; i < num_referenced_vars; i++)
var_ann (referenced_var (i))->current_def = NULL;
- /* Mark loop edges so we avoid threading across loop boundaries.
- This may result in transforming natural loop into irreducible
- region. */
- mark_dfs_back_edges ();
-
/* Create our hash tables. */
- avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, free);
- VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
- nonzero_vars = BITMAP_XMALLOC ();
- VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
- VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
+ avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
+ vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq, free);
+ avail_exprs_stack = VEC_alloc (tree_on_heap, 20);
+ block_defs_stack = VEC_alloc (tree_on_heap, 20);
+ const_and_copies_stack = VEC_alloc (tree_on_heap, 20);
+ nonzero_vars_stack = VEC_alloc (tree_on_heap, 20);
+ vrp_variables_stack = VEC_alloc (tree_on_heap, 20);
+ stmts_to_rescan = VEC_alloc (tree_on_heap, 20);
+ nonzero_vars = BITMAP_ALLOC (NULL);
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
/* Setup callbacks for the generic dominator tree walker. */
walk_data.walk_stmts_backward = false;
walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.initialize_block_local_data = dom_opt_initialize_block_local_data;
+ walk_data.initialize_block_local_data = NULL;
walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
walk_data.before_dom_children_walk_stmts = optimize_stmt;
- walk_data.before_dom_children_after_stmts = cprop_into_phis;
+ walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
walk_data.after_dom_children_before_stmts = NULL;
walk_data.after_dom_children_walk_stmts = NULL;
walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
When we attach more stuff we'll need to fill this out with a real
structure. */
walk_data.global_data = NULL;
- walk_data.block_local_data_size = sizeof (struct dom_walk_block_data);
+ walk_data.block_local_data_size = 0;
/* Now initialize the dominator walker. */
init_walk_dominator_tree (&walk_data);
- /* Reset block_forwardable in each block's annotation. We use that
- attribute when threading through COND_EXPRs. */
- FOR_EACH_BB (bb)
- bb_ann (bb)->forwardable = 1;
-
calculate_dominance_info (CDI_DOMINATORS);
+ /* We need to know which edges exit loops so that we can
+ aggressively thread through loop headers to an exit
+ edge. */
+ flow_loops_find (&loops_info);
+ mark_loop_exit_edges (&loops_info);
+ flow_loops_free (&loops_info);
+
+ /* Clean up the CFG so that any forwarder blocks created by loop
+ canonicalization are removed. */
+ cleanup_tree_cfg ();
+
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
have turned into copies which allows better propagation of
/* Optimize the dominator tree. */
cfg_altered = false;
+ /* We need accurate information regarding back edges in the CFG
+ for jump threading. */
+ mark_dfs_back_edges ();
+
/* Recursively walk the dominator tree optimizing statements. */
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- /* Wipe the hash tables. */
+ /* If we exposed any new variables, go ahead and put them into
+ SSA form now, before we handle jump threading. This simplifies
+ interactions between rewriting of _DECL nodes into SSA form
+ and rewriting SSA_NAME nodes into SSA form after block
+ duplication and CFG manipulation. */
+ if (!bitmap_empty_p (vars_to_rename))
+ {
+ rewrite_into_ssa (false);
+ bitmap_clear (vars_to_rename);
+ }
+
+ free_all_edge_infos ();
- if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
- redirect_edges_and_update_ssa_graph (redirection_edges);
+ {
+ block_stmt_iterator bsi;
+ basic_block bb;
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ update_stmt_if_modified (bsi_stmt (bsi));
+ }
+ }
+ }
+ /* Thread jumps, creating duplicate blocks as needed. */
+ cfg_altered |= thread_through_all_blocks ();
- /* We may have made some basic blocks unreachable, remove them. */
- cfg_altered |= delete_unreachable_blocks ();
+ /* Removal of statements may make some EH edges dead. Purge
+ such edges from the CFG as needed. */
+ if (!bitmap_empty_p (need_eh_cleanup))
+ {
+ cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
+ bitmap_zero (need_eh_cleanup);
+ }
- /* If the CFG was altered, then recompute the dominator tree. This
- is not strictly needed if we only removed unreachable blocks, but
- may produce better results. If we threaded jumps, then rebuilding
- the dominator tree is strictly necessary. */
if (cfg_altered)
+ free_dominance_info (CDI_DOMINATORS);
+
+ cfg_altered |= cleanup_tree_cfg ();
+
+ if (rediscover_loops_after_threading)
{
+ /* Rerun basic loop analysis to discover any newly
+ created loops and update the set of exit edges. */
+ rediscover_loops_after_threading = false;
+ flow_loops_find (&loops_info);
+ mark_loop_exit_edges (&loops_info);
+ flow_loops_free (&loops_info);
+
+ /* Remove any forwarder blocks inserted by loop
+ header canonicalization. */
cleanup_tree_cfg ();
- calculate_dominance_info (CDI_DOMINATORS);
}
- /* If we are going to iterate (CFG_ALTERED is true), then we must
- perform any queued renaming before the next iteration. */
- if (cfg_altered
- && bitmap_first_set_bit (vars_to_rename) >= 0)
- {
- rewrite_into_ssa ();
- bitmap_clear (vars_to_rename);
+ calculate_dominance_info (CDI_DOMINATORS);
- /* The into SSA translation may have created new SSA_NAMES whic
- affect the size of CONST_AND_COPIES and VRP_DATA. */
- VARRAY_GROW (const_and_copies, highest_ssa_version);
- VARRAY_GROW (vrp_data, highest_ssa_version);
- }
+ rewrite_ssa_into_ssa ();
/* Reinitialize the various tables. */
bitmap_clear (nonzero_vars);
htab_empty (avail_exprs);
- VARRAY_CLEAR (const_and_copies);
- VARRAY_CLEAR (vrp_data);
+ htab_empty (vrp_data);
for (i = 0; i < num_referenced_vars; i++)
var_ann (referenced_var (i))->current_def = NULL;
- }
- while (cfg_altered);
- /* Remove any unreachable blocks left behind and linearize the CFG. */
- cleanup_tree_cfg ();
+ /* Finally, remove everything except invariants in SSA_NAME_VALUE.
+
+ This must be done before we iterate as we might have a
+ reference to an SSA_NAME which was removed by the call to
+ rewrite_ssa_into_ssa.
+
+ Long term we will be able to let everything in SSA_NAME_VALUE
+ persist. However, for now, we know this is the safe thing to do. */
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ tree value;
+
+ if (!name)
+ continue;
+
+ value = SSA_NAME_VALUE (name);
+ if (value && !is_gimple_min_invariant (value))
+ SSA_NAME_VALUE (name) = NULL;
+ }
+ }
+ while (optimize > 1 && cfg_altered);
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
- /* We emptyed the hash table earlier, now delete it completely. */
+ /* We emptied the hash table earlier, now delete it completely. */
htab_delete (avail_exprs);
+ htab_delete (vrp_data);
/* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
/* And finalize the dominator walker. */
fini_walk_dominator_tree (&walk_data);
- /* Free nonzero_vars. */
- BITMAP_XFREE (nonzero_vars);
+ /* Free nonzero_vars. */
+ BITMAP_FREE (nonzero_vars);
+ BITMAP_FREE (need_eh_cleanup);
+
+ VEC_free (tree_on_heap, block_defs_stack);
+ VEC_free (tree_on_heap, avail_exprs_stack);
+ VEC_free (tree_on_heap, const_and_copies_stack);
+ VEC_free (tree_on_heap, nonzero_vars_stack);
+ VEC_free (tree_on_heap, vrp_variables_stack);
+ VEC_free (tree_on_heap, stmts_to_rescan);
}
static bool
NULL, /* next */
0, /* static_pass_number */
TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_func | TODO_rename_vars
- | TODO_verify_ssa /* todo_flags_finish */
+ | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
static void
thread_across_edge (struct dom_walk_data *walk_data, edge e)
{
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
block_stmt_iterator bsi;
tree stmt = NULL;
tree phi;
/* Each PHI creates a temporary equivalence, record them. */
- for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
- tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
+ tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
tree dst = PHI_RESULT (phi);
- record_const_or_copy (dst, src, &bd->const_and_copies);
- register_new_def (dst, &bd->block_defs);
+
+ /* If the desired argument is not the same as this PHI's result
+ and it is set by a PHI in this block, then we can not thread
+ through this block. */
+ if (src != dst
+ && TREE_CODE (src) == SSA_NAME
+ && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
+ && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
+ return;
+
+ record_const_or_copy (dst, src);
+ register_new_def (dst, &block_defs_stack);
}
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
cached_lhs = TREE_OPERAND (stmt, 1);
else
- cached_lhs = lookup_avail_expr (stmt, NULL, false);
+ cached_lhs = lookup_avail_expr (stmt, false);
lhs = TREE_OPERAND (stmt, 0);
stmt_ann_t ann = stmt_ann (stmt);
use_optype uses = USE_OPS (ann);
vuse_optype vuses = VUSE_OPS (ann);
- tree *uses_copy = xcalloc (NUM_USES (uses), sizeof (tree));
- tree *vuses_copy = xcalloc (NUM_VUSES (vuses), sizeof (tree));
+ tree *uses_copy = xmalloc (NUM_USES (uses) * sizeof (tree));
+ tree *vuses_copy = xmalloc (NUM_VUSES (vuses) * sizeof (tree));
unsigned int i;
/* Make a copy of the uses into USES_COPY, then cprop into
uses_copy[i] = USE_OP (uses, i);
if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
- tmp = get_value_for (USE_OP (uses, i), const_and_copies);
- if (tmp)
- *USE_OP_PTR (uses, i) = tmp;
+ tmp = SSA_NAME_VALUE (USE_OP (uses, i));
+ if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
+ SET_USE_OP (uses, i, tmp);
}
/* Similarly for virtual uses. */
vuses_copy[i] = VUSE_OP (vuses, i);
if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
- tmp = get_value_for (VUSE_OP (vuses, i), const_and_copies);
- if (tmp)
- VUSE_OP (vuses, i) = tmp;
+ tmp = SSA_NAME_VALUE (VUSE_OP (vuses, i));
+ if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
+ SET_VUSE_OP (vuses, i, tmp);
}
/* Try to lookup the new expression. */
- cached_lhs = lookup_avail_expr (stmt, NULL, false);
+ cached_lhs = lookup_avail_expr (stmt, false);
/* Restore the statement's original uses/defs. */
for (i = 0; i < NUM_USES (uses); i++)
- *USE_OP_PTR (uses, i) = uses_copy[i];
+ SET_USE_OP (uses, i, uses_copy[i]);
for (i = 0; i < NUM_VUSES (vuses); i++)
- VUSE_OP (vuses, i) = vuses_copy[i];
+ SET_VUSE_OP (vuses, i, vuses_copy[i]);
free (uses_copy);
free (vuses_copy);
if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
break;
- /* If CACHED_LHS does not represent the current value of the undering
+ /* If CACHED_LHS does not represent the current value of the underlying
variable in CACHED_LHS/LHS, then we can not ignore this statement. */
if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
break;
We want to record an equivalence lhs = cache_lhs so that if
the result of this statement is used later we can copy propagate
suitably. */
- record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
- register_new_def (lhs, &bd->block_defs);
+ record_const_or_copy (lhs, cached_lhs);
+ register_new_def (lhs, &block_defs_stack);
}
/* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
arm will be taken. */
if (stmt
&& (TREE_CODE (stmt) == COND_EXPR
- || TREE_CODE (stmt) == SWITCH_EXPR))
+ || TREE_CODE (stmt) == SWITCH_EXPR
+ || TREE_CODE (stmt) == GOTO_EXPR))
{
tree cond, cached_lhs;
- edge e1;
-
- /* Do not forward entry edges into the loop. In the case loop
- has multiple entry edges we may end up in constructing irreducible
- region.
- ??? We may consider forwarding the edges in the case all incoming
- edges forward to the same destination block. */
- if (!e->flags & EDGE_DFS_BACK)
- {
- for (e1 = e->dest->pred; e; e = e->pred_next)
- if (e1->flags & EDGE_DFS_BACK)
- break;
- if (e1)
- return;
- }
/* Now temporarily cprop the operands and try to find the resulting
expression in the hash tables. */
if (TREE_CODE (stmt) == COND_EXPR)
cond = COND_EXPR_COND (stmt);
+ else if (TREE_CODE (stmt) == GOTO_EXPR)
+ cond = GOTO_DESTINATION (stmt);
else
cond = SWITCH_COND (stmt);
- if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
+ if (COMPARISON_CLASS_P (cond))
{
tree dummy_cond, op0, op1;
enum tree_code cond_code;
/* Get the current value of both operands. */
if (TREE_CODE (op0) == SSA_NAME)
{
- tree tmp = get_value_for (op0, const_and_copies);
- if (tmp)
+ tree tmp = SSA_NAME_VALUE (op0);
+ if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
op0 = tmp;
}
if (TREE_CODE (op1) == SSA_NAME)
{
- tree tmp = get_value_for (op1, const_and_copies);
- if (tmp)
+ tree tmp = SSA_NAME_VALUE (op1);
+ if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
op1 = tmp;
}
}
else
{
- TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), cond_code);
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op0;
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1) = op1;
+ TREE_SET_CODE (COND_EXPR_COND (dummy_cond), cond_code);
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op0;
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1) = op1;
}
/* If the conditional folds to an invariant, then we are done,
otherwise look it up in the hash tables. */
cached_lhs = local_fold (COND_EXPR_COND (dummy_cond));
if (! is_gimple_min_invariant (cached_lhs))
- cached_lhs = lookup_avail_expr (dummy_cond, NULL, false);
- if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
{
- stmt_ann_t ann = get_stmt_ann (dummy_cond);
- cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
- NULL,
- ann,
- false);
+ cached_lhs = lookup_avail_expr (dummy_cond, false);
+ if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
+ cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
+ NULL,
+ false);
}
}
/* We can have conditionals which just test the state of a
else if (TREE_CODE (cond) == SSA_NAME)
{
cached_lhs = cond;
- cached_lhs = get_value_for (cached_lhs, const_and_copies);
+ cached_lhs = SSA_NAME_VALUE (cached_lhs);
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
cached_lhs = 0;
}
else
- cached_lhs = lookup_avail_expr (stmt, NULL, false);
+ cached_lhs = lookup_avail_expr (stmt, false);
if (cached_lhs)
{
edge taken_edge = find_taken_edge (e->dest, cached_lhs);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
- if (dest == e->src)
+ if (dest == e->dest)
return;
/* If we have a known destination for the conditional, then
we can perform this optimization, which saves at least one
conditional jump each time it applies since we get to
- bypass the conditional at our original destination.
-
- Note that we can either thread through a block with PHIs
- or to a block with PHIs, but not both. At this time the
- bookkeeping to keep the CFG & SSA up-to-date has proven
- difficult. */
+ bypass the conditional at our original destination. */
if (dest)
{
- int saved_forwardable = bb_ann (e->src)->forwardable;
- edge tmp_edge;
-
- bb_ann (e->src)->forwardable = 0;
- tmp_edge = tree_block_forwards_to (dest);
- taken_edge = (tmp_edge ? tmp_edge : taken_edge);
- bb_ann (e->src)->forwardable = saved_forwardable;
- VARRAY_PUSH_EDGE (redirection_edges, e);
- VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
+ struct edge_info *edge_info;
+
+ update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
+ e->count, taken_edge);
+ if (e->aux)
+ edge_info = e->aux;
+ else
+ edge_info = allocate_edge_info (e);
+ edge_info->redirection_target = taken_edge;
+ bb_ann (e->dest)->incoming_edge_threaded = true;
}
}
}
}
-/* Initialize the local stacks.
-
- AVAIL_EXPRS stores all the expressions made available in this block.
-
- CONST_AND_COPIES stores var/value pairs to restore at the end of this
- block.
-
- NONZERO_VARS stores the vars which have a nonzero value made in this
- block.
-
- STMTS_TO_RESCAN is a list of statements we will rescan for operands.
-
- VRP_VARIABLES is the list of variables which have had their values
- constrained by an operation in this block.
-
- These stacks are cleared in the finalization routine run for each
- block. */
-
-static void
-dom_opt_initialize_block_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb ATTRIBUTE_UNUSED,
- bool recycled ATTRIBUTE_UNUSED)
-{
-#ifdef ENABLE_CHECKING
- struct dom_walk_block_data *bd
- = (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
-
- /* We get cleared memory from the allocator, so if the memory is not
- cleared, then we are re-using a previously allocated entry. In
- that case, we can also re-use the underlying virtual arrays. Just
- make sure we clear them before using them! */
- if (recycled)
- {
- if (bd->avail_exprs && VARRAY_ACTIVE_SIZE (bd->avail_exprs) > 0)
- abort ();
- if (bd->const_and_copies && VARRAY_ACTIVE_SIZE (bd->const_and_copies) > 0)
- abort ();
- if (bd->nonzero_vars && VARRAY_ACTIVE_SIZE (bd->nonzero_vars) > 0)
- abort ();
- if (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
- abort ();
- if (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
- abort ();
- if (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
- abort ();
- }
-#endif
-}
-
/* Initialize local stacks for this optimizer and record equivalences
upon entry to BB. Equivalences can come from the edge traversed to
reach BB or they may come from PHI nodes at the start of BB. */
static void
-dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
+dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
- record_equivalences_from_incoming_edge (walk_data, bb);
+ /* Push a marker on the stacks of local information so that we know how
+ far to unwind when we finalize this block. */
+ VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, nonzero_vars_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, vrp_variables_stack, NULL_TREE);
+
+ record_equivalences_from_incoming_edge (bb);
/* PHI nodes can create equivalences too. */
- record_equivalences_from_phis (walk_data, bb);
+ record_equivalences_from_phis (bb);
}
/* Given an expression EXPR (a relational expression or a statement),
For the former case, we have no annotation and we want to hash the
conditional expression. In the latter case we have an annotation and
we want to record the expression the statement evaluates. */
- if (TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
- || TREE_CODE (expr) == TRUTH_NOT_EXPR)
+ if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
{
element->ann = NULL;
element->rhs = expr;
LIMIT entries left in LOCALs. */
static void
-remove_local_expressions_from_table (varray_type locals,
- unsigned limit,
- htab_t table)
+remove_local_expressions_from_table (void)
{
- if (! locals)
- return;
-
/* Remove all the expressions made available in this block. */
- while (VARRAY_ACTIVE_SIZE (locals) > limit)
+ while (VEC_length (tree_on_heap, avail_exprs_stack) > 0)
{
struct expr_hash_elt element;
- tree expr = VARRAY_TOP_TREE (locals);
- VARRAY_POP (locals);
+ tree expr = VEC_pop (tree_on_heap, avail_exprs_stack);
+
+ if (expr == NULL_TREE)
+ break;
initialize_hash_element (expr, NULL, &element);
- htab_remove_elt_with_hash (table, &element, element.hash);
+ htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
}
}
state, stopping when there are LIMIT entries left in LOCALs. */
static void
-restore_nonzero_vars_to_original_value (varray_type locals,
- unsigned limit,
- bitmap table)
+restore_nonzero_vars_to_original_value (void)
{
- if (!locals)
- return;
-
- while (VARRAY_ACTIVE_SIZE (locals) > limit)
+ while (VEC_length (tree_on_heap, nonzero_vars_stack) > 0)
{
- tree name = VARRAY_TOP_TREE (locals);
- VARRAY_POP (locals);
- bitmap_clear_bit (table, SSA_NAME_VERSION (name));
+ tree name = VEC_pop (tree_on_heap, nonzero_vars_stack);
+
+ if (name == NULL)
+ break;
+
+ bitmap_clear_bit (nonzero_vars, SSA_NAME_VERSION (name));
}
}
-/* Use the source/dest pairs in LOCALS to restore TABLE to its original
- state, stopping when there are LIMIT entries left in LOCALs. */
+/* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
+ CONST_AND_COPIES to its original state, stopping when we hit a
+ NULL marker. */
static void
-restore_vars_to_original_value (varray_type locals,
- unsigned limit,
- varray_type table)
+restore_vars_to_original_value (void)
{
- if (! locals)
- return;
-
- while (VARRAY_ACTIVE_SIZE (locals) > limit)
+ while (VEC_length (tree_on_heap, const_and_copies_stack) > 0)
{
tree prev_value, dest;
- prev_value = VARRAY_TOP_TREE (locals);
- VARRAY_POP (locals);
- dest = VARRAY_TOP_TREE (locals);
- VARRAY_POP (locals);
+ dest = VEC_pop (tree_on_heap, const_and_copies_stack);
+
+ if (dest == NULL)
+ break;
- set_value_for (dest, prev_value, table);
+ prev_value = VEC_pop (tree_on_heap, const_and_copies_stack);
+ SSA_NAME_VALUE (dest) = prev_value;
}
}
/* Similar to restore_vars_to_original_value, except that it restores
CURRDEFS to its original value. */
static void
-restore_currdefs_to_original_value (varray_type locals, unsigned limit)
+restore_currdefs_to_original_value (void)
{
- if (!locals)
- return;
-
/* Restore CURRDEFS to its original state. */
- while (VARRAY_ACTIVE_SIZE (locals) > limit)
+ while (VEC_length (tree_on_heap, block_defs_stack) > 0)
{
- tree tmp = VARRAY_TOP_TREE (locals);
+ tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
tree saved_def, var;
- VARRAY_POP (locals);
+ if (tmp == NULL_TREE)
+ break;
/* If we recorded an SSA_NAME, then make the SSA_NAME the current
definition of its underlying variable. If we recorded anything
static void
dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
{
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
tree last;
- /* If we are at a leaf node in the dominator graph, see if we can thread
+ /* If we are at a leaf node in the dominator tree, see if we can thread
the edge from BB through its successor.
Do this before we remove entries from our equivalence tables. */
- if (bb->succ
- && ! bb->succ->succ_next
- && (bb->succ->flags & EDGE_ABNORMAL) == 0
- && (get_immediate_dominator (CDI_DOMINATORS, bb->succ->dest) != bb
- || phi_nodes (bb->succ->dest)))
+ if (single_succ_p (bb)
+ && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
+ && (get_immediate_dominator (CDI_DOMINATORS, single_succ (bb)) != bb
+ || phi_nodes (single_succ (bb))))
{
- thread_across_edge (walk_data, bb->succ);
+ thread_across_edge (walk_data, single_succ_edge (bb));
+ }
+ else if ((last = last_stmt (bb))
+ && TREE_CODE (last) == GOTO_EXPR
+ && TREE_CODE (TREE_OPERAND (last, 0)) == SSA_NAME)
+ {
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ thread_across_edge (walk_data, e);
+ }
}
else if ((last = last_stmt (bb))
&& TREE_CODE (last) == COND_EXPR
- && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last))) == '<'
+ && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
|| TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
- && bb->succ
- && (bb->succ->flags & EDGE_ABNORMAL) == 0
- && bb->succ->succ_next
- && (bb->succ->succ_next->flags & EDGE_ABNORMAL) == 0
- && ! bb->succ->succ_next->succ_next)
+ && EDGE_COUNT (bb->succs) == 2
+ && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
+ && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
{
edge true_edge, false_edge;
- tree cond, inverted = NULL;
- enum tree_code cond_code;
extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
- cond = COND_EXPR_COND (last);
- cond_code = TREE_CODE (cond);
-
- if (TREE_CODE_CLASS (cond_code) == '<')
- inverted = invert_truthvalue (cond);
-
/* If the THEN arm is the end of a dominator tree or has PHI nodes,
then try to thread through its edge. */
if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
|| phi_nodes (true_edge->dest))
{
- unsigned avail_expr_limit;
- unsigned const_and_copies_limit;
- unsigned currdefs_limit;
-
- avail_expr_limit
- = bd->avail_exprs ? VARRAY_ACTIVE_SIZE (bd->avail_exprs) : 0;
- const_and_copies_limit
- = bd->const_and_copies ? VARRAY_ACTIVE_SIZE (bd->const_and_copies)
- : 0;
- currdefs_limit
- = bd->block_defs ? VARRAY_ACTIVE_SIZE (bd->block_defs) : 0;
-
- /* Record any equivalences created by following this edge. */
- if (TREE_CODE_CLASS (cond_code) == '<')
+ struct edge_info *edge_info;
+ unsigned int i;
+
+ /* Push a marker onto the available expression stack so that we
+ unwind any expressions related to the TRUE arm before processing
+ the false arm below. */
+ VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
+ VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
+
+ edge_info = true_edge->aux;
+
+ /* If we have info associated with this edge, record it into
+ our equivalency tables. */
+ if (edge_info)
{
- record_cond (cond, boolean_true_node, &bd->avail_exprs);
- record_cond (inverted, boolean_false_node, &bd->avail_exprs);
+ tree *cond_equivalences = edge_info->cond_equivalences;
+ tree lhs = edge_info->lhs;
+ tree rhs = edge_info->rhs;
+
+ /* If we have a simple NAME = VALUE equivalency record it.
+ Until the jump threading selection code improves, only
+ do this if both the name and value are SSA_NAMEs with
+ the same underlying variable to avoid missing threading
+ opportunities. */
+ if (lhs
+ && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME
+ && TREE_CODE (edge_info->rhs) == SSA_NAME
+ && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))
+ record_const_or_copy (lhs, rhs);
+
+ /* If we have 0 = COND or 1 = COND equivalences, record them
+ into our expression hash tables. */
+ if (cond_equivalences)
+ for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
+ {
+ tree expr = cond_equivalences[i];
+ tree value = cond_equivalences[i + 1];
+
+ record_cond (expr, value);
+ }
}
- else if (cond_code == SSA_NAME)
- record_const_or_copy (cond, boolean_true_node,
- &bd->const_and_copies);
/* Now thread the edge. */
thread_across_edge (walk_data, true_edge);
/* And restore the various tables to their state before
we threaded this edge. */
- remove_local_expressions_from_table (bd->avail_exprs,
- avail_expr_limit,
- avail_exprs);
- restore_vars_to_original_value (bd->const_and_copies,
- const_and_copies_limit,
- const_and_copies);
- restore_currdefs_to_original_value (bd->block_defs, currdefs_limit);
+ remove_local_expressions_from_table ();
+ restore_vars_to_original_value ();
+ restore_currdefs_to_original_value ();
}
/* Similarly for the ELSE arm. */
if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
|| phi_nodes (false_edge->dest))
{
- /* Record any equivalences created by following this edge. */
- if (TREE_CODE_CLASS (cond_code) == '<')
+ struct edge_info *edge_info;
+ unsigned int i;
+
+ edge_info = false_edge->aux;
+
+ /* If we have info associated with this edge, record it into
+ our equivalency tables. */
+ if (edge_info)
{
- record_cond (cond, boolean_false_node, &bd->avail_exprs);
- record_cond (inverted, boolean_true_node, &bd->avail_exprs);
+ tree *cond_equivalences = edge_info->cond_equivalences;
+ tree lhs = edge_info->lhs;
+ tree rhs = edge_info->rhs;
+
+ /* If we have a simple NAME = VALUE equivalency record it.
+ Until the jump threading selection code improves, only
+ do this if both the name and value are SSA_NAMEs with
+ the same underlying variable to avoid missing threading
+ opportunities. */
+ if (lhs
+ && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
+ record_const_or_copy (lhs, rhs);
+
+ /* If we have 0 = COND or 1 = COND equivalences, record them
+ into our expression hash tables. */
+ if (cond_equivalences)
+ for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
+ {
+ tree expr = cond_equivalences[i];
+ tree value = cond_equivalences[i + 1];
+
+ record_cond (expr, value);
+ }
}
- else if (cond_code == SSA_NAME)
- record_const_or_copy (cond, boolean_false_node,
- &bd->const_and_copies);
thread_across_edge (walk_data, false_edge);
}
}
- remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
- restore_nonzero_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
- restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
- restore_currdefs_to_original_value (bd->block_defs, 0);
+ remove_local_expressions_from_table ();
+ restore_nonzero_vars_to_original_value ();
+ restore_vars_to_original_value ();
+ restore_currdefs_to_original_value ();
/* Remove VRP records associated with this basic block. They are no
longer valid.
To be efficient, we note which variables have had their values
constrained in this block. So walk over each variable in the
VRP_VARIABLEs array. */
- while (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
+ while (VEC_length (tree_on_heap, vrp_variables_stack) > 0)
{
- tree var = VARRAY_TOP_TREE (bd->vrp_variables);
+ tree var = VEC_pop (tree_on_heap, vrp_variables_stack);
+ struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
+ void **slot;
/* Each variable has a stack of value range records. We want to
invalidate those associated with our basic block. So we walk
the array backwards popping off records associated with our
block. Once we hit a record not associated with our block
we are done. */
- varray_type var_vrp_records = VARRAY_GENERIC_PTR (vrp_data,
- SSA_NAME_VERSION (var));
+ varray_type var_vrp_records;
+
+ if (var == NULL)
+ break;
+
+ vrp_hash_elt.var = var;
+ vrp_hash_elt.records = NULL;
+
+ slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
+
+ vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
+ var_vrp_records = vrp_hash_elt_p->records;
while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
{
VARRAY_POP (var_vrp_records);
}
-
- VARRAY_POP (bd->vrp_variables);
}
- /* Re-scan operands in all statements that may have had new symbols
- exposed. */
- while (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
+ /* If we queued any statements to rescan in this block, then
+ go ahead and rescan them now. */
+ while (VEC_length (tree_on_heap, stmts_to_rescan) > 0)
{
- tree stmt = VARRAY_TOP_TREE (bd->stmts_to_rescan);
- VARRAY_POP (bd->stmts_to_rescan);
+ tree stmt = VEC_last (tree_on_heap, stmts_to_rescan);
+ basic_block stmt_bb = bb_for_stmt (stmt);
+
+ if (stmt_bb != bb)
+ break;
+
+ VEC_pop (tree_on_heap, stmts_to_rescan);
mark_new_vars_to_rename (stmt, vars_to_rename);
}
}
even if we do not know its exact value. */
static void
-record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block bb)
+record_equivalences_from_phis (basic_block bb)
{
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
tree phi;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree lhs = PHI_RESULT (phi);
tree rhs = NULL;
{
tree t = PHI_ARG_DEF (phi, i);
- if (TREE_CODE (t) == SSA_NAME || is_gimple_min_invariant (t))
- {
- /* Ignore alternatives which are the same as our LHS. */
- if (operand_equal_p (lhs, t, 0))
- continue;
-
- /* If we have not processed an alternative yet, then set
- RHS to this alternative. */
- if (rhs == NULL)
- rhs = t;
- /* If we have processed an alternative (stored in RHS), then
- see if it is equal to this one. If it isn't, then stop
- the search. */
- else if (! operand_equal_p (rhs, t, 0))
- break;
- }
- else
+ /* Ignore alternatives which are the same as our LHS. Since
+ LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
+ can simply compare pointers. */
+ if (lhs == t)
+ continue;
+
+ /* If we have not processed an alternative yet, then set
+ RHS to this alternative. */
+ if (rhs == NULL)
+ rhs = t;
+ /* If we have processed an alternative (stored in RHS), then
+ see if it is equal to this one. If it isn't, then stop
+ the search. */
+ else if (! operand_equal_for_phi_arg_p (rhs, t))
break;
}
by this assignment, so unwinding just costs time and space. */
if (i == PHI_NUM_ARGS (phi)
&& may_propagate_copy (lhs, rhs))
- set_value_for (lhs, rhs, const_and_copies);
+ SSA_NAME_VALUE (lhs) = rhs;
/* Now see if we know anything about the nonzero property for the
result of this PHI. */
if (i == PHI_NUM_ARGS (phi))
bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
- register_new_def (lhs, &bd->block_defs);
+ register_new_def (lhs, &block_defs_stack);
}
}
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+ return that edge. Otherwise return NULL. */
+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)
+ {
+ /* A loop back edge can be identified by the destination of
+ the edge dominating the source of the edge. */
+ if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+ continue;
+
+ /* If we have already seen a non-loop edge, then we must have
+ multiple incoming non-loop edges and thus we return NULL. */
+ if (retval)
+ return NULL;
+
+ /* This is the first non-loop incoming edge we have found. Record
+ it. */
+ retval = e;
+ }
+
+ return retval;
+}
+
/* Record any equivalences created by the incoming edge to BB. If BB
has more than one incoming edge, then no equivalence is created. */
static void
-record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data,
- basic_block bb)
+record_equivalences_from_incoming_edge (basic_block bb)
{
- int edge_flags;
+ edge e;
basic_block parent;
- struct eq_expr_value eq_expr_value;
- tree parent_block_last_stmt = NULL;
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
+ struct edge_info *edge_info;
- /* If our parent block ended with a control statment, then we may be
+ /* If our parent block ended with a control statement, then we may be
able to record some equivalences based on which outgoing edge from
the parent was followed. */
parent = get_immediate_dominator (CDI_DOMINATORS, bb);
- if (parent)
- {
- parent_block_last_stmt = last_stmt (parent);
- if (parent_block_last_stmt && !is_ctrl_stmt (parent_block_last_stmt))
- parent_block_last_stmt = NULL;
- }
- eq_expr_value.src = NULL;
- eq_expr_value.dst = NULL;
+ e = single_incoming_edge_ignoring_loop_edges (bb);
- /* If we have a single predecessor, then extract EDGE_FLAGS from
- our single incoming edge. Otherwise clear EDGE_FLAGS and
- PARENT_BLOCK_LAST_STMT since they're not needed. */
- if (bb->pred
- && ! bb->pred->pred_next
- && parent_block_last_stmt
- && bb_for_stmt (parent_block_last_stmt) == bb->pred->src)
+ /* If we had a single incoming edge from our parent block, then enter
+ any data associated with the edge into our tables. */
+ if (e && e->src == parent)
{
- edge_flags = bb->pred->flags;
- }
- else
- {
- edge_flags = 0;
- parent_block_last_stmt = NULL;
- }
+ unsigned int i;
- /* If our parent block ended in a COND_EXPR, add any equivalences
- created by the COND_EXPR to the hash table and initialize
- EQ_EXPR_VALUE appropriately.
-
- EQ_EXPR_VALUE is an assignment expression created when BB's immediate
- dominator ends in a COND_EXPR statement whose predicate is of the form
- 'VAR == VALUE', where VALUE may be another variable or a constant.
- This is used to propagate VALUE on the THEN_CLAUSE of that
- conditional. This assignment is inserted in CONST_AND_COPIES so that
- the copy and constant propagator can find more propagation
- opportunities. */
- if (parent_block_last_stmt
- && bb->pred->pred_next == NULL
- && TREE_CODE (parent_block_last_stmt) == COND_EXPR
- && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
- eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
- (edge_flags & EDGE_TRUE_VALUE) != 0,
- &bd->avail_exprs,
- bb,
- &bd->vrp_variables);
- /* Similarly when the parent block ended in a SWITCH_EXPR.
- We can only know the value of the switch's condition if the dominator
- parent is also the only predecessor of this block. */
- else if (parent_block_last_stmt
- && bb->pred->pred_next == NULL
- && bb->pred->src == parent
- && TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
- {
- tree switch_cond = SWITCH_COND (parent_block_last_stmt);
+ edge_info = e->aux;
- /* If the switch's condition is an SSA variable, then we may
- know its value at each of the case labels. */
- if (TREE_CODE (switch_cond) == SSA_NAME)
+ if (edge_info)
{
- tree switch_vec = SWITCH_LABELS (parent_block_last_stmt);
- size_t i, n = TREE_VEC_LENGTH (switch_vec);
- int case_count = 0;
- tree match_case = NULL_TREE;
-
- /* Search the case labels for those whose destination is
- the current basic block. */
- for (i = 0; i < n; ++i)
+ tree lhs = edge_info->lhs;
+ tree rhs = edge_info->rhs;
+ tree *cond_equivalences = edge_info->cond_equivalences;
+
+ if (lhs)
+ record_equality (lhs, rhs);
+
+ if (cond_equivalences)
{
- tree elt = TREE_VEC_ELT (switch_vec, i);
- if (label_to_block (CASE_LABEL (elt)) == bb)
+ bool recorded_range = false;
+ for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
{
- if (++case_count > 1 || CASE_HIGH (elt))
- break;
- match_case = elt;
+ tree expr = cond_equivalences[i];
+ tree value = cond_equivalences[i + 1];
+
+ record_cond (expr, value);
+
+ /* For the first true equivalence, record range
+ information. We only do this for the first
+ true equivalence as it should dominate any
+ later true equivalences. */
+ if (! recorded_range
+ && COMPARISON_CLASS_P (expr)
+ && value == boolean_true_node
+ && TREE_CONSTANT (TREE_OPERAND (expr, 1)))
+ {
+ record_range (expr, bb);
+ recorded_range = true;
+ }
}
}
-
- /* If we encountered precisely one CASE_LABEL_EXPR and it
- was not the default case, or a case range, then we know
- the exact value of SWITCH_COND which caused us to get to
- this block. Record that equivalence in EQ_EXPR_VALUE. */
- if (case_count == 1
- && match_case
- && CASE_LOW (match_case)
- && !CASE_HIGH (match_case))
- {
- eq_expr_value.dst = switch_cond;
- eq_expr_value.src = CASE_LOW (match_case);
- }
}
}
-
- /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
- new value for VAR, so that occurrences of VAR can be replaced with
- VALUE while re-writing the THEN arm of a COND_EXPR. */
- if (eq_expr_value.src && eq_expr_value.dst)
- record_equality (eq_expr_value.dst, eq_expr_value.src,
- &bd->const_and_copies);
}
/* Dump SSA statistics on FILE. */
value, then we do nothing. */
static void
-record_var_is_nonzero (tree var, varray_type *block_nonzero_vars_p)
+record_var_is_nonzero (tree var)
{
int indx = SSA_NAME_VERSION (var);
/* Record this SSA_NAME so that we can reset the global table
when we leave this block. */
- if (! *block_nonzero_vars_p)
- VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
- VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
+ VEC_safe_push (tree_on_heap, nonzero_vars_stack, var);
}
/* Enter a statement into the true/false expression hash table indicating
that the condition COND has the value VALUE. */
static void
-record_cond (tree cond, tree value, varray_type *block_avail_exprs_p)
+record_cond (tree cond, tree value)
{
struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
void **slot;
initialize_hash_element (cond, value, element);
slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
- element->hash, true);
+ element->hash, INSERT);
if (*slot == NULL)
{
*slot = (void *) element;
- if (! *block_avail_exprs_p)
- VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
- VARRAY_PUSH_TREE (*block_avail_exprs_p, cond);
+ VEC_safe_push (tree_on_heap, avail_exprs_stack, cond);
}
else
free (element);
}
+/* Build a new conditional using NEW_CODE, OP0 and OP1 and store
+ the new conditional into *p, then store a boolean_true_node
+ into *(p + 1). */
+
+static void
+build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
+{
+ *p = build2 (new_code, boolean_type_node, op0, op1);
+ p++;
+ *p = boolean_true_node;
+}
+
+/* Record that COND is true and INVERTED is false into the edge information
+ structure. Also record that any conditions dominated by COND are true
+ as well.
+
+ For example, if a < b is true, then a <= b must also be true. */
+
+static void
+record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
+{
+ tree op0, op1;
+
+ if (!COMPARISON_CLASS_P (cond))
+ return;
+
+ op0 = TREE_OPERAND (cond, 0);
+ op1 = TREE_OPERAND (cond, 1);
+
+ switch (TREE_CODE (cond))
+ {
+ case LT_EXPR:
+ case GT_EXPR:
+ edge_info->max_cond_equivalences = 12;
+ edge_info->cond_equivalences = xmalloc (12 * sizeof (tree));
+ build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
+ ? LE_EXPR : GE_EXPR),
+ op0, op1, &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ build_and_record_new_cond (NE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[8]);
+ build_and_record_new_cond (LTGT_EXPR, op0, op1,
+ &edge_info->cond_equivalences[10]);
+ break;
+
+ case GE_EXPR:
+ case LE_EXPR:
+ edge_info->max_cond_equivalences = 6;
+ edge_info->cond_equivalences = xmalloc (6 * sizeof (tree));
+ build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+ &edge_info->cond_equivalences[4]);
+ break;
+
+ case EQ_EXPR:
+ edge_info->max_cond_equivalences = 10;
+ edge_info->cond_equivalences = xmalloc (10 * sizeof (tree));
+ build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+ &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (LE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ build_and_record_new_cond (GE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[8]);
+ break;
+
+ case UNORDERED_EXPR:
+ edge_info->max_cond_equivalences = 16;
+ edge_info->cond_equivalences = xmalloc (16 * sizeof (tree));
+ build_and_record_new_cond (NE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (UNLE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ build_and_record_new_cond (UNGE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[8]);
+ build_and_record_new_cond (UNEQ_EXPR, op0, op1,
+ &edge_info->cond_equivalences[10]);
+ build_and_record_new_cond (UNLT_EXPR, op0, op1,
+ &edge_info->cond_equivalences[12]);
+ build_and_record_new_cond (UNGT_EXPR, op0, op1,
+ &edge_info->cond_equivalences[14]);
+ break;
+
+ case UNLT_EXPR:
+ case UNGT_EXPR:
+ edge_info->max_cond_equivalences = 8;
+ edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+ build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
+ ? UNLE_EXPR : UNGE_EXPR),
+ op0, op1, &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (NE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ break;
+
+ case UNEQ_EXPR:
+ edge_info->max_cond_equivalences = 8;
+ edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+ build_and_record_new_cond (UNLE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (UNGE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ break;
+
+ case LTGT_EXPR:
+ edge_info->max_cond_equivalences = 8;
+ edge_info->cond_equivalences = xmalloc (8 * sizeof (tree));
+ build_and_record_new_cond (NE_EXPR, op0, op1,
+ &edge_info->cond_equivalences[4]);
+ build_and_record_new_cond (ORDERED_EXPR, op0, op1,
+ &edge_info->cond_equivalences[6]);
+ break;
+
+ default:
+ edge_info->max_cond_equivalences = 4;
+ edge_info->cond_equivalences = xmalloc (4 * sizeof (tree));
+ break;
+ }
+
+ /* Now store the original true and false conditions into the first
+ two slots. */
+ edge_info->cond_equivalences[0] = cond;
+ edge_info->cond_equivalences[1] = boolean_true_node;
+ edge_info->cond_equivalences[2] = inverted;
+ edge_info->cond_equivalences[3] = boolean_false_node;
+}
+
/* A helper function for record_const_or_copy and record_equality.
Do the work of recording the value and undo info. */
static void
-record_const_or_copy_1 (tree x, tree y, tree prev_x,
- varray_type *block_const_and_copies_p)
+record_const_or_copy_1 (tree x, tree y, tree prev_x)
{
- set_value_for (x, y, const_and_copies);
+ SSA_NAME_VALUE (x) = y;
- if (!*block_const_and_copies_p)
- VARRAY_TREE_INIT (*block_const_and_copies_p, 2, "block_const_and_copies");
- VARRAY_PUSH_TREE (*block_const_and_copies_p, x);
- VARRAY_PUSH_TREE (*block_const_and_copies_p, prev_x);
+ VEC_safe_push (tree_on_heap, const_and_copies_stack, prev_x);
+ VEC_safe_push (tree_on_heap, const_and_copies_stack, x);
}
+
+/* Return the loop depth of the basic block of the defining statement of X.
+ This number should not be treated as absolutely correct because the loop
+ information may not be completely up-to-date when dom runs. However, it
+ will be relatively correct, and as more passes are taught to keep loop info
+ up to date, the result will become more and more accurate. */
+
+static int
+loop_depth_of_name (tree x)
+{
+ tree defstmt;
+ basic_block defbb;
+
+ /* If it's not an SSA_NAME, we have no clue where the definition is. */
+ if (TREE_CODE (x) != SSA_NAME)
+ return 0;
+
+ /* Otherwise return the loop depth of the defining statement's bb.
+ Note that there may not actually be a bb for this statement, if the
+ ssa_name is live on entry. */
+ defstmt = SSA_NAME_DEF_STMT (x);
+ defbb = bb_for_stmt (defstmt);
+ if (!defbb)
+ return 0;
+
+ return defbb->loop_depth;
+}
+
+
/* Record that X is equal to Y in const_and_copies. Record undo
- information in the block-local varray. */
+ information in the block-local vector. */
static void
-record_const_or_copy (tree x, tree y, varray_type *block_const_and_copies_p)
+record_const_or_copy (tree x, tree y)
{
- tree prev_x = get_value_for (x, const_and_copies);
+ tree prev_x = SSA_NAME_VALUE (x);
if (TREE_CODE (y) == SSA_NAME)
{
- tree tmp = get_value_for (y, const_and_copies);
+ tree tmp = SSA_NAME_VALUE (y);
if (tmp)
y = tmp;
}
- record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
+ record_const_or_copy_1 (x, y, prev_x);
}
/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
This constrains the cases in which we may treat this as assignment. */
static void
-record_equality (tree x, tree y, varray_type *block_const_and_copies_p)
+record_equality (tree x, tree y)
{
tree prev_x = NULL, prev_y = NULL;
if (TREE_CODE (x) == SSA_NAME)
- prev_x = get_value_for (x, const_and_copies);
+ prev_x = SSA_NAME_VALUE (x);
if (TREE_CODE (y) == SSA_NAME)
- prev_y = get_value_for (y, const_and_copies);
+ prev_y = SSA_NAME_VALUE (y);
- /* If one of the previous values is invariant, then use that.
+ /* If one of the previous values is invariant, or invariant in more loops
+ (by depth), then use that.
Otherwise it doesn't matter which value we choose, just so
long as we canonicalize on one value. */
if (TREE_INVARIANT (y))
;
- else if (TREE_INVARIANT (x))
+ else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && TREE_INVARIANT (prev_x))
x = y, y = prev_x, prev_x = prev_y;
- else if (prev_y)
+ else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE)
y = prev_y;
/* After the swapping, we must have one SSA_NAME. */
|| REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
return;
- record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
+ record_const_or_copy_1 (x, y, prev_x);
+}
+
+/* Return true, if it is ok to do folding of an associative expression.
+ EXP is the tree for the associative expression. */
+
+static inline bool
+unsafe_associative_fp_binop (tree exp)
+{
+ enum tree_code code = TREE_CODE (exp);
+ return !(!flag_unsafe_math_optimizations
+ && (code == MULT_EXPR || code == PLUS_EXPR
+ || code == MINUS_EXPR)
+ && FLOAT_TYPE_P (TREE_TYPE (exp)));
+}
+
+/* Returns true when STMT is a simple iv increment. It detects the
+ following situation:
+
+ i_1 = phi (..., i_2)
+ i_2 = i_1 +/- ... */
+
+static bool
+simple_iv_increment_p (tree stmt)
+{
+ tree lhs, rhs, preinc, phi;
+ unsigned i;
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return false;
+
+ lhs = TREE_OPERAND (stmt, 0);
+ if (TREE_CODE (lhs) != SSA_NAME)
+ return false;
+
+ rhs = TREE_OPERAND (stmt, 1);
+
+ if (TREE_CODE (rhs) != PLUS_EXPR
+ && TREE_CODE (rhs) != MINUS_EXPR)
+ return false;
+
+ preinc = TREE_OPERAND (rhs, 0);
+ if (TREE_CODE (preinc) != SSA_NAME)
+ return false;
+
+ phi = SSA_NAME_DEF_STMT (preinc);
+ if (TREE_CODE (phi) != PHI_NODE)
+ return false;
+
+ for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+ if (PHI_ARG_DEF (phi, i) == lhs)
+ return true;
+
+ return false;
}
/* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
- tree stmt,
- stmt_ann_t ann,
- int insert)
+ tree stmt, int insert)
{
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhs_code = TREE_CODE (rhs);
tree result = NULL;
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
/* If we have lhs = ~x, look and see if we earlier had x = ~y.
In which case we can change this statement to be lhs = y.
&& ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
result = update_rhs_and_lookup_avail_expr (stmt,
rhs_def_operand,
- &bd->avail_exprs,
- ann,
insert);
}
}
{
tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
+ /* If the statement defines an induction variable, do not propagate
+ its value, so that we do not create overlapping life ranges. */
+ if (simple_iv_increment_p (rhs_def_stmt))
+ goto dont_fold_assoc;
+
/* See if the RHS_DEF_STMT has the same form as our statement. */
if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
{
tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
- if (rhs_code == rhs_def_code
+ if ((rhs_code == rhs_def_code && unsafe_associative_fp_binop (rhs))
|| (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
|| (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
{
tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
tree t;
+ /* If we care about correct floating point results, then
+ don't fold x + c1 - c2. Note that we need to take both
+ the codes and the signs to figure this out. */
+ if (FLOAT_TYPE_P (type)
+ && !flag_unsafe_math_optimizations
+ && (rhs_def_code == PLUS_EXPR
+ || rhs_def_code == MINUS_EXPR))
+ {
+ bool neg = false;
+
+ neg ^= (rhs_code == MINUS_EXPR);
+ neg ^= (rhs_def_code == MINUS_EXPR);
+ neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
+ neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
+
+ if (neg)
+ goto dont_fold_assoc;
+ }
+
/* Ho hum. So fold will only operate on the outermost
thingy that we give it, so we have to build the new
expression in two pieces. This requires that we handle
/* If the result is a suitable looking gimple expression,
then use it instead of the original for STMT. */
if (TREE_CODE (t) == SSA_NAME
- || (TREE_CODE_CLASS (TREE_CODE (t)) == '1'
+ || (UNARY_CLASS_P (t)
&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
- || ((TREE_CODE_CLASS (TREE_CODE (t)) == '2'
- || TREE_CODE_CLASS (TREE_CODE (t)) == '<')
+ || ((BINARY_CLASS_P (t) || COMPARISON_CLASS_P (t))
&& TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
&& is_gimple_val (TREE_OPERAND (t, 1))))
- result = update_rhs_and_lookup_avail_expr
- (stmt, t, &bd->avail_exprs, ann, insert);
+ result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
}
}
}
+ dont_fold_assoc:;
}
/* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
}
else
{
- TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GT_EXPR);
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
+ TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GT_EXPR);
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
= integer_zero_node;
}
- val = simplify_cond_and_lookup_avail_expr (dummy_cond,
- &bd->avail_exprs,
- NULL, false);
+ val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
}
if (val && integer_onep (val))
if (rhs_code == TRUNC_DIV_EXPR)
t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
- build_int_2 (tree_log2 (op1), 0));
+ build_int_cst (NULL_TREE, tree_log2 (op1)));
else
t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
op1, integer_one_node)));
- result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
}
}
}
else
{
- TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), LE_EXPR);
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
- = fold_convert (type, integer_zero_node);
+ TREE_SET_CODE (COND_EXPR_COND (dummy_cond), LE_EXPR);
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
+ = build_int_cst (type, 0);
}
- val = simplify_cond_and_lookup_avail_expr (dummy_cond,
- &bd->avail_exprs,
- NULL, false);
+ val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
if (!val)
{
- TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GE_EXPR);
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
- TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
- = fold_convert (type, integer_zero_node);
+ TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GE_EXPR);
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
+ TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
+ = build_int_cst (type, 0);
val = simplify_cond_and_lookup_avail_expr (dummy_cond,
- &bd->avail_exprs,
NULL, false);
if (val)
else
t = op;
- result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
}
}
tree t = fold_read_from_constant_string (rhs);
if (t)
- result = update_rhs_and_lookup_avail_expr (stmt, t,
- &bd->avail_exprs,
- ann, insert);
+ result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
}
return result;
static tree
simplify_cond_and_lookup_avail_expr (tree stmt,
- varray_type *block_avail_exprs_p,
stmt_ann_t ann,
int insert)
{
tree cond = COND_EXPR_COND (stmt);
- if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
+ if (COMPARISON_CLASS_P (cond))
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
varray_type vrp_records;
struct vrp_element *element;
+ struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
+ void **slot;
/* First see if we have test of an SSA_NAME against a constant
where the SSA_NAME is defined by an earlier typecast which
/* Update the statement to use the new equivalent
condition. */
COND_EXPR_COND (stmt) = new_cond;
- ann->modified = 1;
+
+ /* If this is not a real stmt, ann will be NULL and we
+ avoid processing the operands. */
+ if (ann)
+ mark_stmt_modified (stmt);
/* Lookup the condition and return its known value if it
exists. */
- new_cond = lookup_avail_expr (stmt, block_avail_exprs_p,
- insert);
+ new_cond = lookup_avail_expr (stmt, insert);
if (new_cond)
return new_cond;
Also note the vast majority of conditionals are not testing
a variable which has had its range constrained by an earlier
conditional. So this filter avoids a lot of unnecessary work. */
- vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (op0));
+ vrp_hash_elt.var = op0;
+ vrp_hash_elt.records = NULL;
+ slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
+ if (slot == NULL)
+ return NULL;
+
+ vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
+ vrp_records = vrp_hash_elt_p->records;
if (vrp_records == NULL)
return NULL;
/* We really want to avoid unnecessary computations of range
info. So all ranges are computed lazily; this avoids a
- lot of unnecessary work. ie, we record the conditional,
+ lot of unnecessary work. i.e., we record the conditional,
but do not process how it constrains the variable's
potential values until we know that processing the condition
could be helpful.
tree tmp_high, tmp_low;
int dummy;
- /* The last element has not been processed. Process it now. */
- extract_range_from_cond (element->cond, &tmp_high,
- &tmp_low, &dummy);
-
+ /* The last element has not been processed. Process it now.
+ record_range should ensure for cond inverted is not set.
+ This call can only fail if cond is x < min or x > max,
+ which fold should have optimized into false.
+ If that doesn't happen, just pretend all values are
+ in the range. */
+ if (! extract_range_from_cond (element->cond, &tmp_high,
+ &tmp_low, &dummy))
+ gcc_unreachable ();
+ else
+ gcc_assert (dummy == 0);
+
/* If this is the only element, then no merging is necessary,
the high/low values from extract_range_from_cond are all
we need. */
condition which we may be able to optimize better. */
static tree
-simplify_switch_and_lookup_avail_expr (tree stmt,
- varray_type *block_avail_exprs_p,
- stmt_ann_t ann,
- int insert)
+simplify_switch_and_lookup_avail_expr (tree stmt, int insert)
{
tree cond = SWITCH_COND (stmt);
tree def, to, ti;
def = TREE_OPERAND (def, 1);
if (TREE_CODE (def) == NOP_EXPR)
{
+ int need_precision;
+ bool fail;
+
def = TREE_OPERAND (def, 0);
+
+#ifdef ENABLE_CHECKING
+ /* ??? Why was Jeff testing this? We are gimple... */
+ gcc_assert (is_gimple_val (def));
+#endif
+
to = TREE_TYPE (cond);
ti = TREE_TYPE (def);
- /* If we have an extension that preserves sign, then we
+ /* If we have an extension that preserves value, then we
can copy the source value into the switch. */
- if (TYPE_UNSIGNED (to) == TYPE_UNSIGNED (ti)
- && TYPE_PRECISION (to) >= TYPE_PRECISION (ti)
- && is_gimple_val (def))
+
+ need_precision = TYPE_PRECISION (ti);
+ fail = false;
+ if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
+ fail = true;
+ else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
+ need_precision += 1;
+ if (TYPE_PRECISION (to) < need_precision)
+ fail = true;
+
+ if (!fail)
{
SWITCH_COND (stmt) = def;
- ann->modified = 1;
+ mark_stmt_modified (stmt);
- return lookup_avail_expr (stmt, block_avail_exprs_p, insert);
+ return lookup_avail_expr (stmt, insert);
}
}
}
return 0;
}
-/* Propagate known constants/copies into PHI nodes of BB's successor
- blocks. */
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
+ even if we don't know their precise value.
+
+ Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
+ nodes of the successors of BB. */
+
+static void
+cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ tree phi;
+ int indx;
+
+ /* If this is an abnormal edge, then we do not want to copy propagate
+ into the PHI alternative associated with this edge. */
+ if (e->flags & EDGE_ABNORMAL)
+ continue;
+
+ phi = phi_nodes (e->dest);
+ if (! phi)
+ continue;
+
+ indx = e->dest_idx;
+ for ( ; phi; phi = PHI_CHAIN (phi))
+ {
+ tree new;
+ use_operand_p orig_p;
+ tree orig;
+
+ /* The alternative may be associated with a constant, so verify
+ it is an SSA_NAME before doing anything with it. */
+ orig_p = PHI_ARG_DEF_PTR (phi, indx);
+ orig = USE_FROM_PTR (orig_p);
+ if (TREE_CODE (orig) != SSA_NAME)
+ continue;
+
+ /* If the alternative is known to have a nonzero value, record
+ that fact in the PHI node itself for future use. */
+ if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
+ PHI_ARG_NONZERO (phi, indx) = true;
+
+ /* If we have *ORIG_P in our constant/copy table, then replace
+ ORIG_P with its value in our constant/copy table. */
+ new = SSA_NAME_VALUE (orig);
+ if (new
+ && (TREE_CODE (new) == SSA_NAME
+ || is_gimple_min_invariant (new))
+ && may_propagate_copy (orig, new))
+ {
+ propagate_value (orig_p, new);
+ }
+ }
+ }
+}
+
+/* We have finished optimizing BB, record any information implied by
+ taking a specific outgoing edge from BB. */
+
+static void
+record_edge_info (basic_block bb)
+{
+ block_stmt_iterator bsi = bsi_last (bb);
+ struct edge_info *edge_info;
+
+ if (! bsi_end_p (bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
+ {
+ tree cond = SWITCH_COND (stmt);
+
+ if (TREE_CODE (cond) == SSA_NAME)
+ {
+ tree labels = SWITCH_LABELS (stmt);
+ int i, n_labels = TREE_VEC_LENGTH (labels);
+ tree *info = xcalloc (n_basic_blocks, sizeof (tree));
+ edge e;
+ edge_iterator ei;
+
+ for (i = 0; i < n_labels; i++)
+ {
+ tree label = TREE_VEC_ELT (labels, i);
+ basic_block target_bb = label_to_block (CASE_LABEL (label));
+
+ if (CASE_HIGH (label)
+ || !CASE_LOW (label)
+ || info[target_bb->index])
+ info[target_bb->index] = error_mark_node;
+ else
+ info[target_bb->index] = label;
+ }
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ basic_block target_bb = e->dest;
+ tree node = info[target_bb->index];
+
+ if (node != NULL && node != error_mark_node)
+ {
+ tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
+ edge_info = allocate_edge_info (e);
+ edge_info->lhs = cond;
+ edge_info->rhs = x;
+ }
+ }
+ free (info);
+ }
+ }
+
+ /* A COND_EXPR may create equivalences too. */
+ if (stmt && TREE_CODE (stmt) == COND_EXPR)
+ {
+ tree cond = COND_EXPR_COND (stmt);
+ edge true_edge;
+ edge false_edge;
+
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ /* If the conditional is a single variable 'X', record 'X = 1'
+ for the true edge and 'X = 0' on the false edge. */
+ if (SSA_VAR_P (cond))
+ {
+ struct edge_info *edge_info;
+
+ edge_info = allocate_edge_info (true_edge);
+ edge_info->lhs = cond;
+ edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
+
+ edge_info = allocate_edge_info (false_edge);
+ edge_info->lhs = cond;
+ edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
+ }
+ /* Equality tests may create one or two equivalences. */
+ else if (COMPARISON_CLASS_P (cond))
+ {
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+
+ /* Special case comparing booleans against a constant as we
+ know the value of OP0 on both arms of the branch. i.e., we
+ can record an equivalence for OP0 rather than COND. */
+ if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
+ && TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
+ && is_gimple_min_invariant (op1))
+ {
+ if (TREE_CODE (cond) == EQ_EXPR)
+ {
+ edge_info = allocate_edge_info (true_edge);
+ edge_info->lhs = op0;
+ edge_info->rhs = (integer_zerop (op1)
+ ? boolean_false_node
+ : boolean_true_node);
+
+ edge_info = allocate_edge_info (false_edge);
+ edge_info->lhs = op0;
+ edge_info->rhs = (integer_zerop (op1)
+ ? boolean_true_node
+ : boolean_false_node);
+ }
+ else
+ {
+ edge_info = allocate_edge_info (true_edge);
+ edge_info->lhs = op0;
+ edge_info->rhs = (integer_zerop (op1)
+ ? boolean_true_node
+ : boolean_false_node);
+
+ edge_info = allocate_edge_info (false_edge);
+ edge_info->lhs = op0;
+ edge_info->rhs = (integer_zerop (op1)
+ ? boolean_false_node
+ : boolean_true_node);
+ }
+ }
+
+ else if (is_gimple_min_invariant (op0)
+ && (TREE_CODE (op1) == SSA_NAME
+ || is_gimple_min_invariant (op1)))
+ {
+ tree inverted = invert_truthvalue (cond);
+ struct edge_info *edge_info;
+
+ edge_info = allocate_edge_info (true_edge);
+ record_conditions (edge_info, cond, inverted);
+
+ if (TREE_CODE (cond) == EQ_EXPR)
+ {
+ edge_info->lhs = op1;
+ edge_info->rhs = op0;
+ }
+
+ edge_info = allocate_edge_info (false_edge);
+ record_conditions (edge_info, inverted, cond);
+
+ if (TREE_CODE (cond) == NE_EXPR)
+ {
+ edge_info->lhs = op1;
+ edge_info->rhs = op0;
+ }
+ }
+
+ else if (TREE_CODE (op0) == SSA_NAME
+ && (is_gimple_min_invariant (op1)
+ || TREE_CODE (op1) == SSA_NAME))
+ {
+ tree inverted = invert_truthvalue (cond);
+ struct edge_info *edge_info;
+
+ edge_info = allocate_edge_info (true_edge);
+ record_conditions (edge_info, cond, inverted);
+
+ if (TREE_CODE (cond) == EQ_EXPR)
+ {
+ edge_info->lhs = op0;
+ edge_info->rhs = op1;
+ }
+
+ edge_info = allocate_edge_info (false_edge);
+ record_conditions (edge_info, inverted, cond);
+
+ if (TREE_CODE (cond) == NE_EXPR)
+ {
+ edge_info->lhs = op0;
+ edge_info->rhs = op1;
+ }
+ }
+ }
+
+ /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
+ }
+ }
+}
+
+/* Propagate information from BB to its outgoing edges.
+
+ This can include equivalency information implied by control statements
+ at the end of BB and const/copy propagation into PHIs in BB's
+ successor blocks. */
static void
-cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
+propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
{
- cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
+
+ record_edge_info (bb);
+ cprop_into_successor_phis (bb, nonzero_vars);
}
/* Search for redundant computations in STMT. If any are found, then
bool insert = true;
tree cached_lhs;
bool retval = false;
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
if (TREE_CODE (stmt) == MODIFY_EXPR)
def = TREE_OPERAND (stmt, 0);
/* Certain expressions on the RHS can be optimized away, but can not
- themselves be entered into the hash tables. */
+ themselves be entered into the hash tables. */
if (ann->makes_aliased_stores
|| ! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
- || NUM_V_MAY_DEFS (v_may_defs) != 0)
+ || NUM_V_MAY_DEFS (v_may_defs) != 0
+ /* Do not record equivalences for increments of ivs. This would create
+ overlapping live ranges for a very questionable gain. */
+ || simple_iv_increment_p (stmt))
insert = false;
/* Check if the expression has been computed before. */
- cached_lhs = lookup_avail_expr (stmt, &bd->avail_exprs, insert);
+ cached_lhs = lookup_avail_expr (stmt, insert);
/* If this is an assignment and the RHS was not in the hash table,
then try to simplify the RHS and lookup the new RHS in the
hash table. */
if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
- cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data,
- stmt,
- ann,
- insert);
+ cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data, stmt, insert);
/* Similarly if this is a COND_EXPR and we did not find its
expression in the hash table, simplify the condition and
try again. */
else if (! cached_lhs && TREE_CODE (stmt) == COND_EXPR)
- cached_lhs = simplify_cond_and_lookup_avail_expr (stmt,
- &bd->avail_exprs,
- ann,
- insert);
+ cached_lhs = simplify_cond_and_lookup_avail_expr (stmt, ann, insert);
/* Similarly for a SWITCH_EXPR. */
else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
- cached_lhs = simplify_switch_and_lookup_avail_expr (stmt,
- &bd->avail_exprs,
- ann,
- insert);
+ cached_lhs = simplify_switch_and_lookup_avail_expr (stmt, insert);
opt_stats.num_exprs_considered++;
CACHED_LHS into *EXPR_P. */
if (cached_lhs
&& (TREE_CODE (cached_lhs) != SSA_NAME
- || may_propagate_copy (cached_lhs, *expr_p)))
+ || may_propagate_copy (*expr_p, cached_lhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
opt_stats.num_re++;
#if defined ENABLE_CHECKING
- if (TREE_CODE (cached_lhs) != SSA_NAME
- && !is_gimple_min_invariant (cached_lhs))
- abort ();
+ gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
+ || is_gimple_min_invariant (cached_lhs));
#endif
if (TREE_CODE (cached_lhs) == ADDR_EXPR
&& is_gimple_min_invariant (cached_lhs)))
retval = true;
- propagate_value (expr_p, cached_lhs);
- ann->modified = 1;
+ propagate_tree_value (expr_p, cached_lhs);
+ mark_stmt_modified (stmt);
}
return retval;
}
static void
record_equivalences_from_stmt (tree stmt,
- varray_type *block_avail_exprs_p,
- varray_type *block_nonzero_vars_p,
int may_optimize_p,
stmt_ann_t ann)
{
if (may_optimize_p
&& (TREE_CODE (rhs) == SSA_NAME
|| is_gimple_min_invariant (rhs)))
- set_value_for (lhs, rhs, const_and_copies);
+ SSA_NAME_VALUE (lhs) = rhs;
/* alloca never returns zero and the address of a non-weak symbol
is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
|| (TREE_CODE (rhs) == ADDR_EXPR
&& DECL_P (TREE_OPERAND (rhs, 0))
&& ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
- record_var_is_nonzero (lhs, block_nonzero_vars_p);
+ record_var_is_nonzero (lhs);
/* IOR of any value with a nonzero value will result in a nonzero
value. Even if we do not know the exact result recording that
the result is nonzero is worth the effort. */
if (TREE_CODE (rhs) == BIT_IOR_EXPR
&& integer_nonzerop (TREE_OPERAND (rhs, 1)))
- record_var_is_nonzero (lhs, block_nonzero_vars_p);
+ record_var_is_nonzero (lhs);
}
/* Look at both sides for pointer dereferences. If we find one, then
t = TREE_OPERAND (t, 0);
/* Now see if this is a pointer dereference. */
- if (TREE_CODE (t) == INDIRECT_REF)
+ if (INDIRECT_REF_P (t))
{
tree op = TREE_OPERAND (t, 0);
{
tree def = SSA_NAME_DEF_STMT (op);
- record_var_is_nonzero (op, block_nonzero_vars_p);
+ record_var_is_nonzero (op);
/* And walk up the USE-DEF chains noting other SSA_NAMEs
which are known to have a nonzero value. */
{
tree rhs = TREE_OPERAND (stmt, 1);
tree new;
- size_t j;
/* FIXME: If the LHS of the assignment is a bitfield and the RHS
is a constant, we need to adjust the constant to fit into the
if (rhs)
{
- v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
- v_must_def_optype v_must_defs = V_MUST_DEF_OPS (ann);
-
/* Build a new statement with the RHS and LHS exchanged. */
new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
- /* Get an annotation and set up the real operands. */
- get_stmt_ann (new);
- get_stmt_operands (new);
-
- /* Clear out the virtual operands on the new statement, we are
- going to set them explicitly below. */
- remove_vuses (new);
- remove_v_may_defs (new);
- remove_v_must_defs (new);
-
- start_ssa_stmt_operands (new);
- /* For each VDEF on the original statement, we want to create a
- VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new
- statement. */
- for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
- {
- tree op = V_MAY_DEF_RESULT (v_may_defs, j);
- add_vuse (op, new);
- }
-
- for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
+ create_ssa_artficial_load_stmt (&(ann->operands), new);
+
+ /* Finally enter the statement into the available expression
+ table. */
+ lookup_avail_expr (new, true);
+ }
+ }
+}
+
+/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
+ CONST_AND_COPIES. */
+
+static bool
+cprop_operand (tree stmt, use_operand_p op_p)
+{
+ bool may_have_exposed_new_symbols = false;
+ tree val;
+ tree op = USE_FROM_PTR (op_p);
+
+ /* If the operand has a known constant value or it is known to be a
+ copy of some other variable, use the value or copy stored in
+ CONST_AND_COPIES. */
+ val = SSA_NAME_VALUE (op);
+ if (val && TREE_CODE (val) != VALUE_HANDLE)
+ {
+ tree op_type, val_type;
+
+ /* Do not change the base variable in the virtual operand
+ tables. That would make it impossible to reconstruct
+ the renamed virtual operand if we later modify this
+ statement. Also only allow the new value to be an SSA_NAME
+ for propagation into virtual operands. */
+ if (!is_gimple_reg (op)
+ && (get_virtual_var (val) != get_virtual_var (op)
+ || TREE_CODE (val) != SSA_NAME))
+ return false;
+
+ /* Do not replace hard register operands in asm statements. */
+ if (TREE_CODE (stmt) == ASM_EXPR
+ && !may_propagate_copy_into_asm (op))
+ return false;
+
+ /* Get the toplevel type of each operand. */
+ op_type = TREE_TYPE (op);
+ val_type = TREE_TYPE (val);
+
+ /* While both types are pointers, get the type of the object
+ pointed to. */
+ while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
+ {
+ op_type = TREE_TYPE (op_type);
+ val_type = TREE_TYPE (val_type);
+ }
+
+ /* Make sure underlying types match before propagating a constant by
+ converting the constant to the proper type. Note that convert may
+ return a non-gimple expression, in which case we ignore this
+ propagation opportunity. */
+ if (TREE_CODE (val) != SSA_NAME)
+ {
+ if (!lang_hooks.types_compatible_p (op_type, val_type))
{
- tree op = V_MUST_DEF_OP (v_must_defs, j);
- add_vuse (op, new);
+ val = fold_convert (TREE_TYPE (op), val);
+ if (!is_gimple_min_invariant (val))
+ return false;
}
+ }
- finalize_ssa_stmt_operands (new);
+ /* Certain operands are not allowed to be copy propagated due
+ to their interaction with exception handling and some GCC
+ extensions. */
+ else if (!may_propagate_copy (op, val))
+ return false;
+
+ /* Do not propagate copies if the propagated value is at a deeper loop
+ depth than the propagatee. Otherwise, this may move loop variant
+ variables outside of their loops and prevent coalescing
+ opportunities. If the value was loop invariant, it will be hoisted
+ by LICM and exposed for copy propagation. */
+ if (loop_depth_of_name (val) > loop_depth_of_name (op))
+ return false;
- /* Finally enter the statement into the available expression
- table. */
- lookup_avail_expr (new, block_avail_exprs_p, true);
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Replaced '");
+ print_generic_expr (dump_file, op, dump_flags);
+ fprintf (dump_file, "' with %s '",
+ (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
+ print_generic_expr (dump_file, val, dump_flags);
+ fprintf (dump_file, "'\n");
}
+
+ /* If VAL is an ADDR_EXPR or a constant of pointer type, note
+ that we may have exposed a new symbol for SSA renaming. */
+ if (TREE_CODE (val) == ADDR_EXPR
+ || (POINTER_TYPE_P (TREE_TYPE (op))
+ && is_gimple_min_invariant (val)))
+ may_have_exposed_new_symbols = true;
+
+ propagate_value (op_p, val);
+
+ /* And note that we modified this statement. This is now
+ safe, even if we changed virtual operands since we will
+ rescan the statement and rewrite its operands again. */
+ mark_stmt_modified (stmt);
+ }
+ return may_have_exposed_new_symbols;
+}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+ known value for that SSA_NAME (or NULL if no value is known).
+
+ Propagate values from CONST_AND_COPIES into the uses, vuses and
+ v_may_def_ops of STMT. */
+
+static bool
+cprop_into_stmt (tree stmt)
+{
+ bool may_have_exposed_new_symbols = false;
+ use_operand_p op_p;
+ ssa_op_iter iter;
+ tree rhs;
+
+ FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
+ {
+ if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+ may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
+ }
+
+ if (may_have_exposed_new_symbols)
+ {
+ rhs = get_rhs (stmt);
+ if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
+ recompute_tree_invarant_for_addr_expr (rhs);
}
+
+ return may_have_exposed_new_symbols;
}
+
/* Optimize the statement pointed by iterator SI.
We try to perform some simplistic global redundancy elimination and
the variable in the LHS in the CONST_AND_COPIES table. */
static void
-optimize_stmt (struct dom_walk_data *walk_data,
- basic_block bb ATTRIBUTE_UNUSED,
+optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
block_stmt_iterator si)
{
stmt_ann_t ann;
tree stmt;
bool may_optimize_p;
bool may_have_exposed_new_symbols = false;
- struct dom_walk_block_data *bd
- = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
stmt = bsi_stmt (si);
- get_stmt_operands (stmt);
+ update_stmt_if_modified (stmt);
ann = stmt_ann (stmt);
opt_stats.num_stmts++;
may_have_exposed_new_symbols = false;
}
/* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
- may_have_exposed_new_symbols = cprop_into_stmt (stmt, const_and_copies);
+ may_have_exposed_new_symbols = cprop_into_stmt (stmt);
/* If the statement has been modified with constant replacements,
fold its RHS before checking for redundant computations. */
/* Record any additional equivalences created by this statement. */
if (TREE_CODE (stmt) == MODIFY_EXPR)
record_equivalences_from_stmt (stmt,
- &bd->avail_exprs,
- &bd->nonzero_vars,
may_optimize_p,
ann);
- register_definitions_for_stmt (ann, &bd->block_defs);
+ register_definitions_for_stmt (stmt);
/* If STMT is a COND_EXPR and it was modified, then we may know
where it goes. If that is the case, then mark the CFG as altered.
else if (TREE_CODE (stmt) == SWITCH_EXPR)
val = SWITCH_COND (stmt);
- if (val && TREE_CODE (val) == INTEGER_CST
- && find_taken_edge (bb_for_stmt (stmt), val))
+ if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
cfg_altered = true;
+
+ /* If we simplified a statement in such a way as to be shown that it
+ cannot trap, update the eh information and the cfg to match. */
+ if (maybe_clean_eh_stmt (stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Flagged to clear EH edges.\n");
+ }
}
-
+
if (may_have_exposed_new_symbols)
- {
- if (! bd->stmts_to_rescan)
- VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
- VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
- }
+ VEC_safe_push (tree_on_heap, stmts_to_rescan, bsi_stmt (si));
}
/* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
hash table to account for the changes made to STMT. */
static tree
-update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
- varray_type *block_avail_exprs_p,
- stmt_ann_t ann,
- bool insert)
+update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs, bool insert)
{
tree cached_lhs = NULL;
TREE_OPERAND (stmt, 1) = new_rhs;
/* Now lookup the updated statement in the hash table. */
- cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p, insert);
+ cached_lhs = lookup_avail_expr (stmt, insert);
/* We have now called lookup_avail_expr twice with two different
versions of this same statement, once in optimize_stmt, once here.
We know the call in optimize_stmt did not find an existing entry
in the hash table, so a new entry was created. At the same time
- this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
+ this statement was pushed onto the AVAIL_EXPRS_STACK vector.
If this call failed to find an existing entry on the hash table,
then the new version of this statement was entered into the
for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
If this call succeeded, we still have one copy of this statement
- on the BLOCK_AVAIL_EXPRs varray.
+ on the BLOCK_AVAIL_EXPRs vector.
For both cases, we need to pop the most recent entry off the
- BLOCK_AVAIL_EXPRs varray. For the case where we never found this
+ BLOCK_AVAIL_EXPRs vector. For the case where we never found this
statement in the hash tables, that will leave precisely one
copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
we found a copy of this statement in the second hash table lookup
we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
if (insert)
- VARRAY_POP (*block_avail_exprs_p);
+ VEC_pop (tree_on_heap, avail_exprs_stack);
/* And make sure we record the fact that we modified this
statement. */
- ann->modified = 1;
+ mark_stmt_modified (stmt);
return cached_lhs;
}
aliased references. */
static tree
-lookup_avail_expr (tree stmt, varray_type *block_avail_exprs_p, bool insert)
+lookup_avail_expr (tree stmt, bool insert)
{
void **slot;
tree lhs;
tree temp;
- struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
+ struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
if (*slot == NULL)
{
*slot = (void *) element;
- if (! *block_avail_exprs_p)
- VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
- VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt ? stmt : element->rhs);
+ VEC_safe_push (tree_on_heap, avail_exprs_stack,
+ stmt ? stmt : element->rhs);
return NULL_TREE;
}
use the value from the const_and_copies table. */
if (TREE_CODE (lhs) == SSA_NAME)
{
- temp = get_value_for (lhs, const_and_copies);
- if (temp)
+ temp = SSA_NAME_VALUE (lhs);
+ if (temp && TREE_CODE (temp) != VALUE_HANDLE)
lhs = temp;
}
tree op1 = TREE_OPERAND (cond, 1);
tree high, low, type;
int inverted;
-
+
+ type = TREE_TYPE (op1);
+
/* Experiments have shown that it's rarely, if ever useful to
record ranges for enumerations. Presumably this is due to
the fact that they're rarely used directly. They are typically
cast into an integer type and used that way. */
- if (TREE_CODE (TREE_TYPE (op1)) != INTEGER_TYPE)
+ if (TREE_CODE (type) != INTEGER_TYPE
+ /* We don't know how to deal with types with variable bounds. */
+ || TREE_CODE (TYPE_MIN_VALUE (type)) != INTEGER_CST
+ || TREE_CODE (TYPE_MAX_VALUE (type)) != INTEGER_CST)
return 0;
- type = TREE_TYPE (op1);
-
switch (TREE_CODE (cond))
{
case EQ_EXPR:
break;
case GT_EXPR:
- low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
high = TYPE_MAX_VALUE (type);
+ if (!tree_int_cst_lt (op1, high))
+ return 0;
+ low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
inverted = 0;
break;
break;
case LT_EXPR:
- high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
low = TYPE_MIN_VALUE (type);
+ if (!tree_int_cst_lt (low, op1))
+ return 0;
+ high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
inverted = 0;
break;
/* Record a range created by COND for basic block BB. */
static void
-record_range (tree cond, basic_block bb, varray_type *vrp_variables_p)
+record_range (tree cond, basic_block bb)
{
- /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
- range optimizations and significantly complicate the implementation. */
- if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<'
- && TREE_CODE (cond) != NE_EXPR
+ enum tree_code code = TREE_CODE (cond);
+
+ /* We explicitly ignore NE_EXPRs and all the unordered comparisons.
+ They rarely allow for meaningful range optimizations and significantly
+ complicate the implementation. */
+ if ((code == LT_EXPR || code == LE_EXPR || code == GT_EXPR
+ || code == GE_EXPR || code == EQ_EXPR)
&& TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
{
- struct vrp_element *element = ggc_alloc (sizeof (struct vrp_element));
- int ssa_version = SSA_NAME_VERSION (TREE_OPERAND (cond, 0));
+ struct vrp_hash_elt *vrp_hash_elt;
+ struct vrp_element *element;
+ varray_type *vrp_records_p;
+ void **slot;
+
+
+ vrp_hash_elt = xmalloc (sizeof (struct vrp_hash_elt));
+ vrp_hash_elt->var = TREE_OPERAND (cond, 0);
+ vrp_hash_elt->records = NULL;
+ slot = htab_find_slot (vrp_data, vrp_hash_elt, INSERT);
- varray_type *vrp_records_p
- = (varray_type *)&VARRAY_GENERIC_PTR (vrp_data, ssa_version);
+ if (*slot == NULL)
+ *slot = (void *) vrp_hash_elt;
+ else
+ free (vrp_hash_elt);
+
+ vrp_hash_elt = (struct vrp_hash_elt *) *slot;
+ vrp_records_p = &vrp_hash_elt->records;
+ element = ggc_alloc (sizeof (struct vrp_element));
element->low = NULL;
element->high = NULL;
element->cond = cond;
element->bb = bb;
if (*vrp_records_p == NULL)
- {
- VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
- VARRAY_GENERIC_PTR (vrp_data, ssa_version) = *vrp_records_p;
- }
+ VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
- if (! *vrp_variables_p)
- VARRAY_TREE_INIT (*vrp_variables_p, 2, "vrp_variables");
- VARRAY_PUSH_TREE (*vrp_variables_p, TREE_OPERAND (cond, 0));
+ VEC_safe_push (tree_on_heap, vrp_variables_stack, TREE_OPERAND (cond, 0));
}
}
-/* Given a conditional statement IF_STMT, return the assignment 'X = Y'
- known to be true depending on which arm of IF_STMT is taken.
+/* Hashing and equality functions for VRP_DATA.
- Not all conditional statements will result in a useful assignment.
- Return NULL_TREE in that case.
+ Since this hash table is addressed by SSA_NAMEs, we can hash on
+ their version number and equality can be determined with a
+ pointer comparison. */
- Also enter into the available expression table statements of
- the form:
-
- TRUE ARM FALSE ARM
- 1 = cond 1 = cond'
- 0 = cond' 0 = cond
-
- This allows us to lookup the condition in a dominated block and
- get back a constant indicating if the condition is true. */
-
-static struct eq_expr_value
-get_eq_expr_value (tree if_stmt,
- int true_arm,
- varray_type *block_avail_exprs_p,
- basic_block bb,
- varray_type *vrp_variables_p)
+static hashval_t
+vrp_hash (const void *p)
{
- tree cond;
- struct eq_expr_value retval;
-
- cond = COND_EXPR_COND (if_stmt);
- retval.src = NULL;
- retval.dst = NULL;
-
- /* If the conditional is a single variable 'X', return 'X = 1' for
- the true arm and 'X = 0' on the false arm. */
- if (TREE_CODE (cond) == SSA_NAME)
- {
- retval.dst = cond;
- retval.src = (true_arm ? integer_one_node : integer_zero_node);
- return retval;
- }
-
- /* If we have a comparison expression, then record its result into
- the available expression table. */
- if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
- {
- tree op0 = TREE_OPERAND (cond, 0);
- tree op1 = TREE_OPERAND (cond, 1);
-
- /* Special case comparing booleans against a constant as we know
- the value of OP0 on both arms of the branch. ie, we can record
- an equivalence for OP0 rather than COND. */
- if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
- && TREE_CODE (op0) == SSA_NAME
- && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
- && is_gimple_min_invariant (op1))
- {
- if ((TREE_CODE (cond) == EQ_EXPR && true_arm)
- || (TREE_CODE (cond) == NE_EXPR && ! true_arm))
- {
- retval.src = op1;
- }
- else
- {
- if (integer_zerop (op1))
- retval.src = boolean_true_node;
- else
- retval.src = boolean_false_node;
- }
- retval.dst = op0;
- return retval;
- }
-
- if (TREE_CODE (op0) == SSA_NAME
- && (is_gimple_min_invariant (op1) || TREE_CODE (op1) == SSA_NAME))
- {
- tree inverted = invert_truthvalue (cond);
-
- /* When we find an available expression in the hash table, we replace
- the expression with the LHS of the statement in the hash table.
-
- So, we want to build statements such as "1 = <condition>" on the
- true arm and "0 = <condition>" on the false arm. That way if we
- find the expression in the table, we will replace it with its
- known constant value. Also insert inversions of the result and
- condition into the hash table. */
- if (true_arm)
- {
- record_cond (cond, boolean_true_node, block_avail_exprs_p);
- record_cond (inverted, boolean_false_node, block_avail_exprs_p);
+ tree var = ((struct vrp_hash_elt *)p)->var;
- if (TREE_CONSTANT (op1))
- record_range (cond, bb, vrp_variables_p);
-
- /* If the conditional is of the form 'X == Y', return 'X = Y'
- for the true arm. */
- if (TREE_CODE (cond) == EQ_EXPR)
- {
- retval.dst = op0;
- retval.src = op1;
- return retval;
- }
- }
- else
- {
-
- record_cond (inverted, boolean_true_node, block_avail_exprs_p);
- record_cond (cond, boolean_false_node, block_avail_exprs_p);
-
- if (TREE_CONSTANT (op1))
- record_range (inverted, bb, vrp_variables_p);
+ return SSA_NAME_VERSION (var);
+}
- /* If the conditional is of the form 'X != Y', return 'X = Y'
- for the false arm. */
- if (TREE_CODE (cond) == NE_EXPR)
- {
- retval.dst = op0;
- retval.src = op1;
- return retval;
- }
- }
- }
- }
+static int
+vrp_eq (const void *p1, const void *p2)
+{
+ tree var1 = ((struct vrp_hash_elt *)p1)->var;
+ tree var2 = ((struct vrp_hash_elt *)p2)->var;
- return retval;
+ return var1 == var2;
}
/* Hashing and equality functions for AVAIL_EXPRS. The table stores
return val;
}
+static hashval_t
+real_avail_expr_hash (const void *p)
+{
+ return ((const struct expr_hash_elt *)p)->hash;
+}
static int
avail_expr_eq (const void *p1, const void *p2)
if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
return false;
-#ifdef ENABLE_CHECKING
- if (((struct expr_hash_elt *)p1)->hash
- != ((struct expr_hash_elt *)p2)->hash)
- abort ();
-#endif
+ gcc_assert (((struct expr_hash_elt *)p1)->hash
+ == ((struct expr_hash_elt *)p2)->hash);
return true;
}
return false;
}
-/* Given STMT and a pointer to the block local defintions BLOCK_DEFS_P,
+/* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
register register all objects set by this statement into BLOCK_DEFS_P
and CURRDEFS. */
static void
-register_definitions_for_stmt (stmt_ann_t ann, varray_type *block_defs_p)
+register_definitions_for_stmt (tree stmt)
{
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
- unsigned int i;
+ tree def;
+ ssa_op_iter iter;
- defs = DEF_OPS (ann);
- for (i = 0; i < NUM_DEFS (defs); i++)
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
{
- tree def = DEF_OP (defs, i);
-
- /* FIXME: We shouldn't be registering new defs if the variable
- doesn't need to be renamed. */
- register_new_def (def, block_defs_p);
- }
- /* Register new virtual definitions made by the statement. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- {
- /* FIXME: We shouldn't be registering new defs if the variable
- doesn't need to be renamed. */
- register_new_def (V_MAY_DEF_RESULT (v_may_defs, i), block_defs_p);
- }
-
- /* Register new virtual mustdefs made by the statement. */
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
- {
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
- register_new_def (V_MUST_DEF_OP (v_must_defs, i), block_defs_p);
+ register_new_def (def, &block_defs_stack);
}
}
OSDN Git Service
