diff options
| -rw-r--r-- | gcc/ipa-struct-reorg.c | 3932 | ||||
| -rw-r--r-- | gcc/ipa-struct-reorg.h | 113 |
2 files changed, 4045 insertions, 0 deletions
diff --git a/gcc/ipa-struct-reorg.c b/gcc/ipa-struct-reorg.c new file mode 100644 index 00000000000..9a04289f224 --- /dev/null +++ b/gcc/ipa-struct-reorg.c @@ -0,0 +1,3932 @@ +/* Struct-reorg optimization. + Copyright (C) 2007 Free Software Foundation, Inc. + Contributed by Olga Golovanevsky <olga@il.ibm.com> + (Initial version of this code was developed + by Caroline Tice and Mostafa Hagog.) + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "ggc.h" +#include "tree.h" +#include "rtl.h" +#include "tree-gimple.h" +#include "tree-inline.h" +#include "tree-flow.h" +#include "tree-flow-inline.h" +#include "langhooks.h" +#include "pointer-set.h" +#include "hashtab.h" +#include "c-tree.h" +#include "toplev.h" +#include "flags.h" +#include "debug.h" +#include "target.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "timevar.h" +#include "params.h" +#include "fibheap.h" +#include "intl.h" +#include "function.h" +#include "basic-block.h" +#include "tree-iterator.h" +#include "tree-pass.h" +#include "ipa-struct-reorg.h" +#include "opts.h" +#include "ipa-type-escape.h" +#include "tree-dump.h" +#include "c-common.h" + +/* This optimization implements structure peeling. + + For example, given a structure type: + typedef struct + { + int a; + float b; + int c; + }str_t; + + it can be peeled into two structure types as follows: + + typedef struct and typedef struct + { { + int a; float b; + int c; } str_t_1; + }str_t_0; + + or can be fully peeled: + + typedef struct + { + int a; + }str_t_0; + + typedef struct + { + float b; + }str_t_1; + + typedef struct + { + int c; + }str_t_2; + + When structure type is peeled all instances and their accesses + in the program are updated accordingly. For example, if there is + array of structures: + + str_t A[N]; + + and structure type str_t was peeled into two structures str_t_0 + and str_t_1 as it was shown above, then array A will be replaced + by two arrays as follows: + + str_t_0 A_0[N]; + str_t_1 A_1[N]; + + The field access of field a of element i of array A: A[i].a will be + replaced by an access to field a of element i of array A_0: A_0[i].a. + + This optimization also supports dynamically allocated arrays. + If array of structures was allocated by malloc function: + + str_t * p = (str_t *) malloc (sizeof (str_t) * N) + + the allocation site will be replaced to reflect new structure types: + + str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N) + str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N) + + The field access through the pointer p[i].a will be changed by p_0[i].a. + + The goal of structure peeling is to improve spatial locality. + For example, if one of the fields of a structure is accessed frequently + in the loop: + + for (i = 0; i < N; i++) + { + ... = A[i].a; + } + + the allocation of field a of str_t contiguously in memory will + increase the chances of fetching the field from cache. + + The analysis part of this optimization is based on the frequency of + field accesses, which are collected all over the program. + Then the fields with the frequencies that satisfy the following condition + get peeled out of the structure: + + freq(f) > C * max_field_freq_in_struct + + where max_field_freq_in_struct is the maximum field frequency + in the structure. C is a constant defining which portion of + max_field_freq_in_struct the fields should have in order to be peeled. + + If profiling information is provided, it is used to calculate the + frequency of field accesses. Otherwise, the structure is fully peeled. + + IPA type-escape analysis is used to determine when it is safe + to peel a structure. + + The optimization is activated by flag -fipa-struct-reorg. */ + +/* New variables created by this optimization. + When doing struct peeling, each variable of + the original struct type will be replaced by + the set of new variables corresponding to + the new structure types. */ +struct new_var_data { + /* VAR_DECL for original struct type. */ + tree orig_var; + /* Vector of new variables. */ + VEC(tree, heap) *new_vars; +}; + +typedef struct new_var_data *new_var; +typedef const struct new_var_data *const_new_var; + +/* This structure represents allocation site of the structure. */ +typedef struct alloc_site +{ + tree stmt; + d_str str; +} alloc_site_t; + +DEF_VEC_O (alloc_site_t); +DEF_VEC_ALLOC_O (alloc_site_t, heap); + +/* Allocation sites that belong to the same function. */ +struct func_alloc_sites +{ + tree func; + /* Vector of allocation sites for function. */ + VEC (alloc_site_t, heap) *allocs; +}; + +typedef struct func_alloc_sites *fallocs_t; +typedef const struct func_alloc_sites *const_fallocs_t; + +/* All allocation sites in the program. */ +htab_t alloc_sites; + +/* New global variables. Generated once for whole program. */ +htab_t new_global_vars; + +/* New local variables. Generated per-function. */ +htab_t new_local_vars; + +/* Vector of structures to be transformed. */ +typedef struct data_structure structure; +DEF_VEC_O (structure); +DEF_VEC_ALLOC_O (structure, heap); +VEC (structure, heap) *structures; + +/* Forward declarations. */ +static bool is_equal_types (tree, tree); + +/* Strip structure TYPE from pointers and arrays. */ + +static inline tree +strip_type (tree type) +{ + gcc_assert (TYPE_P (type)); + + while (POINTER_TYPE_P (type) + || TREE_CODE (type) == ARRAY_TYPE) + type = TREE_TYPE (type); + + return type; +} + +/* This function returns type of VAR. */ + +static inline tree +get_type_of_var (tree var) +{ + if (!var) + return NULL; + + if (TREE_CODE (var) == PARM_DECL) + return DECL_ARG_TYPE (var); + else + return TREE_TYPE (var); +} + +/* Set of actions we do for each newly generated STMT. */ + +static inline void +finalize_stmt (tree stmt) +{ + update_stmt (stmt); + mark_symbols_for_renaming (stmt); +} + +/* This function finalizes STMT and appends it to the list STMTS. */ + +static inline void +finalize_stmt_and_append (tree *stmts, tree stmt) +{ + append_to_statement_list (stmt, stmts); + finalize_stmt (stmt); +} + +/* Given structure type SRT_TYPE and field FIELD, + this function is looking for a field with the same name + and type as FIELD in STR_TYPE. It returns it if found, + or NULL_TREE otherwise. */ + +static tree +find_field_in_struct_1 (tree str_type, tree field) +{ + tree str_field; + + for (str_field = TYPE_FIELDS (str_type); str_field; + str_field = TREE_CHAIN (str_field)) + { + const char * str_field_name; + const char * field_name; + + str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field)); + field_name = IDENTIFIER_POINTER (DECL_NAME (field)); + + gcc_assert (str_field_name); + gcc_assert (field_name); + + if (!strcmp (str_field_name, field_name)) + { + /* Check field types. */ + if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field))) + return str_field; + } + } + + return NULL_TREE; +} + +/* Given a field declaration FIELD_DECL, this function + returns corresponding field entry in structure STR. */ + +static struct field_entry * +find_field_in_struct (d_str str, tree field_decl) +{ + int i; + + tree field = find_field_in_struct_1 (str->decl, field_decl); + + for (i = 0; i < str->num_fields; i++) + if (str->fields[i].decl == field) + return &(str->fields[i]); + + return NULL; +} + +/* This function checks whether ARG is a result of multiplication + of some number by STRUCT_SIZE. If yes, the function returns true + and this number is filled into NUM. */ + +static bool +is_result_of_mult (tree arg, tree *num, tree struct_size) +{ + tree size_def_stmt = SSA_NAME_DEF_STMT (arg); + + /* If allocation statementt was of the form + D.2229_10 = <alloc_func> (D.2228_9); + then size_def_stmt can be D.2228_9 = num.3_8 * 8; */ + + if (size_def_stmt && TREE_CODE (size_def_stmt) == GIMPLE_MODIFY_STMT) + { + tree lhs = GIMPLE_STMT_OPERAND (size_def_stmt, 0); + tree rhs = GIMPLE_STMT_OPERAND (size_def_stmt, 1); + + /* We expect temporary here. */ + if (!is_gimple_reg (lhs)) + return false; + + if (TREE_CODE (rhs) == MULT_EXPR) + { + tree arg0 = TREE_OPERAND (rhs, 0); + tree arg1 = TREE_OPERAND (rhs, 1); + + if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST)) + { + *num = arg1; + return true; + } + + if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST)) + { + *num = arg0; + return true; + } + } + } + + *num = NULL_TREE; + return false; +} + + +/* This function returns true if access ACC corresponds to the pattern + generated by compiler when an address of element i of an array + of structures STR_DECL (pointed by p) is calculated (p[i]). If this + pattern is recognized correctly, this function returns true + and fills missing fields in ACC. Otherwise it returns false. */ + +static bool +decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc) +{ + tree ref_var; + tree rhs, struct_size, op0, op1; + tree before_cast; + + ref_var = TREE_OPERAND (acc->ref, 0); + + if (TREE_CODE (ref_var) != SSA_NAME) + return false; + + acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var); + if (!(acc->ref_def_stmt) + || (TREE_CODE (acc->ref_def_stmt) != GIMPLE_MODIFY_STMT)) + return false; + + rhs = GIMPLE_STMT_OPERAND (acc->ref_def_stmt, 1); + + if (TREE_CODE (rhs) != PLUS_EXPR + && TREE_CODE (rhs)!= MINUS_EXPR + && TREE_CODE (rhs) != POINTER_PLUS_EXPR) + return false; + + op0 = TREE_OPERAND (rhs, 0); + op1 = TREE_OPERAND (rhs, 1); + + if (!is_array_access_through_pointer_and_index (TREE_CODE (rhs), op0, op1, + &acc->base, &acc->offset, + &acc->cast_stmt)) + return false; + + if (acc->cast_stmt) + before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE); + else + before_cast = acc->offset; + + if (!before_cast) + return false; + + + if (SSA_NAME_IS_DEFAULT_DEF (before_cast)) + return false; + + struct_size = TYPE_SIZE_UNIT (str_decl); + + if (!is_result_of_mult (before_cast, &acc->num, struct_size)) + return false; + + return true; +} + + +/* This function checks whether the access ACC of structure type STR + is of the form suitable for tranformation. If yes, it returns true. + False otherwise. */ + +static bool +decompose_access (tree str_decl, struct field_access_site *acc) +{ + gcc_assert (acc->ref); + + if (TREE_CODE (acc->ref) == INDIRECT_REF) + return decompose_indirect_ref_acc (str_decl, acc); + else if (TREE_CODE (acc->ref) == ARRAY_REF) + return true; + else if (TREE_CODE (acc->ref) == VAR_DECL) + return true; + + return false; +} + +/* This function creates empty field_access_site node. */ + +static inline struct field_access_site * +make_field_acc_node (void) +{ + int size = sizeof (struct field_access_site); + + return (struct field_access_site *) xcalloc (1, size); +} + +/* This function returns the structure field access, defined by STMT, + if it is aready in hashtable of function accesses F_ACCS. */ + +static struct field_access_site * +is_in_field_accs (tree stmt, htab_t f_accs) +{ + return (struct field_access_site *) + htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt)); +} + +/* This function adds an access ACC to the hashtable + F_ACCS of field accesses. */ + +static void +add_field_acc_to_acc_sites (struct field_access_site *acc, + htab_t f_accs) +{ + void **slot; + + gcc_assert (!is_in_field_accs (acc->stmt, f_accs)); + slot = htab_find_slot_with_hash (f_accs, acc->stmt, + htab_hash_pointer (acc->stmt), + INSERT); + *slot = acc; +} + +/* This function adds the VAR to vector of variables of + an access site defined by statement STMT. If access entry + with statement STMT does not exist in hashtable of + accesses ACCS, this function creates it. */ + +static void +add_access_to_acc_sites (tree stmt, tree var, htab_t accs) +{ + struct access_site *acc; + + acc = (struct access_site *) + htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt)); + + if (!acc) + { + void **slot; + + acc = (struct access_site *) xmalloc (sizeof (struct access_site)); + acc->stmt = stmt; + acc->vars = VEC_alloc (tree, heap, 10); + slot = htab_find_slot_with_hash (accs, stmt, + htab_hash_pointer (stmt), INSERT); + *slot = acc; + + } + VEC_safe_push (tree, heap, acc->vars, var); +} + +/* This function adds NEW_DECL to function + referenced vars, and marks it for renaming. */ + +static void +finalize_var_creation (tree new_decl) +{ + add_referenced_var (new_decl); + if (is_global_var (new_decl)) + mark_call_clobbered (new_decl, ESCAPE_UNKNOWN); + mark_sym_for_renaming (new_decl); +} + +/* This function finalizes VAR creation if it is a global VAR_DECL. */ + +static void +finalize_global_creation (tree var) +{ + if (TREE_CODE (var) == VAR_DECL + && is_global_var (var)) + finalize_var_creation (var); +} + +/* This function inserts NEW_DECL to varpool. */ + +static inline void +insert_global_to_varpool (tree new_decl) +{ + struct varpool_node *new_node; + + new_node = varpool_node (new_decl); + notice_global_symbol (new_decl); + varpool_mark_needed_node (new_node); + varpool_finalize_decl (new_decl); +} + +/* This function finalizes the creation of new variables, + defined by *SLOT->new_vars. */ + +static int +finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED) +{ + new_var n_var = *(new_var *) slot; + unsigned i; + tree var; + + for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++) + finalize_var_creation (var); + return 1; +} + +/* This funciton updates statements in STMT_LIST with BB info. */ + +static void +add_bb_info (basic_block bb, tree stmt_list) +{ + if (TREE_CODE (stmt_list) == STATEMENT_LIST) + { + tree_stmt_iterator tsi; + for (tsi = tsi_start (stmt_list); !tsi_end_p (tsi); tsi_next (&tsi)) + { + tree stmt = tsi_stmt (tsi); + + set_bb_for_stmt (stmt, bb); + } + } +} + +/* This function looks for the variable of NEW_TYPE type, stored in VAR. + It returns it, if found, and NULL_TREE otherwise. */ + +static tree +find_var_in_new_vars_vec (new_var var, tree new_type) +{ + tree n_var; + unsigned i; + + for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++) + { + tree type = strip_type(get_type_of_var (n_var)); + gcc_assert (type); + + if (type == new_type) + return n_var; + } + + return NULL_TREE; +} + +/* This function returns new_var node, the orig_var of which is DECL. + It looks for new_var's in NEW_VARS_HTAB. If not found, + the function returns NULL. */ + +static new_var +is_in_new_vars_htab (tree decl, htab_t new_vars_htab) +{ + return (new_var) htab_find_with_hash (new_vars_htab, decl, + htab_hash_pointer (decl)); +} + +/* Given original varaiable ORIG_VAR, this function returns + new variable corresponding to it of NEW_TYPE type. */ + +static tree +find_new_var_of_type (tree orig_var, tree new_type) +{ + new_var var; + gcc_assert (orig_var && new_type); + + if (TREE_CODE (orig_var) == SSA_NAME) + orig_var = SSA_NAME_VAR (orig_var); + + var = is_in_new_vars_htab (orig_var, new_global_vars); + if (!var) + var = is_in_new_vars_htab (orig_var, new_local_vars); + gcc_assert (var); + return find_var_in_new_vars_vec (var, new_type); +} + +/* This function generates stmt: + res = NUM * sizeof(TYPE) and returns it. + res is filled into RES. */ + +static tree +gen_size (tree num, tree type, tree *res) +{ + tree struct_size = TYPE_SIZE_UNIT (type); + HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size); + tree new_stmt; + + *res = create_tmp_var (TREE_TYPE (num), NULL); + + if (*res) + add_referenced_var (*res); + + if (exact_log2 (struct_size_int) == -1) + new_stmt = build_gimple_modify_stmt (num, struct_size); + else + { + tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int)); + + new_stmt = build_gimple_modify_stmt (*res, build2 (LSHIFT_EXPR, + TREE_TYPE (num), + num, C)); + } + + finalize_stmt (new_stmt); + return new_stmt; +} + +/* This function generates and returns a statement, that cast variable + BEFORE_CAST to NEW_TYPE. The cast result variable is stored + into RES_P. ORIG_CAST_STMT is the original cast statement. */ + +static tree +gen_cast_stmt (tree before_cast, tree new_type, tree orig_cast_stmt, + tree *res_p) +{ + tree lhs, new_lhs, new_stmt; + gcc_assert (TREE_CODE (orig_cast_stmt) == GIMPLE_MODIFY_STMT); + + lhs = GIMPLE_STMT_OPERAND (orig_cast_stmt, 0); + new_lhs = find_new_var_of_type (lhs, new_type); + gcc_assert (new_lhs); + + new_stmt = build_gimple_modify_stmt (new_lhs, + build1 (NOP_EXPR, + TREE_TYPE (new_lhs), + before_cast)); + finalize_stmt (new_stmt); + *res_p = new_lhs; + return new_stmt; +} + +/* This function builds an edge between BB and E->dest and updates + phi nodes of E->dest. It returns newly created edge. */ + +static edge +make_edge_and_fix_phis_of_dest (basic_block bb, edge e) +{ + edge new_e; + tree phi, arg; + + new_e = make_edge (bb, e->dest, e->flags); + + for (phi = phi_nodes (new_e->dest); phi; phi = PHI_CHAIN (phi)) + { + arg = PHI_ARG_DEF_FROM_EDGE (phi, e); + add_phi_arg (phi, arg, new_e); + } + + return new_e; +} + +/* This function inserts NEW_STMTS before STMT. */ + +static void +insert_before_stmt (tree stmt, tree new_stmts) +{ + block_stmt_iterator bsi; + + if (!stmt || !new_stmts) + return; + + bsi = bsi_for_stmt (stmt); + bsi_insert_before (&bsi, new_stmts, BSI_SAME_STMT); +} + +/* Insert NEW_STMTS after STMT. */ + +static void +insert_after_stmt (tree stmt, tree new_stmts) +{ + block_stmt_iterator bsi; + + if (!stmt || !new_stmts) + return; + + bsi = bsi_for_stmt (stmt); + bsi_insert_after (&bsi, new_stmts, BSI_SAME_STMT); +} + +/* This function returns vector of allocation sites + that appear in function FN_DECL. */ + +static fallocs_t +get_fallocs (tree fn_decl) +{ + return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl, + htab_hash_pointer (fn_decl)); +} + +/* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6); + and it is a part of allocation of a structure, + then it is usually followed by a cast stmt + p_8 = (struct str_t *) D.2225_7; + which is returned by this function. */ + +static tree +get_final_alloc_stmt (tree alloc_stmt) +{ + tree final_stmt; + use_operand_p use_p; + tree alloc_res; + + if (!alloc_stmt) + return NULL; + + if (TREE_CODE (alloc_stmt) != GIMPLE_MODIFY_STMT) + return NULL; + + alloc_res = GIMPLE_STMT_OPERAND (alloc_stmt, 0); + + if (TREE_CODE (alloc_res) != SSA_NAME) + return NULL; + + if (!single_imm_use (alloc_res, &use_p, &final_stmt)) + return NULL; + else + return final_stmt; +} + +/* This function returns true if STMT is one of allocation + sites of function FN_DECL. It returns false otherwise. */ + +static bool +is_part_of_malloc (tree stmt, tree fn_decl) +{ + fallocs_t fallocs = get_fallocs (fn_decl); + + if (fallocs) + { + alloc_site_t *call; + unsigned i; + + for (i = 0; + VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++) + if (call->stmt == stmt + || get_final_alloc_stmt (call->stmt) == stmt) + return true; + } + return false; +} + +/* Auxiliary structure for a lookup over field accesses. */ +struct find_stmt_data +{ + bool found; + tree stmt; +}; + +/* This function looks for DATA->stmt among + the statements involved in the field access, + defined by SLOT. It stops when it's found. */ + +static int +find_in_field_accs (void **slot, void *data) +{ + struct field_access_site *f_acc = + *(struct field_access_site **) slot; + tree stmt = ((struct find_stmt_data *)data)->stmt; + + if (f_acc->stmt == stmt + || f_acc->ref_def_stmt == stmt + || f_acc->cast_stmt == stmt) + { + ((struct find_stmt_data *)data)->found = true; + return 0; + } + else + return 1; +} + +/* This function checks whether STMT is part of field + accesses of structure STR. It returns true, if found, + and false otherwise. */ + +static bool +is_part_of_field_access (tree stmt, d_str str) +{ + int i; + + for (i = 0; i < str->num_fields; i++) + { + struct find_stmt_data data; + data.found = false; + data.stmt = stmt; + + if (str->fields[i].acc_sites) + htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data); + + if (data.found) + return true; + } + + return false; +} + +/* Auxiliary data for exclude_from_accs function. */ + +struct exclude_data +{ + tree fn_decl; + d_str str; +}; + +/* This function returns component_ref with the BASE and + field named FIELD_ID from structure TYPE. */ + +static inline tree +build_comp_ref (tree base, tree field_id, tree type) +{ + tree field; + bool found = false; + + + /* Find field of structure type with the same name as field_id. */ + for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) + { + if (DECL_NAME (field) == field_id) + { + found = true; + break; + } + } + + gcc_assert (found); + + return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE); +} + + +/* This struct represent data used for walk_tree + called from function find_pos_in_stmt. + - ref is a tree to be found, + - and pos is a pointer that points to ref in stmt. */ +struct ref_pos +{ + tree *pos; + tree ref; +}; + + +/* This is a callback function for walk_tree, called from + collect_accesses_in_bb function. DATA is a pointer to ref_pos structure. + When *TP is equal to DATA->ref, the walk_tree stops, + and found position, equal to TP, is assigned to DATA->pos. */ + +static tree +find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data) +{ + struct ref_pos * r_pos = (struct ref_pos *) data; + tree ref = r_pos->ref; + tree t = *tp; + + if (t == ref) + { + r_pos->pos = tp; + return t; + } + + switch (TREE_CODE (t)) + { + case GIMPLE_MODIFY_STMT: + { + tree lhs = GIMPLE_STMT_OPERAND (t, 0); + tree rhs = GIMPLE_STMT_OPERAND (t, 1); + *walk_subtrees = 1; + walk_tree (&lhs, find_pos_in_stmt_1, data, NULL); + walk_tree (&rhs, find_pos_in_stmt_1, data, NULL); + *walk_subtrees = 0; + } + break; + + default: + *walk_subtrees = 1; + } + return NULL_TREE; +} + + +/* This function looks for the pointer of REF in STMT, + It returns it, if found, and NULL otherwise. */ + +static tree * +find_pos_in_stmt (tree stmt, tree ref) +{ + struct ref_pos r_pos; + + r_pos.ref = ref; + r_pos.pos = NULL; + walk_tree (&stmt, find_pos_in_stmt_1, &r_pos, NULL); + + return r_pos.pos; +} + +/* This structure is used to represent array + or pointer-to wrappers of structure type. + For example, if type1 is structure type, + then for type1 ** we generate two type_wrapper + structures with wrap = 0 each one. + It's used to unwind the original type up to + structure type, replace it with the new structure type + and wrap it back in the opposite order. */ + +typedef struct type_wrapper +{ + /* 0 stand for pointer wrapper, and 1 for array wrapper. */ + bool wrap; + + /* Relevant for arrays as domain or index. */ + tree domain; +}type_wrapper_t; + +DEF_VEC_O (type_wrapper_t); +DEF_VEC_ALLOC_O (type_wrapper_t, heap); + +/* This function replace field access ACC by the new + field access of structure type NEW_TYPE. */ + +static void +replace_field_acc (struct field_access_site *acc, tree new_type) +{ + tree ref_var = acc->ref; + tree new_ref; + tree lhs, rhs; + tree *pos; + tree new_acc; + tree field_id = DECL_NAME (acc->field_decl); + VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10); + type_wrapper_t wr; + type_wrapper_t *wr_p = NULL; + + while (TREE_CODE (ref_var) == INDIRECT_REF + || TREE_CODE (ref_var) == ARRAY_REF) + { + if ( TREE_CODE (ref_var) == INDIRECT_REF) + { + wr.wrap = 0; + wr.domain = 0; + } + else if (TREE_CODE (ref_var) == ARRAY_REF) + { + wr.wrap = 1; + wr.domain = TREE_OPERAND (ref_var, 1); + } + + VEC_safe_push (type_wrapper_t, heap, wrapper, &wr); + ref_var = TREE_OPERAND (ref_var, 0); + } + + new_ref = find_new_var_of_type (ref_var, new_type); + finalize_global_creation (new_ref); + + while (VEC_length (type_wrapper_t, wrapper) != 0) + { + tree type = TREE_TYPE (TREE_TYPE (new_ref)); + + wr_p = VEC_last (type_wrapper_t, wrapper); + if (wr_p->wrap) /* Array. */ + new_ref = build4 (ARRAY_REF, type, new_ref, + wr_p->domain, NULL_TREE, NULL_TREE); + else /* Pointer. */ + new_ref = build1 (INDIRECT_REF, type, new_ref); + VEC_pop (type_wrapper_t, wrapper); + } + + new_acc = build_comp_ref (new_ref, field_id, new_type); + VEC_free (type_wrapper_t, heap, wrapper); + + if (TREE_CODE (acc->stmt) == GIMPLE_MODIFY_STMT) + { + lhs = GIMPLE_STMT_OPERAND (acc->stmt, 0); + rhs = GIMPLE_STMT_OPERAND (acc->stmt, 1); + + + if (lhs == acc->comp_ref) + GIMPLE_STMT_OPERAND (acc->stmt, 0) = new_acc; + else if (rhs == acc->comp_ref) + GIMPLE_STMT_OPERAND (acc->stmt, 1) = new_acc; + else + { + pos = find_pos_in_stmt (acc->stmt, acc->comp_ref); + gcc_assert (pos); + *pos = new_acc; + } + } + else + { + pos = find_pos_in_stmt (acc->stmt, acc->comp_ref); + gcc_assert (pos); + *pos = new_acc; + } + + finalize_stmt (acc->stmt); +} + +/* This function replace field access ACC by a new field access + of structure type NEW_TYPE. */ + +static void +replace_field_access_stmt (struct field_access_site *acc, tree new_type) +{ + + if (TREE_CODE (acc->ref) == INDIRECT_REF + ||TREE_CODE (acc->ref) == ARRAY_REF + ||TREE_CODE (acc->ref) == VAR_DECL) + replace_field_acc (acc, new_type); + else + gcc_unreachable (); +} + +/* This function looks for d_str, represented by TYPE, in the structures + vector. If found, it returns an index of found structure. Otherwise + it returns a length of the structures vector. */ + +static unsigned +find_structure (tree type) +{ + d_str str; + unsigned i; + + type = TYPE_MAIN_VARIANT (type); + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + if (is_equal_types (str->decl, type)) + return i; + + return VEC_length (structure, structures); +} + +/* In this function we create new statements that have the same + form as ORIG_STMT, but of type NEW_TYPE. The statements + treated by this function are simple assignments, + like assignments: p.8_7 = p; or statements with rhs of + tree codes PLUS_EXPR and MINUS_EXPR. */ + +static tree +create_base_plus_offset (tree orig_stmt, tree new_type, + tree offset) +{ + tree lhs, rhs; + tree new_lhs, new_rhs; + tree new_stmt; + + gcc_assert (TREE_CODE (orig_stmt) == GIMPLE_MODIFY_STMT); + + lhs = GIMPLE_STMT_OPERAND (orig_stmt, 0); + rhs = GIMPLE_STMT_OPERAND (orig_stmt, 1); + + gcc_assert (TREE_CODE (lhs) == VAR_DECL + || TREE_CODE (lhs) == SSA_NAME); + + new_lhs = find_new_var_of_type (lhs, new_type); + gcc_assert (new_lhs); + finalize_var_creation (new_lhs); + + switch (TREE_CODE (rhs)) + { + case PLUS_EXPR: + case MINUS_EXPR: + case POINTER_PLUS_EXPR: + { + tree op0 = TREE_OPERAND (rhs, 0); + tree op1 = TREE_OPERAND (rhs, 1); + tree new_op0 = NULL_TREE, new_op1 = NULL_TREE; + unsigned str0, str1; + unsigned length = VEC_length (structure, structures); + + + str0 = find_structure (strip_type (get_type_of_var (op0))); + str1 = find_structure (strip_type (get_type_of_var (op1))); + gcc_assert ((str0 != length) || (str1 != length)); + + if (str0 != length) + new_op0 = find_new_var_of_type (op0, new_type); + if (str1 != length) + new_op1 = find_new_var_of_type (op1, new_type); + + if (!new_op0) + new_op0 = offset; + if (!new_op1) + new_op1 = offset; + + new_rhs = build2 (TREE_CODE (rhs), TREE_TYPE (new_op0), + new_op0, new_op1); + } + break; + + default: + gcc_unreachable(); + } + + new_stmt = build_gimple_modify_stmt (new_lhs, new_rhs); + finalize_stmt (new_stmt); + + return new_stmt; +} + +/* Given a field access F_ACC of the FIELD, this function + replaces it by the new field access. */ + +static void +create_new_field_access (struct field_access_site *f_acc, + struct field_entry field) +{ + tree new_type = field.field_mapping; + tree new_stmt; + tree size_res; + tree mult_stmt, cast_stmt; + tree cast_res = NULL; + + if (f_acc->num) + { + mult_stmt = gen_size (f_acc->num, new_type, &size_res); + insert_before_stmt (f_acc->ref_def_stmt, mult_stmt); + } + + if (f_acc->cast_stmt) + { + cast_stmt = gen_cast_stmt (size_res, new_type, + f_acc->cast_stmt, &cast_res); + insert_after_stmt (f_acc->cast_stmt, cast_stmt); + } + + if (f_acc->ref_def_stmt) + { + tree offset; + if (cast_res) + offset = cast_res; + else + offset = size_res; + + new_stmt = create_base_plus_offset (f_acc->ref_def_stmt, + new_type, offset); + insert_after_stmt (f_acc->ref_def_stmt, new_stmt); + } + + /* In stmt D.2163_19 = D.2162_18->b; we replace variable + D.2162_18 by an appropriate variable of new_type type. */ + replace_field_access_stmt (f_acc, new_type); +} + +/* This function creates a new condition statement + corresponding to the original COND_STMT, adds new basic block + and redirects condition edges. NEW_VAR is a new condition + variable located in the condition statement at the position POS. */ + +static void +create_new_stmts_for_cond_expr_1 (tree new_var, tree cond_stmt, bool pos) +{ + tree new_cond; + tree new_stmt; + edge true_e = NULL, false_e = NULL; + basic_block new_bb; + tree stmt_list; + + extract_true_false_edges_from_block (bb_for_stmt (cond_stmt), + &true_e, &false_e); + + new_cond = unshare_expr (COND_EXPR_COND (cond_stmt)); + + TREE_OPERAND (new_cond, pos) = new_var; + + new_stmt = build3 (COND_EXPR, TREE_TYPE (cond_stmt), + new_cond, NULL_TREE, NULL_TREE); + + finalize_stmt (new_stmt); + + /* Create new basic block after bb. */ + new_bb = create_empty_bb (bb_for_stmt (cond_stmt)); + + /* Add new condition stmt to the new_bb. */ + stmt_list = bb_stmt_list (new_bb); + append_to_statement_list (new_stmt, &stmt_list); + add_bb_info (new_bb, stmt_list); + + + /* Create false and true edges from new_bb. */ + make_edge_and_fix_phis_of_dest (new_bb, true_e); + make_edge_and_fix_phis_of_dest (new_bb, false_e); + + /* Redirect one of original edges to point to new_bb. */ + if (TREE_CODE (cond_stmt) == NE_EXPR) + redirect_edge_succ (true_e, new_bb); + else + redirect_edge_succ (false_e, new_bb); +} + +/* This function creates new condition statements corresponding + to original condition STMT, one for each new type, and + recursively redirect edges to newly generated basic blocks. */ + +static void +create_new_stmts_for_cond_expr (tree stmt) +{ + tree cond = COND_EXPR_COND (stmt); + tree arg0, arg1, arg; + unsigned str0, str1; + bool s0, s1; + d_str str; + tree type; + bool pos; + int i; + unsigned length = VEC_length (structure, structures); + + gcc_assert (TREE_CODE (cond) == EQ_EXPR + || TREE_CODE (cond) == NE_EXPR); + + arg0 = TREE_OPERAND (cond, 0); + arg1 = TREE_OPERAND (cond, 1); + + str0 = find_structure (strip_type (get_type_of_var (arg0))); + str1 = find_structure (strip_type (get_type_of_var (arg1))); + + s0 = (str0 != length) ? true : false; + s1 = (str1 != length) ? true : false; + + gcc_assert ((!s0 && s1) || (!s1 && s0)); + + str = s0 ? VEC_index (structure, structures, str0): + VEC_index (structure, structures, str1); + arg = s0 ? arg0 : arg1; + pos = s0 ? 0 : 1; + + for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++) + { + tree new_arg; + + new_arg = find_new_var_of_type (arg, type); + create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos); + } +} + +/* Create a new general access to replace original access ACC + for structure type NEW_TYPE. */ + +static tree +create_general_new_stmt (struct access_site *acc, tree new_type) +{ + tree old_stmt = acc->stmt; + tree var; + tree new_stmt = unshare_expr (old_stmt); + unsigned i; + + + for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++) + { + tree *pos; + tree new_var = find_new_var_of_type (var, new_type); + tree lhs, rhs; + + gcc_assert (new_var); + finalize_var_creation (new_var); + + if (TREE_CODE (new_stmt) == GIMPLE_MODIFY_STMT) + { + + lhs = GIMPLE_STMT_OPERAND (new_stmt, 0); + rhs = GIMPLE_STMT_OPERAND (new_stmt, 1); + + if (TREE_CODE (lhs) == SSA_NAME) + lhs = SSA_NAME_VAR (lhs); + if (TREE_CODE (rhs) == SSA_NAME) + rhs = SSA_NAME_VAR (rhs); + + /* It can happen that rhs is a constructor. + Then we have to replace it to be of new_type. */ + if (TREE_CODE (rhs) == CONSTRUCTOR) + { + /* Dealing only with empty constructors right now. */ + gcc_assert (VEC_empty (constructor_elt, + CONSTRUCTOR_ELTS (rhs))); + rhs = build_constructor (new_type, 0); + GIMPLE_STMT_OPERAND (new_stmt, 1) = rhs; + } + + if (lhs == var) + GIMPLE_STMT_OPERAND (new_stmt, 0) = new_var; + else if (rhs == var) + GIMPLE_STMT_OPERAND (new_stmt, 1) = new_var; + else + { + pos = find_pos_in_stmt (new_stmt, var); + gcc_assert (pos); + *pos = new_var; + } + } + else + { + pos = find_pos_in_stmt (new_stmt, var); + gcc_assert (pos); + *pos = new_var; + } + } + + finalize_stmt (new_stmt); + return new_stmt; +} + +/* For each new type in STR this function creates new general accesses + corresponding to the original access ACC. */ + +static void +create_new_stmts_for_general_acc (struct access_site *acc, d_str str) +{ + tree type; + tree stmt = acc->stmt; + unsigned i; + + for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++) + { + tree new_stmt; + + new_stmt = create_general_new_stmt (acc, type); + insert_after_stmt (stmt, new_stmt); + } +} + +/* This function creates a new general access of structure STR + to replace the access ACC. */ + +static void +create_new_general_access (struct access_site *acc, d_str str) +{ + tree stmt = acc->stmt; + switch (TREE_CODE (stmt)) + { + case COND_EXPR: + create_new_stmts_for_cond_expr (stmt); + break; + + default: + create_new_stmts_for_general_acc (acc, str); + } +} + +/* Auxiliary data for creation of accesses. */ +struct create_acc_data +{ + basic_block bb; + d_str str; + int field_index; +}; + +/* This function creates a new general access, defined by SLOT. + DATA is a pointer to create_acc_data structure. */ + +static int +create_new_acc (void **slot, void *data) +{ + struct access_site *acc = *(struct access_site **) slot; + basic_block bb = ((struct create_acc_data *)data)->bb; + d_str str = ((struct create_acc_data *)data)->str; + + if (bb_for_stmt (acc->stmt) == bb) + create_new_general_access (acc, str); + return 1; +} + +/* This function creates a new field access, defined by SLOT. + DATA is a pointer to create_acc_data structure. */ + +static int +create_new_field_acc (void **slot, void *data) +{ + struct field_access_site *f_acc = *(struct field_access_site **) slot; + basic_block bb = ((struct create_acc_data *)data)->bb; + d_str str = ((struct create_acc_data *)data)->str; + int i = ((struct create_acc_data *)data)->field_index; + + if (bb_for_stmt (f_acc->stmt) == bb) + create_new_field_access (f_acc, str->fields[i]); + return 1; +} + +/* This function creates new accesses for the structure + type STR in basic block BB. */ + +static void +create_new_accs_for_struct (d_str str, basic_block bb) +{ + int i; + struct create_acc_data dt; + + dt.str = str; + dt.bb = bb; + dt.field_index = -1; + + for (i = 0; i < str->num_fields; i++) + { + dt.field_index = i; + + if (str->fields[i].acc_sites) + htab_traverse (str->fields[i].acc_sites, + create_new_field_acc, &dt); + } + if (str->accs) + htab_traverse (str->accs, create_new_acc, &dt); +} + +/* This function inserts new variables from new_var, + defined by SLOT, into varpool. */ + +static int +update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED) +{ + new_var n_var = *(new_var *) slot; + tree var; + unsigned i; + + for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++) + insert_global_to_varpool (var); + return 1; +} + +/* This function prints a field access site, defined by SLOT. */ + +static int +dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct field_access_site *f_acc = + *(struct field_access_site **) slot; + + fprintf(dump_file, "\n"); + if (f_acc->stmt) + print_generic_stmt (dump_file, f_acc->stmt, 0); + if (f_acc->ref_def_stmt) + print_generic_stmt (dump_file, f_acc->ref_def_stmt, 0); + if (f_acc->cast_stmt) + print_generic_stmt (dump_file, f_acc->cast_stmt, 0); + return 1; +} + +/* Print field accesses from hashtable F_ACCS. */ + +static void +dump_field_acc_sites (htab_t f_accs) +{ + if (!dump_file) + return; + + if (f_accs) + htab_traverse (f_accs, dump_field_acc, NULL); +} + +/* Hash value for fallocs_t. */ + +static hashval_t +malloc_hash (const void *x) +{ + return htab_hash_pointer (((const_fallocs_t)x)->func); +} + +/* This function returns nonzero if function of func_alloc_sites' X + is equal to Y. */ + +static int +malloc_eq (const void *x, const void *y) +{ + return ((const_fallocs_t)x)->func == (const_tree)y; +} + +/* This function is a callback for traversal over a structure accesses. + It frees an access represented by SLOT. */ + +static int +free_accs (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct access_site * acc = *(struct access_site **) slot; + + VEC_free (tree, heap, acc->vars); + free (acc); + return 1; +} + +/* This is a callback function for traversal over field accesses. + It frees a field access represented by SLOT. */ + +static int +free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct field_access_site *f_acc = *(struct field_access_site **) slot; + + free (f_acc); + return 1; +} + +/* This function inserts TYPE into vector of UNSUITABLE_TYPES, + if it is not there yet. */ + +static void +add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type) +{ + unsigned i; + tree t; + + if (!type) + return; + + type = TYPE_MAIN_VARIANT (type); + + for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++) + if (is_equal_types (t, type)) + break; + + if (i == VEC_length (tree, *unsuitable_types)) + VEC_safe_push (tree, heap, *unsuitable_types, type); +} + +/* Given a type TYPE, this function returns the name of the type. */ + +static const char * +get_type_name (tree type) +{ + if (! TYPE_NAME (type)) + return NULL; + + if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE) + return IDENTIFIER_POINTER (TYPE_NAME (type)); + else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL + && DECL_NAME (TYPE_NAME (type))) + return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type))); + else + return NULL; +} + +/* This function is a temporary hack to overcome the types problem. + When several compilation units are compiled together + with -combine, the TYPE_MAIN_VARIANT of the same type + can appear differently in different compilation units. + Therefore this function first compares type names. + If there are no names, structure bodies are recursively + compared. */ + +static bool +is_equal_types (tree type1, tree type2) +{ + const char * name1,* name2; + + if ((!type1 && type2) + ||(!type2 && type1)) + return false; + + if (!type1 && !type2) + return true; + + if (TREE_CODE (type1) != TREE_CODE (type2)) + return false; + + if (type1 == type2) + return true; + + if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2)) + return true; + + name1 = get_type_name (type1); + name2 = get_type_name (type2); + + if (name1 && name2 && !strcmp (name1, name2)) + return true; + + if (name1 && name2 && strcmp (name1, name2)) + return false; + + switch (TREE_CODE (type1)) + { + case POINTER_TYPE: + case REFERENCE_TYPE: + { + return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)); + } + break; + + case RECORD_TYPE: + case UNION_TYPE: + case QUAL_UNION_TYPE: + case ENUMERAL_TYPE: + { + tree field1; + /* Compare fields of struture. */ + for (field1 = TYPE_FIELDS (type1); field1; + field1 = TREE_CHAIN (field1)) + { + tree field2 = find_field_in_struct_1 (type2, field1); + if (!field2) + return false; + } + return true; + } + break; + + case INTEGER_TYPE: + { + if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2) + && TYPE_PRECISION (type1) == TYPE_PRECISION (type2)) + return true; + } + break; + + case ARRAY_TYPE: + { + tree d1, d2; + tree max1, min1, max2, min2; + + if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2))) + return false; + + d1 = TYPE_DOMAIN (type1); + d2 = TYPE_DOMAIN (type2); + + if (!d1 || !d2) + return false; + + max1 = TYPE_MAX_VALUE (d1); + max2 = TYPE_MAX_VALUE (d2); + min1 = TYPE_MIN_VALUE (d1); + min2 = TYPE_MIN_VALUE (d2); + + if (max1 && max2 && min1 && min2 + && TREE_CODE (max1) == TREE_CODE (max2) + && TREE_CODE (max1) == INTEGER_CST + && TREE_CODE (min1) == TREE_CODE (min2) + && TREE_CODE (min1) == INTEGER_CST + && tree_int_cst_equal (max1, max2) + && tree_int_cst_equal (min1, min2)) + return true; + } + break; + + default: + gcc_unreachable(); + } + + return false; +} + +/* This function free non-field accesses from hashtable ACCS. */ + +static void +free_accesses (htab_t accs) +{ + if (accs) + htab_traverse (accs, free_accs, NULL); + htab_delete (accs); +} + +/* This function free field accesses hashtable F_ACCS. */ + +static void +free_field_accesses (htab_t f_accs) +{ + if (f_accs) + htab_traverse (f_accs, free_field_accs, NULL); + htab_delete (f_accs); +} + +/* Update call graph with new edge generated by new MALLOC_STMT. + The edge origin is CONTEXT function. */ + +static void +update_cgraph_with_malloc_call (tree malloc_stmt, tree context) +{ + tree call_expr; + struct cgraph_node *src, *dest; + tree malloc_fn_decl; + + if (!malloc_stmt) + return; + + call_expr = get_call_expr_in (malloc_stmt); + malloc_fn_decl = get_callee_fndecl (call_expr); + + src = cgraph_node (context); + dest = cgraph_node (malloc_fn_decl); + cgraph_create_edge (src, dest, malloc_stmt, + 0, 0, bb_for_stmt (malloc_stmt)->loop_depth); +} + +/* This function generates set of statements required + to allocate number NUM of structures of type NEW_TYPE. + The statements are stored in NEW_STMTS. The statement that contain + call to malloc is returned. MALLOC_STMT is an original call to malloc. */ + +static tree +create_new_malloc (tree malloc_stmt, tree new_type, tree *new_stmts, tree num) +{ + tree new_malloc_size; + tree call_expr, malloc_fn_decl; + tree new_stmt, malloc_res; + tree call_stmt, final_stmt; + tree cast_res; + + gcc_assert (num && malloc_stmt && new_type); + *new_stmts = alloc_stmt_list (); + + /* Generate argument to malloc as multiplication of num + and size of new_type. */ + new_stmt = gen_size (num, new_type, &new_malloc_size); + append_to_statement_list (new_stmt, new_stmts); + + /* Generate new call for malloc. */ + malloc_res = create_tmp_var (integer_type_node, NULL); + + if (malloc_res) + add_referenced_var (malloc_res); + + call_expr = get_call_expr_in (malloc_stmt); + malloc_fn_decl = get_callee_fndecl (call_expr); + call_expr = build_call_expr (malloc_fn_decl, 1, new_malloc_size); + call_stmt = build_gimple_modify_stmt (malloc_res, call_expr); + finalize_stmt_and_append (new_stmts, call_stmt); + + /* Create new cast statement. */ + final_stmt = get_final_alloc_stmt (malloc_stmt); + gcc_assert (final_stmt); + new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res); + append_to_statement_list (new_stmt, new_stmts); + + return call_stmt; +} + +/* This function returns a tree representing + the number of instances of structure STR_DECL allocated + by allocation STMT. If new statments are generated, + they are filled into NEW_STMTS_P. */ + +static tree +gen_num_of_structs_in_malloc (tree stmt, tree str_decl, tree *new_stmts_p) +{ + call_expr_arg_iterator iter; + tree arg; + tree call_expr; + tree struct_size; + HOST_WIDE_INT struct_size_int; + + if (!stmt) + return NULL_TREE; + + /* Get malloc argument. */ + call_expr = get_call_expr_in (stmt); + if (!call_expr) + return NULL_TREE; + + arg = first_call_expr_arg (call_expr, &iter); + + if (TREE_CODE (arg) != SSA_NAME + && !TREE_CONSTANT (arg)) + return NULL_TREE; + + struct_size = TYPE_SIZE_UNIT (str_decl); + struct_size_int = TREE_INT_CST_LOW (struct_size); + + gcc_assert (struct_size); + + if (TREE_CODE (arg) == SSA_NAME) + { + tree num, div_stmt; + + if (is_result_of_mult (arg, &num, struct_size)) + return num; + + num = create_tmp_var (integer_type_node, NULL); + + if (num) + add_referenced_var (num); + + if (exact_log2 (struct_size_int) == -1) + div_stmt = build_gimple_modify_stmt (num, + build2 (TRUNC_DIV_EXPR, + integer_type_node, + arg, struct_size)); + else + { + tree C = build_int_cst (integer_type_node, + exact_log2 (struct_size_int)); + + div_stmt = + build_gimple_modify_stmt (num, build2 (RSHIFT_EXPR, + integer_type_node, + arg, C)); + } + *new_stmts_p = alloc_stmt_list (); + append_to_statement_list (div_stmt, + new_stmts_p); + finalize_stmt (div_stmt); + return num; + } + + if (CONSTANT_CLASS_P (arg) + && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size)) + return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0); + + return NULL_TREE; +} + +/* This function is a callback for traversal on new_var's hashtable. + SLOT is a pointer to new_var. This function prints to dump_file + an original variable and all new variables from the new_var + pointed by *SLOT. */ + +static int +dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED) +{ + new_var n_var = *(new_var *) slot; + tree var_type; + tree var; + unsigned i; + + var_type = get_type_of_var (n_var->orig_var); + + fprintf (dump_file, "\nOrig var: "); + print_generic_expr (dump_file, n_var->orig_var, 0); + fprintf (dump_file, " of type "); + print_generic_expr (dump_file, var_type, 0); + fprintf (dump_file, "\n"); + + for (i = 0; + VEC_iterate (tree, n_var->new_vars, i, var); i++) + { + var_type = get_type_of_var (var); + + fprintf (dump_file, " "); + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, " of type "); + print_generic_expr (dump_file, var_type, 0); + fprintf (dump_file, "\n"); + } + return 1; +} + +/* This function copies attributes form ORIG_DECL to NEW_DECL. */ + +static inline void +copy_decl_attributes (tree new_decl, tree orig_decl) +{ + + DECL_ARTIFICIAL (new_decl) = 1; + DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl); + TREE_STATIC (new_decl) = TREE_STATIC (orig_decl); + TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl); + TREE_USED (new_decl) = TREE_USED (orig_decl); + DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl); + TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl); + TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl); + + if (TREE_CODE (orig_decl) == VAR_DECL) + { + TREE_READONLY (new_decl) = TREE_READONLY (orig_decl); + DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl); + } +} + +/* This function wraps NEW_STR_TYPE in pointers or arrays wrapper + the same way as a structure type is wrapped in DECL. + It returns the generated type. */ + +static inline tree +gen_struct_type (tree decl, tree new_str_type) +{ + tree type_orig = get_type_of_var (decl); + tree new_type = new_str_type; + VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10); + type_wrapper_t wr; + type_wrapper_t *wr_p; + + while (POINTER_TYPE_P (type_orig) + || TREE_CODE (type_orig) == ARRAY_TYPE) + { + if (POINTER_TYPE_P (type_orig)) + { + wr.wrap = 0; + wr.domain = NULL_TREE; + } + else if (TREE_CODE (type_orig) == ARRAY_TYPE) + { + wr.wrap = 1; + wr.domain = TYPE_DOMAIN (type_orig); + } + VEC_safe_push (type_wrapper_t, heap, wrapper, &wr); + type_orig = TREE_TYPE (type_orig); + } + + while (VEC_length (type_wrapper_t, wrapper) != 0) + { + wr_p = VEC_last (type_wrapper_t, wrapper); + + if (wr_p->wrap) /* Array. */ + new_type = build_array_type (new_type, wr_p->domain); + else /* Pointer. */ + new_type = build_pointer_type (new_type); + + VEC_pop (type_wrapper_t, wrapper); + } + + VEC_free (type_wrapper_t, heap, wrapper); + return new_type; +} + +/* This function generates and returns new variable name based on + ORIG_DECL name, combined with index I. + The form of the new name is <orig_name>.<I> . */ + +static tree +gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i) +{ + const char *old_name; + char *prefix; + char *new_name; + + if (!DECL_NAME (orig_decl) + || !IDENTIFIER_POINTER (DECL_NAME (orig_decl))) + return NULL; + + /* If the original variable has a name, create an + appropriate new name for the new variable. */ + + old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl)); + prefix = alloca (strlen (old_name) + 1); + strcpy (prefix, old_name); + ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i); + return get_identifier (new_name); +} + +/* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */ + +static void +add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab) +{ + void **slot; + + slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var, + htab_hash_pointer (new_node->orig_var), + INSERT); + *slot = new_node; +} + +/* This function creates and returns new_var_data node + with empty new_vars and orig_var equal to VAR. */ + +static new_var +create_new_var_node (tree var, d_str str) +{ + new_var node; + + node = (new_var) xmalloc (sizeof (struct new_var_data)); + node->orig_var = var; + node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types)); + return node; +} + +/* Check whether the type of VAR is potential candidate for peeling. + Returns true if yes, false otherwise. If yes, TYPE_P will contain + candidate type. If VAR is initialized, the type of VAR will be added + to UNSUITABLE_TYPES. */ + +static bool +is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types) +{ + tree type; + bool initialized = false; + + *type_p = NULL; + + if (!var) + return false; + + /* There is no support of initialized vars. */ + if (TREE_CODE (var) == VAR_DECL + && DECL_INITIAL (var) != NULL_TREE) + initialized = true; + + type = get_type_of_var (var); + + if (type) + { + type = TYPE_MAIN_VARIANT (strip_type (type)); + if (TREE_CODE (type) != RECORD_TYPE) + return false; + else + { + if (initialized && unsuitable_types && *unsuitable_types) + add_unsuitable_type (unsuitable_types, type); + *type_p = type; + return true; + } + } + else + return false; +} + +/* Hash value for field_access_site. */ + +static hashval_t +field_acc_hash (const void *x) +{ + return htab_hash_pointer (((const struct field_access_site *)x)->stmt); +} + +/* This function returns nonzero if stmt of field_access_site X + is equal to Y. */ + +static int +field_acc_eq (const void *x, const void *y) +{ + return ((const struct field_access_site *)x)->stmt == (const_tree)y; +} + +/* This function prints an access site, defined by SLOT. */ + +static int +dump_acc (void **slot, void *data ATTRIBUTE_UNUSED) +{ + struct access_site *acc = *(struct access_site **) slot; + tree var; + unsigned i; + + fprintf(dump_file, "\n"); + if (acc->stmt) + print_generic_stmt (dump_file, acc->stmt, 0); + fprintf(dump_file, " : "); + + for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++) + { + print_generic_expr (dump_file, var, 0); + fprintf(dump_file, ", "); + } + return 1; +} + +/* This function frees memory allocated for strcuture clusters, + starting from CLUSTER. */ + +static void +free_struct_cluster (struct field_cluster* cluster) +{ + if (cluster) + { + if (cluster->fields_in_cluster) + sbitmap_free (cluster->fields_in_cluster); + if (cluster->sibling) + free_struct_cluster (cluster->sibling); + free (cluster); + } +} + +/* Free all allocated memory under the structure node pointed by D_NODE. */ + +static void +free_data_struct (d_str d_node) +{ + int i; + + if (!d_node) + return; + + if (dump_file) + { + fprintf (dump_file, "\nRemoving data structure \""); + print_generic_expr (dump_file, d_node->decl, 0); + fprintf (dump_file, "\" from data_struct_list."); + } + + /* Free all space under d_node. */ + if (d_node->fields) + { + for (i = 0; i < d_node->num_fields; i++) + free_field_accesses (d_node->fields[i].acc_sites); + free (d_node->fields); + } + + if (d_node->accs) + free_accesses (d_node->accs); + + if (d_node->struct_clustering) + free_struct_cluster (d_node->struct_clustering); + + if (d_node->new_types) + VEC_free (tree, heap, d_node->new_types); +} + +/* This function creates new general and field accesses in BB. */ + +static void +create_new_accesses_in_bb (basic_block bb) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + create_new_accs_for_struct (str, bb); +} + +/* This function adds allocation sites for peeled structures. + M_DATA is vector of allocation sites of function CONTEXT. */ + +static void +create_new_alloc_sites (fallocs_t m_data, tree context) +{ + alloc_site_t *call; + unsigned j; + + for (j = 0; + VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++) + { + tree stmt = call->stmt; + d_str str = call->str; + tree num; + tree new_stmts = NULL_TREE; + tree last_stmt = get_final_alloc_stmt (stmt); + unsigned i; + tree type; + + num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts); + if (new_stmts) + { + last_stmt = tsi_stmt (tsi_last (new_stmts)); + insert_after_stmt (last_stmt, new_stmts); + } + + /* Generate an allocation sites for each new structure type. */ + for (i = 0; + VEC_iterate (tree, str->new_types, i, type); i++) + { + tree new_malloc_stmt = NULL_TREE; + tree last_stmt_tmp = NULL_TREE; + + new_stmts = NULL_TREE; + new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num); + last_stmt_tmp = tsi_stmt (tsi_last (new_stmts)); + insert_after_stmt (last_stmt, new_stmts); + update_cgraph_with_malloc_call (new_malloc_stmt, context); + last_stmt = last_stmt_tmp; + } + } +} + +/* This function prints new variables from hashtable + NEW_VARS_HTAB to dump_file. */ + +static void +dump_new_vars (htab_t new_vars_htab) +{ + if (!dump_file) + return; + + if (new_vars_htab) + htab_traverse (new_vars_htab, dump_new_var, NULL); +} + +/* Given an original variable ORIG_DECL of structure type STR, + this function generates new variables of the types defined + by STR->new_type. Generated types are saved in new_var node NODE. + ORIG_DECL should has VAR_DECL tree_code. */ + +static void +create_new_var_1 (tree orig_decl, d_str str, new_var node) +{ + unsigned i; + tree type; + + for (i = 0; + VEC_iterate (tree, str->new_types, i, type); i++) + { + tree new_decl = NULL; + tree new_name; + + new_name = gen_var_name (orig_decl, i); + type = gen_struct_type (orig_decl, type); + + if (is_global_var (orig_decl)) + new_decl = build_decl (VAR_DECL, new_name, type); + else + { + const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL; + new_decl = create_tmp_var (type, name); + } + + copy_decl_attributes (new_decl, orig_decl); + VEC_safe_push (tree, heap, node->new_vars, new_decl); + } +} + +/* This function creates new variables to + substitute the original variable VAR_DECL and adds + them to the new_var's hashtable NEW_VARS_HTAB. */ + +static void +create_new_var (tree var_decl, htab_t new_vars_htab) +{ + new_var node; + d_str str; + tree type; + unsigned i; + + if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab)) + return; + + if (!is_candidate (var_decl, &type, NULL)) + return; + + i = find_structure (type); + if (i == VEC_length (structure, structures)) + return; + + str = VEC_index (structure, structures, i); + node = create_new_var_node (var_decl, str); + create_new_var_1 (var_decl, str, node); + add_to_new_vars_htab (node, new_vars_htab); +} + +/* Hash value for new_var. */ + +static hashval_t +new_var_hash (const void *x) +{ + return htab_hash_pointer (((const_new_var)x)->orig_var); +} + +/* This function returns nonzero if orig_var of new_var X is equal to Y. */ + +static int +new_var_eq (const void *x, const void *y) +{ + return ((const_new_var)x)->orig_var == (const_tree)y; +} + +/* This function check whether a structure type represented by STR + escapes due to ipa-type-escape analysis. If yes, this type is added + to UNSUITABLE_TYPES vector. */ + +static void +check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types) +{ + tree type = str->decl; + + if (!ipa_type_escape_type_contained_p (type)) + { + if (dump_file) + { + fprintf (dump_file, "\nEscaping type is "); + print_generic_expr (dump_file, type, 0); + } + add_unsuitable_type (unsuitable_types, type); + } +} + +/* Hash value for access_site. */ + +static hashval_t +acc_hash (const void *x) +{ + return htab_hash_pointer (((const struct access_site *)x)->stmt); +} + +/* Return nonzero if stmt of access_site X is equal to Y. */ + +static int +acc_eq (const void *x, const void *y) +{ + return ((const struct access_site *)x)->stmt == (const_tree)y; +} + +/* Given a structure declaration STRUCT_DECL, and number of fields + in the structure NUM_FIELDS, this function creates and returns + corresponding field_entry's. */ + +static struct field_entry * +get_fields (tree struct_decl, int num_fields) +{ + struct field_entry *list; + tree t = TYPE_FIELDS (struct_decl); + int idx = 0; + + list = + (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry)); + + for (idx = 0 ; t; t = TREE_CHAIN (t), idx++) + if (TREE_CODE (t) == FIELD_DECL) + { + list[idx].index = idx; + list[idx].decl = t; + list[idx].acc_sites = + htab_create (32, field_acc_hash, field_acc_eq, NULL); + list[idx].count = 0; + list[idx].field_mapping = NULL_TREE; + } + + return list; +} + +/* Print non-field accesses from hashtable ACCS of structure. */ + +static void +dump_access_sites (htab_t accs) +{ + if (!dump_file) + return; + + if (accs) + htab_traverse (accs, dump_acc, NULL); +} + +/* This function removes the structure with index I from structures vector. */ + +static void +remove_structure (unsigned i) +{ + d_str str; + + if (i >= VEC_length (structure, structures)) + return; + + str = VEC_index (structure, structures, i); + free_data_struct (str); + VEC_ordered_remove (structure, structures, i); +} + +/* Currently we support only EQ_EXPR or NE_EXPR conditions. + COND_STNT is a condition statement to check. */ + +static bool +is_safe_cond_expr (tree cond_stmt) +{ + + tree arg0, arg1; + unsigned str0, str1; + bool s0, s1; + unsigned length = VEC_length (structure, structures); + + tree cond = COND_EXPR_COND (cond_stmt); + + if (TREE_CODE (cond) != EQ_EXPR + && TREE_CODE (cond) != NE_EXPR) + return false; + + if (TREE_CODE_LENGTH (TREE_CODE (cond)) != 2) + return false; + + arg0 = TREE_OPERAND (cond, 0); + arg1 = TREE_OPERAND (cond, 1); + + str0 = find_structure (strip_type (get_type_of_var (arg0))); + str1 = find_structure (strip_type (get_type_of_var (arg1))); + + s0 = (str0 != length) ? true : false; + s1 = (str1 != length) ? true : false; + + if (!((!s0 && s1) || (!s1 && s0))) + return false; + + return true; +} + +/* This function excludes statements, that are + part of allocation sites or field accesses, from the + hashtable of general accesses. SLOT represents general + access that will be checked. DATA is a pointer to + exclude_data structure. */ + +static int +exclude_from_accs (void **slot, void *data) +{ + struct access_site *acc = *(struct access_site **) slot; + tree fn_decl = ((struct exclude_data *)data)->fn_decl; + d_str str = ((struct exclude_data *)data)->str; + + if (is_part_of_malloc (acc->stmt, fn_decl) + || is_part_of_field_access (acc->stmt, str)) + { + VEC_free (tree, heap, acc->vars); + free (acc); + htab_clear_slot (str->accs, slot); + } + return 1; +} + +/* Callback function for walk_tree called from collect_accesses_in_bb + function. DATA is the statement which is analyzed. */ + +static tree +get_stmt_accesses (tree *tp, int *walk_subtrees, void *data) +{ + tree stmt = (tree) data; + tree t = *tp; + + if (!t) + return NULL; + + switch (TREE_CODE (t)) + { + case GIMPLE_MODIFY_STMT: + { + tree lhs = GIMPLE_STMT_OPERAND (t, 0); + tree rhs = GIMPLE_STMT_OPERAND (t, 1); + *walk_subtrees = 1; + walk_tree (&lhs, get_stmt_accesses, data, NULL); + walk_tree (&rhs, get_stmt_accesses, data, NULL); + *walk_subtrees = 0; + } + break; + + case BIT_FIELD_REF: + { + tree var = TREE_OPERAND(t, 0); + tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var))); + unsigned i = find_structure (type); + + if (i != VEC_length (structure, structures)) + remove_structure (i); + } + break; + + case COMPONENT_REF: + { + tree ref = TREE_OPERAND (t, 0); + tree field_decl = TREE_OPERAND (t, 1); + + + if ((TREE_CODE (ref) == INDIRECT_REF + || TREE_CODE (ref) == ARRAY_REF + || TREE_CODE (ref) == VAR_DECL) + && TREE_CODE (field_decl) == FIELD_DECL) + { + tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref)); + unsigned i = find_structure (type); + + if (i != VEC_length (structure, structures)) + { + d_str str = VEC_index (structure, structures, i); + struct field_entry * field = + find_field_in_struct (str, field_decl); + + if (field) + { + struct field_access_site *acc = make_field_acc_node (); + + gcc_assert (acc); + + acc->stmt = stmt; + acc->comp_ref = t; + acc->ref = ref; + acc->field_decl = field_decl; + + /* Check whether the access is of the form + we can deal with. */ + if (!decompose_access (str->decl, acc)) + { + remove_structure (i); + free (acc); + } + else + { + /* Increase count of field. */ + basic_block bb = bb_for_stmt (stmt); + field->count += bb->count; + + /* Add stmt to the acc_sites of field. */ + add_field_acc_to_acc_sites (acc, field->acc_sites); + } + *walk_subtrees = 0; + } + } + } + } + break; + + case MINUS_EXPR: + case PLUS_EXPR: + { + tree op0 = TREE_OPERAND (t, 0); + tree op1 = TREE_OPERAND (t, 1); + *walk_subtrees = 1; + walk_tree (&op0, get_stmt_accesses, data, NULL); + walk_tree (&op1, get_stmt_accesses, data, NULL); + *walk_subtrees = 0; + } + break; + + case COND_EXPR: + { + tree cond = COND_EXPR_COND (t); + int i; + for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++) + { + tree t = TREE_OPERAND (cond, i); + + *walk_subtrees = 1; + walk_tree (&t, get_stmt_accesses, data, NULL); + } + *walk_subtrees = 0; + } + break; + + case VAR_DECL: + case SSA_NAME: + { + unsigned i; + + if (TREE_CODE (t) == SSA_NAME) + t = SSA_NAME_VAR (t); + + i = find_structure (strip_type (get_type_of_var (t))); + if (i != VEC_length (structure, structures)) + { + d_str str; + + str = VEC_index (structure, structures, i); + add_access_to_acc_sites (stmt, t, str->accs); + } + *walk_subtrees = 0; + } + break; + + case CALL_EXPR: + { + /* It was checked as part of stage1 that structures + to be transformed cannot be passed as parameters of functions. */ + *walk_subtrees = 0; + } + break; + + default: + return NULL; + } + + return NULL; +} + +/* Free structures hashtable. */ + +static void +free_structures (void) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + free_data_struct (str); + + VEC_free (structure, heap, structures); + structures = NULL; +} + +/* This function is a callback for traversal over new_var's hashtable. + SLOT is a pointer to new_var. This function frees memory allocated + for new_var and pointed by *SLOT. */ + +static int +free_new_var (void **slot, void *data ATTRIBUTE_UNUSED) +{ + new_var n_var = *(new_var *) slot; + + /* Free vector of new_vars. */ + VEC_free (tree, heap, n_var->new_vars); + free (n_var); + return 1; +} + +/* Free new_vars hashtable NEW_VARS_HTAB. */ + +static void +free_new_vars_htab (htab_t new_vars_htab) +{ + if (new_vars_htab) + htab_traverse (new_vars_htab, free_new_var, NULL); + htab_delete (new_vars_htab); + new_vars_htab = NULL; +} + +/* This function creates new general and field accesses that appear in cfun. */ + +static void +create_new_accesses_for_func (void) +{ + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + create_new_accesses_in_bb (bb); +} + +/* Create new allocation sites for the function represented by NODE. */ + +static void +create_new_alloc_sites_for_func (struct cgraph_node *node) +{ + fallocs_t fallocs = get_fallocs (node->decl); + + if (fallocs) + create_new_alloc_sites (fallocs, node->decl); +} + +/* For each local variable of structure type from the vector of structures + this function generates new variable(s) to replace it. */ + +static void +create_new_local_vars (void) +{ + tree var; + referenced_var_iterator rvi; + + new_local_vars = htab_create (num_referenced_vars, + new_var_hash, new_var_eq, NULL); + + FOR_EACH_REFERENCED_VAR (var, rvi) + { + if (!is_global_var (var)) + create_new_var (var, new_local_vars); + } + + if (new_local_vars) + htab_traverse (new_local_vars, finalize_new_vars_creation, NULL); + dump_new_vars (new_local_vars); +} + +/* This function prints the SHIFT number of spaces to the DUMP_FILE. */ + +static inline void +print_shift (unsigned HOST_WIDE_INT shift) +{ + unsigned HOST_WIDE_INT sh = shift; + + while (sh--) + fprintf (dump_file, " "); +} + +/* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */ + +static inline void +update_fields_mapping (struct field_cluster *cluster, tree new_type, + struct field_entry * fields, int num_fields) +{ + int i; + + for (i = 0; i < num_fields; i++) + if (TEST_BIT (cluster->fields_in_cluster, i)) + fields[i].field_mapping = new_type; +} + +/* This functions builds structure with FIELDS, + NAME and attributes similar to ORIG_STRUCT. + It returns the newly created structure. */ + +static tree +build_basic_struct (tree fields, tree name, tree orig_struct) +{ + tree attributes = NULL_TREE; + tree ref = 0; + tree x; + + if (TYPE_ATTRIBUTES (orig_struct)) + attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct)); + ref = make_node (RECORD_TYPE); + TYPE_SIZE (ref) = 0; + decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE); + TYPE_PACKED (ref) = TYPE_PACKED (orig_struct); + for (x = fields; x; x = TREE_CHAIN (x)) + { + DECL_CONTEXT (x) = ref; + DECL_PACKED (x) |= TYPE_PACKED (ref); + } + TYPE_FIELDS (ref) = fields; + layout_type (ref); + TYPE_NAME (ref) = name; + + return ref; +} + +/* This function copies FIELDS from CLUSTER into TREE_CHAIN as part + of preparation for new structure building. NUM_FIELDS is a total + number of fields in the structure. The function returns newly + generated fields. */ + +static tree +create_fields (struct field_cluster * cluster, + struct field_entry * fields, int num_fields) +{ + int i; + tree new_types = NULL_TREE; + tree last = NULL_TREE; + + for (i = 0; i < num_fields; i++) + if (TEST_BIT (cluster->fields_in_cluster, i)) + { + tree new_decl = unshare_expr (fields[i].decl); + + if (!new_types) + new_types = new_decl; + else + TREE_CHAIN (last) = new_decl; + last = new_decl; + } + + TREE_CHAIN (last) = NULL_TREE; + return new_types; + +} + +/* This function creates a cluster name. The name is based on + the original structure name, if it is present. It has a form: + + <original_struct_name>_sub.<CLUST_NUM> + + The original structure name is taken from the type of DECL. + If an original structure name is not present, it's generated to be: + + struct.<STR_NUM> + + The function returns identifier of the new cluster name. */ + +static inline tree +gen_cluster_name (tree decl, int clust_num, int str_num) +{ + const char * orig_name = get_type_name (decl); + char * tmp_name = NULL; + char * prefix; + char * new_name; + size_t len; + + if (!orig_name) + ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num); + + len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub"); + prefix = alloca (len + 1); + memcpy (prefix, tmp_name ? tmp_name : orig_name, + strlen (tmp_name ? tmp_name : orig_name)); + strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub"); + + ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num); + return get_identifier (new_name); +} + +/* This function checks whether the structure STR has bitfields. + If yes, this structure type is added to UNSUITABLE_TYPES vector. */ + +static void +check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types) +{ + tree type = str->decl; + int i; + + for (i = 0; i < str->num_fields; i++) + if (DECL_BIT_FIELD (str->fields[i].decl)) + { + add_unsuitable_type (unsuitable_types, type); + if (dump_file) + { + fprintf (dump_file, "\nType "); + print_generic_expr (dump_file, type, 0); + fprintf (dump_file, "\nescapes due to bitfield "); + print_generic_expr (dump_file, str->fields[i].decl, 0); + } + break; + } +} + +/* This function adds to UNSUITABLE_TYPES those types that escape + due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h]. */ + +static void +exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + check_type_escape (str, unsuitable_types); +} + +/* If a structure type is a return type of any function, + we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */ + +static void +exclude_returned_types (VEC (tree, heap) **unsuitable_types) +{ + struct cgraph_node *c_node; + + for (c_node = cgraph_nodes; c_node; c_node = c_node->next) + { + tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl)); + + if (ret_t) + { + ret_t = strip_type (ret_t); + if (TREE_CODE (ret_t) == RECORD_TYPE) + { + add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t)); + if (dump_file) + { + fprintf (dump_file, "\nThe type \""); + print_generic_expr (dump_file, ret_t, 0); + fprintf (dump_file, + "\" is return type of function...Excluded."); + } + } + } + } +} + +/* This function looks for parameters of local functions + which are of structure types, or derived from them (arrays + of structures, pointers to structures, or their combinations). + We are not handling peeling of such structures right now. + The found structures types are added to UNSUITABLE_TYPES vector. */ + +static void +exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types) +{ + struct cgraph_node *c_node; + + for (c_node = cgraph_nodes; c_node; c_node = c_node->next) + if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL) + { + tree fn = c_node->decl; + tree arg; + + for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) + { + tree type = TREE_TYPE (arg); + + type = strip_type (type); + if (TREE_CODE (type) == RECORD_TYPE) + { + add_unsuitable_type (unsuitable_types, + TYPE_MAIN_VARIANT (type)); + if (dump_file) + { + fprintf (dump_file, "\nPointer to type \""); + print_generic_expr (dump_file, type, 0); + fprintf (dump_file, + "\" is passed to local function...Excluded."); + } + } + } + } +} + +/* This function analyzes structure form of structures + potential for transformation. If we are not capable to transform + structure of some form, we remove it from the structures hashtable. + Right now we cannot handle nested structs, when nesting is + through any level of pointers or arrays. + + TBD: release these constrains in future. + + Note, that in this function we suppose that all structures + in the program are members of the structures hashtable right now, + without excluding escaping types. */ + +static void +check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types) +{ + int i; + + for (i = 0; i < str->num_fields; i++) + { + tree f_type = strip_type(TREE_TYPE (str->fields[i].decl)); + + if (TREE_CODE (f_type) == RECORD_TYPE) + { + add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type)); + add_unsuitable_type (unsuitable_types, str->decl); + if (dump_file) + { + fprintf (dump_file, "\nType "); + print_generic_expr (dump_file, f_type, 0); + fprintf (dump_file, " is a field in the structure "); + print_generic_expr (dump_file, str->decl, 0); + fprintf (dump_file, ". Escaping..."); + } + } + } +} + +/* This function adds a structure TYPE to the vector of structures, + if it's not already there. */ + +static void +add_structure (tree type) +{ + struct data_structure node; + unsigned i; + int num_fields; + + type = TYPE_MAIN_VARIANT (type); + + i = find_structure (type); + + if (i != VEC_length (structure, structures)) + return; + + num_fields = fields_length (type); + node.decl = type; + node.num_fields = num_fields; + node.fields = get_fields (type, num_fields); + node.struct_clustering = NULL; + node.accs = htab_create (32, acc_hash, acc_eq, NULL); + node.new_types = VEC_alloc (tree, heap, num_fields); + node.count = 0; + + VEC_safe_push (structure, heap, structures, &node); + + if (dump_file) + { + fprintf (dump_file, "\nAdding data structure \""); + print_generic_expr (dump_file, type, 0); + fprintf (dump_file, "\" to data_struct_list."); + } +} + +/* This function adds an allocation site to alloc_sites hashtable. + The allocation site appears in STMT of function FN_DECL and + allocates the structure represented by STR. */ + +static void +add_alloc_site (tree fn_decl, tree stmt, d_str str) +{ + fallocs_t fallocs = NULL; + alloc_site_t m_call; + + m_call.stmt = stmt; + m_call.str = str; + + fallocs = + (fallocs_t) htab_find_with_hash (alloc_sites, + fn_decl, htab_hash_pointer (fn_decl)); + + if (!fallocs) + { + void **slot; + + fallocs = (fallocs_t) + xmalloc (sizeof (struct func_alloc_sites)); + fallocs->func = fn_decl; + fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1); + slot = htab_find_slot_with_hash (alloc_sites, fn_decl, + htab_hash_pointer (fn_decl), INSERT); + *slot = fallocs; + } + VEC_safe_push (alloc_site_t, heap, + fallocs->allocs, &m_call); + + if (dump_file) + { + fprintf (dump_file, "\nAdding stmt "); + print_generic_stmt (dump_file, stmt, 0); + fprintf (dump_file, " to list of mallocs."); + } +} + +/* This function returns true if the result of STMT, that contains a call + to an allocation function, is cast to one of the structure types. + STMT should be of the form: T.2 = <alloc_func> (T.1); + If true, I_P contains an index of an allocated structure. + Otherwise I_P contains the length of the vector of structures. */ + +static bool +is_alloc_of_struct (tree stmt, unsigned *i_p) +{ + tree lhs; + tree type; + tree final_stmt; + + final_stmt = get_final_alloc_stmt (stmt); + + if (!final_stmt) + return false; + + /* final_stmt should be of the form: + T.3 = (struct_type *) T.2; */ + + if (TREE_CODE (final_stmt) != GIMPLE_MODIFY_STMT) + return false; + + lhs = GIMPLE_STMT_OPERAND (final_stmt, 0); + + type = get_type_of_var (lhs); + + if (!type) + return false; + + if (!POINTER_TYPE_P (type) + || TREE_CODE (strip_type (type)) != RECORD_TYPE) + return false; + + *i_p = find_structure (strip_type (type)); + + if (*i_p == VEC_length (structure, structures)) + return false; + + return true; +} + +/* This function prints non-field and field accesses + of the structure STR. */ + +static void +dump_accs (d_str str) +{ + int i; + + fprintf (dump_file, "\nAccess sites of struct "); + print_generic_expr (dump_file, str->decl, 0); + + for (i = 0; i < str->num_fields; i++) + { + fprintf (dump_file, "\nAccess site of field "); + print_generic_expr (dump_file, str->fields[i].decl, 0); + dump_field_acc_sites (str->fields[i].acc_sites); + fprintf (dump_file, ":\n"); + } + fprintf (dump_file, "\nGeneral access sites\n"); + dump_access_sites (str->accs); +} + +/* This function checks whether an access statement, pointed by SLOT, + is a condition we are capable to transform. If not, it removes + the structure with index, represented by DATA, from the vector + of structures. */ + +static int +safe_cond_expr_check (void **slot, void *data) +{ + struct access_site *acc = *(struct access_site **) slot; + + if (TREE_CODE (acc->stmt) == COND_EXPR) + { + if (!is_safe_cond_expr (acc->stmt)) + remove_structure (*(unsigned *) data); + } + return 1; +} + +/* This function excludes statements that are part of allocation sites and + field accesses from the hashtable of general accesses of the structure + type STR. Only accesses that belong to the function represented by + NODE are treated. */ + +static void +exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node) +{ + struct exclude_data dt; + dt.str = str; + dt.fn_decl = node->decl; + + if (dt.str->accs) + htab_traverse (dt.str->accs, exclude_from_accs, &dt); +} + +/* Collect accesses to the structure types that apear in basic bloack BB. */ + +static void +collect_accesses_in_bb (basic_block bb) +{ + block_stmt_iterator bsi; + + for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + + /* In asm stmt we cannot always track the arguments, + so we just give up. */ + if (TREE_CODE (stmt) == ASM_EXPR) + { + free_structures (); + break; + } + + walk_tree (&stmt, get_stmt_accesses, stmt, NULL); + } +} + +/* This function generates cluster substructure that cointains FIELDS. + The cluster added to the set of clusters of the structure SRT. */ + +static void +gen_cluster (sbitmap fields, d_str str) +{ + struct field_cluster *crr_cluster = NULL; + + crr_cluster = + (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster)); + crr_cluster->sibling = str->struct_clustering; + str->struct_clustering = crr_cluster; + crr_cluster->fields_in_cluster = fields; +} + +/* This function peels a field with the index I from the structure DS. */ + +static void +peel_field (int i, d_str ds) +{ + struct field_cluster *crr_cluster = NULL; + + crr_cluster = + (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster)); + crr_cluster->sibling = ds->struct_clustering; + ds->struct_clustering = crr_cluster; + crr_cluster->fields_in_cluster = + sbitmap_alloc ((unsigned int) ds->num_fields); + sbitmap_zero (crr_cluster->fields_in_cluster); + SET_BIT (crr_cluster->fields_in_cluster, i); +} + +/* This function calculates maximum field count in + the structure STR. */ + +static gcov_type +get_max_field_count (d_str str) +{ + gcov_type max = 0; + int i; + + for (i = 0; i < str->num_fields; i++) + if (str->fields[i].count > max) + max = str->fields[i].count; + + return max; +} + +/* Do struct-reorg transformation for individual function + represented by NODE. All structure types relevant + for this function are transformed. */ + +static void +do_reorg_for_func (struct cgraph_node *node) +{ + create_new_local_vars (); + create_new_alloc_sites_for_func (node); + create_new_accesses_for_func (); + update_ssa (TODO_update_ssa); + cleanup_tree_cfg (); + + /* Free auxiliary data representing local variables. */ + free_new_vars_htab (new_local_vars); +} + +/* Print structure TYPE, its name, if it exists, and body. + INDENT defines the level of indentation (similar + to the option -i of indent command). SHIFT parameter + defines a number of spaces by which a structure will + be shifted right. */ + +static void +dump_struct_type (tree type, unsigned HOST_WIDE_INT indent, + unsigned HOST_WIDE_INT shift) +{ + const char *struct_name; + tree field; + + if (!type || !dump_file) + return; + + if (TREE_CODE (type) != RECORD_TYPE) + { + print_generic_expr (dump_file, type, 0); + return; + } + + print_shift (shift); + struct_name = get_type_name (type); + fprintf (dump_file, "struct "); + if (struct_name) + fprintf (dump_file, "%s\n",struct_name); + print_shift (shift); + fprintf (dump_file, "{\n"); + + for (field = TYPE_FIELDS (type); field; + field = TREE_CHAIN (field)) + { + unsigned HOST_WIDE_INT s = indent; + tree f_type = TREE_TYPE (field); + + print_shift (shift); + while (s--) + fprintf (dump_file, " "); + dump_struct_type (f_type, indent, shift + indent); + fprintf(dump_file, " "); + print_generic_expr (dump_file, field, 0); + fprintf(dump_file, ";\n"); + } + print_shift (shift); + fprintf (dump_file, "}\n"); +} + +/* This function creates new structure types to replace original type, + indicated by STR->decl. The names of the new structure types are + derived from the original structure type. If the original structure + type has no name, we assume that its name is 'struct.<STR_NUM>'. */ + +static void +create_new_type (d_str str, int *str_num) +{ + int cluster_num = 0; + + struct field_cluster *cluster = str->struct_clustering; + while (cluster) + { + tree name = gen_cluster_name (str->decl, cluster_num, + *str_num); + tree fields; + tree new_type; + cluster_num++; + + fields = create_fields (cluster, str->fields, + str->num_fields); + new_type = build_basic_struct (fields, name, str->decl); + + update_fields_mapping (cluster, new_type, + str->fields, str->num_fields); + + VEC_safe_push (tree, heap, str->new_types, new_type); + cluster = cluster->sibling; + } + (*str_num)++; +} + +/* This function is a callback for alloc_sites hashtable + traversal. SLOT is a pointer to fallocs_t. + This function frees memory pointed by *SLOT. */ + +static int +free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED) +{ + fallocs_t fallocs = *(fallocs_t *) slot; + + VEC_free (alloc_site_t, heap, fallocs->allocs); + free (fallocs); + return 1; +} + +/* Remove structures collected in UNSUITABLE_TYPES + from structures vector. */ + +static void +remove_unsuitable_types (VEC (tree, heap) *unsuitable_types) +{ + d_str str; + tree type; + unsigned i, j; + + for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++) + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + if (is_equal_types (str->decl, type)) + { + remove_structure (i); + break; + } +} + +/* Exclude structure types with bitfields. + We would not want to interfere with other optimizations + that can be done in this case. The structure types with + bitfields are added to UNSUITABLE_TYPES vector. */ + +static void +exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + check_bitfields (str, unsuitable_types); +} + +/* This function checks three types of escape. A structure type escapes: + + 1. if it's a type of parameter of a local function. + 2. if it's a type of function return value. + 3. if it escapes as a result of ipa-type-escape analysis. + + The escaping structure types are added to UNSUITABLE_TYPES vector. */ + +static void +exclude_escaping_types (VEC (tree, heap) **unsuitable_types) +{ + exclude_types_passed_to_local_func (unsuitable_types); + exclude_returned_types (unsuitable_types); + exclude_escaping_types_1 (unsuitable_types); +} + +/* This function analyzes whether the form of + structure is such that we are capable to transform it. + Nested structures are checked here. Unsuitable structure + types are added to UNSUITABLE_TYPE vector. */ + +static void +analyze_struct_form (VEC (tree, heap) **unsuitable_types) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + check_struct_form (str, unsuitable_types); +} + +/* This function looks for structure types instantiated in the program. + The candidate types are added to the structures vector. + Unsuitable types are collected into UNSUITABLE_TYPES vector. */ + +static void +build_data_structure (VEC (tree, heap) **unsuitable_types) +{ + tree var, type; + tree var_list; + struct varpool_node *current_varpool; + struct cgraph_node *c_node; + + /* Check global variables. */ + FOR_EACH_STATIC_VARIABLE (current_varpool) + { + var = current_varpool->decl; + if (is_candidate (var, &type, unsuitable_types)) + add_structure (type); + } + + /* Now add structures that are types of function parameters and + local variables. */ + for (c_node = cgraph_nodes; c_node; c_node = c_node->next) + { + enum availability avail = + cgraph_function_body_availability (c_node); + + /* We need AVAIL_AVAILABLE for main function. */ + if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE) + { + struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl); + + for (var = DECL_ARGUMENTS (c_node->decl); var; + var = TREE_CHAIN (var)) + if (is_candidate (var, &type, unsuitable_types)) + add_structure (type); + + /* Check function local variables. */ + for (var_list = fn->unexpanded_var_list; var_list; + var_list = TREE_CHAIN (var_list)) + { + var = TREE_VALUE (var_list); + + if (is_candidate (var, &type, unsuitable_types)) + add_structure (type); + } + } + } +} + +/* This function returns true if the program contains + a call to user defined allocation function, or other + functions that can interfere with struct-reorg optimizations. */ + +static bool +program_redefines_malloc_p (void) +{ + struct cgraph_node *c_node; + struct cgraph_node *c_node2; + struct cgraph_edge *c_edge; + tree fndecl; + tree fndecl2; + tree call_expr; + + for (c_node = cgraph_nodes; c_node; c_node = c_node->next) + { + fndecl = c_node->decl; + + for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee) + { + call_expr = get_call_expr_in (c_edge->call_stmt); + c_node2 = c_edge->callee; + fndecl2 = c_node2->decl; + if (call_expr) + { + const char * fname = get_name (fndecl2); + + if ((call_expr_flags (call_expr) & ECF_MALLOC) && + (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC) && + (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC) && + (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA)) + return true; + + /* Check that there is no __builtin_object_size, + __builtin_offsetof, or realloc's in the program. */ + if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE + || !strcmp (fname, "__builtin_offsetof") + || !strcmp (fname, "realloc")) + return true; + } + } + } + + return false; +} + +/* In this function we assume that an allocation statement + + var = (type_cast) malloc (size); + + is converted into the following set of statements: + + T.1 = size; + T.2 = malloc (T.1); + T.3 = (type_cast) T.2; + var = T.3; + + In this function we collect into alloc_sites the allocation + sites of variables of structure types that are present + in structures vector. */ + +static void +collect_alloc_sites (void) +{ + struct cgraph_node *node; + struct cgraph_edge *cs; + + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed && node->decl) + { + for (cs = node->callees; cs; cs = cs->next_callee) + { + tree stmt = cs->call_stmt; + + if (stmt) + { + tree call = get_call_expr_in (stmt); + tree decl; + + if (call && (decl = get_callee_fndecl (call)) + && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) + { + unsigned i; + + if (is_alloc_of_struct (stmt, &i)) + { + /* We support only malloc now. */ + if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC) + { + d_str str; + + str = VEC_index (structure, structures, i); + add_alloc_site (node->decl, stmt, str); + } + else + remove_structure (i); + } + } + } + } + } +} + +/* Print collected accesses. */ + +static void +dump_accesses (void) +{ + d_str str; + unsigned i; + + if (!dump_file) + return; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + dump_accs (str); +} + +/* This function checks whether the accesses of structures in condition + expressions are of the kind we are capable to transform. + If not, such structures are removed from the vector of structures. */ + +static void +check_cond_exprs (void) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + if (str->accs) + htab_traverse (str->accs, safe_cond_expr_check, &i); +} + +/* We exclude from non-field accesses of the structure + all statements that will be treated as part of the structure + allocation sites or field accesses. */ + +static void +exclude_alloc_and_field_accs (struct cgraph_node *node) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + exclude_alloc_and_field_accs_1 (str, node); +} + +/* This function collects accesses of the fields of the structures + that appear at function FN. */ + +static void +collect_accesses_in_func (struct function *fn) +{ + basic_block bb; + + if (! fn) + return; + + /* Collect accesses for each basic blocks separately. */ + FOR_EACH_BB_FN (bb, fn) + collect_accesses_in_bb (bb); +} + +/* This function summarizes counts of the fields into the structure count. */ + +static void +sum_counts (d_str str, gcov_type *hotest) +{ + int i; + + str->count = 0; + for (i = 0; i < str->num_fields; i++) + { + if (dump_file) + { + fprintf (dump_file, "\nCounter of field \""); + print_generic_expr (dump_file, str->fields[i].decl, 0); + fprintf (dump_file, "\" is " HOST_WIDE_INT_PRINT_DEC, + str->fields[i].count); + } + str->count += str->fields[i].count; + } + + if (dump_file) + { + fprintf (dump_file, "\nCounter of struct \""); + print_generic_expr (dump_file, str->decl, 0); + fprintf (dump_file, "\" is " HOST_WIDE_INT_PRINT_DEC, str->count); + } + + if (str->count > *hotest) + *hotest = str->count; +} + +/* This function peels the field into separate structure if it's + sufficiently hot, i.e. if its count provides at least 90% of + the maximum field count in the structure. */ + +static void +peel_hot_fields (d_str str) +{ + gcov_type max_field_count; + sbitmap fields_left = sbitmap_alloc (str->num_fields); + int i; + + sbitmap_ones (fields_left); + max_field_count = + (gcov_type) (get_max_field_count (str)/100)*90; + + str->struct_clustering = NULL; + + for (i = 0; i < str->num_fields; i++) + { + if (str->count >= max_field_count) + { + RESET_BIT (fields_left, i); + peel_field (i, str); + } + } + + i = sbitmap_first_set_bit (fields_left); + if (i != -1) + gen_cluster (fields_left, str); + else + sbitmap_free (fields_left); +} + +/* This function is a helper for do_reorg. It goes over + functions in call graph and performs actual transformation + on them. */ + +static void +do_reorg_1 (void) +{ + struct cgraph_node *node; + + /* Initialize the default bitmap obstack. */ + bitmap_obstack_initialize (NULL); + + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed && node->decl && !node->next_clone) + { + push_cfun (DECL_STRUCT_FUNCTION (node->decl)); + current_function_decl = node->decl; + if (dump_file) + fprintf (dump_file, "\nFunction to do reorg is %s: \n", + (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl))); + do_reorg_for_func (node); + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + current_function_decl = NULL; + pop_cfun (); + } + + cfun = NULL; +} + +/* This function creates new global struct variables. + For each original variable, the set of new variables + is created with the new structure types corresponding + to the structure type of original variable. + Only VAR_DECL variables are treated by this function. */ + +static void +create_new_global_vars (void) +{ + struct varpool_node *current_varpool; + unsigned HOST_WIDE_INT i; + unsigned HOST_WIDE_INT varpool_size = 0; + + for (i = 0; i < 2; i++) + { + if (i) + new_global_vars = htab_create (varpool_size, + new_var_hash, new_var_eq, NULL); + FOR_EACH_STATIC_VARIABLE(current_varpool) + { + tree var_decl = current_varpool->decl; + + if (!var_decl || TREE_CODE (var_decl) != VAR_DECL) + continue; + if (!i) + varpool_size++; + else + create_new_var (var_decl, new_global_vars); + } + } + + if (new_global_vars) + htab_traverse (new_global_vars, update_varpool_with_new_var, NULL); +} + +/* Dump all new types generated by this optimization. */ + +static void +dump_new_types (void) +{ + d_str str; + tree type; + unsigned i, j; + + if (!dump_file) + return; + + fprintf (dump_file, "\nThe following are the new types generated by" + " this optimization:\n"); + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++) + dump_struct_type (type, 2, 0); +} + +/* This function creates new types to replace old structure types. */ + +static void +create_new_types (void) +{ + d_str str; + unsigned i; + int str_num = 0; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + create_new_type (str, &str_num); +} + +/* Free allocation sites hashtable. */ + +static void +free_alloc_sites (void) +{ + if (alloc_sites) + htab_traverse (alloc_sites, free_falloc_sites, NULL); + htab_delete (alloc_sites); + alloc_sites = NULL; +} + +/* This function collects structures potential + for peeling transformation, and inserts + them into structures hashtable. */ + +static void +collect_structures (void) +{ + VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32); + + structures = VEC_alloc (structure, heap, 32); + + /* If program contains user defined mallocs, we give up. */ + if (program_redefines_malloc_p ()) + return; + + /* Build data structures hashtable of all data structures + in the program. */ + build_data_structure (&unsuitable_types); + + /* This function analyzes whether the form of + structure is such that we are capable to transform it. + Nested structures are checked here. */ + analyze_struct_form (&unsuitable_types); + + /* This function excludes those structure types + that escape compilation unit. */ + exclude_escaping_types (&unsuitable_types); + + /* We do not want to change data layout of the structures with bitfields. */ + exclude_types_with_bit_fields (&unsuitable_types); + + remove_unsuitable_types (unsuitable_types); + VEC_free (tree, heap, unsuitable_types); + + if (!VEC_length (structure, structures)) + { + if (dump_file) + fprintf (dump_file, "\nNo structures to transform. Exiting..."); + return; + } +} + +/* Collect structure allocation sites. In case of arrays + we have nothing to do. */ + +static void +collect_allocation_sites (void) +{ + alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL); + collect_alloc_sites (); +} + +/* This function collects data accesses for the + structures to be transformed. For each structure + field it updates the count field in field_entry. */ + +static void +collect_data_accesses (void) +{ + struct cgraph_node *c_node; + + for (c_node = cgraph_nodes; c_node; c_node = c_node->next) + { + enum availability avail = cgraph_function_body_availability (c_node); + + if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE) + { + struct function *func = DECL_STRUCT_FUNCTION (c_node->decl); + + if (!c_node->next_clone) + collect_accesses_in_func (func); + exclude_alloc_and_field_accs (c_node); + } + } + + check_cond_exprs (); + /* Print collected accesses. */ + dump_accesses (); +} + +/* We do not bother to transform cold structures. + Coldness of the structure is defined relatively + to the highest structure count among the structures + to be transformed. It's triggered by the compiler parameter + + --param struct-reorg-cold-struct-ratio=<value> + + where <value> ranges from 0 to 100. Structures with count ratios + that are less than this parameter are considered to be cold. */ + +static void +exclude_cold_structs (void) +{ + gcov_type hotest = 0; + unsigned i; + d_str str; + + /* We summarize counts of fields of a structure into the structure count. */ + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + sum_counts (str, &hotest); + + /* Remove cold structures from structures vector. */ + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + if (str->count * 100 < (hotest * STRUCT_REORG_COLD_STRUCT_RATIO)) + remove_structure (i); +} + +/* This function decomposes original structure into substructures, + i.e.clusters. */ + +static void +peel_structs (void) +{ + d_str str; + unsigned i; + + for (i = 0; VEC_iterate (structure, structures, i, str); i++) + peel_hot_fields (str); +} + +/* Stage 3. */ +/* Do the actual transformation for each structure + from the structures hashtable. */ + +static void +do_reorg (void) +{ + /* Check that there is a work to do. */ + if (!VEC_length (structure, structures)) + return; + + /* Generate new types. */ + create_new_types (); + dump_new_types (); + + /* Create new global variables. */ + create_new_global_vars (); + dump_new_vars (new_global_vars); + + /* Decompose structures for each function separately. */ + do_reorg_1 (); + + /* Free auxiliary data collected for global variables. */ + free_new_vars_htab (new_global_vars); +} + +/* Free all auxiliary data used by this optimization. */ + +static void +free_data_structs (void) +{ + free_structures (); + free_alloc_sites (); +} + +/* Perform structure decomposition (peeling). */ + +static void +reorg_structs (void) +{ + + /* Stage1. */ + /* Collect structure types. */ + collect_structures (); + + /* Collect structure allocation sites. */ + collect_allocation_sites (); + + /* Collect structure accesses. */ + collect_data_accesses (); + + /* We transform only hot structures. */ + exclude_cold_structs (); + + /* Stage2. */ + /* Decompose structures into substructures, i.e. clusters. */ + peel_structs (); + + /* Stage3. */ + /* Do the actual transformation for each structure + from the structures hashtable. */ + do_reorg (); + + /* Free all auxiliary data used by this optimization. */ + free_data_structs (); +} + +/* Struct-reorg optimization entry point function. */ + +static unsigned int +reorg_structs_drive (void) +{ + reorg_structs (); + return 0; +} + +/* Struct-reorg optimization gate function. */ + +static bool +struct_reorg_gate (void) +{ + return flag_ipa_struct_reorg && flag_whole_program + && (optimize > 0); +} + +struct tree_opt_pass pass_ipa_struct_reorg = +{ + "ipa_struct_reorg", /* name */ + struct_reorg_gate, /* gate */ + reorg_structs_drive, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_INTEGRATION, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + TODO_verify_ssa, /* todo_flags_start */ + TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ + 0 /* letter */ +}; diff --git a/gcc/ipa-struct-reorg.h b/gcc/ipa-struct-reorg.h new file mode 100644 index 00000000000..6f4c5b83d75 --- /dev/null +++ b/gcc/ipa-struct-reorg.h @@ -0,0 +1,113 @@ +/* Struct-reorg optimization. + Copyright (C) 2002, 2003-2007 Free Software Foundation, Inc. + Contributed by Olga Golovanevsky <olga@il.ibm.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2 of the License, or +(at your option) any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; if not, write to the Free Software +Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +#ifndef IPA_STRUCT_REORG_H +#define IPA_STRUCT_REORG_H + +/* This file contains data structures and interfaces required + for struct-reorg optimizations. */ + +/* An access site of the structure field. + We consider an access to be of the following form: + + D.2166_21 = i.6_20 * 8; + D.2167_22 = (struct str_t *) D.2166_21; + D.2168_24 = D.2167_22 + p.5_23; + D.2169_25 = D.2168_24->b; +*/ + +struct field_access_site +{ + /* Statement in which the access site occurs. */ + tree stmt; /* D.2169_25 = D.2168_24->b; */ + tree comp_ref; /* D.2168_24->b */ + tree field_decl; /* b */ + tree ref; /* D.2168_24 */ + tree num; /* i.6_20 */ + tree offset; /* D2167_22 */ + tree base; /* p.5_23 */ + tree ref_def_stmt; /* D.2168_24 = D.2167_22 + p.5_23; */ + tree cast_stmt; /* D.2167_22 = (struct str_t *) D.2166_21; + This statement is not always present. */ +}; + +/* A non-field structure access site. */ +struct access_site +{ + /* A statement in which the access site occurs. */ + tree stmt; + /* A list of structure variables in the access site. */ + VEC (tree, heap) *vars; +}; + +/* A field of the structure. */ +struct field_entry +{ + /* A field index. */ + int index; + /* Number of times the field is accessed (according to profiling). */ + gcov_type count; + tree decl; + /* A type of a new structure this field belongs to. */ + tree field_mapping; + htab_t acc_sites; +}; + +/* This structure represents a result of the structure peeling. + The original structure is decomposed into substructures, or clusters. */ +struct field_cluster +{ + /* A bitmap of field indices. The set bit indicates that the field + corresponding to it is a part of this cluster. */ + sbitmap fields_in_cluster; + struct field_cluster *sibling; +}; + +/* An information about an individual structure type (RECORD_TYPE) required + by struct-reorg optimizations to perform a transformation. */ +struct data_structure +{ + + /* A main variant of the structure type. */ + tree decl; + + /* Number of fields in the structure. */ + int num_fields; + + /* A structure access count collected through profiling. */ + gcov_type count; + + /* An array of the structure fields, indexed by field ID. */ + struct field_entry *fields; + + /* Non-field accesses of the structure. */ + htab_t accs; + + /* A data structure representing a reorganization decision. */ + struct field_cluster *struct_clustering; + + /* New types to replace an the original structure type. */ + VEC(tree, heap) *new_types; +}; + +typedef struct data_structure * d_str; + +#endif /* IPA_STRUCT_REORG_H */ |