/* Conditional constant propagation pass for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
+ Free Software Foundation, Inc.
Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
-/* Conditional constant propagation.
+/* Conditional constant propagation (CCP) is based on the SSA
+ propagation engine (tree-ssa-propagate.c). Constant assignments of
+ the form VAR = CST are propagated from the assignments into uses of
+ VAR, which in turn may generate new constants. The simulation uses
+ a four level lattice to keep track of constant values associated
+ with SSA names. Given an SSA name V_i, it may take one of the
+ following values:
+
+ UNINITIALIZED -> This is the default starting value. V_i
+ has not been processed yet.
+
+ UNDEFINED -> V_i is a local variable whose definition
+ has not been processed yet. Therefore we
+ don't yet know if its value is a constant
+ or not.
+
+ CONSTANT -> V_i has been found to hold a constant
+ value C.
+
+ VARYING -> V_i cannot take a constant value, or if it
+ does, it is not possible to determine it
+ at compile time.
+
+ The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
+
+ 1- In ccp_visit_stmt, we are interested in assignments whose RHS
+ evaluates into a constant and conditional jumps whose predicate
+ evaluates into a boolean true or false. When an assignment of
+ the form V_i = CONST is found, V_i's lattice value is set to
+ CONSTANT and CONST is associated with it. This causes the
+ propagation engine to add all the SSA edges coming out the
+ assignment into the worklists, so that statements that use V_i
+ can be visited.
+
+ If the statement is a conditional with a constant predicate, we
+ mark the outgoing edges as executable or not executable
+ depending on the predicate's value. This is then used when
+ visiting PHI nodes to know when a PHI argument can be ignored.
+
+
+ 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
+ same constant C, then the LHS of the PHI is set to C. This
+ evaluation is known as the "meet operation". Since one of the
+ goals of this evaluation is to optimistically return constant
+ values as often as possible, it uses two main short cuts:
+
+ - If an argument is flowing in through a non-executable edge, it
+ is ignored. This is useful in cases like this:
+
+ if (PRED)
+ a_9 = 3;
+ else
+ a_10 = 100;
+ a_11 = PHI (a_9, a_10)
+
+ If PRED is known to always evaluate to false, then we can
+ assume that a_11 will always take its value from a_10, meaning
+ that instead of consider it VARYING (a_9 and a_10 have
+ different values), we can consider it CONSTANT 100.
+
+ - If an argument has an UNDEFINED value, then it does not affect
+ the outcome of the meet operation. If a variable V_i has an
+ UNDEFINED value, it means that either its defining statement
+ hasn't been visited yet or V_i has no defining statement, in
+ which case the original symbol 'V' is being used
+ uninitialized. Since 'V' is a local variable, the compiler
+ may assume any initial value for it.
+
+
+ After propagation, every variable V_i that ends up with a lattice
+ value of CONSTANT will have the associated constant value in the
+ array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
+ final substitution and folding.
+
+
+ Constant propagation in stores and loads (STORE-CCP)
+ ----------------------------------------------------
+
+ While CCP has all the logic to propagate constants in GIMPLE
+ registers, it is missing the ability to associate constants with
+ stores and loads (i.e., pointer dereferences, structures and
+ global/aliased variables). We don't keep loads and stores in
+ SSA, but we do build a factored use-def web for them (in the
+ virtual operands).
+
+ For instance, consider the following code fragment:
+
+ struct A a;
+ const int B = 42;
+
+ void foo (int i)
+ {
+ if (i > 10)
+ a.a = 42;
+ else
+ {
+ a.b = 21;
+ a.a = a.b + 21;
+ }
+
+ if (a.a != B)
+ never_executed ();
+ }
+
+ We should be able to deduce that the predicate 'a.a != B' is always
+ false. To achieve this, we associate constant values to the SSA
+ names in the V_MAY_DEF and V_MUST_DEF operands for each store.
+ Additionally, since we also glob partial loads/stores with the base
+ symbol, we also keep track of the memory reference where the
+ constant value was stored (in the MEM_REF field of PROP_VALUE_T).
+ For instance,
+
+ # a_5 = V_MAY_DEF <a_4>
+ a.a = 2;
+
+ # VUSE <a_5>
+ x_3 = a.b;
+
+ In the example above, CCP will associate value '2' with 'a_5', but
+ it would be wrong to replace the load from 'a.b' with '2', because
+ '2' had been stored into a.a.
+
+ To support STORE-CCP, it is necessary to add a new value to the
+ constant propagation lattice. When evaluating a load for a memory
+ reference we can no longer assume a value of UNDEFINED if we
+ haven't seen a preceding store to the same memory location.
+ Consider, for instance global variables:
+
+ int A;
+
+ foo (int i)
+ {
+ if (i_3 > 10)
+ A_4 = 3;
+ # A_5 = PHI (A_4, A_2);
+
+ # VUSE <A_5>
+ A.0_6 = A;
+
+ return A.0_6;
+ }
+
+ The value of A_2 cannot be assumed to be UNDEFINED, as it may have
+ been defined outside of foo. If we were to assume it UNDEFINED, we
+ would erroneously optimize the above into 'return 3;'. Therefore,
+ when doing STORE-CCP, we introduce a fifth lattice value
+ (UNKNOWN_VAL), which overrides any other value when computing the
+ meet operation in PHI nodes.
+
+ Though STORE-CCP is not too expensive, it does have to do more work
+ than regular CCP, so it is only enabled at -O2. Both regular CCP
+ and STORE-CCP use the exact same algorithm. The only distinction
+ is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is
+ set to true. This affects the evaluation of statements and PHI
+ nodes.
References:
#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. */
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
-{
- latticevalue lattice_val;
- tree const_val;
-} value;
-
-/* A bitmap to keep track of executable blocks in the CFG. */
-static sbitmap executable_blocks;
+} ccp_lattice_t;
-/* Array of control flow edges on the worklist. */
-static GTY(()) varray_type cfg_blocks = NULL;
+/* Array of propagated constant values. After propagation,
+ CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
+ the constant is held in an SSA name representing a memory store
+ (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will
+ contain the actual memory reference used to store (i.e., the LHS of
+ the assignment doing the store). */
+prop_value_t *const_val;
-static unsigned int cfg_blocks_num = 0;
-static int cfg_blocks_tail;
-static int cfg_blocks_head;
+/* True if we are also propagating constants in stores and loads. */
+static bool do_store_ccp;
-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 bool replace_vuse_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 constant propagation 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, prop_value_t val)
{
- /* Drain the entire worklist. */
- while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
- {
- /* 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);
- }
- }
-}
-
-/* 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 ();
-
- /* 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);
- }
-
- /* 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);
-
- /* Now process the SSA_EDGES worklist. */
- process_ssa_edge_worklist (&ssa_edges);
- }
-
- /* Now perform substitutions based on the known constant values. */
- substitute_and_fold ();
-
- /* Now cleanup any unreachable code. */
- cleanup_tree_cfg ();
-
- /* Free allocated memory. */
- finalize ();
-
- /* Debugging dumps. */
- if (dump_file && (dump_flags & TDF_DETAILS))
+ switch (val.lattice_val)
{
- dump_referenced_vars (dump_file);
- fprintf (dump_file, "\n\n");
+ case UNINITIALIZED:
+ fprintf (outf, "%sUNINITIALIZED", prefix);
+ break;
+ 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.value, dump_flags);
+ break;
+ default:
+ gcc_unreachable ();
}
}
-static bool
-gate_ccp (void)
-{
- return flag_tree_ccp != 0;
-}
-
-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 | PROP_alias, /* 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 */
-};
+/* Print lattice value VAL to stderr. */
-/* Get the constant value associated with variable VAR. */
+void debug_lattice_value (prop_value_t val);
-static value *
-get_value (tree var)
+void
+debug_lattice_value (prop_value_t val)
{
- value *val;
-
-#if defined ENABLE_CHECKING
- if (TREE_CODE (var) != SSA_NAME)
- abort ();
-#endif
-
- val = &value_vector[SSA_NAME_VERSION (var)];
- if (val->lattice_val == UNINITIALIZED)
- *val = get_default_value (var);
-
- return val;
+ dump_lattice_value (stderr, "", val);
+ fprintf (stderr, "\n");
}
-/* Simulate the execution of BLOCK. Evaluate the statement associated
- with each variable reference inside the block. */
-
-static void
-simulate_block (basic_block block)
-{
- tree phi;
-
- /* There is nothing to do for the exit block. */
- if (block == EXIT_BLOCK_PTR)
- return;
+/* Compute a default value for variable VAR and store it in the
+ CONST_VAL array. The following rules are used to get default
+ values:
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nSimulating block %d\n", block->index);
-
- /* 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);
+ 1- Global and static variables that are declared constant are
+ considered CONSTANT.
- /* 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))
- {
- 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)
- {
- if (e->flags & EDGE_ABNORMAL)
- {
- add_control_edge (e);
- }
- else
- {
- normal_edge_count++;
- normal_edge = e;
- }
- }
+ 2- 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.
- if (normal_edge_count == 1)
- add_control_edge (normal_edge);
- }
-}
+ 3- If SSA_NAME_VALUE is set and it is a constant, its value is
+ used.
+ 4- Variables defined by statements other than assignments and PHI
+ nodes are considered VARYING.
-/* Follow the def-use edges for statement DEF_STMT and simulate all the
- statements reached by it. */
+ 5- Variables that are not GIMPLE registers are considered
+ UNKNOWN_VAL, which is really a stronger version of UNDEFINED.
+ It's used to avoid the short circuit evaluation implied by
+ UNDEFINED in ccp_lattice_meet. */
-static void
-simulate_stmt (tree use_stmt)
+static prop_value_t
+get_default_value (tree var)
{
- basic_block use_bb = bb_for_stmt (use_stmt);
+ tree sym = SSA_NAME_VAR (var);
+ prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE };
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (!do_store_ccp && !is_gimple_reg (var))
{
- fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
- print_generic_stmt (dump_file, use_stmt, dump_flags);
+ /* Short circuit for regular CCP. We are not interested in any
+ non-register when DO_STORE_CCP is false. */
+ val.lattice_val = VARYING;
}
-
- if (TREE_CODE (use_stmt) == PHI_NODE)
+ else if (SSA_NAME_VALUE (var)
+ && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
{
- /* PHI nodes are always visited, regardless of whether or not the
- destination block is executable. */
- visit_phi_node (use_stmt);
+ val.lattice_val = CONSTANT;
+ val.value = SSA_NAME_VALUE (var);
}
- else if (TEST_BIT (executable_blocks, use_bb->index))
+ else if (TREE_STATIC (sym)
+ && TREE_READONLY (sym)
+ && DECL_INITIAL (sym)
+ && is_gimple_min_invariant (DECL_INITIAL (sym)))
{
- /* Otherwise, visit the statement containing the use reached by
- DEF, only if the destination block is marked executable. */
- visit_stmt (use_stmt);
+ /* Globals and static variables declared 'const' take their
+ initial value. */
+ val.lattice_val = CONSTANT;
+ val.value = DECL_INITIAL (sym);
+ val.mem_ref = sym;
}
-}
-
-
-/* Perform final substitution and folding. After this pass the program
- should still be in SSA form. */
-
-static void
-substitute_and_fold (void)
-{
- basic_block bb;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "\nSubstituing constants and folding statements\n\n");
-
- /* Substitute constants in every statement of every basic block. */
- FOR_EACH_BB (bb)
+ else
{
- block_stmt_iterator i;
- tree phi;
+ tree stmt = SSA_NAME_DEF_STMT (var);
- /* Propagate our known constants into PHI nodes. */
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ if (IS_EMPTY_STMT (stmt))
{
- int i;
-
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- {
- value *new_val;
- use_operand_p orig_p = PHI_ARG_DEF_PTR (phi, i);
- tree orig = USE_FROM_PTR (orig_p);
-
- if (! SSA_VAR_P (orig))
- break;
-
- new_val = get_value (orig);
- if (new_val->lattice_val == CONSTANT
- && may_propagate_copy (orig, new_val->const_val))
- SET_USE (orig_p, new_val->const_val);
- }
+ /* Variables defined by an empty statement are those used
+ before being initialized. If VAR is a local variable, we
+ can assume initially that it is UNDEFINED. If we are
+ doing STORE-CCP, function arguments and non-register
+ variables are initially UNKNOWN_VAL, because we cannot
+ discard the value incoming from outside of this function
+ (see ccp_lattice_meet for details). */
+ if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
+ val.lattice_val = UNDEFINED;
+ else if (do_store_ccp)
+ val.lattice_val = UNKNOWN_VAL;
+ else
+ val.lattice_val = VARYING;
}
-
- for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+ else if (TREE_CODE (stmt) == MODIFY_EXPR
+ || TREE_CODE (stmt) == PHI_NODE)
{
- bool replaced_address;
- tree stmt = bsi_stmt (i);
-
- /* Skip statements that have been folded already. */
- if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
- continue;
-
- /* Replace the statement with its folded version and mark it
- folded. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- }
-
- 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);
- }
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " with ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
+ /* Any other variable defined by an assignment or a PHI node
+ is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a
+ GIMPLE register). */
+ val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL;
+ }
+ else
+ {
+ /* Otherwise, VAR will never take on a constant value. */
+ val.lattice_val = VARYING;
}
}
+
+ return val;
}
-/* 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. */
+/* Get the constant value associated with variable VAR. If
+ MAY_USE_DEFAULT_P is true, call get_default_value on variables that
+ have the lattice value UNINITIALIZED. */
-static void
-visit_phi_node (tree phi)
+static prop_value_t *
+get_value (tree var, bool may_use_default_p)
{
- bool short_circuit = 0;
- value phi_val, *curr_val;
- int i;
+ prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
+ if (may_use_default_p && val->lattice_val == UNINITIALIZED)
+ *val = get_default_value (var);
- /* If the PHI node has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (phi))
- return;
+ return val;
+}
- 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)
+/* Set the value for variable VAR to NEW_VAL. Return true if the new
+ value is different from VAR's previous value. */
+
+static bool
+set_lattice_value (tree var, prop_value_t new_val)
+{
+ prop_value_t *old_val = get_value (var, false);
+
+ /* Lattice transitions must always be monotonically increasing in
+ value. We allow two exceptions:
+
+ 1- If *OLD_VAL and NEW_VAL are the same, return false to
+ inform the caller that this was a non-transition.
+
+ 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true),
+ allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a
+ special type of UNDEFINED state which prevents the short
+ circuit evaluation of PHI arguments (see ccp_visit_phi_node
+ and ccp_lattice_meet). */
+ gcc_assert (old_val->lattice_val <= new_val.lattice_val
+ || (old_val->lattice_val == new_val.lattice_val
+ && old_val->value == new_val.value
+ && old_val->mem_ref == new_val.mem_ref)
+ || (do_store_ccp
+ && old_val->lattice_val == CONSTANT
+ && new_val.lattice_val == UNKNOWN_VAL));
+
+ if (old_val->lattice_val != new_val.lattice_val)
{
- case VARYING:
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n Shortcircuit. Default of VARYING.");
- short_circuit = 1;
- break;
-
- case CONSTANT:
- phi_val = *curr_val;
- break;
-
- 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. At the same time, place something other
- than NULL_TREE in phi_val.const_val as a flag to
- check when setting a new state for this phi node to
- ensure that we avoid incorrect state transitions from
- UNKNOWN_VAL to UNDEFINED. */
- phi_val.lattice_val = UNDEFINED;
- phi_val.const_val = phi;
- break;
+ {
+ dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
+ fprintf (dump_file, ". %sdding SSA edges to worklist.\n",
+ new_val.lattice_val != UNDEFINED ? "A" : "Not a");
+ }
- case UNDEFINED:
- case UNINITIALIZED:
- phi_val.lattice_val = UNDEFINED;
- phi_val.const_val = NULL_TREE;
- break;
+ *old_val = new_val;
- default:
- abort ();
+ /* Transitions UNINITIALIZED -> UNDEFINED are never interesting
+ for propagation purposes. In these cases return false to
+ avoid doing useless work. */
+ return (new_val.lattice_val != UNDEFINED);
}
- /* 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;
- }
- 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);
+ return false;
+}
- 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;
+/* Return the likely CCP lattice value for STMT.
- if (is_gimple_min_invariant (rdef))
- {
- val.lattice_val = CONSTANT;
- val.const_val = rdef;
- rdef_val = &val;
- }
- else
- rdef_val = get_value (rdef);
+ If STMT has no operands, then return CONSTANT.
- phi_val = cp_lattice_meet (phi_val, *rdef_val);
+ Else if any operands of STMT are undefined, then return UNDEFINED.
- 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");
- }
+ Else if any operands of STMT are constants, then return CONSTANT.
- if (phi_val.lattice_val == VARYING)
- break;
- }
- }
+ Else return VARYING. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_lattice_value (dump_file, "\n PHI node value: ", phi_val);
- fprintf (dump_file, "\n\n");
- }
+static ccp_lattice_t
+likely_value (tree stmt)
+{
+ bool found_constant;
+ stmt_ann_t ann;
+ tree use;
+ ssa_op_iter iter;
- /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
- if (phi_val.lattice_val != UNDEFINED || phi_val.const_val == NULL_TREE)
- {
- set_lattice_value (PHI_RESULT (phi), phi_val);
- if (phi_val.lattice_val == VARYING)
- DONT_SIMULATE_AGAIN (phi) = 1;
- }
-}
+ ann = stmt_ann (stmt);
+ /* If the statement has volatile operands, it won't fold to a
+ constant value. */
+ if (ann->has_volatile_ops)
+ return VARYING;
-/* Compute the meet operator between VAL1 and VAL2:
+ /* If we are not doing store-ccp, statements with loads
+ and/or stores will never fold into a constant. */
+ if (!do_store_ccp
+ && (ann->makes_aliased_stores
+ || ann->makes_aliased_loads
+ || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
+ return VARYING;
- 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)
-{
- value result;
- /* any M UNDEFINED = any. */
- if (val1.lattice_val == UNDEFINED)
- return val2;
- else if (val2.lattice_val == UNDEFINED)
- return val1;
+ /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly
+ conservative, in the presence of const and pure calls. */
+ if (get_call_expr_in (stmt) != NULL_TREE)
+ return VARYING;
- /* any M VARYING = VARYING. */
- if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
- {
- result.lattice_val = VARYING;
- result.const_val = NULL_TREE;
- return result;
- }
+ /* Anything other than assignments and conditional jumps are not
+ interesting for CCP. */
+ if (TREE_CODE (stmt) != MODIFY_EXPR
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ return VARYING;
- /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
- if (val1.lattice_val == UNKNOWN_VAL
- || val2.lattice_val == UNKNOWN_VAL)
+ found_constant = false;
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
{
- result.lattice_val = UNKNOWN_VAL;
- result.const_val = NULL_TREE;
- return result;
- }
+ prop_value_t *val = get_value (use, true);
- /* 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)
- {
- result.lattice_val = CONSTANT;
- result.const_val = val1.const_val;
- }
- else
- {
- result.lattice_val = VARYING;
- result.const_val = NULL_TREE;
- }
+ if (val->lattice_val == VARYING)
+ return VARYING;
- return result;
-}
+ if (val->lattice_val == UNKNOWN_VAL)
+ {
+ /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */
+ gcc_assert (do_store_ccp);
+ return UNKNOWN_VAL;
+ }
+
+ if (val->lattice_val == CONSTANT)
+ found_constant = true;
+ }
+ if (found_constant
+ || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)
+ || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
+ return CONSTANT;
-/* Evaluate statement STMT. If the statement produces an output value and
- its evaluation changes the lattice value of its output, do the following:
+ return UNDEFINED;
+}
- - 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. */
+/* Initialize local data structures for CCP. */
static void
-visit_stmt (tree stmt)
+ccp_initialize (void)
{
- size_t i;
- stmt_ann_t ann;
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
+ basic_block bb;
- /* If the statement has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (stmt))
- return;
+ const_val = xmalloc (num_ssa_names * sizeof (*const_val));
+ memset (const_val, 0, num_ssa_names * sizeof (*const_val));
- if (dump_file && (dump_flags & TDF_DETAILS))
+ /* Initialize simulation flags for PHI nodes and statements. */
+ FOR_EACH_BB (bb)
{
- fprintf (dump_file, "\nVisiting statement: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
+ block_stmt_iterator i;
- ann = stmt_ann (stmt);
+ for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+ {
+ bool is_varying = false;
+ tree stmt = bsi_stmt (i);
+
+ if (likely_value (stmt) == VARYING)
+
+ {
+ tree def;
+ ssa_op_iter iter;
+
+ /* If the statement will not produce a constant, mark
+ all its outputs VARYING. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
+ get_value (def, false)->lattice_val = VARYING;
+
+ /* Never mark conditional jumps with DONT_SIMULATE_AGAIN,
+ otherwise the propagator will never add the outgoing
+ control edges. */
+ if (TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ is_varying = true;
+ }
+
+ DONT_SIMULATE_AGAIN (stmt) = is_varying;
+ }
+ }
- /* 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. */
- 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))
- 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)
+ /* Now process PHI nodes. */
+ FOR_EACH_BB (bb)
{
- DONT_SIMULATE_AGAIN (stmt) = 1;
- for (i = 0; i < NUM_DEFS (defs); i++)
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
- tree def = DEF_OP (defs, i);
- def_to_varying (def);
+ int i;
+ tree arg;
+ prop_value_t *val = get_value (PHI_RESULT (phi), false);
+
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ arg = PHI_ARG_DEF (phi, i);
+
+ if (TREE_CODE (arg) == SSA_NAME
+ && get_value (arg, false)->lattice_val == VARYING)
+ {
+ val->lattice_val = VARYING;
+ break;
+ }
+ }
+
+ DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
}
}
+}
- /* 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
- {
- DONT_SIMULATE_AGAIN (stmt) = 1;
+/* Do final substitution of propagated values, cleanup the flowgraph and
+ free allocated storage. */
- /* 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));
- }
+static void
+ccp_finalize (void)
+{
+ /* Perform substitutions based on the known constant values. */
+ substitute_and_fold (const_val);
- /* 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));
-
+ free (const_val);
}
-/* Visit the assignment statement STMT. Set the value of its LHS to the
- value computed by the RHS. */
+/* Compute the meet operator between *VAL1 and *VAL2. Store the result
+ in VAL1.
+
+ any M UNDEFINED = any
+ any M UNKNOWN_VAL = UNKNOWN_VAL
+ any M VARYING = VARYING
+ Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
+
+ Lattice values UNKNOWN_VAL and UNDEFINED are similar but have
+ different semantics at PHI nodes. Both values imply that we don't
+ know whether the variable is constant or not. However, UNKNOWN_VAL
+ values override all others. For instance, suppose that A is a
+ global variable:
+
+ +------+
+ | |
+ | / \
+ | / \
+ | | A_1 = 4
+ | \ /
+ | \ /
+ | A_3 = PHI (A_2, A_1)
+ | ... = A_3
+ | |
+ +----+
+
+ If the edge into A_2 is not executable, the first visit to A_3 will
+ yield the constant 4. But the second visit to A_3 will be with A_2
+ in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4
+ because A_2 may have been set in another function. If we had used
+ the lattice value UNDEFINED, we would have had wrongly concluded
+ that A_3 is 4. */
+
static void
-visit_assignment (tree stmt)
+ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
{
- value val;
- tree lhs, rhs;
- vuse_optype vuses;
- v_must_def_optype v_must_defs;
-
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
- vuses = STMT_VUSE_OPS (stmt);
- v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
-
-#if defined ENABLE_CHECKING
- if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
- || (NUM_V_MUST_DEFS (v_must_defs) != 1
- && TREE_CODE (lhs) != SSA_NAME))
- abort ();
-#endif
-
- /* We require the SSA version number of the lhs for the value_vector.
- Make sure we have it. */
- if (TREE_CODE (lhs) != SSA_NAME)
+ if (val1->lattice_val == UNDEFINED)
{
- /* If we make it here, then stmt only has one definition:
- a V_MUST_DEF. */
- lhs = V_MUST_DEF_OP (v_must_defs, 0);
+ /* UNDEFINED M any = any */
+ *val1 = *val2;
}
-
- if (TREE_CODE (rhs) == SSA_NAME)
+ else if (val2->lattice_val == UNDEFINED)
{
- /* For a simple copy operation, we copy the lattice values. */
- value *nval = get_value (rhs);
- val = *nval;
+ /* any M UNDEFINED = any
+ Nothing to do. VAL1 already contains the value we want. */
+ ;
}
- else if (DECL_P (rhs)
- && NUM_VUSES (vuses) == 1
- && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
+ else if (val1->lattice_val == UNKNOWN_VAL
+ || val2->lattice_val == UNKNOWN_VAL)
{
- /* 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;
+ /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */
+ gcc_assert (do_store_ccp);
+
+ /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
+ val1->lattice_val = UNKNOWN_VAL;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
}
- else
+ else if (val1->lattice_val == VARYING
+ || val2->lattice_val == VARYING)
{
- /* Evaluate the statement. */
- val = evaluate_stmt (stmt);
+ /* any M VARYING = VARYING. */
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
}
+ else if (val1->lattice_val == CONSTANT
+ && val2->lattice_val == CONSTANT
+ && simple_cst_equal (val1->value, val2->value) == 1
+ && (!do_store_ccp
+ || simple_cst_equal (val1->mem_ref, val2->mem_ref) == 1))
+ {
+ /* Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
- /* 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;
- }
- }
- }
-
- /* 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;
-
- /* 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);
+ If these two values come from memory stores, make sure that
+ they come from the same memory reference. */
+ val1->lattice_val = CONSTANT;
+ val1->value = val1->value;
+ val1->mem_ref = val1->mem_ref;
+ }
else
{
- DONT_SIMULATE_AGAIN (stmt) = 1;
- add_outgoing_control_edges (block);
+ /* Any other combination is VARYING. */
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
}
}
-/* Add all the edges coming out of BB to the control flow worklist. */
+/* 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
-add_outgoing_control_edges (basic_block bb)
+static enum ssa_prop_result
+ccp_visit_phi_node (tree phi)
{
- edge e;
+ int i;
+ prop_value_t *old_val, new_val;
- for (e = bb->succ; e; e = e->succ_next)
- add_control_edge (e);
-}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nVisiting PHI node: ");
+ print_generic_expr (dump_file, phi, dump_flags);
+ }
+ old_val = get_value (PHI_RESULT (phi), false);
+ switch (old_val->lattice_val)
+ {
+ case VARYING:
+ return SSA_PROP_VARYING;
-/* Add edge E to the control flow worklist. */
+ case CONSTANT:
+ new_val = *old_val;
+ break;
-static void
-add_control_edge (edge e)
-{
- basic_block bb = e->dest;
- if (bb == EXIT_BLOCK_PTR)
- return;
+ 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. */
+ gcc_assert (do_store_ccp);
+
+ /* FALLTHRU */
+
+ case UNDEFINED:
+ case UNINITIALIZED:
+ new_val.lattice_val = UNDEFINED;
+ new_val.value = NULL_TREE;
+ new_val.mem_ref = NULL_TREE;
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ /* Compute the meet operator over all the PHI arguments flowing
+ through executable edges. */
+ 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 arg = PHI_ARG_DEF (phi, i);
+ prop_value_t arg_val;
- /* If the edge had already been executed, skip it. */
- if (e->flags & EDGE_EXECUTABLE)
- return;
+ if (is_gimple_min_invariant (arg))
+ {
+ arg_val.lattice_val = CONSTANT;
+ arg_val.value = arg;
+ arg_val.mem_ref = NULL_TREE;
+ }
+ else
+ arg_val = *(get_value (arg, true));
- e->flags |= EDGE_EXECUTABLE;
+ ccp_lattice_meet (&new_val, &arg_val);
- /* 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))
+ {
+ fprintf (dump_file, "\t");
+ print_generic_expr (dump_file, arg, dump_flags);
+ dump_lattice_value (dump_file, "\tValue: ", arg_val);
+ fprintf (dump_file, "\n");
+ }
- cfg_blocks_add (bb);
+ if (new_val.lattice_val == VARYING)
+ break;
+ }
+ }
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);
+ {
+ dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
+ fprintf (dump_file, "\n\n");
+ }
+
+ /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
+ if (do_store_ccp
+ && old_val->lattice_val == UNKNOWN_VAL
+ && new_val.lattice_val == UNDEFINED)
+ return SSA_PROP_NOT_INTERESTING;
+
+ /* 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;
+ {
+ /* If the RHS is an SSA_NAME, return its known constant value,
+ if any. */
+ return get_value (rhs, true)->value;
+ }
+ else if (do_store_ccp && stmt_makes_single_load (stmt))
+ {
+ /* If the RHS is a memory load, see if the VUSEs associated with
+ it are a valid constant for that memory load. */
+ prop_value_t *val = get_value_loaded_by (stmt, const_val);
+ if (val && simple_cst_equal (val->mem_ref, rhs) == 1)
+ return val->value;
+ else
+ return NULL_TREE;
+ }
/* 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);
/* Simplify the operand down to a constant. */
if (TREE_CODE (op0) == SSA_NAME)
{
- value *val = get_value (op0);
+ prop_value_t *val = get_value (op0, true);
if (val->lattice_val == CONSTANT)
- op0 = get_value (op0)->const_val;
+ op0 = get_value (op0, true)->value;
}
- 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)
/* Simplify the operands down to constants when appropriate. */
if (TREE_CODE (op0) == SSA_NAME)
{
- value *val = get_value (op0);
+ prop_value_t *val = get_value (op0, true);
if (val->lattice_val == CONSTANT)
- op0 = val->const_val;
+ op0 = val->value;
}
if (TREE_CODE (op1) == SSA_NAME)
{
- value *val = get_value (op1);
+ prop_value_t *val = get_value (op1, true);
if (val->lattice_val == CONSTANT)
- op1 = val->const_val;
+ op1 = val->value;
}
- 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. */
== FUNCTION_DECL)
&& DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
{
- use_optype uses = STMT_USE_OPS (stmt);
- if (NUM_USES (uses) != 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
{
- tree *orig;
- size_t i;
+ tree *orig, var;
+ tree fndecl, arglist;
+ size_t i = 0;
+ ssa_op_iter iter;
+ use_operand_p var_p;
/* Preserve the original values of every operand. */
- orig = xmalloc (sizeof (tree) * NUM_USES (uses));
- for (i = 0; i < NUM_USES (uses); i++)
- orig[i] = USE_OP (uses, i);
+ orig = xmalloc (sizeof (tree) * NUM_SSA_OPERANDS (stmt, SSA_OP_USE));
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+ orig[i++] = var;
/* Substitute operands with their values and try to fold. */
- replace_uses_in (stmt, NULL);
- retval = fold_builtin (rhs, false);
+ replace_uses_in (stmt, NULL, const_val);
+ fndecl = get_callee_fndecl (rhs);
+ arglist = TREE_OPERAND (rhs, 1);
+ retval = fold_builtin (fndecl, arglist, false);
/* Restore operands to their original form. */
- for (i = 0; i < NUM_USES (uses); i++)
- SET_USE_OP (uses, i, orig[i]);
+ i = 0;
+ FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE)
+ SET_USE (var_p, orig[i++]);
free (orig);
}
}
/* Evaluate statement STMT. */
-static value
+static prop_value_t
evaluate_stmt (tree stmt)
{
- value val;
+ prop_value_t val;
tree simplified;
- latticevalue likelyvalue = likely_value (stmt);
+ ccp_lattice_t likelyvalue = likely_value (stmt);
+
+ val.mem_ref = NULL_TREE;
/* If the statement is likely to have a CONSTANT result, then try
to fold the statement to determine the constant value. */
{
/* The statement produced a constant value. */
val.lattice_val = CONSTANT;
- val.const_val = simplified;
+ val.value = simplified;
}
else
{
/* The statement produced a nonconstant value. If the statement
- 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;
+ had UNDEFINED operands, then the result of the statement
+ should be UNDEFINED. Otherwise, the statement is VARYING. */
+ val.lattice_val = (likelyvalue == UNDEFINED) ? UNDEFINED : VARYING;
+ val.value = NULL_TREE;
}
return val;
}
-/* 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 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:
- 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. */
+/* Visit the assignment statement STMT. Set the value of its LHS to the
+ value computed by the RHS and store LHS in *OUTPUT_P. If STMT
+ creates virtual definitions, set the value of each new name to that
+ of the RHS (if we can derive a constant out of the RHS). */
-tree
-widen_bitfield (tree val, tree field, tree var)
+static enum ssa_prop_result
+visit_assignment (tree stmt, tree *output_p)
{
- 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;
+ prop_value_t val;
+ tree lhs, rhs;
+ enum ssa_prop_result retval;
-#if defined ENABLE_CHECKING
- if (var_size < field_size)
- abort ();
-#endif
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
- /* 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))))
+ if (TREE_CODE (rhs) == SSA_NAME)
{
- /* 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)));
+ /* For a simple copy operation, we copy the lattice values. */
+ prop_value_t *nval = get_value (rhs, true);
+ val = *nval;
}
- else
+ else if (do_store_ccp && stmt_makes_single_load (stmt))
{
- /* 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);
+ /* Same as above, but the RHS is not a gimple register and yet
+ has a known VUSE. If STMT is loading from the same memory
+ location that created the SSA_NAMEs for the virtual operands,
+ we can propagate the value on the RHS. */
+ prop_value_t *nval = get_value_loaded_by (stmt, const_val);
- wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
- fold_convert (TREE_TYPE (var), build_int_2 (mask, 0)));
+ if (nval && simple_cst_equal (nval->mem_ref, rhs) == 1)
+ val = *nval;
+ else
+ val = evaluate_stmt (stmt);
}
+ else
+ /* Evaluate the statement. */
+ val = evaluate_stmt (stmt);
- 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. */
+ /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant
+ value to be a VIEW_CONVERT_EXPR of the old constant value.
-static void
-initialize (void)
-{
- edge e;
- basic_block bb;
- sbitmap virtual_var;
+ ??? 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);
- /* Worklists of SSA edges. */
- VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges");
- VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges");
+ if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR
+ && val.lattice_val == CONSTANT)
+ {
+ tree w = fold (build1 (VIEW_CONVERT_EXPR,
+ TREE_TYPE (TREE_OPERAND (orig_lhs, 0)),
+ val.value));
- executable_blocks = sbitmap_alloc (last_basic_block);
- sbitmap_zero (executable_blocks);
+ orig_lhs = TREE_OPERAND (orig_lhs, 0);
+ if (w && is_gimple_min_invariant (w))
+ val.value = w;
+ else
+ {
+ val.lattice_val = VARYING;
+ val.value = NULL;
+ }
+ }
- bb_in_list = sbitmap_alloc (last_basic_block);
- sbitmap_zero (bb_in_list);
+ if (val.lattice_val == CONSTANT
+ && TREE_CODE (orig_lhs) == COMPONENT_REF
+ && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1)))
+ {
+ tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1),
+ orig_lhs);
- value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
- memset (value_vector, 0, num_ssa_names * sizeof (value));
+ if (w && is_gimple_min_invariant (w))
+ val.value = w;
+ else
+ {
+ val.lattice_val = VARYING;
+ val.value = NULL_TREE;
+ val.mem_ref = NULL_TREE;
+ }
+ }
+ }
- /* 1 if ssa variable is used in a virtual variable context. */
- virtual_var = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (virtual_var);
+ retval = SSA_PROP_NOT_INTERESTING;
- /* Initialize default values and simulation flags for PHI nodes, statements
- and edges. */
- FOR_EACH_BB (bb)
+ /* Set the lattice value of the statement's output. */
+ 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;
- }
-
- /* Get the default value for each V_MUST_DEF. */
- 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);
- if (get_value (v_must_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));
- }
+ /* If STMT is an assignment to an SSA_NAME, we only have one
+ value to set. */
+ if (set_lattice_value (lhs, val))
+ {
+ *output_p = lhs;
+ if (val.lattice_val == VARYING)
+ retval = SSA_PROP_VARYING;
+ else
+ retval = SSA_PROP_INTERESTING;
}
-
- for (e = bb->succ; e; e = e->succ_next)
- e->flags &= ~EDGE_EXECUTABLE;
}
-
- /* Now process PHI nodes. */
- FOR_EACH_BB (bb)
+ else if (do_store_ccp && stmt_makes_single_store (stmt))
{
- 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 has a V_MAY_DEF,
- the result is 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);
- }
- }
-
- sbitmap_free (virtual_var);
- /* Compute immediate uses for variables we care about. */
- compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
+ /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
+ to the new constant value and mark the LHS as the memory
+ reference associated with VAL. */
+ ssa_op_iter i;
+ tree vdef;
+ bool changed;
- if (dump_file && (dump_flags & TDF_DETAILS))
- dump_immediate_uses (dump_file);
+ /* Stores cannot take on an UNDEFINED value. */
+ if (val.lattice_val == UNDEFINED)
+ val.lattice_val = UNKNOWN_VAL;
- VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
+ /* Mark VAL as stored in the LHS of this assignment. */
+ val.mem_ref = lhs;
- /* 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)
- {
- if (e->dest != EXIT_BLOCK_PTR)
- {
- e->flags |= EDGE_EXECUTABLE;
- cfg_blocks_add (e->dest);
+ /* Set the value of every VDEF to VAL. */
+ changed = false;
+ FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
+ changed |= set_lattice_value (vdef, val);
+
+ /* Note that for propagation purposes, we are only interested in
+ visiting statements that load the exact same memory reference
+ stored here. Those statements will have the exact same list
+ of virtual uses, so it is enough to set the output of this
+ statement to be its first virtual definition. */
+ *output_p = first_vdef (stmt);
+ if (changed)
+ {
+ if (val.lattice_val == VARYING)
+ retval = SSA_PROP_VARYING;
+ else
+ retval = SSA_PROP_INTERESTING;
}
}
-}
-
-
-/* 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 ();
+ return retval;
}
-/* 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. */
+/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
+ if it can determine which edge will be taken. Otherwise, return
+ SSA_PROP_VARYING. */
-static void
-cfg_blocks_add (basic_block bb)
+static enum ssa_prop_result
+visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
- if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
- return;
+ prop_value_t val;
+ basic_block block;
- if (TEST_BIT (bb_in_list, bb->index))
- return;
+ block = bb_for_stmt (stmt);
+ val = evaluate_stmt (stmt);
- if (cfg_blocks_empty_p ())
- {
- cfg_blocks_tail = cfg_blocks_head = 0;
- cfg_blocks_num = 1;
- }
- else
- {
- cfg_blocks_num++;
- if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
- {
- /* 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));
- }
- 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);
+ /* 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.value ? find_taken_edge (block, val.value) : 0;
+ if (*taken_edge_p)
+ return SSA_PROP_INTERESTING;
+ else
+ return SSA_PROP_VARYING;
}
-/* 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;
-}
+/* 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. */
-/* 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)
+static enum ssa_prop_result
+ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
- tree stmt = SSA_NAME_DEF_STMT (var);
- dataflow_t df = get_immediate_uses (stmt);
- int num_uses = num_immediate_uses (df);
- int i;
+ tree def;
+ ssa_op_iter iter;
- for (i = 0; i < num_uses; i++)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- 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);
- }
- }
+ fprintf (dump_file, "\nVisiting statement:\n");
+ print_generic_stmt (dump_file, stmt, dump_flags);
+ fprintf (dump_file, "\n");
}
-}
-
-/* Set the lattice value for the variable VAR to VARYING. */
-
-static void
-def_to_varying (tree var)
-{
- value val;
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
- set_lattice_value (var, val);
-}
-
-/* Set the lattice value for variable VAR to VAL. */
-
-static void
-set_lattice_value (tree var, value val)
-{
- value *old = get_value (var);
-#ifdef ENABLE_CHECKING
- if (val.lattice_val == UNDEFINED)
- {
- /* CONSTANT->UNDEFINED is never a valid state transition. */
- if (old->lattice_val == CONSTANT)
- abort ();
-
- /* UNKNOWN_VAL->UNDEFINED is never a valid state transition. */
- if (old->lattice_val == UNKNOWN_VAL)
- 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)
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
{
- /* 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 ();
+ /* 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);
}
-#endif
-
- /* 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))
+ else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
{
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
+ /* If STMT is a conditional branch, see if we can determine
+ which branch will be taken. */
+ return visit_cond_stmt (stmt, taken_edge_p);
}
- 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");
- }
+ /* 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");
- add_var_to_ssa_edges_worklist (var, val);
- *old = val;
+ /* 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_ALL_DEFS)
+ {
+ prop_value_t v = { VARYING, NULL_TREE, NULL_TREE };
+ set_lattice_value (def, v);
}
-}
-/* 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 bool
-replace_uses_in (tree stmt, bool *replaced_addresses_p)
-{
- bool replaced = false;
- use_optype uses;
- size_t i;
+ return SSA_PROP_VARYING;
+}
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
- get_stmt_operands (stmt);
+/* Main entry point for SSA Conditional Constant Propagation. */
- 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));
+static void
+execute_ssa_ccp (bool store_ccp)
+{
+ do_store_ccp = store_ccp;
+ ccp_initialize ();
+ ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
+ ccp_finalize ();
+}
- 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;
- }
- }
- return replaced;
+static void
+do_ssa_ccp (void)
+{
+ execute_ssa_ccp (false);
}
-/* 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)
+gate_ccp (void)
{
- 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);
+ return flag_tree_ccp != 0;
+}
- if (NUM_VUSES (vuses) != 1)
- return false;
- vuse = VUSE_OP_PTR (vuses, 0);
- val = get_value (USE_FROM_PTR (vuse));
+struct tree_opt_pass pass_ccp =
+{
+ "ccp", /* name */
+ gate_ccp, /* gate */
+ do_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_update_ssa
+ | TODO_ggc_collect | TODO_verify_ssa
+ | TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
+};
- 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)))
- {
- 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;
+static void
+do_ssa_store_ccp (void)
+{
+ /* If STORE-CCP is not enabled, we just run regular CCP. */
+ execute_ssa_ccp (flag_tree_store_ccp != 0);
}
-/* Return the likely latticevalue for STMT.
-
- If STMT has no operands, then return CONSTANT.
+static bool
+gate_store_ccp (void)
+{
+ /* STORE-CCP is enabled only with -ftree-store-ccp, but when
+ -fno-tree-store-ccp is specified, we should run regular CCP.
+ That's why the pass is enabled with either flag. */
+ return flag_tree_store_ccp != 0 || 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_store_ccp =
+{
+ "store_ccp", /* name */
+ gate_store_ccp, /* gate */
+ do_ssa_store_ccp, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_STORE_CCP, /* tv_id */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_update_ssa
+ | TODO_ggc_collect | TODO_verify_ssa
+ | TODO_cleanup_cfg
+ | TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
+};
- Else return VARYING. */
+/* 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. */
-static latticevalue
-likely_value (tree stmt)
+tree
+widen_bitfield (tree val, tree field, tree var)
{
- use_optype uses;
- vuse_optype vuses;
- 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;
- uses = USE_OPS (ann);
- for (i = 0; i < NUM_USES (uses); i++)
- {
- tree use = USE_OP (uses, i);
- value *val = get_value (use);
+ gcc_assert (var_size >= field_size);
- if (val->lattice_val == UNDEFINED)
- return UNDEFINED;
+ /* 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;
- if (val->lattice_val == CONSTANT)
- found_constant = 1;
+ wide_val = build2 (BIT_AND_EXPR, TREE_TYPE (var), val,
+ build_int_cst (TREE_TYPE (var), mask));
}
-
- vuses = VUSE_OPS (ann);
-
- if (NUM_VUSES (vuses))
+ else
{
- tree vuse = VUSE_OP (vuses, 0);
- value *val = get_value (vuse);
-
- if (val->lattice_val == UNKNOWN_VAL)
- return UNKNOWN_VAL;
-
-#ifdef ENABLE_CHECKING
- /* There should be no VUSE operands that are UNDEFINED. */
- if (val->lattice_val == UNDEFINED)
- abort ();
-#endif
-
- if (val->lattice_val == CONSTANT)
- found_constant = 1;
+ /* 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 = build2 (BIT_IOR_EXPR, TREE_TYPE (var), val,
+ build_int_cst (TREE_TYPE (var), mask));
}
- return ((found_constant || (!uses && !vuses)) ? 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 (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;
field_type = TREE_TYPE (f);
- if (cmp < 0)
- {
- /* Don't care about offsets into the middle of scalars. */
- if (!AGGREGATE_TYPE_P (field_type))
- continue;
-
- /* Check for array at the end of the struct. This is often
- used as for flexible array members. We should be able to
- turn this into an array access anyway. */
- if (TREE_CODE (field_type) == ARRAY_TYPE)
- tail_array_field = f;
-
- /* Check the end of the field against the offset. */
- if (!DECL_SIZE_UNIT (f)
- || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
- continue;
- t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
- if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
- continue;
-
- /* If we matched, then set offset to the displacement into
- this field. */
- offset = t;
- }
/* Here we exactly match the offset being checked. If the types match,
then we can return that field. */
- else if (lang_hooks.types_compatible_p (orig_type, field_type))
+ if (cmp == 0
+ && lang_hooks.types_compatible_p (orig_type, field_type))
{
if (base_is_ptr)
base = build1 (INDIRECT_REF, record_type, base);
t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
return t;
}
+
+ /* Don't care about offsets into the middle of scalars. */
+ if (!AGGREGATE_TYPE_P (field_type))
+ continue;
- /* Don't care about type-punning of scalars. */
- else if (!AGGREGATE_TYPE_P (field_type))
- return NULL_TREE;
+ /* Check for array at the end of the struct. This is often
+ used as for flexible array members. We should be able to
+ turn this into an array access anyway. */
+ if (TREE_CODE (field_type) == ARRAY_TYPE)
+ tail_array_field = f;
+
+ /* Check the end of the field against the offset. */
+ if (!DECL_SIZE_UNIT (f)
+ || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
+ continue;
+ t = int_const_binop (MINUS_EXPR, offset, field_offset, 1);
+ if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
+ continue;
+ /* If we matched, then set offset to the displacement into
+ this field. */
+ offset = t;
goto found;
}
f = tail_array_field;
field_type = TREE_TYPE (f);
+ offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
found:
/* If we get here, we've got an aggregate field, and a possibly
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. */
substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
are sometimes added. */
base = fold (base);
- STRIP_NOPS (base);
+ STRIP_TYPE_NOPS (base);
TREE_OPERAND (expr, 0) = base;
/* One possibility is that the address reduces to a string constant. */
/* We can get here for out-of-range string constant accesses,
such as "_"[3]. Bail out of the entire substitution search
and arrange for the entire statement to be replaced by a
- call to __builtin_trap. In all likelyhood this will all be
+ call to __builtin_trap. In all likelihood this will all be
constant-folded away, but in the meantime we can't leave with
something that get_expr_operands can't understand. */
&& TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
{
/* FIXME: Except that this causes problems elsewhere with dead
- code not being deleted, and we abort in the rtl expanders
+ code not being deleted, and we die in the rtl expanders
because we failed to remove some ssa_name. In the meantime,
just return zero. */
/* FIXME2: This condition should be signaled by
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 || TREE_CODE (stmt) != MODIFY_EXPR)
- return stmt;
- /* FALLTHRU */
-
- case MODIFY_EXPR:
- stmt = TREE_OPERAND (stmt, 1);
- if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
- return TREE_OPERAND (stmt, 0);
- else
- return stmt;
-
- 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')
- {
- if (!is_gimple_val (TREE_OPERAND (expr, 0)))
- return false;
- }
-
- switch (TREE_CODE (stmt))
+ tree var, def_stmt, val;
+
+ if (TREE_CODE (arg) != SSA_NAME)
{
- 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:
- op = TREE_OPERAND (stmt, 1);
- if (TREE_CODE (op) == WITH_SIZE_EXPR)
- stmt = op;
- 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;
+ val = c_strlen (arg, 1);
+ if (!val)
+ return false;
- 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;
- }
+ if (*length && simple_cst_equal (val, *length) != 1)
+ return false;
- 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;
+ *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);
+
+ 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);
-/* Return a default value for variable VAR using the following rules:
+ /* 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;
- 1- Function arguments are considered VARYING.
-
- 2- Global and static variables that are declared constant are
- considered CONSTANT.
+ *length = len;
+ return true;
+ }
- 3- Any other virtually defined variable is considered UNKNOWN_VAL.
+ break;
+ }
- 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. */
+ case PHI_NODE:
+ {
+ /* All the arguments of the PHI node must have the same constant
+ length. */
+ int i;
-static value
-get_default_value (tree var)
-{
- value val;
- tree sym;
+ for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
+ {
+ tree arg = PHI_ARG_DEF (def_stmt, i);
- if (TREE_CODE (var) == SSA_NAME)
- sym = SSA_NAME_VAR (var);
- else
- {
-#ifdef ENABLE_CHECKING
- if (!DECL_P (var))
- abort ();
-#endif
- sym = var;
- }
+ /* 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;
- val.lattice_val = UNDEFINED;
- val.const_val = NULL_TREE;
+ if (!get_strlen (arg, length, visited))
+ return false;
+ }
- 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;
+ return true;
}
- }
- 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);
- 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;
}
/* First try the generic builtin folder. If that succeeds, return the
result directly. */
- result = fold_builtin (fn, ignore);
+ callee = get_callee_fndecl (fn);
+ arglist = TREE_OPERAND (fn, 1);
+ result = fold_builtin (callee, arglist, ignore);
if (result)
{
if (ignore)
}
/* Ignore MD builtins. */
- callee = get_callee_fndecl (fn);
if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
return NULL_TREE;
/* If the builtin could not be folded, and it has no argument list,
we're done. */
- arglist = TREE_OPERAND (fn, 1);
if (!arglist)
return NULL_TREE;
}
/* Try to use the dataflow information gathered by the CCP process. */
- visited = BITMAP_XMALLOC ();
+ visited = BITMAP_ALLOC (NULL);
memset (strlen_val, 0, sizeof (strlen_val));
for (i = 0, a = arglist;
strlen_val[i] = NULL_TREE;
}
- BITMAP_XFREE (visited);
+ BITMAP_FREE (visited);
result = NULL_TREE;
switch (DECL_FUNCTION_CODE (callee))
case BUILT_IN_STRCPY:
if (strlen_val[1] && is_gimple_val (strlen_val[1]))
- result = fold_builtin_strcpy (fn, strlen_val[1]);
+ {
+ tree fndecl = get_callee_fndecl (fn);
+ tree arglist = TREE_OPERAND (fn, 1);
+ result = fold_builtin_strcpy (fndecl, arglist, strlen_val[1]);
+ }
break;
case BUILT_IN_STRNCPY:
if (strlen_val[1] && is_gimple_val (strlen_val[1]))
- result = fold_builtin_strncpy (fn, strlen_val[1]);
+ {
+ tree fndecl = get_callee_fndecl (fn);
+ tree arglist = TREE_OPERAND (fn, 1);
+ result = fold_builtin_strncpy (fndecl, arglist, strlen_val[1]);
+ }
break;
case BUILT_IN_FPUTS:
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);
- return false;
+ if (EXPR_HAS_LOCATION (stmt))
+ annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
+
+ /* The replacement can expose previously unreferenced variables. */
+ for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti))
+ {
+ tree new_stmt = tsi_stmt (ti);
+ find_new_referenced_vars (tsi_stmt_ptr (ti));
+ bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT);
+ mark_new_vars_to_rename (bsi_stmt (*si_p));
+ bsi_next (si_p);
+ }
+
+ 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)
+ {
+ bool ok = set_rhs (stmtp, result);
+
+ gcc_assert (ok);
+ }
+ }
+ update_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 */
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_update_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
-
-
-#include "gt-tree-ssa-ccp.h"