#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "langhooks.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 "flags.h"
#include "bitmap.h"
#include "obstack.h"
#include "target.h"
#include "expr.h"
#include "params.h"
static unsigned int todoflags;
static bitmap sra_candidates;
static bitmap needs_copy_in;
static bitmap sra_type_decomp_cache;
static bitmap sra_type_inst_cache;
struct sra_elt
{
struct sra_elt *parent;
struct sra_elt *groups;
struct sra_elt *children;
struct sra_elt *sibling;
tree element;
tree type;
tree replacement;
unsigned int n_uses;
unsigned int n_copies;
bool is_scalar;
bool is_group;
bool cannot_scalarize;
bool use_block_copy;
bool all_no_warning;
bool visited;
};
#define IS_ELEMENT_FOR_GROUP(ELEMENT) (TREE_CODE (ELEMENT) == RANGE_EXPR)
#define FOR_EACH_ACTUAL_CHILD(CHILD, ELT) \
for ((CHILD) = (ELT)->is_group \
? next_child_for_group (NULL, (ELT)) \
: (ELT)->children; \
(CHILD); \
(CHILD) = (ELT)->is_group \
? next_child_for_group ((CHILD), (ELT)) \
: (CHILD)->sibling)
static struct sra_elt *
next_child_for_group (struct sra_elt *child, struct sra_elt *group)
{
gcc_assert (group->is_group);
if (child)
child = child->sibling;
else
child = group->parent->children;
while (child)
{
tree g_elt = group->element;
if (TREE_CODE (g_elt) == RANGE_EXPR)
{
if (!tree_int_cst_lt (child->element, TREE_OPERAND (g_elt, 0))
&& !tree_int_cst_lt (TREE_OPERAND (g_elt, 1), child->element))
break;
}
else
gcc_unreachable ();
child = child->sibling;
}
return child;
}
static htab_t sra_map;
static struct obstack sra_obstack;
static void dump_sra_elt_name (FILE *, struct sra_elt *);
extern void debug_sra_elt_name (struct sra_elt *);
static tree generate_element_ref (struct sra_elt *);
static bool
is_sra_candidate_decl (tree decl)
{
return DECL_P (decl) && bitmap_bit_p (sra_candidates, DECL_UID (decl));
}
static bool
is_sra_scalar_type (tree type)
{
enum tree_code code = TREE_CODE (type);
return (code == INTEGER_TYPE || code == REAL_TYPE || code == VECTOR_TYPE
|| code == ENUMERAL_TYPE || code == BOOLEAN_TYPE
|| code == POINTER_TYPE || code == OFFSET_TYPE
|| code == REFERENCE_TYPE);
}
bool
sra_type_can_be_decomposed_p (tree type)
{
unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
tree t;
if (bitmap_bit_p (sra_type_decomp_cache, cache+0))
return true;
if (bitmap_bit_p (sra_type_decomp_cache, cache+1))
return false;
if (TYPE_SIZE (type) == NULL || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
|| integer_zerop (TYPE_SIZE (type)))
goto fail;
switch (TREE_CODE (type))
{
case RECORD_TYPE:
{
bool saw_one_field = false;
for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
if (TREE_CODE (t) == FIELD_DECL)
{
if (DECL_BIT_FIELD (t)
&& (tree_low_cst (DECL_SIZE (t), 1)
!= TYPE_PRECISION (TREE_TYPE (t))))
goto fail;
saw_one_field = true;
}
if (!saw_one_field)
goto fail;
}
break;
case ARRAY_TYPE:
t = TYPE_DOMAIN (type);
if (t == NULL)
goto fail;
if (TYPE_MIN_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MIN_VALUE (t)))
goto fail;
if (TYPE_MAX_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MAX_VALUE (t)))
goto fail;
break;
case COMPLEX_TYPE:
break;
default:
goto fail;
}
bitmap_set_bit (sra_type_decomp_cache, cache+0);
return true;
fail:
bitmap_set_bit (sra_type_decomp_cache, cache+1);
return false;
}
static bool
decl_can_be_decomposed_p (tree var)
{
if (is_sra_scalar_type (TREE_TYPE (var)))
return false;
if (!is_gimple_non_addressable (var))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Cannot scalarize variable ");
print_generic_expr (dump_file, var, dump_flags);
fprintf (dump_file, " because it must live in memory\n");
}
return false;
}
if (TREE_THIS_VOLATILE (var))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Cannot scalarize variable ");
print_generic_expr (dump_file, var, dump_flags);
fprintf (dump_file, " because it is declared volatile\n");
}
return false;
}
if (!sra_type_can_be_decomposed_p (TREE_TYPE (var)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Cannot scalarize variable ");
print_generic_expr (dump_file, var, dump_flags);
fprintf (dump_file, " because its type cannot be decomposed\n");
}
return false;
}
return true;
}
static bool
type_can_instantiate_all_elements (tree type)
{
if (is_sra_scalar_type (type))
return true;
if (!sra_type_can_be_decomposed_p (type))
return false;
switch (TREE_CODE (type))
{
case RECORD_TYPE:
{
unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2;
tree f;
if (bitmap_bit_p (sra_type_inst_cache, cache+0))
return true;
if (bitmap_bit_p (sra_type_inst_cache, cache+1))
return false;
for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
if (TREE_CODE (f) == FIELD_DECL)
{
if (!type_can_instantiate_all_elements (TREE_TYPE (f)))
{
bitmap_set_bit (sra_type_inst_cache, cache+1);
return false;
}
}
bitmap_set_bit (sra_type_inst_cache, cache+0);
return true;
}
case ARRAY_TYPE:
return type_can_instantiate_all_elements (TREE_TYPE (type));
case COMPLEX_TYPE:
return true;
default:
gcc_unreachable ();
}
}
static bool
can_completely_scalarize_p (struct sra_elt *elt)
{
struct sra_elt *c;
if (elt->cannot_scalarize)
return false;
for (c = elt->children; c; c = c->sibling)
if (!can_completely_scalarize_p (c))
return false;
for (c = elt->groups; c; c = c->sibling)
if (!can_completely_scalarize_p (c))
return false;
return true;
}
static hashval_t
sra_hash_tree (tree t)
{
hashval_t h;
switch (TREE_CODE (t))
{
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
h = DECL_UID (t);
break;
case INTEGER_CST:
h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
break;
case RANGE_EXPR:
h = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
h = iterative_hash_expr (TREE_OPERAND (t, 1), h);
break;
case FIELD_DECL:
h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0);
h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h);
break;
default:
gcc_unreachable ();
}
return h;
}
static hashval_t
sra_elt_hash (const void *x)
{
const struct sra_elt *e = x;
const struct sra_elt *p;
hashval_t h;
h = sra_hash_tree (e->element);
for (p = e->parent; p ; p = p->parent)
h = (h * 65521) ^ sra_hash_tree (p->element);
return h;
}
static int
sra_elt_eq (const void *x, const void *y)
{
const struct sra_elt *a = x;
const struct sra_elt *b = y;
tree ae, be;
if (a->parent != b->parent)
return false;
ae = a->element;
be = b->element;
if (ae == be)
return true;
if (TREE_CODE (ae) != TREE_CODE (be))
return false;
switch (TREE_CODE (ae))
{
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
return false;
case INTEGER_CST:
return tree_int_cst_equal (ae, be);
case RANGE_EXPR:
return
tree_int_cst_equal (TREE_OPERAND (ae, 0), TREE_OPERAND (be, 0))
&& tree_int_cst_equal (TREE_OPERAND (ae, 1), TREE_OPERAND (be, 1));
case FIELD_DECL:
if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be))
return false;
return fields_compatible_p (ae, be);
default:
gcc_unreachable ();
}
}
static struct sra_elt *
lookup_element (struct sra_elt *parent, tree child, tree type,
enum insert_option insert)
{
struct sra_elt dummy;
struct sra_elt **slot;
struct sra_elt *elt;
if (parent)
dummy.parent = parent->is_group ? parent->parent : parent;
else
dummy.parent = NULL;
dummy.element = child;
slot = (struct sra_elt **) htab_find_slot (sra_map, &dummy, insert);
if (!slot && insert == NO_INSERT)
return NULL;
elt = *slot;
if (!elt && insert == INSERT)
{
*slot = elt = obstack_alloc (&sra_obstack, sizeof (*elt));
memset (elt, 0, sizeof (*elt));
elt->parent = parent;
elt->element = child;
elt->type = type;
elt->is_scalar = is_sra_scalar_type (type);
if (parent)
{
if (IS_ELEMENT_FOR_GROUP (elt->element))
{
elt->is_group = true;
elt->sibling = parent->groups;
parent->groups = elt;
}
else
{
elt->sibling = parent->children;
parent->children = elt;
}
}
if (TREE_CODE (child) == PARM_DECL)
{
elt->n_copies = 1;
bitmap_set_bit (needs_copy_in, DECL_UID (child));
}
}
return elt;
}
static struct sra_elt *
maybe_lookup_element_for_expr (tree expr)
{
struct sra_elt *elt;
tree child;
switch (TREE_CODE (expr))
{
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
if (is_sra_candidate_decl (expr))
return lookup_element (NULL, expr, TREE_TYPE (expr), INSERT);
return NULL;
case ARRAY_REF:
if (in_array_bounds_p (expr))
child = TREE_OPERAND (expr, 1);
else
return NULL;
break;
case ARRAY_RANGE_REF:
if (range_in_array_bounds_p (expr))
{
tree domain = TYPE_DOMAIN (TREE_TYPE (expr));
child = build2 (RANGE_EXPR, integer_type_node,
TYPE_MIN_VALUE (domain), TYPE_MAX_VALUE (domain));
}
else
return NULL;
break;
case COMPONENT_REF:
if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) != RECORD_TYPE)
return NULL;
child = TREE_OPERAND (expr, 1);
break;
case REALPART_EXPR:
child = integer_zero_node;
break;
case IMAGPART_EXPR:
child = integer_one_node;
break;
default:
return NULL;
}
elt = maybe_lookup_element_for_expr (TREE_OPERAND (expr, 0));
if (elt)
return lookup_element (elt, child, TREE_TYPE (expr), INSERT);
return NULL;
}
struct sra_walk_fns
{
void (*use) (struct sra_elt *elt, tree *expr_p,
block_stmt_iterator *bsi, bool is_output, bool use_all);
void (*copy) (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
block_stmt_iterator *bsi);
void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
void (*ldst) (struct sra_elt *elt, tree other,
block_stmt_iterator *bsi, bool is_output);
bool initial_scan;
};
#ifdef ENABLE_CHECKING
static tree
sra_find_candidate_decl (tree *tp, int *walk_subtrees,
void *data ATTRIBUTE_UNUSED)
{
tree t = *tp;
enum tree_code code = TREE_CODE (t);
if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
{
*walk_subtrees = 0;
if (is_sra_candidate_decl (t))
return t;
}
else if (TYPE_P (t))
*walk_subtrees = 0;
return NULL;
}
#endif
static void
sra_walk_expr (tree *expr_p, block_stmt_iterator *bsi, bool is_output,
const struct sra_walk_fns *fns)
{
tree expr = *expr_p;
tree inner = expr;
bool disable_scalarization = false;
bool use_all_p = false;
while (1)
switch (TREE_CODE (inner))
{
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
if (is_sra_candidate_decl (inner))
{
struct sra_elt *elt = maybe_lookup_element_for_expr (expr);
if (disable_scalarization)
elt->cannot_scalarize = true;
else
fns->use (elt, expr_p, bsi, is_output, use_all_p);
}
return;
case ARRAY_REF:
if (!in_array_bounds_p (inner))
{
disable_scalarization = true;
goto use_all;
}
if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
goto use_all;
inner = TREE_OPERAND (inner, 0);
break;
case ARRAY_RANGE_REF:
if (!range_in_array_bounds_p (inner))
{
disable_scalarization = true;
goto use_all;
}
if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3))
goto use_all;
inner = TREE_OPERAND (inner, 0);
break;
case COMPONENT_REF:
if (TREE_CODE (TREE_TYPE (TREE_OPERAND (inner, 0))) != RECORD_TYPE)
goto use_all;
if (TREE_OPERAND (inner, 2))
goto use_all;
inner = TREE_OPERAND (inner, 0);
break;
case REALPART_EXPR:
case IMAGPART_EXPR:
inner = TREE_OPERAND (inner, 0);
break;
case BIT_FIELD_REF:
goto use_all;
case VIEW_CONVERT_EXPR:
case NOP_EXPR:
goto use_all;
case WITH_SIZE_EXPR:
goto use_all;
use_all:
expr_p = &TREE_OPERAND (inner, 0);
inner = expr = *expr_p;
use_all_p = true;
break;
default:
#ifdef ENABLE_CHECKING
gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL));
#endif
return;
}
}
static void
sra_walk_tree_list (tree list, block_stmt_iterator *bsi, bool is_output,
const struct sra_walk_fns *fns)
{
tree op;
for (op = list; op ; op = TREE_CHAIN (op))
sra_walk_expr (&TREE_VALUE (op), bsi, is_output, fns);
}
static void
sra_walk_call_expr (tree expr, block_stmt_iterator *bsi,
const struct sra_walk_fns *fns)
{
sra_walk_tree_list (TREE_OPERAND (expr, 1), bsi, false, fns);
}
static void
sra_walk_asm_expr (tree expr, block_stmt_iterator *bsi,
const struct sra_walk_fns *fns)
{
sra_walk_tree_list (ASM_INPUTS (expr), bsi, false, fns);
sra_walk_tree_list (ASM_OUTPUTS (expr), bsi, true, fns);
}
static void
sra_walk_modify_expr (tree expr, block_stmt_iterator *bsi,
const struct sra_walk_fns *fns)
{
struct sra_elt *lhs_elt, *rhs_elt;
tree lhs, rhs;
lhs = TREE_OPERAND (expr, 0);
rhs = TREE_OPERAND (expr, 1);
lhs_elt = maybe_lookup_element_for_expr (lhs);
rhs_elt = maybe_lookup_element_for_expr (rhs);
if (lhs_elt && rhs_elt)
{
fns->copy (lhs_elt, rhs_elt, bsi);
return;
}
if (rhs_elt)
{
if (!rhs_elt->is_scalar && !TREE_SIDE_EFFECTS (lhs))
fns->ldst (rhs_elt, lhs, bsi, false);
else
fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, false, false);
}
else
{
tree call = get_call_expr_in (rhs);
if (call)
sra_walk_call_expr (call, bsi, fns);
else
sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns);
}
if (lhs_elt)
{
if (TREE_CODE (rhs) == COMPLEX_EXPR
|| TREE_CODE (rhs) == COMPLEX_CST
|| TREE_CODE (rhs) == CONSTRUCTOR)
fns->init (lhs_elt, rhs, bsi);
else if (TREE_CODE (rhs) == VAR_DECL
&& TREE_STATIC (rhs)
&& TREE_READONLY (rhs)
&& targetm.binds_local_p (rhs))
fns->init (lhs_elt, DECL_INITIAL (rhs), bsi);
else if (!lhs_elt->is_scalar
&& !TREE_SIDE_EFFECTS (rhs) && is_gimple_addressable (rhs))
fns->ldst (lhs_elt, rhs, bsi, true);
else
fns->use (lhs_elt, &TREE_OPERAND (expr, 0), bsi, true, false);
}
else
sra_walk_expr (&TREE_OPERAND (expr, 0), bsi, true, fns);
}
static void
sra_walk_function (const struct sra_walk_fns *fns)
{
basic_block bb;
block_stmt_iterator si, ni;
FOR_EACH_BB (bb)
for (si = bsi_start (bb); !bsi_end_p (si); si = ni)
{
tree stmt, t;
stmt_ann_t ann;
stmt = bsi_stmt (si);
ann = stmt_ann (stmt);
ni = si;
bsi_next (&ni);
if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE)))
continue;
switch (TREE_CODE (stmt))
{
case RETURN_EXPR:
t = TREE_OPERAND (stmt, 0);
if (TREE_CODE (t) == MODIFY_EXPR)
sra_walk_expr (&TREE_OPERAND (t, 1), &si, false, fns);
else
sra_walk_expr (&TREE_OPERAND (stmt, 0), &si, false, fns);
break;
case MODIFY_EXPR:
sra_walk_modify_expr (stmt, &si, fns);
break;
case CALL_EXPR:
sra_walk_call_expr (stmt, &si, fns);
break;
case ASM_EXPR:
sra_walk_asm_expr (stmt, &si, fns);
break;
default:
break;
}
}
}
static bool
find_candidates_for_sra (void)
{
bool any_set = false;
tree var;
referenced_var_iterator rvi;
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (decl_can_be_decomposed_p (var))
{
bitmap_set_bit (sra_candidates, DECL_UID (var));
any_set = true;
}
}
return any_set;
}
static void
scan_use (struct sra_elt *elt, tree *expr_p ATTRIBUTE_UNUSED,
block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
bool is_output ATTRIBUTE_UNUSED, bool use_all ATTRIBUTE_UNUSED)
{
elt->n_uses += 1;
}
static void
scan_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
{
lhs_elt->n_copies += 1;
rhs_elt->n_copies += 1;
}
static void
scan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED,
block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
{
lhs_elt->n_copies += 1;
}
static void
scan_ldst (struct sra_elt *elt, tree other ATTRIBUTE_UNUSED,
block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
bool is_output ATTRIBUTE_UNUSED)
{
elt->n_copies += 1;
}
static void
scan_dump (struct sra_elt *elt)
{
struct sra_elt *c;
dump_sra_elt_name (dump_file, elt);
fprintf (dump_file, ": n_uses=%u n_copies=%u\n", elt->n_uses, elt->n_copies);
for (c = elt->children; c ; c = c->sibling)
scan_dump (c);
for (c = elt->groups; c ; c = c->sibling)
scan_dump (c);
}
static void
scan_function (void)
{
static const struct sra_walk_fns fns = {
scan_use, scan_copy, scan_init, scan_ldst, true
};
bitmap_iterator bi;
sra_walk_function (&fns);
if (dump_file && (dump_flags & TDF_DETAILS))
{
unsigned i;
fputs ("\nScan results:\n", dump_file);
EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
{
tree var = referenced_var (i);
struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
if (elt)
scan_dump (elt);
}
fputc ('\n', dump_file);
}
}
static void
build_element_name_1 (struct sra_elt *elt)
{
tree t;
char buffer[32];
if (elt->parent)
{
build_element_name_1 (elt->parent);
obstack_1grow (&sra_obstack, '$');
if (TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
{
if (elt->element == integer_zero_node)
obstack_grow (&sra_obstack, "real", 4);
else
obstack_grow (&sra_obstack, "imag", 4);
return;
}
}
t = elt->element;
if (TREE_CODE (t) == INTEGER_CST)
{
sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (t));
obstack_grow (&sra_obstack, buffer, strlen (buffer));
}
else
{
tree name = DECL_NAME (t);
if (name)
obstack_grow (&sra_obstack, IDENTIFIER_POINTER (name),
IDENTIFIER_LENGTH (name));
else
{
sprintf (buffer, "D%u", DECL_UID (t));
obstack_grow (&sra_obstack, buffer, strlen (buffer));
}
}
}
static char *
build_element_name (struct sra_elt *elt)
{
build_element_name_1 (elt);
obstack_1grow (&sra_obstack, '\0');
return XOBFINISH (&sra_obstack, char *);
}
static void
instantiate_element (struct sra_elt *elt)
{
struct sra_elt *base_elt;
tree var, base;
for (base_elt = elt; base_elt->parent; base_elt = base_elt->parent)
continue;
base = base_elt->element;
elt->replacement = var = make_rename_temp (elt->type, "SR");
DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (base);
DECL_ARTIFICIAL (var) = 1;
if (TREE_THIS_VOLATILE (elt->type))
{
TREE_THIS_VOLATILE (var) = 1;
TREE_SIDE_EFFECTS (var) = 1;
}
if (DECL_NAME (base) && !DECL_IGNORED_P (base))
{
char *pretty_name = build_element_name (elt);
DECL_NAME (var) = get_identifier (pretty_name);
obstack_free (&sra_obstack, pretty_name);
SET_DECL_DEBUG_EXPR (var, generate_element_ref (elt));
DECL_DEBUG_EXPR_IS_FROM (var) = 1;
DECL_IGNORED_P (var) = 0;
TREE_NO_WARNING (var) = TREE_NO_WARNING (base);
}
else
{
DECL_IGNORED_P (var) = 1;
TREE_NO_WARNING (var) = 1;
}
if (dump_file)
{
fputs (" ", dump_file);
dump_sra_elt_name (dump_file, elt);
fputs (" -> ", dump_file);
print_generic_expr (dump_file, var, dump_flags);
fputc ('\n', dump_file);
}
}
static void
decide_instantiation_1 (struct sra_elt *elt, unsigned int parent_uses,
unsigned int parent_copies)
{
if (dump_file && !elt->parent)
{
fputs ("Initial instantiation for ", dump_file);
dump_sra_elt_name (dump_file, elt);
fputc ('\n', dump_file);
}
if (elt->cannot_scalarize)
return;
if (elt->is_scalar)
{
if (elt->n_uses + elt->n_copies + parent_copies > parent_uses)
instantiate_element (elt);
}
else
{
struct sra_elt *c, *group;
unsigned int this_uses = elt->n_uses + parent_uses;
unsigned int this_copies = elt->n_copies + parent_copies;
for (group = elt->groups; group ; group = group->sibling)
FOR_EACH_ACTUAL_CHILD (c, group)
{
c->n_uses += group->n_uses;
c->n_copies += group->n_copies;
}
for (c = elt->children; c ; c = c->sibling)
decide_instantiation_1 (c, this_uses, this_copies);
}
}
static unsigned int
sum_instantiated_sizes (struct sra_elt *elt, unsigned HOST_WIDE_INT *sizep)
{
if (elt->replacement)
{
*sizep += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt->type));
return 1;
}
else
{
struct sra_elt *c;
unsigned int count = 0;
for (c = elt->children; c ; c = c->sibling)
count += sum_instantiated_sizes (c, sizep);
return count;
}
}
static void instantiate_missing_elements (struct sra_elt *elt);
static void
instantiate_missing_elements_1 (struct sra_elt *elt, tree child, tree type)
{
struct sra_elt *sub = lookup_element (elt, child, type, INSERT);
if (sub->is_scalar)
{
if (sub->replacement == NULL)
instantiate_element (sub);
}
else
instantiate_missing_elements (sub);
}
static void
instantiate_missing_elements (struct sra_elt *elt)
{
tree type = elt->type;
switch (TREE_CODE (type))
{
case RECORD_TYPE:
{
tree f;
for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f))
if (TREE_CODE (f) == FIELD_DECL)
{
tree field_type = TREE_TYPE (f);
if (INTEGRAL_TYPE_P (field_type)
&& DECL_MODE (f) != TYPE_MODE (field_type))
field_type = TREE_TYPE (get_unwidened (build3 (COMPONENT_REF,
field_type,
elt->element,
f, NULL_TREE),
NULL_TREE));
instantiate_missing_elements_1 (elt, f, field_type);
}
break;
}
case ARRAY_TYPE:
{
tree i, max, subtype;
i = TYPE_MIN_VALUE (TYPE_DOMAIN (type));
max = TYPE_MAX_VALUE (TYPE_DOMAIN (type));
subtype = TREE_TYPE (type);
while (1)
{
instantiate_missing_elements_1 (elt, i, subtype);
if (tree_int_cst_equal (i, max))
break;
i = int_const_binop (PLUS_EXPR, i, integer_one_node, true);
}
break;
}
case COMPLEX_TYPE:
type = TREE_TYPE (type);
instantiate_missing_elements_1 (elt, integer_zero_node, type);
instantiate_missing_elements_1 (elt, integer_one_node, type);
break;
default:
gcc_unreachable ();
}
}
static bool
decide_block_copy (struct sra_elt *elt)
{
struct sra_elt *c;
bool any_inst;
gcc_assert (!elt->is_group);
if (elt->cannot_scalarize)
{
elt->use_block_copy = 1;
if (dump_file)
{
fputs ("Scalarization disabled for ", dump_file);
dump_sra_elt_name (dump_file, elt);
fputc ('\n', dump_file);
}
for (c = elt->children; c; c = c->sibling)
{
c->cannot_scalarize = 1;
decide_block_copy (c);
}
for (c = elt->groups; c; c = c->sibling)
{
c->cannot_scalarize = 1;
c->use_block_copy = 1;
}
return false;
}
if (elt->n_uses == 0 && elt->n_copies == 0)
;
else if (!elt->is_scalar)
{
tree size_tree = TYPE_SIZE_UNIT (elt->type);
bool use_block_copy = true;
if (TREE_CODE (elt->type) == COMPLEX_TYPE)
use_block_copy = false;
else if (host_integerp (size_tree, 1))
{
unsigned HOST_WIDE_INT full_size, inst_size = 0;
unsigned int max_size, max_count, inst_count, full_count;
max_size = SRA_MAX_STRUCTURE_SIZE
? SRA_MAX_STRUCTURE_SIZE
: MOVE_RATIO * UNITS_PER_WORD;
max_count = SRA_MAX_STRUCTURE_COUNT
? SRA_MAX_STRUCTURE_COUNT
: MOVE_RATIO;
full_size = tree_low_cst (size_tree, 1);
full_count = count_type_elements (elt->type, false);
inst_count = sum_instantiated_sizes (elt, &inst_size);
if (full_size <= max_size
&& (full_count - inst_count) <= max_count
&& elt->n_copies > elt->n_uses)
use_block_copy = false;
else if (inst_count * 100 >= full_count * SRA_FIELD_STRUCTURE_RATIO
&& inst_size * 100 >= full_size * SRA_FIELD_STRUCTURE_RATIO)
use_block_copy = false;
if (!use_block_copy
&& (!can_completely_scalarize_p (elt)
|| !type_can_instantiate_all_elements (elt->type)))
use_block_copy = true;
}
elt->use_block_copy = use_block_copy;
for (c = elt->groups; c; c = c->sibling)
c->use_block_copy = use_block_copy;
if (dump_file)
{
fprintf (dump_file, "Using %s for ",
use_block_copy ? "block-copy" : "element-copy");
dump_sra_elt_name (dump_file, elt);
fputc ('\n', dump_file);
}
if (!use_block_copy)
{
instantiate_missing_elements (elt);
return true;
}
}
any_inst = elt->replacement != NULL;
for (c = elt->children; c ; c = c->sibling)
any_inst |= decide_block_copy (c);
return any_inst;
}
static void
decide_instantiations (void)
{
unsigned int i;
bool cleared_any;
bitmap_head done_head;
bitmap_iterator bi;
bitmap_initialize (&done_head, &bitmap_default_obstack);
cleared_any = false;
EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi)
{
tree var = referenced_var (i);
struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
if (elt)
{
decide_instantiation_1 (elt, 0, 0);
if (!decide_block_copy (elt))
elt = NULL;
}
if (!elt)
{
bitmap_set_bit (&done_head, i);
cleared_any = true;
}
}
if (cleared_any)
{
bitmap_and_compl_into (sra_candidates, &done_head);
bitmap_and_compl_into (needs_copy_in, &done_head);
}
bitmap_clear (&done_head);
if (!bitmap_empty_p (sra_candidates))
todoflags |= TODO_update_smt_usage;
mark_set_for_renaming (sra_candidates);
if (dump_file)
fputc ('\n', dump_file);
}
static void
mark_all_v_defs_1 (tree stmt)
{
tree sym;
ssa_op_iter iter;
update_stmt_if_modified (stmt);
FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_ALL_VIRTUALS)
{
if (TREE_CODE (sym) == SSA_NAME)
sym = SSA_NAME_VAR (sym);
mark_sym_for_renaming (sym);
}
}
static void
mark_all_v_defs (tree list)
{
if (TREE_CODE (list) != STATEMENT_LIST)
mark_all_v_defs_1 (list);
else
{
tree_stmt_iterator i;
for (i = tsi_start (list); !tsi_end_p (i); tsi_next (&i))
mark_all_v_defs_1 (tsi_stmt (i));
}
}
static void
mark_no_warning (struct sra_elt *elt)
{
if (!elt->all_no_warning)
{
if (elt->replacement)
TREE_NO_WARNING (elt->replacement) = 1;
else
{
struct sra_elt *c;
FOR_EACH_ACTUAL_CHILD (c, elt)
mark_no_warning (c);
}
elt->all_no_warning = true;
}
}
static tree
generate_one_element_ref (struct sra_elt *elt, tree base)
{
switch (TREE_CODE (TREE_TYPE (base)))
{
case RECORD_TYPE:
{
tree field = elt->element;
if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base)))
field = find_compatible_field (TREE_TYPE (base), field);
return build3 (COMPONENT_REF, elt->type, base, field, NULL);
}
case ARRAY_TYPE:
todoflags |= TODO_update_smt_usage;
if (TREE_CODE (elt->element) == RANGE_EXPR)
return build4 (ARRAY_RANGE_REF, elt->type, base,
TREE_OPERAND (elt->element, 0), NULL, NULL);
else
return build4 (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
case COMPLEX_TYPE:
if (elt->element == integer_zero_node)
return build1 (REALPART_EXPR, elt->type, base);
else
return build1 (IMAGPART_EXPR, elt->type, base);
default:
gcc_unreachable ();
}
}
static tree
generate_element_ref (struct sra_elt *elt)
{
if (elt->parent)
return generate_one_element_ref (elt, generate_element_ref (elt->parent));
else
return elt->element;
}
static tree
sra_build_assignment (tree dst, tree src)
{
return build2 (MODIFY_EXPR, void_type_node, dst, src);
}
static void
generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
tree *list_p)
{
struct sra_elt *c;
tree t;
if (!copy_out && TREE_CODE (expr) == SSA_NAME
&& TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
{
tree r, i;
c = lookup_element (elt, integer_zero_node, NULL, NO_INSERT);
r = c->replacement;
c = lookup_element (elt, integer_one_node, NULL, NO_INSERT);
i = c->replacement;
t = build2 (COMPLEX_EXPR, elt->type, r, i);
t = sra_build_assignment (expr, t);
SSA_NAME_DEF_STMT (expr) = t;
append_to_statement_list (t, list_p);
}
else if (elt->replacement)
{
if (copy_out)
t = sra_build_assignment (elt->replacement, expr);
else
t = sra_build_assignment (expr, elt->replacement);
append_to_statement_list (t, list_p);
}
else
{
FOR_EACH_ACTUAL_CHILD (c, elt)
{
t = generate_one_element_ref (c, unshare_expr (expr));
generate_copy_inout (c, copy_out, t, list_p);
}
}
}
static void
generate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p)
{
struct sra_elt *dc, *sc;
FOR_EACH_ACTUAL_CHILD (dc, dst)
{
sc = lookup_element (src, dc->element, NULL, NO_INSERT);
gcc_assert (sc);
generate_element_copy (dc, sc, list_p);
}
if (dst->replacement)
{
tree t;
gcc_assert (src->replacement);
t = sra_build_assignment (dst->replacement, src->replacement);
append_to_statement_list (t, list_p);
}
}
static void
generate_element_zero (struct sra_elt *elt, tree *list_p)
{
struct sra_elt *c;
if (elt->visited)
{
elt->visited = false;
return;
}
FOR_EACH_ACTUAL_CHILD (c, elt)
generate_element_zero (c, list_p);
if (elt->replacement)
{
tree t;
gcc_assert (elt->is_scalar);
t = fold_convert (elt->type, integer_zero_node);
t = sra_build_assignment (elt->replacement, t);
append_to_statement_list (t, list_p);
}
}
static void
generate_one_element_init (tree var, tree init, tree *list_p)
{
tree stmt = sra_build_assignment (var, init);
gimplify_and_add (stmt, list_p);
}
static bool
generate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p)
{
bool result = true;
enum tree_code init_code;
struct sra_elt *sub;
tree t;
unsigned HOST_WIDE_INT idx;
tree value, purpose;
STRIP_USELESS_TYPE_CONVERSION (init);
init_code = TREE_CODE (init);
if (elt->is_scalar)
{
if (elt->replacement)
{
generate_one_element_init (elt->replacement, init, list_p);
elt->visited = true;
}
return result;
}
switch (init_code)
{
case COMPLEX_CST:
case COMPLEX_EXPR:
FOR_EACH_ACTUAL_CHILD (sub, elt)
{
if (sub->element == integer_zero_node)
t = (init_code == COMPLEX_EXPR
? TREE_OPERAND (init, 0) : TREE_REALPART (init));
else
t = (init_code == COMPLEX_EXPR
? TREE_OPERAND (init, 1) : TREE_IMAGPART (init));
result &= generate_element_init_1 (sub, t, list_p);
}
break;
case CONSTRUCTOR:
FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, purpose, value)
{
if (TREE_CODE (purpose) == RANGE_EXPR)
{
tree lower = TREE_OPERAND (purpose, 0);
tree upper = TREE_OPERAND (purpose, 1);
while (1)
{
sub = lookup_element (elt, lower, NULL, NO_INSERT);
if (sub != NULL)
result &= generate_element_init_1 (sub, value, list_p);
if (tree_int_cst_equal (lower, upper))
break;
lower = int_const_binop (PLUS_EXPR, lower,
integer_one_node, true);
}
}
else
{
sub = lookup_element (elt, purpose, NULL, NO_INSERT);
if (sub != NULL)
result &= generate_element_init_1 (sub, value, list_p);
}
}
break;
default:
elt->visited = true;
result = false;
}
return result;
}
static bool
generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
{
bool ret;
push_gimplify_context ();
ret = generate_element_init_1 (elt, init, list_p);
pop_gimplify_context (NULL);
if (ret && *list_p)
{
tree_stmt_iterator i;
for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i))
find_new_referenced_vars (tsi_stmt_ptr (i));
}
return ret;
}
void
insert_edge_copies (tree stmt, basic_block bb)
{
edge e;
edge_iterator ei;
bool first_copy;
first_copy = true;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (!(e->flags & EDGE_ABNORMAL))
{
if (first_copy)
{
bsi_insert_on_edge (e, stmt);
first_copy = false;
}
else
bsi_insert_on_edge (e, unsave_expr_now (stmt));
}
}
}
void
sra_insert_before (block_stmt_iterator *bsi, tree list)
{
tree stmt = bsi_stmt (*bsi);
if (EXPR_HAS_LOCATION (stmt))
annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
bsi_insert_before (bsi, list, BSI_SAME_STMT);
}
void
sra_insert_after (block_stmt_iterator *bsi, tree list)
{
tree stmt = bsi_stmt (*bsi);
if (EXPR_HAS_LOCATION (stmt))
annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
if (stmt_ends_bb_p (stmt))
insert_edge_copies (list, bsi->bb);
else
bsi_insert_after (bsi, list, BSI_SAME_STMT);
}
static void
sra_replace (block_stmt_iterator *bsi, tree list)
{
sra_insert_before (bsi, list);
bsi_remove (bsi, false);
if (bsi_end_p (*bsi))
*bsi = bsi_last (bsi->bb);
else
bsi_prev (bsi);
}
static void
scalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi,
bool is_output, bool use_all)
{
tree list = NULL, stmt = bsi_stmt (*bsi);
if (elt->replacement)
{
if (is_output)
mark_all_v_defs (stmt);
*expr_p = elt->replacement;
update_stmt (stmt);
}
else
{
generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
if (list == NULL)
return;
mark_all_v_defs (list);
if (is_output)
sra_insert_after (bsi, list);
else
{
sra_insert_before (bsi, list);
if (use_all)
mark_no_warning (elt);
}
}
}
static void
scalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt,
block_stmt_iterator *bsi)
{
tree list, stmt;
if (lhs_elt->replacement && rhs_elt->replacement)
{
stmt = bsi_stmt (*bsi);
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
TREE_OPERAND (stmt, 0) = lhs_elt->replacement;
TREE_OPERAND (stmt, 1) = rhs_elt->replacement;
update_stmt (stmt);
}
else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
{
list = NULL;
generate_copy_inout (rhs_elt, false,
generate_element_ref (rhs_elt), &list);
if (list)
{
mark_all_v_defs (list);
sra_insert_before (bsi, list);
}
list = NULL;
generate_copy_inout (lhs_elt, true,
generate_element_ref (lhs_elt), &list);
if (list)
{
mark_all_v_defs (list);
sra_insert_after (bsi, list);
}
}
else
{
stmt = bsi_stmt (*bsi);
mark_all_v_defs (stmt);
list = NULL;
generate_element_copy (lhs_elt, rhs_elt, &list);
gcc_assert (list);
mark_all_v_defs (list);
sra_replace (bsi, list);
}
}
static void
scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
{
bool result = true;
tree list = NULL;
if (rhs)
{
rhs = unshare_expr (rhs);
result = generate_element_init (lhs_elt, rhs, &list);
}
generate_element_zero (lhs_elt, &list);
if (!result)
{
tree list0 = NULL;
generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
&list0);
append_to_statement_list (list, &list0);
list = list0;
}
if (lhs_elt->use_block_copy || !result)
{
if (list)
{
mark_all_v_defs (list);
sra_insert_after (bsi, list);
}
}
else
{
gcc_assert (list);
mark_all_v_defs (bsi_stmt (*bsi));
mark_all_v_defs (list);
sra_replace (bsi, list);
}
}
static tree
mark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
{
tree t = *tp;
if (TREE_CODE (t) == INDIRECT_REF)
{
TREE_THIS_NOTRAP (t) = 1;
*walk_subtrees = 0;
}
else if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
return NULL;
}
static void
scalarize_ldst (struct sra_elt *elt, tree other,
block_stmt_iterator *bsi, bool is_output)
{
gcc_assert (!elt->replacement);
if (elt->use_block_copy)
{
scalarize_use (elt, NULL, bsi, is_output, false);
}
else
{
tree list = NULL, stmt = bsi_stmt (*bsi);
mark_all_v_defs (stmt);
generate_copy_inout (elt, is_output, other, &list);
mark_all_v_defs (list);
gcc_assert (list);
if (stmt_ends_bb_p (stmt))
{
tree_stmt_iterator tsi;
tree first;
tsi = tsi_start (list);
first = tsi_stmt (tsi);
tsi_delink (&tsi);
bsi_replace (bsi, first, true);
if (!tsi_end_p (tsi))
{
do
{
walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL);
tsi_next (&tsi);
}
while (!tsi_end_p (tsi));
insert_edge_copies (list, bsi->bb);
}
}
else
sra_replace (bsi, list);
}
}
static void
scalarize_parms (void)
{
tree list = NULL;
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi)
{
tree var = referenced_var (i);
struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
generate_copy_inout (elt, true, var, &list);
}
if (list)
{
insert_edge_copies (list, ENTRY_BLOCK_PTR);
mark_all_v_defs (list);
}
}
static void
scalarize_function (void)
{
static const struct sra_walk_fns fns = {
scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false
};
sra_walk_function (&fns);
scalarize_parms ();
bsi_commit_edge_inserts ();
}
static void
dump_sra_elt_name (FILE *f, struct sra_elt *elt)
{
if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE)
{
fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f);
dump_sra_elt_name (f, elt->parent);
}
else
{
if (elt->parent)
dump_sra_elt_name (f, elt->parent);
if (DECL_P (elt->element))
{
if (TREE_CODE (elt->element) == FIELD_DECL)
fputc ('.', f);
print_generic_expr (f, elt->element, dump_flags);
}
else if (TREE_CODE (elt->element) == RANGE_EXPR)
fprintf (f, "["HOST_WIDE_INT_PRINT_DEC".."HOST_WIDE_INT_PRINT_DEC"]",
TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 0)),
TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 1)));
else
fprintf (f, "[" HOST_WIDE_INT_PRINT_DEC "]",
TREE_INT_CST_LOW (elt->element));
}
}
void
debug_sra_elt_name (struct sra_elt *elt)
{
dump_sra_elt_name (stderr, elt);
fputc ('\n', stderr);
}
void
sra_init_cache (void)
{
if (sra_type_decomp_cache)
return;
sra_type_decomp_cache = BITMAP_ALLOC (NULL);
sra_type_inst_cache = BITMAP_ALLOC (NULL);
}
static unsigned int
tree_sra (void)
{
todoflags = 0;
gcc_obstack_init (&sra_obstack);
sra_candidates = BITMAP_ALLOC (NULL);
needs_copy_in = BITMAP_ALLOC (NULL);
sra_init_cache ();
sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, NULL);
if (find_candidates_for_sra ())
{
scan_function ();
decide_instantiations ();
scalarize_function ();
}
htab_delete (sra_map);
sra_map = NULL;
BITMAP_FREE (sra_candidates);
BITMAP_FREE (needs_copy_in);
BITMAP_FREE (sra_type_decomp_cache);
BITMAP_FREE (sra_type_inst_cache);
obstack_free (&sra_obstack, NULL);
return todoflags;
}
static bool
gate_sra (void)
{
return flag_tree_sra != 0;
}
struct tree_opt_pass pass_sra =
{
"sra",
gate_sra,
tree_sra,
NULL,
NULL,
0,
TV_TREE_SRA,
PROP_cfg | PROP_ssa | PROP_alias,
0,
PROP_smt_usage,
0,
TODO_dump_func
| TODO_update_ssa
| TODO_ggc_collect | TODO_verify_ssa,
0
};