#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
-#include "ggc.h"
#include "tree.h"
-#include "langhooks.h"
-
-/* These RTL headers are needed for basic-block.h. */
+#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
-#include "hard-reg-set.h"
+#include "ggc.h"
#include "basic-block.h"
-
+#include "output.h"
+#include "errors.h"
+#include "expr.h"
+#include "function.h"
#include "diagnostic.h"
-#include "tree-inline.h"
-#include "tree-flow.h"
-#include "tree-gimple.h"
+#include "timevar.h"
#include "tree-dump.h"
+#include "tree-flow.h"
#include "tree-pass.h"
-#include "timevar.h"
-#include "expr.h"
-#include "flags.h"
+#include "tree-ssa-propagate.h"
+#include "langhooks.h"
/* Possible lattice values. */
{
UNINITIALIZED = 0,
UNDEFINED,
+ UNKNOWN_VAL,
CONSTANT,
VARYING
} latticevalue;
-/* Use the TREE_VISITED bitflag to mark statements and PHI nodes that have
- been deemed VARYING and shouldn't be simulated again. */
-#define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T)
-
/* Main structure for CCP. Contains the lattice value and, if it's a
constant, the constant value. */
typedef struct
tree const_val;
} value;
-/* A bitmap to keep track of executable blocks in the CFG. */
-static sbitmap executable_blocks;
-
-/* Array of control flow edges on the worklist. */
-static GTY(()) varray_type cfg_blocks = NULL;
-
-static unsigned int cfg_blocks_num = 0;
-static int cfg_blocks_tail;
-static int cfg_blocks_head;
-
-static sbitmap bb_in_list;
-
/* This is used to track the current value of each variable. */
static value *value_vector;
-/* Worklist of SSA edges which will need reexamination as their definition
- has changed. SSA edges are def-use edges in the SSA web. For each
- edge, we store the definition statement or PHI node D. The destination
- nodes that need to be visited are accessed using immediate_uses
- (D). */
-static GTY(()) varray_type ssa_edges;
-
-/* Identical to SSA_EDGES. For performance reasons, the list of SSA
- edges is split into two. One contains all SSA edges who need to be
- reexamined because their lattice value changed to varying (this
- worklist), and the other contains all other SSA edges to be
- reexamined (ssa_edges).
-
- Since most values in the program are varying, the ideal situation
- is to move them to that lattice value as quickly as possible.
- Thus, it doesn't make sense to process any other type of lattice
- value until all varying values are propagated fully, which is one
- thing using the varying worklist achieves. In addition, if you
- don't use a separate worklist for varying edges, you end up with
- situations where lattice values move from
- undefined->constant->varying instead of undefined->varying.
-*/
-static GTY(()) varray_type varying_ssa_edges;
-
-
-static void initialize (void);
-static void finalize (void);
-static void visit_phi_node (tree);
-static tree ccp_fold (tree);
-static value cp_lattice_meet (value, value);
-static void visit_stmt (tree);
-static void visit_cond_stmt (tree);
-static void visit_assignment (tree);
-static void add_var_to_ssa_edges_worklist (tree, value);
-static void add_outgoing_control_edges (basic_block);
-static void add_control_edge (edge);
-static void def_to_varying (tree);
-static void set_lattice_value (tree, value);
-static void simulate_block (basic_block);
-static void simulate_stmt (tree);
-static void substitute_and_fold (void);
-static value evaluate_stmt (tree);
-static void dump_lattice_value (FILE *, const char *, value);
-static bool replace_uses_in (tree, bool *);
-static latticevalue likely_value (tree);
-static tree get_rhs (tree);
-static bool set_rhs (tree *, tree);
-static value *get_value (tree);
-static value get_default_value (tree);
-static tree ccp_fold_builtin (tree, tree);
-static bool get_strlen (tree, tree *, bitmap);
-static inline bool cfg_blocks_empty_p (void);
-static void cfg_blocks_add (basic_block);
-static basic_block cfg_blocks_get (void);
-static bool need_imm_uses_for (tree var);
-
-/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
- drain. This pops statements off the given WORKLIST and processes
- them until there are no more statements on WORKLIST. */
+
+/* Dump lattice value VAL to file OUTF prefixed by PREFIX. */
static void
-process_ssa_edge_worklist (varray_type *worklist)
+dump_lattice_value (FILE *outf, const char *prefix, value val)
{
- /* Drain the entire worklist. */
- while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
+ switch (val.lattice_val)
{
- /* Pull the statement to simulate off the worklist. */
- tree stmt = VARRAY_TOP_TREE (*worklist);
- stmt_ann_t ann = stmt_ann (stmt);
- VARRAY_POP (*worklist);
-
- /* visit_stmt can "cancel" reevaluation of some statements.
- If it does, then in_ccp_worklist will be zero. */
- if (ann->in_ccp_worklist)
- {
- ann->in_ccp_worklist = 0;
- simulate_stmt (stmt);
- }
- }
+ case UNDEFINED:
+ fprintf (outf, "%sUNDEFINED", prefix);
+ break;
+ case VARYING:
+ fprintf (outf, "%sVARYING", prefix);
+ break;
+ case UNKNOWN_VAL:
+ fprintf (outf, "%sUNKNOWN_VAL", prefix);
+ break;
+ case CONSTANT:
+ fprintf (outf, "%sCONSTANT ", prefix);
+ print_generic_expr (outf, val.const_val, dump_flags);
+ break;
+ default:
+ gcc_unreachable ();
+ }
}
-
-/* Main entry point for SSA Conditional Constant Propagation. FNDECL is
- the declaration for the function to optimize.
-
- On exit, VARS_TO_RENAME will contain the symbols that have been exposed by
- the propagation of ADDR_EXPR expressions into pointer dereferences and need
- to be renamed into SSA.
- PHASE indicates which dump file from the DUMP_FILES array to use when
- dumping debugging information. */
-static void
-tree_ssa_ccp (void)
-{
- initialize ();
+/* Return a default value for variable VAR using the following rules:
- /* Iterate until the worklists are empty. */
- while (!cfg_blocks_empty_p ()
- || VARRAY_ACTIVE_SIZE (ssa_edges) > 0
- || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0)
- {
- if (!cfg_blocks_empty_p ())
- {
- /* Pull the next block to simulate off the worklist. */
- basic_block dest_block = cfg_blocks_get ();
- simulate_block (dest_block);
- }
+ 1- Function arguments are considered VARYING.
+
+ 2- Global and static variables that are declared constant are
+ considered CONSTANT.
- /* In order to move things to varying as quickly as
- possible,process the VARYING_SSA_EDGES worklist first. */
- process_ssa_edge_worklist (&varying_ssa_edges);
+ 3- Any other virtually defined variable is considered UNKNOWN_VAL.
- /* Now process the SSA_EDGES worklist. */
- process_ssa_edge_worklist (&ssa_edges);
- }
+ 4- Any other value is considered UNDEFINED. This is useful when
+ considering PHI nodes. PHI arguments that are undefined do not
+ change the constant value of the PHI node, which allows for more
+ constants to be propagated. */
- /* Now perform substitutions based on the known constant values. */
- substitute_and_fold ();
+static value
+get_default_value (tree var)
+{
+ value val;
+ tree sym;
- /* Now cleanup any unreachable code. */
- cleanup_tree_cfg ();
+ if (TREE_CODE (var) == SSA_NAME)
+ sym = SSA_NAME_VAR (var);
+ else
+ {
+ gcc_assert (DECL_P (var));
+ sym = var;
+ }
- /* Free allocated memory. */
- finalize ();
+ val.lattice_val = UNDEFINED;
+ val.const_val = NULL_TREE;
- /* Debugging dumps. */
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (TREE_CODE (var) == SSA_NAME
+ && SSA_NAME_VALUE (var)
+ && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
{
- dump_referenced_vars (dump_file);
- fprintf (dump_file, "\n\n");
+ val.lattice_val = CONSTANT;
+ val.const_val = SSA_NAME_VALUE (var);
}
-}
-
-static bool
-gate_ccp (void)
-{
- return flag_tree_ccp != 0;
-}
+ else if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
+ {
+ /* Function arguments and volatile variables are considered VARYING. */
+ val.lattice_val = VARYING;
+ }
+ else if (TREE_STATIC (sym))
+ {
+ /* Globals and static variables are considered UNKNOWN_VAL,
+ unless they are declared 'const'. */
+ if (TREE_READONLY (sym)
+ && DECL_INITIAL (sym)
+ && is_gimple_min_invariant (DECL_INITIAL (sym)))
+ {
+ val.lattice_val = CONSTANT;
+ val.const_val = DECL_INITIAL (sym);
+ }
+ else
+ {
+ val.const_val = NULL_TREE;
+ val.lattice_val = UNKNOWN_VAL;
+ }
+ }
+ else if (!is_gimple_reg (sym))
+ {
+ val.const_val = NULL_TREE;
+ val.lattice_val = UNKNOWN_VAL;
+ }
+ else
+ {
+ enum tree_code code;
+ tree stmt = SSA_NAME_DEF_STMT (var);
-struct tree_opt_pass pass_ccp =
-{
- "ccp", /* name */
- gate_ccp, /* gate */
- tree_ssa_ccp, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_CCP, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func | TODO_rename_vars
- | TODO_ggc_collect | TODO_verify_ssa
- | TODO_verify_stmts /* todo_flags_finish */
-};
+ if (!IS_EMPTY_STMT (stmt))
+ {
+ code = TREE_CODE (stmt);
+ if (code != MODIFY_EXPR && code != PHI_NODE)
+ val.lattice_val = VARYING;
+ }
+ }
+ return val;
+}
/* Get the constant value associated with variable VAR. */
{
value *val;
-#if defined ENABLE_CHECKING
- if (TREE_CODE (var) != SSA_NAME)
- abort ();
-#endif
+ gcc_assert (TREE_CODE (var) == SSA_NAME);
val = &value_vector[SSA_NAME_VERSION (var)];
if (val->lattice_val == UNINITIALIZED)
}
-/* Simulate the execution of BLOCK. Evaluate the statement associated
- with each variable reference inside the block. */
+/* Set the lattice value for variable VAR to VAL. Return true if VAL
+ is different from VAR's previous value. */
+
+static bool
+set_lattice_value (tree var, value val)
+{
+ value *old = get_value (var);
+
+ if (val.lattice_val == UNDEFINED)
+ {
+ /* CONSTANT->UNDEFINED is never a valid state transition. */
+ gcc_assert (old->lattice_val != CONSTANT);
+
+ /* UNKNOWN_VAL->UNDEFINED is never a valid state transition. */
+ gcc_assert (old->lattice_val != UNKNOWN_VAL);
+
+ /* VARYING->UNDEFINED is generally not a valid state transition,
+ except for values which are initialized to VARYING. */
+ gcc_assert (old->lattice_val != VARYING
+ || get_default_value (var).lattice_val == VARYING);
+ }
+ else if (val.lattice_val == CONSTANT)
+ /* VARYING -> CONSTANT is an invalid state transition, except
+ for objects which start off in a VARYING state. */
+ gcc_assert (old->lattice_val != VARYING
+ || get_default_value (var).lattice_val == VARYING);
+
+ /* If the constant for VAR has changed, then this VAR is really varying. */
+ if (old->lattice_val == CONSTANT
+ && val.lattice_val == CONSTANT
+ && !simple_cst_equal (old->const_val, val.const_val))
+ {
+ val.lattice_val = VARYING;
+ val.const_val = NULL_TREE;
+ }
+
+ if (old->lattice_val != val.lattice_val)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_lattice_value (dump_file, "Lattice value changed to ", val);
+ fprintf (dump_file, ". Adding definition to SSA edges.\n");
+ }
+
+ *old = val;
+ return true;
+ }
+
+ return false;
+}
+
+
+/* Set the lattice value for the variable VAR to VARYING. */
static void
-simulate_block (basic_block block)
+def_to_varying (tree var)
{
- tree phi;
+ value val;
+ val.lattice_val = VARYING;
+ val.const_val = NULL_TREE;
+ set_lattice_value (var, val);
+}
- /* There is nothing to do for the exit block. */
- if (block == EXIT_BLOCK_PTR)
- return;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nSimulating block %d\n", block->index);
+/* Return the likely latticevalue for STMT.
+
+ If STMT has no operands, then return CONSTANT.
+
+ Else if any operands of STMT are undefined, then return UNDEFINED.
+
+ Else if any operands of STMT are constants, then return CONSTANT.
+
+ Else return VARYING. */
+
+static latticevalue
+likely_value (tree stmt)
+{
+ vuse_optype vuses;
+ int found_constant = 0;
+ stmt_ann_t ann;
+ tree use;
+ ssa_op_iter iter;
+
+ /* If the statement makes aliased loads or has volatile operands, it
+ won't fold to a constant value. */
+ ann = stmt_ann (stmt);
+ if (ann->makes_aliased_loads || ann->has_volatile_ops)
+ return VARYING;
- /* Always simulate PHI nodes, even if we have simulated this block
- before. */
- for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
- visit_phi_node (phi);
+ /* A CALL_EXPR is assumed to be varying. This may be overly conservative,
+ in the presence of const and pure calls. */
+ if (get_call_expr_in (stmt) != NULL_TREE)
+ return VARYING;
+
+ get_stmt_operands (stmt);
+
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ value *val = get_value (use);
+
+ if (val->lattice_val == UNDEFINED)
+ return UNDEFINED;
- /* If this is the first time we've simulated this block, then we
- must simulate each of its statements. */
- if (!TEST_BIT (executable_blocks, block->index))
+ if (val->lattice_val == CONSTANT)
+ found_constant = 1;
+ }
+
+ vuses = VUSE_OPS (ann);
+
+ if (NUM_VUSES (vuses))
{
- block_stmt_iterator j;
- unsigned int normal_edge_count;
- edge e, normal_edge;
-
- /* Note that we have simulated this block. */
- SET_BIT (executable_blocks, block->index);
-
- for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
- visit_stmt (bsi_stmt (j));
-
- /* We can not predict when abnormal edges will be executed, so
- once a block is considered executable, we consider any
- outgoing abnormal edges as executable.
-
- At the same time, if this block has only one successor that is
- reached by non-abnormal edges, then add that successor to the
- worklist. */
- normal_edge_count = 0;
- normal_edge = NULL;
- for (e = block->succ; e; e = e->succ_next)
+ tree vuse = VUSE_OP (vuses, 0);
+ value *val = get_value (vuse);
+
+ if (val->lattice_val == UNKNOWN_VAL)
+ return UNKNOWN_VAL;
+
+ /* There should be no VUSE operands that are UNDEFINED. */
+ gcc_assert (val->lattice_val != UNDEFINED);
+
+ if (val->lattice_val == CONSTANT)
+ found_constant = 1;
+ }
+
+ return ((found_constant || (!USE_OPS (ann) && !vuses)) ? CONSTANT : VARYING);
+}
+
+
+/* Function indicating whether we ought to include information for VAR
+ when calculating immediate uses. */
+
+static bool
+need_imm_uses_for (tree var)
+{
+ return get_value (var)->lattice_val != VARYING;
+}
+
+
+/* Initialize local data structures for CCP. */
+
+static void
+ccp_initialize (void)
+{
+ basic_block bb;
+ sbitmap is_may_def;
+
+ value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
+ memset (value_vector, 0, num_ssa_names * sizeof (value));
+
+ /* Set of SSA_NAMEs that are defined by a V_MAY_DEF. */
+ is_may_def = sbitmap_alloc (num_ssa_names);
+ sbitmap_zero (is_may_def);
+
+ /* Initialize simulation flags for PHI nodes and statements. */
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator i;
+
+ /* Mark all V_MAY_DEF operands VARYING. */
+ for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
- if (e->flags & EDGE_ABNORMAL)
+ bool is_varying = false;
+ tree stmt = bsi_stmt (i);
+ ssa_op_iter iter;
+ tree def;
+
+ get_stmt_operands (stmt);
+
+ /* Get the default value for each DEF and V_MUST_DEF. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter,
+ (SSA_OP_DEF | SSA_OP_VMUSTDEF))
{
- add_control_edge (e);
+ if (get_value (def)->lattice_val == VARYING)
+ is_varying = true;
}
- else
+
+ /* Mark all V_MAY_DEF operands VARYING. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
+ {
+ get_value (def)->lattice_val = VARYING;
+ SET_BIT (is_may_def, SSA_NAME_VERSION (def));
+ }
+
+ /* Statements other than MODIFY_EXPR, COND_EXPR and
+ SWITCH_EXPR are not interesting for constant propagation.
+ Mark them VARYING. */
+ if (TREE_CODE (stmt) != MODIFY_EXPR
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ is_varying = true;
+
+ DONT_SIMULATE_AGAIN (stmt) = is_varying;
+ }
+ }
+
+ /* Now process PHI nodes. */
+ FOR_EACH_BB (bb)
+ {
+ tree phi, var;
+ int x;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ value *val = get_value (PHI_RESULT (phi));
+
+ for (x = 0; x < PHI_NUM_ARGS (phi); x++)
{
- normal_edge_count++;
- normal_edge = e;
+ var = PHI_ARG_DEF (phi, x);
+
+ /* If one argument has a V_MAY_DEF, the result is
+ VARYING. */
+ if (TREE_CODE (var) == SSA_NAME)
+ {
+ if (TEST_BIT (is_may_def, SSA_NAME_VERSION (var)))
+ {
+ val->lattice_val = VARYING;
+ SET_BIT (is_may_def, SSA_NAME_VERSION (PHI_RESULT (phi)));
+ break;
+ }
+ }
}
- }
- if (normal_edge_count == 1)
- add_control_edge (normal_edge);
+ DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
+ }
}
+
+ sbitmap_free (is_may_def);
+
+ /* Compute immediate uses for variables we care about. */
+ compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
}
-/* Follow the def-use edges for statement DEF_STMT and simulate all the
- statements reached by it. */
+/* Replace USE references in statement STMT with their immediate reaching
+ definition. Return true if at least one reference was replaced. If
+ REPLACED_ADDRESSES_P is given, it will be set to true if an address
+ constant was replaced. */
-static void
-simulate_stmt (tree use_stmt)
+static bool
+replace_uses_in (tree stmt, bool *replaced_addresses_p)
{
- basic_block use_bb = bb_for_stmt (use_stmt);
+ bool replaced = false;
+ use_operand_p use;
+ ssa_op_iter iter;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
- print_generic_stmt (dump_file, use_stmt, dump_flags);
- }
+ if (replaced_addresses_p)
+ *replaced_addresses_p = false;
+
+ get_stmt_operands (stmt);
- if (TREE_CODE (use_stmt) == PHI_NODE)
+ FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
- /* PHI nodes are always visited, regardless of whether or not the
- destination block is executable. */
- visit_phi_node (use_stmt);
+ tree tuse = USE_FROM_PTR (use);
+ value *val = get_value (tuse);
+
+ if (val->lattice_val != CONSTANT)
+ continue;
+
+ if (TREE_CODE (stmt) == ASM_EXPR
+ && !may_propagate_copy_into_asm (tuse))
+ continue;
+
+ SET_USE (use, val->const_val);
+
+ replaced = true;
+ if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
+ *replaced_addresses_p = true;
}
- else if (TEST_BIT (executable_blocks, use_bb->index))
+
+ return replaced;
+}
+
+
+/* Replace the VUSE references in statement STMT with its immediate reaching
+ definition. Return true if the reference was replaced. If
+ REPLACED_ADDRESSES_P is given, it will be set to true if an address
+ constant was replaced. */
+
+static bool
+replace_vuse_in (tree stmt, bool *replaced_addresses_p)
+{
+ bool replaced = false;
+ vuse_optype vuses;
+ use_operand_p vuse;
+ value *val;
+
+ if (replaced_addresses_p)
+ *replaced_addresses_p = false;
+
+ get_stmt_operands (stmt);
+
+ vuses = STMT_VUSE_OPS (stmt);
+
+ if (NUM_VUSES (vuses) != 1)
+ return false;
+
+ vuse = VUSE_OP_PTR (vuses, 0);
+ val = get_value (USE_FROM_PTR (vuse));
+
+ if (val->lattice_val == CONSTANT
+ && TREE_CODE (stmt) == MODIFY_EXPR
+ && DECL_P (TREE_OPERAND (stmt, 1))
+ && TREE_OPERAND (stmt, 1) == SSA_NAME_VAR (USE_FROM_PTR (vuse)))
{
- /* Otherwise, visit the statement containing the use reached by
- DEF, only if the destination block is marked executable. */
- visit_stmt (use_stmt);
+ TREE_OPERAND (stmt, 1) = val->const_val;
+ replaced = true;
+ if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (vuse)))
+ && replaced_addresses_p)
+ *replaced_addresses_p = true;
}
+
+ return replaced;
}
substitute_and_fold (void)
{
basic_block bb;
+ unsigned int i;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
- if (replace_uses_in (stmt, &replaced_address))
+ if (replace_uses_in (stmt, &replaced_address)
+ || replace_vuse_in (stmt, &replaced_address))
{
bool changed = fold_stmt (bsi_stmt_ptr (i));
stmt = bsi_stmt(i);
- modify_stmt (stmt);
+
/* If we folded a builtin function, we'll likely
need to rename VDEFs. */
if (replaced_address || changed)
- {
- mark_new_vars_to_rename (stmt, vars_to_rename);
- if (maybe_clean_eh_stmt (stmt))
- tree_purge_dead_eh_edges (bb);
- }
+ mark_new_vars_to_rename (stmt, vars_to_rename);
+
+ /* If we cleaned up EH information from the statement,
+ remove EH edges. */
+ if (maybe_clean_eh_stmt (stmt))
+ tree_purge_dead_eh_edges (bb);
+
+ modify_stmt (stmt);
}
if (dump_file && (dump_flags & TDF_DETAILS))
}
}
}
-}
-
-
-/* Loop through the PHI_NODE's parameters for BLOCK and compare their
- lattice values to determine PHI_NODE's lattice value. The value of a
- PHI node is determined calling cp_lattice_meet() with all the arguments
- of the PHI node that are incoming via executable edges. */
-
-static void
-visit_phi_node (tree phi)
-{
- bool short_circuit = 0;
- value phi_val, *curr_val;
- int i;
-
- /* If the PHI node has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (phi))
- return;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nVisiting PHI node: ");
- print_generic_expr (dump_file, phi, dump_flags);
- }
- curr_val = get_value (PHI_RESULT (phi));
- switch (curr_val->lattice_val)
+ /* And transfer what we learned from VALUE_VECTOR into the
+ SSA_NAMEs themselves. This probably isn't terribly important
+ since we probably constant propagated the values to their
+ use sites above. */
+ for (i = 0; i < num_ssa_names; i++)
{
- case VARYING:
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n Shortcircuit. Default of VARYING.");
- short_circuit = 1;
- break;
+ tree name = ssa_name (i);
+ value *value;
- case CONSTANT:
- phi_val = *curr_val;
- break;
-
- case UNDEFINED:
- case UNINITIALIZED:
- phi_val.lattice_val = UNDEFINED;
- phi_val.const_val = NULL_TREE;
- break;
-
- default:
- abort ();
- }
+ if (!name)
+ continue;
- /* If the variable is volatile or the variable is never referenced in a
- real operand, then consider the PHI node VARYING. */
- if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
- {
- phi_val.lattice_val = VARYING;
- phi_val.const_val = NULL;
+ value = get_value (name);
+ if (value->lattice_val == CONSTANT
+ && is_gimple_reg (name)
+ && is_gimple_min_invariant (value->const_val))
+ SSA_NAME_VALUE (name) = value->const_val;
}
- else
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- {
- /* Compute the meet operator over all the PHI arguments. */
- edge e = PHI_ARG_EDGE (phi, i);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "\n Argument #%d (%d -> %d %sexecutable)\n",
- i, e->src->index, e->dest->index,
- (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
- }
-
- /* If the incoming edge is executable, Compute the meet operator for
- the existing value of the PHI node and the current PHI argument. */
- if (e->flags & EDGE_EXECUTABLE)
- {
- tree rdef = PHI_ARG_DEF (phi, i);
- value *rdef_val, val;
-
- if (is_gimple_min_invariant (rdef))
- {
- val.lattice_val = CONSTANT;
- val.const_val = rdef;
- rdef_val = &val;
- }
- else
- rdef_val = get_value (rdef);
-
- phi_val = cp_lattice_meet (phi_val, *rdef_val);
+}
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\t");
- print_generic_expr (dump_file, rdef, dump_flags);
- dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
- fprintf (dump_file, "\n");
- }
- if (phi_val.lattice_val == VARYING)
- break;
- }
- }
+/* Free allocated storage. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_lattice_value (dump_file, "\n PHI node value: ", phi_val);
- fprintf (dump_file, "\n\n");
- }
+static void
+ccp_finalize (void)
+{
+ /* Perform substitutions based on the known constant values. */
+ substitute_and_fold ();
- set_lattice_value (PHI_RESULT (phi), phi_val);
- if (phi_val.lattice_val == VARYING)
- DONT_SIMULATE_AGAIN (phi) = 1;
+ free (value_vector);
}
+
/* Compute the meet operator between VAL1 and VAL2:
- any M UNDEFINED = any
- any M VARYING = VARYING
- Ci M Cj = Ci if (i == j)
- Ci M Cj = VARYING if (i != j) */
+ any M UNDEFINED = any
+ any M VARYING = VARYING
+ any M UNKNOWN_VAL = UNKNOWN_VAL
+ Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j) */
static value
-cp_lattice_meet (value val1, value val2)
+ccp_lattice_meet (value val1, value val2)
{
value result;
return result;
}
+ /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
+ if (val1.lattice_val == UNKNOWN_VAL
+ || val2.lattice_val == UNKNOWN_VAL)
+ {
+ result.lattice_val = UNKNOWN_VAL;
+ result.const_val = NULL_TREE;
+ return result;
+ }
+
/* Ci M Cj = Ci if (i == j)
Ci M Cj = VARYING if (i != j) */
if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
}
-/* Evaluate statement STMT. If the statement produces an output value and
- its evaluation changes the lattice value of its output, do the following:
-
- - If the statement is an assignment, add all the SSA edges starting at
- this definition.
-
- - If the statement is a conditional branch:
- . If the statement evaluates to non-constant, add all edges to
- worklist.
- . If the statement is constant, add the edge executed as the
- result of the branch. */
+/* Loop through the PHI_NODE's parameters for BLOCK and compare their
+ lattice values to determine PHI_NODE's lattice value. The value of a
+ PHI node is determined calling ccp_lattice_meet() with all the arguments
+ of the PHI node that are incoming via executable edges. */
-static void
-visit_stmt (tree stmt)
+static enum ssa_prop_result
+ccp_visit_phi_node (tree phi)
{
- size_t i;
- stmt_ann_t ann;
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
-
- /* If the statement has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (stmt))
- return;
+ value new_val, *old_val;
+ int i;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "\nVisiting statement: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
-
- ann = stmt_ann (stmt);
-
- /* If this statement is already in the worklist then "cancel" it. The
- reevaluation implied by the worklist entry will produce the same
- value we generate here and thus reevaluating it again from the
- worklist is pointless. */
- if (ann->in_ccp_worklist)
- ann->in_ccp_worklist = 0;
-
- /* Now examine the statement. If the statement is an assignment that
- produces a single output value, evaluate its RHS to see if the lattice
- value of its output has changed. */
- if (TREE_CODE (stmt) == MODIFY_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
- visit_assignment (stmt);
-
- /* Definitions made by statements other than assignments to SSA_NAMEs
- represent unknown modifications to their outputs. Mark them VARYING. */
- else if (NUM_DEFS (defs = DEF_OPS (ann)) != 0)
- {
- DONT_SIMULATE_AGAIN (stmt) = 1;
- for (i = 0; i < NUM_DEFS (defs); i++)
- {
- tree def = DEF_OP (defs, i);
- def_to_varying (def);
- }
+ fprintf (dump_file, "\nVisiting PHI node: ");
+ print_generic_expr (dump_file, phi, dump_flags);
}
- /* If STMT is a conditional branch, see if we can determine which branch
- will be taken. */
- else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
- visit_cond_stmt (stmt);
-
- /* Any other kind of statement is not interesting for constant
- propagation and, therefore, not worth simulating. */
- else
+ old_val = get_value (PHI_RESULT (phi));
+ switch (old_val->lattice_val)
{
- DONT_SIMULATE_AGAIN (stmt) = 1;
-
- /* If STMT is a computed goto, then mark all the output edges
- executable. */
- if (computed_goto_p (stmt))
- add_outgoing_control_edges (bb_for_stmt (stmt));
- }
-
- /* Mark all V_MAY_DEF operands VARYING. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- def_to_varying (V_MAY_DEF_RESULT (v_may_defs, i));
-
- /* Mark all V_MUST_DEF operands VARYING. */
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
- def_to_varying (V_MUST_DEF_OP (v_must_defs, i));
-}
-
+ case VARYING:
+ return SSA_PROP_NOT_INTERESTING;
-/* Visit the assignment statement STMT. Set the value of its LHS to the
- value computed by the RHS. */
+ case CONSTANT:
+ new_val = *old_val;
+ break;
-static void
-visit_assignment (tree stmt)
-{
- value val;
- tree lhs, rhs;
+ case UNKNOWN_VAL:
+ /* To avoid the default value of UNKNOWN_VAL overriding
+ that of its possible constant arguments, temporarily
+ set the PHI node's default lattice value to be
+ UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and
+ the new value is UNDEFINED, then we prevent the invalid
+ transition by not calling set_lattice_value. */
+ new_val.lattice_val = UNDEFINED;
+ new_val.const_val = NULL_TREE;
+ break;
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
+ case UNDEFINED:
+ case UNINITIALIZED:
+ new_val.lattice_val = UNDEFINED;
+ new_val.const_val = NULL_TREE;
+ break;
- if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
- {
- /* Volatile variables are always VARYING. */
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
- }
- else if (TREE_CODE (rhs) == SSA_NAME)
- {
- /* For a simple copy operation, we copy the lattice values. */
- value *nval = get_value (rhs);
- val = *nval;
- }
- else
- {
- /* Evaluate the statement. */
- val = evaluate_stmt (stmt);
+ default:
+ gcc_unreachable ();
}
- /* FIXME: Hack. If this was a definition of a bitfield, we need to widen
- the constant value into the type of the destination variable. This
- should not be necessary if GCC represented bitfields properly. */
- {
- tree lhs = TREE_OPERAND (stmt, 0);
- if (val.lattice_val == CONSTANT
- && TREE_CODE (lhs) == COMPONENT_REF
- && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
- {
- tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
-
- if (w && is_gimple_min_invariant (w))
- val.const_val = w;
- else
- {
- val.lattice_val = VARYING;
- val.const_val = NULL;
- }
- }
- }
-
- /* Set the lattice value of the statement's output. */
- set_lattice_value (lhs, val);
- if (val.lattice_val == VARYING)
- DONT_SIMULATE_AGAIN (stmt) = 1;
-}
-
-
-/* Visit the conditional statement STMT. If it evaluates to a constant value,
- mark outgoing edges appropriately. */
-
-static void
-visit_cond_stmt (tree stmt)
-{
- edge e;
- value val;
- basic_block block;
-
- block = bb_for_stmt (stmt);
- val = evaluate_stmt (stmt);
-
- /* Find which edge out of the conditional block will be taken and add it
- to the worklist. If no single edge can be determined statically, add
- all outgoing edges from BLOCK. */
- e = find_taken_edge (block, val.const_val);
- if (e)
- add_control_edge (e);
- else
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
- DONT_SIMULATE_AGAIN (stmt) = 1;
- add_outgoing_control_edges (block);
- }
-}
-
+ /* Compute the meet operator over all the PHI arguments. */
+ edge e = PHI_ARG_EDGE (phi, i);
-/* Add all the edges coming out of BB to the control flow worklist. */
-
-static void
-add_outgoing_control_edges (basic_block bb)
-{
- edge e;
-
- for (e = bb->succ; e; e = e->succ_next)
- add_control_edge (e);
-}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "\n Argument #%d (%d -> %d %sexecutable)\n",
+ i, e->src->index, e->dest->index,
+ (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
+ }
+ /* If the incoming edge is executable, Compute the meet operator for
+ the existing value of the PHI node and the current PHI argument. */
+ if (e->flags & EDGE_EXECUTABLE)
+ {
+ tree rdef = PHI_ARG_DEF (phi, i);
+ value *rdef_val, val;
-/* Add edge E to the control flow worklist. */
+ if (is_gimple_min_invariant (rdef))
+ {
+ val.lattice_val = CONSTANT;
+ val.const_val = rdef;
+ rdef_val = &val;
+ }
+ else
+ rdef_val = get_value (rdef);
-static void
-add_control_edge (edge e)
-{
- basic_block bb = e->dest;
- if (bb == EXIT_BLOCK_PTR)
- return;
+ new_val = ccp_lattice_meet (new_val, *rdef_val);
- /* If the edge had already been executed, skip it. */
- if (e->flags & EDGE_EXECUTABLE)
- return;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\t");
+ print_generic_expr (dump_file, rdef, dump_flags);
+ dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
+ fprintf (dump_file, "\n");
+ }
- e->flags |= EDGE_EXECUTABLE;
+ if (new_val.lattice_val == VARYING)
+ break;
+ }
+ }
- /* If the block is already in the list, we're done. */
- if (TEST_BIT (bb_in_list, bb->index))
- return;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
+ fprintf (dump_file, "\n\n");
+ }
- cfg_blocks_add (bb);
+ /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
+ if (old_val->lattice_val == UNKNOWN_VAL
+ && new_val.lattice_val == UNDEFINED)
+ return SSA_PROP_NOT_INTERESTING;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
- e->src->index, e->dest->index);
+ /* Otherwise, make the transition to the new value. */
+ if (set_lattice_value (PHI_RESULT (phi), new_val))
+ {
+ if (new_val.lattice_val == VARYING)
+ return SSA_PROP_VARYING;
+ else
+ return SSA_PROP_INTERESTING;
+ }
+ else
+ return SSA_PROP_NOT_INTERESTING;
}
-/* CCP specific front-end to the non-destructive constant folding routines.
+/* CCP specific front-end to the non-destructive constant folding
+ routines.
Attempt to simplify the RHS of STMT knowing that one or more
operands are constants.
{
tree rhs = get_rhs (stmt);
enum tree_code code = TREE_CODE (rhs);
- int kind = TREE_CODE_CLASS (code);
+ enum tree_code_class kind = TREE_CODE_CLASS (code);
tree retval = NULL_TREE;
+ vuse_optype vuses;
+
+ vuses = STMT_VUSE_OPS (stmt);
/* If the RHS is just a variable, then that variable must now have
a constant value that we can return directly. */
if (TREE_CODE (rhs) == SSA_NAME)
return get_value (rhs)->const_val;
+ else if (DECL_P (rhs)
+ && NUM_VUSES (vuses) == 1
+ && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
+ return get_value (VUSE_OP (vuses, 0))->const_val;
/* Unary operators. Note that we know the single operand must
be a constant. So this should almost always return a
simplified RHS. */
- if (kind == '1')
+ if (kind == tcc_unary)
{
/* Handle unary operators which can appear in GIMPLE form. */
tree op0 = TREE_OPERAND (rhs, 0);
op0 = get_value (op0)->const_val;
}
- retval = nondestructive_fold_unary_to_constant (code,
- TREE_TYPE (rhs),
- op0);
+ retval = fold_unary_to_constant (code, TREE_TYPE (rhs), op0);
/* If we folded, but did not create an invariant, then we can not
use this expression. */
/* Binary and comparison operators. We know one or both of the
operands are constants. */
- else if (kind == '2'
- || kind == '<'
+ else if (kind == tcc_binary
+ || kind == tcc_comparison
|| code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR
|| code == TRUTH_XOR_EXPR)
op1 = val->const_val;
}
- retval = nondestructive_fold_binary_to_constant (code,
- TREE_TYPE (rhs),
- op0, op1);
+ retval = fold_binary_to_constant (code, TREE_TYPE (rhs), op0, op1);
/* If we folded, but did not create an invariant, then we can not
use this expression. */
else
{
/* The statement produced a nonconstant value. If the statement
- had undefined operands, then the result of the statement should
- be undefined. Else the result of the statement is VARYING. */
+ had undefined or virtual operands, then the result of the
+ statement should be undefined or virtual respectively.
+ Else the result of the statement is VARYING. */
val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
+ val.lattice_val = (likelyvalue == UNKNOWN_VAL
+ ? UNKNOWN_VAL : val.lattice_val);
val.const_val = NULL_TREE;
}
}
-/* Debugging dumps. */
-
-static void
-dump_lattice_value (FILE *outf, const char *prefix, value val)
-{
- switch (val.lattice_val)
- {
- case UNDEFINED:
- fprintf (outf, "%sUNDEFINED", prefix);
- break;
- case VARYING:
- fprintf (outf, "%sVARYING", prefix);
- break;
- case CONSTANT:
- fprintf (outf, "%sCONSTANT ", prefix);
- print_generic_expr (outf, val.const_val, dump_flags);
- break;
- default:
- abort ();
- }
-}
-
-/* Given a constant value VAL for bitfield FIELD, and a destination
- variable VAR, return VAL appropriately widened to fit into VAR. If
- FIELD is wider than HOST_WIDE_INT, NULL is returned. */
-
-tree
-widen_bitfield (tree val, tree field, tree var)
-{
- unsigned HOST_WIDE_INT var_size, field_size;
- tree wide_val;
- unsigned HOST_WIDE_INT mask;
- unsigned int i;
-
- /* We can only do this if the size of the type and field and VAL are
- all constants representable in HOST_WIDE_INT. */
- if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
- || !host_integerp (DECL_SIZE (field), 1)
- || !host_integerp (val, 0))
- return NULL_TREE;
-
- var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
- field_size = tree_low_cst (DECL_SIZE (field), 1);
-
- /* Give up if either the bitfield or the variable are too wide. */
- if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
- return NULL_TREE;
-
-#if defined ENABLE_CHECKING
- if (var_size < field_size)
- abort ();
-#endif
-
- /* If the sign bit of the value is not set or the field's type is unsigned,
- just mask off the high order bits of the value. */
- if (DECL_UNSIGNED (field)
- || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
- {
- /* Zero extension. Build a mask with the lower 'field_size' bits
- set and a BIT_AND_EXPR node to clear the high order bits of
- the value. */
- for (i = 0, mask = 0; i < field_size; i++)
- mask |= ((HOST_WIDE_INT) 1) << i;
-
- wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
- fold_convert (TREE_TYPE (var), build_int_2 (mask, 0)));
- }
- else
- {
- /* Sign extension. Create a mask with the upper 'field_size'
- bits set and a BIT_IOR_EXPR to set the high order bits of the
- value. */
- for (i = 0, mask = 0; i < (var_size - field_size); i++)
- mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
-
- wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
- fold_convert (TREE_TYPE (var), build_int_2 (mask, 0)));
- }
-
- return fold (wide_val);
-}
-
-
-/* Function indicating whether we ought to include information for 'var'
- when calculating immediate uses. */
-
-static bool
-need_imm_uses_for (tree var)
-{
- return get_value (var)->lattice_val != VARYING;
-}
-
-
-/* Initialize local data structures and worklists for CCP. */
+/* Visit the assignment statement STMT. Set the value of its LHS to the
+ value computed by the RHS and store LHS in *OUTPUT_P. */
-static void
-initialize (void)
+static enum ssa_prop_result
+visit_assignment (tree stmt, tree *output_p)
{
- edge e;
- basic_block bb;
- sbitmap virtual_var;
-
- /* Worklists of SSA edges. */
- VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges");
- VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges");
-
- executable_blocks = sbitmap_alloc (last_basic_block);
- sbitmap_zero (executable_blocks);
-
- bb_in_list = sbitmap_alloc (last_basic_block);
- sbitmap_zero (bb_in_list);
+ value val;
+ tree lhs, rhs;
+ vuse_optype vuses;
+ v_must_def_optype v_must_defs;
- value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
- memset (value_vector, 0, num_ssa_names * sizeof (value));
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
+ vuses = STMT_VUSE_OPS (stmt);
+ v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
- /* 1 if ssa variable is used in a virtual variable context. */
- virtual_var = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (virtual_var);
+ gcc_assert (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0);
+ gcc_assert (NUM_V_MUST_DEFS (v_must_defs) == 1
+ || TREE_CODE (lhs) == SSA_NAME);
- /* Initialize default values and simulation flags for PHI nodes, statements
- and edges. */
- FOR_EACH_BB (bb)
+ /* We require the SSA version number of the lhs for the value_vector.
+ Make sure we have it. */
+ if (TREE_CODE (lhs) != SSA_NAME)
{
- block_stmt_iterator i;
- tree stmt;
- stmt_ann_t ann;
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
- size_t x;
- int vary;
-
- /* Get the default value for each definition. */
- for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
- {
- vary = 0;
- stmt = bsi_stmt (i);
- get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
- defs = DEF_OPS (ann);
- for (x = 0; x < NUM_DEFS (defs); x++)
- {
- tree def = DEF_OP (defs, x);
- if (get_value (def)->lattice_val == VARYING)
- vary = 1;
- }
- DONT_SIMULATE_AGAIN (stmt) = vary;
-
- /* Mark all V_MAY_DEF operands VARYING. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++)
- {
- tree res = V_MAY_DEF_RESULT (v_may_defs, x);
- get_value (res)->lattice_val = VARYING;
- SET_BIT (virtual_var, SSA_NAME_VERSION (res));
- }
-
- /* Mark all V_MUST_DEF operands VARYING. */
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
- {
- tree v_must_def = V_MUST_DEF_OP (v_must_defs, x);
- get_value (v_must_def)->lattice_val = VARYING;
- SET_BIT (virtual_var, SSA_NAME_VERSION (v_must_def));
- }
- }
-
- for (e = bb->succ; e; e = e->succ_next)
- e->flags &= ~EDGE_EXECUTABLE;
+ /* If we make it here, then stmt only has one definition:
+ a V_MUST_DEF. */
+ lhs = V_MUST_DEF_RESULT (v_must_defs, 0);
}
- /* Now process PHI nodes. */
- FOR_EACH_BB (bb)
+ if (TREE_CODE (rhs) == SSA_NAME)
{
- tree phi, var;
- int x;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- value *val;
- val = get_value (PHI_RESULT (phi));
- if (val->lattice_val != VARYING)
- {
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
- {
- var = PHI_ARG_DEF (phi, x);
- /* If one argument is virtual, the result is virtual, and
- therefore varying. */
- if (TREE_CODE (var) == SSA_NAME)
- {
- if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var)))
- {
- val->lattice_val = VARYING;
- SET_BIT (virtual_var,
- SSA_NAME_VERSION (PHI_RESULT (phi)));
- break;
- }
- }
- }
- }
- DONT_SIMULATE_AGAIN (phi) = ((val->lattice_val == VARYING) ? 1 : 0);
- }
+ /* For a simple copy operation, we copy the lattice values. */
+ value *nval = get_value (rhs);
+ val = *nval;
}
-
- sbitmap_free (virtual_var);
- /* Compute immediate uses for variables we care about. */
- compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- dump_immediate_uses (dump_file);
-
- VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
-
- /* Seed the algorithm by adding the successors of the entry block to the
- edge worklist. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ else if (DECL_P (rhs)
+ && NUM_VUSES (vuses) == 1
+ && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
{
- if (e->dest != EXIT_BLOCK_PTR)
- {
- e->flags |= EDGE_EXECUTABLE;
- cfg_blocks_add (e->dest);
- }
+ /* Same as above, but the rhs is not a gimple register and yet
+ has a known VUSE. */
+ value *nval = get_value (VUSE_OP (vuses, 0));
+ val = *nval;
}
-}
-
-
-/* Free allocated storage. */
-
-static void
-finalize (void)
-{
- ssa_edges = NULL;
- varying_ssa_edges = NULL;
- cfg_blocks = NULL;
- free (value_vector);
- sbitmap_free (bb_in_list);
- sbitmap_free (executable_blocks);
- free_df ();
-}
-
-/* Is the block worklist empty. */
-
-static inline bool
-cfg_blocks_empty_p (void)
-{
- return (cfg_blocks_num == 0);
-}
-
-/* Add a basic block to the worklist. */
+ else
+ /* Evaluate the statement. */
+ val = evaluate_stmt (stmt);
-static void
-cfg_blocks_add (basic_block bb)
-{
- if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
- return;
+ /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant
+ value to be a VIEW_CONVERT_EXPR of the old constant value. This is
+ valid because a VIEW_CONVERT_EXPR is valid everywhere an operand of
+ aggregate type is valid.
- if (TEST_BIT (bb_in_list, bb->index))
- return;
+ ??? Also, if this was a definition of a bitfield, we need to widen
+ the constant value into the type of the destination variable. This
+ should not be necessary if GCC represented bitfields properly. */
+ {
+ tree orig_lhs = TREE_OPERAND (stmt, 0);
- if (cfg_blocks_empty_p ())
+ if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR
+ && val.lattice_val == CONSTANT)
{
- cfg_blocks_tail = cfg_blocks_head = 0;
- cfg_blocks_num = 1;
+ val.const_val = build1 (VIEW_CONVERT_EXPR,
+ TREE_TYPE (TREE_OPERAND (orig_lhs, 0)),
+ val.const_val);
+ orig_lhs = TREE_OPERAND (orig_lhs, 1);
}
- else
+
+ if (val.lattice_val == CONSTANT
+ && TREE_CODE (orig_lhs) == COMPONENT_REF
+ && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1)))
{
- cfg_blocks_num++;
- if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
+ tree w = widen_bitfield (val.const_val, TREE_OPERAND (orig_lhs, 1),
+ orig_lhs);
+
+ if (w && is_gimple_min_invariant (w))
+ val.const_val = w;
+ else
{
- /* We have to grow the array now. Adjust to queue to occupy the
- full space of the original array. */
- cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
- cfg_blocks_head = 0;
- VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
+ val.lattice_val = VARYING;
+ val.const_val = NULL;
}
- else
- cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
}
- VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
- SET_BIT (bb_in_list, bb->index);
-}
-
-/* Remove a block from the worklist. */
-
-static basic_block
-cfg_blocks_get (void)
-{
- basic_block bb;
-
- bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
-
-#ifdef ENABLE_CHECKING
- if (cfg_blocks_empty_p () || !bb)
- abort ();
-#endif
-
- cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
- --cfg_blocks_num;
- RESET_BIT (bb_in_list, bb->index);
-
- return bb;
-}
+ }
-/* We have just defined a new value for VAR. Add all immediate uses
- of VAR to the ssa_edges or varying_ssa_edges worklist. */
-static void
-add_var_to_ssa_edges_worklist (tree var, value val)
-{
- tree stmt = SSA_NAME_DEF_STMT (var);
- dataflow_t df = get_immediate_uses (stmt);
- int num_uses = num_immediate_uses (df);
- int i;
+ /* If LHS is not a gimple register, then it cannot take on an
+ UNDEFINED value. */
+ if (!is_gimple_reg (SSA_NAME_VAR (lhs))
+ && val.lattice_val == UNDEFINED)
+ val.lattice_val = UNKNOWN_VAL;
- for (i = 0; i < num_uses; i++)
+ /* Set the lattice value of the statement's output. */
+ if (set_lattice_value (lhs, val))
{
- tree use = immediate_use (df, i);
-
- if (!DONT_SIMULATE_AGAIN (use))
- {
- stmt_ann_t ann = stmt_ann (use);
- if (ann->in_ccp_worklist == 0)
- {
- ann->in_ccp_worklist = 1;
- if (val.lattice_val == VARYING)
- VARRAY_PUSH_TREE (varying_ssa_edges, use);
- else
- VARRAY_PUSH_TREE (ssa_edges, use);
- }
- }
+ *output_p = lhs;
+ if (val.lattice_val == VARYING)
+ return SSA_PROP_VARYING;
+ else
+ return SSA_PROP_INTERESTING;
}
+ else
+ return SSA_PROP_NOT_INTERESTING;
}
-/* Set the lattice value for the variable VAR to VARYING. */
-static void
-def_to_varying (tree var)
+/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
+ if it can determine which edge will be taken. Otherwise, return
+ SSA_PROP_VARYING. */
+
+static enum ssa_prop_result
+visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
value val;
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
- set_lattice_value (var, val);
-}
+ basic_block block;
-/* Set the lattice value for variable VAR to VAL. */
+ block = bb_for_stmt (stmt);
+ val = evaluate_stmt (stmt);
-static void
-set_lattice_value (tree var, value val)
-{
- value *old = get_value (var);
+ /* Find which edge out of the conditional block will be taken and add it
+ to the worklist. If no single edge can be determined statically,
+ return SSA_PROP_VARYING to feed all the outgoing edges to the
+ propagation engine. */
+ *taken_edge_p = val.const_val ? find_taken_edge (block, val.const_val) : 0;
+ if (*taken_edge_p)
+ return SSA_PROP_INTERESTING;
+ else
+ return SSA_PROP_VARYING;
+}
-#ifdef ENABLE_CHECKING
- if (val.lattice_val == UNDEFINED)
- {
- /* CONSTANT->UNDEFINED is never a valid state transition. */
- if (old->lattice_val == CONSTANT)
- abort ();
- /* VARYING->UNDEFINED is generally not a valid state transition,
- except for values which are initialized to VARYING. */
- if (old->lattice_val == VARYING
- && get_default_value (var).lattice_val != VARYING)
- abort ();
- }
- else if (val.lattice_val == CONSTANT)
- {
- /* VARYING -> CONSTANT is an invalid state transition, except
- for objects which start off in a VARYING state. */
- if (old->lattice_val == VARYING
- && get_default_value (var).lattice_val != VARYING)
- abort ();
- }
-#endif
+/* Evaluate statement STMT. If the statement produces an output value and
+ its evaluation changes the lattice value of its output, return
+ SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
+ output value.
+
+ If STMT is a conditional branch and we can determine its truth
+ value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
+ value, return SSA_PROP_VARYING. */
- /* If the constant for VAR has changed, then this VAR is really varying. */
- if (old->lattice_val == CONSTANT && val.lattice_val == CONSTANT
- && !simple_cst_equal (old->const_val, val.const_val))
+static enum ssa_prop_result
+ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
+{
+ stmt_ann_t ann;
+ v_may_def_optype v_may_defs;
+ v_must_def_optype v_must_defs;
+ tree def;
+ ssa_op_iter iter;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
+ fprintf (dump_file, "\nVisiting statement: ");
+ print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\n");
}
- if (old->lattice_val != val.lattice_val)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_lattice_value (dump_file,
- "Lattice value changed to ", val);
- fprintf (dump_file, ". Adding definition to SSA edges.\n");
- }
+ ann = stmt_ann (stmt);
- add_var_to_ssa_edges_worklist (var, val);
- *old = val;
+ v_must_defs = V_MUST_DEF_OPS (ann);
+ v_may_defs = V_MAY_DEF_OPS (ann);
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && NUM_V_MAY_DEFS (v_may_defs) == 0
+ && (NUM_V_MUST_DEFS (v_must_defs) == 1
+ || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
+ {
+ /* If the statement is an assignment that produces a single
+ output value, evaluate its RHS to see if the lattice value of
+ its output has changed. */
+ return visit_assignment (stmt, output_p);
+ }
+ else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
+ {
+ /* If STMT is a conditional branch, see if we can determine
+ which branch will be taken. */
+ return visit_cond_stmt (stmt, taken_edge_p);
}
-}
-/* Replace USE references in statement STMT with their immediate reaching
- definition. Return true if at least one reference was replaced. If
- REPLACED_ADDRESSES_P is given, it will be set to true if an address
- constant was replaced. */
+ /* Any other kind of statement is not interesting for constant
+ propagation and, therefore, not worth simulating. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
-static bool
-replace_uses_in (tree stmt, bool *replaced_addresses_p)
-{
- bool replaced = false;
- use_optype uses;
- size_t i;
+ /* Definitions made by statements other than assignments to
+ SSA_NAMEs represent unknown modifications to their outputs.
+ Mark them VARYING. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+ def_to_varying (def);
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
+ /* Mark all V_MAY_DEF operands VARYING. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
+ def_to_varying (def);
- get_stmt_operands (stmt);
+ return SSA_PROP_VARYING;
+}
- uses = STMT_USE_OPS (stmt);
- for (i = 0; i < NUM_USES (uses); i++)
- {
- use_operand_p use = USE_OP_PTR (uses, i);
- value *val = get_value (USE_FROM_PTR (use));
- if (val->lattice_val == CONSTANT)
- {
- SET_USE (use, val->const_val);
- replaced = true;
- if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use)))
- && replaced_addresses_p)
- *replaced_addresses_p = true;
- }
- }
+/* Main entry point for SSA Conditional Constant Propagation.
- return replaced;
+ [ DESCRIBE MAIN ALGORITHM HERE ] */
+
+static void
+execute_ssa_ccp (void)
+{
+ ccp_initialize ();
+ ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
+ ccp_finalize ();
}
-/* Return the likely latticevalue for STMT.
- If STMT has no operands, then return CONSTANT.
+static bool
+gate_ccp (void)
+{
+ return flag_tree_ccp != 0;
+}
- Else if any operands of STMT are undefined, then return UNDEFINED.
- Else if any operands of STMT are constants, then return CONSTANT.
+struct tree_opt_pass pass_ccp =
+{
+ "ccp", /* name */
+ gate_ccp, /* gate */
+ execute_ssa_ccp, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_CCP, /* tv_id */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_cleanup_cfg | TODO_dump_func | TODO_rename_vars
+ | TODO_ggc_collect | TODO_verify_ssa
+ | TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
+};
- Else return VARYING. */
-static latticevalue
-likely_value (tree stmt)
+/* Given a constant value VAL for bitfield FIELD, and a destination
+ variable VAR, return VAL appropriately widened to fit into VAR. If
+ FIELD is wider than HOST_WIDE_INT, NULL is returned. */
+
+tree
+widen_bitfield (tree val, tree field, tree var)
{
- use_optype uses;
- size_t i;
- int found_constant = 0;
- stmt_ann_t ann;
+ unsigned HOST_WIDE_INT var_size, field_size;
+ tree wide_val;
+ unsigned HOST_WIDE_INT mask;
+ unsigned int i;
- /* If the statement makes aliased loads or has volatile operands, it
- won't fold to a constant value. */
- ann = stmt_ann (stmt);
- if (ann->makes_aliased_loads || ann->has_volatile_ops)
- return VARYING;
+ /* We can only do this if the size of the type and field and VAL are
+ all constants representable in HOST_WIDE_INT. */
+ if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
+ || !host_integerp (DECL_SIZE (field), 1)
+ || !host_integerp (val, 0))
+ return NULL_TREE;
- /* A CALL_EXPR is assumed to be varying. This may be overly conservative,
- in the presence of const and pure calls. */
- if (get_call_expr_in (stmt) != NULL_TREE)
- return VARYING;
+ var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
+ field_size = tree_low_cst (DECL_SIZE (field), 1);
- get_stmt_operands (stmt);
+ /* Give up if either the bitfield or the variable are too wide. */
+ if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
+ return NULL_TREE;
+
+ gcc_assert (var_size >= field_size);
- uses = USE_OPS (ann);
- for (i = 0; i < NUM_USES (uses); i++)
+ /* If the sign bit of the value is not set or the field's type is unsigned,
+ just mask off the high order bits of the value. */
+ if (DECL_UNSIGNED (field)
+ || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
{
- tree use = USE_OP (uses, i);
- value *val = get_value (use);
+ /* Zero extension. Build a mask with the lower 'field_size' bits
+ set and a BIT_AND_EXPR node to clear the high order bits of
+ the value. */
+ for (i = 0, mask = 0; i < field_size; i++)
+ mask |= ((HOST_WIDE_INT) 1) << i;
- if (val->lattice_val == UNDEFINED)
- return UNDEFINED;
+ wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
+ fold_convert (TREE_TYPE (var),
+ build_int_cst (NULL_TREE, mask)));
+ }
+ else
+ {
+ /* Sign extension. Create a mask with the upper 'field_size'
+ bits set and a BIT_IOR_EXPR to set the high order bits of the
+ value. */
+ for (i = 0, mask = 0; i < (var_size - field_size); i++)
+ mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
- if (val->lattice_val == CONSTANT)
- found_constant = 1;
+ wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
+ fold_convert (TREE_TYPE (var),
+ build_int_cst (NULL_TREE, mask)));
}
- return ((found_constant || !uses) ? CONSTANT : VARYING);
+ return fold (wide_val);
}
+
/* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X].
BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE
is the desired result type. */
|| lrem || hrem)
return NULL_TREE;
- idx = build_int_2_wide (lquo, hquo);
+ idx = build_int_cst_wide (NULL_TREE, lquo, hquo);
}
/* Assume the low bound is zero. If there is a domain type, get the
return build (ARRAY_REF, orig_type, base, idx, min_idx,
size_int (tree_low_cst (elt_size, 1)
- / (TYPE_ALIGN (elt_type) / BITS_PER_UNIT)));
+ / (TYPE_ALIGN_UNIT (elt_type))));
}
+
/* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X.
BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE
is the desired result type. */
maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
tree orig_type, bool base_is_ptr)
{
- tree f, t, field_type, tail_array_field;
+ tree f, t, field_type, tail_array_field, field_offset;
if (TREE_CODE (record_type) != RECORD_TYPE
&& TREE_CODE (record_type) != UNION_TYPE
continue;
if (DECL_BIT_FIELD (f))
continue;
- if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST)
+
+ field_offset = byte_position (f);
+ if (TREE_CODE (field_offset) != INTEGER_CST)
continue;
/* ??? Java creates "interesting" fields for representing base classes.
tail_array_field = NULL_TREE;
/* Check to see if this offset overlaps with the field. */
- cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), offset);
+ cmp = tree_int_cst_compare (field_offset, offset);
if (cmp > 0)
continue;
orig_type, false);
}
+
/* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET).
Return the simplified expression, or NULL if nothing could be done. */
/* Strip the ADDR_EXPR. */
base = TREE_OPERAND (base, 0);
+ /* Fold away CONST_DECL to its value, if the type is scalar. */
+ if (TREE_CODE (base) == CONST_DECL
+ && is_gimple_min_invariant (DECL_INITIAL (base)))
+ return DECL_INITIAL (base);
+
/* Try folding *(&B+O) to B[X]. */
t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
if (t)
return NULL_TREE;
}
+
/* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR.
A quaint feature extant in our address arithmetic is that there
return t;
}
+
/* Subroutine of fold_stmt called via walk_tree. We perform several
simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
return NULL_TREE;
}
-/* Fold the statement pointed by STMT_P. In some cases, this function may
- replace the whole statement with a new one. Returns true iff folding
- makes any changes. */
-
-bool
-fold_stmt (tree *stmt_p)
-{
- tree rhs, result, stmt;
- bool changed = false;
-
- stmt = *stmt_p;
-
- /* If we replaced constants and the statement makes pointer dereferences,
- then we may need to fold instances of *&VAR into VAR, etc. */
- if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
- {
- *stmt_p
- = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
- NULL);
- return true;
- }
-
- rhs = get_rhs (stmt);
- if (!rhs)
- return changed;
- result = NULL_TREE;
-
- if (TREE_CODE (rhs) == CALL_EXPR)
- {
- tree callee;
-
- /* Check for builtins that CCP can handle using information not
- available in the generic fold routines. */
- callee = get_callee_fndecl (rhs);
- if (callee && DECL_BUILT_IN (callee))
- result = ccp_fold_builtin (stmt, rhs);
- else
- {
- /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
- here are when we've propagated the address of a decl into the
- object slot. */
- /* ??? Should perhaps do this in fold proper. However, doing it
- there requires that we create a new CALL_EXPR, and that requires
- copying EH region info to the new node. Easier to just do it
- here where we can just smash the call operand. */
- callee = TREE_OPERAND (rhs, 0);
- if (TREE_CODE (callee) == OBJ_TYPE_REF
- && lang_hooks.fold_obj_type_ref
- && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
- && DECL_P (TREE_OPERAND (OBJ_TYPE_REF_OBJECT (callee), 0)))
- {
- tree t;
-
- /* ??? Caution: Broken ADDR_EXPR semantics means that
- looking at the type of the operand of the addr_expr
- can yield an array type. See silly exception in
- check_pointer_types_r. */
-
- t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
- t = lang_hooks.fold_obj_type_ref (callee, t);
- if (t)
- {
- TREE_OPERAND (rhs, 0) = t;
- changed = true;
- }
- }
- }
- }
-
- /* If we couldn't fold the RHS, hand over to the generic fold routines. */
- if (result == NULL_TREE)
- result = fold (rhs);
-
- /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
- may have been added by fold, and "useless" type conversions that might
- now be apparent due to propagation. */
- STRIP_USELESS_TYPE_CONVERSION (result);
-
- if (result != rhs)
- changed |= set_rhs (stmt_p, result);
-
- return changed;
-}
-
-/* Get the main expression from statement STMT. */
-
-static tree
-get_rhs (tree stmt)
-{
- enum tree_code code = TREE_CODE (stmt);
-
- switch (code)
- {
- case RETURN_EXPR:
- stmt = TREE_OPERAND (stmt, 0);
- if (stmt)
- return get_rhs (stmt);
- else
- return NULL;
-
- case MODIFY_EXPR:
- return TREE_OPERAND (stmt, 1);
-
- case COND_EXPR:
- return COND_EXPR_COND (stmt);
- case SWITCH_EXPR:
- return SWITCH_COND (stmt);
- case GOTO_EXPR:
- return GOTO_DESTINATION (stmt);
- case LABEL_EXPR:
- return LABEL_EXPR_LABEL (stmt);
-
- default:
- return stmt;
- }
-}
-
-/* Set the main expression of *STMT_P to EXPR. */
+/* Return the string length of ARG in LENGTH. If ARG is an SSA name variable,
+ follow its use-def chains. If LENGTH is not NULL and its value is not
+ equal to the length we determine, or if we are unable to determine the
+ length, return false. VISITED is a bitmap of visited variables. */
static bool
-set_rhs (tree *stmt_p, tree expr)
+get_strlen (tree arg, tree *length, bitmap visited)
{
- tree stmt = *stmt_p, op;
- enum tree_code code = TREE_CODE (expr);
- stmt_ann_t ann;
-
- /* Verify the constant folded result is valid gimple. */
- if (TREE_CODE_CLASS (code) == '2')
- {
- if (!is_gimple_val (TREE_OPERAND (expr, 0))
- || !is_gimple_val (TREE_OPERAND (expr, 1)))
- return false;
- }
- else if (TREE_CODE_CLASS (code) == '1')
+ tree var, def_stmt, val;
+
+ if (TREE_CODE (arg) != SSA_NAME)
{
- if (!is_gimple_val (TREE_OPERAND (expr, 0)))
+ val = c_strlen (arg, 1);
+ if (!val)
return false;
- }
-
- switch (TREE_CODE (stmt))
- {
- case RETURN_EXPR:
- op = TREE_OPERAND (stmt, 0);
- if (TREE_CODE (op) != MODIFY_EXPR)
- {
- TREE_OPERAND (stmt, 0) = expr;
- break;
- }
- stmt = op;
- /* FALLTHRU */
-
- case MODIFY_EXPR:
- TREE_OPERAND (stmt, 1) = expr;
- break;
-
- case COND_EXPR:
- COND_EXPR_COND (stmt) = expr;
- break;
- case SWITCH_EXPR:
- SWITCH_COND (stmt) = expr;
- break;
- case GOTO_EXPR:
- GOTO_DESTINATION (stmt) = expr;
- break;
- case LABEL_EXPR:
- LABEL_EXPR_LABEL (stmt) = expr;
- break;
-
- 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)->common.ann = (tree_ann_t) ann;
-
- if (TREE_SIDE_EFFECTS (expr))
- {
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
- size_t i;
-
- /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
- replacement. */
- defs = DEF_OPS (ann);
- for (i = 0; i < NUM_DEFS (defs); i++)
- {
- tree var = DEF_OP (defs, i);
- if (TREE_CODE (var) == SSA_NAME)
- SSA_NAME_DEF_STMT (var) = *stmt_p;
- }
- v_may_defs = V_MAY_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
- {
- tree var = V_MAY_DEF_RESULT (v_may_defs, i);
- if (TREE_CODE (var) == SSA_NAME)
- SSA_NAME_DEF_STMT (var) = *stmt_p;
- }
-
- v_must_defs = V_MUST_DEF_OPS (ann);
- for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
- {
- tree var = V_MUST_DEF_OP (v_must_defs, i);
- if (TREE_CODE (var) == SSA_NAME)
- SSA_NAME_DEF_STMT (var) = *stmt_p;
- }
- }
- break;
+ if (*length && simple_cst_equal (val, *length) != 1)
+ return false;
+
+ *length = val;
+ return true;
}
- return true;
-}
+ /* If we were already here, break the infinite cycle. */
+ if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
+ return true;
+ bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
+ var = arg;
+ def_stmt = SSA_NAME_DEF_STMT (var);
-/* Return a default value for variable VAR using the following rules:
+ switch (TREE_CODE (def_stmt))
+ {
+ case MODIFY_EXPR:
+ {
+ tree len, rhs;
+
+ /* The RHS of the statement defining VAR must either have a
+ constant length or come from another SSA_NAME with a constant
+ length. */
+ rhs = TREE_OPERAND (def_stmt, 1);
+ STRIP_NOPS (rhs);
+ if (TREE_CODE (rhs) == SSA_NAME)
+ return get_strlen (rhs, length, visited);
- 1- Global and static variables are considered VARYING, unless they are
- declared const.
+ /* See if the RHS is a constant length. */
+ len = c_strlen (rhs, 1);
+ if (len)
+ {
+ if (*length && simple_cst_equal (len, *length) != 1)
+ return false;
- 2- Function arguments are considered VARYING.
+ *length = len;
+ return true;
+ }
- 3- Any other value is considered UNDEFINED. This is useful when
- considering PHI nodes. PHI arguments that are undefined do not
- change the constant value of the PHI node, which allows for more
- constants to be propagated. */
+ break;
+ }
-static value
-get_default_value (tree var)
-{
- value val;
- tree sym;
+ case PHI_NODE:
+ {
+ /* All the arguments of the PHI node must have the same constant
+ length. */
+ int i;
- if (TREE_CODE (var) == SSA_NAME)
- sym = SSA_NAME_VAR (var);
- else
- {
-#ifdef ENABLE_CHECKING
- if (!DECL_P (var))
- abort ();
-#endif
- sym = var;
- }
+ for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
+ {
+ tree arg = PHI_ARG_DEF (def_stmt, i);
- val.lattice_val = UNDEFINED;
- val.const_val = NULL_TREE;
+ /* If this PHI has itself as an argument, we cannot
+ determine the string length of this argument. However,
+ if we can find a constant string length for the other
+ PHI args then we can still be sure that this is a
+ constant string length. So be optimistic and just
+ continue with the next argument. */
+ if (arg == PHI_RESULT (def_stmt))
+ continue;
- if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
- {
- /* Function arguments and volatile variables are considered VARYING. */
- val.lattice_val = VARYING;
- }
- else if (decl_function_context (sym) != current_function_decl
- || TREE_STATIC (sym))
- {
- /* Globals and static variables are considered VARYING, unless they
- are declared 'const'. */
- val.lattice_val = VARYING;
+ if (!get_strlen (arg, length, visited))
+ return false;
+ }
- if (TREE_READONLY (sym)
- && DECL_INITIAL (sym)
- && is_gimple_min_invariant (DECL_INITIAL (sym)))
- {
- val.lattice_val = CONSTANT;
- val.const_val = DECL_INITIAL (sym);
+ return true;
}
- }
- else
- {
- enum tree_code code;
- tree stmt = SSA_NAME_DEF_STMT (var);
- if (!IS_EMPTY_STMT (stmt))
- {
- code = TREE_CODE (stmt);
- if (code != MODIFY_EXPR && code != PHI_NODE)
- val.lattice_val = VARYING;
- }
+ default:
+ break;
}
- return val;
+
+ return false;
}
break;
default:
- abort ();
+ gcc_unreachable ();
}
if (result && ignore)
}
-/* Return the string length of ARG in LENGTH. If ARG is an SSA name variable,
- follow its use-def chains. If LENGTH is not NULL and its value is not
- equal to the length we determine, or if we are unable to determine the
- length, return false. VISITED is a bitmap of visited variables. */
+/* Fold the statement pointed by STMT_P. In some cases, this function may
+ replace the whole statement with a new one. Returns true iff folding
+ makes any changes. */
-static bool
-get_strlen (tree arg, tree *length, bitmap visited)
+bool
+fold_stmt (tree *stmt_p)
{
- tree var, def_stmt, val;
-
- if (TREE_CODE (arg) != SSA_NAME)
- {
- val = c_strlen (arg, 1);
- if (!val)
- return false;
+ tree rhs, result, stmt;
+ bool changed = false;
- if (*length && simple_cst_equal (val, *length) != 1)
- return false;
+ stmt = *stmt_p;
- *length = val;
+ /* If we replaced constants and the statement makes pointer dereferences,
+ then we may need to fold instances of *&VAR into VAR, etc. */
+ if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
+ {
+ *stmt_p
+ = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
+ NULL);
return true;
}
- /* If we were already here, break the infinite cycle. */
- if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
- return true;
- bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
-
- var = arg;
- def_stmt = SSA_NAME_DEF_STMT (var);
+ rhs = get_rhs (stmt);
+ if (!rhs)
+ return changed;
+ result = NULL_TREE;
- switch (TREE_CODE (def_stmt))
+ if (TREE_CODE (rhs) == CALL_EXPR)
{
- case MODIFY_EXPR:
- {
- tree len, rhs;
-
- /* The RHS of the statement defining VAR must either have a
- constant length or come from another SSA_NAME with a constant
- length. */
- rhs = TREE_OPERAND (def_stmt, 1);
- STRIP_NOPS (rhs);
- if (TREE_CODE (rhs) == SSA_NAME)
- return get_strlen (rhs, length, visited);
+ tree callee;
- /* See if the RHS is a constant length. */
- len = c_strlen (rhs, 1);
- if (len)
+ /* Check for builtins that CCP can handle using information not
+ available in the generic fold routines. */
+ callee = get_callee_fndecl (rhs);
+ if (callee && DECL_BUILT_IN (callee))
+ result = ccp_fold_builtin (stmt, rhs);
+ else
+ {
+ /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
+ here are when we've propagated the address of a decl into the
+ object slot. */
+ /* ??? Should perhaps do this in fold proper. However, doing it
+ there requires that we create a new CALL_EXPR, and that requires
+ copying EH region info to the new node. Easier to just do it
+ here where we can just smash the call operand. */
+ callee = TREE_OPERAND (rhs, 0);
+ if (TREE_CODE (callee) == OBJ_TYPE_REF
+ && lang_hooks.fold_obj_type_ref
+ && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
+ && DECL_P (TREE_OPERAND
+ (OBJ_TYPE_REF_OBJECT (callee), 0)))
{
- if (*length && simple_cst_equal (len, *length) != 1)
- return false;
+ tree t;
- *length = len;
- return true;
- }
+ /* ??? Caution: Broken ADDR_EXPR semantics means that
+ looking at the type of the operand of the addr_expr
+ can yield an array type. See silly exception in
+ check_pointer_types_r. */
- break;
+ t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
+ t = lang_hooks.fold_obj_type_ref (callee, t);
+ if (t)
+ {
+ TREE_OPERAND (rhs, 0) = t;
+ changed = true;
+ }
+ }
}
+ }
- case PHI_NODE:
- {
- /* All the arguments of the PHI node must have the same constant
- length. */
- int i;
+ /* If we couldn't fold the RHS, hand over to the generic fold routines. */
+ if (result == NULL_TREE)
+ result = fold (rhs);
- for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
- {
- tree arg = PHI_ARG_DEF (def_stmt, i);
+ /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
+ may have been added by fold, and "useless" type conversions that might
+ now be apparent due to propagation. */
+ STRIP_USELESS_TYPE_CONVERSION (result);
- /* If this PHI has itself as an argument, we cannot
- determine the string length of this argument. However,
- if we can find a constant string length for the other
- PHI args then we can still be sure that this is a
- constant string length. So be optimistic and just
- continue with the next argument. */
- if (arg == PHI_RESULT (def_stmt))
- continue;
+ if (result != rhs)
+ changed |= set_rhs (stmt_p, result);
- if (!get_strlen (arg, length, visited))
- return false;
- }
+ return changed;
+}
- return true;
- }
+\f
+/* Convert EXPR into a GIMPLE value suitable for substitution on the
+ RHS of an assignment. Insert the necessary statements before
+ iterator *SI_P. */
- default:
- break;
+static tree
+convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr)
+{
+ tree_stmt_iterator ti;
+ tree stmt = bsi_stmt (*si_p);
+ tree tmp, stmts = NULL;
+
+ push_gimplify_context ();
+ tmp = get_initialized_tmp_var (expr, &stmts, NULL);
+ pop_gimplify_context (NULL);
+
+ /* The replacement can expose previously unreferenced variables. */
+ for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti))
+ {
+ find_new_referenced_vars (tsi_stmt_ptr (ti));
+ mark_new_vars_to_rename (tsi_stmt (ti), vars_to_rename);
}
+ if (EXPR_HAS_LOCATION (stmt))
+ annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
- return false;
+ bsi_insert_before (si_p, stmts, BSI_SAME_STMT);
+
+ return tmp;
}
-\f
+
/* A simple pass that attempts to fold all builtin functions. This pass
is run after we've propagated as many constants as we can. */
static void
execute_fold_all_builtins (void)
{
+ bool cfg_changed = false;
basic_block bb;
FOR_EACH_BB (bb)
{
print_generic_stmt (dump_file, *stmtp, dump_flags);
}
- if (set_rhs (stmtp, result))
- modify_stmt (*stmtp);
+ if (!set_rhs (stmtp, result))
+ {
+ result = convert_to_gimple_builtin (&i, result);
+ if (result && !set_rhs (stmtp, result))
+ abort ();
+ }
+ modify_stmt (*stmtp);
+ if (maybe_clean_eh_stmt (*stmtp)
+ && tree_purge_dead_eh_edges (bb))
+ cfg_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
}
+
+ /* Delete unreachable blocks. */
+ if (cfg_changed)
+ cleanup_tree_cfg ();
}
+
struct tree_opt_pass pass_fold_builtins =
{
"fab", /* name */
NULL, /* next */
0, /* static_pass_number */
0, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
+ TODO_dump_func
+ | TODO_verify_ssa
+ | TODO_rename_vars, /* todo_flags_finish */
+ 0 /* letter */
};
-
-
-#include "gt-tree-ssa-ccp.h"
OSDN Git Service
