/* 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.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "tm_p.h"
#include "ggc.h"
#include "basic-block.h"
+#include "cfgloop.h"
#include "output.h"
-#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.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
(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 varray_type 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. */
-varray_type block_defs_stack;
+static VEC(tree,heap) *avail_exprs_stack;
/* Stack of statements we need to rescan during finalization for newly
exposed variables.
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. */
-varray_type stmts_to_rescan;
+static VEC(tree,heap) *stmts_to_rescan;
/* Structure for entries in the expression hash table.
/* The expression (rhs) we want to record. */
tree rhs;
- /* The annotation if this element corresponds to a statement. */
- stmt_ann_t ann;
+ /* The stmt pointer if this element corresponds to a statement. */
+ tree stmt;
/* The hash value for RHS/ann. */
hashval_t hash;
A NULL entry is used to mark the end of pairs which need to be
restored during finalization of this block. */
-static varray_type const_and_copies_stack;
+static VEC(tree,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;
+/* Bitmap of blocks that are scheduled to be threaded through. This
+ is used to communicate with thread_through_blocks. */
+static bitmap threaded_blocks;
+
/* 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 varray_type nonzero_vars_stack;
+static VEC(tree,heap) *nonzero_vars_stack;
/* Track whether or not we have changed the control flow graph. */
static bool cfg_altered;
long num_stmts;
long num_exprs_considered;
long num_re;
+ long num_const_prop;
+ long num_copy_prop;
+ long num_iterations;
};
static struct opt_stats_d opt_stats;
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
with useful information is very low. */
static htab_t vrp_data;
+typedef struct vrp_element *vrp_element_p;
+
+DEF_VEC_P(vrp_element_p);
+DEF_VEC_ALLOC_P(vrp_element_p,heap);
+
/* 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;
+ VEC(vrp_element_p,heap) *records;
};
/* 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. */
-/* Stack of SSA_NAMEs which had their values constrainted by operations
+/* 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.
A NULL entry marks the end of the SSA_NAMEs associated with this block. */
-static varray_type vrp_variables_stack;
+static VEC(tree,heap) *vrp_variables_stack;
struct eq_expr_value
{
basic_block bb,
block_stmt_iterator);
static tree lookup_avail_expr (tree, bool);
-static struct eq_expr_value get_eq_expr_value (tree, int, basic_block);
static hashval_t vrp_hash (const void *);
static int vrp_eq (const void *, const void *);
static hashval_t 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);
-static void record_dominating_conditions (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, int);
+static tree simplify_rhs_and_lookup_avail_expr (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);
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 bool eliminate_redundant_computations (struct dom_walk_data *,
- tree, stmt_ann_t);
+static void record_equivalences_from_phis (basic_block);
+static void record_equivalences_from_incoming_edge (basic_block);
+static bool eliminate_redundant_computations (tree, 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 (struct dom_walk_data *, basic_block);
-static void cprop_into_phis (struct dom_walk_data *, basic_block);
+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. */
static tree
return t;
}
+/* Allocate an EDGE_INFO for edge E and attach it to E.
+ Return the new EDGE_INFO structure. */
+
+static struct edge_info *
+allocate_edge_info (edge e)
+{
+ struct edge_info *edge_info;
+
+ edge_info = xcalloc (1, sizeof (struct edge_info));
+
+ e->aux = edge_info;
+ return edge_info;
+}
+
+/* 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
+free_all_edge_infos (void)
+{
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ struct edge_info *edge_info = e->aux;
+
+ if (edge_info)
+ {
+ e->aux = edge_info->redirection_target;
+ if (edge_info->cond_equivalences)
+ free (edge_info->cond_equivalences);
+ free (edge_info);
+ }
+ }
+ }
+}
+
+/* Free an instance of vrp_hash_elt. */
+
+static void
+vrp_free (void *data)
+{
+ struct vrp_hash_elt *elt = data;
+ struct VEC(vrp_element_p,heap) **vrp_elt = &elt->records;
+
+ VEC_free (vrp_element_p, heap, *vrp_elt);
+ free (elt);
+}
+
/* Jump threading, redundancy elimination and const/copy propagation.
This pass may expose new symbols that need to be renamed into SSA. For
{
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, real_avail_expr_hash, avail_expr_eq, free);
- vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq, free);
- VARRAY_TREE_INIT (avail_exprs_stack, 20, "Available expression stack");
- VARRAY_TREE_INIT (block_defs_stack, 20, "Block DEFS stack");
- VARRAY_TREE_INIT (const_and_copies_stack, 20, "Block const_and_copies stack");
- VARRAY_TREE_INIT (nonzero_vars_stack, 20, "Block nonzero_vars stack");
- VARRAY_TREE_INIT (vrp_variables_stack, 20, "Block vrp_variables stack");
- VARRAY_TREE_INIT (stmts_to_rescan, 20, "Statements to rescan");
- nonzero_vars = BITMAP_XMALLOC ();
- need_eh_cleanup = BITMAP_XMALLOC ();
+ vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq,
+ vrp_free);
+ avail_exprs_stack = VEC_alloc (tree, heap, 20);
+ const_and_copies_stack = VEC_alloc (tree, heap, 20);
+ nonzero_vars_stack = VEC_alloc (tree, heap, 20);
+ vrp_variables_stack = VEC_alloc (tree, heap, 20);
+ stmts_to_rescan = VEC_alloc (tree, heap, 20);
+ nonzero_vars = BITMAP_ALLOC (NULL);
+ threaded_blocks = 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.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;
structure. */
walk_data.global_data = NULL;
walk_data.block_local_data_size = 0;
+ walk_data.interesting_blocks = NULL;
/* Now initialize the dominator walker. */
init_walk_dominator_tree (&walk_data);
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 ();
+ calculate_dominance_info (CDI_DOMINATORS);
+
/* 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);
+ {
+ 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));
+ }
+ }
+ }
+
/* 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_first_set_bit (vars_to_rename) >= 0)
- {
- rewrite_into_ssa (false);
- bitmap_clear (vars_to_rename);
- }
+ update_ssa (TODO_update_ssa);
+
+ free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
- cfg_altered = thread_through_all_blocks ();
+ cfg_altered |= thread_through_all_blocks (threaded_blocks);
/* Removal of statements may make some EH edges dead. Purge
such edges from the CFG as needed. */
- if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
+ if (!bitmap_empty_p (need_eh_cleanup))
{
cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
bitmap_zero (need_eh_cleanup);
}
- free_dominance_info (CDI_DOMINATORS);
+ 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);
- rewrite_ssa_into_ssa ();
+ update_ssa (TODO_update_ssa);
/* Reinitialize the various tables. */
bitmap_clear (nonzero_vars);
+ bitmap_clear (threaded_blocks);
htab_empty (avail_exprs);
htab_empty (vrp_data);
- for (i = 0; i < num_referenced_vars; i++)
- var_ann (referenced_var (i))->current_def = NULL;
+ /* 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
+ update_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;
+ }
+
+ opt_stats.num_iterations++;
}
- while (cfg_altered);
+ while (optimize > 1 && cfg_altered);
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_STATS))
fini_walk_dominator_tree (&walk_data);
/* Free nonzero_vars. */
- BITMAP_XFREE (nonzero_vars);
- BITMAP_XFREE (need_eh_cleanup);
-
- /* Finally, remove everything except invariants in SSA_NAME_VALUE.
-
- 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;
- }
+ BITMAP_FREE (nonzero_vars);
+ BITMAP_FREE (threaded_blocks);
+ BITMAP_FREE (need_eh_cleanup);
+
+ VEC_free (tree, heap, avail_exprs_stack);
+ VEC_free (tree, heap, const_and_copies_stack);
+ VEC_free (tree, heap, nonzero_vars_stack);
+ VEC_free (tree, heap, vrp_variables_stack);
+ VEC_free (tree, heap, stmts_to_rescan);
}
static bool
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_rename_vars
+ TODO_dump_func
+ | TODO_update_ssa
| TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};
-/* We are exiting BB, see if the target block begins with a conditional
- jump which has a known value when reached via BB. */
+/* We are exiting E->src, see if E->dest ends with a conditional
+ jump which has a known value when reached via E.
+
+ Special care is necessary if E is a back edge in the CFG as we
+ will have already recorded equivalences for E->dest into our
+ various tables, including the result of the conditional at
+ the end of E->dest. Threading opportunities are severely
+ limited in that case to avoid short-circuiting the loop
+ incorrectly.
+
+ Note it is quite common for the first block inside a loop to
+ end with a conditional which is either always true or always
+ false when reached via the loop backedge. Thus we do not want
+ to blindly disable threading across a loop backedge. */
static void
thread_across_edge (struct dom_walk_data *walk_data, edge e)
tree stmt = NULL;
tree phi;
- /* Each PHI creates a temporary equivalence, record them. */
+ /* If E->dest does not end with a conditional, then there is
+ nothing to do. */
+ bsi = bsi_last (e->dest);
+ if (bsi_end_p (bsi)
+ || ! bsi_stmt (bsi)
+ || (TREE_CODE (bsi_stmt (bsi)) != COND_EXPR
+ && TREE_CODE (bsi_stmt (bsi)) != GOTO_EXPR
+ && TREE_CODE (bsi_stmt (bsi)) != SWITCH_EXPR))
+ return;
+
+ /* The basic idea here is to use whatever knowledge we have
+ from our dominator walk to simplify statements in E->dest,
+ with the ultimate goal being to simplify the conditional
+ at the end of E->dest.
+
+ Note that we must undo any changes we make to the underlying
+ statements as the simplifications we are making are control
+ flow sensitive (ie, the simplifications are valid when we
+ traverse E, but may not be valid on other paths to E->dest. */
+
+ /* Each PHI creates a temporary equivalence, record them. Again
+ these are context sensitive equivalences and will be removed
+ by our caller. */
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
tree dst = PHI_RESULT (phi);
+
+ /* If the desired argument is not the same as this PHI's result
+ and it is set by a PHI in E->dest, then we can not thread
+ through E->dest. */
+ 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);
}
+ /* Try to simplify each statement in E->dest, ultimately leading to
+ a simplification of the COND_EXPR at the end of E->dest.
+
+ We might consider marking just those statements which ultimately
+ feed the COND_EXPR. It's not clear if the overhead of bookkeeping
+ would be recovered by trying to simplify fewer statements.
+
+ If we are able to simplify a statement into the form
+ SSA_NAME = (SSA_NAME | gimple invariant), then we can record
+ a context sensitive equivalency which may help us simplify
+ later statements in E->dest.
+
+ Failure to simplify into the form above merely means that the
+ statement provides no equivalences to help simplify later
+ statements. This does not prevent threading through E->dest. */
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
{
- tree lhs, cached_lhs;
+ tree cached_lhs;
stmt = bsi_stmt (bsi);
if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
continue;
+ /* Safely handle threading across loop backedges. This is
+ over conservative, but still allows us to capture the
+ majority of the cases where we can thread across a loop
+ backedge. */
+ if ((e->flags & EDGE_DFS_BACK) != 0
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ return;
+
+ /* If the statement has volatile operands, then we assume we
+ can not thread through this block. This is overly
+ conservative in some ways. */
+ if (TREE_CODE (stmt) == ASM_EXPR && ASM_VOLATILE_P (stmt))
+ return;
+
/* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
- value, then stop our search here. Ideally when we stop a
- search we stop on a COND_EXPR or SWITCH_EXPR. */
+ value, then do not try to simplify this statement as it will
+ not simplify in any way that is helpful for jump threading. */
if (TREE_CODE (stmt) != MODIFY_EXPR
|| TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
- break;
+ continue;
/* At this point we have a statement which assigns an RHS to an
- SSA_VAR on the LHS. We want to prove that the RHS is already
- available and that its value is held in the current definition
- of the LHS -- meaning that this assignment is a NOP when
- reached via edge E. */
+ SSA_VAR on the LHS. We want to try and simplify this statement
+ to expose more context sensitive equivalences which in turn may
+ allow us to simplify the condition at the end of the loop. */
if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
cached_lhs = TREE_OPERAND (stmt, 1);
else
- cached_lhs = lookup_avail_expr (stmt, false);
-
- lhs = TREE_OPERAND (stmt, 0);
-
- /* This can happen if we thread around to the start of a loop. */
- if (lhs == cached_lhs)
- break;
-
- /* If we did not find RHS in the hash table, then try again after
- temporarily const/copy propagating the operands. */
- if (!cached_lhs)
{
/* Copy the operands. */
- 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));
- unsigned int i;
-
- /* Make a copy of the uses into USES_COPY, then cprop into
- the use operands. */
- for (i = 0; i < NUM_USES (uses); i++)
- {
- tree tmp = NULL;
+ tree *copy;
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ unsigned int num, i = 0;
- uses_copy[i] = USE_OP (uses, i);
- if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
- tmp = SSA_NAME_VALUE (USE_OP (uses, i));
- if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
- SET_USE_OP (uses, i, tmp);
- }
+ num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
+ copy = xcalloc (num, sizeof (tree));
- /* Similarly for virtual uses. */
- for (i = 0; i < NUM_VUSES (vuses); i++)
+ /* Make a copy of the uses & vuses into USES_COPY, then cprop into
+ the operands. */
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
{
tree tmp = NULL;
+ tree use = USE_FROM_PTR (use_p);
- vuses_copy[i] = VUSE_OP (vuses, i);
- if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
- tmp = SSA_NAME_VALUE (VUSE_OP (vuses, i));
+ copy[i++] = use;
+ if (TREE_CODE (use) == SSA_NAME)
+ tmp = SSA_NAME_VALUE (use);
if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
- SET_VUSE_OP (vuses, i, tmp);
+ SET_USE (use_p, tmp);
}
- /* Try to lookup the new expression. */
- cached_lhs = lookup_avail_expr (stmt, false);
+ /* Try to fold/lookup the new expression. Inserting the
+ expression into the hash table is unlikely to help
+ simplify anything later, so just query the hashtable. */
+ cached_lhs = fold (TREE_OPERAND (stmt, 1));
+ if (TREE_CODE (cached_lhs) != SSA_NAME
+ && !is_gimple_min_invariant (cached_lhs))
+ cached_lhs = lookup_avail_expr (stmt, false);
- /* Restore the statement's original uses/defs. */
- for (i = 0; i < NUM_USES (uses); i++)
- SET_USE_OP (uses, i, uses_copy[i]);
-
- for (i = 0; i < NUM_VUSES (vuses); i++)
- SET_VUSE_OP (vuses, i, vuses_copy[i]);
- free (uses_copy);
- free (vuses_copy);
+ /* Restore the statement's original uses/defs. */
+ i = 0;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
+ SET_USE (use_p, copy[i++]);
- /* If we still did not find the expression in the hash table,
- then we can not ignore this statement. */
- if (! cached_lhs)
- break;
+ free (copy);
}
- /* If the expression in the hash table was not assigned to an
- SSA_NAME, then we can not ignore this statement. */
- if (TREE_CODE (cached_lhs) != SSA_NAME)
- break;
-
- /* If we have different underlying variables, then we can not
- ignore this statement. */
- if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
- break;
-
- /* If CACHED_LHS does not represent the current value of the undering
- variable in CACHED_LHS/LHS, then we can not ignore this statement. */
- if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
- break;
-
- /* If we got here, then we can ignore this statement and continue
- walking through the statements in the block looking for a threadable
- COND_EXPR.
-
- 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);
- register_new_def (lhs, &block_defs_stack);
+ /* Record the context sensitive equivalence if we were able
+ to simplify this statement. */
+ if (cached_lhs
+ && (TREE_CODE (cached_lhs) == SSA_NAME
+ || is_gimple_min_invariant (cached_lhs)))
+ record_const_or_copy (TREE_OPERAND (stmt, 0), cached_lhs);
}
- /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
- arm will be taken. */
+ /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
+ will be taken. */
if (stmt
&& (TREE_CODE (stmt) == COND_EXPR
+ || TREE_CODE (stmt) == GOTO_EXPR
|| TREE_CODE (stmt) == SWITCH_EXPR))
{
tree cond, cached_lhs;
- edge e1;
- edge_iterator ei;
-
- /* 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_EACH_EDGE (e1, ei, e->dest->preds)
- 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);
}
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, false);
- if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
{
- cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
- NULL,
- 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
cached_lhs = cond;
cached_lhs = SSA_NAME_VALUE (cached_lhs);
if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
- cached_lhs = 0;
+ cached_lhs = NULL;
}
else
cached_lhs = lookup_avail_expr (stmt, false);
bypass the conditional at our original destination. */
if (dest)
{
- update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
- e->count, taken_edge);
- e->aux = taken_edge;
- bb_ann (e->dest)->incoming_edge_threaded = true;
+ struct edge_info *edge_info;
+
+ if (e->aux)
+ edge_info = e->aux;
+ else
+ edge_info = allocate_edge_info (e);
+ edge_info->redirection_target = taken_edge;
+ bitmap_set_bit (threaded_blocks, e->dest->index);
}
}
}
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);
/* Push a marker on the stacks of local information so that we know how
far to unwind when we finalize this block. */
- VARRAY_PUSH_TREE (avail_exprs_stack, NULL_TREE);
- VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
- VARRAY_PUSH_TREE (const_and_copies_stack, NULL_TREE);
- VARRAY_PUSH_TREE (nonzero_vars_stack, NULL_TREE);
- VARRAY_PUSH_TREE (vrp_variables_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, nonzero_vars_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, vrp_variables_stack, NULL_TREE);
- record_equivalences_from_incoming_edge (walk_data, bb);
+ 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),
- initialize the hash table element pointed by by ELEMENT. */
+ initialize the hash table element pointed to by ELEMENT. */
static void
initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
we want to record the expression the statement evaluates. */
if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
{
- element->ann = NULL;
+ element->stmt = NULL;
element->rhs = expr;
}
else if (TREE_CODE (expr) == COND_EXPR)
{
- element->ann = stmt_ann (expr);
+ element->stmt = expr;
element->rhs = COND_EXPR_COND (expr);
}
else if (TREE_CODE (expr) == SWITCH_EXPR)
{
- element->ann = stmt_ann (expr);
+ element->stmt = expr;
element->rhs = SWITCH_COND (expr);
}
else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
{
- element->ann = stmt_ann (expr);
+ element->stmt = expr;
element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
}
+ else if (TREE_CODE (expr) == GOTO_EXPR)
+ {
+ element->stmt = expr;
+ element->rhs = GOTO_DESTINATION (expr);
+ }
else
{
- element->ann = stmt_ann (expr);
+ element->stmt = expr;
element->rhs = TREE_OPERAND (expr, 1);
}
remove_local_expressions_from_table (void)
{
/* Remove all the expressions made available in this block. */
- while (VARRAY_ACTIVE_SIZE (avail_exprs_stack) > 0)
+ while (VEC_length (tree, avail_exprs_stack) > 0)
{
struct expr_hash_elt element;
- tree expr = VARRAY_TOP_TREE (avail_exprs_stack);
- VARRAY_POP (avail_exprs_stack);
+ tree expr = VEC_pop (tree, avail_exprs_stack);
if (expr == NULL_TREE)
break;
static void
restore_nonzero_vars_to_original_value (void)
{
- while (VARRAY_ACTIVE_SIZE (nonzero_vars_stack) > 0)
+ while (VEC_length (tree, nonzero_vars_stack) > 0)
{
- tree name = VARRAY_TOP_TREE (nonzero_vars_stack);
- VARRAY_POP (nonzero_vars_stack);
+ tree name = VEC_pop (tree, nonzero_vars_stack);
if (name == NULL)
break;
static void
restore_vars_to_original_value (void)
{
- while (VARRAY_ACTIVE_SIZE (const_and_copies_stack) > 0)
+ while (VEC_length (tree, const_and_copies_stack) > 0)
{
tree prev_value, dest;
- dest = VARRAY_TOP_TREE (const_and_copies_stack);
- VARRAY_POP (const_and_copies_stack);
+ dest = VEC_pop (tree, const_and_copies_stack);
if (dest == NULL)
break;
- prev_value = VARRAY_TOP_TREE (const_and_copies_stack);
- VARRAY_POP (const_and_copies_stack);
-
+ prev_value = VEC_pop (tree, 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 (void)
-{
- /* Restore CURRDEFS to its original state. */
- while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
- {
- tree tmp = VARRAY_TOP_TREE (block_defs_stack);
- tree saved_def, var;
-
- VARRAY_POP (block_defs_stack);
-
- 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
- else, it must have been an _DECL node and its current reaching
- definition must have been NULL. */
- if (TREE_CODE (tmp) == SSA_NAME)
- {
- saved_def = tmp;
- var = SSA_NAME_VAR (saved_def);
- }
- else
- {
- saved_def = NULL;
- var = tmp;
- }
-
- var_ann (var)->current_def = saved_def;
- }
-}
-
/* We have finished processing the dominator children of BB, perform
any finalization actions in preparation for leaving this node in
the dominator tree. */
{
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 (EDGE_COUNT (bb->succs) == 1
- && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
- && (get_immediate_dominator (CDI_DOMINATORS, EDGE_SUCC (bb, 0)->dest) != bb
- || phi_nodes (EDGE_SUCC (bb, 0)->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, EDGE_SUCC (bb, 0));
+ thread_across_edge (walk_data, single_succ_edge (bb));
}
else if ((last = last_stmt (bb))
&& TREE_CODE (last) == COND_EXPR
&& (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) == tcc_comparison)
- 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))
{
+ 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. */
- VARRAY_PUSH_TREE (avail_exprs_stack, NULL_TREE);
- VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
- VARRAY_PUSH_TREE (const_and_copies_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
+ VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
+
+ edge_info = true_edge->aux;
- /* Record any equivalences created by following this edge. */
- if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
+ /* If we have info associated with this edge, record it into
+ our equivalency tables. */
+ if (edge_info)
{
- record_cond (cond, boolean_true_node);
- record_dominating_conditions (cond);
- record_cond (inverted, boolean_false_node);
+ 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. */
+ if (lhs && TREE_CODE (lhs) == 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_true_node);
/* Now thread the edge. */
thread_across_edge (walk_data, true_edge);
we threaded this edge. */
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) == tcc_comparison)
+ 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);
- record_cond (inverted, boolean_true_node);
- record_dominating_conditions (inverted);
+ 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. */
+ if (lhs && TREE_CODE (lhs) == 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);
thread_across_edge (walk_data, false_edge);
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 (VARRAY_ACTIVE_SIZE (vrp_variables_stack) > 0)
+ while (VEC_length (tree, vrp_variables_stack) > 0)
{
- tree var = VARRAY_TOP_TREE (vrp_variables_stack);
+ tree var = VEC_pop (tree, vrp_variables_stack);
struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
void **slot;
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_POP (vrp_variables_stack);
+ VEC(vrp_element_p,heap) **var_vrp_records;
if (var == NULL)
break;
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;
+ var_vrp_records = &vrp_hash_elt_p->records;
- while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
+ while (VEC_length (vrp_element_p, *var_vrp_records) > 0)
{
struct vrp_element *element
- = (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
+ = VEC_last (vrp_element_p, *var_vrp_records);
if (element->bb != bb)
break;
- VARRAY_POP (var_vrp_records);
+ VEC_pop (vrp_element_p, *var_vrp_records);
}
}
/* If we queued any statements to rescan in this block, then
go ahead and rescan them now. */
- while (VARRAY_ACTIVE_SIZE (stmts_to_rescan) > 0)
+ while (VEC_length (tree, stmts_to_rescan) > 0)
{
- tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
+ tree stmt = VEC_last (tree, stmts_to_rescan);
basic_block stmt_bb = bb_for_stmt (stmt);
if (stmt_bb != bb)
break;
- VARRAY_POP (stmts_to_rescan);
- mark_new_vars_to_rename (stmt, vars_to_rename);
+ VEC_pop (tree, stmts_to_rescan);
+ mark_new_vars_to_rename (stmt);
}
}
even if we do not know its exact value. */
static void
-record_equivalences_from_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
+record_equivalences_from_phis (basic_block bb)
{
tree phi;
{
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;
}
if (i == PHI_NUM_ARGS (phi))
bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
-
- register_new_def (lhs, &block_defs_stack);
}
}
has more than one incoming edge, then no equivalence is created. */
static void
-record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- 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 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 (ignoring loop backedges), then extract
- EDGE_FLAGS from the single incoming edge. Otherwise just return as
- there is nothing to do. */
- if (EDGE_COUNT (bb->preds) >= 1
- && parent_block_last_stmt)
+ /* 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 e = single_incoming_edge_ignoring_loop_edges (bb);
- if (e && bb_for_stmt (parent_block_last_stmt) == e->src)
- edge_flags = e->flags;
- else
- return;
- }
- else
- return;
+ 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 (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,
- bb);
- /* 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 (EDGE_PRED (bb, 0)->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 = fold_convert (TREE_TYPE (switch_cond),
- 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);
}
/* Dump SSA statistics on FILE. */
fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
opt_stats.num_re, PERCENT (opt_stats.num_re,
n_exprs));
+ fprintf (file, " Constants propagated: %6ld\n",
+ opt_stats.num_const_prop);
+ fprintf (file, " Copies propagated: %6ld\n",
+ opt_stats.num_copy_prop);
+
+ fprintf (file, "\nTotal number of DOM iterations: %6ld\n",
+ opt_stats.num_iterations);
fprintf (file, "\nHash table statistics:\n");
/* Record this SSA_NAME so that we can reset the global table
when we leave this block. */
- VARRAY_PUSH_TREE (nonzero_vars_stack, var);
+ VEC_safe_push (tree, heap, nonzero_vars_stack, var);
}
/* Enter a statement into the true/false expression hash table indicating
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;
- VARRAY_PUSH_TREE (avail_exprs_stack, cond);
+ VEC_safe_push (tree, heap, avail_exprs_stack, cond);
}
else
free (element);
}
-/* COND is a condition which is known to be true. Record variants of
- COND which must also be true.
+/* 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_dominating_conditions (tree cond)
+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:
- record_cond (build2 (LE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (ORDERED_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (LTGT_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- break;
-
case GT_EXPR:
- record_cond (build2 (GE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (ORDERED_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (LTGT_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (ORDERED_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (ORDERED_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (LE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (GE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNLE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNGE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNEQ_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNLT_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNGT_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (UNLE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- break;
-
case UNGT_EXPR:
- record_cond (build2 (UNGE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (UNLE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (UNGE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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:
- record_cond (build2 (NE_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
- record_cond (build2 (ORDERED_EXPR, boolean_type_node,
- TREE_OPERAND (cond, 0),
- TREE_OPERAND (cond, 1)),
- boolean_true_node);
+ 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.
{
SSA_NAME_VALUE (x) = y;
- VARRAY_PUSH_TREE (const_and_copies_stack, prev_x);
- VARRAY_PUSH_TREE (const_and_copies_stack, x);
+ VEC_reserve (tree, heap, const_and_copies_stack, 2);
+ VEC_quick_push (tree, const_and_copies_stack, prev_x);
+ VEC_quick_push (tree, 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. */
+
+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)
if (TREE_CODE (y) == SSA_NAME)
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;
{
enum tree_code code = TREE_CODE (exp);
return !(!flag_unsafe_math_optimizations
- && (code == MULT_EXPR || code == PLUS_EXPR)
+ && (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
hash tables. Try to simplify the RHS using whatever equivalences
we may have recorded.
the hash table and return the result. Otherwise return NULL. */
static tree
-simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
- tree stmt, int insert)
+simplify_rhs_and_lookup_avail_expr (tree stmt, int insert)
{
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhs_code = TREE_CODE (rhs);
{
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)
{
dont_fold_assoc:;
}
- /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
- and BIT_AND_EXPR respectively if the first operand is greater
- than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
- && integer_pow2p (TREE_OPERAND (rhs, 1)))
- {
- tree val;
- tree op = TREE_OPERAND (rhs, 0);
-
- if (TYPE_UNSIGNED (TREE_TYPE (op)))
- {
- val = integer_one_node;
- }
- else
- {
- tree dummy_cond = walk_data->global_data;
-
- if (! dummy_cond)
- {
- dummy_cond = build (GT_EXPR, boolean_type_node,
- op, integer_zero_node);
- dummy_cond = build (COND_EXPR, void_type_node,
- dummy_cond, NULL, NULL);
- walk_data->global_data = dummy_cond;
- }
- 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)
- = integer_zero_node;
- }
- val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
- }
-
- if (val && integer_onep (val))
- {
- tree t;
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- if (rhs_code == TRUNC_DIV_EXPR)
- t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
- 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, insert);
- }
- }
-
- /* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
- {
- tree val;
- tree op = TREE_OPERAND (rhs, 0);
- tree type = TREE_TYPE (op);
-
- if (TYPE_UNSIGNED (type))
- {
- val = integer_zero_node;
- }
- else
- {
- tree dummy_cond = walk_data->global_data;
-
- if (! dummy_cond)
- {
- dummy_cond = build (LE_EXPR, boolean_type_node,
- op, integer_zero_node);
- dummy_cond = build (COND_EXPR, void_type_node,
- dummy_cond, NULL, NULL);
- walk_data->global_data = dummy_cond;
- }
- 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)
- = build_int_cst (type, 0);
- }
- 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)
- = build_int_cst (type, 0);
-
- val = simplify_cond_and_lookup_avail_expr (dummy_cond,
- NULL, false);
-
- if (val)
- {
- if (integer_zerop (val))
- val = integer_one_node;
- else if (integer_onep (val))
- val = integer_zero_node;
- }
- }
- }
-
- if (val
- && (integer_onep (val) || integer_zerop (val)))
- {
- tree t;
-
- if (integer_onep (val))
- t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
- else
- t = op;
-
- result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
- }
- }
-
/* Optimize *"foo" into 'f'. This is done here rather than
in fold to avoid problems with stuff like &*"foo". */
if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
{
tree def_rhs = TREE_OPERAND (def_stmt, 1);
+
+ /* If either operand to the comparison is a pointer to
+ a function, then we can not apply this optimization
+ as some targets require function pointers to be
+ canonicalized and in this case this optimization would
+ eliminate a necessary canonicalization. */
+ if ((POINTER_TYPE_P (TREE_TYPE (op0))
+ && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == FUNCTION_TYPE)
+ || (POINTER_TYPE_P (TREE_TYPE (op1))
+ && TREE_CODE (TREE_TYPE (TREE_TYPE (op1))) == FUNCTION_TYPE))
+ return NULL;
+
/* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
if ((TREE_CODE (def_rhs) == NOP_EXPR
|| TREE_CODE (def_rhs) == CONVERT_EXPR)
> TYPE_PRECISION (TREE_TYPE (def_rhs)))
return NULL;
+ /* If the inner type of the conversion is a pointer to
+ a function, then we can not apply this optimization
+ as some targets require function pointers to be
+ canonicalized. This optimization would result in
+ canonicalization of the pointer when it was not originally
+ needed/intended. */
+ if (POINTER_TYPE_P (def_rhs_inner_type)
+ && TREE_CODE (TREE_TYPE (def_rhs_inner_type)) == FUNCTION_TYPE)
+ return NULL;
+
/* What we want to prove is that if we convert OP1 to
the type of the object inside the NOP_EXPR that the
result is still equivalent to SRC.
int limit;
tree low, high, cond_low, cond_high;
int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
- varray_type vrp_records;
+ VEC(vrp_element_p,heap) **vrp_records;
struct vrp_element *element;
struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
void **slot;
/* If this is not a real stmt, ann will be NULL and we
avoid processing the operands. */
if (ann)
- modify_stmt (stmt);
+ mark_stmt_modified (stmt);
/* Lookup the condition and return its known value if it
exists. */
return NULL;
vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
- vrp_records = vrp_hash_elt_p->records;
- if (vrp_records == NULL)
- return NULL;
+ vrp_records = &vrp_hash_elt_p->records;
- limit = VARRAY_ACTIVE_SIZE (vrp_records);
+ limit = VEC_length (vrp_element_p, *vrp_records);
/* If we have no value range records for this variable, or we are
unable to extract a range for this condition, then there is
conditional into the current range.
These properties also help us avoid unnecessary work. */
- element
- = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
+ element = VEC_last (vrp_element_p, *vrp_records);
if (element->high && element->low)
{
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. */
{
/* Get the high/low value from the previous element. */
struct vrp_element *prev
- = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
- limit - 2);
+ = VEC_index (vrp_element_p, *vrp_records, limit - 2);
low = prev->low;
high = prev->high;
Similarly the high value for the merged range is the
minimum of the previous high value and the high value of
this record. */
- low = (tree_int_cst_compare (low, tmp_low) == 1
+ low = (low && tree_int_cst_compare (low, tmp_low) == 1
? low : tmp_low);
- high = (tree_int_cst_compare (high, tmp_high) == -1
+ high = (high && tree_int_cst_compare (high, tmp_high) == -1
? high : tmp_high);
}
if (!fail)
{
SWITCH_COND (stmt) = def;
- modify_stmt (stmt);
+ mark_stmt_modified (stmt);
return lookup_avail_expr (stmt, insert);
}
edge e;
edge_iterator ei;
- /* This can get rather expensive if the implementation is naive in
- how it finds the phi alternative associated with a particular edge. */
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
- int phi_num_args;
- int hint;
+ 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 (! phi)
continue;
- /* There is no guarantee that for any two PHI nodes in a block that
- the phi alternative associated with a particular edge will be
- at the same index in the phi alternative array.
-
- However, it is very likely they will be the same. So we keep
- track of the index of the alternative where we found the edge in
- the previous phi node and check that index first in the next
- phi node. If that hint fails, then we actually search all
- the entries. */
- phi_num_args = PHI_NUM_ARGS (phi);
- hint = phi_num_args;
+ indx = e->dest_idx;
for ( ; phi; phi = PHI_CHAIN (phi))
{
- int i;
tree new;
use_operand_p orig_p;
tree orig;
- /* If the hint is valid (!= phi_num_args), see if it points
- us to the desired phi alternative. */
- if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
- ;
- else
- {
- /* The hint was either invalid or did not point to the
- correct phi alternative. Search all the alternatives
- for the correct one. Update the hint. */
- for (i = 0; i < phi_num_args; i++)
- if (PHI_ARG_EDGE (phi, i) == e)
- break;
- hint = i;
- }
-
- /* If we did not find the proper alternative, then something is
- horribly wrong. */
- gcc_assert (hint != phi_num_args);
-
/* 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, hint);
+ 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, hint) = true;
+ 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
+ && new != orig
&& (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)
{
- propagate_value (orig_p, new);
+ tree labels = SWITCH_LABELS (stmt);
+ int i, n_labels = TREE_VEC_LENGTH (labels);
+ tree *info = xcalloc (last_basic_block, 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.
-/* Propagate known constants/copies into PHI nodes of BB's successor
- blocks. */
+ 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)
{
+ record_edge_info (bb);
cprop_into_successor_phis (bb, nonzero_vars);
}
table. */
static bool
-eliminate_redundant_computations (struct dom_walk_data *walk_data,
- tree stmt, stmt_ann_t ann)
+eliminate_redundant_computations (tree stmt, stmt_ann_t ann)
{
- v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
tree *expr_p, def = NULL_TREE;
bool insert = true;
tree cached_lhs;
bool retval = false;
+ bool modify_expr_p = false;
if (TREE_CODE (stmt) == MODIFY_EXPR)
def = TREE_OPERAND (stmt, 0);
|| ! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
- || NUM_V_MAY_DEFS (v_may_defs) != 0)
+ || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)
+ /* 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. */
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, insert);
+ cached_lhs = simplify_rhs_and_lookup_avail_expr (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 (TREE_CODE (stmt) == SWITCH_EXPR)
expr_p = &SWITCH_COND (stmt);
else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
- expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+ {
+ expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+ modify_expr_p = true;
+ }
else
- expr_p = &TREE_OPERAND (stmt, 1);
+ {
+ expr_p = &TREE_OPERAND (stmt, 1);
+ modify_expr_p = true;
+ }
/* It is safe to ignore types here since we have already done
type checking in the hashing and equality routines. In fact
propagation. Also, make sure that it is safe to propagate
CACHED_LHS into *EXPR_P. */
if (cached_lhs
- && (TREE_CODE (cached_lhs) != SSA_NAME
+ && ((TREE_CODE (cached_lhs) != SSA_NAME
+ && (modify_expr_p
+ || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
+ TREE_TYPE (cached_lhs))))
|| may_propagate_copy (*expr_p, cached_lhs)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
|| (POINTER_TYPE_P (TREE_TYPE (*expr_p))
&& is_gimple_min_invariant (cached_lhs)))
retval = true;
+
+ if (modify_expr_p
+ && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
+ TREE_TYPE (cached_lhs)))
+ cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);
propagate_tree_value (expr_p, cached_lhs);
- modify_stmt (stmt);
+ mark_stmt_modified (stmt);
}
return retval;
}
|| is_gimple_min_invariant (rhs)))
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
- stripped as they do not affect this equivalence. */
- while (TREE_CODE (rhs) == NOP_EXPR
- || TREE_CODE (rhs) == CONVERT_EXPR)
- rhs = TREE_OPERAND (rhs, 0);
-
- if (alloca_call_p (rhs)
- || (TREE_CODE (rhs) == ADDR_EXPR
- && DECL_P (TREE_OPERAND (rhs, 0))
- && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
- 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)))
+ if (tree_expr_nonzero_p (rhs))
record_var_is_nonzero (lhs);
}
/* Build a new statement with the RHS and LHS exchanged. */
new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
- create_ssa_artficial_load_stmt (&(ann->operands), new);
+ create_ssa_artficial_load_stmt (new, stmt);
/* Finally enter the statement into the available expression
table. */
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)
+ if (val && val != op && TREE_CODE (val) != VALUE_HANDLE)
{
tree op_type, val_type;
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))
+ && (TREE_CODE (val) != SSA_NAME
+ || is_gimple_reg (val)
+ || get_virtual_var (val) != get_virtual_var (op)))
return false;
/* Do not replace hard register operands in asm statements. */
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;
/* Dump details. */
if (dump_file && (dump_flags & TDF_DETAILS))
&& is_gimple_min_invariant (val)))
may_have_exposed_new_symbols = true;
+ if (TREE_CODE (val) != SSA_NAME)
+ opt_stats.num_const_prop++;
+ else
+ opt_stats.num_copy_prop++;
+
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. */
- modify_stmt (stmt);
+ mark_stmt_modified (stmt);
}
return may_have_exposed_new_symbols;
}
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)
{
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.
+/* Optimize the statement pointed to by iterator SI.
We try to perform some simplistic global redundancy elimination and
constant propagation:
the variable in the LHS in the CONST_AND_COPIES table. */
static void
-optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
- block_stmt_iterator si)
+optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb, block_stmt_iterator si)
{
stmt_ann_t ann;
- tree stmt;
+ tree stmt, old_stmt;
bool may_optimize_p;
bool may_have_exposed_new_symbols = false;
- stmt = bsi_stmt (si);
+ old_stmt = 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;
fold its RHS before checking for redundant computations. */
if (ann->modified)
{
+ tree rhs;
+
/* Try to fold the statement making sure that STMT is kept
up to date. */
if (fold_stmt (bsi_stmt_ptr (si)))
}
}
+ rhs = get_rhs (stmt);
+ if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
+ recompute_tree_invarant_for_addr_expr (rhs);
+
/* Constant/copy propagation above may change the set of
virtual operands associated with this statement. Folding
may remove the need for some virtual operands.
if (may_optimize_p)
may_have_exposed_new_symbols
- |= eliminate_redundant_computations (walk_data, stmt, ann);
+ |= eliminate_redundant_computations (stmt, ann);
/* Record any additional equivalences created by this statement. */
if (TREE_CODE (stmt) == MODIFY_EXPR)
may_optimize_p,
ann);
- 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.
/* 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))
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
{
bitmap_set_bit (need_eh_cleanup, bb->index);
if (dump_file && (dump_flags & TDF_DETAILS))
}
if (may_have_exposed_new_symbols)
- VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
+ VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si));
}
/* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
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 (avail_exprs_stack);
+ VEC_pop (tree, avail_exprs_stack);
/* And make sure we record the fact that we modified this
statement. */
- modify_stmt (stmt);
+ mark_stmt_modified (stmt);
return cached_lhs;
}
NULL_TREE.
Also, when an expression is first inserted in the AVAIL_EXPRS table, it
- is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
+ is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they
can be removed when we finish processing this block and its children.
NOTE: This function assumes that STMT is a MODIFY_EXPR node that
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;
{
tree t = element->rhs;
free (element);
-
- if (TREE_CODE (t) == EQ_EXPR)
- return boolean_false_node;
- else
- return boolean_true_node;
+ return constant_boolean_node (TREE_CODE (t) != EQ_EXPR,
+ TREE_TYPE (t));
}
}
if (*slot == NULL)
{
*slot = (void *) element;
- VARRAY_PUSH_TREE (avail_exprs_stack, stmt ? stmt : element->rhs);
+ VEC_safe_push (tree, heap, avail_exprs_stack,
+ stmt ? stmt : element->rhs);
return NULL_TREE;
}
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;
static void
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 (COMPARISON_CLASS_P (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_hash_elt *vrp_hash_elt;
struct vrp_element *element;
- varray_type *vrp_records_p;
+ VEC(vrp_element_p,heap) **vrp_records_p;
void **slot;
if (*slot == NULL)
*slot = (void *) vrp_hash_elt;
else
- free (vrp_hash_elt);
+ vrp_free (vrp_hash_elt);
vrp_hash_elt = (struct vrp_hash_elt *) *slot;
vrp_records_p = &vrp_hash_elt->records;
element->cond = cond;
element->bb = bb;
- if (*vrp_records_p == NULL)
- VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
-
- VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
- VARRAY_PUSH_TREE (vrp_variables_stack, TREE_OPERAND (cond, 0));
+ VEC_safe_push (vrp_element_p, heap, *vrp_records_p, element);
+ VEC_safe_push (tree, 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.
-
- Not all conditional statements will result in a useful assignment.
- Return NULL_TREE in that case.
-
- 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,
- basic_block bb)
-{
- 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 = constant_boolean_node (true_arm, TREE_TYPE (cond));
- return retval;
- }
-
- /* If we have a comparison expression, then record its result into
- the available expression table. */
- 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 && 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);
- record_dominating_conditions (cond);
- record_cond (inverted, boolean_false_node);
-
- if (TREE_CONSTANT (op1))
- record_range (cond, bb);
-
- /* 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);
- record_dominating_conditions (inverted);
- record_cond (cond, boolean_false_node);
-
- if (TREE_CONSTANT (op1))
- record_range (inverted, bb);
-
- /* 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;
- }
- }
- }
- }
-
- return retval;
-}
-
/* Hashing and equality functions for VRP_DATA.
Since this hash table is addressed by SSA_NAMEs, we can hash on
static hashval_t
avail_expr_hash (const void *p)
{
- stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
+ tree stmt = ((struct expr_hash_elt *)p)->stmt;
tree rhs = ((struct expr_hash_elt *)p)->rhs;
+ tree vuse;
+ ssa_op_iter iter;
hashval_t val = 0;
- size_t i;
- vuse_optype vuses;
/* iterative_hash_expr knows how to deal with any expression and
deals with commutative operators as well, so just use it instead
/* If the hash table entry is not associated with a statement, then we
can just hash the expression and not worry about virtual operands
and such. */
- if (!ann)
+ if (!stmt || !stmt_ann (stmt))
return val;
/* Add the SSA version numbers of every vuse operand. This is important
because compound variables like arrays are not renamed in the
operands. Rather, the rename is done on the virtual variable
representing all the elements of the array. */
- vuses = VUSE_OPS (ann);
- for (i = 0; i < NUM_VUSES (vuses); i++)
- val = iterative_hash_expr (VUSE_OP (vuses, i), val);
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+ val = iterative_hash_expr (vuse, val);
return val;
}
static int
avail_expr_eq (const void *p1, const void *p2)
{
- stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
+ tree stmt1 = ((struct expr_hash_elt *)p1)->stmt;
tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
- stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
+ tree stmt2 = ((struct expr_hash_elt *)p2)->stmt;
tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
/* If they are the same physical expression, return true. */
- if (rhs1 == rhs2 && ann1 == ann2)
+ if (rhs1 == rhs2 && stmt1 == stmt2)
return true;
/* If their codes are not equal, then quit now. */
|| lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
&& operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
{
- vuse_optype ops1 = NULL;
- vuse_optype ops2 = NULL;
- size_t num_ops1 = 0;
- size_t num_ops2 = 0;
- size_t i;
-
- if (ann1)
- {
- ops1 = VUSE_OPS (ann1);
- num_ops1 = NUM_VUSES (ops1);
- }
-
- if (ann2)
- {
- ops2 = VUSE_OPS (ann2);
- num_ops2 = NUM_VUSES (ops2);
- }
-
- /* If the number of virtual uses is different, then we consider
- them not equal. */
- if (num_ops1 != num_ops2)
- return false;
-
- for (i = 0; i < num_ops1; i++)
- if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
- return false;
-
- gcc_assert (((struct expr_hash_elt *)p1)->hash
+ bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
+ gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash
== ((struct expr_hash_elt *)p2)->hash);
- return true;
+ return ret;
}
return false;
}
-
-/* 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 (tree stmt)
-{
- tree def;
- ssa_op_iter iter;
-
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
- {
-
- /* FIXME: We shouldn't be registering new defs if the variable
- doesn't need to be renamed. */
- register_new_def (def, &block_defs_stack);
- }
-}
-