/* Generic SSA value propagation engine.
- Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
- Free Software Foundation; either version 2, or (at your option) any
+ Free Software Foundation; either version 3, or (at your option) any
later version.
GCC is distributed in the hope that it will be useful, but WITHOUT
for more details.
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, 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "langhooks.h"
#include "varray.h"
#include "vec.h"
+#include "value-prof.h"
/* This file implements a generic value propagation engine based on
the same propagation used by the SSA-CCP algorithm [1].
static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
-/* Use the TREE_DEPRECATED bitflag to mark statements that have been
+/* Use the deprecated flag to mark statements that have been
added to one of the SSA edges worklists. This flag is used to
avoid visiting statements unnecessarily when draining an SSA edge
worklist. If while simulating a basic block, we find a statement with
STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
processing from visiting it again. */
-#define STMT_IN_SSA_EDGE_WORKLIST(T) TREE_DEPRECATED (T)
+#define STMT_IN_SSA_EDGE_WORKLIST(T) ((T)->base.deprecated_flag)
/* A bitmap to keep track of executable blocks in the CFG. */
static sbitmap executable_blocks;
static void
cfg_blocks_add (basic_block bb)
{
+ bool head = false;
+
gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
gcc_assert (!TEST_BIT (bb_in_list, bb->index));
cfg_blocks_head = 0;
VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
}
- else
+ /* Minor optimization: we prefer to see blocks with more
+ predecessors later, because there is more of a chance that
+ the incoming edges will be executable. */
+ else if (EDGE_COUNT (bb->preds)
+ >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
+ cfg_blocks_head)->preds))
cfg_blocks_tail = ((cfg_blocks_tail + 1)
% VEC_length (basic_block, cfg_blocks));
+ else
+ {
+ if (cfg_blocks_head == 0)
+ cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
+ --cfg_blocks_head;
+ head = true;
+ }
}
- VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb);
+ VEC_replace (basic_block, cfg_blocks,
+ head ? cfg_blocks_head : cfg_blocks_tail,
+ bb);
SET_BIT (bb_in_list, bb->index);
}
}
-/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
- GIMPLE expression no changes are done and the function returns
- false. */
+/* Return true if EXPR is a valid GIMPLE expression. */
bool
-set_rhs (tree *stmt_p, tree expr)
+valid_gimple_expression_p (tree expr)
{
- tree stmt = *stmt_p, op;
enum tree_code code = TREE_CODE (expr);
- stmt_ann_t ann;
- tree var;
- ssa_op_iter iter;
- /* Verify the constant folded result is valid gimple. */
switch (TREE_CODE_CLASS (code))
{
case tcc_declaration:
- if (!is_gimple_variable(expr))
+ if (!is_gimple_variable (expr))
return false;
break;
switch (code)
{
case ADDR_EXPR:
- if (TREE_CODE (TREE_OPERAND (expr, 0)) == ARRAY_REF
- && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (expr, 0), 1)))
- return false;
- break;
+ {
+ tree t = TREE_OPERAND (expr, 0);
+ while (handled_component_p (t))
+ {
+ /* ??? More checks needed, see the GIMPLE verifier. */
+ if ((TREE_CODE (t) == ARRAY_REF
+ || TREE_CODE (t) == ARRAY_RANGE_REF)
+ && !is_gimple_val (TREE_OPERAND (t, 1)))
+ return false;
+ t = TREE_OPERAND (t, 0);
+ }
+ if (!is_gimple_id (t))
+ return false;
+ break;
+ }
case TRUTH_NOT_EXPR:
if (!is_gimple_val (TREE_OPERAND (expr, 0)))
return false;
}
+ return true;
+}
+
+
+/* Set the main expression of *STMT_P to EXPR. If EXPR is not a valid
+ GIMPLE expression no changes are done and the function returns
+ false. */
+
+bool
+set_rhs (tree *stmt_p, tree expr)
+{
+ tree stmt = *stmt_p, op;
+ tree new_stmt;
+ tree var;
+ ssa_op_iter iter;
+ int eh_region;
+
+ if (!valid_gimple_expression_p (expr))
+ return false;
+
if (EXPR_HAS_LOCATION (stmt)
&& (EXPR_P (expr)
|| GIMPLE_STMT_P (expr))
case GIMPLE_MODIFY_STMT:
op = GIMPLE_STMT_OPERAND (stmt, 1);
if (TREE_CODE (op) == WITH_SIZE_EXPR)
- {
- stmt = op;
- TREE_OPERAND (stmt, 1) = expr;
- }
+ TREE_OPERAND (op, 0) = expr;
else
- GIMPLE_STMT_OPERAND (stmt, 1) = expr;
+ GIMPLE_STMT_OPERAND (stmt, 1) = expr;
break;
case COND_EXPR:
default:
/* Replace the whole statement with EXPR. If EXPR has no side
effects, then replace *STMT_P with an empty statement. */
- ann = stmt_ann (stmt);
- *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
- (*stmt_p)->base.ann = (tree_ann_t) ann;
+ new_stmt = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
+ *stmt_p = new_stmt;
+
+ /* Preserve the annotation, the histograms and the EH region information
+ associated with the original statement. The EH information
+ needs to be preserved only if the new statement still can throw. */
+ new_stmt->base.ann = (tree_ann_t) stmt_ann (stmt);
+ gimple_move_stmt_histograms (cfun, new_stmt, stmt);
+ if (tree_could_throw_p (new_stmt))
+ {
+ eh_region = lookup_stmt_eh_region (stmt);
+ /* We couldn't possibly turn a nothrow into a throw statement. */
+ gcc_assert (eh_region >= 0);
+ remove_stmt_from_eh_region (stmt);
+ add_stmt_to_eh_region (new_stmt, eh_region);
+ }
if (gimple_in_ssa_p (cfun)
&& TREE_SIDE_EFFECTS (expr))
SSA_NAME_DEF_STMT (var) = *stmt_p;
}
}
+ stmt->base.ann = NULL;
break;
}
long num_const_prop;
long num_copy_prop;
long num_pred_folded;
+ long num_dce;
};
static struct prop_stats_d prop_stats;
else
return false;
- val = vrp_evaluate_conditional (*pred_p, true);
+ if (TREE_CODE (*pred_p) == SSA_NAME)
+ val = vrp_evaluate_conditional (EQ_EXPR,
+ *pred_p,
+ boolean_true_node,
+ stmt);
+ else
+ val = vrp_evaluate_conditional (TREE_CODE (*pred_p),
+ TREE_OPERAND (*pred_p, 0),
+ TREE_OPERAND (*pred_p, 1),
+ stmt);
+
if (val)
{
if (modify_stmt_p)
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
replace_phi_args_in (phi, prop_value);
- for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+ /* Propagate known values into stmts. Do a backward walk to expose
+ more trivially deletable stmts. */
+ for (i = bsi_last (bb); !bsi_end_p (i);)
{
bool replaced_address, did_replace;
- tree prev_stmt = NULL;
+ tree call, prev_stmt = NULL;
tree stmt = bsi_stmt (i);
/* Ignore ASSERT_EXPRs. They are used by VRP to generate
afterwards. */
if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
&& TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
- continue;
+ {
+ bsi_prev (&i);
+ continue;
+ }
+
+ /* No point propagating into a stmt whose result is not used,
+ but instead we might be able to remove a trivially dead stmt. */
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+ && !stmt_ann (stmt)->has_volatile_ops
+ && has_zero_uses (GIMPLE_STMT_OPERAND (stmt, 0))
+ && !tree_could_throw_p (stmt)
+ && (!(call = get_call_expr_in (stmt))
+ || !TREE_SIDE_EFFECTS (call)))
+ {
+ block_stmt_iterator i2;
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "Removing dead stmt ");
+ print_generic_expr (dump_file, stmt, 0);
+ fprintf (dump_file, "\n");
+ }
+ prop_stats.num_dce++;
+ bsi_prev (&i);
+ i2 = bsi_for_stmt (stmt);
+ bsi_remove (&i2, true);
+ release_defs (stmt);
+ continue;
+ }
/* Record the state of the statement before replacements. */
push_stmt_changes (bsi_stmt_ptr (i));
statement. */
if (use_ranges_p)
simplify_stmt_using_ranges (stmt);
+
+ bsi_prev (&i);
}
}
- if (dump_file && (dump_flags & TDF_STATS))
- {
- fprintf (dump_file, "Constants propagated: %6ld\n",
- prop_stats.num_const_prop);
- fprintf (dump_file, "Copies propagated: %6ld\n",
- prop_stats.num_copy_prop);
- fprintf (dump_file, "Predicates folded: %6ld\n",
- prop_stats.num_pred_folded);
- }
+ statistics_counter_event (cfun, "Constants propagated",
+ prop_stats.num_const_prop);
+ statistics_counter_event (cfun, "Copies propagated",
+ prop_stats.num_copy_prop);
+ statistics_counter_event (cfun, "Predicates folded",
+ prop_stats.num_pred_folded);
+ statistics_counter_event (cfun, "Statements deleted",
+ prop_stats.num_dce);
return something_changed;
}