/* Conditional constant propagation pass for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
+ Free Software Foundation, Inc.
Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
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 -> This is the default starting value. V_i
+ has not been processed yet.
+
+ UNDEFINED -> V_i is a local variable whose definition
+ has not been processed yet. Therefore we
+ don't yet know if its value is a constant
+ or not.
+
+ CONSTANT -> V_i has been found to hold a constant
+ value C.
+
+ VARYING -> V_i cannot take a constant value, or if it
+ does, it is not possible to determine it
+ at compile time.
+
+ The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
+
+ 1- In ccp_visit_stmt, we are interested in assignments whose RHS
+ evaluates into a constant and conditional jumps whose predicate
+ evaluates into a boolean true or false. When an assignment of
+ the form V_i = CONST is found, V_i's lattice value is set to
+ CONSTANT and CONST is associated with it. This causes the
+ propagation engine to add all the SSA edges coming out the
+ assignment into the worklists, so that statements that use V_i
+ can be visited.
+
+ If the statement is a conditional with a constant predicate, we
+ mark the outgoing edges as executable or not executable
+ depending on the predicate's value. This is then used when
+ visiting PHI nodes to know when a PHI argument can be ignored.
+
+
+ 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
+ same constant C, then the LHS of the PHI is set to C. This
+ evaluation is known as the "meet operation". Since one of the
+ goals of this evaluation is to optimistically return constant
+ values as often as possible, it uses two main short cuts:
+
+ - If an argument is flowing in through a non-executable edge, it
+ is ignored. This is useful in cases like this:
+
+ if (PRED)
+ a_9 = 3;
+ else
+ a_10 = 100;
+ a_11 = PHI (a_9, a_10)
+
+ If PRED is known to always evaluate to false, then we can
+ assume that a_11 will always take its value from a_10, meaning
+ that instead of consider it VARYING (a_9 and a_10 have
+ different values), we can consider it CONSTANT 100.
+
+ - If an argument has an UNDEFINED value, then it does not affect
+ the outcome of the meet operation. If a variable V_i has an
+ UNDEFINED value, it means that either its defining statement
+ hasn't been visited yet or V_i has no defining statement, in
+ which case the original symbol 'V' is being used
+ uninitialized. Since 'V' is a local variable, the compiler
+ may assume any initial value for it.
+
+
+ After propagation, every variable V_i that ends up with a lattice
+ value of CONSTANT will have the associated constant value in the
+ array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
+ final substitution and folding.
+
+
+ Constant propagation in stores and loads (STORE-CCP)
+ ----------------------------------------------------
+
+ While CCP has all the logic to propagate constants in GIMPLE
+ registers, it is missing the ability to associate constants with
+ stores and loads (i.e., pointer dereferences, structures and
+ global/aliased variables). We don't keep loads and stores in
+ SSA, but we do build a factored use-def web for them (in the
+ virtual operands).
+
+ For instance, consider the following code fragment:
+
+ struct A a;
+ const int B = 42;
+
+ void foo (int i)
+ {
+ if (i > 10)
+ a.a = 42;
+ else
+ {
+ a.b = 21;
+ a.a = a.b + 21;
+ }
+
+ if (a.a != B)
+ never_executed ();
+ }
+
+ We should be able to deduce that the predicate 'a.a != B' is always
+ false. To achieve this, we associate constant values to the SSA
+ names in the V_MAY_DEF and V_MUST_DEF operands for each store.
+ Additionally, since we also glob partial loads/stores with the base
+ symbol, we also keep track of the memory reference where the
+ constant value was stored (in the MEM_REF field of PROP_VALUE_T).
+ For instance,
+
+ # a_5 = V_MAY_DEF <a_4>
+ a.a = 2;
+
+ # VUSE <a_5>
+ x_3 = a.b;
+
+ In the example above, CCP will associate value '2' with 'a_5', but
+ it would be wrong to replace the load from 'a.b' with '2', because
+ '2' had been stored into a.a.
+
+ To support STORE-CCP, it is necessary to add a new value to the
+ constant propagation lattice. When evaluating a load for a memory
+ reference we can no longer assume a value of UNDEFINED if we
+ haven't seen a preceding store to the same memory location.
+ Consider, for instance global variables:
+
+ int A;
+
+ foo (int i)
+ {
+ if (i_3 > 10)
+ A_4 = 3;
+ # A_5 = PHI (A_4, A_2);
+
+ # VUSE <A_5>
+ A.0_6 = A;
+
+ return A.0_6;
+ }
+
+ The value of A_2 cannot be assumed to be UNDEFINED, as it may have
+ been defined outside of foo. If we were to assume it UNDEFINED, we
+ would erroneously optimize the above into 'return 3;'. Therefore,
+ when doing STORE-CCP, we introduce a fifth lattice value
+ (UNKNOWN_VAL), which overrides any other value when computing the
+ meet operation in PHI nodes.
-/* Conditional constant propagation.
+ 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 "ggc.h"
#include "basic-block.h"
#include "output.h"
-#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
+#include "target.h"
/* Possible lattice values. */
UNKNOWN_VAL,
CONSTANT,
VARYING
-} latticevalue;
-
-/* 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;
+} ccp_lattice_t;
-/* This is used to track the current value of each variable. */
-static value *value_vector;
+/* Array of propagated constant values. After propagation,
+ CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
+ the constant is held in an SSA name representing a memory store
+ (i.e., a V_MAY_DEF or V_MUST_DEF), CONST_VAL[I].MEM_REF will
+ contain the actual memory reference used to store (i.e., the LHS of
+ the assignment doing the store). */
+static prop_value_t *const_val;
+/* True if we are also propagating constants in stores and loads. */
+static bool do_store_ccp;
-/* Dump lattice value VAL to file OUTF prefixed by PREFIX. */
+/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
static void
-dump_lattice_value (FILE *outf, const char *prefix, value val)
+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;
break;
case CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
- print_generic_expr (outf, val.const_val, dump_flags);
+ print_generic_expr (outf, val.value, dump_flags);
break;
default:
gcc_unreachable ();
}
-/* Return a default value for variable VAR using the following rules:
+/* Print lattice value VAL to stderr. */
- 1- Function arguments are considered VARYING.
-
- 2- Global and static variables that are declared constant are
- considered CONSTANT.
+void debug_lattice_value (prop_value_t val);
+
+void
+debug_lattice_value (prop_value_t val)
+{
+ dump_lattice_value (stderr, "", val);
+ fprintf (stderr, "\n");
+}
- 3- Any other virtually defined variable is considered UNKNOWN_VAL.
- 4- Any other value is considered UNDEFINED. This is useful when
+/* Compute a default value for variable VAR and store it in the
+ CONST_VAL array. The following rules are used to get default
+ values:
+
+ 1- Global and static variables that are declared constant are
+ considered CONSTANT.
+
+ 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. */
+ constants to be propagated.
-static value
-get_default_value (tree var)
-{
- value val;
- tree sym;
+ 3- If SSA_NAME_VALUE is set and it is a constant, its value is
+ used.
- if (TREE_CODE (var) == SSA_NAME)
- sym = SSA_NAME_VAR (var);
- else
- {
- gcc_assert (DECL_P (var));
- sym = var;
- }
+ 4- Variables defined by statements other than assignments and PHI
+ nodes are considered VARYING.
- val.lattice_val = UNDEFINED;
- val.const_val = NULL_TREE;
+ 5- Variables that are not GIMPLE registers are considered
+ UNKNOWN_VAL, which is really a stronger version of UNDEFINED.
+ It's used to avoid the short circuit evaluation implied by
+ UNDEFINED in ccp_lattice_meet. */
- if (TREE_CODE (var) == SSA_NAME
- && SSA_NAME_VALUE (var)
- && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
- {
- val.lattice_val = CONSTANT;
- val.const_val = SSA_NAME_VALUE (var);
- }
- else if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
+static prop_value_t
+get_default_value (tree var)
+{
+ tree sym = SSA_NAME_VAR (var);
+ prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE };
+
+ if (!do_store_ccp && !is_gimple_reg (var))
{
- /* Function arguments and volatile variables are considered VARYING. */
+ /* 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 (TREE_STATIC (sym))
+ else if (SSA_NAME_VALUE (var)
+ && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
{
- /* 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;
- }
+ val.lattice_val = CONSTANT;
+ val.value = SSA_NAME_VALUE (var);
}
- else if (!is_gimple_reg (sym))
+ else if (TREE_STATIC (sym)
+ && TREE_READONLY (sym)
+ && DECL_INITIAL (sym)
+ && is_gimple_min_invariant (DECL_INITIAL (sym)))
{
- val.const_val = NULL_TREE;
- val.lattice_val = UNKNOWN_VAL;
+ /* Globals and static variables declared 'const' take their
+ initial value. */
+ val.lattice_val = CONSTANT;
+ val.value = DECL_INITIAL (sym);
+ val.mem_ref = sym;
}
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)
+ 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. If we are
+ doing STORE-CCP, function arguments and non-register
+ variables are initially UNKNOWN_VAL, because we cannot
+ discard the value incoming from outside of this function
+ (see ccp_lattice_meet for details). */
+ if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL)
+ val.lattice_val = UNDEFINED;
+ else if (do_store_ccp)
+ val.lattice_val = UNKNOWN_VAL;
+ else
val.lattice_val = VARYING;
}
+ else if (TREE_CODE (stmt) == MODIFY_EXPR
+ || TREE_CODE (stmt) == PHI_NODE)
+ {
+ /* Any other variable defined by an assignment or a PHI node
+ is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a
+ GIMPLE register). */
+ val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL;
+ }
+ else
+ {
+ /* Otherwise, VAR will never take on a constant value. */
+ val.lattice_val = VARYING;
+ }
}
return val;
}
-/* Get the constant value associated with variable VAR. */
-
-static value *
-get_value (tree var)
-{
- value *val;
- gcc_assert (TREE_CODE (var) == SSA_NAME);
+/* Get the constant value associated with variable VAR. If
+ MAY_USE_DEFAULT_P is true, call get_default_value on variables that
+ have the lattice value UNINITIALIZED. */
- val = &value_vector[SSA_NAME_VERSION (var)];
- if (val->lattice_val == UNINITIALIZED)
+static prop_value_t *
+get_value (tree var, bool may_use_default_p)
+{
+ prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
+ if (may_use_default_p && val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
return val;
}
-/* Set the lattice value for variable VAR to VAL. Return true if VAL
- is different from VAR's previous value. */
+/* 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, value val)
+set_lattice_value (tree var, prop_value_t new_val)
{
- value *old = get_value (var);
-
- if (val.lattice_val == UNDEFINED)
- {
- /* CONSTANT->UNDEFINED is never a valid state transition. */
- gcc_assert (old->lattice_val != CONSTANT);
-
- /* UNKNOWN_VAL->UNDEFINED is never a valid state transition. */
- gcc_assert (old->lattice_val != UNKNOWN_VAL);
-
- /* VARYING->UNDEFINED is generally not a valid state transition,
- except for values which are initialized to VARYING. */
- gcc_assert (old->lattice_val != VARYING
- || get_default_value (var).lattice_val == VARYING);
- }
- else if (val.lattice_val == CONSTANT)
- /* VARYING -> CONSTANT is an invalid state transition, except
- for objects which start off in a VARYING state. */
- gcc_assert (old->lattice_val != VARYING
- || get_default_value (var).lattice_val == VARYING);
-
- /* If the constant for VAR has changed, then this VAR is really varying. */
- if (old->lattice_val == CONSTANT
- && val.lattice_val == CONSTANT
- && !simple_cst_equal (old->const_val, val.const_val))
- {
- val.lattice_val = VARYING;
- val.const_val = NULL_TREE;
- }
-
- if (old->lattice_val != val.lattice_val)
+ prop_value_t *old_val = get_value (var, false);
+
+ /* Lattice transitions must always be monotonically increasing in
+ value. We allow two exceptions:
+
+ 1- If *OLD_VAL and NEW_VAL are the same, return false to
+ inform the caller that this was a non-transition.
+
+ 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true),
+ allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a
+ special type of UNDEFINED state which prevents the short
+ circuit evaluation of PHI arguments (see ccp_visit_phi_node
+ and ccp_lattice_meet). */
+ gcc_assert (old_val->lattice_val <= new_val.lattice_val
+ || (old_val->lattice_val == new_val.lattice_val
+ && old_val->value == new_val.value
+ && old_val->mem_ref == new_val.mem_ref)
+ || (do_store_ccp
+ && old_val->lattice_val == CONSTANT
+ && new_val.lattice_val == UNKNOWN_VAL));
+
+ if (old_val->lattice_val != new_val.lattice_val)
{
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");
+ dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
+ fprintf (dump_file, ". %sdding SSA edges to worklist.\n",
+ new_val.lattice_val != UNDEFINED ? "A" : "Not a");
}
- *old = val;
- return true;
+ *old_val = new_val;
+
+ /* Transitions UNINITIALIZED -> UNDEFINED are never interesting
+ for propagation purposes. In these cases return false to
+ avoid doing useless work. */
+ return (new_val.lattice_val != UNDEFINED);
}
return false;
}
-/* 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);
-}
-
-
-/* Return the likely latticevalue for STMT.
+/* Return the likely CCP lattice value for STMT.
If STMT has no operands, then return CONSTANT.
Else return VARYING. */
-static latticevalue
+static ccp_lattice_t
likely_value (tree stmt)
{
- vuse_optype vuses;
- int found_constant = 0;
+ bool found_constant;
stmt_ann_t ann;
tree use;
ssa_op_iter iter;
- /* If the statement makes aliased loads or has volatile operands, it
- won't fold to a constant value. */
ann = stmt_ann (stmt);
- if (ann->makes_aliased_loads || ann->has_volatile_ops)
+
+ /* 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
+ && (ann->makes_aliased_stores
+ || ann->makes_aliased_loads
+ || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
return VARYING;
- /* A CALL_EXPR is assumed to be varying. This may be overly conservative,
- in the presence of const and pure calls. */
+
+ /* 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;
- get_stmt_operands (stmt);
+ /* Anything other than assignments and conditional jumps are not
+ interesting for CCP. */
+ if (TREE_CODE (stmt) != MODIFY_EXPR
+ && TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
+ return VARYING;
+
+ if (is_gimple_min_invariant (get_rhs (stmt)))
+ return CONSTANT;
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ found_constant = false;
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
{
- value *val = get_value (use);
+ prop_value_t *val = get_value (use, true);
- if (val->lattice_val == UNDEFINED)
- return UNDEFINED;
+ if (val->lattice_val == VARYING)
+ return VARYING;
- if (val->lattice_val == CONSTANT)
- found_constant = 1;
- }
-
- vuses = VUSE_OPS (ann);
-
- if (NUM_VUSES (vuses))
- {
- tree vuse = VUSE_OP (vuses, 0);
- value *val = get_value (vuse);
-
if (val->lattice_val == UNKNOWN_VAL)
- return UNKNOWN_VAL;
-
- /* There should be no VUSE operands that are UNDEFINED. */
- gcc_assert (val->lattice_val != UNDEFINED);
-
+ {
+ /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */
+ gcc_assert (do_store_ccp);
+ return UNKNOWN_VAL;
+ }
+
if (val->lattice_val == CONSTANT)
- found_constant = 1;
+ found_constant = true;
}
- return ((found_constant || (!USE_OPS (ann) && !vuses)) ? CONSTANT : VARYING);
-}
-
-
-/* Function indicating whether we ought to include information for VAR
- when calculating immediate uses. */
+ if (found_constant
+ || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)
+ || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
+ return CONSTANT;
-static bool
-need_imm_uses_for (tree var)
-{
- return get_value (var)->lattice_val != VARYING;
+ return UNDEFINED;
}
ccp_initialize (void)
{
basic_block bb;
- sbitmap is_may_def;
-
- value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
- memset (value_vector, 0, num_ssa_names * sizeof (value));
- /* Set of SSA_NAMEs that are defined by a V_MAY_DEF. */
- is_may_def = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (is_may_def);
+ const_val = xmalloc (num_ssa_names * sizeof (*const_val));
+ memset (const_val, 0, num_ssa_names * sizeof (*const_val));
/* Initialize simulation flags for PHI nodes and statements. */
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
- /* Mark all V_MAY_DEF operands VARYING. */
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
bool is_varying = false;
tree stmt = bsi_stmt (i);
- ssa_op_iter iter;
- tree def;
- get_stmt_operands (stmt);
+ if (likely_value (stmt) == VARYING)
- /* Get the default value for each DEF and V_MUST_DEF. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter,
- (SSA_OP_DEF | SSA_OP_VMUSTDEF))
{
- if (get_value (def)->lattice_val == VARYING)
+ tree def;
+ ssa_op_iter iter;
+
+ /* If the statement will not produce a constant, mark
+ all its outputs VARYING. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
+ get_value (def, false)->lattice_val = VARYING;
+
+ /* Never mark conditional jumps with DONT_SIMULATE_AGAIN,
+ otherwise the propagator will never add the outgoing
+ control edges. */
+ if (TREE_CODE (stmt) != COND_EXPR
+ && TREE_CODE (stmt) != SWITCH_EXPR)
is_varying = true;
}
- /* Mark all V_MAY_DEF operands VARYING. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
- {
- get_value (def)->lattice_val = VARYING;
- SET_BIT (is_may_def, SSA_NAME_VERSION (def));
- }
-
- /* Statements other than MODIFY_EXPR, COND_EXPR and
- SWITCH_EXPR are not interesting for constant propagation.
- Mark them VARYING. */
- if (TREE_CODE (stmt) != MODIFY_EXPR
- && TREE_CODE (stmt) != COND_EXPR
- && TREE_CODE (stmt) != SWITCH_EXPR)
- is_varying = true;
-
DONT_SIMULATE_AGAIN (stmt) = is_varying;
}
}
/* Now process PHI nodes. */
FOR_EACH_BB (bb)
{
- tree phi, var;
- int x;
-
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- value *val = get_value (PHI_RESULT (phi));
-
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
- {
- var = PHI_ARG_DEF (phi, x);
-
- /* If one argument has a V_MAY_DEF, the result is
- VARYING. */
- if (TREE_CODE (var) == SSA_NAME)
- {
- if (TEST_BIT (is_may_def, SSA_NAME_VERSION (var)))
- {
- val->lattice_val = VARYING;
- SET_BIT (is_may_def, SSA_NAME_VERSION (PHI_RESULT (phi)));
- break;
- }
- }
- }
-
- DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
- }
- }
-
- sbitmap_free (is_may_def);
-
- /* Compute immediate uses for variables we care about. */
- compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
-}
-
-
-/* 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_operand_p use;
- ssa_op_iter iter;
-
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
-
- get_stmt_operands (stmt);
-
- FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
- {
- tree tuse = USE_FROM_PTR (use);
- value *val = get_value (tuse);
-
- if (val->lattice_val != CONSTANT)
- continue;
-
- if (TREE_CODE (stmt) == ASM_EXPR
- && !may_propagate_copy_into_asm (tuse))
- continue;
-
- SET_USE (use, val->const_val);
-
- replaced = true;
- if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
- *replaced_addresses_p = true;
- }
-
- return replaced;
-}
-
-
-/* Replace the VUSE references in statement STMT with its immediate reaching
- definition. Return true if the reference was replaced. If
- REPLACED_ADDRESSES_P is given, it will be set to true if an address
- constant was replaced. */
-
-static bool
-replace_vuse_in (tree stmt, bool *replaced_addresses_p)
-{
- bool replaced = false;
- vuse_optype vuses;
- use_operand_p vuse;
- value *val;
-
- if (replaced_addresses_p)
- *replaced_addresses_p = false;
-
- get_stmt_operands (stmt);
-
- vuses = STMT_VUSE_OPS (stmt);
-
- if (NUM_VUSES (vuses) != 1)
- return false;
-
- vuse = VUSE_OP_PTR (vuses, 0);
- val = get_value (USE_FROM_PTR (vuse));
-
- if (val->lattice_val == CONSTANT
- && TREE_CODE (stmt) == MODIFY_EXPR
- && DECL_P (TREE_OPERAND (stmt, 1))
- && TREE_OPERAND (stmt, 1) == SSA_NAME_VAR (USE_FROM_PTR (vuse)))
- {
- 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;
-}
-
-
-/* Perform final substitution and folding. After this pass the program
- should still be in SSA form. */
-
-static void
-substitute_and_fold (void)
-{
- basic_block bb;
- unsigned int i;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file,
- "\nSubstituing constants and folding statements\n\n");
-
- /* Substitute constants in every statement of every basic block. */
- FOR_EACH_BB (bb)
- {
- 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;
+ tree arg;
+ prop_value_t *val = get_value (PHI_RESULT (phi), false);
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);
-
- /* Skip statements that have been folded already. */
- if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
- continue;
-
- /* Replace the statement with its folded version and mark it
- folded. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
- }
+ arg = PHI_ARG_DEF (phi, i);
- 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);
- /* If we folded a builtin function, we'll likely
- need to rename VDEFs. */
- if (replaced_address || changed)
+ if (TREE_CODE (arg) == SSA_NAME
+ && get_value (arg, false)->lattice_val == VARYING)
{
- mark_new_vars_to_rename (stmt, vars_to_rename);
- if (maybe_clean_eh_stmt (stmt))
- tree_purge_dead_eh_edges (bb);
+ val->lattice_val = VARYING;
+ break;
}
- else
- modify_stmt (stmt);
}
- 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 (phi) = (val->lattice_val == VARYING);
}
}
-
- /* And transfer what we learned from VALUE_VECTOR into the
- SSA_NAMEs themselves. This probably isn't terribly important
- since we probably constant propagated the values to their
- use sites above. */
- for (i = 0; i < num_ssa_names; i++)
- {
- tree name = ssa_name (i);
- value *value;
-
- if (!name)
- continue;
-
- value = get_value (name);
- if (value->lattice_val == CONSTANT
- && is_gimple_reg (name)
- && is_gimple_min_invariant (value->const_val))
- SSA_NAME_VALUE (name) = value->const_val;
- }
}
-/* Free allocated storage. */
+/* Do final substitution of propagated values, cleanup the flowgraph and
+ free allocated storage. */
static void
ccp_finalize (void)
{
/* Perform substitutions based on the known constant values. */
- substitute_and_fold ();
-
- /* Now cleanup any unreachable code. */
- cleanup_tree_cfg ();
+ substitute_and_fold (const_val, false);
- free (value_vector);
+ free (const_val);
}
+/* Compute the meet operator between *VAL1 and *VAL2. Store the result
+ in VAL1.
+
+ any M UNDEFINED = any
+ any M UNKNOWN_VAL = UNKNOWN_VAL
+ any M VARYING = VARYING
+ Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
+
+ Lattice values UNKNOWN_VAL and UNDEFINED are similar but have
+ different semantics at PHI nodes. Both values imply that we don't
+ know whether the variable is constant or not. However, UNKNOWN_VAL
+ values override all others. For instance, suppose that A is a
+ global variable:
+
+ +------+
+ | |
+ | / \
+ | / \
+ | | A_1 = 4
+ | \ /
+ | \ /
+ | A_3 = PHI (A_2, A_1)
+ | ... = A_3
+ | |
+ +----+
+
+ If the edge into A_2 is not executable, the first visit to A_3 will
+ yield the constant 4. But the second visit to A_3 will be with A_2
+ in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4
+ because A_2 may have been set in another function. If we had used
+ the lattice value UNDEFINED, we would have had wrongly concluded
+ that A_3 is 4. */
+
-/* 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
-ccp_lattice_meet (value val1, value val2)
+static void
+ccp_lattice_meet (prop_value_t *val1, prop_value_t *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)
+ if (val1->lattice_val == UNDEFINED)
{
- result.lattice_val = VARYING;
- result.const_val = NULL_TREE;
- return result;
+ /* UNDEFINED M any = any */
+ *val1 = *val2;
}
-
- /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
- if (val1.lattice_val == UNKNOWN_VAL
- || val2.lattice_val == UNKNOWN_VAL)
+ else if (val2->lattice_val == UNDEFINED)
{
- result.lattice_val = UNKNOWN_VAL;
- result.const_val = NULL_TREE;
- return result;
+ /* any M UNDEFINED = any
+ Nothing to do. VAL1 already contains the value we want. */
+ ;
}
+ else if (val1->lattice_val == UNKNOWN_VAL
+ || val2->lattice_val == UNKNOWN_VAL)
+ {
+ /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */
+ gcc_assert (do_store_ccp);
- /* 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)
+ /* any M UNKNOWN_VAL = UNKNOWN_VAL. */
+ val1->lattice_val = UNKNOWN_VAL;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
+ }
+ else if (val1->lattice_val == VARYING
+ || val2->lattice_val == VARYING)
{
- result.lattice_val = CONSTANT;
- result.const_val = val1.const_val;
+ /* any M VARYING = VARYING. */
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ val1->mem_ref = NULL_TREE;
+ }
+ else if (val1->lattice_val == CONSTANT
+ && val2->lattice_val == CONSTANT
+ && simple_cst_equal (val1->value, val2->value) == 1
+ && (!do_store_ccp
+ || (val1->mem_ref && val2->mem_ref
+ && operand_equal_p (val1->mem_ref, val2->mem_ref, 0))))
+ {
+ /* Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
+
+ 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;
}
/* 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
+ PHI node is determined calling ccp_lattice_meet with all the arguments
of the PHI node that are incoming via executable edges. */
static enum ssa_prop_result
ccp_visit_phi_node (tree phi)
{
- value new_val, *old_val;
int i;
+ prop_value_t *old_val, new_val;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, phi, dump_flags);
}
- old_val = get_value (PHI_RESULT (phi));
+ old_val = get_value (PHI_RESULT (phi), false);
switch (old_val->lattice_val)
{
case VARYING:
- return SSA_PROP_NOT_INTERESTING;
+ return SSA_PROP_VARYING;
case CONSTANT:
new_val = *old_val;
UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and
the new value is UNDEFINED, then we prevent the invalid
transition by not calling set_lattice_value. */
- new_val.lattice_val = UNDEFINED;
- new_val.const_val = NULL_TREE;
- break;
+ gcc_assert (do_store_ccp);
+
+ /* FALLTHRU */
case UNDEFINED:
case UNINITIALIZED:
new_val.lattice_val = UNDEFINED;
- new_val.const_val = NULL_TREE;
+ new_val.value = NULL_TREE;
+ new_val.mem_ref = NULL_TREE;
break;
default:
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
- /* Compute the meet operator over all the PHI arguments. */
+ /* 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))
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;
+ tree arg = PHI_ARG_DEF (phi, i);
+ prop_value_t arg_val;
- if (is_gimple_min_invariant (rdef))
+ if (is_gimple_min_invariant (arg))
{
- val.lattice_val = CONSTANT;
- val.const_val = rdef;
- rdef_val = &val;
+ arg_val.lattice_val = CONSTANT;
+ arg_val.value = arg;
+ arg_val.mem_ref = NULL_TREE;
}
else
- rdef_val = get_value (rdef);
+ arg_val = *(get_value (arg, true));
- new_val = ccp_lattice_meet (new_val, *rdef_val);
+ ccp_lattice_meet (&new_val, &arg_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);
+ print_generic_expr (dump_file, arg, dump_flags);
+ dump_lattice_value (dump_file, "\tValue: ", arg_val);
fprintf (dump_file, "\n");
}
}
/* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */
- if (old_val->lattice_val == UNKNOWN_VAL
+ if (do_store_ccp
+ && old_val->lattice_val == UNKNOWN_VAL
&& new_val.lattice_val == UNDEFINED)
return SSA_PROP_NOT_INTERESTING;
enum tree_code code = TREE_CODE (rhs);
enum tree_code_class kind = TREE_CODE_CLASS (code);
tree retval = NULL_TREE;
- vuse_optype vuses;
-
- vuses = STMT_VUSE_OPS (stmt);
- /* If the RHS is just a variable, then that variable must now have
- a constant value that we can return directly. */
if (TREE_CODE (rhs) == SSA_NAME)
- return get_value (rhs)->const_val;
- else if (DECL_P (rhs)
- && NUM_VUSES (vuses) == 1
- && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
- return get_value (VUSE_OP (vuses, 0))->const_val;
+ {
+ /* If the RHS is an SSA_NAME, return its known constant value,
+ if any. */
+ return get_value (rhs, true)->value;
+ }
+ else if (do_store_ccp && stmt_makes_single_load (stmt))
+ {
+ /* If the RHS is a memory load, see if the VUSEs associated with
+ it are a valid constant for that memory load. */
+ prop_value_t *val = get_value_loaded_by (stmt, const_val);
+ if (val && val->mem_ref
+ && operand_equal_p (val->mem_ref, rhs, 0))
+ return val->value;
+ else
+ return NULL_TREE;
+ }
/* Unary operators. Note that we know the single operand must
be a constant. So this should almost always return a
/* Simplify the operand down to a constant. */
if (TREE_CODE (op0) == SSA_NAME)
{
- value *val = get_value (op0);
+ prop_value_t *val = get_value (op0, true);
if (val->lattice_val == CONSTANT)
- op0 = get_value (op0)->const_val;
+ op0 = get_value (op0, true)->value;
}
- retval = nondestructive_fold_unary_to_constant (code,
- TREE_TYPE (rhs),
- op0);
-
- /* 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);
+ return fold_unary (code, TREE_TYPE (rhs), op0);
}
/* Binary and comparison operators. We know one or both of the
/* Simplify the operands down to constants when appropriate. */
if (TREE_CODE (op0) == SSA_NAME)
{
- value *val = get_value (op0);
+ prop_value_t *val = get_value (op0, true);
if (val->lattice_val == CONSTANT)
- op0 = val->const_val;
+ op0 = val->value;
}
if (TREE_CODE (op1) == SSA_NAME)
{
- value *val = get_value (op1);
+ prop_value_t *val = get_value (op1, true);
if (val->lattice_val == CONSTANT)
- op1 = val->const_val;
+ op1 = val->value;
}
- retval = nondestructive_fold_binary_to_constant (code,
- TREE_TYPE (rhs),
- op0, op1);
-
- /* 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 = xmalloc (sizeof (tree) * NUM_SSA_OPERANDS (stmt, SSA_OP_USE));
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+ orig[i++] = var;
/* Substitute operands with their values and try to fold. */
- replace_uses_in (stmt, NULL);
- retval = fold_builtin (rhs, false);
+ replace_uses_in (stmt, NULL, const_val);
+ fndecl = get_callee_fndecl (rhs);
+ arglist = TREE_OPERAND (rhs, 1);
+ retval = fold_builtin (fndecl, arglist, false);
/* Restore operands to their original form. */
- for (i = 0; i < NUM_USES (uses); i++)
- SET_USE_OP (uses, i, orig[i]);
+ i = 0;
+ FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE)
+ SET_USE (var_p, orig[i++]);
free (orig);
}
}
}
+/* 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_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, true))
+ && 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;
+ }
+
+ /* 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;
+ prop_value_t val;
tree simplified;
- latticevalue likelyvalue = likely_value (stmt);
+ ccp_lattice_t likelyvalue = likely_value (stmt);
+
+ val.mem_ref = NULL_TREE;
/* If the statement is likely to have a CONSTANT result, then try
to fold the statement to determine the constant value. */
bother folding the statement. */
else if (likelyvalue == VARYING)
simplified = get_rhs (stmt);
- /* Otherwise the statement is likely to have an UNDEFINED value and
- there will be nothing to do. */
+ /* 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
- simplified = NULL_TREE;
+ 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 || likelyvalue == UNKNOWN_VAL)
+ val.lattice_val = likelyvalue;
+ else
+ val.lattice_val = VARYING;
+
+ val.value = NULL_TREE;
}
return val;
/* Visit the assignment statement STMT. Set the value of its LHS to the
- value computed by the RHS and store LHS in *OUTPUT_P. */
+ 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). */
static enum ssa_prop_result
visit_assignment (tree stmt, tree *output_p)
{
- value val;
+ prop_value_t val;
tree lhs, rhs;
- vuse_optype vuses;
- v_must_def_optype v_must_defs;
+ enum ssa_prop_result retval;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
- vuses = STMT_VUSE_OPS (stmt);
- v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
-
- gcc_assert (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0);
- gcc_assert (NUM_V_MUST_DEFS (v_must_defs) == 1
- || TREE_CODE (lhs) == SSA_NAME);
-
- /* 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_RESULT (v_must_defs, 0);
- }
if (TREE_CODE (rhs) == SSA_NAME)
{
/* For a simple copy operation, we copy the lattice values. */
- value *nval = get_value (rhs);
+ prop_value_t *nval = get_value (rhs, true);
val = *nval;
}
- else if (DECL_P (rhs)
- && NUM_VUSES (vuses) == 1
- && rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
+ else if (do_store_ccp && stmt_makes_single_load (stmt))
{
- /* 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;
+ /* 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);
+
+ if (nval && nval->mem_ref
+ && operand_equal_p (nval->mem_ref, rhs, 0))
+ val = *nval;
+ else
+ val = evaluate_stmt (stmt);
}
else
- {
- /* Evaluate the statement. */
+ /* Evaluate the statement. */
val = evaluate_stmt (stmt);
- }
- /* FIXME: Hack. If this was a definition of a bitfield, we need to widen
+ /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant
+ value to be a VIEW_CONVERT_EXPR of the old constant value.
+
+ ??? 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 lhs = TREE_OPERAND (stmt, 0);
+ tree orig_lhs = TREE_OPERAND (stmt, 0);
+
+ if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR
+ && val.lattice_val == CONSTANT)
+ {
+ tree w = fold_build1 (VIEW_CONVERT_EXPR,
+ TREE_TYPE (TREE_OPERAND (orig_lhs, 0)),
+ val.value);
+
+ 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;
+ }
+ }
+
if (val.lattice_val == CONSTANT
- && TREE_CODE (lhs) == COMPONENT_REF
- && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
+ && TREE_CODE (orig_lhs) == COMPONENT_REF
+ && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1)))
{
- tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
+ tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1),
+ orig_lhs);
if (w && is_gimple_min_invariant (w))
- val.const_val = w;
+ val.value = w;
else
{
val.lattice_val = VARYING;
- val.const_val = NULL;
+ val.value = NULL_TREE;
+ val.mem_ref = NULL_TREE;
}
}
}
- /* 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;
+ retval = SSA_PROP_NOT_INTERESTING;
/* Set the lattice value of the statement's output. */
- if (set_lattice_value (lhs, val))
+ if (TREE_CODE (lhs) == SSA_NAME)
{
- *output_p = lhs;
- if (val.lattice_val == VARYING)
- return SSA_PROP_VARYING;
- else
- return SSA_PROP_INTERESTING;
+ /* 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;
+ }
}
- else
- return SSA_PROP_NOT_INTERESTING;
+ else if (do_store_ccp && stmt_makes_single_store (stmt))
+ {
+ /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
+ to the new constant value and mark the LHS as the memory
+ reference associated with VAL. */
+ ssa_op_iter i;
+ tree vdef;
+ bool changed;
+
+ /* Stores cannot take on an UNDEFINED value. */
+ if (val.lattice_val == UNDEFINED)
+ val.lattice_val = UNKNOWN_VAL;
+
+ /* Mark VAL as stored in the LHS of this assignment. */
+ val.mem_ref = lhs;
+
+ /* Set the value of every VDEF to VAL. */
+ changed = false;
+ FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
+ changed |= set_lattice_value (vdef, val);
+
+ /* Note that for propagation purposes, we are only interested in
+ visiting statements that load the exact same memory reference
+ stored here. Those statements will have the exact same list
+ of virtual uses, so it is enough to set the output of this
+ statement to be its first virtual definition. */
+ *output_p = first_vdef (stmt);
+ if (changed)
+ {
+ if (val.lattice_val == VARYING)
+ retval = SSA_PROP_VARYING;
+ else
+ retval = SSA_PROP_INTERESTING;
+ }
+ }
+
+ return retval;
}
static enum ssa_prop_result
visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
- value val;
+ prop_value_t val;
basic_block block;
block = bb_for_stmt (stmt);
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 = find_taken_edge (block, val.const_val);
+ *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
if (*taken_edge_p)
return SSA_PROP_INTERESTING;
else
static enum ssa_prop_result
ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
- stmt_ann_t ann;
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
tree def;
ssa_op_iter iter;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, "\nVisiting statement: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\nVisiting statement:\n");
+ print_generic_stmt (dump_file, stmt, dump_flags);
fprintf (dump_file, "\n");
}
- ann = stmt_ann (stmt);
-
- v_must_defs = V_MUST_DEF_OPS (ann);
- v_may_defs = V_MAY_DEF_OPS (ann);
- if (TREE_CODE (stmt) == MODIFY_EXPR
- && NUM_V_MAY_DEFS (v_may_defs) == 0
- && (NUM_V_MUST_DEFS (v_must_defs) == 1
- || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
{
/* If the statement is an assignment that produces a single
output value, evaluate its RHS to see if the lattice value of
/* Definitions made by statements other than assignments to
SSA_NAMEs represent unknown modifications to their outputs.
Mark them VARYING. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- def_to_varying (def);
-
- /* Mark all V_MAY_DEF operands VARYING. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
- def_to_varying (def);
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
+ {
+ prop_value_t v = { VARYING, NULL_TREE, NULL_TREE };
+ set_lattice_value (def, v);
+ }
return SSA_PROP_VARYING;
}
-/* Main entry point for SSA Conditional Constant Propagation.
-
- [ DESCRIBE MAIN ALGORITHM HERE ] */
+/* Main entry point for SSA Conditional Constant Propagation. */
static void
-execute_ssa_ccp (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 ();
}
+static void
+do_ssa_ccp (void)
+{
+ execute_ssa_ccp (false);
+}
+
+
static bool
gate_ccp (void)
{
{
"ccp", /* name */
gate_ccp, /* gate */
- execute_ssa_ccp, /* execute */
+ do_ssa_ccp, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_rename_vars
+ TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa
| TODO_ggc_collect | TODO_verify_ssa
| TODO_verify_stmts, /* todo_flags_finish */
0 /* letter */
};
+static void
+do_ssa_store_ccp (void)
+{
+ /* If STORE-CCP is not enabled, we just run regular CCP. */
+ execute_ssa_ccp (flag_tree_store_ccp != 0);
+}
+
+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;
+}
+
+
+struct tree_opt_pass pass_store_ccp =
+{
+ "store_ccp", /* name */
+ gate_store_ccp, /* gate */
+ do_ssa_store_ccp, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_STORE_CCP, /* tv_id */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_update_ssa
+ | TODO_ggc_collect | TODO_verify_ssa
+ | TODO_cleanup_cfg
+ | TODO_verify_stmts, /* todo_flags_finish */
+ 0 /* letter */
+};
+
/* 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. */
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_cst (NULL_TREE, mask)));
+ wide_val = fold_build2 (BIT_AND_EXPR, TREE_TYPE (var), val,
+ build_int_cst (TREE_TYPE (var), mask));
}
else
{
for (i = 0, mask = 0; i < (var_size - field_size); i++)
mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
- wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
- fold_convert (TREE_TYPE (var),
- build_int_cst (NULL_TREE, mask)));
+ wide_val = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (var), val,
+ build_int_cst (TREE_TYPE (var), mask));
}
- return fold (wide_val);
+ return wide_val;
}
continue;
field_type = TREE_TYPE (f);
- if (cmp < 0)
- {
- /* Don't care about offsets into the middle of scalars. */
- if (!AGGREGATE_TYPE_P (field_type))
- continue;
-
- /* Check for array at the end of the struct. This is often
- used as for flexible array members. We should be able to
- turn this into an array access anyway. */
- if (TREE_CODE (field_type) == ARRAY_TYPE)
- tail_array_field = f;
-
- /* Check the end of the field against the offset. */
- if (!DECL_SIZE_UNIT (f)
- || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
- continue;
- t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
- if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
- continue;
-
- /* If we matched, then set offset to the displacement into
- this field. */
- offset = t;
- }
/* Here we exactly match the offset being checked. If the types match,
then we can return that field. */
- else if (lang_hooks.types_compatible_p (orig_type, field_type))
+ if (cmp == 0
+ && lang_hooks.types_compatible_p (orig_type, field_type))
{
if (base_is_ptr)
base = build1 (INDIRECT_REF, record_type, base);
t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
return t;
}
+
+ /* Don't care about offsets into the middle of scalars. */
+ if (!AGGREGATE_TYPE_P (field_type))
+ continue;
- /* Don't care about type-punning of scalars. */
- else if (!AGGREGATE_TYPE_P (field_type))
- return NULL_TREE;
+ /* Check for array at the end of the struct. This is often
+ used as for flexible array members. We should be able to
+ turn this into an array access anyway. */
+ if (TREE_CODE (field_type) == ARRAY_TYPE)
+ tail_array_field = f;
+ /* Check the end of the field against the offset. */
+ if (!DECL_SIZE_UNIT (f)
+ || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
+ continue;
+ t = int_const_binop (MINUS_EXPR, offset, field_offset, 1);
+ if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
+ continue;
+
+ /* If we matched, then set offset to the displacement into
+ this field. */
+ offset = t;
goto found;
}
f = tail_array_field;
field_type = TREE_TYPE (f);
+ offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
found:
/* If we get here, we've got an aggregate field, and a possibly
substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
are sometimes added. */
base = fold (base);
- STRIP_NOPS (base);
+ STRIP_TYPE_NOPS (base);
TREE_OPERAND (expr, 0) = base;
/* One possibility is that the address reduces to a string constant. */
/* We can get here for out-of-range string constant accesses,
such as "_"[3]. Bail out of the entire substitution search
and arrange for the entire statement to be replaced by a
- call to __builtin_trap. In all likelyhood this will all be
+ call to __builtin_trap. In all likelihood this will all be
constant-folded away, but in the meantime we can't leave with
something that get_expr_operands can't understand. */
&& TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
{
/* FIXME: Except that this causes problems elsewhere with dead
- code not being deleted, and we abort in the rtl expanders
+ code not being deleted, and we die in the rtl expanders
because we failed to remove some ssa_name. In the meantime,
just return zero. */
/* FIXME2: This condition should be signaled by
{
if (TYPE_UNSIGNED (TREE_TYPE (op1)))
return NULL;
- op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
+ op1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (op1), op1);
/* ??? In theory fold should always produce another integer. */
if (TREE_CODE (op1) != INTEGER_CST)
return NULL;
return t;
}
-
/* Subroutine of fold_stmt called via walk_tree. We perform several
simplifications of EXPR_P, mostly having to do with pointer arithmetic. */
}
break;
+ case TARGET_MEM_REF:
+ t = maybe_fold_tmr (expr);
+ break;
+
default:
return NULL_TREE;
}
}
-/* 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. */
+/* 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
-get_strlen (tree arg, tree *length, bitmap visited)
+get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
{
tree var, def_stmt, val;
if (TREE_CODE (arg) != SSA_NAME)
{
- val = c_strlen (arg, 1);
+ if (type == 2)
+ {
+ val = arg;
+ if (TREE_CODE (val) != INTEGER_CST
+ || tree_int_cst_sgn (val) < 0)
+ return false;
+ }
+ else
+ val = c_strlen (arg, 1);
if (!val)
return false;
- if (*length && simple_cst_equal (val, *length) != 1)
- return false;
+ if (*length)
+ {
+ if (type > 0)
+ {
+ 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;
+ }
*length = val;
return true;
{
case MODIFY_EXPR:
{
- tree len, rhs;
-
+ tree 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);
-
- /* See if the RHS is a constant length. */
- len = c_strlen (rhs, 1);
- if (len)
- {
- if (*length && simple_cst_equal (len, *length) != 1)
- return false;
-
- *length = len;
- return true;
- }
-
- break;
+ return get_maxval_strlen (rhs, length, visited, type);
}
case PHI_NODE:
if (arg == PHI_RESULT (def_stmt))
continue;
- if (!get_strlen (arg, length, visited))
+ if (!get_maxval_strlen (arg, length, visited, type))
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;
/* 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]);
+ val[0]);
break;
case BUILT_IN_FPUTS_UNLOCKED:
result = fold_builtin_fputs (arglist,
TREE_CODE (stmt) != MODIFY_EXPR, 1,
- strlen_val[0]);
+ 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:
}
-/* Fold the statement pointed by STMT_P. In some cases, this function may
+/* 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. */
return changed;
}
+/* 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. */
+
+bool
+fold_stmt_inplace (tree stmt)
+{
+ tree old_stmt = stmt, rhs, new_rhs;
+ bool changed = false;
+
+ walk_tree (&stmt, fold_stmt_r, &changed, 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
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));
+
/* 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));
- mark_new_vars_to_rename (tsi_stmt (ti), vars_to_rename);
+ bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT);
+ mark_new_vars_to_rename (bsi_stmt (*si_p));
+ bsi_next (si_p);
}
- if (EXPR_HAS_LOCATION (stmt))
- annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
-
- bsi_insert_before (si_p, stmts, BSI_SAME_STMT);
-
return tmp;
}
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;
}
if (!set_rhs (stmtp, result))
{
result = convert_to_gimple_builtin (&i, result);
- if (result && !set_rhs (stmtp, result))
- abort ();
+ if (result)
+ {
+ bool ok = set_rhs (stmtp, result);
+
+ gcc_assert (ok);
+ }
}
- modify_stmt (*stmtp);
- if (maybe_clean_eh_stmt (*stmtp)
+ mark_new_vars_to_rename (*stmtp);
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp)
&& tree_purge_dead_eh_edges (bb))
cfg_changed = true;
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);
}
}
0, /* todo_flags_start */
TODO_dump_func
| TODO_verify_ssa
- | TODO_rename_vars, /* todo_flags_finish */
+ | TODO_update_ssa, /* todo_flags_finish */
0 /* letter */
};
OSDN Git Service
