#include "config.h"
#include "system.h"
#include "coretypes.h"
#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 "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
typedef enum
{
UNINITIALIZED = 0,
UNDEFINED,
UNKNOWN_VAL,
CONSTANT,
VARYING
} latticevalue;
typedef struct
{
latticevalue lattice_val;
tree const_val;
} value;
static value *value_vector;
static void
dump_lattice_value (FILE *outf, const char *prefix, value val)
{
switch (val.lattice_val)
{
case UNDEFINED:
fprintf (outf, "%sUNDEFINED", prefix);
break;
case VARYING:
fprintf (outf, "%sVARYING", prefix);
break;
case UNKNOWN_VAL:
fprintf (outf, "%sUNKNOWN_VAL", prefix);
break;
case CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
print_generic_expr (outf, val.const_val, dump_flags);
break;
default:
gcc_unreachable ();
}
}
static value
get_default_value (tree var)
{
value val;
tree sym;
if (TREE_CODE (var) == SSA_NAME)
sym = SSA_NAME_VAR (var);
else
{
gcc_assert (DECL_P (var));
sym = var;
}
val.lattice_val = UNDEFINED;
val.const_val = NULL_TREE;
if (TREE_CODE (var) == SSA_NAME
&& SSA_NAME_VALUE (var)
&& is_gimple_min_invariant (SSA_NAME_VALUE (var)))
{
val.lattice_val = CONSTANT;
val.const_val = SSA_NAME_VALUE (var);
}
else if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
{
val.lattice_val = VARYING;
}
else if (TREE_STATIC (sym))
{
if (TREE_READONLY (sym)
&& DECL_INITIAL (sym)
&& is_gimple_min_invariant (DECL_INITIAL (sym)))
{
val.lattice_val = CONSTANT;
val.const_val = DECL_INITIAL (sym);
}
else
{
val.const_val = NULL_TREE;
val.lattice_val = UNKNOWN_VAL;
}
}
else if (!is_gimple_reg (sym))
{
val.const_val = NULL_TREE;
val.lattice_val = UNKNOWN_VAL;
}
else
{
enum tree_code code;
tree stmt = SSA_NAME_DEF_STMT (var);
if (!IS_EMPTY_STMT (stmt))
{
code = TREE_CODE (stmt);
if (code != MODIFY_EXPR && code != PHI_NODE)
val.lattice_val = VARYING;
}
}
return val;
}
static value *
get_value (tree var)
{
value *val;
gcc_assert (TREE_CODE (var) == SSA_NAME);
val = &value_vector[SSA_NAME_VERSION (var)];
if (val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
return val;
}
static bool
set_lattice_value (tree var, value val)
{
value *old = get_value (var);
if (val.lattice_val == UNDEFINED)
{
gcc_assert (old->lattice_val != CONSTANT);
gcc_assert (old->lattice_val != UNKNOWN_VAL);
gcc_assert (old->lattice_val != VARYING
|| get_default_value (var).lattice_val == VARYING);
}
else if (val.lattice_val == CONSTANT)
gcc_assert (old->lattice_val != VARYING
|| get_default_value (var).lattice_val == VARYING);
if (old->lattice_val == CONSTANT
&& val.lattice_val == CONSTANT
&& !simple_cst_equal (old->const_val, val.const_val))
{
val.lattice_val = VARYING;
val.const_val = NULL_TREE;
}
if (old->lattice_val != val.lattice_val)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_lattice_value (dump_file, "Lattice value changed to ", val);
fprintf (dump_file, ". Adding definition to SSA edges.\n");
}
*old = val;
return true;
}
return false;
}
static void
def_to_varying (tree var)
{
value val;
val.lattice_val = VARYING;
val.const_val = NULL_TREE;
set_lattice_value (var, val);
}
static latticevalue
likely_value (tree stmt)
{
vuse_optype vuses;
int found_constant = 0;
stmt_ann_t ann;
tree use;
ssa_op_iter iter;
ann = stmt_ann (stmt);
if (ann->makes_aliased_loads || ann->has_volatile_ops)
return VARYING;
if (get_call_expr_in (stmt) != NULL_TREE)
return VARYING;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
value *val = get_value (use);
if (val->lattice_val == UNDEFINED)
return UNDEFINED;
if (val->lattice_val == CONSTANT)
found_constant = 1;
}
vuses = VUSE_OPS (ann);
if (NUM_VUSES (vuses))
{
tree vuse = VUSE_OP (vuses, 0);
value *val = get_value (vuse);
if (val->lattice_val == UNKNOWN_VAL)
return UNKNOWN_VAL;
gcc_assert (val->lattice_val != UNDEFINED);
if (val->lattice_val == CONSTANT)
found_constant = 1;
}
return ((found_constant || (!USE_OPS (ann) && !vuses)) ? CONSTANT : VARYING);
}
static bool
need_imm_uses_for (tree var)
{
return get_value (var)->lattice_val != VARYING;
}
static void
ccp_initialize (void)
{
basic_block bb;
sbitmap is_may_def;
value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
memset (value_vector, 0, num_ssa_names * sizeof (value));
is_may_def = sbitmap_alloc (num_ssa_names);
sbitmap_zero (is_may_def);
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
bool is_varying = false;
tree stmt = bsi_stmt (i);
ssa_op_iter iter;
tree def;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter,
(SSA_OP_DEF | SSA_OP_VMUSTDEF))
{
if (get_value (def)->lattice_val == VARYING)
is_varying = true;
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
{
get_value (def)->lattice_val = VARYING;
SET_BIT (is_may_def, SSA_NAME_VERSION (def));
}
if (TREE_CODE (stmt) != MODIFY_EXPR
&& TREE_CODE (stmt) != COND_EXPR
&& TREE_CODE (stmt) != SWITCH_EXPR)
is_varying = true;
DONT_SIMULATE_AGAIN (stmt) = is_varying;
}
}
FOR_EACH_BB (bb)
{
tree phi, var;
int x;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
value *val = get_value (PHI_RESULT (phi));
for (x = 0; x < PHI_NUM_ARGS (phi); x++)
{
var = PHI_ARG_DEF (phi, x);
if (TREE_CODE (var) == SSA_NAME)
{
if (TEST_BIT (is_may_def, SSA_NAME_VERSION (var)))
{
val->lattice_val = VARYING;
SET_BIT (is_may_def, SSA_NAME_VERSION (PHI_RESULT (phi)));
break;
}
}
}
DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING);
}
}
sbitmap_free (is_may_def);
compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, need_imm_uses_for);
}
static bool
replace_uses_in (tree stmt, bool *replaced_addresses_p)
{
bool replaced = false;
use_operand_p use;
ssa_op_iter iter;
if (replaced_addresses_p)
*replaced_addresses_p = false;
get_stmt_operands (stmt);
FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
tree tuse = USE_FROM_PTR (use);
value *val = get_value (tuse);
if (val->lattice_val != CONSTANT)
continue;
if (TREE_CODE (stmt) == ASM_EXPR
&& !may_propagate_copy_into_asm (tuse))
continue;
SET_USE (use, val->const_val);
replaced = true;
if (POINTER_TYPE_P (TREE_TYPE (tuse)) && replaced_addresses_p)
*replaced_addresses_p = true;
}
return replaced;
}
static bool
replace_vuse_in (tree stmt, bool *replaced_addresses_p)
{
bool replaced = false;
vuse_optype vuses;
use_operand_p vuse;
value *val;
if (replaced_addresses_p)
*replaced_addresses_p = false;
get_stmt_operands (stmt);
vuses = STMT_VUSE_OPS (stmt);
if (NUM_VUSES (vuses) != 1)
return false;
vuse = VUSE_OP_PTR (vuses, 0);
val = get_value (USE_FROM_PTR (vuse));
if (val->lattice_val == CONSTANT
&& TREE_CODE (stmt) == MODIFY_EXPR
&& DECL_P (TREE_OPERAND (stmt, 1))
&& TREE_OPERAND (stmt, 1) == SSA_NAME_VAR (USE_FROM_PTR (vuse)))
{
TREE_OPERAND (stmt, 1) = val->const_val;
replaced = true;
if (POINTER_TYPE_P (TREE_TYPE (USE_FROM_PTR (vuse)))
&& replaced_addresses_p)
*replaced_addresses_p = true;
}
return replaced;
}
static void
substitute_and_fold (void)
{
basic_block bb;
unsigned int i;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"\nSubstituing constants and folding statements\n\n");
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
value *new_val;
use_operand_p orig_p = PHI_ARG_DEF_PTR (phi, i);
tree orig = USE_FROM_PTR (orig_p);
if (! SSA_VAR_P (orig))
break;
new_val = get_value (orig);
if (new_val->lattice_val == CONSTANT
&& may_propagate_copy (orig, new_val->const_val))
SET_USE (orig_p, new_val->const_val);
}
}
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
bool replaced_address;
tree stmt = bsi_stmt (i);
if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
continue;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
print_generic_stmt (dump_file, stmt, TDF_SLIM);
}
if (replace_uses_in (stmt, &replaced_address)
|| replace_vuse_in (stmt, &replaced_address))
{
bool changed = fold_stmt (bsi_stmt_ptr (i));
stmt = bsi_stmt(i);
if (replaced_address || changed)
{
mark_new_vars_to_rename (stmt, vars_to_rename);
if (maybe_clean_eh_stmt (stmt))
tree_purge_dead_eh_edges (bb);
}
else
modify_stmt (stmt);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " with ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
}
}
for (i = 0; i < num_ssa_names; i++)
{
tree name = ssa_name (i);
value *value;
if (!name)
continue;
value = get_value (name);
if (value->lattice_val == CONSTANT
&& is_gimple_reg (name)
&& is_gimple_min_invariant (value->const_val))
SSA_NAME_VALUE (name) = value->const_val;
}
}
static void
ccp_finalize (void)
{
substitute_and_fold ();
free (value_vector);
}
static value
ccp_lattice_meet (value val1, value val2)
{
value result;
if (val1.lattice_val == UNDEFINED)
return val2;
else if (val2.lattice_val == UNDEFINED)
return val1;
if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
{
result.lattice_val = VARYING;
result.const_val = NULL_TREE;
return result;
}
if (val1.lattice_val == UNKNOWN_VAL
|| val2.lattice_val == UNKNOWN_VAL)
{
result.lattice_val = UNKNOWN_VAL;
result.const_val = NULL_TREE;
return result;
}
if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
{
result.lattice_val = CONSTANT;
result.const_val = val1.const_val;
}
else
{
result.lattice_val = VARYING;
result.const_val = NULL_TREE;
}
return result;
}
static enum ssa_prop_result
ccp_visit_phi_node (tree phi)
{
value new_val, *old_val;
int i;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
print_generic_expr (dump_file, phi, dump_flags);
}
old_val = get_value (PHI_RESULT (phi));
switch (old_val->lattice_val)
{
case VARYING:
return SSA_PROP_NOT_INTERESTING;
case CONSTANT:
new_val = *old_val;
break;
case UNKNOWN_VAL:
new_val.lattice_val = UNDEFINED;
new_val.const_val = NULL_TREE;
break;
case UNDEFINED:
case UNINITIALIZED:
new_val.lattice_val = UNDEFINED;
new_val.const_val = NULL_TREE;
break;
default:
gcc_unreachable ();
}
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
edge e = PHI_ARG_EDGE (phi, i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"\n Argument #%d (%d -> %d %sexecutable)\n",
i, e->src->index, e->dest->index,
(e->flags & EDGE_EXECUTABLE) ? "" : "not ");
}
if (e->flags & EDGE_EXECUTABLE)
{
tree rdef = PHI_ARG_DEF (phi, i);
value *rdef_val, val;
if (is_gimple_min_invariant (rdef))
{
val.lattice_val = CONSTANT;
val.const_val = rdef;
rdef_val = &val;
}
else
rdef_val = get_value (rdef);
new_val = ccp_lattice_meet (new_val, *rdef_val);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\t");
print_generic_expr (dump_file, rdef, dump_flags);
dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
fprintf (dump_file, "\n");
}
if (new_val.lattice_val == VARYING)
break;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
fprintf (dump_file, "\n\n");
}
if (old_val->lattice_val == UNKNOWN_VAL
&& new_val.lattice_val == UNDEFINED)
return SSA_PROP_NOT_INTERESTING;
if (set_lattice_value (PHI_RESULT (phi), new_val))
{
if (new_val.lattice_val == VARYING)
return SSA_PROP_VARYING;
else
return SSA_PROP_INTERESTING;
}
else
return SSA_PROP_NOT_INTERESTING;
}
static tree
ccp_fold (tree 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;
vuse_optype vuses;
vuses = STMT_VUSE_OPS (stmt);
if (TREE_CODE (rhs) == SSA_NAME)
return get_value (rhs)->const_val;
else if (DECL_P (rhs)
&& NUM_VUSES (vuses) == 1
&& rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
return get_value (VUSE_OP (vuses, 0))->const_val;
if (kind == tcc_unary)
{
tree op0 = TREE_OPERAND (rhs, 0);
if (TREE_CODE (op0) == SSA_NAME)
{
value *val = get_value (op0);
if (val->lattice_val == CONSTANT)
op0 = get_value (op0)->const_val;
}
retval = nondestructive_fold_unary_to_constant (code,
TREE_TYPE (rhs),
op0);
if (retval && ! is_gimple_min_invariant (retval))
return NULL;
if (! retval && is_gimple_min_invariant (op0))
return build1 (code, TREE_TYPE (rhs), op0);
}
else if (kind == tcc_binary
|| kind == tcc_comparison
|| code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR
|| code == TRUTH_XOR_EXPR)
{
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
if (TREE_CODE (op0) == SSA_NAME)
{
value *val = get_value (op0);
if (val->lattice_val == CONSTANT)
op0 = val->const_val;
}
if (TREE_CODE (op1) == SSA_NAME)
{
value *val = get_value (op1);
if (val->lattice_val == CONSTANT)
op1 = val->const_val;
}
retval = nondestructive_fold_binary_to_constant (code,
TREE_TYPE (rhs),
op0, op1);
if (retval && ! is_gimple_min_invariant (retval))
return NULL;
if (! retval
&& is_gimple_min_invariant (op0)
&& is_gimple_min_invariant (op1))
return build (code, TREE_TYPE (rhs), op0, op1);
}
else if (code == CALL_EXPR
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
&& (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
== FUNCTION_DECL)
&& DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
{
use_optype uses = STMT_USE_OPS (stmt);
if (NUM_USES (uses) != 0)
{
tree *orig;
size_t i;
orig = xmalloc (sizeof (tree) * NUM_USES (uses));
for (i = 0; i < NUM_USES (uses); i++)
orig[i] = USE_OP (uses, i);
replace_uses_in (stmt, NULL);
retval = fold_builtin (rhs, false);
for (i = 0; i < NUM_USES (uses); i++)
SET_USE_OP (uses, i, orig[i]);
free (orig);
}
}
else
return rhs;
if (retval)
return fold_convert (TREE_TYPE (rhs), retval);
return rhs;
}
static value
evaluate_stmt (tree stmt)
{
value val;
tree simplified;
latticevalue likelyvalue = likely_value (stmt);
if (likelyvalue == CONSTANT)
simplified = ccp_fold (stmt);
else if (likelyvalue == VARYING)
simplified = get_rhs (stmt);
else
simplified = NULL_TREE;
if (simplified && is_gimple_min_invariant (simplified))
{
val.lattice_val = CONSTANT;
val.const_val = simplified;
}
else
{
val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
val.lattice_val = (likelyvalue == UNKNOWN_VAL
? UNKNOWN_VAL : val.lattice_val);
val.const_val = NULL_TREE;
}
return val;
}
static enum ssa_prop_result
visit_assignment (tree stmt, tree *output_p)
{
value val;
tree lhs, rhs;
vuse_optype vuses;
v_must_def_optype v_must_defs;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
vuses = STMT_VUSE_OPS (stmt);
v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
gcc_assert (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0);
gcc_assert (NUM_V_MUST_DEFS (v_must_defs) == 1
|| TREE_CODE (lhs) == SSA_NAME);
if (TREE_CODE (lhs) != SSA_NAME)
{
lhs = V_MUST_DEF_RESULT (v_must_defs, 0);
}
if (TREE_CODE (rhs) == SSA_NAME)
{
value *nval = get_value (rhs);
val = *nval;
}
else if (DECL_P (rhs)
&& NUM_VUSES (vuses) == 1
&& rhs == SSA_NAME_VAR (VUSE_OP (vuses, 0)))
{
value *nval = get_value (VUSE_OP (vuses, 0));
val = *nval;
}
else
{
val = evaluate_stmt (stmt);
}
{
tree lhs = TREE_OPERAND (stmt, 0);
if (val.lattice_val == CONSTANT
&& TREE_CODE (lhs) == COMPONENT_REF
&& DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
{
tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
if (w && is_gimple_min_invariant (w))
val.const_val = w;
else
{
val.lattice_val = VARYING;
val.const_val = NULL;
}
}
}
if (!is_gimple_reg (SSA_NAME_VAR (lhs))
&& val.lattice_val == UNDEFINED)
val.lattice_val = UNKNOWN_VAL;
if (set_lattice_value (lhs, val))
{
*output_p = lhs;
if (val.lattice_val == VARYING)
return SSA_PROP_VARYING;
else
return SSA_PROP_INTERESTING;
}
else
return SSA_PROP_NOT_INTERESTING;
}
static enum ssa_prop_result
visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
value val;
basic_block block;
block = bb_for_stmt (stmt);
val = evaluate_stmt (stmt);
*taken_edge_p = find_taken_edge (block, val.const_val);
if (*taken_edge_p)
return SSA_PROP_INTERESTING;
else
return SSA_PROP_VARYING;
}
static enum ssa_prop_result
ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
stmt_ann_t ann;
v_may_def_optype v_may_defs;
v_must_def_optype v_must_defs;
tree def;
ssa_op_iter iter;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting statement: ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
ann = stmt_ann (stmt);
v_must_defs = V_MUST_DEF_OPS (ann);
v_may_defs = V_MAY_DEF_OPS (ann);
if (TREE_CODE (stmt) == MODIFY_EXPR
&& NUM_V_MAY_DEFS (v_may_defs) == 0
&& (NUM_V_MUST_DEFS (v_must_defs) == 1
|| TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
{
return visit_assignment (stmt, output_p);
}
else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
{
return visit_cond_stmt (stmt, taken_edge_p);
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
def_to_varying (def);
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
def_to_varying (def);
return SSA_PROP_VARYING;
}
static void
execute_ssa_ccp (void)
{
ccp_initialize ();
ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
ccp_finalize ();
}
static bool
gate_ccp (void)
{
return flag_tree_ccp != 0;
}
struct tree_opt_pass pass_ccp =
{
"ccp",
gate_ccp,
execute_ssa_ccp,
NULL,
NULL,
0,
TV_TREE_CCP,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_cleanup_cfg | TODO_dump_func | TODO_rename_vars
| TODO_ggc_collect | TODO_verify_ssa
| TODO_verify_stmts,
0
};
tree
widen_bitfield (tree val, tree field, tree var)
{
unsigned HOST_WIDE_INT var_size, field_size;
tree wide_val;
unsigned HOST_WIDE_INT mask;
unsigned int i;
if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1)
|| !host_integerp (DECL_SIZE (field), 1)
|| !host_integerp (val, 0))
return NULL_TREE;
var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1);
field_size = tree_low_cst (DECL_SIZE (field), 1);
if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
return NULL_TREE;
gcc_assert (var_size >= field_size);
if (DECL_UNSIGNED (field)
|| !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1))))
{
for (i = 0, mask = 0; i < field_size; i++)
mask |= ((HOST_WIDE_INT) 1) << i;
wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
fold_convert (TREE_TYPE (var),
build_int_cst (NULL_TREE, mask)));
}
else
{
for (i = 0, mask = 0; i < (var_size - field_size); i++)
mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1);
wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
fold_convert (TREE_TYPE (var),
build_int_cst (NULL_TREE, mask)));
}
return fold (wide_val);
}
static tree
maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
{
tree min_idx, idx, elt_offset = integer_zero_node;
tree array_type, elt_type, elt_size;
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);
}
array_type = TREE_TYPE (base);
if (TREE_CODE (array_type) != ARRAY_TYPE)
return NULL_TREE;
elt_type = TREE_TYPE (array_type);
if (!lang_hooks.types_compatible_p (orig_type, elt_type))
return NULL_TREE;
elt_size = TYPE_SIZE_UNIT (elt_type);
if (integer_zerop (offset))
{
if (TREE_CODE (elt_size) != INTEGER_CST)
elt_size = size_int (TYPE_ALIGN (elt_type));
idx = integer_zero_node;
}
else
{
unsigned HOST_WIDE_INT lquo, lrem;
HOST_WIDE_INT hquo, hrem;
if (TREE_CODE (elt_size) != INTEGER_CST
|| div_and_round_double (TRUNC_DIV_EXPR, 1,
TREE_INT_CST_LOW (offset),
TREE_INT_CST_HIGH (offset),
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 (NULL_TREE, lquo, hquo);
}
min_idx = integer_zero_node;
if (TYPE_DOMAIN (array_type))
{
if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)))
min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type));
else
min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx);
if (TREE_CODE (min_idx) != INTEGER_CST)
return NULL_TREE;
idx = fold_convert (TYPE_DOMAIN (array_type), idx);
elt_offset = fold_convert (TYPE_DOMAIN (array_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);
return build (ARRAY_REF, orig_type, base, idx, min_idx,
size_int (tree_low_cst (elt_size, 1)
/ (TYPE_ALIGN_UNIT (elt_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;
if (TREE_CODE (record_type) != RECORD_TYPE
&& TREE_CODE (record_type) != UNION_TYPE
&& TREE_CODE (record_type) != QUAL_UNION_TYPE)
return NULL_TREE;
if (lang_hooks.types_compatible_p (record_type, orig_type))
return NULL_TREE;
tail_array_field = NULL_TREE;
for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
{
int cmp;
if (TREE_CODE (f) != FIELD_DECL)
continue;
if (DECL_BIT_FIELD (f))
continue;
field_offset = byte_position (f);
if (TREE_CODE (field_offset) != INTEGER_CST)
continue;
if (!DECL_FIELD_CONTEXT (f))
continue;
tail_array_field = NULL_TREE;
cmp = tree_int_cst_compare (field_offset, offset);
if (cmp > 0)
continue;
field_type = TREE_TYPE (f);
if (cmp < 0)
{
if (!AGGREGATE_TYPE_P (field_type))
continue;
if (TREE_CODE (field_type) == ARRAY_TYPE)
tail_array_field = f;
if (!DECL_SIZE_UNIT (f)
|| TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
continue;
t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
continue;
offset = t;
}
else if (lang_hooks.types_compatible_p (orig_type, field_type))
{
if (base_is_ptr)
base = build1 (INDIRECT_REF, record_type, base);
t = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
return t;
}
else if (!AGGREGATE_TYPE_P (field_type))
return NULL_TREE;
goto found;
}
if (!tail_array_field)
return NULL_TREE;
f = tail_array_field;
field_type = TREE_TYPE (f);
found:
if (base_is_ptr)
base = build1 (INDIRECT_REF, record_type, base);
base = build (COMPONENT_REF, field_type, base, f, NULL_TREE);
t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
if (t)
return t;
return maybe_fold_offset_to_component_ref (field_type, base, offset,
orig_type, false);
}
static tree
maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
{
tree t;
base = fold (base);
STRIP_NOPS (base);
TREE_OPERAND (expr, 0) = base;
t = fold_read_from_constant_string (expr);
if (t)
return t;
if (TREE_CODE (base) == PLUS_EXPR)
{
tree offset2;
offset2 = TREE_OPERAND (base, 1);
if (TREE_CODE (offset2) != INTEGER_CST)
return NULL_TREE;
base = TREE_OPERAND (base, 0);
offset = int_const_binop (PLUS_EXPR, offset, offset2, 1);
}
if (TREE_CODE (base) == ADDR_EXPR)
{
base = TREE_OPERAND (base, 0);
if (TREE_CODE (base) == CONST_DECL
&& is_gimple_min_invariant (DECL_INITIAL (base)))
return DECL_INITIAL (base);
t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
if (t)
return t;
t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset,
TREE_TYPE (expr), false);
if (t)
return t;
if (integer_zerop (offset)
&& lang_hooks.types_compatible_p (TREE_TYPE (base),
TREE_TYPE (expr)))
return base;
}
else
{
t = base;
STRIP_NOPS (t);
if (TREE_CODE (t) == ADDR_EXPR
&& TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
{
return integer_zero_node;
}
if (POINTER_TYPE_P (TREE_TYPE (base)))
{
t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)),
base, offset,
TREE_TYPE (expr), true);
if (t)
return t;
}
}
return NULL_TREE;
}
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;
bool subtract = (TREE_CODE (expr) == MINUS_EXPR);
if (!POINTER_TYPE_P (ptr_type))
return NULL_TREE;
if (INTEGRAL_TYPE_P (TREE_TYPE (op0)))
{
if (subtract)
return NULL_TREE;
t = op0, op0 = op1, op1 = t;
}
if (TREE_CODE (op1) != INTEGER_CST)
return NULL_TREE;
if (TREE_CODE (op0) != ADDR_EXPR)
return NULL_TREE;
op0 = TREE_OPERAND (op0, 0);
while (TREE_CODE (op0) == ARRAY_REF)
{
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;
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 = convert (TREE_TYPE (min_idx), array_idx);
if (!integer_zerop (min_idx))
array_idx = int_const_binop (MINUS_EXPR, array_idx,
min_idx, 0);
}
}
array_idx = convert (sizetype, array_idx);
array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
if (subtract
&& TYPE_UNSIGNED (TREE_TYPE (op1))
&& tree_int_cst_lt (array_idx, op1))
return NULL;
op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR,
array_idx, op1, 0);
subtract = false;
op0 = array_obj;
}
if (subtract)
{
if (TYPE_UNSIGNED (TREE_TYPE (op1)))
return NULL;
op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
if (TREE_CODE (op1) != INTEGER_CST)
return NULL;
}
ptd_type = TREE_TYPE (ptr_type);
t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type);
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;
}
static tree
fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
{
bool *changed_p = data;
tree expr = *expr_p, t;
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);
break;
case ADDR_EXPR:
t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
if (t)
return t;
*walk_subtrees = 0;
if (*changed_p)
recompute_tree_invarant_for_addr_expr (expr);
return NULL_TREE;
case PLUS_EXPR:
case MINUS_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;
{
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;
default:
return NULL_TREE;
}
if (t)
{
*expr_p = t;
*changed_p = true;
}
return NULL_TREE;
}
static bool
get_strlen (tree arg, tree *length, bitmap visited)
{
tree var, def_stmt, val;
if (TREE_CODE (arg) != SSA_NAME)
{
val = c_strlen (arg, 1);
if (!val)
return false;
if (*length && simple_cst_equal (val, *length) != 1)
return false;
*length = val;
return true;
}
if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
return true;
bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
var = arg;
def_stmt = SSA_NAME_DEF_STMT (var);
switch (TREE_CODE (def_stmt))
{
case MODIFY_EXPR:
{
tree len, rhs;
rhs = TREE_OPERAND (def_stmt, 1);
STRIP_NOPS (rhs);
if (TREE_CODE (rhs) == SSA_NAME)
return get_strlen (rhs, length, visited);
len = c_strlen (rhs, 1);
if (len)
{
if (*length && simple_cst_equal (len, *length) != 1)
return false;
*length = len;
return true;
}
break;
}
case PHI_NODE:
{
int i;
for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
{
tree arg = PHI_ARG_DEF (def_stmt, i);
if (arg == PHI_RESULT (def_stmt))
continue;
if (!get_strlen (arg, length, visited))
return false;
}
return true;
}
default:
break;
}
return false;
}
static tree
ccp_fold_builtin (tree stmt, tree fn)
{
tree result, strlen_val[2];
tree callee, arglist, a;
int strlen_arg, i;
bitmap visited;
bool ignore;
ignore = TREE_CODE (stmt) != MODIFY_EXPR;
result = fold_builtin (fn, ignore);
if (result)
{
if (ignore)
STRIP_NOPS (result);
return result;
}
callee = get_callee_fndecl (fn);
if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
return NULL_TREE;
arglist = TREE_OPERAND (fn, 1);
if (!arglist)
return NULL_TREE;
switch (DECL_FUNCTION_CODE (callee))
{
case BUILT_IN_STRLEN:
case BUILT_IN_FPUTS:
case BUILT_IN_FPUTS_UNLOCKED:
strlen_arg = 1;
break;
case BUILT_IN_STRCPY:
case BUILT_IN_STRNCPY:
strlen_arg = 2;
break;
default:
return NULL_TREE;
}
visited = BITMAP_XMALLOC ();
memset (strlen_val, 0, sizeof (strlen_val));
for (i = 0, a = arglist;
strlen_arg;
i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
if (strlen_arg & 1)
{
bitmap_clear (visited);
if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
strlen_val[i] = NULL_TREE;
}
BITMAP_XFREE (visited);
result = NULL_TREE;
switch (DECL_FUNCTION_CODE (callee))
{
case BUILT_IN_STRLEN:
if (strlen_val[0])
{
tree new = fold_convert (TREE_TYPE (fn), strlen_val[0]);
if (is_gimple_val (new)
|| (is_gimple_cast (new)
&& is_gimple_val (TREE_OPERAND (new, 0))))
return new;
}
break;
case BUILT_IN_STRCPY:
if (strlen_val[1] && is_gimple_val (strlen_val[1]))
result = fold_builtin_strcpy (fn, strlen_val[1]);
break;
case BUILT_IN_STRNCPY:
if (strlen_val[1] && is_gimple_val (strlen_val[1]))
result = fold_builtin_strncpy (fn, strlen_val[1]);
break;
case BUILT_IN_FPUTS:
result = fold_builtin_fputs (arglist,
TREE_CODE (stmt) != MODIFY_EXPR, 0,
strlen_val[0]);
break;
case BUILT_IN_FPUTS_UNLOCKED:
result = fold_builtin_fputs (arglist,
TREE_CODE (stmt) != MODIFY_EXPR, 1,
strlen_val[0]);
break;
default:
gcc_unreachable ();
}
if (result && ignore)
result = fold_ignored_result (result);
return result;
}
bool
fold_stmt (tree *stmt_p)
{
tree rhs, result, stmt;
bool changed = false;
stmt = *stmt_p;
if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
{
*stmt_p
= build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
NULL);
return true;
}
rhs = get_rhs (stmt);
if (!rhs)
return changed;
result = NULL_TREE;
if (TREE_CODE (rhs) == CALL_EXPR)
{
tree callee;
callee = get_callee_fndecl (rhs);
if (callee && DECL_BUILT_IN (callee))
result = ccp_fold_builtin (stmt, rhs);
else
{
callee = TREE_OPERAND (rhs, 0);
if (TREE_CODE (callee) == OBJ_TYPE_REF
&& lang_hooks.fold_obj_type_ref
&& TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
&& DECL_P (TREE_OPERAND
(OBJ_TYPE_REF_OBJECT (callee), 0)))
{
tree t;
t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
t = lang_hooks.fold_obj_type_ref (callee, t);
if (t)
{
TREE_OPERAND (rhs, 0) = t;
changed = true;
}
}
}
}
if (result == NULL_TREE)
result = fold (rhs);
STRIP_USELESS_TYPE_CONVERSION (result);
if (result != rhs)
changed |= set_rhs (stmt_p, result);
return changed;
}
static tree
convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr)
{
tree_stmt_iterator ti;
tree stmt = bsi_stmt (*si_p);
tree tmp, stmts = NULL;
push_gimplify_context ();
tmp = get_initialized_tmp_var (expr, &stmts, NULL);
pop_gimplify_context (NULL);
for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti))
{
find_new_referenced_vars (tsi_stmt_ptr (ti));
mark_new_vars_to_rename (tsi_stmt (ti), vars_to_rename);
}
if (EXPR_HAS_LOCATION (stmt))
annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt));
bsi_insert_before (si_p, stmts, BSI_SAME_STMT);
return tmp;
}
static void
execute_fold_all_builtins (void)
{
bool cfg_changed = false;
basic_block bb;
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
tree *stmtp = bsi_stmt_ptr (i);
tree call = get_rhs (*stmtp);
tree callee, result;
if (!call || TREE_CODE (call) != CALL_EXPR)
continue;
callee = get_callee_fndecl (call);
if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
continue;
result = ccp_fold_builtin (*stmtp, call);
if (!result)
switch (DECL_FUNCTION_CODE (callee))
{
case BUILT_IN_CONSTANT_P:
result = integer_zero_node;
break;
default:
continue;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Simplified\n ");
print_generic_stmt (dump_file, *stmtp, dump_flags);
}
if (!set_rhs (stmtp, result))
{
result = convert_to_gimple_builtin (&i, result);
if (result && !set_rhs (stmtp, result))
abort ();
}
modify_stmt (*stmtp);
if (maybe_clean_eh_stmt (*stmtp)
&& tree_purge_dead_eh_edges (bb))
cfg_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "to\n ");
print_generic_stmt (dump_file, *stmtp, dump_flags);
fprintf (dump_file, "\n");
}
}
}
if (cfg_changed)
cleanup_tree_cfg ();
}
struct tree_opt_pass pass_fold_builtins =
{
"fab",
NULL,
execute_fold_all_builtins,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func
| TODO_verify_ssa
| TODO_rename_vars,
0
};