#include "tm_p.h"
#include "ggc.h"
#include "basic-block.h"
+#include "cfgloop.h"
#include "output.h"
#include "errors.h"
#include "expr.h"
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
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.
{
struct dom_walk_data walk_data;
unsigned int i;
+ struct loops loops_info;
memset (&opt_stats, 0, sizeof (opt_stats));
nonzero_vars_stack = VEC_alloc (tree_on_heap, 20);
vrp_variables_stack = VEC_alloc (tree_on_heap, 20);
stmts_to_rescan = VEC_alloc (tree_on_heap, 20);
- nonzero_vars = BITMAP_XMALLOC ();
- need_eh_cleanup = BITMAP_XMALLOC ();
+ nonzero_vars = BITMAP_ALLOC (NULL);
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
/* Setup callbacks for the generic dominator tree walker. */
walk_data.walk_stmts_backward = false;
calculate_dominance_info (CDI_DOMINATORS);
+ /* We need to know which edges exit loops so that we can
+ aggressively thread through loop headers to an exit
+ edge. */
+ flow_loops_find (&loops_info);
+ mark_loop_exit_edges (&loops_info);
+ flow_loops_free (&loops_info);
+
+ /* Clean up the CFG so that any forwarder blocks created by loop
+ canonicalization are removed. */
+ cleanup_tree_cfg ();
+
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
have turned into copies which allows better propagation of
/* Optimize the dominator tree. */
cfg_altered = false;
+ /* We need accurate information regarding back edges in the CFG
+ for jump threading. */
+ mark_dfs_back_edges ();
+
/* Recursively walk the dominator tree optimizing statements. */
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
- cfg_altered = thread_through_all_blocks ();
+ cfg_altered |= thread_through_all_blocks ();
/* Removal of statements may make some EH edges dead. Purge
such edges from the CFG as needed. */
bitmap_zero (need_eh_cleanup);
}
- free_dominance_info (CDI_DOMINATORS);
- cfg_altered = cleanup_tree_cfg ();
+ 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 ();
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
SSA_NAME_VALUE (name) = NULL;
}
}
- 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);
+ BITMAP_FREE (nonzero_vars);
+ BITMAP_FREE (need_eh_cleanup);
VEC_free (tree_on_heap, block_defs_stack);
VEC_free (tree_on_heap, avail_exprs_stack);
stmt_ann_t ann = stmt_ann (stmt);
use_optype uses = USE_OPS (ann);
vuse_optype vuses = VUSE_OPS (ann);
- tree *uses_copy = xcalloc (NUM_USES (uses), sizeof (tree));
- tree *vuses_copy = xcalloc (NUM_VUSES (vuses), sizeof (tree));
+ tree *uses_copy = xmalloc (NUM_USES (uses) * sizeof (tree));
+ tree *vuses_copy = xmalloc (NUM_VUSES (vuses) * sizeof (tree));
unsigned int i;
/* Make a copy of the uses into USES_COPY, then cprop into
arm will be taken. */
if (stmt
&& (TREE_CODE (stmt) == COND_EXPR
- || TREE_CODE (stmt) == SWITCH_EXPR))
+ || TREE_CODE (stmt) == SWITCH_EXPR
+ || TREE_CODE (stmt) == GOTO_EXPR))
{
tree cond, cached_lhs;
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);
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) == GOTO_EXPR
+ && TREE_CODE (TREE_OPERAND (last, 0)) == SSA_NAME)
+ {
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ thread_across_edge (walk_data, e);
+ }
}
else if ((last = last_stmt (bb))
&& TREE_CODE (last) == COND_EXPR
basic_block parent;
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);
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;
/* Build a new conditional using NEW_CODE, OP0 and OP1 and store
the new conditional into *p, then store a boolean_true_node
- into the the *(p + 1). */
+ into *(p + 1). */
static void
build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
&& 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.
{
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)
{
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;
|| ! def
|| TREE_CODE (def) != SSA_NAME
|| SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
- || NUM_V_MAY_DEFS (v_may_defs) != 0)
+ || NUM_V_MAY_DEFS (v_may_defs) != 0
+ /* Do not record equivalences for increments of ivs. This would create
+ overlapping live ranges for a very questionable gain. */
+ || simple_iv_increment_p (stmt))
insert = false;
/* Check if the expression has been computed before. */
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))
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 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:
OSDN Git Service
