1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Olga Golovanevsky <olga@il.ibm.com>
4 (Initial version of this code was developed
5 by Caroline Tice and Mostafa Hagog.)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-flow-inline.h"
34 #include "langhooks.h"
35 #include "pointer-set.h"
42 #include "diagnostic.h"
48 #include "basic-block.h"
49 #include "tree-iterator.h"
50 #include "tree-pass.h"
51 #include "ipa-struct-reorg.h"
53 #include "ipa-type-escape.h"
54 #include "tree-dump.h"
57 /* This optimization implements structure peeling.
59 For example, given a structure type:
67 it can be peeled into two structure types as follows:
69 typedef struct and typedef struct
75 or can be fully peeled:
92 When structure type is peeled all instances and their accesses
93 in the program are updated accordingly. For example, if there is
98 and structure type str_t was peeled into two structures str_t_0
99 and str_t_1 as it was shown above, then array A will be replaced
100 by two arrays as follows:
105 The field access of field a of element i of array A: A[i].a will be
106 replaced by an access to field a of element i of array A_0: A_0[i].a.
108 This optimization also supports dynamically allocated arrays.
109 If array of structures was allocated by malloc function:
111 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
113 the allocation site will be replaced to reflect new structure types:
115 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
116 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
118 The field access through the pointer p[i].a will be changed by p_0[i].a.
120 The goal of structure peeling is to improve spatial locality.
121 For example, if one of the fields of a structure is accessed frequently
124 for (i = 0; i < N; i++)
129 the allocation of field a of str_t contiguously in memory will
130 increase the chances of fetching the field from cache.
132 The analysis part of this optimization is based on the frequency of
133 field accesses, which are collected all over the program.
134 Then the fields with the frequencies that satisfy the following condition
135 get peeled out of the structure:
137 freq(f) > C * max_field_freq_in_struct
139 where max_field_freq_in_struct is the maximum field frequency
140 in the structure. C is a constant defining which portion of
141 max_field_freq_in_struct the fields should have in order to be peeled.
143 If profiling information is provided, it is used to calculate the
144 frequency of field accesses. Otherwise, the structure is fully peeled.
146 IPA type-escape analysis is used to determine when it is safe
149 The optimization is activated by flag -fipa-struct-reorg. */
151 /* New variables created by this optimization.
152 When doing struct peeling, each variable of
153 the original struct type will be replaced by
154 the set of new variables corresponding to
155 the new structure types. */
156 struct new_var_data {
157 /* VAR_DECL for original struct type. */
159 /* Vector of new variables. */
160 VEC(tree, heap) *new_vars;
163 typedef struct new_var_data *new_var;
164 typedef const struct new_var_data *const_new_var;
166 /* This structure represents allocation site of the structure. */
167 typedef struct alloc_site
173 DEF_VEC_O (alloc_site_t);
174 DEF_VEC_ALLOC_O (alloc_site_t, heap);
176 /* Allocation sites that belong to the same function. */
177 struct func_alloc_sites
180 /* Vector of allocation sites for function. */
181 VEC (alloc_site_t, heap) *allocs;
184 typedef struct func_alloc_sites *fallocs_t;
185 typedef const struct func_alloc_sites *const_fallocs_t;
187 /* All allocation sites in the program. */
188 htab_t alloc_sites = NULL;
190 /* New global variables. Generated once for whole program. */
191 htab_t new_global_vars;
193 /* New local variables. Generated per-function. */
194 htab_t new_local_vars;
196 /* Vector of structures to be transformed. */
197 typedef struct data_structure structure;
198 DEF_VEC_O (structure);
199 DEF_VEC_ALLOC_O (structure, heap);
200 VEC (structure, heap) *structures;
202 /* Forward declarations. */
203 static bool is_equal_types (tree, tree);
205 /* Strip structure TYPE from pointers and arrays. */
208 strip_type (tree type)
210 gcc_assert (TYPE_P (type));
212 while (POINTER_TYPE_P (type)
213 || TREE_CODE (type) == ARRAY_TYPE)
214 type = TREE_TYPE (type);
219 /* This function returns type of VAR. */
222 get_type_of_var (tree var)
227 if (TREE_CODE (var) == PARM_DECL)
228 return DECL_ARG_TYPE (var);
230 return TREE_TYPE (var);
233 /* Set of actions we do for each newly generated STMT. */
236 finalize_stmt (gimple stmt)
239 mark_symbols_for_renaming (stmt);
242 /* This function finalizes STMT and appends it to the list STMTS. */
245 finalize_stmt_and_append (gimple_seq *stmts, gimple stmt)
247 gimple_seq_add_stmt (stmts, stmt);
248 finalize_stmt (stmt);
251 /* Given structure type SRT_TYPE and field FIELD,
252 this function is looking for a field with the same name
253 and type as FIELD in STR_TYPE. It returns it if found,
254 or NULL_TREE otherwise. */
257 find_field_in_struct_1 (tree str_type, tree field)
261 if (!DECL_NAME (field))
264 for (str_field = TYPE_FIELDS (str_type); str_field;
265 str_field = TREE_CHAIN (str_field))
267 const char *str_field_name;
268 const char *field_name;
270 if (!DECL_NAME (str_field))
273 str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
274 field_name = IDENTIFIER_POINTER (DECL_NAME (field));
276 gcc_assert (str_field_name);
277 gcc_assert (field_name);
279 if (!strcmp (str_field_name, field_name))
281 /* Check field types. */
282 if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
290 /* Given a field declaration FIELD_DECL, this function
291 returns corresponding field entry in structure STR. */
293 static struct field_entry *
294 find_field_in_struct (d_str str, tree field_decl)
298 tree field = find_field_in_struct_1 (str->decl, field_decl);
300 for (i = 0; i < str->num_fields; i++)
301 if (str->fields[i].decl == field)
302 return &(str->fields[i]);
307 /* This function checks whether ARG is a result of multiplication
308 of some number by STRUCT_SIZE. If yes, the function returns true
309 and this number is filled into NUM. */
312 is_result_of_mult (tree arg, tree *num, tree struct_size)
314 gimple size_def_stmt = SSA_NAME_DEF_STMT (arg);
316 /* If the allocation statement was of the form
317 D.2229_10 = <alloc_func> (D.2228_9);
318 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
320 if (size_def_stmt && is_gimple_assign (size_def_stmt))
322 tree lhs = gimple_assign_lhs (size_def_stmt);
324 /* We expect temporary here. */
325 if (!is_gimple_reg (lhs))
328 if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR)
330 tree arg0 = gimple_assign_rhs1 (size_def_stmt);
331 tree arg1 = gimple_assign_rhs2 (size_def_stmt);
333 if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
339 if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
352 /* This function returns true if access ACC corresponds to the pattern
353 generated by compiler when an address of element i of an array
354 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
355 pattern is recognized correctly, this function returns true
356 and fills missing fields in ACC. Otherwise it returns false. */
359 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
362 tree struct_size, op0, op1;
364 enum tree_code rhs_code;
366 ref_var = TREE_OPERAND (acc->ref, 0);
368 if (TREE_CODE (ref_var) != SSA_NAME)
371 acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
372 if (!(acc->ref_def_stmt)
373 || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN))
376 rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt);
378 if (rhs_code != PLUS_EXPR
379 && rhs_code != MINUS_EXPR
380 && rhs_code != POINTER_PLUS_EXPR)
383 op0 = gimple_assign_rhs1 (acc->ref_def_stmt);
384 op1 = gimple_assign_rhs2 (acc->ref_def_stmt);
386 if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1,
387 &acc->base, &acc->offset,
392 before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
394 before_cast = acc->offset;
400 if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
403 struct_size = TYPE_SIZE_UNIT (str_decl);
405 if (!is_result_of_mult (before_cast, &acc->num, struct_size))
412 /* This function checks whether the access ACC of structure type STR
413 is of the form suitable for transformation. If yes, it returns true.
417 decompose_access (tree str_decl, struct field_access_site *acc)
419 gcc_assert (acc->ref);
421 if (TREE_CODE (acc->ref) == INDIRECT_REF)
422 return decompose_indirect_ref_acc (str_decl, acc);
423 else if (TREE_CODE (acc->ref) == ARRAY_REF)
425 else if (TREE_CODE (acc->ref) == VAR_DECL)
431 /* This function creates empty field_access_site node. */
433 static inline struct field_access_site *
434 make_field_acc_node (void)
436 int size = sizeof (struct field_access_site);
438 return (struct field_access_site *) xcalloc (1, size);
441 /* This function returns the structure field access, defined by STMT,
442 if it is already in hashtable of function accesses F_ACCS. */
444 static struct field_access_site *
445 is_in_field_accs (gimple stmt, htab_t f_accs)
447 return (struct field_access_site *)
448 htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
451 /* This function adds an access ACC to the hashtable
452 F_ACCS of field accesses. */
455 add_field_acc_to_acc_sites (struct field_access_site *acc,
460 gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
461 slot = htab_find_slot_with_hash (f_accs, acc->stmt,
462 htab_hash_pointer (acc->stmt),
467 /* This function adds the VAR to vector of variables of
468 an access site defined by statement STMT. If access entry
469 with statement STMT does not exist in hashtable of
470 accesses ACCS, this function creates it. */
473 add_access_to_acc_sites (gimple stmt, tree var, htab_t accs)
475 struct access_site *acc;
477 acc = (struct access_site *)
478 htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
484 acc = (struct access_site *) xmalloc (sizeof (struct access_site));
486 acc->vars = VEC_alloc (tree, heap, 10);
487 slot = htab_find_slot_with_hash (accs, stmt,
488 htab_hash_pointer (stmt), INSERT);
492 VEC_safe_push (tree, heap, acc->vars, var);
495 /* This function adds NEW_DECL to function
496 referenced vars, and marks it for renaming. */
499 finalize_var_creation (tree new_decl)
501 add_referenced_var (new_decl);
502 mark_sym_for_renaming (new_decl);
505 /* This function finalizes VAR creation if it is a global VAR_DECL. */
508 finalize_global_creation (tree var)
510 if (TREE_CODE (var) == VAR_DECL
511 && is_global_var (var))
512 finalize_var_creation (var);
515 /* This function inserts NEW_DECL to varpool. */
518 insert_global_to_varpool (tree new_decl)
520 struct varpool_node *new_node;
522 new_node = varpool_node (new_decl);
523 notice_global_symbol (new_decl);
524 varpool_mark_needed_node (new_node);
525 varpool_finalize_decl (new_decl);
528 /* This function finalizes the creation of new variables,
529 defined by *SLOT->new_vars. */
532 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
534 new_var n_var = *(new_var *) slot;
538 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
539 finalize_var_creation (var);
543 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
544 It returns it, if found, and NULL_TREE otherwise. */
547 find_var_in_new_vars_vec (new_var var, tree new_type)
552 for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
554 tree type = strip_type(get_type_of_var (n_var));
557 if (type == new_type)
564 /* This function returns new_var node, the orig_var of which is DECL.
565 It looks for new_var's in NEW_VARS_HTAB. If not found,
566 the function returns NULL. */
569 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
571 return (new_var) htab_find_with_hash (new_vars_htab, decl,
572 htab_hash_pointer (decl));
575 /* Given original variable ORIG_VAR, this function returns
576 new variable corresponding to it of NEW_TYPE type. */
579 find_new_var_of_type (tree orig_var, tree new_type)
582 gcc_assert (orig_var && new_type);
584 if (TREE_CODE (orig_var) == SSA_NAME)
585 orig_var = SSA_NAME_VAR (orig_var);
587 var = is_in_new_vars_htab (orig_var, new_global_vars);
589 var = is_in_new_vars_htab (orig_var, new_local_vars);
591 return find_var_in_new_vars_vec (var, new_type);
594 /* This function generates stmt:
595 res = NUM * sizeof(TYPE) and returns it.
596 res is filled into RES. */
599 gen_size (tree num, tree type, tree *res)
601 tree struct_size = TYPE_SIZE_UNIT (type);
602 HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
605 *res = create_tmp_var (TREE_TYPE (num), NULL);
608 add_referenced_var (*res);
610 if (exact_log2 (struct_size_int) == -1)
612 tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
613 new_stmt = gimple_build_assign (*res, fold_build2 (MULT_EXPR,
619 tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
621 new_stmt = gimple_build_assign (*res, fold_build2 (LSHIFT_EXPR,
626 finalize_stmt (new_stmt);
630 /* This function generates and returns a statement, that cast variable
631 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
632 into RES_P. ORIG_CAST_STMT is the original cast statement. */
635 gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt,
641 lhs = gimple_assign_lhs (orig_cast_stmt);
642 new_lhs = find_new_var_of_type (lhs, new_type);
643 gcc_assert (new_lhs);
645 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0);
646 finalize_stmt (new_stmt);
651 /* This function builds an edge between BB and E->dest and updates
652 phi nodes of E->dest. It returns newly created edge. */
655 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
659 gimple_stmt_iterator si;
661 new_e = make_edge (bb, e->dest, e->flags);
663 for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si))
665 gimple phi = gsi_stmt (si);
666 arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
667 add_phi_arg (phi, arg, new_e, gimple_phi_arg_location_from_edge (phi, e));
673 /* This function inserts NEW_STMT before STMT. */
676 insert_before_stmt (gimple stmt, gimple new_stmt)
678 gimple_stmt_iterator bsi;
680 if (!stmt || !new_stmt)
683 bsi = gsi_for_stmt (stmt);
684 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
687 /* Insert NEW_STMTS after STMT. */
690 insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts)
692 gimple_stmt_iterator bsi;
694 if (!stmt || !new_stmts)
697 bsi = gsi_for_stmt (stmt);
698 gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT);
701 /* Insert NEW_STMT after STMT. */
704 insert_after_stmt (gimple stmt, gimple new_stmt)
706 gimple_stmt_iterator bsi;
708 if (!stmt || !new_stmt)
711 bsi = gsi_for_stmt (stmt);
712 gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT);
715 /* This function returns vector of allocation sites
716 that appear in function FN_DECL. */
719 get_fallocs (tree fn_decl)
721 return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
722 htab_hash_pointer (fn_decl));
725 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
726 and it is a part of allocation of a structure,
727 then it is usually followed by a cast stmt
728 p_8 = (struct str_t *) D.2225_7;
729 which is returned by this function. */
732 get_final_alloc_stmt (gimple alloc_stmt)
741 if (!is_gimple_call (alloc_stmt))
744 alloc_res = gimple_get_lhs (alloc_stmt);
746 if (TREE_CODE (alloc_res) != SSA_NAME)
749 if (!single_imm_use (alloc_res, &use_p, &final_stmt))
755 /* This function returns true if STMT is one of allocation
756 sites of function FN_DECL. It returns false otherwise. */
759 is_part_of_malloc (gimple stmt, tree fn_decl)
761 fallocs_t fallocs = get_fallocs (fn_decl);
768 for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
769 if (call->stmt == stmt
770 || get_final_alloc_stmt (call->stmt) == stmt)
776 /* Auxiliary structure for a lookup over field accesses. */
777 struct find_stmt_data
783 /* This function looks for DATA->stmt among
784 the statements involved in the field access,
785 defined by SLOT. It stops when it's found. */
788 find_in_field_accs (void **slot, void *data)
790 struct field_access_site *f_acc = *(struct field_access_site **) slot;
791 gimple stmt = ((struct find_stmt_data *)data)->stmt;
793 if (f_acc->stmt == stmt
794 || f_acc->ref_def_stmt == stmt
795 || f_acc->cast_stmt == stmt)
797 ((struct find_stmt_data *)data)->found = true;
804 /* This function checks whether STMT is part of field
805 accesses of structure STR. It returns true, if found,
806 and false otherwise. */
809 is_part_of_field_access (gimple stmt, d_str str)
813 for (i = 0; i < str->num_fields; i++)
815 struct find_stmt_data data;
819 if (str->fields[i].acc_sites)
820 htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
829 /* Auxiliary data for exclude_from_accs function. */
837 /* This function returns component_ref with the BASE and
838 field named FIELD_ID from structure TYPE. */
841 build_comp_ref (tree base, tree field_id, tree type)
847 /* Find field of structure type with the same name as field_id. */
848 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
850 if (DECL_NAME (field) == field_id)
859 return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
863 /* This struct represent data used for walk_tree
864 called from function find_pos_in_stmt.
865 - ref is a tree to be found,
866 - and pos is a pointer that points to ref in stmt. */
875 /* This is a callback function for walk_tree, called from
876 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
877 When *TP is equal to DATA->ref, the walk_tree stops,
878 and found position, equal to TP, is assigned to DATA->pos. */
881 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
883 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
884 struct ref_pos *r_pos = (struct ref_pos *) wi->info;
885 tree ref = r_pos->ref;
888 if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref))
894 r_pos->container = t;
900 /* This function looks for the pointer of REF in STMT,
901 It returns it, if found, and NULL otherwise. */
904 find_pos_in_stmt (gimple stmt, tree ref, struct ref_pos * r_pos)
906 struct walk_stmt_info wi;
910 r_pos->container = NULL_TREE;
911 memset (&wi, 0, sizeof (wi));
913 walk_gimple_op (stmt, find_pos_in_stmt_1, &wi);
918 /* This structure is used to represent array
919 or pointer-to wrappers of structure type.
920 For example, if type1 is structure type,
921 then for type1 ** we generate two type_wrapper
922 structures with wrap = 0 each one.
923 It's used to unwind the original type up to
924 structure type, replace it with the new structure type
925 and wrap it back in the opposite order. */
927 typedef struct type_wrapper
929 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
932 /* Relevant for arrays as domain or index. */
936 DEF_VEC_O (type_wrapper_t);
937 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
939 /* This function replace field access ACC by the new
940 field access of structure type NEW_TYPE. */
943 replace_field_acc (struct field_access_site *acc, tree new_type)
945 tree ref_var = acc->ref;
950 tree field_id = DECL_NAME (acc->field_decl);
951 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
952 type_wrapper_t *wr_p = NULL;
953 struct ref_pos r_pos;
955 while (TREE_CODE (ref_var) == INDIRECT_REF
956 || TREE_CODE (ref_var) == ARRAY_REF)
960 if ( TREE_CODE (ref_var) == INDIRECT_REF)
968 wr.domain = TREE_OPERAND (ref_var, 1);
971 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
972 ref_var = TREE_OPERAND (ref_var, 0);
975 new_ref = find_new_var_of_type (ref_var, new_type);
976 finalize_global_creation (new_ref);
978 while (VEC_length (type_wrapper_t, wrapper) != 0)
980 tree type = TREE_TYPE (TREE_TYPE (new_ref));
982 wr_p = VEC_last (type_wrapper_t, wrapper);
983 if (wr_p->wrap) /* Array. */
984 new_ref = build4 (ARRAY_REF, type, new_ref,
985 wr_p->domain, NULL_TREE, NULL_TREE);
987 new_ref = build1 (INDIRECT_REF, type, new_ref);
988 VEC_pop (type_wrapper_t, wrapper);
991 new_acc = build_comp_ref (new_ref, field_id, new_type);
992 VEC_free (type_wrapper_t, heap, wrapper);
994 if (is_gimple_assign (acc->stmt))
996 lhs = gimple_assign_lhs (acc->stmt);
997 rhs = gimple_assign_rhs1 (acc->stmt);
999 if (lhs == acc->comp_ref)
1000 gimple_assign_set_lhs (acc->stmt, new_acc);
1001 else if (rhs == acc->comp_ref)
1002 gimple_assign_set_rhs1 (acc->stmt, new_acc);
1005 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos);
1012 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos);
1017 finalize_stmt (acc->stmt);
1020 /* This function replace field access ACC by a new field access
1021 of structure type NEW_TYPE. */
1024 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1027 if (TREE_CODE (acc->ref) == INDIRECT_REF
1028 ||TREE_CODE (acc->ref) == ARRAY_REF
1029 ||TREE_CODE (acc->ref) == VAR_DECL)
1030 replace_field_acc (acc, new_type);
1035 /* This function looks for d_str, represented by TYPE, in the structures
1036 vector. If found, it returns an index of found structure. Otherwise
1037 it returns a length of the structures vector. */
1040 find_structure (tree type)
1045 type = TYPE_MAIN_VARIANT (type);
1047 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1048 if (is_equal_types (str->decl, type))
1051 return VEC_length (structure, structures);
1054 /* In this function we create new statements that have the same
1055 form as ORIG_STMT, but of type NEW_TYPE. The statements
1056 treated by this function are simple assignments,
1057 like assignments: p.8_7 = p; or statements with rhs of
1058 tree codes PLUS_EXPR and MINUS_EXPR. */
1061 create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset)
1066 tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1068 lhs = gimple_assign_lhs (orig_stmt);
1070 gcc_assert (TREE_CODE (lhs) == VAR_DECL
1071 || TREE_CODE (lhs) == SSA_NAME);
1073 new_lhs = find_new_var_of_type (lhs, new_type);
1074 gcc_assert (new_lhs);
1075 finalize_var_creation (new_lhs);
1077 switch (gimple_assign_rhs_code (orig_stmt))
1081 case POINTER_PLUS_EXPR:
1083 tree op0 = gimple_assign_rhs1 (orig_stmt);
1084 tree op1 = gimple_assign_rhs2 (orig_stmt);
1085 unsigned str0, str1;
1086 unsigned length = VEC_length (structure, structures);
1089 str0 = find_structure (strip_type (get_type_of_var (op0)));
1090 str1 = find_structure (strip_type (get_type_of_var (op1)));
1091 gcc_assert ((str0 != length) || (str1 != length));
1094 new_op0 = find_new_var_of_type (op0, new_type);
1096 new_op1 = find_new_var_of_type (op1, new_type);
1109 new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt),
1110 new_lhs, new_op0, new_op1);
1111 finalize_stmt (new_stmt);
1116 /* Given a field access F_ACC of the FIELD, this function
1117 replaces it by the new field access. */
1120 create_new_field_access (struct field_access_site *f_acc,
1121 struct field_entry field)
1123 tree new_type = field.field_mapping;
1128 tree cast_res = NULL;
1132 mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1133 insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1136 if (f_acc->cast_stmt)
1138 cast_stmt = gen_cast_stmt (size_res, new_type,
1139 f_acc->cast_stmt, &cast_res);
1140 insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1143 if (f_acc->ref_def_stmt)
1151 new_stmt = create_base_plus_offset (f_acc->ref_def_stmt,
1153 insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1156 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1157 D.2162_18 by an appropriate variable of new_type type. */
1158 replace_field_access_stmt (f_acc, new_type);
1161 /* This function creates a new condition statement
1162 corresponding to the original COND_STMT, adds new basic block
1163 and redirects condition edges. NEW_VAR is a new condition
1164 variable located in the condition statement at the position POS. */
1167 create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos)
1170 edge true_e = NULL, false_e = NULL;
1172 gimple_stmt_iterator si;
1174 extract_true_false_edges_from_block (gimple_bb (cond_stmt),
1177 new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1178 pos == 0 ? new_var : gimple_cond_lhs (cond_stmt),
1179 pos == 1 ? new_var : gimple_cond_rhs (cond_stmt),
1183 finalize_stmt (new_stmt);
1185 /* Create new basic block after bb. */
1186 new_bb = create_empty_bb (gimple_bb (cond_stmt));
1188 /* Add new condition stmt to the new_bb. */
1189 si = gsi_start_bb (new_bb);
1190 gsi_insert_after (&si, new_stmt, GSI_NEW_STMT);
1192 /* Create false and true edges from new_bb. */
1193 make_edge_and_fix_phis_of_dest (new_bb, true_e);
1194 make_edge_and_fix_phis_of_dest (new_bb, false_e);
1196 /* Redirect one of original edges to point to new_bb. */
1197 if (gimple_cond_code (cond_stmt) == NE_EXPR)
1198 redirect_edge_succ (true_e, new_bb);
1200 redirect_edge_succ (false_e, new_bb);
1203 /* This function creates new condition statements corresponding
1204 to original condition STMT, one for each new type, and
1205 recursively redirect edges to newly generated basic blocks. */
1208 create_new_stmts_for_cond_expr (gimple stmt)
1210 tree arg0, arg1, arg;
1211 unsigned str0, str1;
1217 unsigned length = VEC_length (structure, structures);
1219 gcc_assert (gimple_cond_code (stmt) == EQ_EXPR
1220 || gimple_cond_code (stmt) == NE_EXPR);
1222 arg0 = gimple_cond_lhs (stmt);
1223 arg1 = gimple_cond_rhs (stmt);
1225 str0 = find_structure (strip_type (get_type_of_var (arg0)));
1226 str1 = find_structure (strip_type (get_type_of_var (arg1)));
1228 s0 = (str0 != length) ? true : false;
1229 s1 = (str1 != length) ? true : false;
1231 gcc_assert (s0 || s1);
1232 /* For now we allow only comparison with 0 or NULL. */
1233 gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1235 str = integer_zerop (arg0) ?
1236 VEC_index (structure, structures, str1):
1237 VEC_index (structure, structures, str0);
1238 arg = integer_zerop (arg0) ? arg1 : arg0;
1239 pos = integer_zerop (arg0) ? 1 : 0;
1241 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1245 new_arg = find_new_var_of_type (arg, type);
1246 create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1250 /* This function looks for VAR in STMT, and replace it with NEW_VAR.
1251 If needed, it wraps NEW_VAR in pointers and indirect references
1252 before insertion. */
1255 insert_new_var_in_stmt (gimple stmt, tree var, tree new_var)
1257 struct ref_pos r_pos;
1260 pos = find_pos_in_stmt (stmt, var, &r_pos);
1263 while (r_pos.container && (TREE_CODE(r_pos.container) == INDIRECT_REF
1264 || TREE_CODE(r_pos.container) == ADDR_EXPR))
1266 tree type = TREE_TYPE (TREE_TYPE (new_var));
1268 if (TREE_CODE(r_pos.container) == INDIRECT_REF)
1269 new_var = build1 (INDIRECT_REF, type, new_var);
1271 new_var = build_fold_addr_expr (new_var);
1272 pos = find_pos_in_stmt (stmt, r_pos.container, &r_pos);
1279 /* Create a new general access to replace original access ACC
1280 for structure type NEW_TYPE. */
1283 create_general_new_stmt (struct access_site *acc, tree new_type)
1285 gimple old_stmt = acc->stmt;
1287 gimple new_stmt = gimple_copy (old_stmt);
1290 /* We are really building a new stmt, clear the virtual operands. */
1291 if (gimple_has_mem_ops (new_stmt))
1293 gimple_set_vuse (new_stmt, NULL_TREE);
1294 gimple_set_vdef (new_stmt, NULL_TREE);
1297 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1299 tree new_var = find_new_var_of_type (var, new_type);
1300 tree lhs, rhs = NULL_TREE;
1302 gcc_assert (new_var);
1303 finalize_var_creation (new_var);
1305 if (is_gimple_assign (new_stmt))
1307 lhs = gimple_assign_lhs (new_stmt);
1309 if (TREE_CODE (lhs) == SSA_NAME)
1310 lhs = SSA_NAME_VAR (lhs);
1311 if (gimple_assign_rhs_code (new_stmt) == SSA_NAME)
1312 rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt));
1314 /* It can happen that rhs is a constructor.
1315 Then we have to replace it to be of new_type. */
1316 if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR)
1318 /* Dealing only with empty constructors right now. */
1319 gcc_assert (VEC_empty (constructor_elt,
1320 CONSTRUCTOR_ELTS (rhs)));
1321 rhs = build_constructor (new_type, 0);
1322 gimple_assign_set_rhs1 (new_stmt, rhs);
1326 gimple_assign_set_lhs (new_stmt, new_var);
1327 else if (rhs == var)
1328 gimple_assign_set_rhs1 (new_stmt, new_var);
1330 insert_new_var_in_stmt (new_stmt, var, new_var);
1333 insert_new_var_in_stmt (new_stmt, var, new_var);
1336 finalize_stmt (new_stmt);
1340 /* For each new type in STR this function creates new general accesses
1341 corresponding to the original access ACC. */
1344 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1347 gimple stmt = acc->stmt;
1350 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1354 new_stmt = create_general_new_stmt (acc, type);
1355 insert_after_stmt (stmt, new_stmt);
1359 /* This function creates a new general access of structure STR
1360 to replace the access ACC. */
1363 create_new_general_access (struct access_site *acc, d_str str)
1365 gimple stmt = acc->stmt;
1366 switch (gimple_code (stmt))
1369 create_new_stmts_for_cond_expr (stmt);
1373 create_new_stmts_for_general_acc (acc, str);
1377 /* Auxiliary data for creation of accesses. */
1378 struct create_acc_data
1385 /* This function creates a new general access, defined by SLOT.
1386 DATA is a pointer to create_acc_data structure. */
1389 create_new_acc (void **slot, void *data)
1391 struct access_site *acc = *(struct access_site **) slot;
1392 basic_block bb = ((struct create_acc_data *)data)->bb;
1393 d_str str = ((struct create_acc_data *)data)->str;
1395 if (gimple_bb (acc->stmt) == bb)
1396 create_new_general_access (acc, str);
1400 /* This function creates a new field access, defined by SLOT.
1401 DATA is a pointer to create_acc_data structure. */
1404 create_new_field_acc (void **slot, void *data)
1406 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1407 basic_block bb = ((struct create_acc_data *)data)->bb;
1408 d_str str = ((struct create_acc_data *)data)->str;
1409 int i = ((struct create_acc_data *)data)->field_index;
1411 if (gimple_bb (f_acc->stmt) == bb)
1412 create_new_field_access (f_acc, str->fields[i]);
1416 /* This function creates new accesses for the structure
1417 type STR in basic block BB. */
1420 create_new_accs_for_struct (d_str str, basic_block bb)
1423 struct create_acc_data dt;
1427 dt.field_index = -1;
1429 for (i = 0; i < str->num_fields; i++)
1433 if (str->fields[i].acc_sites)
1434 htab_traverse (str->fields[i].acc_sites,
1435 create_new_field_acc, &dt);
1438 htab_traverse (str->accs, create_new_acc, &dt);
1441 /* This function inserts new variables from new_var,
1442 defined by SLOT, into varpool. */
1445 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1447 new_var n_var = *(new_var *) slot;
1451 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1452 insert_global_to_varpool (var);
1456 /* This function prints a field access site, defined by SLOT. */
1459 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1461 struct field_access_site *f_acc =
1462 *(struct field_access_site **) slot;
1464 fprintf(dump_file, "\n");
1466 print_gimple_stmt (dump_file, f_acc->stmt, 0, 0);
1467 if (f_acc->ref_def_stmt)
1468 print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0);
1469 if (f_acc->cast_stmt)
1470 print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0);
1474 /* Print field accesses from hashtable F_ACCS. */
1477 dump_field_acc_sites (htab_t f_accs)
1483 htab_traverse (f_accs, dump_field_acc, NULL);
1486 /* Hash value for fallocs_t. */
1489 malloc_hash (const void *x)
1491 return htab_hash_pointer (((const_fallocs_t)x)->func);
1494 /* This function returns nonzero if function of func_alloc_sites' X
1498 malloc_eq (const void *x, const void *y)
1500 return ((const_fallocs_t)x)->func == (const_tree)y;
1503 /* This function is a callback for traversal over a structure accesses.
1504 It frees an access represented by SLOT. */
1507 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1509 struct access_site * acc = *(struct access_site **) slot;
1511 VEC_free (tree, heap, acc->vars);
1516 /* This is a callback function for traversal over field accesses.
1517 It frees a field access represented by SLOT. */
1520 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1522 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1528 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1529 if it is not there yet. */
1532 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1540 type = TYPE_MAIN_VARIANT (type);
1542 for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1543 if (is_equal_types (t, type))
1546 if (i == VEC_length (tree, *unsuitable_types))
1547 VEC_safe_push (tree, heap, *unsuitable_types, type);
1550 /* Given a type TYPE, this function returns the name of the type. */
1553 get_type_name (tree type)
1555 if (! TYPE_NAME (type))
1558 if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1559 return IDENTIFIER_POINTER (TYPE_NAME (type));
1560 else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1561 && DECL_NAME (TYPE_NAME (type)))
1562 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1567 /* This function is a temporary hack to overcome the types problem.
1568 When several compilation units are compiled together
1569 with -combine, the TYPE_MAIN_VARIANT of the same type
1570 can appear differently in different compilation units.
1571 Therefore this function first compares type names.
1572 If there are no names, structure bodies are recursively
1576 is_equal_types (tree type1, tree type2)
1578 const char * name1,* name2;
1580 if ((!type1 && type2)
1581 ||(!type2 && type1))
1584 if (!type1 && !type2)
1587 if (TREE_CODE (type1) != TREE_CODE (type2))
1593 if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1596 name1 = get_type_name (type1);
1597 name2 = get_type_name (type2);
1599 if (name1 && name2 && !strcmp (name1, name2))
1602 if (name1 && name2 && strcmp (name1, name2))
1605 switch (TREE_CODE (type1))
1608 case REFERENCE_TYPE:
1610 return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1616 case QUAL_UNION_TYPE:
1620 /* Compare fields of structure. */
1621 for (field1 = TYPE_FIELDS (type1); field1;
1622 field1 = TREE_CHAIN (field1))
1624 tree field2 = find_field_in_struct_1 (type2, field1);
1634 if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1635 && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1643 tree max1, min1, max2, min2;
1645 if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1648 d1 = TYPE_DOMAIN (type1);
1649 d2 = TYPE_DOMAIN (type2);
1654 max1 = TYPE_MAX_VALUE (d1);
1655 max2 = TYPE_MAX_VALUE (d2);
1656 min1 = TYPE_MIN_VALUE (d1);
1657 min2 = TYPE_MIN_VALUE (d2);
1659 if (max1 && max2 && min1 && min2
1660 && TREE_CODE (max1) == TREE_CODE (max2)
1661 && TREE_CODE (max1) == INTEGER_CST
1662 && TREE_CODE (min1) == TREE_CODE (min2)
1663 && TREE_CODE (min1) == INTEGER_CST
1664 && tree_int_cst_equal (max1, max2)
1665 && tree_int_cst_equal (min1, min2))
1677 /* This function free non-field accesses from hashtable ACCS. */
1680 free_accesses (htab_t accs)
1683 htab_traverse (accs, free_accs, NULL);
1687 /* This function free field accesses hashtable F_ACCS. */
1690 free_field_accesses (htab_t f_accs)
1693 htab_traverse (f_accs, free_field_accs, NULL);
1694 htab_delete (f_accs);
1697 /* Update call graph with new edge generated by new MALLOC_STMT.
1698 The edge origin is CONTEXT function. */
1701 update_cgraph_with_malloc_call (gimple malloc_stmt, tree context)
1703 struct cgraph_node *src, *dest;
1704 tree malloc_fn_decl;
1709 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1711 src = cgraph_node (context);
1712 dest = cgraph_node (malloc_fn_decl);
1713 cgraph_create_edge (src, dest, malloc_stmt,
1714 gimple_bb (malloc_stmt)->count,
1715 compute_call_stmt_bb_frequency
1716 (context, gimple_bb (malloc_stmt)),
1717 gimple_bb (malloc_stmt)->loop_depth);
1720 /* This function generates set of statements required
1721 to allocate number NUM of structures of type NEW_TYPE.
1722 The statements are stored in NEW_STMTS. The statement that contain
1723 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1726 create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts,
1729 tree new_malloc_size;
1730 tree malloc_fn_decl;
1733 gimple call_stmt, final_stmt;
1736 gcc_assert (num && malloc_stmt && new_type);
1737 *new_stmts = gimple_seq_alloc ();
1739 /* Generate argument to malloc as multiplication of num
1740 and size of new_type. */
1741 new_stmt = gen_size (num, new_type, &new_malloc_size);
1742 gimple_seq_add_stmt (new_stmts, new_stmt);
1744 /* Generate new call for malloc. */
1745 malloc_res = create_tmp_var (ptr_type_node, NULL);
1746 add_referenced_var (malloc_res);
1748 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1749 call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size);
1750 gimple_call_set_lhs (call_stmt, malloc_res);
1751 finalize_stmt_and_append (new_stmts, call_stmt);
1753 /* Create new cast statement. */
1754 final_stmt = get_final_alloc_stmt (malloc_stmt);
1755 gcc_assert (final_stmt);
1756 new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1757 gimple_seq_add_stmt (new_stmts, new_stmt);
1762 /* This function returns a tree representing
1763 the number of instances of structure STR_DECL allocated
1764 by allocation STMT. If new statements are generated,
1765 they are filled into NEW_STMTS_P. */
1768 gen_num_of_structs_in_malloc (gimple stmt, tree str_decl,
1769 gimple_seq *new_stmts_p)
1773 HOST_WIDE_INT struct_size_int;
1778 /* Get malloc argument. */
1779 if (!is_gimple_call (stmt))
1782 arg = gimple_call_arg (stmt, 0);
1784 if (TREE_CODE (arg) != SSA_NAME
1785 && !TREE_CONSTANT (arg))
1788 struct_size = TYPE_SIZE_UNIT (str_decl);
1789 struct_size_int = TREE_INT_CST_LOW (struct_size);
1791 gcc_assert (struct_size);
1793 if (TREE_CODE (arg) == SSA_NAME)
1798 if (is_result_of_mult (arg, &num, struct_size))
1801 num = create_tmp_var (integer_type_node, NULL);
1804 add_referenced_var (num);
1806 if (exact_log2 (struct_size_int) == -1)
1807 div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg,
1811 tree C = build_int_cst (integer_type_node,
1812 exact_log2 (struct_size_int));
1814 div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C);
1816 gimple_seq_add_stmt (new_stmts_p, div_stmt);
1817 finalize_stmt (div_stmt);
1821 if (CONSTANT_CLASS_P (arg)
1822 && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))
1823 return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1828 /* This function is a callback for traversal on new_var's hashtable.
1829 SLOT is a pointer to new_var. This function prints to dump_file
1830 an original variable and all new variables from the new_var
1831 pointed by *SLOT. */
1834 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1836 new_var n_var = *(new_var *) slot;
1841 var_type = get_type_of_var (n_var->orig_var);
1843 fprintf (dump_file, "\nOrig var: ");
1844 print_generic_expr (dump_file, n_var->orig_var, 0);
1845 fprintf (dump_file, " of type ");
1846 print_generic_expr (dump_file, var_type, 0);
1847 fprintf (dump_file, "\n");
1850 VEC_iterate (tree, n_var->new_vars, i, var); i++)
1852 var_type = get_type_of_var (var);
1854 fprintf (dump_file, " ");
1855 print_generic_expr (dump_file, var, 0);
1856 fprintf (dump_file, " of type ");
1857 print_generic_expr (dump_file, var_type, 0);
1858 fprintf (dump_file, "\n");
1863 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1866 copy_decl_attributes (tree new_decl, tree orig_decl)
1869 DECL_ARTIFICIAL (new_decl) = 1;
1870 DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1871 TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1872 TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1873 TREE_USED (new_decl) = TREE_USED (orig_decl);
1874 DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1875 TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1876 TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1878 if (TREE_CODE (orig_decl) == VAR_DECL)
1880 TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1881 DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1885 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1886 the same way as a structure type is wrapped in DECL.
1887 It returns the generated type. */
1890 gen_struct_type (tree decl, tree new_str_type)
1892 tree type_orig = get_type_of_var (decl);
1893 tree new_type = new_str_type;
1894 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1896 type_wrapper_t *wr_p;
1898 while (POINTER_TYPE_P (type_orig)
1899 || TREE_CODE (type_orig) == ARRAY_TYPE)
1901 if (POINTER_TYPE_P (type_orig))
1904 wr.domain = NULL_TREE;
1908 gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1910 wr.domain = TYPE_DOMAIN (type_orig);
1912 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1913 type_orig = TREE_TYPE (type_orig);
1916 while (VEC_length (type_wrapper_t, wrapper) != 0)
1918 wr_p = VEC_last (type_wrapper_t, wrapper);
1920 if (wr_p->wrap) /* Array. */
1921 new_type = build_array_type (new_type, wr_p->domain);
1923 new_type = build_pointer_type (new_type);
1925 VEC_pop (type_wrapper_t, wrapper);
1928 VEC_free (type_wrapper_t, heap, wrapper);
1932 /* This function generates and returns new variable name based on
1933 ORIG_DECL name, combined with index I.
1934 The form of the new name is <orig_name>.<I> . */
1937 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1939 const char *old_name;
1943 if (!DECL_NAME (orig_decl)
1944 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1947 /* If the original variable has a name, create an
1948 appropriate new name for the new variable. */
1950 old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1951 prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1952 strcpy (prefix, old_name);
1953 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1954 return get_identifier (new_name);
1957 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1960 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1964 slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1965 htab_hash_pointer (new_node->orig_var),
1970 /* This function creates and returns new_var_data node
1971 with empty new_vars and orig_var equal to VAR. */
1974 create_new_var_node (tree var, d_str str)
1978 node = (new_var) xmalloc (sizeof (struct new_var_data));
1979 node->orig_var = var;
1980 node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1984 /* Check whether the type of VAR is potential candidate for peeling.
1985 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1986 candidate type. If VAR is initialized, the type of VAR will be added
1987 to UNSUITABLE_TYPES. */
1990 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1993 bool initialized = false;
2000 /* There is no support of initialized vars. */
2001 if (TREE_CODE (var) == VAR_DECL
2002 && DECL_INITIAL (var) != NULL_TREE)
2005 type = get_type_of_var (var);
2009 type = TYPE_MAIN_VARIANT (strip_type (type));
2010 if (TREE_CODE (type) != RECORD_TYPE)
2014 if (initialized && unsuitable_types && *unsuitable_types)
2018 fprintf (dump_file, "The type ");
2019 print_generic_expr (dump_file, type, 0);
2020 fprintf (dump_file, " is initialized...Excluded.");
2022 add_unsuitable_type (unsuitable_types, type);
2032 /* Hash value for field_access_site. */
2035 field_acc_hash (const void *x)
2037 return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2040 /* This function returns nonzero if stmt of field_access_site X
2044 field_acc_eq (const void *x, const void *y)
2046 return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2049 /* This function prints an access site, defined by SLOT. */
2052 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2054 struct access_site *acc = *(struct access_site **) slot;
2058 fprintf(dump_file, "\n");
2060 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2061 fprintf(dump_file, " : ");
2063 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2065 print_generic_expr (dump_file, var, 0);
2066 fprintf(dump_file, ", ");
2071 /* This function frees memory allocated for structure clusters,
2072 starting from CLUSTER. */
2075 free_struct_cluster (struct field_cluster* cluster)
2079 if (cluster->fields_in_cluster)
2080 sbitmap_free (cluster->fields_in_cluster);
2081 if (cluster->sibling)
2082 free_struct_cluster (cluster->sibling);
2087 /* Free all allocated memory under the structure node pointed by D_NODE. */
2090 free_data_struct (d_str d_node)
2099 fprintf (dump_file, "\nRemoving data structure \"");
2100 print_generic_expr (dump_file, d_node->decl, 0);
2101 fprintf (dump_file, "\" from data_struct_list.");
2104 /* Free all space under d_node. */
2107 for (i = 0; i < d_node->num_fields; i++)
2108 free_field_accesses (d_node->fields[i].acc_sites);
2109 free (d_node->fields);
2113 free_accesses (d_node->accs);
2115 if (d_node->struct_clustering)
2116 free_struct_cluster (d_node->struct_clustering);
2118 if (d_node->new_types)
2119 VEC_free (tree, heap, d_node->new_types);
2122 /* This function creates new general and field accesses in BB. */
2125 create_new_accesses_in_bb (basic_block bb)
2130 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2131 create_new_accs_for_struct (str, bb);
2134 /* This function adds allocation sites for peeled structures.
2135 M_DATA is vector of allocation sites of function CONTEXT. */
2138 create_new_alloc_sites (fallocs_t m_data, tree context)
2143 for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2145 gimple stmt = call->stmt;
2146 d_str str = call->str;
2148 gimple_seq new_stmts = NULL;
2149 gimple last_stmt = get_final_alloc_stmt (stmt);
2153 num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2156 gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2157 insert_seq_after_stmt (last_stmt, new_stmts);
2158 last_stmt = last_stmt_tmp;
2161 /* Generate an allocation sites for each new structure type. */
2162 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
2164 gimple new_malloc_stmt = NULL;
2165 gimple last_stmt_tmp = NULL;
2168 new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2169 last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2170 insert_seq_after_stmt (last_stmt, new_stmts);
2171 update_cgraph_with_malloc_call (new_malloc_stmt, context);
2172 last_stmt = last_stmt_tmp;
2177 /* This function prints new variables from hashtable
2178 NEW_VARS_HTAB to dump_file. */
2181 dump_new_vars (htab_t new_vars_htab)
2187 htab_traverse (new_vars_htab, dump_new_var, NULL);
2190 /* Given an original variable ORIG_DECL of structure type STR,
2191 this function generates new variables of the types defined
2192 by STR->new_type. Generated types are saved in new_var node NODE.
2193 ORIG_DECL should has VAR_DECL tree_code. */
2196 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2202 VEC_iterate (tree, str->new_types, i, type); i++)
2204 tree new_decl = NULL;
2207 new_name = gen_var_name (orig_decl, i);
2208 type = gen_struct_type (orig_decl, type);
2210 if (is_global_var (orig_decl))
2211 new_decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
2212 VAR_DECL, new_name, type);
2215 const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2216 new_decl = create_tmp_var (type, name);
2219 copy_decl_attributes (new_decl, orig_decl);
2220 VEC_safe_push (tree, heap, node->new_vars, new_decl);
2224 /* This function creates new variables to
2225 substitute the original variable VAR_DECL and adds
2226 them to the new_var's hashtable NEW_VARS_HTAB. */
2229 create_new_var (tree var_decl, htab_t new_vars_htab)
2236 if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2239 if (!is_candidate (var_decl, &type, NULL))
2242 i = find_structure (type);
2243 if (i == VEC_length (structure, structures))
2246 str = VEC_index (structure, structures, i);
2247 node = create_new_var_node (var_decl, str);
2248 create_new_var_1 (var_decl, str, node);
2249 add_to_new_vars_htab (node, new_vars_htab);
2252 /* Hash value for new_var. */
2255 new_var_hash (const void *x)
2257 return htab_hash_pointer (((const_new_var)x)->orig_var);
2260 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2263 new_var_eq (const void *x, const void *y)
2265 return ((const_new_var)x)->orig_var == (const_tree)y;
2268 /* This function check whether a structure type represented by STR
2269 escapes due to ipa-type-escape analysis. If yes, this type is added
2270 to UNSUITABLE_TYPES vector. */
2273 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2275 tree type = str->decl;
2277 if (!ipa_type_escape_type_contained_p (type))
2281 fprintf (dump_file, "\nEscaping type is ");
2282 print_generic_expr (dump_file, type, 0);
2284 add_unsuitable_type (unsuitable_types, type);
2288 /* Hash value for access_site. */
2291 acc_hash (const void *x)
2293 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2296 /* Return nonzero if stmt of access_site X is equal to Y. */
2299 acc_eq (const void *x, const void *y)
2301 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2304 /* Given a structure declaration STRUCT_DECL, and number of fields
2305 in the structure NUM_FIELDS, this function creates and returns
2306 corresponding field_entry's. */
2308 static struct field_entry *
2309 get_fields (tree struct_decl, int num_fields)
2311 struct field_entry *list;
2312 tree t = TYPE_FIELDS (struct_decl);
2316 (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2318 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2319 if (TREE_CODE (t) == FIELD_DECL)
2321 list[idx].index = idx;
2323 list[idx].acc_sites =
2324 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2325 list[idx].count = 0;
2326 list[idx].field_mapping = NULL_TREE;
2332 /* Print non-field accesses from hashtable ACCS of structure. */
2335 dump_access_sites (htab_t accs)
2341 htab_traverse (accs, dump_acc, NULL);
2344 /* This function is a callback for alloc_sites hashtable
2345 traversal. SLOT is a pointer to fallocs_t. This function
2346 removes all allocations of the structure defined by DATA. */
2349 remove_str_allocs_in_func (void **slot, void *data)
2351 fallocs_t fallocs = *(fallocs_t *) slot;
2355 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2357 if (call->str == (d_str) data)
2358 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2366 /* This function remove all entries corresponding to the STR structure
2367 from alloc_sites hashtable. */
2370 remove_str_allocs (d_str str)
2376 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2379 /* This function removes the structure with index I from structures vector. */
2382 remove_structure (unsigned i)
2386 if (i >= VEC_length (structure, structures))
2389 str = VEC_index (structure, structures, i);
2391 /* Before removing the structure str, we have to remove its
2392 allocations from alloc_sites hashtable. */
2393 remove_str_allocs (str);
2394 free_data_struct (str);
2395 VEC_ordered_remove (structure, structures, i);
2398 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2399 COND_STMT is a condition statement to check. */
2402 is_safe_cond_expr (gimple cond_stmt)
2405 unsigned str0, str1;
2407 unsigned length = VEC_length (structure, structures);
2409 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2410 && gimple_cond_code (cond_stmt) != NE_EXPR)
2413 arg0 = gimple_cond_lhs (cond_stmt);
2414 arg1 = gimple_cond_rhs (cond_stmt);
2416 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2417 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2419 s0 = (str0 != length) ? true : false;
2420 s1 = (str1 != length) ? true : false;
2425 /* For now we allow only comparison with 0 or NULL. */
2426 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2432 /* This function excludes statements, that are
2433 part of allocation sites or field accesses, from the
2434 hashtable of general accesses. SLOT represents general
2435 access that will be checked. DATA is a pointer to
2436 exclude_data structure. */
2439 exclude_from_accs (void **slot, void *data)
2441 struct access_site *acc = *(struct access_site **) slot;
2442 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2443 d_str str = ((struct exclude_data *)data)->str;
2445 if (is_part_of_malloc (acc->stmt, fn_decl)
2446 || is_part_of_field_access (acc->stmt, str))
2448 VEC_free (tree, heap, acc->vars);
2450 htab_clear_slot (str->accs, slot);
2455 /* Callback function for walk_tree called from collect_accesses_in_bb
2456 function. DATA is the statement which is analyzed. */
2459 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2461 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2462 gimple stmt = (gimple) wi->info;
2468 switch (TREE_CODE (t))
2472 tree var = TREE_OPERAND(t, 0);
2473 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2474 unsigned i = find_structure (type);
2476 if (i != VEC_length (structure, structures))
2480 fprintf (dump_file, "\nThe type ");
2481 print_generic_expr (dump_file, type, 0);
2482 fprintf (dump_file, " has bitfield.");
2484 remove_structure (i);
2491 tree ref = TREE_OPERAND (t, 0);
2492 tree field_decl = TREE_OPERAND (t, 1);
2495 if ((TREE_CODE (ref) == INDIRECT_REF
2496 || TREE_CODE (ref) == ARRAY_REF
2497 || TREE_CODE (ref) == VAR_DECL)
2498 && TREE_CODE (field_decl) == FIELD_DECL)
2500 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2501 unsigned i = find_structure (type);
2503 if (i != VEC_length (structure, structures))
2505 d_str str = VEC_index (structure, structures, i);
2506 struct field_entry * field =
2507 find_field_in_struct (str, field_decl);
2511 struct field_access_site *acc = make_field_acc_node ();
2518 acc->field_decl = field_decl;
2520 /* Check whether the access is of the form
2521 we can deal with. */
2522 if (!decompose_access (str->decl, acc))
2526 fprintf (dump_file, "\nThe type ");
2527 print_generic_expr (dump_file, type, 0);
2529 " has complicate access in statement ");
2530 print_gimple_stmt (dump_file, stmt, 0, 0);
2533 remove_structure (i);
2538 /* Increase count of field. */
2539 basic_block bb = gimple_bb (stmt);
2540 field->count += bb->count;
2542 /* Add stmt to the acc_sites of field. */
2543 add_field_acc_to_acc_sites (acc, field->acc_sites);
2554 tree cond = COND_EXPR_COND (t);
2556 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2558 tree t = TREE_OPERAND (cond, i);
2561 walk_tree (&t, get_stmt_accesses, data, NULL);
2572 if (TREE_CODE (t) == SSA_NAME)
2573 t = SSA_NAME_VAR (t);
2575 i = find_structure (strip_type (get_type_of_var (t)));
2576 if (i != VEC_length (structure, structures))
2580 str = VEC_index (structure, structures, i);
2581 add_access_to_acc_sites (stmt, t, str->accs);
2594 /* Free structures hashtable. */
2597 free_structures (void)
2602 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2603 free_data_struct (str);
2605 VEC_free (structure, heap, structures);
2609 /* This function is a callback for traversal over new_var's hashtable.
2610 SLOT is a pointer to new_var. This function frees memory allocated
2611 for new_var and pointed by *SLOT. */
2614 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2616 new_var n_var = *(new_var *) slot;
2618 /* Free vector of new_vars. */
2619 VEC_free (tree, heap, n_var->new_vars);
2624 /* Free new_vars hashtable NEW_VARS_HTAB. */
2627 free_new_vars_htab (htab_t new_vars_htab)
2630 htab_traverse (new_vars_htab, free_new_var, NULL);
2631 htab_delete (new_vars_htab);
2632 new_vars_htab = NULL;
2635 /* This function creates new general and field accesses that appear in cfun. */
2638 create_new_accesses_for_func (void)
2642 FOR_EACH_BB_FN (bb, cfun)
2643 create_new_accesses_in_bb (bb);
2646 /* Create new allocation sites for the function represented by NODE. */
2649 create_new_alloc_sites_for_func (struct cgraph_node *node)
2651 fallocs_t fallocs = get_fallocs (node->decl);
2654 create_new_alloc_sites (fallocs, node->decl);
2657 /* For each local variable of structure type from the vector of structures
2658 this function generates new variable(s) to replace it. */
2661 create_new_local_vars (void)
2664 referenced_var_iterator rvi;
2666 new_local_vars = htab_create (num_referenced_vars,
2667 new_var_hash, new_var_eq, NULL);
2669 FOR_EACH_REFERENCED_VAR (var, rvi)
2671 if (!is_global_var (var))
2672 create_new_var (var, new_local_vars);
2676 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2677 dump_new_vars (new_local_vars);
2680 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2683 print_shift (unsigned HOST_WIDE_INT shift)
2685 unsigned HOST_WIDE_INT sh = shift;
2688 fprintf (dump_file, " ");
2691 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2694 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2695 struct field_entry * fields, int num_fields)
2699 for (i = 0; i < num_fields; i++)
2700 if (TEST_BIT (cluster->fields_in_cluster, i))
2701 fields[i].field_mapping = new_type;
2704 /* This functions builds structure with FIELDS,
2705 NAME and attributes similar to ORIG_STRUCT.
2706 It returns the newly created structure. */
2709 build_basic_struct (tree fields, tree name, tree orig_struct)
2711 tree attributes = NULL_TREE;
2715 if (TYPE_ATTRIBUTES (orig_struct))
2716 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2717 ref = make_node (RECORD_TYPE);
2718 TYPE_SIZE (ref) = 0;
2719 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2720 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2721 for (x = fields; x; x = TREE_CHAIN (x))
2723 DECL_CONTEXT (x) = ref;
2724 DECL_PACKED (x) |= TYPE_PACKED (ref);
2726 TYPE_FIELDS (ref) = fields;
2728 TYPE_NAME (ref) = name;
2733 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2734 of preparation for new structure building. NUM_FIELDS is a total
2735 number of fields in the structure. The function returns newly
2736 generated fields. */
2739 create_fields (struct field_cluster * cluster,
2740 struct field_entry * fields, int num_fields)
2743 tree new_types = NULL_TREE;
2744 tree last = NULL_TREE;
2746 for (i = 0; i < num_fields; i++)
2747 if (TEST_BIT (cluster->fields_in_cluster, i))
2749 tree new_decl = unshare_expr (fields[i].decl);
2752 new_types = new_decl;
2754 TREE_CHAIN (last) = new_decl;
2758 TREE_CHAIN (last) = NULL_TREE;
2763 /* This function creates a cluster name. The name is based on
2764 the original structure name, if it is present. It has a form:
2766 <original_struct_name>_sub.<CLUST_NUM>
2768 The original structure name is taken from the type of DECL.
2769 If an original structure name is not present, it's generated to be:
2773 The function returns identifier of the new cluster name. */
2776 gen_cluster_name (tree decl, int clust_num, int str_num)
2778 const char * orig_name = get_type_name (decl);
2779 char * tmp_name = NULL;
2785 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2787 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2788 prefix = XALLOCAVEC (char, len + 1);
2789 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2790 strlen (tmp_name ? tmp_name : orig_name));
2791 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2793 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2794 return get_identifier (new_name);
2797 /* This function checks whether the structure STR has bitfields.
2798 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2801 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2803 tree type = str->decl;
2806 for (i = 0; i < str->num_fields; i++)
2807 if (DECL_BIT_FIELD (str->fields[i].decl))
2809 add_unsuitable_type (unsuitable_types, type);
2812 fprintf (dump_file, "\nType ");
2813 print_generic_expr (dump_file, type, 0);
2814 fprintf (dump_file, "\nescapes due to bitfield ");
2815 print_generic_expr (dump_file, str->fields[i].decl, 0);
2821 /* This function adds to UNSUITABLE_TYPES those types that escape
2822 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2825 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2830 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2831 check_type_escape (str, unsuitable_types);
2834 /* If a structure type is a return type of any function,
2835 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2838 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2840 struct cgraph_node *c_node;
2842 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2844 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2848 ret_t = strip_type (ret_t);
2849 if (TREE_CODE (ret_t) == RECORD_TYPE)
2851 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2854 fprintf (dump_file, "\nThe type \"");
2855 print_generic_expr (dump_file, ret_t, 0);
2857 "\" is return type of function...Excluded.");
2864 /* This function looks for parameters of local functions
2865 which are of structure types, or derived from them (arrays
2866 of structures, pointers to structures, or their combinations).
2867 We are not handling peeling of such structures right now.
2868 The found structures types are added to UNSUITABLE_TYPES vector. */
2871 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2873 struct cgraph_node *c_node;
2875 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2876 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2878 tree fn = c_node->decl;
2881 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2883 tree type = TREE_TYPE (arg);
2885 type = strip_type (type);
2886 if (TREE_CODE (type) == RECORD_TYPE)
2888 add_unsuitable_type (unsuitable_types,
2889 TYPE_MAIN_VARIANT (type));
2892 fprintf (dump_file, "\nPointer to type \"");
2893 print_generic_expr (dump_file, type, 0);
2895 "\" is passed to local function...Excluded.");
2902 /* This function analyzes structure form of structures
2903 potential for transformation. If we are not capable to transform
2904 structure of some form, we remove it from the structures hashtable.
2905 Right now we cannot handle nested structs, when nesting is
2906 through any level of pointers or arrays.
2908 TBD: release these constrains in future.
2910 Note, that in this function we suppose that all structures
2911 in the program are members of the structures hashtable right now,
2912 without excluding escaping types. */
2915 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2919 for (i = 0; i < str->num_fields; i++)
2921 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2923 if (TREE_CODE (f_type) == RECORD_TYPE)
2925 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2926 add_unsuitable_type (unsuitable_types, str->decl);
2929 fprintf (dump_file, "\nType ");
2930 print_generic_expr (dump_file, f_type, 0);
2931 fprintf (dump_file, " is a field in the structure ");
2932 print_generic_expr (dump_file, str->decl, 0);
2933 fprintf (dump_file, ". Escaping...");
2939 /* This function adds a structure TYPE to the vector of structures,
2940 if it's not already there. */
2943 add_structure (tree type)
2945 struct data_structure node;
2949 type = TYPE_MAIN_VARIANT (type);
2951 i = find_structure (type);
2953 if (i != VEC_length (structure, structures))
2956 num_fields = fields_length (type);
2958 node.num_fields = num_fields;
2959 node.fields = get_fields (type, num_fields);
2960 node.struct_clustering = NULL;
2961 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2962 node.new_types = VEC_alloc (tree, heap, num_fields);
2965 VEC_safe_push (structure, heap, structures, &node);
2969 fprintf (dump_file, "\nAdding data structure \"");
2970 print_generic_expr (dump_file, type, 0);
2971 fprintf (dump_file, "\" to data_struct_list.");
2975 /* This function adds an allocation site to alloc_sites hashtable.
2976 The allocation site appears in STMT of function FN_DECL and
2977 allocates the structure represented by STR. */
2980 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2982 fallocs_t fallocs = NULL;
2983 alloc_site_t m_call;
2989 (fallocs_t) htab_find_with_hash (alloc_sites,
2990 fn_decl, htab_hash_pointer (fn_decl));
2996 fallocs = (fallocs_t)
2997 xmalloc (sizeof (struct func_alloc_sites));
2998 fallocs->func = fn_decl;
2999 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
3000 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
3001 htab_hash_pointer (fn_decl), INSERT);
3004 VEC_safe_push (alloc_site_t, heap,
3005 fallocs->allocs, &m_call);
3009 fprintf (dump_file, "\nAdding stmt ");
3010 print_gimple_stmt (dump_file, stmt, 0, 0);
3011 fprintf (dump_file, " to list of mallocs.");
3015 /* This function returns true if the result of STMT, that contains a call
3016 to an allocation function, is cast to one of the structure types.
3017 STMT should be of the form: T.2 = <alloc_func> (T.1);
3018 If true, I_P contains an index of an allocated structure.
3019 Otherwise I_P contains the length of the vector of structures. */
3022 is_alloc_of_struct (gimple stmt, unsigned *i_p)
3028 final_stmt = get_final_alloc_stmt (stmt);
3033 /* final_stmt should be of the form:
3034 T.3 = (struct_type *) T.2; */
3036 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3039 lhs = gimple_assign_lhs (final_stmt);
3041 type = get_type_of_var (lhs);
3046 if (!POINTER_TYPE_P (type)
3047 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3050 *i_p = find_structure (strip_type (type));
3052 if (*i_p == VEC_length (structure, structures))
3058 /* This function prints non-field and field accesses
3059 of the structure STR. */
3062 dump_accs (d_str str)
3066 fprintf (dump_file, "\nAccess sites of struct ");
3067 print_generic_expr (dump_file, str->decl, 0);
3069 for (i = 0; i < str->num_fields; i++)
3071 fprintf (dump_file, "\nAccess site of field ");
3072 print_generic_expr (dump_file, str->fields[i].decl, 0);
3073 dump_field_acc_sites (str->fields[i].acc_sites);
3074 fprintf (dump_file, ":\n");
3076 fprintf (dump_file, "\nGeneral access sites\n");
3077 dump_access_sites (str->accs);
3080 /* This function checks whether an access statement, pointed by SLOT,
3081 is a condition we are capable to transform. It returns false if not,
3082 setting bool *DATA to false. */
3085 safe_cond_expr_check (void **slot, void *data)
3087 struct access_site *acc = *(struct access_site **) slot;
3089 if (gimple_code (acc->stmt) == GIMPLE_COND
3090 && !is_safe_cond_expr (acc->stmt))
3094 fprintf (dump_file, "\nUnsafe conditional statement ");
3095 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3097 *(bool *) data = false;
3103 /* This function excludes statements that are part of allocation sites and
3104 field accesses from the hashtable of general accesses of the structure
3105 type STR. Only accesses that belong to the function represented by
3106 NODE are treated. */
3109 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3111 struct exclude_data dt;
3113 dt.fn_decl = node->decl;
3116 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3119 /* Collect accesses to the structure types that appear in basic block BB. */
3122 collect_accesses_in_bb (basic_block bb)
3124 gimple_stmt_iterator bsi;
3125 struct walk_stmt_info wi;
3127 memset (&wi, 0, sizeof (wi));
3129 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3131 gimple stmt = gsi_stmt (bsi);
3133 /* In asm stmt we cannot always track the arguments,
3134 so we just give up. */
3135 if (gimple_code (stmt) == GIMPLE_ASM)
3141 wi.info = (void *) stmt;
3142 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3146 /* This function generates cluster substructure that contains FIELDS.
3147 The cluster added to the set of clusters of the structure STR. */
3150 gen_cluster (sbitmap fields, d_str str)
3152 struct field_cluster *crr_cluster = NULL;
3155 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3156 crr_cluster->sibling = str->struct_clustering;
3157 str->struct_clustering = crr_cluster;
3158 crr_cluster->fields_in_cluster = fields;
3161 /* This function peels a field with the index I from the structure DS. */
3164 peel_field (int i, d_str ds)
3166 struct field_cluster *crr_cluster = NULL;
3169 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3170 crr_cluster->sibling = ds->struct_clustering;
3171 ds->struct_clustering = crr_cluster;
3172 crr_cluster->fields_in_cluster =
3173 sbitmap_alloc ((unsigned int) ds->num_fields);
3174 sbitmap_zero (crr_cluster->fields_in_cluster);
3175 SET_BIT (crr_cluster->fields_in_cluster, i);
3178 /* This function calculates maximum field count in
3179 the structure STR. */
3182 get_max_field_count (d_str str)
3187 for (i = 0; i < str->num_fields; i++)
3188 if (str->fields[i].count > max)
3189 max = str->fields[i].count;
3194 /* Do struct-reorg transformation for individual function
3195 represented by NODE. All structure types relevant
3196 for this function are transformed. */
3199 do_reorg_for_func (struct cgraph_node *node)
3201 create_new_local_vars ();
3202 create_new_alloc_sites_for_func (node);
3203 create_new_accesses_for_func ();
3204 update_ssa (TODO_update_ssa);
3205 cleanup_tree_cfg ();
3207 /* Free auxiliary data representing local variables. */
3208 free_new_vars_htab (new_local_vars);
3211 /* Print structure TYPE, its name, if it exists, and body.
3212 INDENT defines the level of indentation (similar
3213 to the option -i of indent command). SHIFT parameter
3214 defines a number of spaces by which a structure will
3215 be shifted right. */
3218 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3219 unsigned HOST_WIDE_INT shift)
3221 const char *struct_name;
3224 if (!type || !dump_file)
3227 if (TREE_CODE (type) != RECORD_TYPE)
3229 print_generic_expr (dump_file, type, 0);
3233 print_shift (shift);
3234 struct_name = get_type_name (type);
3235 fprintf (dump_file, "struct ");
3237 fprintf (dump_file, "%s\n",struct_name);
3238 print_shift (shift);
3239 fprintf (dump_file, "{\n");
3241 for (field = TYPE_FIELDS (type); field;
3242 field = TREE_CHAIN (field))
3244 unsigned HOST_WIDE_INT s = indent;
3245 tree f_type = TREE_TYPE (field);
3247 print_shift (shift);
3249 fprintf (dump_file, " ");
3250 dump_struct_type (f_type, indent, shift + indent);
3251 fprintf(dump_file, " ");
3252 print_generic_expr (dump_file, field, 0);
3253 fprintf(dump_file, ";\n");
3255 print_shift (shift);
3256 fprintf (dump_file, "}\n");
3259 /* This function creates new structure types to replace original type,
3260 indicated by STR->decl. The names of the new structure types are
3261 derived from the original structure type. If the original structure
3262 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3265 create_new_type (d_str str, int *str_num)
3267 int cluster_num = 0;
3269 struct field_cluster *cluster = str->struct_clustering;
3272 tree name = gen_cluster_name (str->decl, cluster_num,
3278 fields = create_fields (cluster, str->fields,
3280 new_type = build_basic_struct (fields, name, str->decl);
3282 update_fields_mapping (cluster, new_type,
3283 str->fields, str->num_fields);
3285 VEC_safe_push (tree, heap, str->new_types, new_type);
3286 cluster = cluster->sibling;
3291 /* This function is a callback for alloc_sites hashtable
3292 traversal. SLOT is a pointer to fallocs_t.
3293 This function frees memory pointed by *SLOT. */
3296 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3298 fallocs_t fallocs = *(fallocs_t *) slot;
3300 VEC_free (alloc_site_t, heap, fallocs->allocs);
3305 /* Remove structures collected in UNSUITABLE_TYPES
3306 from structures vector. */
3309 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3315 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3316 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3317 if (is_equal_types (str->decl, type))
3319 remove_structure (i);
3324 /* Exclude structure types with bitfields.
3325 We would not want to interfere with other optimizations
3326 that can be done in this case. The structure types with
3327 bitfields are added to UNSUITABLE_TYPES vector. */
3330 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3335 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3336 check_bitfields (str, unsuitable_types);
3339 /* This function checks three types of escape. A structure type escapes:
3341 1. if it's a type of parameter of a local function.
3342 2. if it's a type of function return value.
3343 3. if it escapes as a result of ipa-type-escape analysis.
3345 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3348 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3350 exclude_types_passed_to_local_func (unsuitable_types);
3351 exclude_returned_types (unsuitable_types);
3352 exclude_escaping_types_1 (unsuitable_types);
3355 /* This function analyzes whether the form of
3356 structure is such that we are capable to transform it.
3357 Nested structures are checked here. Unsuitable structure
3358 types are added to UNSUITABLE_TYPE vector. */
3361 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3366 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3367 check_struct_form (str, unsuitable_types);
3370 /* This function looks for structure types instantiated in the program.
3371 The candidate types are added to the structures vector.
3372 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3375 build_data_structure (VEC (tree, heap) **unsuitable_types)
3379 struct varpool_node *current_varpool;
3380 struct cgraph_node *c_node;
3382 /* Check global variables. */
3383 FOR_EACH_STATIC_VARIABLE (current_varpool)
3385 var = current_varpool->decl;
3386 if (is_candidate (var, &type, unsuitable_types))
3387 add_structure (type);
3390 /* Now add structures that are types of function parameters and
3392 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3394 enum availability avail =
3395 cgraph_function_body_availability (c_node);
3397 /* We need AVAIL_AVAILABLE for main function. */
3398 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3400 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3402 for (var = DECL_ARGUMENTS (c_node->decl); var;
3403 var = TREE_CHAIN (var))
3404 if (is_candidate (var, &type, unsuitable_types))
3405 add_structure (type);
3409 /* Skip cones that haven't been materialized yet. */
3410 gcc_assert (c_node->clone_of
3411 && c_node->clone_of->decl != c_node->decl);
3415 /* Check function local variables. */
3416 for (var_list = fn->local_decls; var_list;
3417 var_list = TREE_CHAIN (var_list))
3419 var = TREE_VALUE (var_list);
3421 if (is_candidate (var, &type, unsuitable_types))
3422 add_structure (type);
3428 /* This function returns true if the program contains
3429 a call to user defined allocation function, or other
3430 functions that can interfere with struct-reorg optimizations. */
3433 program_redefines_malloc_p (void)
3435 struct cgraph_node *c_node;
3436 struct cgraph_node *c_node2;
3437 struct cgraph_edge *c_edge;
3441 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3443 fndecl = c_node->decl;
3445 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3447 c_node2 = c_edge->callee;
3448 fndecl2 = c_node2->decl;
3449 if (is_gimple_call (c_edge->call_stmt))
3451 const char * fname = get_name (fndecl2);
3453 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3454 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3455 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3456 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3459 /* Check that there is no __builtin_object_size,
3460 __builtin_offsetof, or realloc's in the program. */
3461 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3462 || !strcmp (fname, "__builtin_offsetof")
3463 || !strcmp (fname, "realloc"))
3472 /* In this function we assume that an allocation statement
3474 var = (type_cast) malloc (size);
3476 is converted into the following set of statements:
3480 T.3 = (type_cast) T.2;
3483 In this function we collect into alloc_sites the allocation
3484 sites of variables of structure types that are present
3485 in structures vector. */
3488 collect_alloc_sites (void)
3490 struct cgraph_node *node;
3491 struct cgraph_edge *cs;
3493 for (node = cgraph_nodes; node; node = node->next)
3494 if (node->analyzed && node->decl)
3496 for (cs = node->callees; cs; cs = cs->next_callee)
3498 gimple stmt = cs->call_stmt;
3504 if (is_gimple_call (stmt)
3505 && (decl = gimple_call_fndecl (stmt))
3506 && gimple_call_lhs (stmt))
3510 if (is_alloc_of_struct (stmt, &i))
3512 /* We support only malloc now. */
3513 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3517 str = VEC_index (structure, structures, i);
3518 add_alloc_site (node->decl, stmt, str);
3525 "\nUnsupported allocation function ");
3526 print_gimple_stmt (dump_file, stmt, 0, 0);
3528 remove_structure (i);
3537 /* Print collected accesses. */
3540 dump_accesses (void)
3548 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3552 /* This function checks whether the accesses of structures in condition
3553 expressions are of the kind we are capable to transform.
3554 If not, such structures are removed from the vector of structures. */
3557 check_cond_exprs (void)
3563 while (VEC_iterate (structure, structures, i, str))
3568 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3570 remove_structure (i);
3576 /* We exclude from non-field accesses of the structure
3577 all statements that will be treated as part of the structure
3578 allocation sites or field accesses. */
3581 exclude_alloc_and_field_accs (struct cgraph_node *node)
3586 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3587 exclude_alloc_and_field_accs_1 (str, node);
3590 /* This function collects accesses of the fields of the structures
3591 that appear at function FN. */
3594 collect_accesses_in_func (struct function *fn)
3601 /* Collect accesses for each basic blocks separately. */
3602 FOR_EACH_BB_FN (bb, fn)
3603 collect_accesses_in_bb (bb);
3606 /* This function summarizes counts of the fields into the structure count. */
3609 sum_counts (d_str str, gcov_type *hottest)
3614 for (i = 0; i < str->num_fields; i++)
3618 fprintf (dump_file, "\nCounter of field \"");
3619 print_generic_expr (dump_file, str->fields[i].decl, 0);
3620 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3621 str->fields[i].count);
3623 str->count += str->fields[i].count;
3628 fprintf (dump_file, "\nCounter of struct \"");
3629 print_generic_expr (dump_file, str->decl, 0);
3630 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3633 if (str->count > *hottest)
3634 *hottest = str->count;
3637 /* This function peels the field into separate structure if it's
3638 sufficiently hot, i.e. if its count provides at least 90% of
3639 the maximum field count in the structure. */
3642 peel_hot_fields (d_str str)
3644 gcov_type max_field_count;
3645 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3648 sbitmap_ones (fields_left);
3650 (gcov_type) (get_max_field_count (str)/100)*90;
3652 str->struct_clustering = NULL;
3654 for (i = 0; i < str->num_fields; i++)
3656 if (str->count >= max_field_count)
3658 RESET_BIT (fields_left, i);
3659 peel_field (i, str);
3663 i = sbitmap_first_set_bit (fields_left);
3665 gen_cluster (fields_left, str);
3667 sbitmap_free (fields_left);
3670 /* This function is a helper for do_reorg. It goes over
3671 functions in call graph and performs actual transformation
3677 struct cgraph_node *node;
3679 /* Initialize the default bitmap obstack. */
3680 bitmap_obstack_initialize (NULL);
3682 for (node = cgraph_nodes; node; node = node->next)
3683 if (node->analyzed && node->decl)
3685 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3686 current_function_decl = node->decl;
3688 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3689 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3690 do_reorg_for_func (node);
3691 free_dominance_info (CDI_DOMINATORS);
3692 free_dominance_info (CDI_POST_DOMINATORS);
3693 current_function_decl = NULL;
3698 bitmap_obstack_release (NULL);
3701 /* This function creates new global struct variables.
3702 For each original variable, the set of new variables
3703 is created with the new structure types corresponding
3704 to the structure type of original variable.
3705 Only VAR_DECL variables are treated by this function. */
3708 create_new_global_vars (void)
3710 struct varpool_node *current_varpool;
3711 unsigned HOST_WIDE_INT i;
3712 unsigned HOST_WIDE_INT varpool_size = 0;
3714 for (i = 0; i < 2; i++)
3717 new_global_vars = htab_create (varpool_size,
3718 new_var_hash, new_var_eq, NULL);
3719 FOR_EACH_STATIC_VARIABLE(current_varpool)
3721 tree var_decl = current_varpool->decl;
3723 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3728 create_new_var (var_decl, new_global_vars);
3732 if (new_global_vars)
3733 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3736 /* Dump all new types generated by this optimization. */
3739 dump_new_types (void)
3748 fprintf (dump_file, "\nThe following are the new types generated by"
3749 " this optimization:\n");
3751 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3755 fprintf (dump_file, "\nFor type ");
3756 dump_struct_type (str->decl, 2, 0);
3757 fprintf (dump_file, "\nthe number of new types is %d\n",
3758 VEC_length (tree, str->new_types));
3760 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3761 dump_struct_type (type, 2, 0);
3765 /* This function creates new types to replace old structure types. */
3768 create_new_types (void)
3774 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3775 create_new_type (str, &str_num);
3778 /* Free allocation sites hashtable. */
3781 free_alloc_sites (void)
3784 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3785 htab_delete (alloc_sites);
3789 /* This function collects structures potential
3790 for peeling transformation, and inserts
3791 them into structures hashtable. */
3794 collect_structures (void)
3796 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3798 structures = VEC_alloc (structure, heap, 32);
3800 /* If program contains user defined mallocs, we give up. */
3801 if (program_redefines_malloc_p ())
3804 /* Build data structures hashtable of all data structures
3806 build_data_structure (&unsuitable_types);
3808 /* This function analyzes whether the form of
3809 structure is such that we are capable to transform it.
3810 Nested structures are checked here. */
3811 analyze_struct_form (&unsuitable_types);
3813 /* This function excludes those structure types
3814 that escape compilation unit. */
3815 exclude_escaping_types (&unsuitable_types);
3817 /* We do not want to change data layout of the structures with bitfields. */
3818 exclude_types_with_bit_fields (&unsuitable_types);
3820 remove_unsuitable_types (unsuitable_types);
3821 VEC_free (tree, heap, unsuitable_types);
3824 /* Collect structure allocation sites. In case of arrays
3825 we have nothing to do. */
3828 collect_allocation_sites (void)
3830 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3831 collect_alloc_sites ();
3834 /* This function collects data accesses for the
3835 structures to be transformed. For each structure
3836 field it updates the count field in field_entry. */
3839 collect_data_accesses (void)
3841 struct cgraph_node *c_node;
3843 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3845 enum availability avail = cgraph_function_body_availability (c_node);
3847 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3849 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3851 collect_accesses_in_func (func);
3852 exclude_alloc_and_field_accs (c_node);
3856 check_cond_exprs ();
3857 /* Print collected accesses. */
3861 /* We do not bother to transform cold structures.
3862 Coldness of the structure is defined relatively
3863 to the highest structure count among the structures
3864 to be transformed. It's triggered by the compiler parameter
3866 --param struct-reorg-cold-struct-ratio=<value>
3868 where <value> ranges from 0 to 100. Structures with count ratios
3869 that are less than this parameter are considered to be cold. */
3872 exclude_cold_structs (void)
3874 gcov_type hottest = 0;
3878 /* We summarize counts of fields of a structure into the structure count. */
3879 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3880 sum_counts (str, &hottest);
3882 /* Remove cold structures from structures vector. */
3884 while (VEC_iterate (structure, structures, i, str))
3885 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3889 fprintf (dump_file, "\nThe structure ");
3890 print_generic_expr (dump_file, str->decl, 0);
3891 fprintf (dump_file, " is cold.");
3893 remove_structure (i);
3899 /* This function decomposes original structure into substructures,
3908 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3909 peel_hot_fields (str);
3913 /* Do the actual transformation for each structure
3914 from the structures hashtable. */
3919 /* Check that there is a work to do. */
3920 if (!VEC_length (structure, structures))
3923 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3930 fprintf (dump_file, "\nNumber of structures to transform is %d",
3931 VEC_length (structure, structures));
3935 /* Generate new types. */
3936 create_new_types ();
3939 /* Create new global variables. */
3940 create_new_global_vars ();
3941 dump_new_vars (new_global_vars);
3943 /* Decompose structures for each function separately. */
3946 /* Free auxiliary data collected for global variables. */
3947 free_new_vars_htab (new_global_vars);
3950 /* Free all auxiliary data used by this optimization. */
3953 free_data_structs (void)
3956 free_alloc_sites ();
3959 /* Perform structure decomposition (peeling). */
3962 reorg_structs (void)
3966 /* Collect structure types. */
3967 collect_structures ();
3969 /* Collect structure allocation sites. */
3970 collect_allocation_sites ();
3972 /* Collect structure accesses. */
3973 collect_data_accesses ();
3975 /* We transform only hot structures. */
3976 exclude_cold_structs ();
3979 /* Decompose structures into substructures, i.e. clusters. */
3983 /* Do the actual transformation for each structure
3984 from the structures hashtable. */
3987 /* Free all auxiliary data used by this optimization. */
3988 free_data_structs ();
3991 /* Struct-reorg optimization entry point function. */
3994 reorg_structs_drive (void)
4000 /* Struct-reorg optimization gate function. */
4003 struct_reorg_gate (void)
4005 return flag_ipa_struct_reorg
4006 && flag_whole_program
4010 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
4014 "ipa_struct_reorg", /* name */
4015 struct_reorg_gate, /* gate */
4016 reorg_structs_drive, /* execute */
4019 0, /* static_pass_number */
4020 TV_INTEGRATION, /* tv_id */
4021 0, /* properties_required */
4022 0, /* properties_provided */
4023 0, /* properties_destroyed */
4024 TODO_verify_ssa, /* todo_flags_start */
4025 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */