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,
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 DECL_UID (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 DECL_UID (((const_new_var)x)->orig_var);
2260 /* This function returns nonzero if orig_var of new_var X
2261 and tree Y have equal UIDs. */
2264 new_var_eq (const void *x, const void *y)
2266 if (DECL_P ((const_tree)y))
2267 return DECL_UID (((const_new_var)x)->orig_var) == DECL_UID ((const_tree)y);
2272 /* This function check whether a structure type represented by STR
2273 escapes due to ipa-type-escape analysis. If yes, this type is added
2274 to UNSUITABLE_TYPES vector. */
2277 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2279 tree type = str->decl;
2281 if (!ipa_type_escape_type_contained_p (type))
2285 fprintf (dump_file, "\nEscaping type is ");
2286 print_generic_expr (dump_file, type, 0);
2288 add_unsuitable_type (unsuitable_types, type);
2292 /* Hash value for access_site. */
2295 acc_hash (const void *x)
2297 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2300 /* Return nonzero if stmt of access_site X is equal to Y. */
2303 acc_eq (const void *x, const void *y)
2305 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2308 /* Given a structure declaration STRUCT_DECL, and number of fields
2309 in the structure NUM_FIELDS, this function creates and returns
2310 corresponding field_entry's. */
2312 static struct field_entry *
2313 get_fields (tree struct_decl, int num_fields)
2315 struct field_entry *list;
2316 tree t = TYPE_FIELDS (struct_decl);
2320 (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2322 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2323 if (TREE_CODE (t) == FIELD_DECL)
2325 list[idx].index = idx;
2327 list[idx].acc_sites =
2328 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2329 list[idx].count = 0;
2330 list[idx].field_mapping = NULL_TREE;
2336 /* Print non-field accesses from hashtable ACCS of structure. */
2339 dump_access_sites (htab_t accs)
2345 htab_traverse (accs, dump_acc, NULL);
2348 /* This function is a callback for alloc_sites hashtable
2349 traversal. SLOT is a pointer to fallocs_t. This function
2350 removes all allocations of the structure defined by DATA. */
2353 remove_str_allocs_in_func (void **slot, void *data)
2355 fallocs_t fallocs = *(fallocs_t *) slot;
2359 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2361 if (call->str == (d_str) data)
2362 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2370 /* This function remove all entries corresponding to the STR structure
2371 from alloc_sites hashtable. */
2374 remove_str_allocs (d_str str)
2380 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2383 /* This function removes the structure with index I from structures vector. */
2386 remove_structure (unsigned i)
2390 if (i >= VEC_length (structure, structures))
2393 str = VEC_index (structure, structures, i);
2395 /* Before removing the structure str, we have to remove its
2396 allocations from alloc_sites hashtable. */
2397 remove_str_allocs (str);
2398 free_data_struct (str);
2399 VEC_ordered_remove (structure, structures, i);
2402 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2403 COND_STMT is a condition statement to check. */
2406 is_safe_cond_expr (gimple cond_stmt)
2409 unsigned str0, str1;
2411 unsigned length = VEC_length (structure, structures);
2413 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2414 && gimple_cond_code (cond_stmt) != NE_EXPR)
2417 arg0 = gimple_cond_lhs (cond_stmt);
2418 arg1 = gimple_cond_rhs (cond_stmt);
2420 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2421 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2423 s0 = (str0 != length) ? true : false;
2424 s1 = (str1 != length) ? true : false;
2429 /* For now we allow only comparison with 0 or NULL. */
2430 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2436 /* This function excludes statements, that are
2437 part of allocation sites or field accesses, from the
2438 hashtable of general accesses. SLOT represents general
2439 access that will be checked. DATA is a pointer to
2440 exclude_data structure. */
2443 exclude_from_accs (void **slot, void *data)
2445 struct access_site *acc = *(struct access_site **) slot;
2446 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2447 d_str str = ((struct exclude_data *)data)->str;
2449 if (is_part_of_malloc (acc->stmt, fn_decl)
2450 || is_part_of_field_access (acc->stmt, str))
2452 VEC_free (tree, heap, acc->vars);
2454 htab_clear_slot (str->accs, slot);
2459 /* Callback function for walk_tree called from collect_accesses_in_bb
2460 function. DATA is the statement which is analyzed. */
2463 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2465 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2466 gimple stmt = (gimple) wi->info;
2472 switch (TREE_CODE (t))
2476 tree var = TREE_OPERAND(t, 0);
2477 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2478 unsigned i = find_structure (type);
2480 if (i != VEC_length (structure, structures))
2484 fprintf (dump_file, "\nThe type ");
2485 print_generic_expr (dump_file, type, 0);
2486 fprintf (dump_file, " has bitfield.");
2488 remove_structure (i);
2495 tree ref = TREE_OPERAND (t, 0);
2496 tree field_decl = TREE_OPERAND (t, 1);
2499 if ((TREE_CODE (ref) == INDIRECT_REF
2500 || TREE_CODE (ref) == ARRAY_REF
2501 || TREE_CODE (ref) == VAR_DECL)
2502 && TREE_CODE (field_decl) == FIELD_DECL)
2504 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2505 unsigned i = find_structure (type);
2507 if (i != VEC_length (structure, structures))
2509 d_str str = VEC_index (structure, structures, i);
2510 struct field_entry * field =
2511 find_field_in_struct (str, field_decl);
2515 struct field_access_site *acc = make_field_acc_node ();
2522 acc->field_decl = field_decl;
2524 /* Check whether the access is of the form
2525 we can deal with. */
2526 if (!decompose_access (str->decl, acc))
2530 fprintf (dump_file, "\nThe type ");
2531 print_generic_expr (dump_file, type, 0);
2533 " has complicate access in statement ");
2534 print_gimple_stmt (dump_file, stmt, 0, 0);
2537 remove_structure (i);
2542 /* Increase count of field. */
2543 basic_block bb = gimple_bb (stmt);
2544 field->count += bb->count;
2546 /* Add stmt to the acc_sites of field. */
2547 add_field_acc_to_acc_sites (acc, field->acc_sites);
2558 tree cond = COND_EXPR_COND (t);
2560 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2562 tree t = TREE_OPERAND (cond, i);
2565 walk_tree (&t, get_stmt_accesses, data, NULL);
2576 if (TREE_CODE (t) == SSA_NAME)
2577 t = SSA_NAME_VAR (t);
2579 i = find_structure (strip_type (get_type_of_var (t)));
2580 if (i != VEC_length (structure, structures))
2584 str = VEC_index (structure, structures, i);
2585 add_access_to_acc_sites (stmt, t, str->accs);
2598 /* Free structures hashtable. */
2601 free_structures (void)
2606 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2607 free_data_struct (str);
2609 VEC_free (structure, heap, structures);
2613 /* This function is a callback for traversal over new_var's hashtable.
2614 SLOT is a pointer to new_var. This function frees memory allocated
2615 for new_var and pointed by *SLOT. */
2618 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2620 new_var n_var = *(new_var *) slot;
2622 /* Free vector of new_vars. */
2623 VEC_free (tree, heap, n_var->new_vars);
2628 /* Free new_vars hashtable NEW_VARS_HTAB. */
2631 free_new_vars_htab (htab_t new_vars_htab)
2634 htab_traverse (new_vars_htab, free_new_var, NULL);
2635 htab_delete (new_vars_htab);
2636 new_vars_htab = NULL;
2639 /* This function creates new general and field accesses that appear in cfun. */
2642 create_new_accesses_for_func (void)
2646 FOR_EACH_BB_FN (bb, cfun)
2647 create_new_accesses_in_bb (bb);
2650 /* Create new allocation sites for the function represented by NODE. */
2653 create_new_alloc_sites_for_func (struct cgraph_node *node)
2655 fallocs_t fallocs = get_fallocs (node->decl);
2658 create_new_alloc_sites (fallocs, node->decl);
2661 /* For each local variable of structure type from the vector of structures
2662 this function generates new variable(s) to replace it. */
2665 create_new_local_vars (void)
2668 referenced_var_iterator rvi;
2670 new_local_vars = htab_create (num_referenced_vars,
2671 new_var_hash, new_var_eq, NULL);
2673 FOR_EACH_REFERENCED_VAR (var, rvi)
2675 if (!is_global_var (var))
2676 create_new_var (var, new_local_vars);
2680 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2681 dump_new_vars (new_local_vars);
2684 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2687 print_shift (unsigned HOST_WIDE_INT shift)
2689 unsigned HOST_WIDE_INT sh = shift;
2692 fprintf (dump_file, " ");
2695 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2698 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2699 struct field_entry * fields, int num_fields)
2703 for (i = 0; i < num_fields; i++)
2704 if (TEST_BIT (cluster->fields_in_cluster, i))
2705 fields[i].field_mapping = new_type;
2708 /* This functions builds structure with FIELDS,
2709 NAME and attributes similar to ORIG_STRUCT.
2710 It returns the newly created structure. */
2713 build_basic_struct (tree fields, tree name, tree orig_struct)
2715 tree attributes = NULL_TREE;
2719 if (TYPE_ATTRIBUTES (orig_struct))
2720 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2721 ref = make_node (RECORD_TYPE);
2722 TYPE_SIZE (ref) = 0;
2723 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2724 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2725 for (x = fields; x; x = TREE_CHAIN (x))
2727 DECL_CONTEXT (x) = ref;
2728 DECL_PACKED (x) |= TYPE_PACKED (ref);
2730 TYPE_FIELDS (ref) = fields;
2732 TYPE_NAME (ref) = name;
2737 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2738 of preparation for new structure building. NUM_FIELDS is a total
2739 number of fields in the structure. The function returns newly
2740 generated fields. */
2743 create_fields (struct field_cluster * cluster,
2744 struct field_entry * fields, int num_fields)
2747 tree new_types = NULL_TREE;
2748 tree last = NULL_TREE;
2750 for (i = 0; i < num_fields; i++)
2751 if (TEST_BIT (cluster->fields_in_cluster, i))
2753 tree new_decl = unshare_expr (fields[i].decl);
2756 new_types = new_decl;
2758 TREE_CHAIN (last) = new_decl;
2762 TREE_CHAIN (last) = NULL_TREE;
2767 /* This function creates a cluster name. The name is based on
2768 the original structure name, if it is present. It has a form:
2770 <original_struct_name>_sub.<CLUST_NUM>
2772 The original structure name is taken from the type of DECL.
2773 If an original structure name is not present, it's generated to be:
2777 The function returns identifier of the new cluster name. */
2780 gen_cluster_name (tree decl, int clust_num, int str_num)
2782 const char * orig_name = get_type_name (decl);
2783 char * tmp_name = NULL;
2789 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2791 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2792 prefix = XALLOCAVEC (char, len + 1);
2793 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2794 strlen (tmp_name ? tmp_name : orig_name));
2795 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2797 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2798 return get_identifier (new_name);
2801 /* This function checks whether the structure STR has bitfields.
2802 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2805 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2807 tree type = str->decl;
2810 for (i = 0; i < str->num_fields; i++)
2811 if (DECL_BIT_FIELD (str->fields[i].decl))
2813 add_unsuitable_type (unsuitable_types, type);
2816 fprintf (dump_file, "\nType ");
2817 print_generic_expr (dump_file, type, 0);
2818 fprintf (dump_file, "\nescapes due to bitfield ");
2819 print_generic_expr (dump_file, str->fields[i].decl, 0);
2825 /* This function adds to UNSUITABLE_TYPES those types that escape
2826 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2829 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2834 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2835 check_type_escape (str, unsuitable_types);
2838 /* If a structure type is a return type of any function,
2839 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2842 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2844 struct cgraph_node *c_node;
2846 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2848 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2852 ret_t = strip_type (ret_t);
2853 if (TREE_CODE (ret_t) == RECORD_TYPE)
2855 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2858 fprintf (dump_file, "\nThe type \"");
2859 print_generic_expr (dump_file, ret_t, 0);
2861 "\" is return type of function...Excluded.");
2868 /* This function looks for parameters of local functions
2869 which are of structure types, or derived from them (arrays
2870 of structures, pointers to structures, or their combinations).
2871 We are not handling peeling of such structures right now.
2872 The found structures types are added to UNSUITABLE_TYPES vector. */
2875 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2877 struct cgraph_node *c_node;
2879 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2880 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2882 tree fn = c_node->decl;
2885 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2887 tree type = TREE_TYPE (arg);
2889 type = strip_type (type);
2890 if (TREE_CODE (type) == RECORD_TYPE)
2892 add_unsuitable_type (unsuitable_types,
2893 TYPE_MAIN_VARIANT (type));
2896 fprintf (dump_file, "\nPointer to type \"");
2897 print_generic_expr (dump_file, type, 0);
2899 "\" is passed to local function...Excluded.");
2906 /* This function analyzes structure form of structures
2907 potential for transformation. If we are not capable to transform
2908 structure of some form, we remove it from the structures hashtable.
2909 Right now we cannot handle nested structs, when nesting is
2910 through any level of pointers or arrays.
2912 TBD: release these constrains in future.
2914 Note, that in this function we suppose that all structures
2915 in the program are members of the structures hashtable right now,
2916 without excluding escaping types. */
2919 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2923 for (i = 0; i < str->num_fields; i++)
2925 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2927 if (TREE_CODE (f_type) == RECORD_TYPE)
2929 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2930 add_unsuitable_type (unsuitable_types, str->decl);
2933 fprintf (dump_file, "\nType ");
2934 print_generic_expr (dump_file, f_type, 0);
2935 fprintf (dump_file, " is a field in the structure ");
2936 print_generic_expr (dump_file, str->decl, 0);
2937 fprintf (dump_file, ". Escaping...");
2943 /* This function adds a structure TYPE to the vector of structures,
2944 if it's not already there. */
2947 add_structure (tree type)
2949 struct data_structure node;
2953 type = TYPE_MAIN_VARIANT (type);
2955 i = find_structure (type);
2957 if (i != VEC_length (structure, structures))
2960 num_fields = fields_length (type);
2962 node.num_fields = num_fields;
2963 node.fields = get_fields (type, num_fields);
2964 node.struct_clustering = NULL;
2965 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2966 node.new_types = VEC_alloc (tree, heap, num_fields);
2969 VEC_safe_push (structure, heap, structures, &node);
2973 fprintf (dump_file, "\nAdding data structure \"");
2974 print_generic_expr (dump_file, type, 0);
2975 fprintf (dump_file, "\" to data_struct_list.");
2979 /* This function adds an allocation site to alloc_sites hashtable.
2980 The allocation site appears in STMT of function FN_DECL and
2981 allocates the structure represented by STR. */
2984 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2986 fallocs_t fallocs = NULL;
2987 alloc_site_t m_call;
2993 (fallocs_t) htab_find_with_hash (alloc_sites,
2994 fn_decl, htab_hash_pointer (fn_decl));
3000 fallocs = (fallocs_t)
3001 xmalloc (sizeof (struct func_alloc_sites));
3002 fallocs->func = fn_decl;
3003 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
3004 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
3005 htab_hash_pointer (fn_decl), INSERT);
3008 VEC_safe_push (alloc_site_t, heap,
3009 fallocs->allocs, &m_call);
3013 fprintf (dump_file, "\nAdding stmt ");
3014 print_gimple_stmt (dump_file, stmt, 0, 0);
3015 fprintf (dump_file, " to list of mallocs.");
3019 /* This function returns true if the result of STMT, that contains a call
3020 to an allocation function, is cast to one of the structure types.
3021 STMT should be of the form: T.2 = <alloc_func> (T.1);
3022 If true, I_P contains an index of an allocated structure.
3023 Otherwise I_P contains the length of the vector of structures. */
3026 is_alloc_of_struct (gimple stmt, unsigned *i_p)
3032 final_stmt = get_final_alloc_stmt (stmt);
3037 /* final_stmt should be of the form:
3038 T.3 = (struct_type *) T.2; */
3040 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3043 lhs = gimple_assign_lhs (final_stmt);
3045 type = get_type_of_var (lhs);
3050 if (!POINTER_TYPE_P (type)
3051 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3054 *i_p = find_structure (strip_type (type));
3056 if (*i_p == VEC_length (structure, structures))
3062 /* This function prints non-field and field accesses
3063 of the structure STR. */
3066 dump_accs (d_str str)
3070 fprintf (dump_file, "\nAccess sites of struct ");
3071 print_generic_expr (dump_file, str->decl, 0);
3073 for (i = 0; i < str->num_fields; i++)
3075 fprintf (dump_file, "\nAccess site of field ");
3076 print_generic_expr (dump_file, str->fields[i].decl, 0);
3077 dump_field_acc_sites (str->fields[i].acc_sites);
3078 fprintf (dump_file, ":\n");
3080 fprintf (dump_file, "\nGeneral access sites\n");
3081 dump_access_sites (str->accs);
3084 /* This function checks whether an access statement, pointed by SLOT,
3085 is a condition we are capable to transform. It returns false if not,
3086 setting bool *DATA to false. */
3089 safe_cond_expr_check (void **slot, void *data)
3091 struct access_site *acc = *(struct access_site **) slot;
3093 if (gimple_code (acc->stmt) == GIMPLE_COND
3094 && !is_safe_cond_expr (acc->stmt))
3098 fprintf (dump_file, "\nUnsafe conditional statement ");
3099 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3101 *(bool *) data = false;
3107 /* This function excludes statements that are part of allocation sites and
3108 field accesses from the hashtable of general accesses of the structure
3109 type STR. Only accesses that belong to the function represented by
3110 NODE are treated. */
3113 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3115 struct exclude_data dt;
3117 dt.fn_decl = node->decl;
3120 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3123 /* Collect accesses to the structure types that appear in basic block BB. */
3126 collect_accesses_in_bb (basic_block bb)
3128 gimple_stmt_iterator bsi;
3129 struct walk_stmt_info wi;
3131 memset (&wi, 0, sizeof (wi));
3133 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3135 gimple stmt = gsi_stmt (bsi);
3137 /* In asm stmt we cannot always track the arguments,
3138 so we just give up. */
3139 if (gimple_code (stmt) == GIMPLE_ASM)
3145 wi.info = (void *) stmt;
3146 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3150 /* This function generates cluster substructure that contains FIELDS.
3151 The cluster added to the set of clusters of the structure STR. */
3154 gen_cluster (sbitmap fields, d_str str)
3156 struct field_cluster *crr_cluster = NULL;
3159 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3160 crr_cluster->sibling = str->struct_clustering;
3161 str->struct_clustering = crr_cluster;
3162 crr_cluster->fields_in_cluster = fields;
3165 /* This function peels a field with the index I from the structure DS. */
3168 peel_field (int i, d_str ds)
3170 struct field_cluster *crr_cluster = NULL;
3173 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3174 crr_cluster->sibling = ds->struct_clustering;
3175 ds->struct_clustering = crr_cluster;
3176 crr_cluster->fields_in_cluster =
3177 sbitmap_alloc ((unsigned int) ds->num_fields);
3178 sbitmap_zero (crr_cluster->fields_in_cluster);
3179 SET_BIT (crr_cluster->fields_in_cluster, i);
3182 /* This function calculates maximum field count in
3183 the structure STR. */
3186 get_max_field_count (d_str str)
3191 for (i = 0; i < str->num_fields; i++)
3192 if (str->fields[i].count > max)
3193 max = str->fields[i].count;
3198 /* Do struct-reorg transformation for individual function
3199 represented by NODE. All structure types relevant
3200 for this function are transformed. */
3203 do_reorg_for_func (struct cgraph_node *node)
3205 create_new_local_vars ();
3206 create_new_alloc_sites_for_func (node);
3207 create_new_accesses_for_func ();
3208 update_ssa (TODO_update_ssa);
3209 cleanup_tree_cfg ();
3211 /* Free auxiliary data representing local variables. */
3212 free_new_vars_htab (new_local_vars);
3215 /* Print structure TYPE, its name, if it exists, and body.
3216 INDENT defines the level of indentation (similar
3217 to the option -i of indent command). SHIFT parameter
3218 defines a number of spaces by which a structure will
3219 be shifted right. */
3222 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3223 unsigned HOST_WIDE_INT shift)
3225 const char *struct_name;
3228 if (!type || !dump_file)
3231 if (TREE_CODE (type) != RECORD_TYPE)
3233 print_generic_expr (dump_file, type, 0);
3237 print_shift (shift);
3238 struct_name = get_type_name (type);
3239 fprintf (dump_file, "struct ");
3241 fprintf (dump_file, "%s\n",struct_name);
3242 print_shift (shift);
3243 fprintf (dump_file, "{\n");
3245 for (field = TYPE_FIELDS (type); field;
3246 field = TREE_CHAIN (field))
3248 unsigned HOST_WIDE_INT s = indent;
3249 tree f_type = TREE_TYPE (field);
3251 print_shift (shift);
3253 fprintf (dump_file, " ");
3254 dump_struct_type (f_type, indent, shift + indent);
3255 fprintf(dump_file, " ");
3256 print_generic_expr (dump_file, field, 0);
3257 fprintf(dump_file, ";\n");
3259 print_shift (shift);
3260 fprintf (dump_file, "}\n");
3263 /* This function creates new structure types to replace original type,
3264 indicated by STR->decl. The names of the new structure types are
3265 derived from the original structure type. If the original structure
3266 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3269 create_new_type (d_str str, int *str_num)
3271 int cluster_num = 0;
3273 struct field_cluster *cluster = str->struct_clustering;
3276 tree name = gen_cluster_name (str->decl, cluster_num,
3282 fields = create_fields (cluster, str->fields,
3284 new_type = build_basic_struct (fields, name, str->decl);
3286 update_fields_mapping (cluster, new_type,
3287 str->fields, str->num_fields);
3289 VEC_safe_push (tree, heap, str->new_types, new_type);
3290 cluster = cluster->sibling;
3295 /* This function is a callback for alloc_sites hashtable
3296 traversal. SLOT is a pointer to fallocs_t.
3297 This function frees memory pointed by *SLOT. */
3300 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3302 fallocs_t fallocs = *(fallocs_t *) slot;
3304 VEC_free (alloc_site_t, heap, fallocs->allocs);
3309 /* Remove structures collected in UNSUITABLE_TYPES
3310 from structures vector. */
3313 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3319 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3320 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3321 if (is_equal_types (str->decl, type))
3323 remove_structure (i);
3328 /* Exclude structure types with bitfields.
3329 We would not want to interfere with other optimizations
3330 that can be done in this case. The structure types with
3331 bitfields are added to UNSUITABLE_TYPES vector. */
3334 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3339 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3340 check_bitfields (str, unsuitable_types);
3343 /* This function checks three types of escape. A structure type escapes:
3345 1. if it's a type of parameter of a local function.
3346 2. if it's a type of function return value.
3347 3. if it escapes as a result of ipa-type-escape analysis.
3349 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3352 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3354 exclude_types_passed_to_local_func (unsuitable_types);
3355 exclude_returned_types (unsuitable_types);
3356 exclude_escaping_types_1 (unsuitable_types);
3359 /* This function analyzes whether the form of
3360 structure is such that we are capable to transform it.
3361 Nested structures are checked here. Unsuitable structure
3362 types are added to UNSUITABLE_TYPE vector. */
3365 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3370 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3371 check_struct_form (str, unsuitable_types);
3374 /* This function looks for structure types instantiated in the program.
3375 The candidate types are added to the structures vector.
3376 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3379 build_data_structure (VEC (tree, heap) **unsuitable_types)
3383 struct varpool_node *current_varpool;
3384 struct cgraph_node *c_node;
3386 /* Check global variables. */
3387 FOR_EACH_STATIC_VARIABLE (current_varpool)
3389 var = current_varpool->decl;
3390 if (is_candidate (var, &type, unsuitable_types))
3391 add_structure (type);
3394 /* Now add structures that are types of function parameters and
3396 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3398 enum availability avail =
3399 cgraph_function_body_availability (c_node);
3401 /* We need AVAIL_AVAILABLE for main function. */
3402 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3404 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3406 for (var = DECL_ARGUMENTS (c_node->decl); var;
3407 var = TREE_CHAIN (var))
3408 if (is_candidate (var, &type, unsuitable_types))
3409 add_structure (type);
3413 /* Skip cones that haven't been materialized yet. */
3414 gcc_assert (c_node->clone_of
3415 && c_node->clone_of->decl != c_node->decl);
3419 /* Check function local variables. */
3420 for (var_list = fn->local_decls; var_list;
3421 var_list = TREE_CHAIN (var_list))
3423 var = TREE_VALUE (var_list);
3425 if (is_candidate (var, &type, unsuitable_types))
3426 add_structure (type);
3432 /* This function returns true if the program contains
3433 a call to user defined allocation function, or other
3434 functions that can interfere with struct-reorg optimizations. */
3437 program_redefines_malloc_p (void)
3439 struct cgraph_node *c_node;
3440 struct cgraph_node *c_node2;
3441 struct cgraph_edge *c_edge;
3444 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3446 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3448 c_node2 = c_edge->callee;
3449 fndecl2 = c_node2->decl;
3450 if (is_gimple_call (c_edge->call_stmt))
3452 const char * fname = get_name (fndecl2);
3454 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3455 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3456 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3457 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3460 /* Check that there is no __builtin_object_size,
3461 __builtin_offsetof, or realloc's in the program. */
3462 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3463 || !strcmp (fname, "__builtin_offsetof")
3464 || !strcmp (fname, "realloc"))
3473 /* In this function we assume that an allocation statement
3475 var = (type_cast) malloc (size);
3477 is converted into the following set of statements:
3481 T.3 = (type_cast) T.2;
3484 In this function we collect into alloc_sites the allocation
3485 sites of variables of structure types that are present
3486 in structures vector. */
3489 collect_alloc_sites (void)
3491 struct cgraph_node *node;
3492 struct cgraph_edge *cs;
3494 for (node = cgraph_nodes; node; node = node->next)
3495 if (node->analyzed && node->decl)
3497 for (cs = node->callees; cs; cs = cs->next_callee)
3499 gimple stmt = cs->call_stmt;
3505 if (is_gimple_call (stmt)
3506 && (decl = gimple_call_fndecl (stmt))
3507 && gimple_call_lhs (stmt))
3511 if (is_alloc_of_struct (stmt, &i))
3513 /* We support only malloc now. */
3514 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3518 str = VEC_index (structure, structures, i);
3519 add_alloc_site (node->decl, stmt, str);
3526 "\nUnsupported allocation function ");
3527 print_gimple_stmt (dump_file, stmt, 0, 0);
3529 remove_structure (i);
3538 /* Print collected accesses. */
3541 dump_accesses (void)
3549 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3553 /* This function checks whether the accesses of structures in condition
3554 expressions are of the kind we are capable to transform.
3555 If not, such structures are removed from the vector of structures. */
3558 check_cond_exprs (void)
3564 while (VEC_iterate (structure, structures, i, str))
3569 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3571 remove_structure (i);
3577 /* We exclude from non-field accesses of the structure
3578 all statements that will be treated as part of the structure
3579 allocation sites or field accesses. */
3582 exclude_alloc_and_field_accs (struct cgraph_node *node)
3587 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3588 exclude_alloc_and_field_accs_1 (str, node);
3591 /* This function collects accesses of the fields of the structures
3592 that appear at function FN. */
3595 collect_accesses_in_func (struct function *fn)
3602 /* Collect accesses for each basic blocks separately. */
3603 FOR_EACH_BB_FN (bb, fn)
3604 collect_accesses_in_bb (bb);
3607 /* This function summarizes counts of the fields into the structure count. */
3610 sum_counts (d_str str, gcov_type *hottest)
3615 for (i = 0; i < str->num_fields; i++)
3619 fprintf (dump_file, "\nCounter of field \"");
3620 print_generic_expr (dump_file, str->fields[i].decl, 0);
3621 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3622 str->fields[i].count);
3624 str->count += str->fields[i].count;
3629 fprintf (dump_file, "\nCounter of struct \"");
3630 print_generic_expr (dump_file, str->decl, 0);
3631 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3634 if (str->count > *hottest)
3635 *hottest = str->count;
3638 /* This function peels the field into separate structure if it's
3639 sufficiently hot, i.e. if its count provides at least 90% of
3640 the maximum field count in the structure. */
3643 peel_hot_fields (d_str str)
3645 gcov_type max_field_count;
3646 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3649 sbitmap_ones (fields_left);
3651 (gcov_type) (get_max_field_count (str)/100)*90;
3653 str->struct_clustering = NULL;
3655 for (i = 0; i < str->num_fields; i++)
3657 if (str->count >= max_field_count)
3659 RESET_BIT (fields_left, i);
3660 peel_field (i, str);
3664 i = sbitmap_first_set_bit (fields_left);
3666 gen_cluster (fields_left, str);
3668 sbitmap_free (fields_left);
3671 /* This function is a helper for do_reorg. It goes over
3672 functions in call graph and performs actual transformation
3678 struct cgraph_node *node;
3680 /* Initialize the default bitmap obstack. */
3681 bitmap_obstack_initialize (NULL);
3683 for (node = cgraph_nodes; node; node = node->next)
3684 if (node->analyzed && node->decl)
3686 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3687 current_function_decl = node->decl;
3689 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3690 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3691 do_reorg_for_func (node);
3692 free_dominance_info (CDI_DOMINATORS);
3693 free_dominance_info (CDI_POST_DOMINATORS);
3694 current_function_decl = NULL;
3699 bitmap_obstack_release (NULL);
3702 /* This function creates new global struct variables.
3703 For each original variable, the set of new variables
3704 is created with the new structure types corresponding
3705 to the structure type of original variable.
3706 Only VAR_DECL variables are treated by this function. */
3709 create_new_global_vars (void)
3711 struct varpool_node *current_varpool;
3712 unsigned HOST_WIDE_INT i;
3713 unsigned HOST_WIDE_INT varpool_size = 0;
3715 for (i = 0; i < 2; i++)
3718 new_global_vars = htab_create (varpool_size,
3719 new_var_hash, new_var_eq, NULL);
3720 FOR_EACH_STATIC_VARIABLE(current_varpool)
3722 tree var_decl = current_varpool->decl;
3724 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3729 create_new_var (var_decl, new_global_vars);
3733 if (new_global_vars)
3734 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3737 /* Dump all new types generated by this optimization. */
3740 dump_new_types (void)
3749 fprintf (dump_file, "\nThe following are the new types generated by"
3750 " this optimization:\n");
3752 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3756 fprintf (dump_file, "\nFor type ");
3757 dump_struct_type (str->decl, 2, 0);
3758 fprintf (dump_file, "\nthe number of new types is %d\n",
3759 VEC_length (tree, str->new_types));
3761 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3762 dump_struct_type (type, 2, 0);
3766 /* This function creates new types to replace old structure types. */
3769 create_new_types (void)
3775 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3776 create_new_type (str, &str_num);
3779 /* Free allocation sites hashtable. */
3782 free_alloc_sites (void)
3785 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3786 htab_delete (alloc_sites);
3790 /* This function collects structures potential
3791 for peeling transformation, and inserts
3792 them into structures hashtable. */
3795 collect_structures (void)
3797 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3799 structures = VEC_alloc (structure, heap, 32);
3801 /* If program contains user defined mallocs, we give up. */
3802 if (program_redefines_malloc_p ())
3805 /* Build data structures hashtable of all data structures
3807 build_data_structure (&unsuitable_types);
3809 /* This function analyzes whether the form of
3810 structure is such that we are capable to transform it.
3811 Nested structures are checked here. */
3812 analyze_struct_form (&unsuitable_types);
3814 /* This function excludes those structure types
3815 that escape compilation unit. */
3816 exclude_escaping_types (&unsuitable_types);
3818 /* We do not want to change data layout of the structures with bitfields. */
3819 exclude_types_with_bit_fields (&unsuitable_types);
3821 remove_unsuitable_types (unsuitable_types);
3822 VEC_free (tree, heap, unsuitable_types);
3825 /* Collect structure allocation sites. In case of arrays
3826 we have nothing to do. */
3829 collect_allocation_sites (void)
3831 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3832 collect_alloc_sites ();
3835 /* This function collects data accesses for the
3836 structures to be transformed. For each structure
3837 field it updates the count field in field_entry. */
3840 collect_data_accesses (void)
3842 struct cgraph_node *c_node;
3844 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3846 enum availability avail = cgraph_function_body_availability (c_node);
3848 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3850 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3852 collect_accesses_in_func (func);
3853 exclude_alloc_and_field_accs (c_node);
3857 check_cond_exprs ();
3858 /* Print collected accesses. */
3862 /* We do not bother to transform cold structures.
3863 Coldness of the structure is defined relatively
3864 to the highest structure count among the structures
3865 to be transformed. It's triggered by the compiler parameter
3867 --param struct-reorg-cold-struct-ratio=<value>
3869 where <value> ranges from 0 to 100. Structures with count ratios
3870 that are less than this parameter are considered to be cold. */
3873 exclude_cold_structs (void)
3875 gcov_type hottest = 0;
3879 /* We summarize counts of fields of a structure into the structure count. */
3880 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3881 sum_counts (str, &hottest);
3883 /* Remove cold structures from structures vector. */
3885 while (VEC_iterate (structure, structures, i, str))
3886 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3890 fprintf (dump_file, "\nThe structure ");
3891 print_generic_expr (dump_file, str->decl, 0);
3892 fprintf (dump_file, " is cold.");
3894 remove_structure (i);
3900 /* This function decomposes original structure into substructures,
3909 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3910 peel_hot_fields (str);
3914 /* Do the actual transformation for each structure
3915 from the structures hashtable. */
3920 /* Check that there is a work to do. */
3921 if (!VEC_length (structure, structures))
3924 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3931 fprintf (dump_file, "\nNumber of structures to transform is %d",
3932 VEC_length (structure, structures));
3936 /* Generate new types. */
3937 create_new_types ();
3940 /* Create new global variables. */
3941 create_new_global_vars ();
3942 dump_new_vars (new_global_vars);
3944 /* Decompose structures for each function separately. */
3947 /* Free auxiliary data collected for global variables. */
3948 free_new_vars_htab (new_global_vars);
3951 /* Free all auxiliary data used by this optimization. */
3954 free_data_structs (void)
3957 free_alloc_sites ();
3960 /* Perform structure decomposition (peeling). */
3963 reorg_structs (void)
3967 /* Collect structure types. */
3968 collect_structures ();
3970 /* Collect structure allocation sites. */
3971 collect_allocation_sites ();
3973 /* Collect structure accesses. */
3974 collect_data_accesses ();
3976 /* We transform only hot structures. */
3977 exclude_cold_structs ();
3980 /* Decompose structures into substructures, i.e. clusters. */
3984 /* Do the actual transformation for each structure
3985 from the structures hashtable. */
3988 /* Free all auxiliary data used by this optimization. */
3989 free_data_structs ();
3992 /* Struct-reorg optimization entry point function. */
3995 reorg_structs_drive (void)
4001 /* Struct-reorg optimization gate function. */
4004 struct_reorg_gate (void)
4006 return flag_ipa_struct_reorg
4007 && flag_whole_program
4011 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
4015 "ipa_struct_reorg", /* name */
4016 struct_reorg_gate, /* gate */
4017 reorg_structs_drive, /* execute */
4020 0, /* static_pass_number */
4021 TV_INTEGRATION, /* tv_id */
4022 0, /* properties_required */
4023 0, /* properties_provided */
4024 0, /* properties_destroyed */
4025 TODO_verify_ssa, /* todo_flags_start */
4026 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */