#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.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"
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 *children;
struct sra_elt *sibling;
tree element;
tree type;
tree replacement;
unsigned int n_uses;
unsigned int n_copies;
bool is_scalar;
bool cannot_scalarize;
bool use_block_copy;
bool visited;
};
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 bool
is_sra_candidate_decl (tree decl)
{
return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
}
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 == CHAR_TYPE || code == POINTER_TYPE || code == OFFSET_TYPE
|| code == REFERENCE_TYPE);
}
static bool
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 || 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 (!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 (!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;
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 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 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;
dummy.parent = parent;
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)
{
elt->sibling = parent->children;
parent->children = elt;
}
if (TREE_CODE (child) == PARM_DECL)
{
elt->n_copies = 1;
bitmap_set_bit (needs_copy_in, var_ann (child)->uid);
}
}
return elt;
}
static bool
is_valid_const_index (tree expr)
{
tree dom, t, index = TREE_OPERAND (expr, 1);
if (TREE_CODE (index) != INTEGER_CST)
return false;
dom = TYPE_DOMAIN (TREE_TYPE (TREE_OPERAND (expr, 0)));
if (dom == NULL)
return false;
t = TYPE_MIN_VALUE (dom);
if (!t || TREE_CODE (t) != INTEGER_CST)
return false;
if (tree_int_cst_lt (index, t))
return false;
t = TYPE_MAX_VALUE (dom);
if (!t || TREE_CODE (t) != INTEGER_CST)
return false;
if (tree_int_cst_lt (t, index))
return false;
return true;
}
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 (is_valid_const_index (expr))
child = TREE_OPERAND (expr, 1);
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);
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;
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);
}
return;
case ARRAY_REF:
if (!is_valid_const_index (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 ARRAY_RANGE_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;
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 (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 && is_gimple_addressable (rhs))
fns->ldst (lhs_elt, rhs, bsi, true);
else
fns->use (lhs_elt, &TREE_OPERAND (expr, 0), bsi, true);
}
else
{
sra_walk_expr (&TREE_OPERAND (expr, 0), bsi, true, fns);
}
if (rhs_elt)
{
if (!rhs_elt->is_scalar)
fns->ldst (rhs_elt, lhs, bsi, false);
else
fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, 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);
}
}
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 (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
&& NUM_VUSES (VUSE_OPS (ann)) == 0
&& NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
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)
{
size_t i;
bool any_set = false;
for (i = 0; i < num_referenced_vars; i++)
{
tree var = referenced_var (i);
if (decl_can_be_decomposed_p (var))
{
bitmap_set_bit (sra_candidates, var_ann (var)->uid);
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)
{
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);
}
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))
{
size_t 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 obstack_finish (&sra_obstack);
}
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);
TREE_NO_WARNING (var) = TREE_NO_WARNING (base);
DECL_ARTIFICIAL (var) = DECL_ARTIFICIAL (base);
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);
}
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;
unsigned int this_uses = elt->n_uses + parent_uses;
unsigned int this_copies = elt->n_copies + parent_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)
instantiate_missing_elements_1 (elt, f, TREE_TYPE (f));
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;
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);
}
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 (host_integerp (size_tree, 1))
{
unsigned HOST_WIDE_INT full_size, inst_size = 0;
unsigned int inst_count;
full_size = tree_low_cst (size_tree, 1);
if (full_size <= (unsigned) MOVE_RATIO * UNITS_PER_WORD
&& elt->n_copies > elt->n_uses)
use_block_copy = false;
else
{
inst_count = sum_instantiated_sizes (elt, &inst_size);
if (inst_size * 4 >= full_size * 3)
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;
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;
struct bitmap_head_def done_head;
bitmap_iterator bi;
bitmap_initialize (&done_head, 1);
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_operation (sra_candidates, sra_candidates, &done_head,
BITMAP_AND_COMPL);
bitmap_operation (needs_copy_in, needs_copy_in, &done_head,
BITMAP_AND_COMPL);
}
bitmap_clear (&done_head);
if (dump_file)
fputc ('\n', dump_file);
}
static void
mark_all_v_defs (tree stmt)
{
tree sym;
ssa_op_iter iter;
get_stmt_operands (stmt);
FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
if (TREE_CODE (sym) == SSA_NAME)
sym = SSA_NAME_VAR (sym);
bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
}
}
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 build (COMPONENT_REF, elt->type, base, field, NULL);
}
case ARRAY_TYPE:
return build (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
case COMPLEX_TYPE:
if (elt->element == integer_zero_node)
return build (REALPART_EXPR, elt->type, base);
else
return build (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 void
generate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr,
tree *list_p)
{
struct sra_elt *c;
tree t;
if (elt->replacement)
{
if (copy_out)
t = build (MODIFY_EXPR, void_type_node, elt->replacement, expr);
else
t = build (MODIFY_EXPR, void_type_node, expr, elt->replacement);
append_to_statement_list (t, list_p);
}
else
{
for (c = elt->children; c ; c = c->sibling)
{
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 (dc = dst->children; dc ; dc = dc->sibling)
{
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 = build (MODIFY_EXPR, void_type_node, 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 (c = elt->children; c ; c = c->sibling)
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 = build (MODIFY_EXPR, void_type_node, 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;
stmt = build (MODIFY_EXPR, void_type_node, var, init);
gimplify_stmt (&stmt);
if (TREE_CODE (stmt) == STATEMENT_LIST)
{
tree_stmt_iterator i;
for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
find_new_referenced_vars (tsi_stmt_ptr (i));
}
else
find_new_referenced_vars (&stmt);
append_to_statement_list (stmt, list_p);
}
static bool
generate_element_init (struct sra_elt *elt, tree init, tree *list_p)
{
bool result = true;
enum tree_code init_code;
struct sra_elt *sub;
tree t;
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 (sub = elt->children; sub ; sub = sub->sibling)
{
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 (sub, t, list_p);
}
break;
case CONSTRUCTOR:
for (t = CONSTRUCTOR_ELTS (init); t ; t = TREE_CHAIN (t))
{
sub = lookup_element (elt, TREE_PURPOSE (t), NULL, NO_INSERT);
if (sub == NULL)
continue;
result &= generate_element_init (sub, TREE_VALUE (t), list_p);
}
break;
default:
elt->visited = true;
result = false;
}
return result;
}
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));
}
}
}
static 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);
}
static 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);
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)
{
tree list = NULL, stmt = bsi_stmt (*bsi);
if (elt->replacement)
{
if (is_output)
mark_all_v_defs (stmt);
*expr_p = elt->replacement;
modify_stmt (stmt);
}
else
{
generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
if (list == NULL)
return;
mark_all_v_defs (expr_first (list));
if (is_output)
sra_insert_after (bsi, list);
else
sra_insert_before (bsi, list);
}
}
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;
modify_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 (expr_first (list));
sra_insert_before (bsi, list);
}
list = NULL;
generate_copy_inout (lhs_elt, true,
generate_element_ref (lhs_elt), &list);
if (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);
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)
{
push_gimplify_context ();
result = generate_element_init (lhs_elt, rhs, &list);
pop_gimplify_context (NULL);
}
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 (expr_first (list));
sra_insert_after (bsi, list);
}
}
else
{
gcc_assert (list);
mark_all_v_defs (bsi_stmt (*bsi));
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);
}
else
{
tree list = NULL, stmt = bsi_stmt (*bsi);
mark_all_v_defs (stmt);
generate_copy_inout (elt, is_output, other, &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;
size_t 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);
}
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 (NULL);
}
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
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);
}
static void
tree_sra (void)
{
gcc_obstack_init (&sra_obstack);
sra_candidates = BITMAP_XMALLOC ();
needs_copy_in = BITMAP_XMALLOC ();
sra_type_decomp_cache = BITMAP_XMALLOC ();
sra_type_inst_cache = BITMAP_XMALLOC ();
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_XFREE (sra_candidates);
BITMAP_XFREE (needs_copy_in);
BITMAP_XFREE (sra_type_decomp_cache);
BITMAP_XFREE (sra_type_inst_cache);
obstack_free (&sra_obstack, NULL);
}
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,
0,
0,
TODO_dump_func | TODO_rename_vars
| TODO_ggc_collect | TODO_verify_ssa,
0
};