/* 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, 2006
+ 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>
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
+
+/* 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 -> the initial state of the value. This value
+ is replaced with a correct initial value
+ the first time the value is used, so the
+ rest of the pass does not need to care about
+ it. Using this value simplifies initialization
+ of the pass, and prevents us from needlessly
+ scanning statements that are never reached.
+
+ 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 VDEF 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 = VDEF <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.
-/* Conditional constant propagation.
+ Note that the initial value of virtual operands is VARYING, not
+ UNDEFINED. 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;'.
+
+ 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 "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"
+#include "target.h"
/* Possible lattice values. */
typedef enum
{
- UNINITIALIZED = 0,
+ UNINITIALIZED,
UNDEFINED,
- UNKNOWN_VAL,
CONSTANT,
VARYING
-} latticevalue;
+} ccp_lattice_t;
-/* 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)
+/* 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 VDEF), CONST_VAL[I].MEM_REF will contain the actual
+ memory reference used to store (i.e., the LHS of the assignment
+ doing the store). */
+static prop_value_t *const_val;
-/* 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;
+/* True if we are also propagating constants in stores and loads. */
+static bool do_store_ccp;
-/* A bitmap to keep track of executable blocks in the CFG. */
-static sbitmap executable_blocks;
+/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
+
+static void
+dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
+{
+ switch (val.lattice_val)
+ {
+ case UNINITIALIZED:
+ fprintf (outf, "%sUNINITIALIZED", prefix);
+ break;
+ case UNDEFINED:
+ fprintf (outf, "%sUNDEFINED", prefix);
+ break;
+ case VARYING:
+ fprintf (outf, "%sVARYING", prefix);
+ break;
+ case CONSTANT:
+ fprintf (outf, "%sCONSTANT ", prefix);
+ print_generic_expr (outf, val.value, dump_flags);
+ break;
+ default:
+ gcc_unreachable ();
+ }
+}
-/* Array of control flow edges on the worklist. */
-static GTY(()) varray_type cfg_blocks = NULL;
-static unsigned int cfg_blocks_num = 0;
-static int cfg_blocks_tail;
-static int cfg_blocks_head;
+/* Print lattice value VAL to stderr. */
-static sbitmap bb_in_list;
+void debug_lattice_value (prop_value_t val);
-/* This is used to track the current value of each variable. */
-static value *value_vector;
+void
+debug_lattice_value (prop_value_t val)
+{
+ dump_lattice_value (stderr, "", val);
+ fprintf (stderr, "\n");
+}
-/* 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. */
+/* The regular is_gimple_min_invariant does a shallow test of the object.
+ It assumes that full gimplification has happened, or will happen on the
+ object. For a value coming from DECL_INITIAL, this is not true, so we
+ have to be more strict ourselves. */
-static void
-process_ssa_edge_worklist (varray_type *worklist)
+static bool
+ccp_decl_initial_min_invariant (tree t)
{
- /* Drain the entire worklist. */
- while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
+ if (!is_gimple_min_invariant (t))
+ return false;
+ if (TREE_CODE (t) == ADDR_EXPR)
{
- /* 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)
+ /* Inline and unroll is_gimple_addressable. */
+ while (1)
{
- ann->in_ccp_worklist = 0;
- simulate_stmt (stmt);
+ t = TREE_OPERAND (t, 0);
+ if (is_gimple_id (t))
+ return true;
+ if (!handled_component_p (t))
+ return false;
}
- }
+ }
+ return true;
}
-
-/* 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. */
+/* If SYM is a constant variable with known value, return the value.
+ NULL_TREE is returned otherwise. */
-static void
-tree_ssa_ccp (void)
+static tree
+get_symbol_constant_value (tree sym)
{
- 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 (TREE_STATIC (sym)
+ && TREE_READONLY (sym)
+ && !MTAG_P (sym))
{
- 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);
- }
+ tree val = DECL_INITIAL (sym);
+ if (val
+ && ccp_decl_initial_min_invariant (val))
+ return val;
+ }
- /* 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);
+ return NULL_TREE;
+}
- /* Now process the SSA_EDGES worklist. */
- process_ssa_edge_worklist (&ssa_edges);
- }
+/* Compute a default value for variable VAR and store it in the
+ CONST_VAL array. The following rules are used to get default
+ values:
- /* Now perform substitutions based on the known constant values. */
- substitute_and_fold ();
+ 1- Global and static variables that are declared constant are
+ considered CONSTANT.
- /* Now cleanup any unreachable code. */
- cleanup_tree_cfg ();
+ 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.
- /* Free allocated memory. */
- finalize ();
+ 3- If SSA_NAME_VALUE is set and it is a constant, its value is
+ used.
- /* Debugging dumps. */
- if (dump_file && (dump_flags & TDF_DETAILS))
+ 4- Variables defined by statements other than assignments and PHI
+ nodes are considered VARYING.
+
+ 5- Initial values of variables that are not GIMPLE registers are
+ considered VARYING. */
+
+static prop_value_t
+get_default_value (tree var)
+{
+ tree sym = SSA_NAME_VAR (var);
+ prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE };
+ tree cst_val;
+
+ if (!do_store_ccp && !is_gimple_reg (var))
{
- dump_referenced_vars (dump_file);
- fprintf (dump_file, "\n\n");
+ /* Short circuit for regular CCP. We are not interested in any
+ non-register when DO_STORE_CCP is false. */
+ val.lattice_val = VARYING;
}
-}
+ else if (SSA_NAME_VALUE (var)
+ && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
+ {
+ val.lattice_val = CONSTANT;
+ val.value = SSA_NAME_VALUE (var);
+ }
+ else if ((cst_val = get_symbol_constant_value (sym)) != NULL_TREE)
+ {
+ /* Globals and static variables declared 'const' take their
+ initial value. */
+ val.lattice_val = CONSTANT;
+ val.value = cst_val;
+ val.mem_ref = sym;
+ }
+ else
+ {
+ tree stmt = SSA_NAME_DEF_STMT (var);
-static bool
-gate_ccp (void)
-{
- return flag_tree_ccp != 0;
-}
+ if (IS_EMPTY_STMT (stmt))
+ {
+ /* 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, otherwise we must
+ consider it VARYING. */
+ if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
+ val.lattice_val = UNDEFINED;
+ else
+ val.lattice_val = VARYING;
+ }
+ else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ || TREE_CODE (stmt) == PHI_NODE)
+ {
+ /* Any other variable defined by an assignment or a PHI node
+ is considered UNDEFINED. */
+ val.lattice_val = UNDEFINED;
+ }
+ else
+ {
+ /* Otherwise, VAR will never take on a constant value. */
+ val.lattice_val = VARYING;
+ }
+ }
-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 */
-};
+ return val;
+}
/* Get the constant value associated with variable VAR. */
-static value *
+static inline prop_value_t *
get_value (tree var)
{
- value *val;
-
-#if defined ENABLE_CHECKING
- if (TREE_CODE (var) != SSA_NAME)
- abort ();
-#endif
+ prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
- val = &value_vector[SSA_NAME_VERSION (var)];
if (val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
return val;
}
+/* Sets the value associated with VAR to VARYING. */
-/* Simulate the execution of BLOCK. Evaluate the statement associated
- with each variable reference inside the block. */
+static inline void
+set_value_varying (tree var)
+{
+ prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
+
+ val->lattice_val = VARYING;
+ val->value = NULL_TREE;
+ val->mem_ref = NULL_TREE;
+}
+
+/* For float types, modify the value of VAL to make ccp work correctly
+ for non-standard values (-0, NaN):
+
+ If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
+ If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
+ This is to fix the following problem (see PR 29921): Suppose we have
+
+ x = 0.0 * y
+
+ and we set value of y to NaN. This causes value of x to be set to NaN.
+ When we later determine that y is in fact VARYING, fold uses the fact
+ that HONOR_NANS is false, and we try to change the value of x to 0,
+ causing an ICE. With HONOR_NANS being false, the real appearance of
+ NaN would cause undefined behavior, though, so claiming that y (and x)
+ are UNDEFINED initially is correct. */
static void
-simulate_block (basic_block block)
+canonicalize_float_value (prop_value_t *val)
{
- tree phi;
+ enum machine_mode mode;
+ tree type;
+ REAL_VALUE_TYPE d;
- /* There is nothing to do for the exit block. */
- if (block == EXIT_BLOCK_PTR)
+ if (val->lattice_val != CONSTANT
+ || TREE_CODE (val->value) != REAL_CST)
return;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nSimulating block %d\n", block->index);
+ d = TREE_REAL_CST (val->value);
+ type = TREE_TYPE (val->value);
+ mode = TYPE_MODE (type);
- /* 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);
+ if (!HONOR_SIGNED_ZEROS (mode)
+ && REAL_VALUE_MINUS_ZERO (d))
+ {
+ val->value = build_real (type, dconst0);
+ return;
+ }
- /* If this is the first time we've simulated this block, then we
- must simulate each of its statements. */
- if (!TEST_BIT (executable_blocks, block->index))
+ if (!HONOR_NANS (mode)
+ && REAL_VALUE_ISNAN (d))
{
- block_stmt_iterator j;
- unsigned int normal_edge_count;
- edge e, normal_edge;
+ val->lattice_val = UNDEFINED;
+ val->value = NULL;
+ val->mem_ref = NULL;
+ return;
+ }
+}
- /* Note that we have simulated this block. */
- SET_BIT (executable_blocks, block->index);
+/* 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);
- for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
- visit_stmt (bsi_stmt (j));
+ canonicalize_float_value (&new_val);
- /* 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.
+ /* Lattice transitions must always be monotonically increasing in
+ value. If *OLD_VAL and NEW_VAL are the same, return false to
+ inform the caller that this was a non-transition. */
- 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;
- }
- }
+ gcc_assert (old_val->lattice_val < new_val.lattice_val
+ || (old_val->lattice_val == new_val.lattice_val
+ && ((!old_val->value && !new_val.value)
+ || operand_equal_p (old_val->value, new_val.value, 0))
+ && old_val->mem_ref == new_val.mem_ref));
- if (normal_edge_count == 1)
- add_control_edge (normal_edge);
+ if (old_val->lattice_val != new_val.lattice_val)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
+ fprintf (dump_file, ". Adding SSA edges to worklist.\n");
+ }
+
+ *old_val = new_val;
+
+ gcc_assert (new_val.lattice_val != UNDEFINED);
+ return true;
}
+
+ return false;
}
-/* Follow the def-use edges for statement DEF_STMT and simulate all the
- statements reached by it. */
+/* Return the likely CCP lattice value for STMT.
-static void
-simulate_stmt (tree use_stmt)
+ If STMT has no operands, then return CONSTANT.
+
+ Else if any operands of STMT are undefined, then return UNDEFINED.
+
+ Else if any operands of STMT are constants, then return CONSTANT.
+
+ Else return VARYING. */
+
+static ccp_lattice_t
+likely_value (tree stmt)
{
- basic_block use_bb = bb_for_stmt (use_stmt);
+ bool has_constant_operand;
+ stmt_ann_t ann;
+ tree use;
+ ssa_op_iter iter;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
- print_generic_stmt (dump_file, use_stmt, dump_flags);
- }
+ 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;
+
+ /* If we are not doing store-ccp, statements with loads
+ and/or stores will never fold into a constant. */
+ if (!do_store_ccp
+ && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ return VARYING;
+
+
+ /* 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;
- if (TREE_CODE (use_stmt) == PHI_NODE)
+ /* Anything other than assignments and conditional jumps are not
+ interesting for CCP. */
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
+ && !(TREE_CODE (stmt) == RETURN_EXPR && get_rhs (stmt) != NULL_TREE)
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ return VARYING;
+
+ if (is_gimple_min_invariant (get_rhs (stmt)))
+ return CONSTANT;
+
+ has_constant_operand = false;
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
{
- /* PHI nodes are always visited, regardless of whether or not the
- destination block is executable. */
- visit_phi_node (use_stmt);
+ prop_value_t *val = get_value (use);
+
+ if (val->lattice_val == UNDEFINED)
+ return UNDEFINED;
+
+ if (val->lattice_val == CONSTANT)
+ has_constant_operand = true;
}
- else if (TEST_BIT (executable_blocks, use_bb->index))
+
+ if (has_constant_operand
+ /* We do not consider virtual operands here -- load from read-only
+ memory may have only VARYING virtual operands, but still be
+ constant. */
+ || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
+ return CONSTANT;
+
+ return VARYING;
+}
+
+/* Returns true if STMT cannot be constant. */
+
+static bool
+surely_varying_stmt_p (tree stmt)
+{
+ /* If the statement has operands that we cannot handle, it cannot be
+ constant. */
+ if (stmt_ann (stmt)->has_volatile_ops)
+ return true;
+
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
{
- /* Otherwise, visit the statement containing the use reached by
- DEF, only if the destination block is marked executable. */
- visit_stmt (use_stmt);
+ if (!do_store_ccp)
+ return true;
+
+ /* We can only handle simple loads and stores. */
+ if (!stmt_makes_single_load (stmt)
+ && !stmt_makes_single_store (stmt))
+ return true;
}
-}
+ /* If it contains a call, it is varying. */
+ if (get_call_expr_in (stmt) != NULL_TREE)
+ return true;
+
+ /* Anything other than assignments and conditional jumps are not
+ interesting for CCP. */
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
+ && !(TREE_CODE (stmt) == RETURN_EXPR && get_rhs (stmt) != NULL_TREE)
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ return true;
+
+ return false;
+}
-/* Perform final substitution and folding. After this pass the program
- should still be in SSA form. */
+/* Initialize local data structures for CCP. */
static void
-substitute_and_fold (void)
+ccp_initialize (void)
{
basic_block bb;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "\nSubstituing constants and folding statements\n\n");
+ const_val = XCNEWVEC (prop_value_t, num_ssa_names);
- /* Substitute constants in every statement of every basic block. */
+ /* Initialize simulation flags for PHI nodes and statements. */
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
- tree phi;
-
- /* Propagate our known constants into PHI nodes. */
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- 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);
- }
- }
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
- {
- bool replaced_address;
+ {
tree stmt = bsi_stmt (i);
+ bool is_varying = surely_varying_stmt_p (stmt);
- /* 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))
+ if (is_varying)
{
- fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- }
+ tree def;
+ ssa_op_iter iter;
- 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)
+ /* 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)
{
- mark_new_vars_to_rename (stmt, vars_to_rename);
- if (maybe_clean_eh_stmt (stmt))
- tree_purge_dead_eh_edges (bb);
+ if (is_varying)
+ set_value_varying (def);
}
}
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " with ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
+ DONT_SIMULATE_AGAIN (stmt) = is_varying;
+ }
+ }
+
+ /* Now process PHI nodes. We never set DONT_SIMULATE_AGAIN on phi node,
+ since we do not know which edges are executable yet, except for
+ phi nodes for virtual operands when we do not do store ccp. */
+ FOR_EACH_BB (bb)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ if (!do_store_ccp && !is_gimple_reg (PHI_RESULT (phi)))
+ DONT_SIMULATE_AGAIN (phi) = true;
+ else
+ DONT_SIMULATE_AGAIN (phi) = false;
}
}
}
-/* 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. */
+/* Do final substitution of propagated values, cleanup the flowgraph and
+ free allocated storage. */
static void
-visit_phi_node (tree phi)
+ccp_finalize (void)
{
- bool short_circuit = 0;
- value phi_val, *curr_val;
- int i;
+ /* Perform substitutions based on the known constant values. */
+ substitute_and_fold (const_val, false);
- /* If the PHI node has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (phi))
- return;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nVisiting PHI node: ");
- print_generic_expr (dump_file, phi, dump_flags);
- }
-
- curr_val = get_value (PHI_RESULT (phi));
- switch (curr_val->lattice_val)
- {
- 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;
-
- case UNDEFINED:
- case UNINITIALIZED:
- phi_val.lattice_val = UNDEFINED;
- phi_val.const_val = NULL_TREE;
- break;
-
- default:
- abort ();
- }
-
- /* 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);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "\n Argument #%d (%d -> %d %sexecutable)\n",
- i, e->src->index, e->dest->index,
- (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
- }
-
- /* If the incoming edge is executable, Compute the meet operator for
- the existing value of the PHI node and the current PHI argument. */
- if (e->flags & EDGE_EXECUTABLE)
- {
- tree rdef = PHI_ARG_DEF (phi, i);
- value *rdef_val, val;
-
- if (is_gimple_min_invariant (rdef))
- {
- val.lattice_val = CONSTANT;
- val.const_val = rdef;
- rdef_val = &val;
- }
- else
- rdef_val = get_value (rdef);
+ free (const_val);
+}
- phi_val = cp_lattice_meet (phi_val, *rdef_val);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\t");
- print_generic_expr (dump_file, rdef, dump_flags);
- dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
- fprintf (dump_file, "\n");
- }
+/* Compute the meet operator between *VAL1 and *VAL2. Store the result
+ in VAL1.
- if (phi_val.lattice_val == VARYING)
- break;
- }
- }
+ any M UNDEFINED = any
+ any M VARYING = VARYING
+ Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
+ */
- if (dump_file && (dump_flags & TDF_DETAILS))
+static void
+ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
+{
+ if (val1->lattice_val == UNDEFINED)
{
- dump_lattice_value (dump_file, "\n PHI node value: ", phi_val);
- fprintf (dump_file, "\n\n");
+ /* UNDEFINED M any = any */
+ *val1 = *val2;
}
-
- /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
- if (phi_val.lattice_val != UNDEFINED || phi_val.const_val == NULL_TREE)
+ else if (val2->lattice_val == UNDEFINED)
{
- set_lattice_value (PHI_RESULT (phi), phi_val);
- if (phi_val.lattice_val == VARYING)
- DONT_SIMULATE_AGAIN (phi) = 1;
+ /* any M UNDEFINED = any
+ Nothing to do. VAL1 already contains the value we want. */
+ ;
}
-}
-
-
-/* Compute the meet operator between VAL1 and VAL2:
-
- 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;
-
- /* any M VARYING = VARYING. */
- if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
+ else if (val1->lattice_val == VARYING
+ || val2->lattice_val == VARYING)
{
- result.lattice_val = VARYING;
- result.const_val = NULL_TREE;
- return result;
+ /* any M VARYING = VARYING. */
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
}
-
- /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
- if (val1.lattice_val == UNKNOWN_VAL
- || val2.lattice_val == UNKNOWN_VAL)
+ else if (val1->lattice_val == CONSTANT
+ && val2->lattice_val == CONSTANT
+ && simple_cst_equal (val1->value, val2->value) == 1
+ && (!do_store_ccp
+ || (val1->mem_ref && val2->mem_ref
+ && operand_equal_p (val1->mem_ref, val2->mem_ref, 0))))
{
- result.lattice_val = UNKNOWN_VAL;
- result.const_val = NULL_TREE;
- return result;
- }
+ /* Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
- /* 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;
+ 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
{
- result.lattice_val = VARYING;
- result.const_val = NULL_TREE;
+ /* Any other combination is VARYING. */
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
}
-
- return result;
}
-/* Evaluate statement STMT. If the statement produces an output value and
- its evaluation changes the lattice value of its output, do the following:
-
- - If the statement is an assignment, add all the SSA edges starting at
- this definition.
-
- - If the statement is a conditional branch:
- . If the statement evaluates to non-constant, add all edges to
- worklist.
- . If the statement is constant, add the edge executed as the
- result of the branch. */
+/* Loop through the PHI_NODE's parameters for BLOCK and compare their
+ lattice values to determine PHI_NODE's lattice value. The value of a
+ PHI node is determined calling ccp_lattice_meet with all the arguments
+ of the PHI node that are incoming via executable edges. */
-static void
-visit_stmt (tree stmt)
+static enum ssa_prop_result
+ccp_visit_phi_node (tree phi)
{
- size_t i;
- stmt_ann_t ann;
- def_optype defs;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
-
- /* If the statement has already been deemed to be VARYING, don't simulate
- it again. */
- if (DONT_SIMULATE_AGAIN (stmt))
- return;
+ int i;
+ prop_value_t *old_val, new_val;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "\nVisiting statement: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- fprintf (dump_file, "\n");
+ fprintf (dump_file, "\nVisiting PHI node: ");
+ print_generic_expr (dump_file, phi, dump_flags);
}
- ann = stmt_ann (stmt);
-
- /* If this statement is already in the worklist then "cancel" it. The
- reevaluation implied by the worklist entry will produce the same
- value we generate here and thus reevaluating it again from the
- worklist is pointless. */
- if (ann->in_ccp_worklist)
- ann->in_ccp_worklist = 0;
-
- /* Now examine the statement. If the statement is an assignment that
- produces a single output value, evaluate its RHS to see if the lattice
- value of its output has changed. */
- 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)
- {
- DONT_SIMULATE_AGAIN (stmt) = 1;
- for (i = 0; i < NUM_DEFS (defs); i++)
- {
- tree def = DEF_OP (defs, i);
- def_to_varying (def);
- }
- }
+ old_val = get_value (PHI_RESULT (phi));
+ switch (old_val->lattice_val)
+ {
+ case VARYING:
+ return SSA_PROP_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);
+ case CONSTANT:
+ new_val = *old_val;
+ break;
- /* Any other kind of statement is not interesting for constant
- propagation and, therefore, not worth simulating. */
- else
- {
- DONT_SIMULATE_AGAIN (stmt) = 1;
+ case UNDEFINED:
+ new_val.lattice_val = UNDEFINED;
+ new_val.value = NULL_TREE;
+ new_val.mem_ref = NULL_TREE;
+ break;
- /* 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));
+ default:
+ gcc_unreachable ();
}
- /* 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));
-
-}
+ 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 ");
+ }
-/* Visit the assignment statement STMT. Set the value of its LHS to the
- value computed by the RHS. */
+ /* 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;
-static void
-visit_assignment (tree stmt)
-{
- value val;
- tree lhs, rhs;
- vuse_optype vuses;
- v_must_def_optype v_must_defs;
+ 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));
- lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
- vuses = STMT_VUSE_OPS (stmt);
- v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
+ ccp_lattice_meet (&new_val, &arg_val);
-#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
+ 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");
+ }
- /* 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 we make it here, then stmt only has one definition:
- a V_MUST_DEF. */
- lhs = V_MUST_DEF_OP (v_must_defs, 0);
+ if (new_val.lattice_val == VARYING)
+ break;
+ }
}
- if (TREE_CODE (rhs) == SSA_NAME)
- {
- /* For a simple copy operation, we copy the lattice values. */
- value *nval = get_value (rhs);
- val = *nval;
- }
- else if (DECL_P (rhs)
- && NUM_VUSES (vuses) == 1
- && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
- {
- /* 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;
- }
- else
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- /* Evaluate the statement. */
- val = evaluate_stmt (stmt);
+ dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
+ fprintf (dump_file, "\n\n");
}
- /* 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);
- else
+ /* Make the transition to the new value. */
+ if (set_lattice_value (PHI_RESULT (phi), new_val))
{
- DONT_SIMULATE_AGAIN (stmt) = 1;
- add_outgoing_control_edges (block);
+ if (new_val.lattice_val == VARYING)
+ return SSA_PROP_VARYING;
+ else
+ return SSA_PROP_INTERESTING;
}
+ else
+ return SSA_PROP_NOT_INTERESTING;
}
-/* Add all the edges coming out of BB to the control flow worklist. */
-
-static void
-add_outgoing_control_edges (basic_block bb)
-{
- edge e;
-
- for (e = bb->succ; e; e = e->succ_next)
- add_control_edge (e);
-}
-
-
-/* Add edge E to the control flow worklist. */
-
-static void
-add_control_edge (edge e)
-{
- basic_block bb = e->dest;
- if (bb == EXIT_BLOCK_PTR)
- return;
-
- /* If the edge had already been executed, skip it. */
- if (e->flags & EDGE_EXECUTABLE)
- return;
-
- e->flags |= EDGE_EXECUTABLE;
-
- /* If the block is already in the list, we're done. */
- if (TEST_BIT (bb_in_list, bb->index))
- return;
-
- cfg_blocks_add (bb);
-
- 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);
-}
-
-
-/* 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)->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 && val->mem_ref)
+ {
+ if (operand_equal_p (val->mem_ref, rhs, 0))
+ return val->value;
+
+ /* If RHS is extracting REALPART_EXPR or IMAGPART_EXPR of a
+ complex type with a known constant value, return it. */
+ if ((TREE_CODE (rhs) == REALPART_EXPR
+ || TREE_CODE (rhs) == IMAGPART_EXPR)
+ && operand_equal_p (val->mem_ref, TREE_OPERAND (rhs, 0), 0))
+ return fold_build1 (TREE_CODE (rhs), TREE_TYPE (rhs), val->value);
+ }
+ 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);
if (val->lattice_val == CONSTANT)
- op0 = get_value (op0)->const_val;
+ op0 = get_value (op0)->value;
}
- retval = nondestructive_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. */
- if (retval && ! is_gimple_min_invariant (retval))
- return NULL;
-
- /* If we could not fold the expression, but the arguments are all
- constants and gimple values, then build and return the new
- expression.
-
- In some cases the new expression is still something we can
- use as a replacement for an argument. This happens with
- NOP conversions of types for example.
-
- In other cases the new expression can not be used as a
- replacement for an argument (as it would create non-gimple
- code). But the new expression can still be used to derive
- other constants. */
- if (! retval && is_gimple_min_invariant (op0))
- return build1 (code, TREE_TYPE (rhs), op0);
+ if ((code == NOP_EXPR || code == CONVERT_EXPR)
+ && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs),
+ TREE_TYPE (op0)))
+ return op0;
+ return fold_unary (code, TREE_TYPE (rhs), op0);
}
/* 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);
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);
if (val->lattice_val == CONSTANT)
- op1 = val->const_val;
+ op1 = val->value;
}
- retval = nondestructive_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. */
- if (retval && ! is_gimple_min_invariant (retval))
- return NULL;
-
- /* If we could not fold the expression, but the arguments are all
- constants and gimple values, then build and return the new
- expression.
-
- In some cases the new expression is still something we can
- use as a replacement for an argument. This happens with
- NOP conversions of types for example.
-
- In other cases the new expression can not be used as a
- replacement for an argument (as it would create non-gimple
- code). But the new expression can still be used to derive
- other constants. */
- if (! retval
- && is_gimple_min_invariant (op0)
- && is_gimple_min_invariant (op1))
- return build (code, TREE_TYPE (rhs), op0, op1);
+ return fold_binary (code, TREE_TYPE (rhs), op0, op1);
}
/* We may be able to fold away calls to builtin functions if their
== 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 = XNEWVEC (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);
}
}
}
+/* Return the tree representing the element referenced by T if T is an
+ ARRAY_REF or COMPONENT_REF into constant aggregates. Return
+ NULL_TREE otherwise. */
+
+static tree
+fold_const_aggregate_ref (tree t)
+{
+ prop_value_t *value;
+ tree base, ctor, idx, field;
+ unsigned HOST_WIDE_INT cnt;
+ tree cfield, cval;
+
+ switch (TREE_CODE (t))
+ {
+ case ARRAY_REF:
+ /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
+ DECL_INITIAL. If BASE is a nested reference into another
+ ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
+ the inner reference. */
+ base = TREE_OPERAND (t, 0);
+ switch (TREE_CODE (base))
+ {
+ case VAR_DECL:
+ if (!TREE_READONLY (base)
+ || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
+ || !targetm.binds_local_p (base))
+ return NULL_TREE;
+
+ ctor = DECL_INITIAL (base);
+ break;
+
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ ctor = fold_const_aggregate_ref (base);
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (ctor == NULL_TREE
+ || (TREE_CODE (ctor) != CONSTRUCTOR
+ && TREE_CODE (ctor) != STRING_CST)
+ || !TREE_STATIC (ctor))
+ return NULL_TREE;
+
+ /* Get the index. If we have an SSA_NAME, try to resolve it
+ with the current lattice value for the SSA_NAME. */
+ idx = TREE_OPERAND (t, 1);
+ switch (TREE_CODE (idx))
+ {
+ case SSA_NAME:
+ if ((value = get_value (idx))
+ && value->lattice_val == CONSTANT
+ && TREE_CODE (value->value) == INTEGER_CST)
+ idx = value->value;
+ else
+ return NULL_TREE;
+ break;
+
+ case INTEGER_CST:
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ /* Fold read from constant string. */
+ if (TREE_CODE (ctor) == STRING_CST)
+ {
+ if ((TYPE_MODE (TREE_TYPE (t))
+ == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
+ && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor))))
+ == MODE_INT)
+ && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1
+ && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0)
+ return build_int_cst (TREE_TYPE (t), (TREE_STRING_POINTER (ctor)
+ [TREE_INT_CST_LOW (idx)]));
+ return NULL_TREE;
+ }
+
+ /* Whoo-hoo! I'll fold ya baby. Yeah! */
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
+ if (tree_int_cst_equal (cfield, idx))
+ return cval;
+ break;
+
+ case COMPONENT_REF:
+ /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
+ DECL_INITIAL. If BASE is a nested reference into another
+ ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
+ the inner reference. */
+ base = TREE_OPERAND (t, 0);
+ switch (TREE_CODE (base))
+ {
+ case VAR_DECL:
+ if (!TREE_READONLY (base)
+ || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
+ || !targetm.binds_local_p (base))
+ return NULL_TREE;
+
+ ctor = DECL_INITIAL (base);
+ break;
+
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ ctor = fold_const_aggregate_ref (base);
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (ctor == NULL_TREE
+ || TREE_CODE (ctor) != CONSTRUCTOR
+ || !TREE_STATIC (ctor))
+ return NULL_TREE;
+
+ field = TREE_OPERAND (t, 1);
+
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
+ if (cfield == field
+ /* FIXME: Handle bit-fields. */
+ && ! DECL_BIT_FIELD (cfield))
+ return cval;
+ break;
+
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ {
+ tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0));
+ if (c && TREE_CODE (c) == COMPLEX_CST)
+ return fold_build1 (TREE_CODE (t), TREE_TYPE (t), c);
+ break;
+ }
+
+ default:
+ break;
+ }
+
+ return NULL_TREE;
+}
+
/* Evaluate statement STMT. */
-static value
+static prop_value_t
evaluate_stmt (tree stmt)
{
- value val;
- tree simplified;
- latticevalue likelyvalue = likely_value (stmt);
+ prop_value_t val;
+ tree simplified = NULL_TREE;
+ 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. */
simplified = ccp_fold (stmt);
/* If the statement is likely to have a VARYING result, then do not
bother folding the statement. */
- else if (likelyvalue == VARYING)
+ if (likelyvalue == VARYING)
simplified = get_rhs (stmt);
- /* Otherwise the statement is likely to have an UNDEFINED value and
- there will be nothing to do. */
- else
- simplified = NULL_TREE;
+ /* If the statement is an ARRAY_REF or COMPONENT_REF into constant
+ aggregates, extract the referenced constant. Otherwise the
+ statement is likely to have an UNDEFINED value, and there will be
+ nothing to do. Note that fold_const_aggregate_ref returns
+ NULL_TREE if the first case does not match. */
+ else if (!simplified)
+ simplified = fold_const_aggregate_ref (get_rhs (stmt));
if (simplified && is_gimple_min_invariant (simplified))
{
/* 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. */
+ if (likelyvalue == UNDEFINED)
+ val.lattice_val = likelyvalue;
+ else
+ val.lattice_val = 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 = GIMPLE_STMT_OPERAND (stmt, 0);
+ rhs = GIMPLE_STMT_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);
+ 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
+ && nval->mem_ref
+ && operand_equal_p (nval->mem_ref, rhs, 0))
+ 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 = GIMPLE_STMT_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_unary (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);
- }
- }
+ /* Otherwise, set the names in VDEF 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;
- 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);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- dump_immediate_uses (dump_file);
+ /* Mark VAL as stored in the LHS of this assignment. */
+ if (val.lattice_val == CONSTANT)
+ val.mem_ref = lhs;
- VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
+ /* Set the value of every VDEF to VAL. */
+ changed = false;
+ FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
+ {
+ /* See PR 29801. We may have VDEFs for read-only variables
+ (see the handling of unmodifiable variables in
+ add_virtual_operand); do not attempt to change their value. */
+ if (get_symbol_constant_value (SSA_NAME_VAR (vdef)) != NULL_TREE)
+ continue;
- /* 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);
+ 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);
-}
+/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
+ if it can determine which edge will be taken. Otherwise, return
+ SSA_PROP_VARYING. */
-/* Add a basic block to the worklist. */
-
-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)
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- /* 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 ();
+ /* If the statement is an assignment that produces a single
+ output value, evaluate its RHS to see if the lattice value of
+ its output has changed. */
+ return visit_assignment (stmt, output_p);
}
- else if (val.lattice_val == CONSTANT)
+ else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_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 STMT is a conditional branch, see if we can determine
+ which branch will be taken. */
+ return visit_cond_stmt (stmt, taken_edge_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))
- {
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
- }
+ /* 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");
- if (old->lattice_val != val.lattice_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)
{
- 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");
- }
-
- add_var_to_ssa_edges_worklist (var, val);
- *old = val;
+ 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;
-
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
- get_stmt_operands (stmt);
+ return SSA_PROP_VARYING;
+}
- uses = STMT_USE_OPS (stmt);
- for (i = 0; i < NUM_USES (uses); i++)
- {
- use_operand_p use = USE_OP_PTR (uses, i);
- value *val = get_value (USE_FROM_PTR (use));
- if (val->lattice_val == CONSTANT)
- {
- SET_USE (use, val->const_val);
- replaced = true;
- if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (use)))
- && replaced_addresses_p)
- *replaced_addresses_p = true;
- }
- }
+/* Main entry point for SSA Conditional Constant Propagation. */
- return replaced;
+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 ();
}
-/* 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)
+static unsigned int
+do_ssa_ccp (void)
{
- bool replaced = false;
- vuse_optype vuses;
- use_operand_p vuse;
- value *val;
-
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
+ execute_ssa_ccp (false);
+ return 0;
+}
- get_stmt_operands (stmt);
- vuses = STMT_VUSE_OPS (stmt);
+static bool
+gate_ccp (void)
+{
+ 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_update_smt_usage, /* 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 unsigned int
+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 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_update_smt_usage, /* 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 = fold_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 = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (var), val,
+ build_int_cst (TREE_TYPE (var), mask));
}
- return ((found_constant || (!uses && !vuses)) ? CONSTANT : VARYING);
+ return 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
if (!integer_zerop (elt_offset))
idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
- 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)));
+ return build4 (ARRAY_REF, orig_type, base, idx, min_idx,
+ size_int (tree_low_cst (elt_size, 1)
+ / (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);
+ t = build3 (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
nonzero offset into them. Recurse and hope for a valid match. */
if (base_is_ptr)
base = build1 (INDIRECT_REF, record_type, base);
- base = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
+ base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
if (t)
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. */
/* Fold away CONST_DECL to its value, if the type is scalar. */
if (TREE_CODE (base) == CONST_DECL
- && is_gimple_min_invariant (DECL_INITIAL (base)))
+ && ccp_decl_initial_min_invariant (DECL_INITIAL (base)))
return DECL_INITIAL (base);
/* Try folding *(&B+O) to B[X]. */
/* 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
if (TREE_CODE (min_idx) != INTEGER_CST)
break;
- array_idx = convert (TREE_TYPE (min_idx), array_idx);
+ array_idx = fold_convert (TREE_TYPE (min_idx), array_idx);
if (!integer_zerop (min_idx))
array_idx = int_const_binop (MINUS_EXPR, array_idx,
min_idx, 0);
}
/* Convert the index to a byte offset. */
- array_idx = convert (sizetype, array_idx);
+ array_idx = fold_convert (sizetype, array_idx);
array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
/* Update the operands for the next round, or for folding. */
{
if (TYPE_UNSIGNED (TREE_TYPE (op1)))
return NULL;
- op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
+ op1 = fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1);
/* ??? In theory fold should always produce another integer. */
- if (TREE_CODE (op1) != INTEGER_CST)
+ if (op1 == NULL || TREE_CODE (op1) != INTEGER_CST)
return NULL;
}
return t;
}
+/* For passing state through walk_tree into fold_stmt_r and its
+ children. */
+
+struct fold_stmt_r_data
+{
+ bool *changed_p;
+ bool *inside_addr_expr_p;
+};
+
/* Subroutine of fold_stmt called via walk_tree. We perform several
simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
static tree
fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
{
- bool *changed_p = data;
+ struct fold_stmt_r_data *fold_stmt_r_data = (struct fold_stmt_r_data *) data;
+ bool *inside_addr_expr_p = fold_stmt_r_data->inside_addr_expr_p;
+ bool *changed_p = fold_stmt_r_data->changed_p;
tree expr = *expr_p, t;
/* ??? It'd be nice if walk_tree had a pre-order option. */
integer_zero_node);
break;
- /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
+ /* ??? Could handle more ARRAY_REFs here, as a variant of INDIRECT_REF.
We'd only want to bother decomposing an existing ARRAY_REF if
the base array is found to have another offset contained within.
Otherwise we'd be wasting time. */
+ case ARRAY_REF:
+ /* If we are not processing expressions found within an
+ ADDR_EXPR, then we can fold constant array references. */
+ if (!*inside_addr_expr_p)
+ t = fold_read_from_constant_string (expr);
+ else
+ t = NULL;
+ break;
case ADDR_EXPR:
+ *inside_addr_expr_p = true;
t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
+ *inside_addr_expr_p = false;
if (t)
return t;
*walk_subtrees = 0;
/* Set TREE_INVARIANT properly so that the value is properly
considered constant, and so gets propagated as expected. */
if (*changed_p)
- recompute_tree_invarant_for_addr_expr (expr);
+ recompute_tree_invariant_for_addr_expr (expr);
return NULL_TREE;
case PLUS_EXPR:
}
break;
+ case TARGET_MEM_REF:
+ t = maybe_fold_tmr (expr);
+ break;
+
+ case COND_EXPR:
+ if (COMPARISON_CLASS_P (TREE_OPERAND (expr, 0)))
+ {
+ tree op0 = TREE_OPERAND (expr, 0);
+ tree tem = fold_binary (TREE_CODE (op0), TREE_TYPE (op0),
+ TREE_OPERAND (op0, 0),
+ TREE_OPERAND (op0, 1));
+ if (tem && set_rhs (expr_p, tem))
+ {
+ t = *expr_p;
+ break;
+ }
+ }
+ return NULL_TREE;
+
default:
return NULL_TREE;
}
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, maximum string length or maximum value of
+ ARG in LENGTH.
+ If ARG is an SSA name variable, follow its use-def chains. If LENGTH
+ is not NULL and, for TYPE == 0, its value is not equal to the length
+ we determine or if we are unable to determine the length or value,
+ return false. VISITED is a bitmap of visited variables.
+ TYPE is 0 if string length should be returned, 1 for maximum string
+ length and 2 for maximum value ARG can have. */
static bool
-set_rhs (tree *stmt_p, tree expr)
+get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
{
- 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)
+ if (type == 2)
{
- TREE_OPERAND (stmt, 0) = expr;
- break;
+ val = arg;
+ if (TREE_CODE (val) != INTEGER_CST
+ || tree_int_cst_sgn (val) < 0)
+ return false;
}
- 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;
-
- 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;
- }
+ else
+ val = c_strlen (arg, 1);
+ if (!val)
+ 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++)
+ if (*length)
+ {
+ if (type > 0)
{
- tree var = V_MUST_DEF_OP (v_must_defs, i);
- if (TREE_CODE (var) == SSA_NAME)
- SSA_NAME_DEF_STMT (var) = *stmt_p;
+ if (TREE_CODE (*length) != INTEGER_CST
+ || TREE_CODE (val) != INTEGER_CST)
+ return false;
+
+ if (tree_int_cst_lt (*length, val))
+ *length = val;
+ return true;
}
+ else if (simple_cst_equal (val, *length) != 1)
+ return false;
}
- break;
- }
- return true;
-}
+ *length = val;
+ 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));
-/* Return a default value for variable VAR using the following rules:
+ var = arg;
+ def_stmt = SSA_NAME_DEF_STMT (var);
- 1- Function arguments are considered VARYING.
-
- 2- Global and static variables that are declared constant are
- considered CONSTANT.
+ switch (TREE_CODE (def_stmt))
+ {
+ case GIMPLE_MODIFY_STMT:
+ {
+ tree rhs;
- 3- Any other virtually defined variable is considered UNKNOWN_VAL.
+ /* The RHS of the statement defining VAR must either have a
+ constant length or come from another SSA_NAME with a constant
+ length. */
+ rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+ STRIP_NOPS (rhs);
+ return get_maxval_strlen (rhs, length, visited, type);
+ }
- 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_maxval_strlen (arg, length, visited, type))
+ 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;
}
static tree
ccp_fold_builtin (tree stmt, tree fn)
{
- tree result, strlen_val[2];
+ tree result, val[3];
tree callee, arglist, a;
- int strlen_arg, i;
+ int arg_mask, i, type;
bitmap visited;
bool ignore;
- ignore = TREE_CODE (stmt) != MODIFY_EXPR;
+ ignore = TREE_CODE (stmt) != GIMPLE_MODIFY_STMT;
/* 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)
- STRIP_NOPS (result);
- return result;
- }
+ {
+ if (ignore)
+ STRIP_NOPS (result);
+ return result;
+ }
/* 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;
case BUILT_IN_STRLEN:
case BUILT_IN_FPUTS:
case BUILT_IN_FPUTS_UNLOCKED:
- strlen_arg = 1;
+ arg_mask = 1;
+ type = 0;
break;
case BUILT_IN_STRCPY:
case BUILT_IN_STRNCPY:
- strlen_arg = 2;
+ arg_mask = 2;
+ type = 0;
+ break;
+ case BUILT_IN_MEMCPY_CHK:
+ case BUILT_IN_MEMPCPY_CHK:
+ case BUILT_IN_MEMMOVE_CHK:
+ case BUILT_IN_MEMSET_CHK:
+ case BUILT_IN_STRNCPY_CHK:
+ arg_mask = 4;
+ type = 2;
+ break;
+ case BUILT_IN_STRCPY_CHK:
+ case BUILT_IN_STPCPY_CHK:
+ arg_mask = 2;
+ type = 1;
+ break;
+ case BUILT_IN_SNPRINTF_CHK:
+ case BUILT_IN_VSNPRINTF_CHK:
+ arg_mask = 2;
+ type = 2;
break;
default:
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));
+ memset (val, 0, sizeof (val));
for (i = 0, a = arglist;
- strlen_arg;
- i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
- if (strlen_arg & 1)
+ arg_mask;
+ i++, arg_mask >>= 1, a = TREE_CHAIN (a))
+ if (arg_mask & 1)
{
bitmap_clear (visited);
- if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
- strlen_val[i] = NULL_TREE;
+ if (!get_maxval_strlen (TREE_VALUE (a), &val[i], visited, type))
+ val[i] = NULL_TREE;
}
- BITMAP_XFREE (visited);
+ BITMAP_FREE (visited);
result = NULL_TREE;
switch (DECL_FUNCTION_CODE (callee))
{
case BUILT_IN_STRLEN:
- if (strlen_val[0])
+ if (val[0])
{
- tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]);
+ tree new = fold_convert (TREE_TYPE (fn), val[0]);
/* If the result is not a valid gimple value, or not a cast
of a valid gimple value, then we can not use the result. */
break;
case BUILT_IN_STRCPY:
- if (strlen_val[1] && is_gimple_val (strlen_val[1]))
- result = fold_builtin_strcpy (fn, strlen_val[1]);
+ if (val[1] && is_gimple_val (val[1]))
+ result = fold_builtin_strcpy (callee, arglist, 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]);
+ if (val[1] && is_gimple_val (val[1]))
+ result = fold_builtin_strncpy (callee, arglist, val[1]);
break;
case BUILT_IN_FPUTS:
result = fold_builtin_fputs (arglist,
- TREE_CODE (stmt) != MODIFY_EXPR, 0,
- strlen_val[0]);
+ TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 0,
+ val[0]);
break;
case BUILT_IN_FPUTS_UNLOCKED:
result = fold_builtin_fputs (arglist,
- TREE_CODE (stmt) != MODIFY_EXPR, 1,
- strlen_val[0]);
+ TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 1,
+ val[0]);
+ break;
+
+ case BUILT_IN_MEMCPY_CHK:
+ case BUILT_IN_MEMPCPY_CHK:
+ case BUILT_IN_MEMMOVE_CHK:
+ case BUILT_IN_MEMSET_CHK:
+ if (val[2] && is_gimple_val (val[2]))
+ result = fold_builtin_memory_chk (callee, arglist, val[2], ignore,
+ DECL_FUNCTION_CODE (callee));
+ break;
+
+ case BUILT_IN_STRCPY_CHK:
+ case BUILT_IN_STPCPY_CHK:
+ if (val[1] && is_gimple_val (val[1]))
+ result = fold_builtin_stxcpy_chk (callee, arglist, val[1], ignore,
+ DECL_FUNCTION_CODE (callee));
+ break;
+
+ case BUILT_IN_STRNCPY_CHK:
+ if (val[2] && is_gimple_val (val[2]))
+ result = fold_builtin_strncpy_chk (arglist, val[2]);
+ break;
+
+ case BUILT_IN_SNPRINTF_CHK:
+ case BUILT_IN_VSNPRINTF_CHK:
+ if (val[1] && is_gimple_val (val[1]))
+ result = fold_builtin_snprintf_chk (arglist, val[1],
+ DECL_FUNCTION_CODE (callee));
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 to 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;
+ struct fold_stmt_r_data fold_stmt_r_data;
+ bool changed = false;
+ bool inside_addr_expr = false;
- if (*length && simple_cst_equal (val, *length) != 1)
- return false;
+ fold_stmt_r_data.changed_p = &changed;
+ fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
- *length = val;
+ 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, &fold_stmt_r_data, 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. Also
+ CALL_EXPR_RETURN_SLOT_OPT needs to be handled correctly and
+ copied, fold_ternary does not have not information. */
+ 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;
- }
+/* Perform the minimal folding on statement STMT. Only operations like
+ *&x created by constant propagation are handled. The statement cannot
+ be replaced with a new one. */
- default:
- break;
+bool
+fold_stmt_inplace (tree stmt)
+{
+ tree old_stmt = stmt, rhs, new_rhs;
+ struct fold_stmt_r_data fold_stmt_r_data;
+ bool changed = false;
+ bool inside_addr_expr = false;
+
+ fold_stmt_r_data.changed_p = &changed;
+ fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
+
+ walk_tree (&stmt, fold_stmt_r, &fold_stmt_r_data, NULL);
+ gcc_assert (stmt == old_stmt);
+
+ rhs = get_rhs (stmt);
+ if (!rhs || rhs == stmt)
+ return changed;
+
+ new_rhs = fold (rhs);
+ STRIP_USELESS_TYPE_CONVERSION (new_rhs);
+ if (new_rhs == rhs)
+ return changed;
+
+ changed |= set_rhs (&stmt, new_rhs);
+ gcc_assert (stmt == old_stmt);
+
+ return changed;
+}
+\f
+/* Convert EXPR into a GIMPLE value suitable for substitution on the
+ RHS of an assignment. Insert the necessary statements before
+ iterator *SI_P.
+ When IGNORE is set, don't worry about the return value. */
+
+static tree
+convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr, bool ignore)
+{
+ tree_stmt_iterator ti;
+ tree stmt = bsi_stmt (*si_p);
+ tree tmp, stmts = NULL;
+
+ push_gimplify_context ();
+ if (ignore)
+ {
+ tmp = build_empty_stmt ();
+ gimplify_and_add (expr, &stmts);
}
+ else
+ tmp = get_initialized_tmp_var (expr, &stmts, NULL);
+ pop_gimplify_context (NULL);
+ if (EXPR_HAS_LOCATION (stmt))
+ annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
- return false;
+ /* 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_symbols_for_renaming (new_stmt);
+ 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
+static unsigned int
execute_fold_all_builtins (void)
{
+ bool cfg_changed = false;
basic_block bb;
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
- for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+ for (i = bsi_start (bb); !bsi_end_p (i); )
{
tree *stmtp = bsi_stmt_ptr (i);
+ tree old_stmt = *stmtp;
tree call = get_rhs (*stmtp);
tree callee, result;
+ enum built_in_function fcode;
if (!call || TREE_CODE (call) != CALL_EXPR)
- continue;
+ {
+ bsi_next (&i);
+ continue;
+ }
callee = get_callee_fndecl (call);
if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
- continue;
+ {
+ bsi_next (&i);
+ continue;
+ }
+ fcode = DECL_FUNCTION_CODE (callee);
result = ccp_fold_builtin (*stmtp, call);
if (!result)
break;
default:
+ bsi_next (&i);
continue;
}
print_generic_stmt (dump_file, *stmtp, dump_flags);
}
- if (set_rhs (stmtp, result))
- modify_stmt (*stmtp);
+ push_stmt_changes (stmtp);
+
+ if (!set_rhs (stmtp, result))
+ {
+ result = convert_to_gimple_builtin (&i, result,
+ TREE_CODE (old_stmt)
+ != GIMPLE_MODIFY_STMT);
+ if (result)
+ {
+ bool ok = set_rhs (stmtp, result);
+ gcc_assert (ok);
+ }
+ }
+
+ pop_stmt_changes (stmtp);
+
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp)
+ && tree_purge_dead_eh_edges (bb))
+ cfg_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_stmt (dump_file, *stmtp, dump_flags);
fprintf (dump_file, "\n");
}
+
+ /* Retry the same statement if it changed into another
+ builtin, there might be new opportunities now. */
+ call = get_rhs (*stmtp);
+ if (!call || TREE_CODE (call) != CALL_EXPR)
+ {
+ bsi_next (&i);
+ continue;
+ }
+ callee = get_callee_fndecl (call);
+ if (!callee
+ || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
+ || DECL_FUNCTION_CODE (callee) == fcode)
+ bsi_next (&i);
}
}
+
+ /* Delete unreachable blocks. */
+ if (cfg_changed)
+ cleanup_tree_cfg ();
+ return 0;
}
+
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"