#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "langhooks.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-inline.h"
#include "tree-flow.h"
#include "tree-gimple.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "timevar.h"
#include "expr.h"
#include "flags.h"
typedef enum
{
UNINITIALIZED = 0,
UNDEFINED,
CONSTANT,
VARYING
} latticevalue;
#define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T)
typedef struct
{
latticevalue lattice_val;
tree const_val;
} value;
static sbitmap executable_blocks;
static GTY(()) varray_type cfg_blocks = NULL;
static unsigned int cfg_blocks_num = 0;
static int cfg_blocks_tail;
static int cfg_blocks_head;
static sbitmap bb_in_list;
static value *value_vector;
static GTY(()) varray_type ssa_edges;
static void initialize (void);
static void finalize (void);
static void visit_phi_node (tree);
static tree ccp_fold (tree);
static value cp_lattice_meet (value, value);
static void visit_stmt (tree);
static void visit_cond_stmt (tree);
static void visit_assignment (tree);
static void add_var_to_ssa_edges_worklist (tree);
static void add_outgoing_control_edges (basic_block);
static void add_control_edge (edge);
static void def_to_varying (tree);
static void set_lattice_value (tree, value);
static void simulate_block (basic_block);
static void simulate_stmt (tree);
static void substitute_and_fold (void);
static value evaluate_stmt (tree);
static void dump_lattice_value (FILE *, const char *, value);
static bool replace_uses_in (tree, bool *);
static latticevalue likely_value (tree);
static tree get_rhs (tree);
static void set_rhs (tree *, tree);
static value *get_value (tree);
static value get_default_value (tree);
static tree ccp_fold_builtin (tree, tree);
static bool get_strlen (tree, tree *, bitmap);
static inline bool cfg_blocks_empty_p (void);
static void cfg_blocks_add (basic_block);
static basic_block cfg_blocks_get (void);
static bool need_imm_uses_for (tree var);
static void
tree_ssa_ccp (void)
{
initialize ();
while (!cfg_blocks_empty_p () || VARRAY_ACTIVE_SIZE (ssa_edges) > 0)
{
if (!cfg_blocks_empty_p ())
{
basic_block dest_block = cfg_blocks_get ();
simulate_block (dest_block);
}
while (VARRAY_ACTIVE_SIZE (ssa_edges) > 0)
{
tree stmt = VARRAY_TOP_TREE (ssa_edges);
stmt_ann_t ann = stmt_ann (stmt);
VARRAY_POP (ssa_edges);
if (ann->in_ccp_worklist)
{
ann->in_ccp_worklist = 0;
simulate_stmt (stmt);
}
}
}
substitute_and_fold ();
cleanup_tree_cfg ();
finalize ();
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_referenced_vars (dump_file);
fprintf (dump_file, "\n\n");
}
}
static bool
gate_ccp (void)
{
return flag_tree_ccp != 0;
}
struct tree_opt_pass pass_ccp =
{
"ccp",
gate_ccp,
tree_ssa_ccp,
NULL,
NULL,
0,
TV_TREE_CCP,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_rename_vars
| TODO_ggc_collect | TODO_verify_ssa
};
static value *
get_value (tree var)
{
value *val;
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
val = &value_vector[SSA_NAME_VERSION (var)];
if (val->lattice_val == UNINITIALIZED)
*val = get_default_value (var);
return val;
}
static void
simulate_block (basic_block block)
{
tree phi;
if (block == EXIT_BLOCK_PTR)
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nSimulating block %d\n", block->index);
for (phi = phi_nodes (block); phi; phi = TREE_CHAIN (phi))
visit_phi_node (phi);
if (!TEST_BIT (executable_blocks, block->index))
{
block_stmt_iterator j;
unsigned int normal_edge_count;
edge e, normal_edge;
SET_BIT (executable_blocks, block->index);
for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
visit_stmt (bsi_stmt (j));
normal_edge_count = 0;
normal_edge = NULL;
for (e = block->succ; e; e = e->succ_next)
{
if (e->flags & EDGE_ABNORMAL)
{
add_control_edge (e);
}
else
{
normal_edge_count++;
normal_edge = e;
}
}
if (normal_edge_count == 1)
add_control_edge (normal_edge);
}
}
static void
simulate_stmt (tree use_stmt)
{
basic_block use_bb = bb_for_stmt (use_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
print_generic_stmt (dump_file, use_stmt, dump_flags);
}
if (TREE_CODE (use_stmt) == PHI_NODE)
{
visit_phi_node (use_stmt);
}
else if (TEST_BIT (executable_blocks, use_bb->index))
{
visit_stmt (use_stmt);
}
}
static void
substitute_and_fold (void)
{
basic_block bb;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"\nSubstituing constants and folding statements\n\n");
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
int i;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
value *new_val;
tree *orig_p = &PHI_ARG_DEF (phi, i);
if (! SSA_VAR_P (*orig_p))
break;
new_val = get_value (*orig_p);
if (new_val->lattice_val == CONSTANT
&& may_propagate_copy (*orig_p, new_val->const_val))
*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))
{
bool changed = fold_stmt (bsi_stmt_ptr (i));
stmt = bsi_stmt(i);
modify_stmt (stmt);
if (replaced_address || changed)
mark_new_vars_to_rename (stmt, vars_to_rename);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " with ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
}
}
}
static void
visit_phi_node (tree phi)
{
bool short_circuit = 0;
value phi_val, *curr_val;
int i;
if (DONT_SIMULATE_AGAIN (phi))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
print_generic_expr (dump_file, phi, dump_flags);
}
curr_val = get_value (PHI_RESULT (phi));
switch (curr_val->lattice_val)
{
case VARYING:
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n Shortcircuit. Default of VARYING.");
short_circuit = 1;
break;
case CONSTANT:
phi_val = *curr_val;
break;
case UNDEFINED:
case UNINITIALIZED:
phi_val.lattice_val = UNDEFINED;
phi_val.const_val = NULL_TREE;
break;
default:
abort ();
}
if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
{
phi_val.lattice_val = VARYING;
phi_val.const_val = NULL;
}
else
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
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);
phi_val = cp_lattice_meet (phi_val, *rdef_val);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\t");
print_generic_expr (dump_file, rdef, dump_flags);
dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
fprintf (dump_file, "\n");
}
if (phi_val.lattice_val == VARYING)
break;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_lattice_value (dump_file, "\n PHI node value: ", phi_val);
fprintf (dump_file, "\n\n");
}
set_lattice_value (PHI_RESULT (phi), phi_val);
if (phi_val.lattice_val == VARYING)
DONT_SIMULATE_AGAIN (phi) = 1;
}
static value
cp_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 (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 void
visit_stmt (tree stmt)
{
size_t i;
stmt_ann_t ann;
def_optype defs;
vdef_optype vdefs;
if (DONT_SIMULATE_AGAIN (stmt))
return;
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);
if (ann->in_ccp_worklist)
ann->in_ccp_worklist = 0;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
visit_assignment (stmt);
else if (NUM_DEFS (defs = DEF_OPS (ann)) != 0)
{
DONT_SIMULATE_AGAIN (stmt) = 1;
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree def = DEF_OP (defs, i);
def_to_varying (def);
}
}
else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
visit_cond_stmt (stmt);
else
{
DONT_SIMULATE_AGAIN (stmt) = 1;
if (computed_goto_p (stmt))
add_outgoing_control_edges (bb_for_stmt (stmt));
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
def_to_varying (VDEF_RESULT (vdefs, i));
}
static void
visit_assignment (tree stmt)
{
value val;
tree lhs, rhs;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
{
val.lattice_val = VARYING;
val.const_val = NULL_TREE;
}
else if (TREE_CODE (rhs) == SSA_NAME)
{
value *nval = get_value (rhs);
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;
}
}
}
set_lattice_value (lhs, val);
if (val.lattice_val == VARYING)
DONT_SIMULATE_AGAIN (stmt) = 1;
}
static void
visit_cond_stmt (tree stmt)
{
edge e;
value val;
basic_block block;
block = bb_for_stmt (stmt);
val = evaluate_stmt (stmt);
e = find_taken_edge (block, val.const_val);
if (e)
add_control_edge (e);
else
{
DONT_SIMULATE_AGAIN (stmt) = 1;
add_outgoing_control_edges (block);
}
}
static void
add_outgoing_control_edges (basic_block bb)
{
edge e;
for (e = bb->succ; e; e = e->succ_next)
add_control_edge (e);
}
static void
add_control_edge (edge e)
{
basic_block bb = e->dest;
if (bb == EXIT_BLOCK_PTR)
return;
if (e->flags & EDGE_EXECUTABLE)
return;
e->flags |= EDGE_EXECUTABLE;
if (TEST_BIT (bb_in_list, bb->index))
return;
cfg_blocks_add (bb);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
e->src->index, e->dest->index);
}
static tree
ccp_fold (tree stmt)
{
tree rhs = get_rhs (stmt);
enum tree_code code = TREE_CODE (rhs);
int kind = TREE_CODE_CLASS (code);
tree retval = NULL_TREE;
if (TREE_CODE (rhs) == SSA_NAME)
return get_value (rhs)->const_val;
if (kind == '1')
{
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 == '2'
|| kind == '<'
|| 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);
for (i = 0; i < NUM_USES (uses); i++)
*(USE_OP_PTR (uses, i)) = orig[i];
free (orig);
}
}
else
return rhs;
if (retval)
{
if (TREE_TYPE (retval) != TREE_TYPE (rhs))
retval = convert (TREE_TYPE (rhs), retval);
if (TREE_TYPE (retval) == TREE_TYPE (rhs))
return 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.const_val = NULL_TREE;
}
return val;
}
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 CONSTANT:
fprintf (outf, "%sCONSTANT ", prefix);
print_generic_expr (outf, val.const_val, dump_flags);
break;
default:
abort ();
}
}
tree
widen_bitfield (tree val, tree field, tree var)
{
unsigned var_size, field_size;
tree wide_val;
unsigned HOST_WIDE_INT mask;
unsigned i;
var_size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE ((var))));
field_size = TREE_INT_CST_LOW (DECL_SIZE (field));
if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
return NULL;
#if defined ENABLE_CHECKING
if (var_size < field_size)
abort ();
#endif
if (TREE_CODE (val) != INTEGER_CST)
return NULL;
if ((TREE_INT_CST_LOW (val) & (1 << (field_size - 1))) == 0
|| DECL_UNSIGNED (field))
{
for (i = 0, mask = 0; i < field_size; i++)
mask |= 1 << i;
wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
build_int_2 (mask, 0));
}
else
{
for (i = 0, mask = 0; i < (var_size - field_size); i++)
mask |= 1 << (var_size - i - 1);
wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
build_int_2 (mask, 0));
}
return fold (wide_val);
}
static bool
need_imm_uses_for (tree var)
{
return get_value (var)->lattice_val != VARYING;
}
static void
initialize (void)
{
edge e;
basic_block bb;
sbitmap virtual_var;
VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges");
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
bb_in_list = sbitmap_alloc (last_basic_block);
sbitmap_zero (bb_in_list);
value_vector = (value *) xmalloc (highest_ssa_version * sizeof (value));
memset (value_vector, 0, highest_ssa_version * sizeof (value));
virtual_var = sbitmap_alloc (highest_ssa_version);
sbitmap_zero (virtual_var);
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
tree stmt;
stmt_ann_t ann;
def_optype defs;
vdef_optype vdefs;
size_t x;
int vary;
for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
{
vary = 0;
stmt = bsi_stmt (i);
get_stmt_operands (stmt);
ann = stmt_ann (stmt);
defs = DEF_OPS (ann);
for (x = 0; x < NUM_DEFS (defs); x++)
{
tree def = DEF_OP (defs, x);
if (get_value (def)->lattice_val == VARYING)
vary = 1;
}
DONT_SIMULATE_AGAIN (stmt) = vary;
vdefs = VDEF_OPS (ann);
for (x = 0; x < NUM_VDEFS (vdefs); x++)
{
tree res = VDEF_RESULT (vdefs, x);
get_value (res)->lattice_val = VARYING;
SET_BIT (virtual_var, SSA_NAME_VERSION (res));
}
}
for (e = bb->succ; e; e = e->succ_next)
e->flags &= ~EDGE_EXECUTABLE;
}
FOR_EACH_BB (bb)
{
tree phi, var;
int x;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
value *val;
val = get_value (PHI_RESULT (phi));
if (val->lattice_val != VARYING)
{
for (x = 0; x < PHI_NUM_ARGS (phi); x++)
{
var = PHI_ARG_DEF (phi, x);
if (TREE_CODE (var) == SSA_NAME)
{
if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var)))
{
val->lattice_val = VARYING;
SET_BIT (virtual_var,
SSA_NAME_VERSION (PHI_RESULT (phi)));
break;
}
}
}
}
DONT_SIMULATE_AGAIN (phi) = ((val->lattice_val == VARYING) ? 1 : 0);
}
}
sbitmap_free (virtual_var);
compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_immediate_uses (dump_file);
VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
if (e->dest != EXIT_BLOCK_PTR)
{
e->flags |= EDGE_EXECUTABLE;
cfg_blocks_add (e->dest);
}
}
}
static void
finalize (void)
{
ssa_edges = NULL;
cfg_blocks = NULL;
free (value_vector);
sbitmap_free (bb_in_list);
sbitmap_free (executable_blocks);
free_df ();
}
static inline bool
cfg_blocks_empty_p (void)
{
return (cfg_blocks_num == 0);
}
static void
cfg_blocks_add (basic_block bb)
{
if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
return;
if (TEST_BIT (bb_in_list, bb->index))
return;
if (cfg_blocks_empty_p ())
{
cfg_blocks_tail = cfg_blocks_head = 0;
cfg_blocks_num = 1;
}
else
{
cfg_blocks_num++;
if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
{
cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
cfg_blocks_head = 0;
VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
}
else
cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
}
VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
SET_BIT (bb_in_list, bb->index);
}
static basic_block
cfg_blocks_get (void)
{
basic_block bb;
bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
#ifdef ENABLE_CHECKING
if (cfg_blocks_empty_p () || !bb)
abort ();
#endif
cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
--cfg_blocks_num;
RESET_BIT (bb_in_list, bb->index);
return bb;
}
static void
add_var_to_ssa_edges_worklist (tree var)
{
tree stmt = SSA_NAME_DEF_STMT (var);
dataflow_t df = get_immediate_uses (stmt);
int num_uses = num_immediate_uses (df);
int i;
for (i = 0; i < num_uses; i++)
{
tree use = immediate_use (df, i);
if (!DONT_SIMULATE_AGAIN (use))
{
stmt_ann_t ann = stmt_ann (use);
if (ann->in_ccp_worklist == 0)
{
ann->in_ccp_worklist = 1;
VARRAY_PUSH_TREE (ssa_edges, use);
}
}
}
}
static void
def_to_varying (tree var)
{
value val;
val.lattice_val = VARYING;
val.const_val = NULL_TREE;
set_lattice_value (var, val);
}
static void
set_lattice_value (tree var, value val)
{
value *old = get_value (var);
#ifdef ENABLE_CHECKING
if (val.lattice_val == UNDEFINED)
{
if (old->lattice_val == CONSTANT)
abort ();
if (old->lattice_val == VARYING
&& get_default_value (var).lattice_val != VARYING)
abort ();
}
else if (val.lattice_val == CONSTANT)
{
if (old->lattice_val == VARYING
&& get_default_value (var).lattice_val != VARYING)
abort ();
}
#endif
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");
}
add_var_to_ssa_edges_worklist (var);
*old = val;
}
}
static bool
replace_uses_in (tree stmt, bool *replaced_addresses_p)
{
bool replaced = false;
use_optype uses;
size_t i;
if (replaced_addresses_p)
*replaced_addresses_p = false;
get_stmt_operands (stmt);
uses = STMT_USE_OPS (stmt);
for (i = 0; i < NUM_USES (uses); i++)
{
tree *use = USE_OP_PTR (uses, i);
value *val = get_value (*use);
if (val->lattice_val == CONSTANT)
{
*use = val->const_val;
replaced = true;
if (POINTER_TYPE_P (TREE_TYPE (*use)) && replaced_addresses_p)
*replaced_addresses_p = true;
}
}
return replaced;
}
static latticevalue
likely_value (tree stmt)
{
use_optype uses;
size_t i;
int found_constant = 0;
stmt_ann_t ann;
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);
uses = USE_OPS (ann);
for (i = 0; i < NUM_USES (uses); i++)
{
tree use = USE_OP (uses, i);
value *val = get_value (use);
if (val->lattice_val == UNDEFINED)
return UNDEFINED;
if (val->lattice_val == CONSTANT)
found_constant = 1;
}
return ((found_constant || !uses) ? CONSTANT : VARYING);
}
static tree
maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
{
unsigned HOST_WIDE_INT lquo, lrem;
HOST_WIDE_INT hquo, hrem;
tree elt_size, min_idx, idx;
tree array_type, elt_type;
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 (TREE_CODE (elt_size) != INTEGER_CST)
return NULL_TREE;
if (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_2_wide (lquo, hquo);
min_idx = TYPE_DOMAIN (TREE_TYPE (base));
if (min_idx)
{
min_idx = TYPE_MIN_VALUE (min_idx);
if (min_idx)
{
idx = convert (TREE_TYPE (min_idx), idx);
if (!integer_zerop (min_idx))
idx = int_const_binop (PLUS_EXPR, idx, min_idx, 1);
}
}
return build (ARRAY_REF, orig_type, base, idx);
}
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;
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;
if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST)
continue;
if (!DECL_FIELD_CONTEXT (f))
continue;
tail_array_field = NULL_TREE;
cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), 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);
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);
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);
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))
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)
{
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;
if ((current_file_decl && TREE_CHAIN (current_file_decl))
&& (DECL_FIELD_CONTEXT (TREE_OPERAND (expr, 1)) !=
TREE_TYPE (TREE_OPERAND (expr, 0))))
{
tree f;
tree orig_field = TREE_OPERAND (expr, 1);
tree orig_type = TREE_TYPE (orig_field);
for (f = TYPE_FIELDS (TREE_TYPE (TREE_OPERAND (expr, 0)));
f; f = TREE_CHAIN (f))
{
if (lang_hooks.types_compatible_p (TREE_TYPE (f), orig_type)
&& tree_int_cst_compare (DECL_FIELD_BIT_OFFSET (f),
DECL_FIELD_BIT_OFFSET (orig_field))
== 0
&& tree_int_cst_compare (DECL_FIELD_OFFSET (f),
DECL_FIELD_OFFSET (orig_field))
== 0)
{
TREE_OPERAND (expr, 1) = f;
break;
}
}
}
break;
default:
return NULL_TREE;
}
if (t)
{
*expr_p = t;
*changed_p = true;
}
return NULL_TREE;
}
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 = get_callee_fndecl (rhs);
if (callee && DECL_BUILT_IN (callee))
result = ccp_fold_builtin (stmt, rhs);
}
if (result == NULL_TREE)
result = fold (rhs);
STRIP_MAIN_TYPE_NOPS (result);
STRIP_USELESS_TYPE_CONVERSION (result);
if (result != rhs)
{
changed = true;
set_rhs (stmt_p, result);
}
return changed;
}
static tree
get_rhs (tree stmt)
{
enum tree_code code = TREE_CODE (stmt);
if (code == MODIFY_EXPR)
return TREE_OPERAND (stmt, 1);
if (code == COND_EXPR)
return COND_EXPR_COND (stmt);
else if (code == SWITCH_EXPR)
return SWITCH_COND (stmt);
else if (code == RETURN_EXPR)
{
if (!TREE_OPERAND (stmt, 0))
return NULL_TREE;
if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
return TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
return TREE_OPERAND (stmt, 0);
}
else if (code == GOTO_EXPR)
return GOTO_DESTINATION (stmt);
else if (code == LABEL_EXPR)
return LABEL_EXPR_LABEL (stmt);
else
return stmt;
}
static void
set_rhs (tree *stmt_p, tree expr)
{
tree stmt = *stmt_p;
enum tree_code code = TREE_CODE (stmt);
if (code == MODIFY_EXPR)
TREE_OPERAND (stmt, 1) = expr;
else if (code == COND_EXPR)
COND_EXPR_COND (stmt) = expr;
else if (code == SWITCH_EXPR)
SWITCH_COND (stmt) = expr;
else if (code == RETURN_EXPR)
{
if (TREE_OPERAND (stmt, 0)
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
TREE_OPERAND (TREE_OPERAND (stmt, 0), 1) = expr;
else
TREE_OPERAND (stmt, 0) = expr;
}
else if (code == GOTO_EXPR)
GOTO_DESTINATION (stmt) = expr;
else if (code == LABEL_EXPR)
LABEL_EXPR_LABEL (stmt) = expr;
else
{
stmt_ann_t ann = stmt_ann (stmt);
*stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
(*stmt_p)->common.ann = (tree_ann) ann;
if (TREE_SIDE_EFFECTS (expr))
{
def_optype defs;
vdef_optype vdefs;
size_t i;
defs = DEF_OPS (ann);
for (i = 0; i < NUM_DEFS (defs); i++)
{
tree var = DEF_OP (defs, i);
if (TREE_CODE (var) == SSA_NAME)
SSA_NAME_DEF_STMT (var) = *stmt_p;
}
vdefs = VDEF_OPS (ann);
for (i = 0; i < NUM_VDEFS (vdefs); i++)
{
tree var = VDEF_RESULT (vdefs, i);
if (TREE_CODE (var) == SSA_NAME)
SSA_NAME_DEF_STMT (var) = *stmt_p;
}
}
}
}
static value
get_default_value (tree var)
{
value val;
tree sym;
if (TREE_CODE (var) == SSA_NAME)
sym = SSA_NAME_VAR (var);
else
{
#ifdef ENABLE_CHECKING
if (!DECL_P (var))
abort ();
#endif
sym = var;
}
val.lattice_val = UNDEFINED;
val.const_val = NULL_TREE;
if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
{
val.lattice_val = VARYING;
}
else if (decl_function_context (sym) != current_function_decl
|| TREE_STATIC (sym))
{
val.lattice_val = VARYING;
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
{
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 tree
ccp_fold_builtin (tree stmt, tree fn)
{
tree result, strlen_val[2];
tree arglist = TREE_OPERAND (fn, 1), a;
tree callee = get_callee_fndecl (fn);
bitmap visited;
int strlen_arg, i;
if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
return NULL_TREE;
result = fold_builtin (fn);
if (result)
return result;
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);
switch (DECL_FUNCTION_CODE (callee))
{
case BUILT_IN_STRLEN:
if (strlen_val[0]
&& size_type_node)
{
tree new = convert (size_type_node, strlen_val[0]);
if (is_gimple_val (new)
|| (is_gimple_cast (new)
&& is_gimple_val (TREE_OPERAND (new, 0))))
return new;
else
return NULL_TREE;
}
return strlen_val[0];
case BUILT_IN_STRCPY:
if (strlen_val[1]
&& is_gimple_val (strlen_val[1]))
return simplify_builtin_strcpy (arglist, strlen_val[1]);
case BUILT_IN_STRNCPY:
if (strlen_val[1]
&& is_gimple_val (strlen_val[1]))
return simplify_builtin_strncpy (arglist, strlen_val[1]);
case BUILT_IN_FPUTS:
return simplify_builtin_fputs (arglist,
TREE_CODE (stmt) != MODIFY_EXPR, 0,
strlen_val[0]);
case BUILT_IN_FPUTS_UNLOCKED:
return simplify_builtin_fputs (arglist,
TREE_CODE (stmt) != MODIFY_EXPR, 1,
strlen_val[0]);
default:
abort ();
}
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 void
execute_fold_all_builtins (void)
{
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);
}
set_rhs (stmtp, result);
modify_stmt (*stmtp);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "to\n ");
print_generic_stmt (dump_file, *stmtp, dump_flags);
fprintf (dump_file, "\n");
}
}
}
}
struct tree_opt_pass pass_fold_builtins =
{
"fab",
NULL,
execute_fold_all_builtins,
NULL,
NULL,
0,
0,
PROP_cfg | PROP_ssa,
0,
0,
0,
TODO_dump_func | TODO_verify_ssa
};
#include "gt-tree-ssa-ccp.h"