/* Conditional constant propagation pass for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
- Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
+ 2010 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>
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
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
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.
-
- 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:
Constant propagation with conditional branches,
#include "tm.h"
#include "tree.h"
#include "flags.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "ggc.h"
#include "basic-block.h"
#include "output.h"
-#include "expr.h"
#include "function.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "value-prof.h"
#include "langhooks.h"
#include "target.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
+#include "dbgcnt.h"
/* Possible lattice values. */
VARYING
} ccp_lattice_t;
+struct prop_value_d {
+ /* Lattice value. */
+ ccp_lattice_t lattice_val;
+
+ /* Propagated value. */
+ tree value;
+
+ /* Mask that applies to the propagated value during CCP. For
+ X with a CONSTANT lattice value X & ~mask == value & ~mask. */
+ double_int mask;
+};
+
+typedef struct prop_value_d prop_value_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
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;
+static void canonicalize_float_value (prop_value_t *);
+static bool ccp_fold_stmt (gimple_stmt_iterator *);
+static tree fold_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size);
/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
break;
case CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
- print_generic_expr (outf, val.value, dump_flags);
+ if (TREE_CODE (val.value) != INTEGER_CST
+ || double_int_zero_p (val.mask))
+ print_generic_expr (outf, val.value, dump_flags);
+ else
+ {
+ double_int cval = double_int_and_not (tree_to_double_int (val.value),
+ val.mask);
+ fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX,
+ prefix, cval.high, cval.low);
+ fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")",
+ val.mask.high, val.mask.low);
+ }
break;
default:
gcc_unreachable ();
void debug_lattice_value (prop_value_t val);
-void
+DEBUG_FUNCTION void
debug_lattice_value (prop_value_t val)
{
dump_lattice_value (stderr, "", val);
}
-/* If SYM is a constant variable with known value, return the value.
- NULL_TREE is returned otherwise. */
-
-tree
-get_symbol_constant_value (tree sym)
-{
- if (TREE_STATIC (sym)
- && TREE_READONLY (sym)
- && !MTAG_P (sym))
- {
- tree val = DECL_INITIAL (sym);
- if (val)
- {
- STRIP_USELESS_TYPE_CONVERSION (val);
- if (is_gimple_min_invariant (val))
- return val;
- }
- /* Variables declared 'const' without an initializer
- have zero as the initializer if they may not be
- overridden at link or run time. */
- if (!val
- && targetm.binds_local_p (sym)
- && (INTEGRAL_TYPE_P (TREE_TYPE (sym))
- || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym))))
- return fold_convert (TREE_TYPE (sym), integer_zero_node);
- }
-
- return NULL_TREE;
-}
-
/* Compute a default value for variable VAR and store it in the
CONST_VAL array. The following rules are used to get default
values:
change the constant value of the PHI node, which allows for more
constants to be propagated.
- 3- If SSA_NAME_VALUE is set and it is a constant, its value is
- used.
-
- 4- Variables defined by statements other than assignments and PHI
+ 3- Variables defined by statements other than assignments and PHI
nodes are considered VARYING.
- 5- Initial values of variables that are not GIMPLE registers are
+ 4- 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))
- {
- /* 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);
+ prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } };
+ gimple stmt;
- if (IS_EMPTY_STMT (stmt))
+ stmt = SSA_NAME_DEF_STMT (var);
+
+ if (gimple_nop_p (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) == VAR_DECL)
+ val.lattice_val = UNDEFINED;
+ else
{
- /* 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;
+ val.lattice_val = VARYING;
+ val.mask = double_int_minus_one;
}
- else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- || TREE_CODE (stmt) == PHI_NODE)
+ }
+ else if (is_gimple_assign (stmt)
+ /* Value-returning GIMPLE_CALL statements assign to
+ a variable, and are treated similarly to GIMPLE_ASSIGN. */
+ || (is_gimple_call (stmt)
+ && gimple_call_lhs (stmt) != NULL_TREE)
+ || gimple_code (stmt) == GIMPLE_PHI)
+ {
+ tree cst;
+ if (gimple_assign_single_p (stmt)
+ && DECL_P (gimple_assign_rhs1 (stmt))
+ && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
{
- /* Any other variable defined by an assignment or a PHI node
- is considered UNDEFINED. */
- val.lattice_val = UNDEFINED;
+ val.lattice_val = CONSTANT;
+ val.value = cst;
}
else
- {
- /* Otherwise, VAR will never take on a constant value. */
- val.lattice_val = VARYING;
- }
+ /* 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;
+ val.mask = double_int_minus_one;
}
return val;
if (val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
+ canonicalize_float_value (val);
+
return val;
}
+/* Return the constant tree value associated with VAR. */
+
+static inline tree
+get_constant_value (tree var)
+{
+ prop_value_t *val;
+ if (TREE_CODE (var) != SSA_NAME)
+ {
+ if (is_gimple_min_invariant (var))
+ return var;
+ return NULL_TREE;
+ }
+ val = get_value (var);
+ if (val
+ && val->lattice_val == CONSTANT
+ && (TREE_CODE (val->value) != INTEGER_CST
+ || double_int_zero_p (val->mask)))
+ return val->value;
+ return NULL_TREE;
+}
+
/* Sets the value associated with VAR to VARYING. */
static inline void
val->lattice_val = VARYING;
val->value = NULL_TREE;
- val->mem_ref = NULL_TREE;
+ val->mask = double_int_minus_one;
}
/* For float types, modify the value of VAL to make ccp work correctly
{
val->lattice_val = UNDEFINED;
val->value = NULL;
- val->mem_ref = NULL;
return;
}
}
+/* Return whether the lattice transition is valid. */
+
+static bool
+valid_lattice_transition (prop_value_t old_val, prop_value_t new_val)
+{
+ /* Lattice transitions must always be monotonically increasing in
+ value. */
+ if (old_val.lattice_val < new_val.lattice_val)
+ return true;
+
+ if (old_val.lattice_val != new_val.lattice_val)
+ return false;
+
+ if (!old_val.value && !new_val.value)
+ return true;
+
+ /* Now both lattice values are CONSTANT. */
+
+ /* Allow transitioning from &x to &x & ~3. */
+ if (TREE_CODE (old_val.value) != INTEGER_CST
+ && TREE_CODE (new_val.value) == INTEGER_CST)
+ return true;
+
+ /* Bit-lattices have to agree in the still valid bits. */
+ if (TREE_CODE (old_val.value) == INTEGER_CST
+ && TREE_CODE (new_val.value) == INTEGER_CST)
+ return double_int_equal_p
+ (double_int_and_not (tree_to_double_int (old_val.value),
+ new_val.mask),
+ double_int_and_not (tree_to_double_int (new_val.value),
+ new_val.mask));
+
+ /* Otherwise constant values have to agree. */
+ return operand_equal_p (old_val.value, new_val.value, 0);
+}
+
/* 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);
+ /* We can deal with old UNINITIALIZED values just fine here. */
+ prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
canonicalize_float_value (&new_val);
- /* 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. */
+ /* We have to be careful to not go up the bitwise lattice
+ represented by the mask.
+ ??? This doesn't seem to be the best place to enforce this. */
+ if (new_val.lattice_val == CONSTANT
+ && old_val->lattice_val == CONSTANT
+ && TREE_CODE (new_val.value) == INTEGER_CST
+ && TREE_CODE (old_val->value) == INTEGER_CST)
+ {
+ double_int diff;
+ diff = double_int_xor (tree_to_double_int (new_val.value),
+ tree_to_double_int (old_val->value));
+ new_val.mask = double_int_ior (new_val.mask,
+ double_int_ior (old_val->mask, diff));
+ }
- 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));
+ gcc_assert (valid_lattice_transition (*old_val, new_val));
- if (old_val->lattice_val != new_val.lattice_val)
+ /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
+ caller that this was a non-transition. */
+ if (old_val->lattice_val != new_val.lattice_val
+ || (new_val.lattice_val == CONSTANT
+ && TREE_CODE (new_val.value) == INTEGER_CST
+ && (TREE_CODE (old_val->value) != INTEGER_CST
+ || !double_int_equal_p (new_val.mask, old_val->mask))))
{
+ /* ??? We would like to delay creation of INTEGER_CSTs from
+ partially constants here. */
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
*old_val = new_val;
- gcc_assert (new_val.lattice_val != UNDEFINED);
+ gcc_assert (new_val.lattice_val != UNINITIALIZED);
return true;
}
return false;
}
+static prop_value_t get_value_for_expr (tree, bool);
+static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
+static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *,
+ tree, double_int, double_int,
+ tree, double_int, double_int);
+
+/* Return a double_int that can be used for bitwise simplifications
+ from VAL. */
+
+static double_int
+value_to_double_int (prop_value_t val)
+{
+ if (val.value
+ && TREE_CODE (val.value) == INTEGER_CST)
+ return tree_to_double_int (val.value);
+ else
+ return double_int_zero;
+}
+
+/* Return the value for the address expression EXPR based on alignment
+ information. */
+
+static prop_value_t
+get_value_from_alignment (tree expr)
+{
+ prop_value_t val;
+ HOST_WIDE_INT bitsize, bitpos;
+ tree base, offset;
+ enum machine_mode mode;
+ int align;
+
+ gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
+
+ base = get_inner_reference (TREE_OPERAND (expr, 0),
+ &bitsize, &bitpos, &offset,
+ &mode, &align, &align, false);
+ if (TREE_CODE (base) == MEM_REF)
+ val = bit_value_binop (PLUS_EXPR, TREE_TYPE (expr),
+ TREE_OPERAND (base, 0), TREE_OPERAND (base, 1));
+ else if (base
+ && ((align = get_object_alignment (base, BIGGEST_ALIGNMENT))
+ > BITS_PER_UNIT))
+ {
+ val.lattice_val = CONSTANT;
+ /* We assume pointers are zero-extended. */
+ val.mask = double_int_and_not
+ (double_int_mask (TYPE_PRECISION (TREE_TYPE (expr))),
+ uhwi_to_double_int (align / BITS_PER_UNIT - 1));
+ val.value = build_int_cst (TREE_TYPE (expr), 0);
+ }
+ else
+ {
+ val.lattice_val = VARYING;
+ val.mask = double_int_minus_one;
+ val.value = NULL_TREE;
+ }
+ if (bitpos != 0)
+ {
+ double_int value, mask;
+ bit_value_binop_1 (PLUS_EXPR, TREE_TYPE (expr), &value, &mask,
+ TREE_TYPE (expr), value_to_double_int (val), val.mask,
+ TREE_TYPE (expr),
+ shwi_to_double_int (bitpos / BITS_PER_UNIT),
+ double_int_zero);
+ val.lattice_val = double_int_minus_one_p (mask) ? VARYING : CONSTANT;
+ val.mask = mask;
+ if (val.lattice_val == CONSTANT)
+ val.value = double_int_to_tree (TREE_TYPE (expr), value);
+ else
+ val.value = NULL_TREE;
+ }
+ /* ??? We should handle i * 4 and more complex expressions from
+ the offset, possibly by just expanding get_value_for_expr. */
+ if (offset != NULL_TREE)
+ {
+ double_int value, mask;
+ prop_value_t oval = get_value_for_expr (offset, true);
+ bit_value_binop_1 (PLUS_EXPR, TREE_TYPE (expr), &value, &mask,
+ TREE_TYPE (expr), value_to_double_int (val), val.mask,
+ TREE_TYPE (expr), value_to_double_int (oval),
+ oval.mask);
+ val.mask = mask;
+ if (double_int_minus_one_p (mask))
+ {
+ val.lattice_val = VARYING;
+ val.value = NULL_TREE;
+ }
+ else
+ {
+ val.lattice_val = CONSTANT;
+ val.value = double_int_to_tree (TREE_TYPE (expr), value);
+ }
+ }
+
+ return val;
+}
+
+/* Return the value for the tree operand EXPR. If FOR_BITS_P is true
+ return constant bits extracted from alignment information for
+ invariant addresses. */
+
+static prop_value_t
+get_value_for_expr (tree expr, bool for_bits_p)
+{
+ prop_value_t val;
+
+ if (TREE_CODE (expr) == SSA_NAME)
+ {
+ val = *get_value (expr);
+ if (for_bits_p
+ && val.lattice_val == CONSTANT
+ && TREE_CODE (val.value) == ADDR_EXPR)
+ val = get_value_from_alignment (val.value);
+ }
+ else if (is_gimple_min_invariant (expr)
+ && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))
+ {
+ val.lattice_val = CONSTANT;
+ val.value = expr;
+ val.mask = double_int_zero;
+ canonicalize_float_value (&val);
+ }
+ else if (TREE_CODE (expr) == ADDR_EXPR)
+ val = get_value_from_alignment (expr);
+ else
+ {
+ val.lattice_val = VARYING;
+ val.mask = double_int_minus_one;
+ val.value = NULL_TREE;
+ }
+ return val;
+}
/* Return the likely CCP lattice value for STMT.
Else return VARYING. */
static ccp_lattice_t
-likely_value (tree stmt)
+likely_value (gimple stmt)
{
bool has_constant_operand, has_undefined_operand, all_undefined_operands;
- stmt_ann_t ann;
tree use;
ssa_op_iter iter;
+ unsigned i;
+
+ enum gimple_code code = gimple_code (stmt);
- ann = stmt_ann (stmt);
+ /* This function appears to be called only for assignments, calls,
+ conditionals, and switches, due to the logic in visit_stmt. */
+ gcc_assert (code == GIMPLE_ASSIGN
+ || code == GIMPLE_CALL
+ || code == GIMPLE_COND
+ || code == GIMPLE_SWITCH);
/* 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;
-
- /* 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)
+ if (gimple_has_volatile_ops (stmt))
return VARYING;
- if (is_gimple_min_invariant (get_rhs (stmt)))
- return CONSTANT;
-
+ /* Arrive here for more complex cases. */
has_constant_operand = false;
has_undefined_operand = false;
all_undefined_operands = true;
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
prop_value_t *val = get_value (use);
has_constant_operand = true;
}
+ /* There may be constants in regular rhs operands. For calls we
+ have to ignore lhs, fndecl and static chain, otherwise only
+ the lhs. */
+ for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
+ i < gimple_num_ops (stmt); ++i)
+ {
+ tree op = gimple_op (stmt, i);
+ if (!op || TREE_CODE (op) == SSA_NAME)
+ continue;
+ if (is_gimple_min_invariant (op))
+ has_constant_operand = true;
+ }
+
+ if (has_constant_operand)
+ all_undefined_operands = false;
+
/* If the operation combines operands like COMPLEX_EXPR make sure to
not mark the result UNDEFINED if only one part of the result is
undefined. */
- if (has_undefined_operand
- && all_undefined_operands)
+ if (has_undefined_operand && all_undefined_operands)
return UNDEFINED;
- else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && has_undefined_operand)
+ else if (code == GIMPLE_ASSIGN && has_undefined_operand)
{
- switch (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)))
+ switch (gimple_assign_rhs_code (stmt))
{
/* Unary operators are handled with all_undefined_operands. */
case PLUS_EXPR:
if (has_undefined_operand)
return VARYING;
+ /* We do not consider virtual operands here -- load from read-only
+ memory may have only VARYING virtual operands, but still be
+ constant. */
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))
+ || gimple_references_memory_p (stmt))
return CONSTANT;
return VARYING;
/* Returns true if STMT cannot be constant. */
static bool
-surely_varying_stmt_p (tree stmt)
+surely_varying_stmt_p (gimple stmt)
{
/* If the statement has operands that we cannot handle, it cannot be
constant. */
- if (stmt_ann (stmt)->has_volatile_ops)
+ if (gimple_has_volatile_ops (stmt))
return true;
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ /* If it is a call and does not return a value or is not a
+ builtin and not an indirect call, it is varying. */
+ if (is_gimple_call (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))
+ tree fndecl;
+ if (!gimple_call_lhs (stmt)
+ || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
+ && !DECL_BUILT_IN (fndecl)))
return true;
}
- /* If it contains a call, it is varying. */
- if (get_call_expr_in (stmt) != NULL_TREE)
+ /* Any other store operation is not interesting. */
+ else if (gimple_vdef (stmt))
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)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ && gimple_code (stmt) != GIMPLE_COND
+ && gimple_code (stmt) != GIMPLE_SWITCH
+ && gimple_code (stmt) != GIMPLE_CALL)
return true;
return false;
/* Initialize simulation flags for PHI nodes and statements. */
FOR_EACH_BB (bb)
{
- block_stmt_iterator i;
+ gimple_stmt_iterator i;
- for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+ for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
{
- tree stmt = bsi_stmt (i);
- bool is_varying = surely_varying_stmt_p (stmt);
+ gimple stmt = gsi_stmt (i);
+ bool is_varying;
+
+ /* If the statement is a control insn, then we do not
+ want to avoid simulating the statement once. Failure
+ to do so means that those edges will never get added. */
+ if (stmt_ends_bb_p (stmt))
+ is_varying = false;
+ else
+ is_varying = surely_varying_stmt_p (stmt);
if (is_varying)
{
/* 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)
- {
- if (is_varying)
- set_value_varying (def);
- }
+ set_value_varying (def);
}
-
- DONT_SIMULATE_AGAIN (stmt) = is_varying;
+ prop_set_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. */
+ /* Now process PHI nodes. We never clear the simulate_again flag on
+ phi nodes, 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;
+ gimple_stmt_iterator i;
- 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;
+ for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
+ {
+ gimple phi = gsi_stmt (i);
+
+ if (!is_gimple_reg (gimple_phi_result (phi)))
+ prop_set_simulate_again (phi, false);
else
- DONT_SIMULATE_AGAIN (phi) = false;
+ prop_set_simulate_again (phi, true);
}
}
}
+/* Debug count support. Reset the values of ssa names
+ VARYING when the total number ssa names analyzed is
+ beyond the debug count specified. */
+
+static void
+do_dbg_cnt (void)
+{
+ unsigned i;
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ if (!dbg_cnt (ccp))
+ {
+ const_val[i].lattice_val = VARYING;
+ const_val[i].mask = double_int_minus_one;
+ const_val[i].value = NULL_TREE;
+ }
+ }
+}
+
/* Do final substitution of propagated values, cleanup the flowgraph and
- free allocated storage.
+ free allocated storage.
Return TRUE when something was optimized. */
static bool
ccp_finalize (void)
{
+ bool something_changed;
+ unsigned i;
+
+ do_dbg_cnt ();
+
+ /* Derive alignment and misalignment information from partially
+ constant pointers in the lattice. */
+ for (i = 1; i < num_ssa_names; ++i)
+ {
+ tree name = ssa_name (i);
+ prop_value_t *val;
+ struct ptr_info_def *pi;
+ unsigned int tem, align;
+
+ if (!name
+ || !POINTER_TYPE_P (TREE_TYPE (name)))
+ continue;
+
+ val = get_value (name);
+ if (val->lattice_val != CONSTANT
+ || TREE_CODE (val->value) != INTEGER_CST)
+ continue;
+
+ /* Trailing constant bits specify the alignment, trailing value
+ bits the misalignment. */
+ tem = val->mask.low;
+ align = (tem & -tem);
+ if (align == 1)
+ continue;
+
+ pi = get_ptr_info (name);
+ pi->align = align;
+ pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1);
+ }
+
/* Perform substitutions based on the known constant values. */
- bool something_changed = substitute_and_fold (const_val, false);
+ something_changed = substitute_and_fold (get_constant_value,
+ ccp_fold_stmt, true);
free (const_val);
const_val = NULL;
{
/* any M VARYING = VARYING. */
val1->lattice_val = VARYING;
+ val1->mask = double_int_minus_one;
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))))
+ && TREE_CODE (val1->value) == INTEGER_CST
+ && TREE_CODE (val2->value) == INTEGER_CST)
+ {
+ /* Ci M Cj = Ci if (i == j)
+ Ci M Cj = VARYING if (i != j)
+
+ For INTEGER_CSTs mask unequal bits. If no equal bits remain,
+ drop to varying. */
+ val1->mask
+ = double_int_ior (double_int_ior (val1->mask,
+ val2->mask),
+ double_int_xor (tree_to_double_int (val1->value),
+ tree_to_double_int (val2->value)));
+ if (double_int_minus_one_p (val1->mask))
+ {
+ val1->lattice_val = VARYING;
+ val1->value = NULL_TREE;
+ }
+ }
+ else if (val1->lattice_val == CONSTANT
+ && val2->lattice_val == CONSTANT
+ && simple_cst_equal (val1->value, val2->value) == 1)
{
/* 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;
+ VAL1 already contains the value we want for equivalent values. */
+ }
+ else if (val1->lattice_val == CONSTANT
+ && val2->lattice_val == CONSTANT
+ && (TREE_CODE (val1->value) == ADDR_EXPR
+ || TREE_CODE (val2->value) == ADDR_EXPR))
+ {
+ /* When not equal addresses are involved try meeting for
+ alignment. */
+ prop_value_t tem = *val2;
+ if (TREE_CODE (val1->value) == ADDR_EXPR)
+ *val1 = get_value_for_expr (val1->value, true);
+ if (TREE_CODE (val2->value) == ADDR_EXPR)
+ tem = get_value_for_expr (val2->value, true);
+ ccp_lattice_meet (val1, &tem);
}
else
{
/* Any other combination is VARYING. */
val1->lattice_val = VARYING;
+ val1->mask = double_int_minus_one;
val1->value = NULL_TREE;
- val1->mem_ref = NULL_TREE;
}
}
of the PHI node that are incoming via executable edges. */
static enum ssa_prop_result
-ccp_visit_phi_node (tree phi)
+ccp_visit_phi_node (gimple phi)
{
- int i;
+ unsigned i;
prop_value_t *old_val, new_val;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
- print_generic_expr (dump_file, phi, dump_flags);
+ print_gimple_stmt (dump_file, phi, 0, dump_flags);
}
- old_val = get_value (PHI_RESULT (phi));
+ old_val = get_value (gimple_phi_result (phi));
switch (old_val->lattice_val)
{
case VARYING:
case UNDEFINED:
new_val.lattice_val = UNDEFINED;
new_val.value = NULL_TREE;
- new_val.mem_ref = NULL_TREE;
break;
default:
gcc_unreachable ();
}
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ for (i = 0; i < gimple_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);
+ edge e = gimple_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 arg = PHI_ARG_DEF (phi, i);
- prop_value_t arg_val;
-
- 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));
+ tree arg = gimple_phi_arg (phi, i)->def;
+ prop_value_t arg_val = get_value_for_expr (arg, false);
ccp_lattice_meet (&new_val, &arg_val);
}
/* Make the transition to the new value. */
- if (set_lattice_value (PHI_RESULT (phi), new_val))
+ if (set_lattice_value (gimple_phi_result (phi), new_val))
{
if (new_val.lattice_val == VARYING)
return SSA_PROP_VARYING;
return SSA_PROP_NOT_INTERESTING;
}
+/* Return the constant value for OP or OP otherwise. */
+
+static tree
+valueize_op (tree op)
+{
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ tree tem = get_constant_value (op);
+ if (tem)
+ return tem;
+ }
+ return op;
+}
/* CCP specific front-end to the non-destructive constant folding
routines.
operands are constants.
If simplification is possible, return the simplified RHS,
- otherwise return the original RHS. */
+ otherwise return the original RHS or NULL_TREE. */
static tree
-ccp_fold (tree stmt)
+ccp_fold (gimple stmt)
{
- tree rhs = get_rhs (stmt);
- enum tree_code code = TREE_CODE (rhs);
- enum tree_code_class kind = TREE_CODE_CLASS (code);
- tree retval = NULL_TREE;
-
- if (TREE_CODE (rhs) == SSA_NAME)
- {
- /* 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))
+ location_t loc = gimple_location (stmt);
+ switch (gimple_code (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;
- }
+ case GIMPLE_ASSIGN:
+ {
+ enum tree_code subcode = gimple_assign_rhs_code (stmt);
+
+ switch (get_gimple_rhs_class (subcode))
+ {
+ case GIMPLE_SINGLE_RHS:
+ {
+ tree rhs = gimple_assign_rhs1 (stmt);
+ enum tree_code_class kind = TREE_CODE_CLASS (subcode);
+
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ /* If the RHS is an SSA_NAME, return its known constant value,
+ if any. */
+ return get_constant_value (rhs);
+ }
+ /* Handle propagating invariant addresses into address operations.
+ The folding we do here matches that in tree-ssa-forwprop.c. */
+ else if (TREE_CODE (rhs) == ADDR_EXPR)
+ {
+ tree *base;
+ base = &TREE_OPERAND (rhs, 0);
+ while (handled_component_p (*base))
+ base = &TREE_OPERAND (*base, 0);
+ if (TREE_CODE (*base) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (*base, 0)) == SSA_NAME)
+ {
+ tree val = get_constant_value (TREE_OPERAND (*base, 0));
+ if (val
+ && TREE_CODE (val) == ADDR_EXPR)
+ {
+ tree ret, save = *base;
+ tree new_base;
+ new_base = fold_build2 (MEM_REF, TREE_TYPE (*base),
+ unshare_expr (val),
+ TREE_OPERAND (*base, 1));
+ /* We need to return a new tree, not modify the IL
+ or share parts of it. So play some tricks to
+ avoid manually building it. */
+ *base = new_base;
+ ret = unshare_expr (rhs);
+ recompute_tree_invariant_for_addr_expr (ret);
+ *base = save;
+ return ret;
+ }
+ }
+ }
+ else if (TREE_CODE (rhs) == CONSTRUCTOR
+ && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE
+ && (CONSTRUCTOR_NELTS (rhs)
+ == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs))))
+ {
+ unsigned i;
+ tree val, list;
+
+ list = NULL_TREE;
+ FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
+ {
+ val = valueize_op (val);
+ if (TREE_CODE (val) == INTEGER_CST
+ || TREE_CODE (val) == REAL_CST
+ || TREE_CODE (val) == FIXED_CST)
+ list = tree_cons (NULL_TREE, val, list);
+ else
+ return NULL_TREE;
+ }
+
+ return build_vector (TREE_TYPE (rhs), nreverse (list));
+ }
- /* Unary operators. Note that we know the single operand must
- be a constant. So this should almost always return a
- simplified RHS. */
- if (kind == tcc_unary)
- {
- /* Handle unary operators which can appear in GIMPLE form. */
- tree op0 = TREE_OPERAND (rhs, 0);
+ if (kind == tcc_reference)
+ {
+ if ((TREE_CODE (rhs) == VIEW_CONVERT_EXPR
+ || TREE_CODE (rhs) == REALPART_EXPR
+ || TREE_CODE (rhs) == IMAGPART_EXPR)
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
+ {
+ tree val = get_constant_value (TREE_OPERAND (rhs, 0));
+ if (val)
+ return fold_unary_loc (EXPR_LOCATION (rhs),
+ TREE_CODE (rhs),
+ TREE_TYPE (rhs), val);
+ }
+ else if (TREE_CODE (rhs) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
+ {
+ tree val = get_constant_value (TREE_OPERAND (rhs, 0));
+ if (val
+ && TREE_CODE (val) == ADDR_EXPR)
+ {
+ tree tem = fold_build2 (MEM_REF, TREE_TYPE (rhs),
+ unshare_expr (val),
+ TREE_OPERAND (rhs, 1));
+ if (tem)
+ rhs = tem;
+ }
+ }
+ return fold_const_aggregate_ref (rhs);
+ }
+ else if (kind == tcc_declaration)
+ return get_symbol_constant_value (rhs);
+ return rhs;
+ }
+
+ case GIMPLE_UNARY_RHS:
+ {
+ /* Handle unary operators that can appear in GIMPLE form.
+ Note that we know the single operand must be a constant,
+ so this should almost always return a simplified RHS. */
+ tree lhs = gimple_assign_lhs (stmt);
+ tree op0 = valueize_op (gimple_assign_rhs1 (stmt));
+
+ /* Conversions are useless for CCP purposes if they are
+ value-preserving. Thus the restrictions that
+ useless_type_conversion_p places for pointer type conversions
+ do not apply here. Substitution later will only substitute to
+ allowed places. */
+ if (CONVERT_EXPR_CODE_P (subcode)
+ && POINTER_TYPE_P (TREE_TYPE (lhs))
+ && POINTER_TYPE_P (TREE_TYPE (op0)))
+ {
+ tree tem;
+ /* Try to re-construct array references on-the-fly. */
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (op0))
+ && ((tem = maybe_fold_offset_to_address
+ (loc,
+ op0, integer_zero_node, TREE_TYPE (lhs)))
+ != NULL_TREE))
+ return tem;
+ return op0;
+ }
- /* Simplify the operand down to a constant. */
- if (TREE_CODE (op0) == SSA_NAME)
- {
- prop_value_t *val = get_value (op0);
- if (val->lattice_val == CONSTANT)
- op0 = get_value (op0)->value;
- }
+ return
+ fold_unary_ignore_overflow_loc (loc, subcode,
+ gimple_expr_type (stmt), op0);
+ }
+
+ case GIMPLE_BINARY_RHS:
+ {
+ /* Handle binary operators that can appear in GIMPLE form. */
+ tree op0 = valueize_op (gimple_assign_rhs1 (stmt));
+ tree op1 = valueize_op (gimple_assign_rhs2 (stmt));
+
+ /* Translate &x + CST into an invariant form suitable for
+ further propagation. */
+ if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
+ && TREE_CODE (op0) == ADDR_EXPR
+ && TREE_CODE (op1) == INTEGER_CST)
+ {
+ tree off = fold_convert (ptr_type_node, op1);
+ return build_fold_addr_expr
+ (fold_build2 (MEM_REF,
+ TREE_TYPE (TREE_TYPE (op0)),
+ unshare_expr (op0), off));
+ }
- /* Conversions are useless for CCP purposes if they are
- value-preserving. Thus the restrictions that
- useless_type_conversion_p places for pointer type conversions do
- not apply here. Substitution later will only substitute to
- allowed places. */
- if ((code == NOP_EXPR || code == CONVERT_EXPR)
- && ((POINTER_TYPE_P (TREE_TYPE (rhs))
- && POINTER_TYPE_P (TREE_TYPE (op0)))
- || useless_type_conversion_p (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 == tcc_binary
- || kind == tcc_comparison
- || code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR
- || code == TRUTH_XOR_EXPR)
- {
- /* Handle binary and comparison operators that can appear in
- GIMPLE form. */
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- /* Simplify the operands down to constants when appropriate. */
- if (TREE_CODE (op0) == SSA_NAME)
- {
- prop_value_t *val = get_value (op0);
- if (val->lattice_val == CONSTANT)
- op0 = val->value;
- }
+ return fold_binary_loc (loc, subcode,
+ gimple_expr_type (stmt), op0, op1);
+ }
- if (TREE_CODE (op1) == SSA_NAME)
- {
- prop_value_t *val = get_value (op1);
- if (val->lattice_val == CONSTANT)
- op1 = val->value;
- }
+ case GIMPLE_TERNARY_RHS:
+ {
+ /* Handle ternary operators that can appear in GIMPLE form. */
+ tree op0 = valueize_op (gimple_assign_rhs1 (stmt));
+ tree op1 = valueize_op (gimple_assign_rhs2 (stmt));
+ tree op2 = valueize_op (gimple_assign_rhs3 (stmt));
- return fold_binary (code, TREE_TYPE (rhs), op0, op1);
- }
+ return fold_ternary_loc (loc, subcode,
+ gimple_expr_type (stmt), op0, op1, op2);
+ }
- else if (kind == tcc_declaration)
- return get_symbol_constant_value (rhs);
+ default:
+ gcc_unreachable ();
+ }
+ }
+ break;
- else if (kind == tcc_reference)
- return fold_const_aggregate_ref (rhs);
+ case GIMPLE_CALL:
+ {
+ tree fn = valueize_op (gimple_call_fn (stmt));
+ if (TREE_CODE (fn) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
+ && DECL_BUILT_IN (TREE_OPERAND (fn, 0)))
+ {
+ tree *args = XALLOCAVEC (tree, gimple_call_num_args (stmt));
+ tree call, retval;
+ unsigned i;
+ for (i = 0; i < gimple_call_num_args (stmt); ++i)
+ args[i] = valueize_op (gimple_call_arg (stmt, i));
+ call = build_call_array_loc (loc,
+ gimple_call_return_type (stmt),
+ fn, gimple_call_num_args (stmt), args);
+ retval = fold_call_expr (EXPR_LOCATION (call), call, false);
+ if (retval)
+ /* fold_call_expr wraps the result inside a NOP_EXPR. */
+ STRIP_NOPS (retval);
+ return retval;
+ }
+ return NULL_TREE;
+ }
- /* Handle propagating invariant addresses into address operations.
- The folding we do here matches that in tree-ssa-forwprop.c. */
- else if (code == ADDR_EXPR)
- {
- tree *base;
- base = &TREE_OPERAND (rhs, 0);
- while (handled_component_p (*base))
- base = &TREE_OPERAND (*base, 0);
- if (TREE_CODE (*base) == INDIRECT_REF
- && TREE_CODE (TREE_OPERAND (*base, 0)) == SSA_NAME)
+ case GIMPLE_COND:
+ {
+ /* Handle comparison operators that can appear in GIMPLE form. */
+ tree op0 = valueize_op (gimple_cond_lhs (stmt));
+ tree op1 = valueize_op (gimple_cond_rhs (stmt));
+ enum tree_code code = gimple_cond_code (stmt);
+ return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
+ }
+
+ case GIMPLE_SWITCH:
+ {
+ /* Return the constant switch index. */
+ return valueize_op (gimple_switch_index (stmt));
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* See if we can find constructor defining value of BASE.
+ When we know the consructor with constant offset (such as
+ base is array[40] and we do know constructor of array), then
+ BIT_OFFSET is adjusted accordingly.
+
+ As a special case, return error_mark_node when constructor
+ is not explicitly available, but it is known to be zero
+ such as 'static const int a;'. */
+static tree
+get_base_constructor (tree base, HOST_WIDE_INT *bit_offset)
+{
+ HOST_WIDE_INT bit_offset2, size, max_size;
+ if (TREE_CODE (base) == MEM_REF)
+ {
+ if (!integer_zerop (TREE_OPERAND (base, 1)))
{
- prop_value_t *val = get_value (TREE_OPERAND (*base, 0));
- if (val->lattice_val == CONSTANT
- && TREE_CODE (val->value) == ADDR_EXPR
- && useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (*base, 0)),
- TREE_TYPE (val->value))
- && useless_type_conversion_p (TREE_TYPE (*base),
- TREE_TYPE (TREE_OPERAND (val->value, 0))))
- {
- /* We need to return a new tree, not modify the IL or share
- parts of it. So play some tricks to avoid manually
- building it. */
- tree ret, save = *base;
- *base = TREE_OPERAND (val->value, 0);
- ret = unshare_expr (rhs);
- recompute_tree_invariant_for_addr_expr (ret);
- *base = save;
- return ret;
- }
+ if (!host_integerp (TREE_OPERAND (base, 1), 0))
+ return NULL_TREE;
+ *bit_offset += (mem_ref_offset (base).low
+ * BITS_PER_UNIT);
}
+
+ base = get_constant_value (TREE_OPERAND (base, 0));
+ if (!base || TREE_CODE (base) != ADDR_EXPR)
+ return NULL_TREE;
+ base = TREE_OPERAND (base, 0);
+ }
+
+ /* 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. */
+ switch (TREE_CODE (base))
+ {
+ case VAR_DECL:
+ if (!const_value_known_p (base))
+ return NULL_TREE;
+
+ /* Fallthru. */
+ case CONST_DECL:
+ if (!DECL_INITIAL (base)
+ && (TREE_STATIC (base) || DECL_EXTERNAL (base)))
+ return error_mark_node;
+ return DECL_INITIAL (base);
+
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ base = get_ref_base_and_extent (base, &bit_offset2, &size, &max_size);
+ if (max_size == -1 || size != max_size)
+ return NULL_TREE;
+ *bit_offset += bit_offset2;
+ return get_base_constructor (base, bit_offset);
+
+ case STRING_CST:
+ case CONSTRUCTOR:
+ return base;
+
+ default:
+ return NULL_TREE;
+ }
+}
+
+/* CTOR is STRING_CST. Fold reference of type TYPE and size SIZE
+ to the memory at bit OFFSET.
+
+ We do only simple job of folding byte accesses. */
+
+static tree
+fold_string_cst_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+{
+ if (INTEGRAL_TYPE_P (type)
+ && (TYPE_MODE (type)
+ == 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
+ && size == BITS_PER_UNIT
+ && !(offset % BITS_PER_UNIT))
+ {
+ offset /= BITS_PER_UNIT;
+ if (offset < (unsigned HOST_WIDE_INT) TREE_STRING_LENGTH (ctor))
+ return build_int_cst_type (type, (TREE_STRING_POINTER (ctor)
+ [offset]));
+ /* Folding
+ const char a[20]="hello";
+ return a[10];
+
+ might lead to offset greater than string length. In this case we
+ know value is either initialized to 0 or out of bounds. Return 0
+ in both cases. */
+ return build_zero_cst (type);
+ }
+ return NULL_TREE;
+}
+
+/* CTOR is CONSTRUCTOR of an array type. Fold reference of type TYPE and size
+ SIZE to the memory at bit OFFSET. */
+
+static tree
+fold_array_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+{
+ unsigned HOST_WIDE_INT cnt;
+ tree cfield, cval;
+ double_int low_bound, elt_size;
+ double_int index, max_index;
+ double_int access_index;
+ tree domain_type = TYPE_DOMAIN (TREE_TYPE (ctor));
+ HOST_WIDE_INT inner_offset;
+
+ /* Compute low bound and elt size. */
+ if (domain_type && TYPE_MIN_VALUE (domain_type))
+ {
+ /* Static constructors for variably sized objects makes no sense. */
+ gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST);
+ low_bound = tree_to_double_int (TYPE_MIN_VALUE (domain_type));
}
+ else
+ low_bound = double_int_zero;
+ /* Static constructors for variably sized objects makes no sense. */
+ gcc_assert (TREE_CODE(TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))))
+ == INTEGER_CST);
+ elt_size =
+ tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor))));
+
+
+ /* We can handle only constantly sized accesses that are known to not
+ be larger than size of array element. */
+ if (!TYPE_SIZE_UNIT (type)
+ || TREE_CODE (TYPE_SIZE_UNIT (type)) != INTEGER_CST
+ || double_int_cmp (elt_size,
+ tree_to_double_int (TYPE_SIZE_UNIT (type)), 0) < 0)
+ return NULL_TREE;
+
+ /* Compute the array index we look for. */
+ access_index = double_int_udiv (uhwi_to_double_int (offset / BITS_PER_UNIT),
+ elt_size, TRUNC_DIV_EXPR);
+ access_index = double_int_add (access_index, low_bound);
+
+ /* And offset within the access. */
+ inner_offset = offset % (double_int_to_uhwi (elt_size) * BITS_PER_UNIT);
+
+ /* See if the array field is large enough to span whole access. We do not
+ care to fold accesses spanning multiple array indexes. */
+ if (inner_offset + size > double_int_to_uhwi (elt_size) * BITS_PER_UNIT)
+ return NULL_TREE;
- /* We may be able to fold away calls to builtin functions if their
- arguments are constants. */
- else if (code == CALL_EXPR
- && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)) == FUNCTION_DECL
- && DECL_BUILT_IN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
+ index = double_int_sub (low_bound, double_int_one);
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
{
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE))
+ /* Array constructor might explicitely set index, or specify range
+ or leave index NULL meaning that it is next index after previous
+ one. */
+ if (cfield)
{
- tree *orig, var;
- size_t i = 0;
- ssa_op_iter iter;
- use_operand_p var_p;
-
- /* Preserve the original values of every operand. */
- 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, const_val);
- retval = fold_call_expr (rhs, false);
-
- /* Restore operands to their original form. */
- i = 0;
- FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE)
- SET_USE (var_p, orig[i++]);
- free (orig);
+ if (TREE_CODE (cfield) == INTEGER_CST)
+ max_index = index = tree_to_double_int (cfield);
+ else
+ {
+ gcc_assert (TREE_CODE (cfield) == RANGE_EXPR);
+ index = tree_to_double_int (TREE_OPERAND (cfield, 0));
+ max_index = tree_to_double_int (TREE_OPERAND (cfield, 1));
+ }
}
+ else
+ max_index = index = double_int_add (index, double_int_one);
+
+ /* Do we have match? */
+ if (double_int_cmp (access_index, index, 1) >= 0
+ && double_int_cmp (access_index, max_index, 1) <= 0)
+ return fold_ctor_reference (type, cval, inner_offset, size);
}
- else
- return rhs;
+ /* When memory is not explicitely mentioned in constructor,
+ it is 0 (or out of range). */
+ return build_zero_cst (type);
+}
- /* If we got a simplified form, see if we need to convert its type. */
- if (retval)
- return fold_convert (TREE_TYPE (rhs), retval);
+/* CTOR is CONSTRUCTOR of an aggregate or vector.
+ Fold reference of type TYPE and size SIZE to the memory at bit OFFSET. */
- /* No simplification was possible. */
- return rhs;
+static tree
+fold_nonarray_ctor_reference (tree type, tree ctor,
+ unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+{
+ unsigned HOST_WIDE_INT cnt;
+ tree cfield, cval;
+
+ FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield,
+ cval)
+ {
+ tree byte_offset = DECL_FIELD_OFFSET (cfield);
+ tree field_offset = DECL_FIELD_BIT_OFFSET (cfield);
+ tree field_size = DECL_SIZE (cfield);
+ double_int bitoffset;
+ double_int byte_offset_cst = tree_to_double_int (byte_offset);
+ double_int bits_per_unit_cst = uhwi_to_double_int (BITS_PER_UNIT);
+ double_int bitoffset_end;
+
+ /* Variable sized objects in static constructors makes no sense,
+ but field_size can be NULL for flexible array members. */
+ gcc_assert (TREE_CODE (field_offset) == INTEGER_CST
+ && TREE_CODE (byte_offset) == INTEGER_CST
+ && (field_size != NULL_TREE
+ ? TREE_CODE (field_size) == INTEGER_CST
+ : TREE_CODE (TREE_TYPE (cfield)) == ARRAY_TYPE));
+
+ /* Compute bit offset of the field. */
+ bitoffset = double_int_add (tree_to_double_int (field_offset),
+ double_int_mul (byte_offset_cst,
+ bits_per_unit_cst));
+ /* Compute bit offset where the field ends. */
+ if (field_size != NULL_TREE)
+ bitoffset_end = double_int_add (bitoffset,
+ tree_to_double_int (field_size));
+ else
+ bitoffset_end = double_int_zero;
+
+ /* Is OFFSET in the range (BITOFFSET, BITOFFSET_END)? */
+ if (double_int_cmp (uhwi_to_double_int (offset), bitoffset, 0) >= 0
+ && (field_size == NULL_TREE
+ || double_int_cmp (uhwi_to_double_int (offset),
+ bitoffset_end, 0) < 0))
+ {
+ double_int access_end = double_int_add (uhwi_to_double_int (offset),
+ uhwi_to_double_int (size));
+ double_int inner_offset = double_int_sub (uhwi_to_double_int (offset),
+ bitoffset);
+ /* We do have overlap. Now see if field is large enough to
+ cover the access. Give up for accesses spanning multiple
+ fields. */
+ if (double_int_cmp (access_end, bitoffset_end, 0) > 0)
+ return NULL_TREE;
+ return fold_ctor_reference (type, cval,
+ double_int_to_uhwi (inner_offset), size);
+ }
+ }
+ /* When memory is not explicitely mentioned in constructor, it is 0. */
+ return build_zero_cst (type);
}
+/* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
+ to the memory at bit OFFSET. */
+
+static tree
+fold_ctor_reference (tree type, tree ctor, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
+{
+ tree ret;
+
+ /* We found the field with exact match. */
+ if (useless_type_conversion_p (type, TREE_TYPE (ctor))
+ && !offset)
+ return canonicalize_constructor_val (ctor);
+
+ /* We are at the end of walk, see if we can view convert the
+ result. */
+ if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor)) && !offset
+ /* VIEW_CONVERT_EXPR is defined only for matching sizes. */
+ && operand_equal_p (TYPE_SIZE (type),
+ TYPE_SIZE (TREE_TYPE (ctor)), 0))
+ {
+ ret = canonicalize_constructor_val (ctor);
+ ret = fold_unary (VIEW_CONVERT_EXPR, type, ret);
+ if (ret)
+ STRIP_NOPS (ret);
+ return ret;
+ }
+ if (TREE_CODE (ctor) == STRING_CST)
+ return fold_string_cst_ctor_reference (type, ctor, offset, size);
+ if (TREE_CODE (ctor) == CONSTRUCTOR)
+ {
+
+ if (TREE_CODE (TREE_TYPE (ctor)) == ARRAY_TYPE)
+ return fold_array_ctor_reference (type, ctor, offset, size);
+ else
+ return fold_nonarray_ctor_reference (type, ctor, offset, size);
+ }
+
+ return NULL_TREE;
+}
/* Return the tree representing the element referenced by T if T is an
ARRAY_REF or COMPONENT_REF into constant aggregates. Return
tree
fold_const_aggregate_ref (tree t)
{
- prop_value_t *value;
- tree base, ctor, idx, field;
- unsigned HOST_WIDE_INT cnt;
- tree cfield, cval;
+ tree ctor, idx, base;
+ HOST_WIDE_INT offset, size, max_size;
+ tree tem;
+
+ if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_declaration)
+ return get_symbol_constant_value (t);
+
+ tem = fold_read_from_constant_string (t);
+ if (tem)
+ return tem;
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 ARRAY_RANGE_REF:
+ /* Constant indexes are handled well by get_base_constructor.
+ Only special case variable offsets.
+ FIXME: This code can't handle nested references with variable indexes
+ (they will be handled only by iteration of ccp). Perhaps we can bring
+ get_ref_base_and_extent here and make it use get_constant_value. */
+ if (TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME
+ && (idx = get_constant_value (TREE_OPERAND (t, 1)))
+ && host_integerp (idx, 0))
{
- case VAR_DECL:
- if (!TREE_READONLY (base)
- || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
- || !targetm.binds_local_p (base))
- return NULL_TREE;
+ tree low_bound, unit_size;
- ctor = DECL_INITIAL (base);
- break;
+ /* If the resulting bit-offset is constant, track it. */
+ if ((low_bound = array_ref_low_bound (t),
+ host_integerp (low_bound, 0))
+ && (unit_size = array_ref_element_size (t),
+ host_integerp (unit_size, 1)))
+ {
+ offset = TREE_INT_CST_LOW (idx);
+ offset -= TREE_INT_CST_LOW (low_bound);
+ offset *= TREE_INT_CST_LOW (unit_size);
+ offset *= BITS_PER_UNIT;
+
+ base = TREE_OPERAND (t, 0);
+ ctor = get_base_constructor (base, &offset);
+ /* Empty constructor. Always fold to 0. */
+ if (ctor == error_mark_node)
+ return build_zero_cst (TREE_TYPE (t));
+ /* Out of bound array access. Value is undefined, but don't fold. */
+ if (offset < 0)
+ return NULL_TREE;
+ /* We can not determine ctor. */
+ if (!ctor)
+ return NULL_TREE;
+ return fold_ctor_reference (TREE_TYPE (t), ctor, offset,
+ TREE_INT_CST_LOW (unit_size)
+ * BITS_PER_UNIT);
+ }
+ }
+ /* Fallthru. */
+
+ case COMPONENT_REF:
+ case BIT_FIELD_REF:
+ case TARGET_MEM_REF:
+ case MEM_REF:
+ base = get_ref_base_and_extent (t, &offset, &size, &max_size);
+ ctor = get_base_constructor (base, &offset);
+
+ /* Empty constructor. Always fold to 0. */
+ if (ctor == error_mark_node)
+ return build_zero_cst (TREE_TYPE (t));
+ /* We do not know precise address. */
+ if (max_size == -1 || max_size != size)
+ return NULL_TREE;
+ /* We can not determine ctor. */
+ if (!ctor)
+ return NULL_TREE;
- case ARRAY_REF:
- case COMPONENT_REF:
- ctor = fold_const_aggregate_ref (base);
- break;
+ /* Out of bound array access. Value is undefined, but don't fold. */
+ if (offset < 0)
+ return NULL_TREE;
- case STRING_CST:
- case CONSTRUCTOR:
- ctor = base;
- break;
+ return fold_ctor_reference (TREE_TYPE (t), ctor, offset, size);
- default:
- return NULL_TREE;
- }
+ 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_loc (EXPR_LOCATION (t),
+ TREE_CODE (t), TREE_TYPE (t), c);
+ break;
+ }
- if (ctor == NULL_TREE
- || (TREE_CODE (ctor) != CONSTRUCTOR
- && TREE_CODE (ctor) != STRING_CST)
- || !TREE_STATIC (ctor))
- return NULL_TREE;
+ default:
+ break;
+ }
- /* 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;
+ return NULL_TREE;
+}
- case INTEGER_CST:
- break;
+/* Apply the operation CODE in type TYPE to the value, mask pair
+ RVAL and RMASK representing a value of type RTYPE and set
+ the value, mask pair *VAL and *MASK to the result. */
- default:
- return NULL_TREE;
- }
+static void
+bit_value_unop_1 (enum tree_code code, tree type,
+ double_int *val, double_int *mask,
+ tree rtype, double_int rval, double_int rmask)
+{
+ switch (code)
+ {
+ case BIT_NOT_EXPR:
+ *mask = rmask;
+ *val = double_int_not (rval);
+ break;
- /* 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_type (TREE_TYPE (t),
- (TREE_STRING_POINTER (ctor)
- [TREE_INT_CST_LOW (idx)]));
- return NULL_TREE;
- }
+ case NEGATE_EXPR:
+ {
+ double_int temv, temm;
+ /* Return ~rval + 1. */
+ bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask);
+ bit_value_binop_1 (PLUS_EXPR, type, val, mask,
+ type, temv, temm,
+ type, double_int_one, double_int_zero);
+ break;
+ }
- /* 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))
- {
- STRIP_USELESS_TYPE_CONVERSION (cval);
- return cval;
- }
+ CASE_CONVERT:
+ {
+ bool uns;
+
+ /* First extend mask and value according to the original type. */
+ uns = (TREE_CODE (rtype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (rtype)
+ ? 0 : TYPE_UNSIGNED (rtype));
+ *mask = double_int_ext (rmask, TYPE_PRECISION (rtype), uns);
+ *val = double_int_ext (rval, TYPE_PRECISION (rtype), uns);
+
+ /* Then extend mask and value according to the target type. */
+ uns = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
+ ? 0 : TYPE_UNSIGNED (type));
+ *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
+ *val = double_int_ext (*val, TYPE_PRECISION (type), uns);
+ break;
+ }
+
+ default:
+ *mask = double_int_minus_one;
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;
+/* Apply the operation CODE in type TYPE to the value, mask pairs
+ R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
+ and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
- ctor = DECL_INITIAL (base);
- break;
+static void
+bit_value_binop_1 (enum tree_code code, tree type,
+ double_int *val, double_int *mask,
+ tree r1type, double_int r1val, double_int r1mask,
+ tree r2type, double_int r2val, double_int r2mask)
+{
+ bool uns = (TREE_CODE (type) == INTEGER_TYPE
+ && TYPE_IS_SIZETYPE (type) ? 0 : TYPE_UNSIGNED (type));
+ /* Assume we'll get a constant result. Use an initial varying value,
+ we fall back to varying in the end if necessary. */
+ *mask = double_int_minus_one;
+ switch (code)
+ {
+ case BIT_AND_EXPR:
+ /* The mask is constant where there is a known not
+ set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
+ *mask = double_int_and (double_int_ior (r1mask, r2mask),
+ double_int_and (double_int_ior (r1val, r1mask),
+ double_int_ior (r2val, r2mask)));
+ *val = double_int_and (r1val, r2val);
+ break;
- case ARRAY_REF:
- case COMPONENT_REF:
- ctor = fold_const_aggregate_ref (base);
- break;
+ case BIT_IOR_EXPR:
+ /* The mask is constant where there is a known
+ set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
+ *mask = double_int_and_not
+ (double_int_ior (r1mask, r2mask),
+ double_int_ior (double_int_and_not (r1val, r1mask),
+ double_int_and_not (r2val, r2mask)));
+ *val = double_int_ior (r1val, r2val);
+ break;
- default:
- return NULL_TREE;
+ case BIT_XOR_EXPR:
+ /* m1 | m2 */
+ *mask = double_int_ior (r1mask, r2mask);
+ *val = double_int_xor (r1val, r2val);
+ break;
+
+ case LROTATE_EXPR:
+ case RROTATE_EXPR:
+ if (double_int_zero_p (r2mask))
+ {
+ HOST_WIDE_INT shift = r2val.low;
+ if (code == RROTATE_EXPR)
+ shift = -shift;
+ *mask = double_int_lrotate (r1mask, shift, TYPE_PRECISION (type));
+ *val = double_int_lrotate (r1val, shift, TYPE_PRECISION (type));
}
+ break;
- if (ctor == NULL_TREE
- || TREE_CODE (ctor) != CONSTRUCTOR
- || !TREE_STATIC (ctor))
- return NULL_TREE;
+ case LSHIFT_EXPR:
+ case RSHIFT_EXPR:
+ /* ??? We can handle partially known shift counts if we know
+ its sign. That way we can tell that (x << (y | 8)) & 255
+ is zero. */
+ if (double_int_zero_p (r2mask))
+ {
+ HOST_WIDE_INT shift = r2val.low;
+ if (code == RSHIFT_EXPR)
+ shift = -shift;
+ /* We need to know if we are doing a left or a right shift
+ to properly shift in zeros for left shift and unsigned
+ right shifts and the sign bit for signed right shifts.
+ For signed right shifts we shift in varying in case
+ the sign bit was varying. */
+ if (shift > 0)
+ {
+ *mask = double_int_lshift (r1mask, shift,
+ TYPE_PRECISION (type), false);
+ *val = double_int_lshift (r1val, shift,
+ TYPE_PRECISION (type), false);
+ }
+ else if (shift < 0)
+ {
+ shift = -shift;
+ *mask = double_int_rshift (r1mask, shift,
+ TYPE_PRECISION (type), !uns);
+ *val = double_int_rshift (r1val, shift,
+ TYPE_PRECISION (type), !uns);
+ }
+ else
+ {
+ *mask = r1mask;
+ *val = r1val;
+ }
+ }
+ break;
+
+ case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
+ {
+ double_int lo, hi;
+ /* Do the addition with unknown bits set to zero, to give carry-ins of
+ zero wherever possible. */
+ lo = double_int_add (double_int_and_not (r1val, r1mask),
+ double_int_and_not (r2val, r2mask));
+ lo = double_int_ext (lo, TYPE_PRECISION (type), uns);
+ /* Do the addition with unknown bits set to one, to give carry-ins of
+ one wherever possible. */
+ hi = double_int_add (double_int_ior (r1val, r1mask),
+ double_int_ior (r2val, r2mask));
+ hi = double_int_ext (hi, TYPE_PRECISION (type), uns);
+ /* Each bit in the result is known if (a) the corresponding bits in
+ both inputs are known, and (b) the carry-in to that bit position
+ is known. We can check condition (b) by seeing if we got the same
+ result with minimised carries as with maximised carries. */
+ *mask = double_int_ior (double_int_ior (r1mask, r2mask),
+ double_int_xor (lo, hi));
+ *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
+ /* It shouldn't matter whether we choose lo or hi here. */
+ *val = lo;
+ break;
+ }
- field = TREE_OPERAND (t, 1);
+ case MINUS_EXPR:
+ {
+ double_int temv, temm;
+ bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm,
+ r2type, r2val, r2mask);
+ bit_value_binop_1 (PLUS_EXPR, type, val, mask,
+ r1type, r1val, r1mask,
+ r2type, temv, temm);
+ break;
+ }
- FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval)
- if (cfield == field
- /* FIXME: Handle bit-fields. */
- && ! DECL_BIT_FIELD (cfield))
+ case MULT_EXPR:
+ {
+ /* Just track trailing zeros in both operands and transfer
+ them to the other. */
+ int r1tz = double_int_ctz (double_int_ior (r1val, r1mask));
+ int r2tz = double_int_ctz (double_int_ior (r2val, r2mask));
+ if (r1tz + r2tz >= HOST_BITS_PER_DOUBLE_INT)
{
- STRIP_USELESS_TYPE_CONVERSION (cval);
- return cval;
+ *mask = double_int_zero;
+ *val = double_int_zero;
}
- break;
+ else if (r1tz + r2tz > 0)
+ {
+ *mask = double_int_not (double_int_mask (r1tz + r2tz));
+ *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
+ *val = double_int_zero;
+ }
+ break;
+ }
- case REALPART_EXPR:
- case IMAGPART_EXPR:
+ case EQ_EXPR:
+ case NE_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);
+ double_int m = double_int_ior (r1mask, r2mask);
+ if (!double_int_equal_p (double_int_and_not (r1val, m),
+ double_int_and_not (r2val, m)))
+ {
+ *mask = double_int_zero;
+ *val = ((code == EQ_EXPR) ? double_int_zero : double_int_one);
+ }
+ else
+ {
+ /* We know the result of a comparison is always one or zero. */
+ *mask = double_int_one;
+ *val = double_int_zero;
+ }
break;
}
- case INDIRECT_REF:
+ case GE_EXPR:
+ case GT_EXPR:
+ {
+ double_int tem = r1val;
+ r1val = r2val;
+ r2val = tem;
+ tem = r1mask;
+ r1mask = r2mask;
+ r2mask = tem;
+ code = swap_tree_comparison (code);
+ }
+ /* Fallthru. */
+ case LT_EXPR:
+ case LE_EXPR:
{
- tree base = TREE_OPERAND (t, 0);
- if (TREE_CODE (base) == SSA_NAME
- && (value = get_value (base))
- && value->lattice_val == CONSTANT
- && TREE_CODE (value->value) == ADDR_EXPR)
- return fold_const_aggregate_ref (TREE_OPERAND (value->value, 0));
+ int minmax, maxmin;
+ /* If the most significant bits are not known we know nothing. */
+ if (double_int_negative_p (r1mask) || double_int_negative_p (r2mask))
+ break;
+
+ /* If we know the most significant bits we know the values
+ value ranges by means of treating varying bits as zero
+ or one. Do a cross comparison of the max/min pairs. */
+ maxmin = double_int_cmp (double_int_ior (r1val, r1mask),
+ double_int_and_not (r2val, r2mask), uns);
+ minmax = double_int_cmp (double_int_and_not (r1val, r1mask),
+ double_int_ior (r2val, r2mask), uns);
+ if (maxmin < 0) /* r1 is less than r2. */
+ {
+ *mask = double_int_zero;
+ *val = double_int_one;
+ }
+ else if (minmax > 0) /* r1 is not less or equal to r2. */
+ {
+ *mask = double_int_zero;
+ *val = double_int_zero;
+ }
+ else if (maxmin == minmax) /* r1 and r2 are equal. */
+ {
+ /* This probably should never happen as we'd have
+ folded the thing during fully constant value folding. */
+ *mask = double_int_zero;
+ *val = (code == LE_EXPR ? double_int_one : double_int_zero);
+ }
+ else
+ {
+ /* We know the result of a comparison is always one or zero. */
+ *mask = double_int_one;
+ *val = double_int_zero;
+ }
break;
}
- default:
- break;
+ default:;
}
-
- return NULL_TREE;
}
-
-/* Evaluate statement STMT. */
+
+/* Return the propagation value when applying the operation CODE to
+ the value RHS yielding type TYPE. */
static prop_value_t
-evaluate_stmt (tree stmt)
+bit_value_unop (enum tree_code code, tree type, tree rhs)
{
+ prop_value_t rval = get_value_for_expr (rhs, true);
+ double_int value, mask;
prop_value_t val;
- tree simplified = NULL_TREE;
- ccp_lattice_t likelyvalue = likely_value (stmt);
- bool is_constant;
-
- val.mem_ref = NULL_TREE;
+ gcc_assert ((rval.lattice_val == CONSTANT
+ && TREE_CODE (rval.value) == INTEGER_CST)
+ || double_int_minus_one_p (rval.mask));
+ bit_value_unop_1 (code, type, &value, &mask,
+ TREE_TYPE (rhs), value_to_double_int (rval), rval.mask);
+ if (!double_int_minus_one_p (mask))
+ {
+ val.lattice_val = CONSTANT;
+ val.mask = mask;
+ /* ??? Delay building trees here. */
+ val.value = double_int_to_tree (type, value);
+ }
+ else
+ {
+ val.lattice_val = VARYING;
+ val.value = NULL_TREE;
+ val.mask = double_int_minus_one;
+ }
+ return val;
+}
- fold_defer_overflow_warnings ();
+/* Return the propagation value when applying the operation CODE to
+ the values RHS1 and RHS2 yielding type TYPE. */
- /* If the statement is likely to have a CONSTANT result, then try
- to fold the statement to determine the constant value. */
- if (likelyvalue == CONSTANT)
- 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)
- simplified = get_rhs (stmt);
+static prop_value_t
+bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
+{
+ prop_value_t r1val = get_value_for_expr (rhs1, true);
+ prop_value_t r2val = get_value_for_expr (rhs2, true);
+ double_int value, mask;
+ prop_value_t val;
+ gcc_assert ((r1val.lattice_val == CONSTANT
+ && TREE_CODE (r1val.value) == INTEGER_CST)
+ || double_int_minus_one_p (r1val.mask));
+ gcc_assert ((r2val.lattice_val == CONSTANT
+ && TREE_CODE (r2val.value) == INTEGER_CST)
+ || double_int_minus_one_p (r2val.mask));
+ bit_value_binop_1 (code, type, &value, &mask,
+ TREE_TYPE (rhs1), value_to_double_int (r1val), r1val.mask,
+ TREE_TYPE (rhs2), value_to_double_int (r2val), r2val.mask);
+ if (!double_int_minus_one_p (mask))
+ {
+ val.lattice_val = CONSTANT;
+ val.mask = mask;
+ /* ??? Delay building trees here. */
+ val.value = double_int_to_tree (type, value);
+ }
+ else
+ {
+ val.lattice_val = VARYING;
+ val.value = NULL_TREE;
+ val.mask = double_int_minus_one;
+ }
+ return val;
+}
- is_constant = simplified && is_gimple_min_invariant (simplified);
+/* Evaluate statement STMT.
+ Valid only for assignments, calls, conditionals, and switches. */
- fold_undefer_overflow_warnings (is_constant, stmt, 0);
+static prop_value_t
+evaluate_stmt (gimple stmt)
+{
+ prop_value_t val;
+ tree simplified = NULL_TREE;
+ ccp_lattice_t likelyvalue = likely_value (stmt);
+ bool is_constant = false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n");
}
- if (is_constant)
+ /* If the statement is likely to have a CONSTANT result, then try
+ to fold the statement to determine the constant value. */
+ /* FIXME. This is the only place that we call ccp_fold.
+ Since likely_value never returns CONSTANT for calls, we will
+ not attempt to fold them, including builtins that may profit. */
+ if (likelyvalue == CONSTANT)
{
- /* The statement produced a constant value. */
- val.lattice_val = CONSTANT;
- val.value = simplified;
+ fold_defer_overflow_warnings ();
+ simplified = ccp_fold (stmt);
+ is_constant = simplified && is_gimple_min_invariant (simplified);
+ fold_undefer_overflow_warnings (is_constant, stmt, 0);
+ if (is_constant)
+ {
+ /* The statement produced a constant value. */
+ val.lattice_val = CONSTANT;
+ val.value = simplified;
+ val.mask = double_int_zero;
+ }
}
- else
- {
- /* The statement produced a nonconstant value. If the statement
- 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;
-}
-
-
-/* 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). */
-
-static enum ssa_prop_result
-visit_assignment (tree stmt, tree *output_p)
-{
- prop_value_t val;
- tree lhs, rhs;
- enum ssa_prop_result retval;
-
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- rhs = GIMPLE_STMT_OPERAND (stmt, 1);
-
- if (TREE_CODE (rhs) == SSA_NAME)
- {
- /* For a simple copy operation, we copy the lattice values. */
- prop_value_t *nval = get_value (rhs);
- val = *nval;
- }
- 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. 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. */
- val = evaluate_stmt (stmt);
-
- retval = SSA_PROP_NOT_INTERESTING;
-
- /* Set the lattice value of the statement's output. */
- if (TREE_CODE (lhs) == SSA_NAME)
- {
- /* 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 if (do_store_ccp && stmt_makes_single_store (stmt))
- {
- /* 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;
-
- /* Mark VAL as stored in the LHS of this assignment. */
- if (val.lattice_val == CONSTANT)
- 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)
- {
- /* 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;
-
- 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;
-}
-
-
-/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
- if it can determine which edge will be taken. Otherwise, return
- SSA_PROP_VARYING. */
-
-static enum ssa_prop_result
-visit_cond_stmt (tree stmt, edge *taken_edge_p)
-{
- prop_value_t 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,
- 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;
-}
-
-
-/* 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. */
-
-static enum ssa_prop_result
-ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
-{
- tree def;
- ssa_op_iter iter;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nVisiting statement:\n");
- print_generic_stmt (dump_file, stmt, dump_flags);
- }
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
- {
- /* If the statement is an assignment that produces a single
- output value, evaluate its RHS to see if the lattice value of
- its output has changed. */
- return visit_assignment (stmt, output_p);
- }
- else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
- {
- /* If STMT is a conditional branch, see if we can determine
- which branch will be taken. */
- return visit_cond_stmt (stmt, taken_edge_p);
- }
-
- /* 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");
-
- /* Definitions made by statements other than assignments to
- SSA_NAMEs represent unknown modifications to their outputs.
- Mark them VARYING. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
- {
- prop_value_t v = { VARYING, NULL_TREE, NULL_TREE };
- set_lattice_value (def, v);
- }
-
- return SSA_PROP_VARYING;
-}
-
-
-/* Main entry point for SSA Conditional Constant Propagation. */
-
-static unsigned int
-execute_ssa_ccp (bool store_ccp)
-{
- do_store_ccp = store_ccp;
- ccp_initialize ();
- ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
- if (ccp_finalize ())
- return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
- else
- return 0;
-}
-
-
-static unsigned int
-do_ssa_ccp (void)
-{
- return execute_ssa_ccp (false);
-}
-
-
-static bool
-gate_ccp (void)
-{
- return flag_tree_ccp != 0;
-}
-
-
-struct gimple_opt_pass pass_ccp =
-{
- {
- GIMPLE_PASS,
- "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, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func | TODO_verify_ssa
- | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
- }
-};
-
-
-static unsigned int
-do_ssa_store_ccp (void)
-{
- /* If STORE-CCP is not enabled, we just run regular CCP. */
- return 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 gimple_opt_pass pass_store_ccp =
-{
- {
- GIMPLE_PASS,
- "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_verify_ssa
- | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
- }
-};
-
-/* 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. */
-
-static tree
-maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type,
- bool allow_negative_idx)
-{
- tree min_idx, idx, idx_type, elt_offset = integer_zero_node;
- tree array_type, elt_type, elt_size;
- tree domain_type;
-
- /* If BASE is an ARRAY_REF, we can pick up another offset (this time
- measured in units of the size of elements type) from that ARRAY_REF).
- We can't do anything if either is variable.
-
- The case we handle here is *(&A[N]+O). */
- if (TREE_CODE (base) == ARRAY_REF)
- {
- tree low_bound = array_ref_low_bound (base);
-
- elt_offset = TREE_OPERAND (base, 1);
- if (TREE_CODE (low_bound) != INTEGER_CST
- || TREE_CODE (elt_offset) != INTEGER_CST)
- return NULL_TREE;
-
- elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0);
- base = TREE_OPERAND (base, 0);
- }
-
- /* Ignore stupid user tricks of indexing non-array variables. */
- array_type = TREE_TYPE (base);
- if (TREE_CODE (array_type) != ARRAY_TYPE)
- return NULL_TREE;
- elt_type = TREE_TYPE (array_type);
- if (!useless_type_conversion_p (orig_type, elt_type))
- return NULL_TREE;
-
- /* Use signed size type for intermediate computation on the index. */
- idx_type = signed_type_for (size_type_node);
-
- /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
- element type (so we can use the alignment if it's not constant).
- Otherwise, compute the offset as an index by using a division. If the
- division isn't exact, then don't do anything. */
- elt_size = TYPE_SIZE_UNIT (elt_type);
- if (!elt_size)
- return NULL;
- if (integer_zerop (offset))
- {
- if (TREE_CODE (elt_size) != INTEGER_CST)
- elt_size = size_int (TYPE_ALIGN (elt_type));
-
- idx = build_int_cst (idx_type, 0);
- }
- else
- {
- unsigned HOST_WIDE_INT lquo, lrem;
- HOST_WIDE_INT hquo, hrem;
- double_int soffset;
-
- /* The final array offset should be signed, so we need
- to sign-extend the (possibly pointer) offset here
- and use signed division. */
- soffset = double_int_sext (tree_to_double_int (offset),
- TYPE_PRECISION (TREE_TYPE (offset)));
- if (TREE_CODE (elt_size) != INTEGER_CST
- || div_and_round_double (TRUNC_DIV_EXPR, 0,
- soffset.low, soffset.high,
- TREE_INT_CST_LOW (elt_size),
- TREE_INT_CST_HIGH (elt_size),
- &lquo, &hquo, &lrem, &hrem)
- || lrem || hrem)
- return NULL_TREE;
-
- idx = build_int_cst_wide (idx_type, lquo, hquo);
- }
-
- /* Assume the low bound is zero. If there is a domain type, get the
- low bound, if any, convert the index into that type, and add the
- low bound. */
- min_idx = build_int_cst (idx_type, 0);
- domain_type = TYPE_DOMAIN (array_type);
- if (domain_type)
- {
- idx_type = domain_type;
- if (TYPE_MIN_VALUE (idx_type))
- min_idx = TYPE_MIN_VALUE (idx_type);
- else
- min_idx = fold_convert (idx_type, min_idx);
-
- if (TREE_CODE (min_idx) != INTEGER_CST)
- return NULL_TREE;
-
- elt_offset = fold_convert (idx_type, elt_offset);
- }
-
- if (!integer_zerop (min_idx))
- idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0);
- if (!integer_zerop (elt_offset))
- idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0);
-
- /* Make sure to possibly truncate late after offsetting. */
- idx = fold_convert (idx_type, idx);
-
- /* We don't want to construct access past array bounds. For example
- char *(c[4]);
- c[3][2];
- should not be simplified into (*c)[14] or tree-vrp will
- give false warnings. The same is true for
- struct A { long x; char d[0]; } *a;
- (char *)a - 4;
- which should be not folded to &a->d[-8]. */
- if (domain_type
- && TYPE_MAX_VALUE (domain_type)
- && TREE_CODE (TYPE_MAX_VALUE (domain_type)) == INTEGER_CST)
- {
- tree up_bound = TYPE_MAX_VALUE (domain_type);
-
- if (tree_int_cst_lt (up_bound, idx)
- /* Accesses after the end of arrays of size 0 (gcc
- extension) and 1 are likely intentional ("struct
- hack"). */
- && compare_tree_int (up_bound, 1) > 0)
- return NULL_TREE;
- }
- if (domain_type
- && TYPE_MIN_VALUE (domain_type))
- {
- if (!allow_negative_idx
- && TREE_CODE (TYPE_MIN_VALUE (domain_type)) == INTEGER_CST
- && tree_int_cst_lt (idx, TYPE_MIN_VALUE (domain_type)))
- return NULL_TREE;
- }
- else if (!allow_negative_idx
- && compare_tree_int (idx, 0) < 0)
- return NULL_TREE;
-
- return build4 (ARRAY_REF, elt_type, base, idx, NULL_TREE, NULL_TREE);
-}
-
-
-/* Attempt to fold *(S+O) to S.X.
- BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE
- is the desired result type. */
-
-static tree
-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, field_offset;
- tree ret;
- tree new_base;
-
- if (TREE_CODE (record_type) != RECORD_TYPE
- && TREE_CODE (record_type) != UNION_TYPE
- && TREE_CODE (record_type) != QUAL_UNION_TYPE)
- return NULL_TREE;
-
- /* Short-circuit silly cases. */
- if (useless_type_conversion_p (record_type, orig_type))
- return NULL_TREE;
-
- tail_array_field = NULL_TREE;
- for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
+ /* If the statement is likely to have a VARYING result, then do not
+ bother folding the statement. */
+ else if (likelyvalue == VARYING)
{
- int cmp;
-
- if (TREE_CODE (f) != FIELD_DECL)
- continue;
- if (DECL_BIT_FIELD (f))
- continue;
-
- if (!DECL_FIELD_OFFSET (f))
- continue;
- field_offset = byte_position (f);
- if (TREE_CODE (field_offset) != INTEGER_CST)
- continue;
-
- /* ??? Java creates "interesting" fields for representing base classes.
- They have no name, and have no context. With no context, we get into
- trouble with nonoverlapping_component_refs_p. Skip them. */
- if (!DECL_FIELD_CONTEXT (f))
- continue;
-
- /* The previous array field isn't at the end. */
- tail_array_field = NULL_TREE;
-
- /* Check to see if this offset overlaps with the field. */
- cmp = tree_int_cst_compare (field_offset, offset);
- if (cmp > 0)
- continue;
-
- field_type = TREE_TYPE (f);
-
- /* Here we exactly match the offset being checked. If the types match,
- then we can return that field. */
- if (cmp == 0
- && useless_type_conversion_p (orig_type, field_type))
- {
- if (base_is_ptr)
- base = build1 (INDIRECT_REF, record_type, base);
- 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;
-
- /* 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;
+ enum gimple_code code = gimple_code (stmt);
+ if (code == GIMPLE_ASSIGN)
+ {
+ enum tree_code subcode = gimple_assign_rhs_code (stmt);
- /* If we matched, then set offset to the displacement into
- this field. */
- if (base_is_ptr)
- new_base = build1 (INDIRECT_REF, record_type, base);
+ /* Other cases cannot satisfy is_gimple_min_invariant
+ without folding. */
+ if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
+ simplified = gimple_assign_rhs1 (stmt);
+ }
+ else if (code == GIMPLE_SWITCH)
+ simplified = gimple_switch_index (stmt);
else
- new_base = base;
- new_base = build3 (COMPONENT_REF, field_type, new_base, f, NULL_TREE);
-
- /* Recurse to possibly find the match. */
- ret = maybe_fold_offset_to_array_ref (new_base, t, orig_type,
- f == TYPE_FIELDS (record_type));
- if (ret)
- return ret;
- ret = maybe_fold_offset_to_component_ref (field_type, new_base, t,
- orig_type, false);
- if (ret)
- return ret;
- }
-
- if (!tail_array_field)
- return NULL_TREE;
-
- f = tail_array_field;
- field_type = TREE_TYPE (f);
- offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1);
-
- /* 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 = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE);
-
- t = maybe_fold_offset_to_array_ref (base, offset, orig_type,
- f == TYPE_FIELDS (record_type));
- if (t)
- return t;
- return maybe_fold_offset_to_component_ref (field_type, base, offset,
- orig_type, false);
-}
-
-/* Attempt to express (ORIG_TYPE)BASE+OFFSET as BASE->field_of_orig_type
- or BASE[index] or by combination of those.
-
- Before attempting the conversion strip off existing ADDR_EXPRs and
- handled component refs. */
-
-tree
-maybe_fold_offset_to_reference (tree base, tree offset, tree orig_type)
-{
- tree ret;
- tree type;
- bool base_is_ptr = true;
-
- STRIP_NOPS (base);
- if (TREE_CODE (base) == ADDR_EXPR)
- {
- base_is_ptr = false;
-
- base = TREE_OPERAND (base, 0);
-
- /* Handle case where existing COMPONENT_REF pick e.g. wrong field of union,
- so it needs to be removed and new COMPONENT_REF constructed.
- The wrong COMPONENT_REF are often constructed by folding the
- (type *)&object within the expression (type *)&object+offset */
- if (handled_component_p (base) && 0)
- {
- HOST_WIDE_INT sub_offset, size, maxsize;
- tree newbase;
- newbase = get_ref_base_and_extent (base, &sub_offset,
- &size, &maxsize);
- gcc_assert (newbase);
- gcc_assert (!(sub_offset & (BITS_PER_UNIT - 1)));
- if (size == maxsize)
- {
- base = newbase;
- if (sub_offset)
- offset = int_const_binop (PLUS_EXPR, offset,
- build_int_cst (TREE_TYPE (offset),
- sub_offset / BITS_PER_UNIT), 1);
- }
- }
- if (useless_type_conversion_p (orig_type, TREE_TYPE (base))
- && integer_zerop (offset))
- return base;
- type = TREE_TYPE (base);
- }
- else
- {
- base_is_ptr = true;
- if (!POINTER_TYPE_P (TREE_TYPE (base)))
- return NULL_TREE;
- type = TREE_TYPE (TREE_TYPE (base));
- }
- ret = maybe_fold_offset_to_component_ref (type, base, offset,
- orig_type, base_is_ptr);
- if (!ret)
- {
- if (base_is_ptr)
- base = build1 (INDIRECT_REF, type, base);
- ret = maybe_fold_offset_to_array_ref (base, offset, orig_type, true);
- }
- return ret;
-}
-
-/* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET).
- Return the simplified expression, or NULL if nothing could be done. */
-
-static tree
-maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
-{
- tree t;
- bool volatile_p = TREE_THIS_VOLATILE (expr);
-
- /* We may well have constructed a double-nested PLUS_EXPR via multiple
- substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that
- are sometimes added. */
- base = fold (base);
- STRIP_TYPE_NOPS (base);
- TREE_OPERAND (expr, 0) = base;
-
- /* One possibility is that the address reduces to a string constant. */
- t = fold_read_from_constant_string (expr);
- if (t)
- return t;
-
- /* Add in any offset from a POINTER_PLUS_EXPR. */
- if (TREE_CODE (base) == POINTER_PLUS_EXPR)
- {
- tree offset2;
-
- offset2 = TREE_OPERAND (base, 1);
- if (TREE_CODE (offset2) != INTEGER_CST)
- return NULL_TREE;
- base = TREE_OPERAND (base, 0);
-
- offset = fold_convert (sizetype,
- int_const_binop (PLUS_EXPR, offset, offset2, 1));
- }
-
- if (TREE_CODE (base) == ADDR_EXPR)
- {
- tree base_addr = base;
-
- /* Strip the ADDR_EXPR. */
- base = TREE_OPERAND (base, 0);
-
- /* Fold away CONST_DECL to its value, if the type is scalar. */
- if (TREE_CODE (base) == CONST_DECL
- && is_gimple_min_invariant (DECL_INITIAL (base)))
- return DECL_INITIAL (base);
-
- /* Try folding *(&B+O) to B.X. */
- t = maybe_fold_offset_to_reference (base_addr, offset,
- TREE_TYPE (expr));
- if (t)
- {
- TREE_THIS_VOLATILE (t) = volatile_p;
- return t;
- }
- }
- else
- {
- /* 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 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. */
-
- t = base;
- STRIP_NOPS (t);
- if (TREE_CODE (t) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
- {
- /* FIXME: Except that this causes problems elsewhere with dead
- 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
- fold_read_from_constant_string directly, rather than
- re-checking for it here. */
- return integer_zero_node;
- }
-
- /* Try folding *(B+O) to B->X. Still an improvement. */
- if (POINTER_TYPE_P (TREE_TYPE (base)))
+ /* These cannot satisfy is_gimple_min_invariant without folding. */
+ gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
+ is_constant = simplified && is_gimple_min_invariant (simplified);
+ if (is_constant)
{
- t = maybe_fold_offset_to_reference (base, offset,
- TREE_TYPE (expr));
- if (t)
- return t;
+ /* The statement produced a constant value. */
+ val.lattice_val = CONSTANT;
+ val.value = simplified;
+ val.mask = double_int_zero;
}
}
- /* Otherwise we had an offset that we could not simplify. */
- return NULL_TREE;
-}
-
-
-/* A subroutine of fold_stmt_r. EXPR is a POINTER_PLUS_EXPR.
-
- A quaint feature extant in our address arithmetic is that there
- can be hidden type changes here. The type of the result need
- not be the same as the type of the input pointer.
-
- What we're after here is an expression of the form
- (T *)(&array + const)
- where the cast doesn't actually exist, but is implicit in the
- type of the POINTER_PLUS_EXPR. We'd like to turn this into
- &array[x]
- which may be able to propagate further. */
-
-static tree
-maybe_fold_stmt_addition (tree expr)
-{
- tree op0 = TREE_OPERAND (expr, 0);
- tree op1 = TREE_OPERAND (expr, 1);
- tree ptr_type = TREE_TYPE (expr);
- tree ptd_type;
- tree t;
-
- gcc_assert (TREE_CODE (expr) == POINTER_PLUS_EXPR);
-
- /* It had better be a constant. */
- if (TREE_CODE (op1) != INTEGER_CST)
- return NULL_TREE;
- /* The first operand should be an ADDR_EXPR. */
- if (TREE_CODE (op0) != ADDR_EXPR)
- return NULL_TREE;
- op0 = TREE_OPERAND (op0, 0);
-
- /* If the first operand is an ARRAY_REF, expand it so that we can fold
- the offset into it. */
- while (TREE_CODE (op0) == ARRAY_REF)
+ /* Resort to simplification for bitwise tracking. */
+ if (flag_tree_bit_ccp
+ && likelyvalue == CONSTANT
+ && !is_constant)
{
- tree array_obj = TREE_OPERAND (op0, 0);
- tree array_idx = TREE_OPERAND (op0, 1);
- tree elt_type = TREE_TYPE (op0);
- tree elt_size = TYPE_SIZE_UNIT (elt_type);
- tree min_idx;
-
- if (TREE_CODE (array_idx) != INTEGER_CST)
- break;
- if (TREE_CODE (elt_size) != INTEGER_CST)
- break;
-
- /* Un-bias the index by the min index of the array type. */
- min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
- if (min_idx)
- {
- min_idx = TYPE_MIN_VALUE (min_idx);
- if (min_idx)
- {
- if (TREE_CODE (min_idx) != INTEGER_CST)
- break;
-
- 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 = 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. */
- op1 = int_const_binop (PLUS_EXPR,
- array_idx, op1, 0);
- op0 = array_obj;
- }
-
- ptd_type = TREE_TYPE (ptr_type);
- /* If we want a pointer to void, reconstruct the reference from the
- array element type. A pointer to that can be trivially converted
- to void *. This happens as we fold (void *)(ptr p+ off). */
- if (VOID_TYPE_P (ptd_type)
- && TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE)
- ptd_type = TREE_TYPE (TREE_TYPE (op0));
-
- /* At which point we can try some of the same things as for indirects. */
- t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type, true);
- if (!t)
- t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
- ptd_type, false);
- if (t)
- t = build1 (ADDR_EXPR, ptr_type, t);
-
- return t;
-}
-
-/* For passing state through walk_tree into fold_stmt_r and its
- children. */
-
-struct fold_stmt_r_data
-{
- tree stmt;
- 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)
-{
- 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;
- bool volatile_p = TREE_THIS_VOLATILE (expr);
-
- /* ??? It'd be nice if walk_tree had a pre-order option. */
- switch (TREE_CODE (expr))
- {
- case INDIRECT_REF:
- t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
- if (t)
- return t;
- *walk_subtrees = 0;
-
- t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
- integer_zero_node);
- if (!t
- && TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR)
- /* If we had a good reason for propagating the address here,
- make sure we end up with valid gimple. See PR34989. */
- t = TREE_OPERAND (TREE_OPERAND (expr, 0), 0);
- break;
-
- case NOP_EXPR:
- t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
- if (t)
- return t;
- *walk_subtrees = 0;
-
- if (POINTER_TYPE_P (TREE_TYPE (expr))
- && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))
- && (t = maybe_fold_offset_to_reference
- (TREE_OPERAND (expr, 0),
- integer_zero_node,
- TREE_TYPE (TREE_TYPE (expr)))))
+ enum gimple_code code = gimple_code (stmt);
+ tree fndecl;
+ val.lattice_val = VARYING;
+ val.value = NULL_TREE;
+ val.mask = double_int_minus_one;
+ if (code == GIMPLE_ASSIGN)
{
- tree ptr_type = build_pointer_type (TREE_TYPE (t));
- if (!useless_type_conversion_p (TREE_TYPE (expr), ptr_type))
- return NULL_TREE;
- t = build_fold_addr_expr_with_type (t, ptr_type);
- }
- break;
-
- /* ??? 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;
-
- /* Make sure the value is properly considered constant, and so gets
- propagated as expected. */
- if (*changed_p)
- recompute_tree_invariant_for_addr_expr (expr);
- return NULL_TREE;
-
- case POINTER_PLUS_EXPR:
- t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
- if (t)
- return t;
- t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
- if (t)
- return t;
- *walk_subtrees = 0;
-
- t = maybe_fold_stmt_addition (expr);
- break;
-
- case COMPONENT_REF:
- t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
- if (t)
- return t;
- *walk_subtrees = 0;
-
- /* Make sure the FIELD_DECL is actually a field in the type on the lhs.
- We've already checked that the records are compatible, so we should
- come up with a set of compatible fields. */
- {
- tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0));
- tree expr_field = TREE_OPERAND (expr, 1);
-
- if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record))
- {
- expr_field = find_compatible_field (expr_record, expr_field);
- TREE_OPERAND (expr, 1) = expr_field;
- }
- }
- 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;
- bool set;
-
- fold_defer_overflow_warnings ();
- tem = fold_binary (TREE_CODE (op0), TREE_TYPE (op0),
- TREE_OPERAND (op0, 0),
- TREE_OPERAND (op0, 1));
- set = tem && set_rhs (expr_p, tem);
- fold_undefer_overflow_warnings (set, fold_stmt_r_data->stmt, 0);
- if (set)
+ enum tree_code subcode = gimple_assign_rhs_code (stmt);
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ switch (get_gimple_rhs_class (subcode))
{
- t = *expr_p;
+ case GIMPLE_SINGLE_RHS:
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+ || POINTER_TYPE_P (TREE_TYPE (rhs1)))
+ val = get_value_for_expr (rhs1, true);
break;
- }
- }
- return NULL_TREE;
-
- default:
- return NULL_TREE;
- }
-
- if (t)
- {
- /* Preserve volatileness of the original expression. */
- TREE_THIS_VOLATILE (t) = volatile_p;
- *expr_p = t;
- *changed_p = true;
- }
-
- return NULL_TREE;
-}
+ case GIMPLE_UNARY_RHS:
+ if ((INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+ || POINTER_TYPE_P (TREE_TYPE (rhs1)))
+ && (INTEGRAL_TYPE_P (gimple_expr_type (stmt))
+ || POINTER_TYPE_P (gimple_expr_type (stmt))))
+ val = bit_value_unop (subcode, gimple_expr_type (stmt), rhs1);
+ break;
-/* 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. */
+ case GIMPLE_BINARY_RHS:
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+ || POINTER_TYPE_P (TREE_TYPE (rhs1)))
+ {
+ tree rhs2 = gimple_assign_rhs2 (stmt);
+ val = bit_value_binop (subcode,
+ TREE_TYPE (rhs1), rhs1, rhs2);
+ }
+ break;
-static bool
-get_maxval_strlen (tree arg, tree *length, bitmap visited, int type)
-{
- tree var, def_stmt, val;
-
- if (TREE_CODE (arg) != SSA_NAME)
- {
- if (TREE_CODE (arg) == COND_EXPR)
- return get_maxval_strlen (COND_EXPR_THEN (arg), length, visited, type)
- && get_maxval_strlen (COND_EXPR_ELSE (arg), length, visited, type);
- /* We can end up with &(*iftmp_1)[0] here as well, so handle it. */
- else if (TREE_CODE (arg) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (arg, 0)) == ARRAY_REF
- && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg, 0), 1)))
- {
- tree aop0 = TREE_OPERAND (TREE_OPERAND (arg, 0), 0);
- if (TREE_CODE (aop0) == INDIRECT_REF
- && TREE_CODE (TREE_OPERAND (aop0, 0)) == SSA_NAME)
- return get_maxval_strlen (TREE_OPERAND (aop0, 0),
- length, visited, type);
+ default:;
+ }
}
-
- if (type == 2)
+ else if (code == GIMPLE_COND)
{
- val = arg;
- if (TREE_CODE (val) != INTEGER_CST
- || tree_int_cst_sgn (val) < 0)
- return false;
+ enum tree_code code = gimple_cond_code (stmt);
+ tree rhs1 = gimple_cond_lhs (stmt);
+ tree rhs2 = gimple_cond_rhs (stmt);
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+ || POINTER_TYPE_P (TREE_TYPE (rhs1)))
+ val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
}
- else
- val = c_strlen (arg, 1);
- if (!val)
- return false;
-
- if (*length)
+ else if (code == GIMPLE_CALL
+ && (fndecl = gimple_call_fndecl (stmt))
+ && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
{
- if (type > 0)
+ switch (DECL_FUNCTION_CODE (fndecl))
{
- if (TREE_CODE (*length) != INTEGER_CST
- || TREE_CODE (val) != INTEGER_CST)
- return false;
+ case BUILT_IN_MALLOC:
+ case BUILT_IN_REALLOC:
+ case BUILT_IN_CALLOC:
+ val.lattice_val = CONSTANT;
+ val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
+ val.mask = shwi_to_double_int
+ (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT)
+ / BITS_PER_UNIT - 1));
+ break;
+
+ case BUILT_IN_ALLOCA:
+ val.lattice_val = CONSTANT;
+ val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
+ val.mask = shwi_to_double_int
+ (~(((HOST_WIDE_INT) BIGGEST_ALIGNMENT)
+ / BITS_PER_UNIT - 1));
+ break;
- if (tree_int_cst_lt (*length, val))
- *length = val;
- return true;
+ default:;
}
- else if (simple_cst_equal (val, *length) != 1)
- return false;
}
-
- *length = val;
- return true;
+ is_constant = (val.lattice_val == CONSTANT);
}
- /* If we were already here, break the infinite cycle. */
- if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
- return true;
- bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
-
- var = arg;
- def_stmt = SSA_NAME_DEF_STMT (var);
-
- switch (TREE_CODE (def_stmt))
+ if (!is_constant)
{
- case GIMPLE_MODIFY_STMT:
+ /* The statement produced a nonconstant value. If the statement
+ had UNDEFINED operands, then the result of the statement
+ should be UNDEFINED. Otherwise, the statement is VARYING. */
+ if (likelyvalue == UNDEFINED)
{
- 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 = GIMPLE_STMT_OPERAND (def_stmt, 1);
- STRIP_NOPS (rhs);
- return get_maxval_strlen (rhs, length, visited, type);
+ val.lattice_val = likelyvalue;
+ val.mask = double_int_zero;
}
-
- case PHI_NODE:
+ else
{
- /* All the arguments of the PHI node must have the same constant
- length. */
- int i;
-
- for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
- {
- tree arg = PHI_ARG_DEF (def_stmt, i);
-
- /* 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 (!get_maxval_strlen (arg, length, visited, type))
- return false;
- }
-
- return true;
+ val.lattice_val = VARYING;
+ val.mask = double_int_minus_one;
}
- default:
- break;
+ val.value = NULL_TREE;
}
-
- return false;
+ return val;
}
+/* Fold the stmt at *GSI with CCP specific information that propagating
+ and regular folding does not catch. */
-/* Fold builtin call FN in statement STMT. If it cannot be folded into a
- constant, return NULL_TREE. Otherwise, return its constant value. */
-
-static tree
-ccp_fold_builtin (tree stmt, tree fn)
+static bool
+ccp_fold_stmt (gimple_stmt_iterator *gsi)
{
- tree result, val[3];
- tree callee, a;
- int arg_mask, i, type;
- bitmap visited;
- bool ignore;
- call_expr_arg_iterator iter;
- int nargs;
+ gimple stmt = gsi_stmt (*gsi);
- ignore = TREE_CODE (stmt) != GIMPLE_MODIFY_STMT;
-
- /* First try the generic builtin folder. If that succeeds, return the
- result directly. */
- result = fold_call_expr (fn, ignore);
- if (result)
+ switch (gimple_code (stmt))
{
- if (ignore)
- STRIP_NOPS (result);
- return result;
- }
+ case GIMPLE_COND:
+ {
+ prop_value_t val;
+ /* Statement evaluation will handle type mismatches in constants
+ more gracefully than the final propagation. This allows us to
+ fold more conditionals here. */
+ val = evaluate_stmt (stmt);
+ if (val.lattice_val != CONSTANT
+ || !double_int_zero_p (val.mask))
+ return false;
- /* Ignore MD builtins. */
- callee = get_callee_fndecl (fn);
- if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
- return NULL_TREE;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Folding predicate ");
+ print_gimple_expr (dump_file, stmt, 0, 0);
+ fprintf (dump_file, " to ");
+ print_generic_expr (dump_file, val.value, 0);
+ fprintf (dump_file, "\n");
+ }
- /* If the builtin could not be folded, and it has no argument list,
- we're done. */
- nargs = call_expr_nargs (fn);
- if (nargs == 0)
- return NULL_TREE;
+ if (integer_zerop (val.value))
+ gimple_cond_make_false (stmt);
+ else
+ gimple_cond_make_true (stmt);
- /* Limit the work only for builtins we know how to simplify. */
- switch (DECL_FUNCTION_CODE (callee))
- {
- case BUILT_IN_STRLEN:
- case BUILT_IN_FPUTS:
- case BUILT_IN_FPUTS_UNLOCKED:
- arg_mask = 1;
- type = 0;
- break;
- case BUILT_IN_STRCPY:
- case BUILT_IN_STRNCPY:
- 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;
- }
+ return true;
+ }
- /* Try to use the dataflow information gathered by the CCP process. */
- visited = BITMAP_ALLOC (NULL);
+ case GIMPLE_CALL:
+ {
+ tree lhs = gimple_call_lhs (stmt);
+ tree val;
+ tree argt;
+ tree callee;
+ bool changed = false;
+ unsigned i;
+
+ /* If the call was folded into a constant make sure it goes
+ away even if we cannot propagate into all uses because of
+ type issues. */
+ if (lhs
+ && TREE_CODE (lhs) == SSA_NAME
+ && (val = get_constant_value (lhs)))
+ {
+ tree new_rhs = unshare_expr (val);
+ bool res;
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (new_rhs)))
+ new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
+ res = update_call_from_tree (gsi, new_rhs);
+ gcc_assert (res);
+ return true;
+ }
- memset (val, 0, sizeof (val));
- init_call_expr_arg_iterator (fn, &iter);
- for (i = 0; arg_mask; i++, arg_mask >>= 1)
- {
- a = next_call_expr_arg (&iter);
- if (arg_mask & 1)
- {
- bitmap_clear (visited);
- if (!get_maxval_strlen (a, &val[i], visited, type))
- val[i] = NULL_TREE;
- }
- }
+ /* Propagate into the call arguments. Compared to replace_uses_in
+ this can use the argument slot types for type verification
+ instead of the current argument type. We also can safely
+ drop qualifiers here as we are dealing with constants anyway. */
+ argt = TYPE_ARG_TYPES (TREE_TYPE (TREE_TYPE (gimple_call_fn (stmt))));
+ for (i = 0; i < gimple_call_num_args (stmt) && argt;
+ ++i, argt = TREE_CHAIN (argt))
+ {
+ tree arg = gimple_call_arg (stmt, i);
+ if (TREE_CODE (arg) == SSA_NAME
+ && (val = get_constant_value (arg))
+ && useless_type_conversion_p
+ (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
+ TYPE_MAIN_VARIANT (TREE_TYPE (val))))
+ {
+ gimple_call_set_arg (stmt, i, unshare_expr (val));
+ changed = true;
+ }
+ }
- BITMAP_FREE (visited);
+ callee = gimple_call_fn (stmt);
+ if (TREE_CODE (callee) == OBJ_TYPE_REF
+ && TREE_CODE (OBJ_TYPE_REF_EXPR (callee)) == SSA_NAME)
+ {
+ tree expr = OBJ_TYPE_REF_EXPR (callee);
+ OBJ_TYPE_REF_EXPR (callee) = valueize_op (expr);
+ if (TREE_CODE (OBJ_TYPE_REF_EXPR (callee)) == ADDR_EXPR)
+ {
+ tree t;
+ t = gimple_fold_obj_type_ref (callee, NULL_TREE);
+ if (t)
+ {
+ gimple_call_set_fn (stmt, t);
+ changed = true;
+ }
+ }
+ OBJ_TYPE_REF_EXPR (callee) = expr;
+ }
- result = NULL_TREE;
- switch (DECL_FUNCTION_CODE (callee))
- {
- case BUILT_IN_STRLEN:
- if (val[0])
- {
- tree new_val = 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. */
- if (is_gimple_val (new_val)
- || (is_gimple_cast (new_val)
- && is_gimple_val (TREE_OPERAND (new_val, 0))))
- return new_val;
- }
- break;
+ return changed;
+ }
- case BUILT_IN_STRCPY:
- if (val[1] && is_gimple_val (val[1]) && nargs == 2)
- result = fold_builtin_strcpy (callee,
- CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- val[1]);
- break;
+ case GIMPLE_ASSIGN:
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree val;
+
+ /* If we have a load that turned out to be constant replace it
+ as we cannot propagate into all uses in all cases. */
+ if (gimple_assign_single_p (stmt)
+ && TREE_CODE (lhs) == SSA_NAME
+ && (val = get_constant_value (lhs)))
+ {
+ tree rhs = unshare_expr (val);
+ if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
+ rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
+ gimple_assign_set_rhs_from_tree (gsi, rhs);
+ return true;
+ }
- case BUILT_IN_STRNCPY:
- if (val[1] && is_gimple_val (val[1]) && nargs == 3)
- result = fold_builtin_strncpy (callee,
- CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- CALL_EXPR_ARG (fn, 2),
- val[1]);
- break;
+ return false;
+ }
- case BUILT_IN_FPUTS:
- result = fold_builtin_fputs (CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 0,
- val[0]);
- break;
+ default:
+ return false;
+ }
+}
- case BUILT_IN_FPUTS_UNLOCKED:
- result = fold_builtin_fputs (CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- TREE_CODE (stmt) != GIMPLE_MODIFY_STMT, 1,
- val[0]);
- break;
+/* 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).
+ Value-returning call statements also perform an assignment, and
+ are handled here. */
- 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,
- CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- CALL_EXPR_ARG (fn, 2),
- CALL_EXPR_ARG (fn, 3),
- val[2], ignore,
- DECL_FUNCTION_CODE (callee));
- break;
+static enum ssa_prop_result
+visit_assignment (gimple stmt, tree *output_p)
+{
+ prop_value_t val;
+ enum ssa_prop_result retval;
- case BUILT_IN_STRCPY_CHK:
- case BUILT_IN_STPCPY_CHK:
- if (val[1] && is_gimple_val (val[1]))
- result = fold_builtin_stxcpy_chk (callee,
- CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- CALL_EXPR_ARG (fn, 2),
- val[1], ignore,
- DECL_FUNCTION_CODE (callee));
- break;
+ tree lhs = gimple_get_lhs (stmt);
- case BUILT_IN_STRNCPY_CHK:
- if (val[2] && is_gimple_val (val[2]))
- result = fold_builtin_strncpy_chk (CALL_EXPR_ARG (fn, 0),
- CALL_EXPR_ARG (fn, 1),
- CALL_EXPR_ARG (fn, 2),
- CALL_EXPR_ARG (fn, 3),
- val[2]);
- break;
+ gcc_assert (gimple_code (stmt) != GIMPLE_CALL
+ || gimple_call_lhs (stmt) != NULL_TREE);
- case BUILT_IN_SNPRINTF_CHK:
- case BUILT_IN_VSNPRINTF_CHK:
- if (val[1] && is_gimple_val (val[1]))
- result = fold_builtin_snprintf_chk (fn, val[1],
- DECL_FUNCTION_CODE (callee));
- break;
+ if (gimple_assign_single_p (stmt)
+ && gimple_assign_rhs_code (stmt) == SSA_NAME)
+ /* For a simple copy operation, we copy the lattice values. */
+ val = *get_value (gimple_assign_rhs1 (stmt));
+ else
+ /* Evaluate the statement, which could be
+ either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
+ val = evaluate_stmt (stmt);
- default:
- gcc_unreachable ();
+ retval = SSA_PROP_NOT_INTERESTING;
+
+ /* Set the lattice value of the statement's output. */
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ /* 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;
+ }
}
- if (result && ignore)
- result = fold_ignored_result (result);
- return result;
+ return retval;
}
-/* 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. */
+/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
+ if it can determine which edge will be taken. Otherwise, return
+ SSA_PROP_VARYING. */
-bool
-fold_stmt (tree *stmt_p)
+static enum ssa_prop_result
+visit_cond_stmt (gimple stmt, edge *taken_edge_p)
{
- tree rhs, result, stmt;
- struct fold_stmt_r_data fold_stmt_r_data;
- bool changed = false;
- bool inside_addr_expr = false;
+ prop_value_t val;
+ basic_block block;
+
+ block = gimple_bb (stmt);
+ val = evaluate_stmt (stmt);
+ if (val.lattice_val != CONSTANT
+ || !double_int_zero_p (val.mask))
+ return SSA_PROP_VARYING;
+
+ /* 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 = find_taken_edge (block, val.value);
+ if (*taken_edge_p)
+ return SSA_PROP_INTERESTING;
+ else
+ return SSA_PROP_VARYING;
+}
+
- stmt = *stmt_p;
+/* 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. */
- fold_stmt_r_data.stmt = stmt;
- fold_stmt_r_data.changed_p = &changed;
- fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
+static enum ssa_prop_result
+ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
+{
+ tree def;
+ ssa_op_iter iter;
- /* 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))
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- *stmt_p = build_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], 0);
- return true;
+ fprintf (dump_file, "\nVisiting statement:\n");
+ print_gimple_stmt (dump_file, stmt, 0, dump_flags);
}
- rhs = get_rhs (stmt);
- if (!rhs)
- return changed;
- result = NULL_TREE;
-
- if (TREE_CODE (rhs) == CALL_EXPR)
+ switch (gimple_code (stmt))
{
- tree callee;
+ case GIMPLE_ASSIGN:
+ /* 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);
- /* 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_call_expr does not have not information. */
- callee = CALL_EXPR_FN (rhs);
- 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;
+ case GIMPLE_CALL:
+ /* A value-returning call also performs an assignment. */
+ if (gimple_call_lhs (stmt) != NULL_TREE)
+ return visit_assignment (stmt, output_p);
+ break;
- /* ??? 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. */
+ case GIMPLE_COND:
+ case GIMPLE_SWITCH:
+ /* If STMT is a conditional branch, see if we can determine
+ which branch will be taken. */
+ /* FIXME. It appears that we should be able to optimize
+ computed GOTOs here as well. */
+ return visit_cond_stmt (stmt, taken_edge_p);
- t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
- t = lang_hooks.fold_obj_type_ref (callee, t);
- if (t)
- {
- CALL_EXPR_FN (rhs) = t;
- changed = true;
- }
- }
- }
+ default:
+ break;
}
- else if (TREE_CODE (rhs) == COND_EXPR)
+
+ /* 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");
+
+ /* 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)
{
- tree temp = fold (COND_EXPR_COND (rhs));
- if (temp != COND_EXPR_COND (rhs))
- result = fold_build3 (COND_EXPR, TREE_TYPE (rhs), temp,
- COND_EXPR_THEN (rhs), COND_EXPR_ELSE (rhs));
+ prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } };
+ set_lattice_value (def, v);
}
- /* If we couldn't fold the RHS, hand over to the generic fold routines. */
- if (result == NULL_TREE)
- result = fold (rhs);
+ return SSA_PROP_VARYING;
+}
- /* 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);
+/* Main entry point for SSA Conditional Constant Propagation. */
- return changed;
+static unsigned int
+do_ssa_ccp (void)
+{
+ ccp_initialize ();
+ ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
+ if (ccp_finalize ())
+ return (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
+ else
+ return 0;
}
-/* 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)
+static bool
+gate_ccp (void)
{
- 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.stmt = stmt;
- fold_stmt_r_data.changed_p = &changed;
- fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr;
+ return flag_tree_ccp != 0;
+}
- 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;
+struct gimple_opt_pass pass_ccp =
+{
+ {
+ GIMPLE_PASS,
+ "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, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_verify_ssa
+ | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
+ }
+};
- 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
/* Try to optimize out __builtin_stack_restore. Optimize it out
if there is another __builtin_stack_restore in the same basic
block and no calls or ASM_EXPRs are in between, or if this block's
ASM_EXPRs after this __builtin_stack_restore. */
static tree
-optimize_stack_restore (basic_block bb, tree call, block_stmt_iterator i)
+optimize_stack_restore (gimple_stmt_iterator i)
{
- tree stack_save, stmt, callee;
+ tree callee;
+ gimple stmt;
+
+ basic_block bb = gsi_bb (i);
+ gimple call = gsi_stmt (i);
- if (TREE_CODE (call) != CALL_EXPR
- || call_expr_nargs (call) != 1
- || TREE_CODE (CALL_EXPR_ARG (call, 0)) != SSA_NAME
- || !POINTER_TYPE_P (TREE_TYPE (CALL_EXPR_ARG (call, 0))))
+ if (gimple_code (call) != GIMPLE_CALL
+ || gimple_call_num_args (call) != 1
+ || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
+ || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
return NULL_TREE;
- for (bsi_next (&i); !bsi_end_p (i); bsi_next (&i))
+ for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
{
- tree call;
-
- stmt = bsi_stmt (i);
- if (TREE_CODE (stmt) == ASM_EXPR)
+ stmt = gsi_stmt (i);
+ if (gimple_code (stmt) == GIMPLE_ASM)
return NULL_TREE;
- call = get_call_expr_in (stmt);
- if (call == NULL)
+ if (gimple_code (stmt) != GIMPLE_CALL)
continue;
- callee = get_callee_fndecl (call);
- if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
+ callee = gimple_call_fndecl (stmt);
+ if (!callee
+ || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
+ /* All regular builtins are ok, just obviously not alloca. */
+ || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA)
return NULL_TREE;
if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
- break;
+ goto second_stack_restore;
}
- if (bsi_end_p (i)
- && (! single_succ_p (bb)
- || single_succ_edge (bb)->dest != EXIT_BLOCK_PTR))
- return NULL_TREE;
-
- stack_save = SSA_NAME_DEF_STMT (CALL_EXPR_ARG (call, 0));
- if (TREE_CODE (stack_save) != GIMPLE_MODIFY_STMT
- || GIMPLE_STMT_OPERAND (stack_save, 0) != CALL_EXPR_ARG (call, 0)
- || TREE_CODE (GIMPLE_STMT_OPERAND (stack_save, 1)) != CALL_EXPR
- || tree_could_throw_p (stack_save)
- || !has_single_use (CALL_EXPR_ARG (call, 0)))
+ if (!gsi_end_p (i))
return NULL_TREE;
- callee = get_callee_fndecl (GIMPLE_STMT_OPERAND (stack_save, 1));
- if (!callee
- || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
- || DECL_FUNCTION_CODE (callee) != BUILT_IN_STACK_SAVE
- || call_expr_nargs (GIMPLE_STMT_OPERAND (stack_save, 1)) != 0)
- return NULL_TREE;
-
- stmt = stack_save;
- push_stmt_changes (&stmt);
- if (!set_rhs (&stmt,
- build_int_cst (TREE_TYPE (CALL_EXPR_ARG (call, 0)), 0)))
+ /* Allow one successor of the exit block, or zero successors. */
+ switch (EDGE_COUNT (bb->succs))
{
- discard_stmt_changes (&stmt);
+ case 0:
+ break;
+ case 1:
+ if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR)
+ return NULL_TREE;
+ break;
+ default:
return NULL_TREE;
}
- gcc_assert (stmt == stack_save);
- pop_stmt_changes (&stmt);
+ second_stack_restore:
+
+ /* If there's exactly one use, then zap the call to __builtin_stack_save.
+ If there are multiple uses, then the last one should remove the call.
+ In any case, whether the call to __builtin_stack_save can be removed
+ or not is irrelevant to removing the call to __builtin_stack_restore. */
+ if (has_single_use (gimple_call_arg (call, 0)))
+ {
+ gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
+ if (is_gimple_call (stack_save))
+ {
+ callee = gimple_call_fndecl (stack_save);
+ if (callee
+ && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
+ && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
+ {
+ gimple_stmt_iterator stack_save_gsi;
+ tree rhs;
+
+ stack_save_gsi = gsi_for_stmt (stack_save);
+ rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
+ update_call_from_tree (&stack_save_gsi, rhs);
+ }
+ }
+ }
+ /* No effect, so the statement will be deleted. */
return integer_zero_node;
}
-\f
+
/* If va_list type is a simple pointer and nothing special is needed,
optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
__builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
pointer assignment. */
static tree
-optimize_stdarg_builtin (tree call)
+optimize_stdarg_builtin (gimple call)
{
tree callee, lhs, rhs, cfun_va_list;
bool va_list_simple_ptr;
+ location_t loc = gimple_location (call);
- if (TREE_CODE (call) != CALL_EXPR)
+ if (gimple_code (call) != GIMPLE_CALL)
return NULL_TREE;
- callee = get_callee_fndecl (call);
+ callee = gimple_call_fndecl (call);
cfun_va_list = targetm.fn_abi_va_list (callee);
va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
case BUILT_IN_VA_START:
if (!va_list_simple_ptr
|| targetm.expand_builtin_va_start != NULL
- || built_in_decls[BUILT_IN_NEXT_ARG] == NULL)
+ || built_in_decls[BUILT_IN_NEXT_ARG] == NULL)
return NULL_TREE;
- if (call_expr_nargs (call) != 2)
+ if (gimple_call_num_args (call) != 2)
return NULL_TREE;
- lhs = CALL_EXPR_ARG (call, 0);
+ lhs = gimple_call_arg (call, 0);
if (!POINTER_TYPE_P (TREE_TYPE (lhs))
|| TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
!= TYPE_MAIN_VARIANT (cfun_va_list))
return NULL_TREE;
- lhs = build_fold_indirect_ref (lhs);
- rhs = build_call_expr (built_in_decls[BUILT_IN_NEXT_ARG],
- 1, integer_zero_node);
- rhs = fold_convert (TREE_TYPE (lhs), rhs);
+ lhs = build_fold_indirect_ref_loc (loc, lhs);
+ rhs = build_call_expr_loc (loc, built_in_decls[BUILT_IN_NEXT_ARG],
+ 1, integer_zero_node);
+ rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
case BUILT_IN_VA_COPY:
if (!va_list_simple_ptr)
return NULL_TREE;
- if (call_expr_nargs (call) != 2)
+ if (gimple_call_num_args (call) != 2)
return NULL_TREE;
- lhs = CALL_EXPR_ARG (call, 0);
+ lhs = gimple_call_arg (call, 0);
if (!POINTER_TYPE_P (TREE_TYPE (lhs))
|| TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
!= TYPE_MAIN_VARIANT (cfun_va_list))
return NULL_TREE;
- lhs = build_fold_indirect_ref (lhs);
- rhs = CALL_EXPR_ARG (call, 1);
+ lhs = build_fold_indirect_ref_loc (loc, lhs);
+ rhs = gimple_call_arg (call, 1);
if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
!= TYPE_MAIN_VARIANT (cfun_va_list))
return NULL_TREE;
- rhs = fold_convert (TREE_TYPE (lhs), rhs);
+ rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
case BUILT_IN_VA_END:
+ /* No effect, so the statement will be deleted. */
return integer_zero_node;
default:
gcc_unreachable ();
}
}
-\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;
- struct gimplify_ctx gctx;
-
- push_gimplify_context (&gctx);
- 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));
-
- /* 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;
-}
-
/* A simple pass that attempts to fold all builtin functions. This pass
is run after we've propagated as many constants as we can. */
bool cfg_changed = false;
basic_block bb;
unsigned int todoflags = 0;
-
+
FOR_EACH_BB (bb)
{
- block_stmt_iterator i;
- for (i = bsi_start (bb); !bsi_end_p (i); )
+ gimple_stmt_iterator i;
+ for (i = gsi_start_bb (bb); !gsi_end_p (i); )
{
- tree *stmtp = bsi_stmt_ptr (i);
- tree old_stmt = *stmtp;
- tree call = get_rhs (*stmtp);
+ gimple stmt, old_stmt;
tree callee, result;
enum built_in_function fcode;
- if (!call || TREE_CODE (call) != CALL_EXPR)
+ stmt = gsi_stmt (i);
+
+ if (gimple_code (stmt) != GIMPLE_CALL)
{
- bsi_next (&i);
+ gsi_next (&i);
continue;
}
- callee = get_callee_fndecl (call);
+ callee = gimple_call_fndecl (stmt);
if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
{
- bsi_next (&i);
+ gsi_next (&i);
continue;
}
fcode = DECL_FUNCTION_CODE (callee);
- result = ccp_fold_builtin (*stmtp, call);
+ result = gimple_fold_builtin (stmt);
if (result)
- gimple_remove_stmt_histograms (cfun, *stmtp);
+ gimple_remove_stmt_histograms (cfun, stmt);
if (!result)
switch (DECL_FUNCTION_CODE (callee))
/* Resolve __builtin_constant_p. If it hasn't been
folded to integer_one_node by now, it's fairly
certain that the value simply isn't constant. */
- result = integer_zero_node;
+ result = integer_zero_node;
break;
case BUILT_IN_STACK_RESTORE:
- result = optimize_stack_restore (bb, *stmtp, i);
+ result = optimize_stack_restore (i);
if (result)
break;
- bsi_next (&i);
+ gsi_next (&i);
continue;
case BUILT_IN_VA_START:
case BUILT_IN_VA_END:
case BUILT_IN_VA_COPY:
/* These shouldn't be folded before pass_stdarg. */
- result = optimize_stdarg_builtin (*stmtp);
+ result = optimize_stdarg_builtin (stmt);
if (result)
break;
/* FALLTHRU */
default:
- bsi_next (&i);
+ gsi_next (&i);
continue;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Simplified\n ");
- print_generic_stmt (dump_file, *stmtp, dump_flags);
+ print_gimple_stmt (dump_file, stmt, 0, dump_flags);
}
- push_stmt_changes (stmtp);
-
- if (!set_rhs (stmtp, result))
+ old_stmt = stmt;
+ if (!update_call_from_tree (&i, 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);
- todoflags |= TODO_rebuild_alias;
- }
+ gimplify_and_update_call_from_tree (&i, result);
+ todoflags |= TODO_update_address_taken;
}
- pop_stmt_changes (stmtp);
+ stmt = gsi_stmt (i);
+ update_stmt (stmt);
- if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp)
- && tree_purge_dead_eh_edges (bb))
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
+ && gimple_purge_dead_eh_edges (bb))
cfg_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "to\n ");
- print_generic_stmt (dump_file, *stmtp, dump_flags);
+ print_gimple_stmt (dump_file, stmt, 0, 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)
+ if (gimple_code (stmt) != GIMPLE_CALL)
{
- bsi_next (&i);
+ gsi_next (&i);
continue;
}
- callee = get_callee_fndecl (call);
+ callee = gimple_call_fndecl (stmt);
if (!callee
- || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
+ || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
|| DECL_FUNCTION_CODE (callee) == fcode)
- bsi_next (&i);
+ gsi_next (&i);
}
}
-
+
/* Delete unreachable blocks. */
if (cfg_changed)
todoflags |= TODO_cleanup_cfg;
-
+
return todoflags;
}
-struct gimple_opt_pass pass_fold_builtins =
+struct gimple_opt_pass pass_fold_builtins =
{
{
GIMPLE_PASS,
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
+ TV_NONE, /* tv_id */
PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */