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"
43 #include "diagnostic.h"
49 #include "basic-block.h"
50 #include "tree-iterator.h"
51 #include "tree-pass.h"
52 #include "ipa-struct-reorg.h"
54 #include "ipa-type-escape.h"
55 #include "tree-dump.h"
59 /* This optimization implements structure peeling.
61 For example, given a structure type:
69 it can be peeled into two structure types as follows:
71 typedef struct and typedef struct
77 or can be fully peeled:
94 When structure type is peeled all instances and their accesses
95 in the program are updated accordingly. For example, if there is
100 and structure type str_t was peeled into two structures str_t_0
101 and str_t_1 as it was shown above, then array A will be replaced
102 by two arrays as follows:
107 The field access of field a of element i of array A: A[i].a will be
108 replaced by an access to field a of element i of array A_0: A_0[i].a.
110 This optimization also supports dynamically allocated arrays.
111 If array of structures was allocated by malloc function:
113 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
115 the allocation site will be replaced to reflect new structure types:
117 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
118 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
120 The field access through the pointer p[i].a will be changed by p_0[i].a.
122 The goal of structure peeling is to improve spatial locality.
123 For example, if one of the fields of a structure is accessed frequently
126 for (i = 0; i < N; i++)
131 the allocation of field a of str_t contiguously in memory will
132 increase the chances of fetching the field from cache.
134 The analysis part of this optimization is based on the frequency of
135 field accesses, which are collected all over the program.
136 Then the fields with the frequencies that satisfy the following condition
137 get peeled out of the structure:
139 freq(f) > C * max_field_freq_in_struct
141 where max_field_freq_in_struct is the maximum field frequency
142 in the structure. C is a constant defining which portion of
143 max_field_freq_in_struct the fields should have in order to be peeled.
145 If profiling information is provided, it is used to calculate the
146 frequency of field accesses. Otherwise, the structure is fully peeled.
148 IPA type-escape analysis is used to determine when it is safe
151 The optimization is activated by flag -fipa-struct-reorg. */
153 /* New variables created by this optimization.
154 When doing struct peeling, each variable of
155 the original struct type will be replaced by
156 the set of new variables corresponding to
157 the new structure types. */
158 struct new_var_data {
159 /* VAR_DECL for original struct type. */
161 /* Vector of new variables. */
162 VEC(tree, heap) *new_vars;
165 typedef struct new_var_data *new_var;
166 typedef const struct new_var_data *const_new_var;
168 /* This structure represents allocation site of the structure. */
169 typedef struct alloc_site
175 DEF_VEC_O (alloc_site_t);
176 DEF_VEC_ALLOC_O (alloc_site_t, heap);
178 /* Allocation sites that belong to the same function. */
179 struct func_alloc_sites
182 /* Vector of allocation sites for function. */
183 VEC (alloc_site_t, heap) *allocs;
186 typedef struct func_alloc_sites *fallocs_t;
187 typedef const struct func_alloc_sites *const_fallocs_t;
189 /* All allocation sites in the program. */
190 htab_t alloc_sites = NULL;
192 /* New global variables. Generated once for whole program. */
193 htab_t new_global_vars;
195 /* New local variables. Generated per-function. */
196 htab_t new_local_vars;
198 /* Vector of structures to be transformed. */
199 typedef struct data_structure structure;
200 DEF_VEC_O (structure);
201 DEF_VEC_ALLOC_O (structure, heap);
202 VEC (structure, heap) *structures;
204 /* Forward declarations. */
205 static bool is_equal_types (tree, tree);
207 /* Strip structure TYPE from pointers and arrays. */
210 strip_type (tree type)
212 gcc_assert (TYPE_P (type));
214 while (POINTER_TYPE_P (type)
215 || TREE_CODE (type) == ARRAY_TYPE)
216 type = TREE_TYPE (type);
221 /* This function returns type of VAR. */
224 get_type_of_var (tree var)
229 if (TREE_CODE (var) == PARM_DECL)
230 return DECL_ARG_TYPE (var);
232 return TREE_TYPE (var);
235 /* Set of actions we do for each newly generated STMT. */
238 finalize_stmt (gimple stmt)
241 mark_symbols_for_renaming (stmt);
244 /* This function finalizes STMT and appends it to the list STMTS. */
247 finalize_stmt_and_append (gimple_seq *stmts, gimple stmt)
249 gimple_seq_add_stmt (stmts, stmt);
250 finalize_stmt (stmt);
253 /* Given structure type SRT_TYPE and field FIELD,
254 this function is looking for a field with the same name
255 and type as FIELD in STR_TYPE. It returns it if found,
256 or NULL_TREE otherwise. */
259 find_field_in_struct_1 (tree str_type, tree field)
263 for (str_field = TYPE_FIELDS (str_type); str_field;
264 str_field = TREE_CHAIN (str_field))
266 const char * str_field_name;
267 const char * field_name;
269 str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
270 field_name = IDENTIFIER_POINTER (DECL_NAME (field));
272 gcc_assert (str_field_name);
273 gcc_assert (field_name);
275 if (!strcmp (str_field_name, field_name))
277 /* Check field types. */
278 if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
286 /* Given a field declaration FIELD_DECL, this function
287 returns corresponding field entry in structure STR. */
289 static struct field_entry *
290 find_field_in_struct (d_str str, tree field_decl)
294 tree field = find_field_in_struct_1 (str->decl, field_decl);
296 for (i = 0; i < str->num_fields; i++)
297 if (str->fields[i].decl == field)
298 return &(str->fields[i]);
303 /* This function checks whether ARG is a result of multiplication
304 of some number by STRUCT_SIZE. If yes, the function returns true
305 and this number is filled into NUM. */
308 is_result_of_mult (tree arg, tree *num, tree struct_size)
310 gimple size_def_stmt = SSA_NAME_DEF_STMT (arg);
312 /* If the allocation statement was of the form
313 D.2229_10 = <alloc_func> (D.2228_9);
314 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
316 if (size_def_stmt && is_gimple_assign (size_def_stmt))
318 tree lhs = gimple_assign_lhs (size_def_stmt);
320 /* We expect temporary here. */
321 if (!is_gimple_reg (lhs))
324 if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR)
326 tree arg0 = gimple_assign_rhs1 (size_def_stmt);
327 tree arg1 = gimple_assign_rhs2 (size_def_stmt);
329 if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
335 if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
348 /* This function returns true if access ACC corresponds to the pattern
349 generated by compiler when an address of element i of an array
350 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
351 pattern is recognized correctly, this function returns true
352 and fills missing fields in ACC. Otherwise it returns false. */
355 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
358 tree struct_size, op0, op1;
360 enum tree_code rhs_code;
362 ref_var = TREE_OPERAND (acc->ref, 0);
364 if (TREE_CODE (ref_var) != SSA_NAME)
367 acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
368 if (!(acc->ref_def_stmt)
369 || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN))
372 rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt);
374 if (rhs_code != PLUS_EXPR
375 && rhs_code != MINUS_EXPR
376 && rhs_code != POINTER_PLUS_EXPR)
379 op0 = gimple_assign_rhs1 (acc->ref_def_stmt);
380 op1 = gimple_assign_rhs2 (acc->ref_def_stmt);
382 if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1,
383 &acc->base, &acc->offset,
388 before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
390 before_cast = acc->offset;
396 if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
399 struct_size = TYPE_SIZE_UNIT (str_decl);
401 if (!is_result_of_mult (before_cast, &acc->num, struct_size))
408 /* This function checks whether the access ACC of structure type STR
409 is of the form suitable for transformation. If yes, it returns true.
413 decompose_access (tree str_decl, struct field_access_site *acc)
415 gcc_assert (acc->ref);
417 if (TREE_CODE (acc->ref) == INDIRECT_REF)
418 return decompose_indirect_ref_acc (str_decl, acc);
419 else if (TREE_CODE (acc->ref) == ARRAY_REF)
421 else if (TREE_CODE (acc->ref) == VAR_DECL)
427 /* This function creates empty field_access_site node. */
429 static inline struct field_access_site *
430 make_field_acc_node (void)
432 int size = sizeof (struct field_access_site);
434 return (struct field_access_site *) xcalloc (1, size);
437 /* This function returns the structure field access, defined by STMT,
438 if it is already in hashtable of function accesses F_ACCS. */
440 static struct field_access_site *
441 is_in_field_accs (gimple stmt, htab_t f_accs)
443 return (struct field_access_site *)
444 htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
447 /* This function adds an access ACC to the hashtable
448 F_ACCS of field accesses. */
451 add_field_acc_to_acc_sites (struct field_access_site *acc,
456 gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
457 slot = htab_find_slot_with_hash (f_accs, acc->stmt,
458 htab_hash_pointer (acc->stmt),
463 /* This function adds the VAR to vector of variables of
464 an access site defined by statement STMT. If access entry
465 with statement STMT does not exist in hashtable of
466 accesses ACCS, this function creates it. */
469 add_access_to_acc_sites (gimple stmt, tree var, htab_t accs)
471 struct access_site *acc;
473 acc = (struct access_site *)
474 htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
480 acc = (struct access_site *) xmalloc (sizeof (struct access_site));
482 acc->vars = VEC_alloc (tree, heap, 10);
483 slot = htab_find_slot_with_hash (accs, stmt,
484 htab_hash_pointer (stmt), INSERT);
488 VEC_safe_push (tree, heap, acc->vars, var);
491 /* This function adds NEW_DECL to function
492 referenced vars, and marks it for renaming. */
495 finalize_var_creation (tree new_decl)
497 add_referenced_var (new_decl);
498 mark_sym_for_renaming (new_decl);
501 /* This function finalizes VAR creation if it is a global VAR_DECL. */
504 finalize_global_creation (tree var)
506 if (TREE_CODE (var) == VAR_DECL
507 && is_global_var (var))
508 finalize_var_creation (var);
511 /* This function inserts NEW_DECL to varpool. */
514 insert_global_to_varpool (tree new_decl)
516 struct varpool_node *new_node;
518 new_node = varpool_node (new_decl);
519 notice_global_symbol (new_decl);
520 varpool_mark_needed_node (new_node);
521 varpool_finalize_decl (new_decl);
524 /* This function finalizes the creation of new variables,
525 defined by *SLOT->new_vars. */
528 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
530 new_var n_var = *(new_var *) slot;
534 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
535 finalize_var_creation (var);
539 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
540 It returns it, if found, and NULL_TREE otherwise. */
543 find_var_in_new_vars_vec (new_var var, tree new_type)
548 for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
550 tree type = strip_type(get_type_of_var (n_var));
553 if (type == new_type)
560 /* This function returns new_var node, the orig_var of which is DECL.
561 It looks for new_var's in NEW_VARS_HTAB. If not found,
562 the function returns NULL. */
565 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
567 return (new_var) htab_find_with_hash (new_vars_htab, decl,
568 htab_hash_pointer (decl));
571 /* Given original variable ORIG_VAR, this function returns
572 new variable corresponding to it of NEW_TYPE type. */
575 find_new_var_of_type (tree orig_var, tree new_type)
578 gcc_assert (orig_var && new_type);
580 if (TREE_CODE (orig_var) == SSA_NAME)
581 orig_var = SSA_NAME_VAR (orig_var);
583 var = is_in_new_vars_htab (orig_var, new_global_vars);
585 var = is_in_new_vars_htab (orig_var, new_local_vars);
587 return find_var_in_new_vars_vec (var, new_type);
590 /* This function generates stmt:
591 res = NUM * sizeof(TYPE) and returns it.
592 res is filled into RES. */
595 gen_size (tree num, tree type, tree *res)
597 tree struct_size = TYPE_SIZE_UNIT (type);
598 HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
601 *res = create_tmp_var (TREE_TYPE (num), NULL);
604 add_referenced_var (*res);
606 if (exact_log2 (struct_size_int) == -1)
608 tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
609 new_stmt = gimple_build_assign (*res, fold_build2 (MULT_EXPR,
615 tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
617 new_stmt = gimple_build_assign (*res, fold_build2 (LSHIFT_EXPR,
622 finalize_stmt (new_stmt);
626 /* This function generates and returns a statement, that cast variable
627 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
628 into RES_P. ORIG_CAST_STMT is the original cast statement. */
631 gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt,
637 lhs = gimple_assign_lhs (orig_cast_stmt);
638 new_lhs = find_new_var_of_type (lhs, new_type);
639 gcc_assert (new_lhs);
641 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0);
642 finalize_stmt (new_stmt);
647 /* This function builds an edge between BB and E->dest and updates
648 phi nodes of E->dest. It returns newly created edge. */
651 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
655 gimple_stmt_iterator si;
657 new_e = make_edge (bb, e->dest, e->flags);
659 for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si))
661 gimple phi = gsi_stmt (si);
662 arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
663 add_phi_arg (phi, arg, new_e);
669 /* This function inserts NEW_STMT before STMT. */
672 insert_before_stmt (gimple stmt, gimple new_stmt)
674 gimple_stmt_iterator bsi;
676 if (!stmt || !new_stmt)
679 bsi = gsi_for_stmt (stmt);
680 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
683 /* Insert NEW_STMTS after STMT. */
686 insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts)
688 gimple_stmt_iterator bsi;
690 if (!stmt || !new_stmts)
693 bsi = gsi_for_stmt (stmt);
694 gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT);
697 /* Insert NEW_STMT after STMT. */
700 insert_after_stmt (gimple stmt, gimple new_stmt)
702 gimple_stmt_iterator bsi;
704 if (!stmt || !new_stmt)
707 bsi = gsi_for_stmt (stmt);
708 gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT);
711 /* This function returns vector of allocation sites
712 that appear in function FN_DECL. */
715 get_fallocs (tree fn_decl)
717 return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
718 htab_hash_pointer (fn_decl));
721 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
722 and it is a part of allocation of a structure,
723 then it is usually followed by a cast stmt
724 p_8 = (struct str_t *) D.2225_7;
725 which is returned by this function. */
728 get_final_alloc_stmt (gimple alloc_stmt)
737 if (!is_gimple_call (alloc_stmt))
740 alloc_res = gimple_get_lhs (alloc_stmt);
742 if (TREE_CODE (alloc_res) != SSA_NAME)
745 if (!single_imm_use (alloc_res, &use_p, &final_stmt))
751 /* This function returns true if STMT is one of allocation
752 sites of function FN_DECL. It returns false otherwise. */
755 is_part_of_malloc (gimple stmt, tree fn_decl)
757 fallocs_t fallocs = get_fallocs (fn_decl);
764 for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
765 if (call->stmt == stmt
766 || get_final_alloc_stmt (call->stmt) == stmt)
772 /* Auxiliary structure for a lookup over field accesses. */
773 struct find_stmt_data
779 /* This function looks for DATA->stmt among
780 the statements involved in the field access,
781 defined by SLOT. It stops when it's found. */
784 find_in_field_accs (void **slot, void *data)
786 struct field_access_site *f_acc = *(struct field_access_site **) slot;
787 gimple stmt = ((struct find_stmt_data *)data)->stmt;
789 if (f_acc->stmt == stmt
790 || f_acc->ref_def_stmt == stmt
791 || f_acc->cast_stmt == stmt)
793 ((struct find_stmt_data *)data)->found = true;
800 /* This function checks whether STMT is part of field
801 accesses of structure STR. It returns true, if found,
802 and false otherwise. */
805 is_part_of_field_access (gimple stmt, d_str str)
809 for (i = 0; i < str->num_fields; i++)
811 struct find_stmt_data data;
815 if (str->fields[i].acc_sites)
816 htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
825 /* Auxiliary data for exclude_from_accs function. */
833 /* This function returns component_ref with the BASE and
834 field named FIELD_ID from structure TYPE. */
837 build_comp_ref (tree base, tree field_id, tree type)
843 /* Find field of structure type with the same name as field_id. */
844 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
846 if (DECL_NAME (field) == field_id)
855 return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
859 /* This struct represent data used for walk_tree
860 called from function find_pos_in_stmt.
861 - ref is a tree to be found,
862 - and pos is a pointer that points to ref in stmt. */
870 /* This is a callback function for walk_tree, called from
871 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
872 When *TP is equal to DATA->ref, the walk_tree stops,
873 and found position, equal to TP, is assigned to DATA->pos. */
876 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
878 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
879 struct ref_pos *r_pos = (struct ref_pos *) wi->info;
880 tree ref = r_pos->ref;
883 if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref))
894 /* This function looks for the pointer of REF in STMT,
895 It returns it, if found, and NULL otherwise. */
898 find_pos_in_stmt (gimple stmt, tree ref)
900 struct ref_pos r_pos;
901 struct walk_stmt_info wi;
905 memset (&wi, 0, sizeof (wi));
907 walk_gimple_op (stmt, find_pos_in_stmt_1, &wi);
912 /* This structure is used to represent array
913 or pointer-to wrappers of structure type.
914 For example, if type1 is structure type,
915 then for type1 ** we generate two type_wrapper
916 structures with wrap = 0 each one.
917 It's used to unwind the original type up to
918 structure type, replace it with the new structure type
919 and wrap it back in the opposite order. */
921 typedef struct type_wrapper
923 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
926 /* Relevant for arrays as domain or index. */
930 DEF_VEC_O (type_wrapper_t);
931 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
933 /* This function replace field access ACC by the new
934 field access of structure type NEW_TYPE. */
937 replace_field_acc (struct field_access_site *acc, tree new_type)
939 tree ref_var = acc->ref;
944 tree field_id = DECL_NAME (acc->field_decl);
945 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
946 type_wrapper_t *wr_p = NULL;
948 while (TREE_CODE (ref_var) == INDIRECT_REF
949 || TREE_CODE (ref_var) == ARRAY_REF)
953 if ( TREE_CODE (ref_var) == INDIRECT_REF)
961 wr.domain = TREE_OPERAND (ref_var, 1);
964 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
965 ref_var = TREE_OPERAND (ref_var, 0);
968 new_ref = find_new_var_of_type (ref_var, new_type);
969 finalize_global_creation (new_ref);
971 while (VEC_length (type_wrapper_t, wrapper) != 0)
973 tree type = TREE_TYPE (TREE_TYPE (new_ref));
975 wr_p = VEC_last (type_wrapper_t, wrapper);
976 if (wr_p->wrap) /* Array. */
977 new_ref = build4 (ARRAY_REF, type, new_ref,
978 wr_p->domain, NULL_TREE, NULL_TREE);
980 new_ref = build1 (INDIRECT_REF, type, new_ref);
981 VEC_pop (type_wrapper_t, wrapper);
984 new_acc = build_comp_ref (new_ref, field_id, new_type);
985 VEC_free (type_wrapper_t, heap, wrapper);
987 if (is_gimple_assign (acc->stmt))
989 lhs = gimple_assign_lhs (acc->stmt);
990 rhs = gimple_assign_rhs1 (acc->stmt);
992 if (lhs == acc->comp_ref)
993 gimple_assign_set_lhs (acc->stmt, new_acc);
994 else if (rhs == acc->comp_ref)
995 gimple_assign_set_rhs1 (acc->stmt, new_acc);
998 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1005 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1010 finalize_stmt (acc->stmt);
1013 /* This function replace field access ACC by a new field access
1014 of structure type NEW_TYPE. */
1017 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1020 if (TREE_CODE (acc->ref) == INDIRECT_REF
1021 ||TREE_CODE (acc->ref) == ARRAY_REF
1022 ||TREE_CODE (acc->ref) == VAR_DECL)
1023 replace_field_acc (acc, new_type);
1028 /* This function looks for d_str, represented by TYPE, in the structures
1029 vector. If found, it returns an index of found structure. Otherwise
1030 it returns a length of the structures vector. */
1033 find_structure (tree type)
1038 type = TYPE_MAIN_VARIANT (type);
1040 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1041 if (is_equal_types (str->decl, type))
1044 return VEC_length (structure, structures);
1047 /* In this function we create new statements that have the same
1048 form as ORIG_STMT, but of type NEW_TYPE. The statements
1049 treated by this function are simple assignments,
1050 like assignments: p.8_7 = p; or statements with rhs of
1051 tree codes PLUS_EXPR and MINUS_EXPR. */
1054 create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset)
1059 tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1061 lhs = gimple_assign_lhs (orig_stmt);
1063 gcc_assert (TREE_CODE (lhs) == VAR_DECL
1064 || TREE_CODE (lhs) == SSA_NAME);
1066 new_lhs = find_new_var_of_type (lhs, new_type);
1067 gcc_assert (new_lhs);
1068 finalize_var_creation (new_lhs);
1070 switch (gimple_assign_rhs_code (orig_stmt))
1074 case POINTER_PLUS_EXPR:
1076 tree op0 = gimple_assign_rhs1 (orig_stmt);
1077 tree op1 = gimple_assign_rhs2 (orig_stmt);
1078 unsigned str0, str1;
1079 unsigned length = VEC_length (structure, structures);
1082 str0 = find_structure (strip_type (get_type_of_var (op0)));
1083 str1 = find_structure (strip_type (get_type_of_var (op1)));
1084 gcc_assert ((str0 != length) || (str1 != length));
1087 new_op0 = find_new_var_of_type (op0, new_type);
1089 new_op1 = find_new_var_of_type (op1, new_type);
1102 new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt),
1103 new_lhs, new_op0, new_op1);
1104 finalize_stmt (new_stmt);
1109 /* Given a field access F_ACC of the FIELD, this function
1110 replaces it by the new field access. */
1113 create_new_field_access (struct field_access_site *f_acc,
1114 struct field_entry field)
1116 tree new_type = field.field_mapping;
1121 tree cast_res = NULL;
1125 mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1126 insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1129 if (f_acc->cast_stmt)
1131 cast_stmt = gen_cast_stmt (size_res, new_type,
1132 f_acc->cast_stmt, &cast_res);
1133 insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1136 if (f_acc->ref_def_stmt)
1144 new_stmt = create_base_plus_offset (f_acc->ref_def_stmt,
1146 insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1149 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1150 D.2162_18 by an appropriate variable of new_type type. */
1151 replace_field_access_stmt (f_acc, new_type);
1154 /* This function creates a new condition statement
1155 corresponding to the original COND_STMT, adds new basic block
1156 and redirects condition edges. NEW_VAR is a new condition
1157 variable located in the condition statement at the position POS. */
1160 create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos)
1163 edge true_e = NULL, false_e = NULL;
1165 gimple_stmt_iterator si;
1167 extract_true_false_edges_from_block (gimple_bb (cond_stmt),
1170 new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1171 pos == 0 ? new_var : gimple_cond_lhs (cond_stmt),
1172 pos == 1 ? new_var : gimple_cond_rhs (cond_stmt),
1176 finalize_stmt (new_stmt);
1178 /* Create new basic block after bb. */
1179 new_bb = create_empty_bb (gimple_bb (cond_stmt));
1181 /* Add new condition stmt to the new_bb. */
1182 si = gsi_start_bb (new_bb);
1183 gsi_insert_after (&si, new_stmt, GSI_NEW_STMT);
1185 /* Create false and true edges from new_bb. */
1186 make_edge_and_fix_phis_of_dest (new_bb, true_e);
1187 make_edge_and_fix_phis_of_dest (new_bb, false_e);
1189 /* Redirect one of original edges to point to new_bb. */
1190 if (gimple_cond_code (cond_stmt) == NE_EXPR)
1191 redirect_edge_succ (true_e, new_bb);
1193 redirect_edge_succ (false_e, new_bb);
1196 /* This function creates new condition statements corresponding
1197 to original condition STMT, one for each new type, and
1198 recursively redirect edges to newly generated basic blocks. */
1201 create_new_stmts_for_cond_expr (gimple stmt)
1203 tree arg0, arg1, arg;
1204 unsigned str0, str1;
1210 unsigned length = VEC_length (structure, structures);
1212 gcc_assert (gimple_cond_code (stmt) == EQ_EXPR
1213 || gimple_cond_code (stmt) == NE_EXPR);
1215 arg0 = gimple_cond_lhs (stmt);
1216 arg1 = gimple_cond_rhs (stmt);
1218 str0 = find_structure (strip_type (get_type_of_var (arg0)));
1219 str1 = find_structure (strip_type (get_type_of_var (arg1)));
1221 s0 = (str0 != length) ? true : false;
1222 s1 = (str1 != length) ? true : false;
1224 gcc_assert (s0 || s1);
1225 /* For now we allow only comparison with 0 or NULL. */
1226 gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1228 str = integer_zerop (arg0) ?
1229 VEC_index (structure, structures, str1):
1230 VEC_index (structure, structures, str0);
1231 arg = integer_zerop (arg0) ? arg1 : arg0;
1232 pos = integer_zerop (arg0) ? 1 : 0;
1234 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1238 new_arg = find_new_var_of_type (arg, type);
1239 create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1243 /* Create a new general access to replace original access ACC
1244 for structure type NEW_TYPE. */
1247 create_general_new_stmt (struct access_site *acc, tree new_type)
1249 gimple old_stmt = acc->stmt;
1251 gimple new_stmt = gimple_copy (old_stmt);
1254 /* We are really building a new stmt, clear the virtual operands. */
1255 if (gimple_has_mem_ops (new_stmt))
1257 gimple_set_vuse (new_stmt, NULL_TREE);
1258 gimple_set_vdef (new_stmt, NULL_TREE);
1261 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1264 tree new_var = find_new_var_of_type (var, new_type);
1265 tree lhs, rhs = NULL_TREE;
1267 gcc_assert (new_var);
1268 finalize_var_creation (new_var);
1270 if (is_gimple_assign (new_stmt))
1272 lhs = gimple_assign_lhs (new_stmt);
1274 if (TREE_CODE (lhs) == SSA_NAME)
1275 lhs = SSA_NAME_VAR (lhs);
1276 if (gimple_assign_rhs_code (new_stmt) == SSA_NAME)
1277 rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt));
1279 /* It can happen that rhs is a constructor.
1280 Then we have to replace it to be of new_type. */
1281 if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR)
1283 /* Dealing only with empty constructors right now. */
1284 gcc_assert (VEC_empty (constructor_elt,
1285 CONSTRUCTOR_ELTS (rhs)));
1286 rhs = build_constructor (new_type, 0);
1287 gimple_assign_set_rhs1 (new_stmt, rhs);
1291 gimple_assign_set_lhs (new_stmt, new_var);
1292 else if (rhs == var)
1293 gimple_assign_set_rhs1 (new_stmt, new_var);
1296 pos = find_pos_in_stmt (new_stmt, var);
1298 /* ??? This misses adjustments to the type of the
1299 INDIRECT_REF we possibly replace the operand of. */
1305 pos = find_pos_in_stmt (new_stmt, var);
1311 finalize_stmt (new_stmt);
1315 /* For each new type in STR this function creates new general accesses
1316 corresponding to the original access ACC. */
1319 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1322 gimple stmt = acc->stmt;
1325 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1329 new_stmt = create_general_new_stmt (acc, type);
1330 insert_after_stmt (stmt, new_stmt);
1334 /* This function creates a new general access of structure STR
1335 to replace the access ACC. */
1338 create_new_general_access (struct access_site *acc, d_str str)
1340 gimple stmt = acc->stmt;
1341 switch (gimple_code (stmt))
1344 create_new_stmts_for_cond_expr (stmt);
1348 create_new_stmts_for_general_acc (acc, str);
1352 /* Auxiliary data for creation of accesses. */
1353 struct create_acc_data
1360 /* This function creates a new general access, defined by SLOT.
1361 DATA is a pointer to create_acc_data structure. */
1364 create_new_acc (void **slot, void *data)
1366 struct access_site *acc = *(struct access_site **) slot;
1367 basic_block bb = ((struct create_acc_data *)data)->bb;
1368 d_str str = ((struct create_acc_data *)data)->str;
1370 if (gimple_bb (acc->stmt) == bb)
1371 create_new_general_access (acc, str);
1375 /* This function creates a new field access, defined by SLOT.
1376 DATA is a pointer to create_acc_data structure. */
1379 create_new_field_acc (void **slot, void *data)
1381 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1382 basic_block bb = ((struct create_acc_data *)data)->bb;
1383 d_str str = ((struct create_acc_data *)data)->str;
1384 int i = ((struct create_acc_data *)data)->field_index;
1386 if (gimple_bb (f_acc->stmt) == bb)
1387 create_new_field_access (f_acc, str->fields[i]);
1391 /* This function creates new accesses for the structure
1392 type STR in basic block BB. */
1395 create_new_accs_for_struct (d_str str, basic_block bb)
1398 struct create_acc_data dt;
1402 dt.field_index = -1;
1404 for (i = 0; i < str->num_fields; i++)
1408 if (str->fields[i].acc_sites)
1409 htab_traverse (str->fields[i].acc_sites,
1410 create_new_field_acc, &dt);
1413 htab_traverse (str->accs, create_new_acc, &dt);
1416 /* This function inserts new variables from new_var,
1417 defined by SLOT, into varpool. */
1420 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1422 new_var n_var = *(new_var *) slot;
1426 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1427 insert_global_to_varpool (var);
1431 /* This function prints a field access site, defined by SLOT. */
1434 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1436 struct field_access_site *f_acc =
1437 *(struct field_access_site **) slot;
1439 fprintf(dump_file, "\n");
1441 print_gimple_stmt (dump_file, f_acc->stmt, 0, 0);
1442 if (f_acc->ref_def_stmt)
1443 print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0);
1444 if (f_acc->cast_stmt)
1445 print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0);
1449 /* Print field accesses from hashtable F_ACCS. */
1452 dump_field_acc_sites (htab_t f_accs)
1458 htab_traverse (f_accs, dump_field_acc, NULL);
1461 /* Hash value for fallocs_t. */
1464 malloc_hash (const void *x)
1466 return htab_hash_pointer (((const_fallocs_t)x)->func);
1469 /* This function returns nonzero if function of func_alloc_sites' X
1473 malloc_eq (const void *x, const void *y)
1475 return ((const_fallocs_t)x)->func == (const_tree)y;
1478 /* This function is a callback for traversal over a structure accesses.
1479 It frees an access represented by SLOT. */
1482 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1484 struct access_site * acc = *(struct access_site **) slot;
1486 VEC_free (tree, heap, acc->vars);
1491 /* This is a callback function for traversal over field accesses.
1492 It frees a field access represented by SLOT. */
1495 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1497 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1503 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1504 if it is not there yet. */
1507 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1515 type = TYPE_MAIN_VARIANT (type);
1517 for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1518 if (is_equal_types (t, type))
1521 if (i == VEC_length (tree, *unsuitable_types))
1522 VEC_safe_push (tree, heap, *unsuitable_types, type);
1525 /* Given a type TYPE, this function returns the name of the type. */
1528 get_type_name (tree type)
1530 if (! TYPE_NAME (type))
1533 if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1534 return IDENTIFIER_POINTER (TYPE_NAME (type));
1535 else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1536 && DECL_NAME (TYPE_NAME (type)))
1537 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1542 /* This function is a temporary hack to overcome the types problem.
1543 When several compilation units are compiled together
1544 with -combine, the TYPE_MAIN_VARIANT of the same type
1545 can appear differently in different compilation units.
1546 Therefore this function first compares type names.
1547 If there are no names, structure bodies are recursively
1551 is_equal_types (tree type1, tree type2)
1553 const char * name1,* name2;
1555 if ((!type1 && type2)
1556 ||(!type2 && type1))
1559 if (!type1 && !type2)
1562 if (TREE_CODE (type1) != TREE_CODE (type2))
1568 if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1571 name1 = get_type_name (type1);
1572 name2 = get_type_name (type2);
1574 if (name1 && name2 && !strcmp (name1, name2))
1577 if (name1 && name2 && strcmp (name1, name2))
1580 switch (TREE_CODE (type1))
1583 case REFERENCE_TYPE:
1585 return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1591 case QUAL_UNION_TYPE:
1595 /* Compare fields of structure. */
1596 for (field1 = TYPE_FIELDS (type1); field1;
1597 field1 = TREE_CHAIN (field1))
1599 tree field2 = find_field_in_struct_1 (type2, field1);
1609 if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1610 && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1618 tree max1, min1, max2, min2;
1620 if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1623 d1 = TYPE_DOMAIN (type1);
1624 d2 = TYPE_DOMAIN (type2);
1629 max1 = TYPE_MAX_VALUE (d1);
1630 max2 = TYPE_MAX_VALUE (d2);
1631 min1 = TYPE_MIN_VALUE (d1);
1632 min2 = TYPE_MIN_VALUE (d2);
1634 if (max1 && max2 && min1 && min2
1635 && TREE_CODE (max1) == TREE_CODE (max2)
1636 && TREE_CODE (max1) == INTEGER_CST
1637 && TREE_CODE (min1) == TREE_CODE (min2)
1638 && TREE_CODE (min1) == INTEGER_CST
1639 && tree_int_cst_equal (max1, max2)
1640 && tree_int_cst_equal (min1, min2))
1652 /* This function free non-field accesses from hashtable ACCS. */
1655 free_accesses (htab_t accs)
1658 htab_traverse (accs, free_accs, NULL);
1662 /* This function free field accesses hashtable F_ACCS. */
1665 free_field_accesses (htab_t f_accs)
1668 htab_traverse (f_accs, free_field_accs, NULL);
1669 htab_delete (f_accs);
1672 /* Update call graph with new edge generated by new MALLOC_STMT.
1673 The edge origin is CONTEXT function. */
1676 update_cgraph_with_malloc_call (gimple malloc_stmt, tree context)
1678 struct cgraph_node *src, *dest;
1679 tree malloc_fn_decl;
1684 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1686 src = cgraph_node (context);
1687 dest = cgraph_node (malloc_fn_decl);
1688 cgraph_create_edge (src, dest, malloc_stmt,
1689 0, 0, gimple_bb (malloc_stmt)->loop_depth);
1692 /* This function generates set of statements required
1693 to allocate number NUM of structures of type NEW_TYPE.
1694 The statements are stored in NEW_STMTS. The statement that contain
1695 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1698 create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts,
1701 tree new_malloc_size;
1702 tree malloc_fn_decl;
1705 gimple call_stmt, final_stmt;
1708 gcc_assert (num && malloc_stmt && new_type);
1709 *new_stmts = gimple_seq_alloc ();
1711 /* Generate argument to malloc as multiplication of num
1712 and size of new_type. */
1713 new_stmt = gen_size (num, new_type, &new_malloc_size);
1714 gimple_seq_add_stmt (new_stmts, new_stmt);
1716 /* Generate new call for malloc. */
1717 malloc_res = create_tmp_var (ptr_type_node, NULL);
1718 add_referenced_var (malloc_res);
1720 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1721 call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size);
1722 gimple_call_set_lhs (call_stmt, malloc_res);
1723 finalize_stmt_and_append (new_stmts, call_stmt);
1725 /* Create new cast statement. */
1726 final_stmt = get_final_alloc_stmt (malloc_stmt);
1727 gcc_assert (final_stmt);
1728 new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1729 gimple_seq_add_stmt (new_stmts, new_stmt);
1734 /* This function returns a tree representing
1735 the number of instances of structure STR_DECL allocated
1736 by allocation STMT. If new statements are generated,
1737 they are filled into NEW_STMTS_P. */
1740 gen_num_of_structs_in_malloc (gimple stmt, tree str_decl,
1741 gimple_seq *new_stmts_p)
1745 HOST_WIDE_INT struct_size_int;
1750 /* Get malloc argument. */
1751 if (!is_gimple_call (stmt))
1754 arg = gimple_call_arg (stmt, 0);
1756 if (TREE_CODE (arg) != SSA_NAME
1757 && !TREE_CONSTANT (arg))
1760 struct_size = TYPE_SIZE_UNIT (str_decl);
1761 struct_size_int = TREE_INT_CST_LOW (struct_size);
1763 gcc_assert (struct_size);
1765 if (TREE_CODE (arg) == SSA_NAME)
1770 if (is_result_of_mult (arg, &num, struct_size))
1773 num = create_tmp_var (integer_type_node, NULL);
1776 add_referenced_var (num);
1778 if (exact_log2 (struct_size_int) == -1)
1779 div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg,
1783 tree C = build_int_cst (integer_type_node,
1784 exact_log2 (struct_size_int));
1786 div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C);
1788 gimple_seq_add_stmt (new_stmts_p, div_stmt);
1789 finalize_stmt (div_stmt);
1793 if (CONSTANT_CLASS_P (arg)
1794 && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))
1795 return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1800 /* This function is a callback for traversal on new_var's hashtable.
1801 SLOT is a pointer to new_var. This function prints to dump_file
1802 an original variable and all new variables from the new_var
1803 pointed by *SLOT. */
1806 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1808 new_var n_var = *(new_var *) slot;
1813 var_type = get_type_of_var (n_var->orig_var);
1815 fprintf (dump_file, "\nOrig var: ");
1816 print_generic_expr (dump_file, n_var->orig_var, 0);
1817 fprintf (dump_file, " of type ");
1818 print_generic_expr (dump_file, var_type, 0);
1819 fprintf (dump_file, "\n");
1822 VEC_iterate (tree, n_var->new_vars, i, var); i++)
1824 var_type = get_type_of_var (var);
1826 fprintf (dump_file, " ");
1827 print_generic_expr (dump_file, var, 0);
1828 fprintf (dump_file, " of type ");
1829 print_generic_expr (dump_file, var_type, 0);
1830 fprintf (dump_file, "\n");
1835 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1838 copy_decl_attributes (tree new_decl, tree orig_decl)
1841 DECL_ARTIFICIAL (new_decl) = 1;
1842 DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1843 TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1844 TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1845 TREE_USED (new_decl) = TREE_USED (orig_decl);
1846 DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1847 TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1848 TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1850 if (TREE_CODE (orig_decl) == VAR_DECL)
1852 TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1853 DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1857 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1858 the same way as a structure type is wrapped in DECL.
1859 It returns the generated type. */
1862 gen_struct_type (tree decl, tree new_str_type)
1864 tree type_orig = get_type_of_var (decl);
1865 tree new_type = new_str_type;
1866 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1868 type_wrapper_t *wr_p;
1870 while (POINTER_TYPE_P (type_orig)
1871 || TREE_CODE (type_orig) == ARRAY_TYPE)
1873 if (POINTER_TYPE_P (type_orig))
1876 wr.domain = NULL_TREE;
1880 gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1882 wr.domain = TYPE_DOMAIN (type_orig);
1884 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1885 type_orig = TREE_TYPE (type_orig);
1888 while (VEC_length (type_wrapper_t, wrapper) != 0)
1890 wr_p = VEC_last (type_wrapper_t, wrapper);
1892 if (wr_p->wrap) /* Array. */
1893 new_type = build_array_type (new_type, wr_p->domain);
1895 new_type = build_pointer_type (new_type);
1897 VEC_pop (type_wrapper_t, wrapper);
1900 VEC_free (type_wrapper_t, heap, wrapper);
1904 /* This function generates and returns new variable name based on
1905 ORIG_DECL name, combined with index I.
1906 The form of the new name is <orig_name>.<I> . */
1909 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1911 const char *old_name;
1915 if (!DECL_NAME (orig_decl)
1916 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1919 /* If the original variable has a name, create an
1920 appropriate new name for the new variable. */
1922 old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1923 prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1924 strcpy (prefix, old_name);
1925 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1926 return get_identifier (new_name);
1929 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1932 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1936 slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1937 htab_hash_pointer (new_node->orig_var),
1942 /* This function creates and returns new_var_data node
1943 with empty new_vars and orig_var equal to VAR. */
1946 create_new_var_node (tree var, d_str str)
1950 node = (new_var) xmalloc (sizeof (struct new_var_data));
1951 node->orig_var = var;
1952 node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1956 /* Check whether the type of VAR is potential candidate for peeling.
1957 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1958 candidate type. If VAR is initialized, the type of VAR will be added
1959 to UNSUITABLE_TYPES. */
1962 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1965 bool initialized = false;
1972 /* There is no support of initialized vars. */
1973 if (TREE_CODE (var) == VAR_DECL
1974 && DECL_INITIAL (var) != NULL_TREE)
1977 type = get_type_of_var (var);
1981 type = TYPE_MAIN_VARIANT (strip_type (type));
1982 if (TREE_CODE (type) != RECORD_TYPE)
1986 if (initialized && unsuitable_types && *unsuitable_types)
1990 fprintf (dump_file, "The type ");
1991 print_generic_expr (dump_file, type, 0);
1992 fprintf (dump_file, " is initialized...Excluded.");
1994 add_unsuitable_type (unsuitable_types, type);
2004 /* Hash value for field_access_site. */
2007 field_acc_hash (const void *x)
2009 return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2012 /* This function returns nonzero if stmt of field_access_site X
2016 field_acc_eq (const void *x, const void *y)
2018 return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2021 /* This function prints an access site, defined by SLOT. */
2024 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2026 struct access_site *acc = *(struct access_site **) slot;
2030 fprintf(dump_file, "\n");
2032 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2033 fprintf(dump_file, " : ");
2035 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2037 print_generic_expr (dump_file, var, 0);
2038 fprintf(dump_file, ", ");
2043 /* This function frees memory allocated for structure clusters,
2044 starting from CLUSTER. */
2047 free_struct_cluster (struct field_cluster* cluster)
2051 if (cluster->fields_in_cluster)
2052 sbitmap_free (cluster->fields_in_cluster);
2053 if (cluster->sibling)
2054 free_struct_cluster (cluster->sibling);
2059 /* Free all allocated memory under the structure node pointed by D_NODE. */
2062 free_data_struct (d_str d_node)
2071 fprintf (dump_file, "\nRemoving data structure \"");
2072 print_generic_expr (dump_file, d_node->decl, 0);
2073 fprintf (dump_file, "\" from data_struct_list.");
2076 /* Free all space under d_node. */
2079 for (i = 0; i < d_node->num_fields; i++)
2080 free_field_accesses (d_node->fields[i].acc_sites);
2081 free (d_node->fields);
2085 free_accesses (d_node->accs);
2087 if (d_node->struct_clustering)
2088 free_struct_cluster (d_node->struct_clustering);
2090 if (d_node->new_types)
2091 VEC_free (tree, heap, d_node->new_types);
2094 /* This function creates new general and field accesses in BB. */
2097 create_new_accesses_in_bb (basic_block bb)
2102 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2103 create_new_accs_for_struct (str, bb);
2106 /* This function adds allocation sites for peeled structures.
2107 M_DATA is vector of allocation sites of function CONTEXT. */
2110 create_new_alloc_sites (fallocs_t m_data, tree context)
2115 for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2117 gimple stmt = call->stmt;
2118 d_str str = call->str;
2120 gimple_seq new_stmts = NULL;
2121 gimple last_stmt = get_final_alloc_stmt (stmt);
2125 num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2128 gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2129 insert_seq_after_stmt (last_stmt, new_stmts);
2130 last_stmt = last_stmt_tmp;
2133 /* Generate an allocation sites for each new structure type. */
2134 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
2136 gimple new_malloc_stmt = NULL;
2137 gimple last_stmt_tmp = NULL;
2140 new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2141 last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2142 insert_seq_after_stmt (last_stmt, new_stmts);
2143 update_cgraph_with_malloc_call (new_malloc_stmt, context);
2144 last_stmt = last_stmt_tmp;
2149 /* This function prints new variables from hashtable
2150 NEW_VARS_HTAB to dump_file. */
2153 dump_new_vars (htab_t new_vars_htab)
2159 htab_traverse (new_vars_htab, dump_new_var, NULL);
2162 /* Given an original variable ORIG_DECL of structure type STR,
2163 this function generates new variables of the types defined
2164 by STR->new_type. Generated types are saved in new_var node NODE.
2165 ORIG_DECL should has VAR_DECL tree_code. */
2168 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2174 VEC_iterate (tree, str->new_types, i, type); i++)
2176 tree new_decl = NULL;
2179 new_name = gen_var_name (orig_decl, i);
2180 type = gen_struct_type (orig_decl, type);
2182 if (is_global_var (orig_decl))
2183 new_decl = build_decl (VAR_DECL, new_name, type);
2186 const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2187 new_decl = create_tmp_var (type, name);
2190 copy_decl_attributes (new_decl, orig_decl);
2191 VEC_safe_push (tree, heap, node->new_vars, new_decl);
2195 /* This function creates new variables to
2196 substitute the original variable VAR_DECL and adds
2197 them to the new_var's hashtable NEW_VARS_HTAB. */
2200 create_new_var (tree var_decl, htab_t new_vars_htab)
2207 if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2210 if (!is_candidate (var_decl, &type, NULL))
2213 i = find_structure (type);
2214 if (i == VEC_length (structure, structures))
2217 str = VEC_index (structure, structures, i);
2218 node = create_new_var_node (var_decl, str);
2219 create_new_var_1 (var_decl, str, node);
2220 add_to_new_vars_htab (node, new_vars_htab);
2223 /* Hash value for new_var. */
2226 new_var_hash (const void *x)
2228 return htab_hash_pointer (((const_new_var)x)->orig_var);
2231 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2234 new_var_eq (const void *x, const void *y)
2236 return ((const_new_var)x)->orig_var == (const_tree)y;
2239 /* This function check whether a structure type represented by STR
2240 escapes due to ipa-type-escape analysis. If yes, this type is added
2241 to UNSUITABLE_TYPES vector. */
2244 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2246 tree type = str->decl;
2248 if (!ipa_type_escape_type_contained_p (type))
2252 fprintf (dump_file, "\nEscaping type is ");
2253 print_generic_expr (dump_file, type, 0);
2255 add_unsuitable_type (unsuitable_types, type);
2259 /* Hash value for access_site. */
2262 acc_hash (const void *x)
2264 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2267 /* Return nonzero if stmt of access_site X is equal to Y. */
2270 acc_eq (const void *x, const void *y)
2272 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2275 /* Given a structure declaration STRUCT_DECL, and number of fields
2276 in the structure NUM_FIELDS, this function creates and returns
2277 corresponding field_entry's. */
2279 static struct field_entry *
2280 get_fields (tree struct_decl, int num_fields)
2282 struct field_entry *list;
2283 tree t = TYPE_FIELDS (struct_decl);
2287 (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2289 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2290 if (TREE_CODE (t) == FIELD_DECL)
2292 list[idx].index = idx;
2294 list[idx].acc_sites =
2295 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2296 list[idx].count = 0;
2297 list[idx].field_mapping = NULL_TREE;
2303 /* Print non-field accesses from hashtable ACCS of structure. */
2306 dump_access_sites (htab_t accs)
2312 htab_traverse (accs, dump_acc, NULL);
2315 /* This function is a callback for alloc_sites hashtable
2316 traversal. SLOT is a pointer to fallocs_t. This function
2317 removes all allocations of the structure defined by DATA. */
2320 remove_str_allocs_in_func (void **slot, void *data)
2322 fallocs_t fallocs = *(fallocs_t *) slot;
2326 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2328 if (call->str == (d_str) data)
2329 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2337 /* This function remove all entries corresponding to the STR structure
2338 from alloc_sites hashtable. */
2341 remove_str_allocs (d_str str)
2347 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2350 /* This function removes the structure with index I from structures vector. */
2353 remove_structure (unsigned i)
2357 if (i >= VEC_length (structure, structures))
2360 str = VEC_index (structure, structures, i);
2362 /* Before removing the structure str, we have to remove its
2363 allocations from alloc_sites hashtable. */
2364 remove_str_allocs (str);
2365 free_data_struct (str);
2366 VEC_ordered_remove (structure, structures, i);
2369 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2370 COND_STMT is a condition statement to check. */
2373 is_safe_cond_expr (gimple cond_stmt)
2376 unsigned str0, str1;
2378 unsigned length = VEC_length (structure, structures);
2380 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2381 && gimple_cond_code (cond_stmt) != NE_EXPR)
2384 arg0 = gimple_cond_lhs (cond_stmt);
2385 arg1 = gimple_cond_rhs (cond_stmt);
2387 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2388 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2390 s0 = (str0 != length) ? true : false;
2391 s1 = (str1 != length) ? true : false;
2396 /* For now we allow only comparison with 0 or NULL. */
2397 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2403 /* This function excludes statements, that are
2404 part of allocation sites or field accesses, from the
2405 hashtable of general accesses. SLOT represents general
2406 access that will be checked. DATA is a pointer to
2407 exclude_data structure. */
2410 exclude_from_accs (void **slot, void *data)
2412 struct access_site *acc = *(struct access_site **) slot;
2413 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2414 d_str str = ((struct exclude_data *)data)->str;
2416 if (is_part_of_malloc (acc->stmt, fn_decl)
2417 || is_part_of_field_access (acc->stmt, str))
2419 VEC_free (tree, heap, acc->vars);
2421 htab_clear_slot (str->accs, slot);
2426 /* Callback function for walk_tree called from collect_accesses_in_bb
2427 function. DATA is the statement which is analyzed. */
2430 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2432 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2433 gimple stmt = (gimple) wi->info;
2439 switch (TREE_CODE (t))
2443 tree var = TREE_OPERAND(t, 0);
2444 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2445 unsigned i = find_structure (type);
2447 if (i != VEC_length (structure, structures))
2451 fprintf (dump_file, "\nThe type ");
2452 print_generic_expr (dump_file, type, 0);
2453 fprintf (dump_file, " has bitfield.");
2455 remove_structure (i);
2462 tree ref = TREE_OPERAND (t, 0);
2463 tree field_decl = TREE_OPERAND (t, 1);
2466 if ((TREE_CODE (ref) == INDIRECT_REF
2467 || TREE_CODE (ref) == ARRAY_REF
2468 || TREE_CODE (ref) == VAR_DECL)
2469 && TREE_CODE (field_decl) == FIELD_DECL)
2471 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2472 unsigned i = find_structure (type);
2474 if (i != VEC_length (structure, structures))
2476 d_str str = VEC_index (structure, structures, i);
2477 struct field_entry * field =
2478 find_field_in_struct (str, field_decl);
2482 struct field_access_site *acc = make_field_acc_node ();
2489 acc->field_decl = field_decl;
2491 /* Check whether the access is of the form
2492 we can deal with. */
2493 if (!decompose_access (str->decl, acc))
2497 fprintf (dump_file, "\nThe type ");
2498 print_generic_expr (dump_file, type, 0);
2500 " has complicate access in statement ");
2501 print_gimple_stmt (dump_file, stmt, 0, 0);
2504 remove_structure (i);
2509 /* Increase count of field. */
2510 basic_block bb = gimple_bb (stmt);
2511 field->count += bb->count;
2513 /* Add stmt to the acc_sites of field. */
2514 add_field_acc_to_acc_sites (acc, field->acc_sites);
2525 tree cond = COND_EXPR_COND (t);
2527 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2529 tree t = TREE_OPERAND (cond, i);
2532 walk_tree (&t, get_stmt_accesses, data, NULL);
2543 if (TREE_CODE (t) == SSA_NAME)
2544 t = SSA_NAME_VAR (t);
2546 i = find_structure (strip_type (get_type_of_var (t)));
2547 if (i != VEC_length (structure, structures))
2551 str = VEC_index (structure, structures, i);
2552 add_access_to_acc_sites (stmt, t, str->accs);
2565 /* Free structures hashtable. */
2568 free_structures (void)
2573 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2574 free_data_struct (str);
2576 VEC_free (structure, heap, structures);
2580 /* This function is a callback for traversal over new_var's hashtable.
2581 SLOT is a pointer to new_var. This function frees memory allocated
2582 for new_var and pointed by *SLOT. */
2585 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2587 new_var n_var = *(new_var *) slot;
2589 /* Free vector of new_vars. */
2590 VEC_free (tree, heap, n_var->new_vars);
2595 /* Free new_vars hashtable NEW_VARS_HTAB. */
2598 free_new_vars_htab (htab_t new_vars_htab)
2601 htab_traverse (new_vars_htab, free_new_var, NULL);
2602 htab_delete (new_vars_htab);
2603 new_vars_htab = NULL;
2606 /* This function creates new general and field accesses that appear in cfun. */
2609 create_new_accesses_for_func (void)
2613 FOR_EACH_BB_FN (bb, cfun)
2614 create_new_accesses_in_bb (bb);
2617 /* Create new allocation sites for the function represented by NODE. */
2620 create_new_alloc_sites_for_func (struct cgraph_node *node)
2622 fallocs_t fallocs = get_fallocs (node->decl);
2625 create_new_alloc_sites (fallocs, node->decl);
2628 /* For each local variable of structure type from the vector of structures
2629 this function generates new variable(s) to replace it. */
2632 create_new_local_vars (void)
2635 referenced_var_iterator rvi;
2637 new_local_vars = htab_create (num_referenced_vars,
2638 new_var_hash, new_var_eq, NULL);
2640 FOR_EACH_REFERENCED_VAR (var, rvi)
2642 if (!is_global_var (var))
2643 create_new_var (var, new_local_vars);
2647 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2648 dump_new_vars (new_local_vars);
2651 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2654 print_shift (unsigned HOST_WIDE_INT shift)
2656 unsigned HOST_WIDE_INT sh = shift;
2659 fprintf (dump_file, " ");
2662 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2665 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2666 struct field_entry * fields, int num_fields)
2670 for (i = 0; i < num_fields; i++)
2671 if (TEST_BIT (cluster->fields_in_cluster, i))
2672 fields[i].field_mapping = new_type;
2675 /* This functions builds structure with FIELDS,
2676 NAME and attributes similar to ORIG_STRUCT.
2677 It returns the newly created structure. */
2680 build_basic_struct (tree fields, tree name, tree orig_struct)
2682 tree attributes = NULL_TREE;
2686 if (TYPE_ATTRIBUTES (orig_struct))
2687 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2688 ref = make_node (RECORD_TYPE);
2689 TYPE_SIZE (ref) = 0;
2690 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2691 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2692 for (x = fields; x; x = TREE_CHAIN (x))
2694 DECL_CONTEXT (x) = ref;
2695 DECL_PACKED (x) |= TYPE_PACKED (ref);
2697 TYPE_FIELDS (ref) = fields;
2699 TYPE_NAME (ref) = name;
2704 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2705 of preparation for new structure building. NUM_FIELDS is a total
2706 number of fields in the structure. The function returns newly
2707 generated fields. */
2710 create_fields (struct field_cluster * cluster,
2711 struct field_entry * fields, int num_fields)
2714 tree new_types = NULL_TREE;
2715 tree last = NULL_TREE;
2717 for (i = 0; i < num_fields; i++)
2718 if (TEST_BIT (cluster->fields_in_cluster, i))
2720 tree new_decl = unshare_expr (fields[i].decl);
2723 new_types = new_decl;
2725 TREE_CHAIN (last) = new_decl;
2729 TREE_CHAIN (last) = NULL_TREE;
2734 /* This function creates a cluster name. The name is based on
2735 the original structure name, if it is present. It has a form:
2737 <original_struct_name>_sub.<CLUST_NUM>
2739 The original structure name is taken from the type of DECL.
2740 If an original structure name is not present, it's generated to be:
2744 The function returns identifier of the new cluster name. */
2747 gen_cluster_name (tree decl, int clust_num, int str_num)
2749 const char * orig_name = get_type_name (decl);
2750 char * tmp_name = NULL;
2756 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2758 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2759 prefix = XALLOCAVEC (char, len + 1);
2760 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2761 strlen (tmp_name ? tmp_name : orig_name));
2762 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2764 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2765 return get_identifier (new_name);
2768 /* This function checks whether the structure STR has bitfields.
2769 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2772 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2774 tree type = str->decl;
2777 for (i = 0; i < str->num_fields; i++)
2778 if (DECL_BIT_FIELD (str->fields[i].decl))
2780 add_unsuitable_type (unsuitable_types, type);
2783 fprintf (dump_file, "\nType ");
2784 print_generic_expr (dump_file, type, 0);
2785 fprintf (dump_file, "\nescapes due to bitfield ");
2786 print_generic_expr (dump_file, str->fields[i].decl, 0);
2792 /* This function adds to UNSUITABLE_TYPES those types that escape
2793 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2796 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2801 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2802 check_type_escape (str, unsuitable_types);
2805 /* If a structure type is a return type of any function,
2806 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2809 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2811 struct cgraph_node *c_node;
2813 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2815 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2819 ret_t = strip_type (ret_t);
2820 if (TREE_CODE (ret_t) == RECORD_TYPE)
2822 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2825 fprintf (dump_file, "\nThe type \"");
2826 print_generic_expr (dump_file, ret_t, 0);
2828 "\" is return type of function...Excluded.");
2835 /* This function looks for parameters of local functions
2836 which are of structure types, or derived from them (arrays
2837 of structures, pointers to structures, or their combinations).
2838 We are not handling peeling of such structures right now.
2839 The found structures types are added to UNSUITABLE_TYPES vector. */
2842 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2844 struct cgraph_node *c_node;
2846 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2847 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2849 tree fn = c_node->decl;
2852 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2854 tree type = TREE_TYPE (arg);
2856 type = strip_type (type);
2857 if (TREE_CODE (type) == RECORD_TYPE)
2859 add_unsuitable_type (unsuitable_types,
2860 TYPE_MAIN_VARIANT (type));
2863 fprintf (dump_file, "\nPointer to type \"");
2864 print_generic_expr (dump_file, type, 0);
2866 "\" is passed to local function...Excluded.");
2873 /* This function analyzes structure form of structures
2874 potential for transformation. If we are not capable to transform
2875 structure of some form, we remove it from the structures hashtable.
2876 Right now we cannot handle nested structs, when nesting is
2877 through any level of pointers or arrays.
2879 TBD: release these constrains in future.
2881 Note, that in this function we suppose that all structures
2882 in the program are members of the structures hashtable right now,
2883 without excluding escaping types. */
2886 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2890 for (i = 0; i < str->num_fields; i++)
2892 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2894 if (TREE_CODE (f_type) == RECORD_TYPE)
2896 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2897 add_unsuitable_type (unsuitable_types, str->decl);
2900 fprintf (dump_file, "\nType ");
2901 print_generic_expr (dump_file, f_type, 0);
2902 fprintf (dump_file, " is a field in the structure ");
2903 print_generic_expr (dump_file, str->decl, 0);
2904 fprintf (dump_file, ". Escaping...");
2910 /* This function adds a structure TYPE to the vector of structures,
2911 if it's not already there. */
2914 add_structure (tree type)
2916 struct data_structure node;
2920 type = TYPE_MAIN_VARIANT (type);
2922 i = find_structure (type);
2924 if (i != VEC_length (structure, structures))
2927 num_fields = fields_length (type);
2929 node.num_fields = num_fields;
2930 node.fields = get_fields (type, num_fields);
2931 node.struct_clustering = NULL;
2932 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2933 node.new_types = VEC_alloc (tree, heap, num_fields);
2936 VEC_safe_push (structure, heap, structures, &node);
2940 fprintf (dump_file, "\nAdding data structure \"");
2941 print_generic_expr (dump_file, type, 0);
2942 fprintf (dump_file, "\" to data_struct_list.");
2946 /* This function adds an allocation site to alloc_sites hashtable.
2947 The allocation site appears in STMT of function FN_DECL and
2948 allocates the structure represented by STR. */
2951 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2953 fallocs_t fallocs = NULL;
2954 alloc_site_t m_call;
2960 (fallocs_t) htab_find_with_hash (alloc_sites,
2961 fn_decl, htab_hash_pointer (fn_decl));
2967 fallocs = (fallocs_t)
2968 xmalloc (sizeof (struct func_alloc_sites));
2969 fallocs->func = fn_decl;
2970 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
2971 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
2972 htab_hash_pointer (fn_decl), INSERT);
2975 VEC_safe_push (alloc_site_t, heap,
2976 fallocs->allocs, &m_call);
2980 fprintf (dump_file, "\nAdding stmt ");
2981 print_gimple_stmt (dump_file, stmt, 0, 0);
2982 fprintf (dump_file, " to list of mallocs.");
2986 /* This function returns true if the result of STMT, that contains a call
2987 to an allocation function, is cast to one of the structure types.
2988 STMT should be of the form: T.2 = <alloc_func> (T.1);
2989 If true, I_P contains an index of an allocated structure.
2990 Otherwise I_P contains the length of the vector of structures. */
2993 is_alloc_of_struct (gimple stmt, unsigned *i_p)
2999 final_stmt = get_final_alloc_stmt (stmt);
3004 /* final_stmt should be of the form:
3005 T.3 = (struct_type *) T.2; */
3007 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3010 lhs = gimple_assign_lhs (final_stmt);
3012 type = get_type_of_var (lhs);
3017 if (!POINTER_TYPE_P (type)
3018 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3021 *i_p = find_structure (strip_type (type));
3023 if (*i_p == VEC_length (structure, structures))
3029 /* This function prints non-field and field accesses
3030 of the structure STR. */
3033 dump_accs (d_str str)
3037 fprintf (dump_file, "\nAccess sites of struct ");
3038 print_generic_expr (dump_file, str->decl, 0);
3040 for (i = 0; i < str->num_fields; i++)
3042 fprintf (dump_file, "\nAccess site of field ");
3043 print_generic_expr (dump_file, str->fields[i].decl, 0);
3044 dump_field_acc_sites (str->fields[i].acc_sites);
3045 fprintf (dump_file, ":\n");
3047 fprintf (dump_file, "\nGeneral access sites\n");
3048 dump_access_sites (str->accs);
3051 /* This function checks whether an access statement, pointed by SLOT,
3052 is a condition we are capable to transform. It returns false if not,
3053 setting bool *DATA to false. */
3056 safe_cond_expr_check (void **slot, void *data)
3058 struct access_site *acc = *(struct access_site **) slot;
3060 if (gimple_code (acc->stmt) == GIMPLE_COND
3061 && !is_safe_cond_expr (acc->stmt))
3065 fprintf (dump_file, "\nUnsafe conditional statement ");
3066 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3068 *(bool *) data = false;
3074 /* This function excludes statements that are part of allocation sites and
3075 field accesses from the hashtable of general accesses of the structure
3076 type STR. Only accesses that belong to the function represented by
3077 NODE are treated. */
3080 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3082 struct exclude_data dt;
3084 dt.fn_decl = node->decl;
3087 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3090 /* Collect accesses to the structure types that appear in basic block BB. */
3093 collect_accesses_in_bb (basic_block bb)
3095 gimple_stmt_iterator bsi;
3096 struct walk_stmt_info wi;
3098 memset (&wi, 0, sizeof (wi));
3100 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3102 gimple stmt = gsi_stmt (bsi);
3104 /* In asm stmt we cannot always track the arguments,
3105 so we just give up. */
3106 if (gimple_code (stmt) == GIMPLE_ASM)
3112 wi.info = (void *) stmt;
3113 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3117 /* This function generates cluster substructure that contains FIELDS.
3118 The cluster added to the set of clusters of the structure STR. */
3121 gen_cluster (sbitmap fields, d_str str)
3123 struct field_cluster *crr_cluster = NULL;
3126 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3127 crr_cluster->sibling = str->struct_clustering;
3128 str->struct_clustering = crr_cluster;
3129 crr_cluster->fields_in_cluster = fields;
3132 /* This function peels a field with the index I from the structure DS. */
3135 peel_field (int i, d_str ds)
3137 struct field_cluster *crr_cluster = NULL;
3140 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3141 crr_cluster->sibling = ds->struct_clustering;
3142 ds->struct_clustering = crr_cluster;
3143 crr_cluster->fields_in_cluster =
3144 sbitmap_alloc ((unsigned int) ds->num_fields);
3145 sbitmap_zero (crr_cluster->fields_in_cluster);
3146 SET_BIT (crr_cluster->fields_in_cluster, i);
3149 /* This function calculates maximum field count in
3150 the structure STR. */
3153 get_max_field_count (d_str str)
3158 for (i = 0; i < str->num_fields; i++)
3159 if (str->fields[i].count > max)
3160 max = str->fields[i].count;
3165 /* Do struct-reorg transformation for individual function
3166 represented by NODE. All structure types relevant
3167 for this function are transformed. */
3170 do_reorg_for_func (struct cgraph_node *node)
3172 create_new_local_vars ();
3173 create_new_alloc_sites_for_func (node);
3174 create_new_accesses_for_func ();
3175 update_ssa (TODO_update_ssa);
3176 cleanup_tree_cfg ();
3178 /* Free auxiliary data representing local variables. */
3179 free_new_vars_htab (new_local_vars);
3182 /* Print structure TYPE, its name, if it exists, and body.
3183 INDENT defines the level of indentation (similar
3184 to the option -i of indent command). SHIFT parameter
3185 defines a number of spaces by which a structure will
3186 be shifted right. */
3189 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3190 unsigned HOST_WIDE_INT shift)
3192 const char *struct_name;
3195 if (!type || !dump_file)
3198 if (TREE_CODE (type) != RECORD_TYPE)
3200 print_generic_expr (dump_file, type, 0);
3204 print_shift (shift);
3205 struct_name = get_type_name (type);
3206 fprintf (dump_file, "struct ");
3208 fprintf (dump_file, "%s\n",struct_name);
3209 print_shift (shift);
3210 fprintf (dump_file, "{\n");
3212 for (field = TYPE_FIELDS (type); field;
3213 field = TREE_CHAIN (field))
3215 unsigned HOST_WIDE_INT s = indent;
3216 tree f_type = TREE_TYPE (field);
3218 print_shift (shift);
3220 fprintf (dump_file, " ");
3221 dump_struct_type (f_type, indent, shift + indent);
3222 fprintf(dump_file, " ");
3223 print_generic_expr (dump_file, field, 0);
3224 fprintf(dump_file, ";\n");
3226 print_shift (shift);
3227 fprintf (dump_file, "}\n");
3230 /* This function creates new structure types to replace original type,
3231 indicated by STR->decl. The names of the new structure types are
3232 derived from the original structure type. If the original structure
3233 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3236 create_new_type (d_str str, int *str_num)
3238 int cluster_num = 0;
3240 struct field_cluster *cluster = str->struct_clustering;
3243 tree name = gen_cluster_name (str->decl, cluster_num,
3249 fields = create_fields (cluster, str->fields,
3251 new_type = build_basic_struct (fields, name, str->decl);
3253 update_fields_mapping (cluster, new_type,
3254 str->fields, str->num_fields);
3256 VEC_safe_push (tree, heap, str->new_types, new_type);
3257 cluster = cluster->sibling;
3262 /* This function is a callback for alloc_sites hashtable
3263 traversal. SLOT is a pointer to fallocs_t.
3264 This function frees memory pointed by *SLOT. */
3267 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3269 fallocs_t fallocs = *(fallocs_t *) slot;
3271 VEC_free (alloc_site_t, heap, fallocs->allocs);
3276 /* Remove structures collected in UNSUITABLE_TYPES
3277 from structures vector. */
3280 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3286 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3287 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3288 if (is_equal_types (str->decl, type))
3290 remove_structure (i);
3295 /* Exclude structure types with bitfields.
3296 We would not want to interfere with other optimizations
3297 that can be done in this case. The structure types with
3298 bitfields are added to UNSUITABLE_TYPES vector. */
3301 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3306 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3307 check_bitfields (str, unsuitable_types);
3310 /* This function checks three types of escape. A structure type escapes:
3312 1. if it's a type of parameter of a local function.
3313 2. if it's a type of function return value.
3314 3. if it escapes as a result of ipa-type-escape analysis.
3316 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3319 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3321 exclude_types_passed_to_local_func (unsuitable_types);
3322 exclude_returned_types (unsuitable_types);
3323 exclude_escaping_types_1 (unsuitable_types);
3326 /* This function analyzes whether the form of
3327 structure is such that we are capable to transform it.
3328 Nested structures are checked here. Unsuitable structure
3329 types are added to UNSUITABLE_TYPE vector. */
3332 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3337 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3338 check_struct_form (str, unsuitable_types);
3341 /* This function looks for structure types instantiated in the program.
3342 The candidate types are added to the structures vector.
3343 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3346 build_data_structure (VEC (tree, heap) **unsuitable_types)
3350 struct varpool_node *current_varpool;
3351 struct cgraph_node *c_node;
3353 /* Check global variables. */
3354 FOR_EACH_STATIC_VARIABLE (current_varpool)
3356 var = current_varpool->decl;
3357 if (is_candidate (var, &type, unsuitable_types))
3358 add_structure (type);
3361 /* Now add structures that are types of function parameters and
3363 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3365 enum availability avail =
3366 cgraph_function_body_availability (c_node);
3368 /* We need AVAIL_AVAILABLE for main function. */
3369 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3371 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3373 for (var = DECL_ARGUMENTS (c_node->decl); var;
3374 var = TREE_CHAIN (var))
3375 if (is_candidate (var, &type, unsuitable_types))
3376 add_structure (type);
3378 /* Check function local variables. */
3379 for (var_list = fn->local_decls; var_list;
3380 var_list = TREE_CHAIN (var_list))
3382 var = TREE_VALUE (var_list);
3384 if (is_candidate (var, &type, unsuitable_types))
3385 add_structure (type);
3391 /* This function returns true if the program contains
3392 a call to user defined allocation function, or other
3393 functions that can interfere with struct-reorg optimizations. */
3396 program_redefines_malloc_p (void)
3398 struct cgraph_node *c_node;
3399 struct cgraph_node *c_node2;
3400 struct cgraph_edge *c_edge;
3404 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3406 fndecl = c_node->decl;
3408 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3410 c_node2 = c_edge->callee;
3411 fndecl2 = c_node2->decl;
3412 if (is_gimple_call (c_edge->call_stmt))
3414 const char * fname = get_name (fndecl2);
3416 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3417 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3418 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3419 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3422 /* Check that there is no __builtin_object_size,
3423 __builtin_offsetof, or realloc's in the program. */
3424 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3425 || !strcmp (fname, "__builtin_offsetof")
3426 || !strcmp (fname, "realloc"))
3435 /* In this function we assume that an allocation statement
3437 var = (type_cast) malloc (size);
3439 is converted into the following set of statements:
3443 T.3 = (type_cast) T.2;
3446 In this function we collect into alloc_sites the allocation
3447 sites of variables of structure types that are present
3448 in structures vector. */
3451 collect_alloc_sites (void)
3453 struct cgraph_node *node;
3454 struct cgraph_edge *cs;
3456 for (node = cgraph_nodes; node; node = node->next)
3457 if (node->analyzed && node->decl)
3459 for (cs = node->callees; cs; cs = cs->next_callee)
3461 gimple stmt = cs->call_stmt;
3467 if (is_gimple_call (stmt)
3468 && (decl = gimple_call_fndecl (stmt))
3469 && gimple_call_lhs (stmt))
3473 if (is_alloc_of_struct (stmt, &i))
3475 /* We support only malloc now. */
3476 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3480 str = VEC_index (structure, structures, i);
3481 add_alloc_site (node->decl, stmt, str);
3488 "\nUnsupported allocation function ");
3489 print_gimple_stmt (dump_file, stmt, 0, 0);
3491 remove_structure (i);
3500 /* Print collected accesses. */
3503 dump_accesses (void)
3511 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3515 /* This function checks whether the accesses of structures in condition
3516 expressions are of the kind we are capable to transform.
3517 If not, such structures are removed from the vector of structures. */
3520 check_cond_exprs (void)
3526 while (VEC_iterate (structure, structures, i, str))
3531 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3533 remove_structure (i);
3539 /* We exclude from non-field accesses of the structure
3540 all statements that will be treated as part of the structure
3541 allocation sites or field accesses. */
3544 exclude_alloc_and_field_accs (struct cgraph_node *node)
3549 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3550 exclude_alloc_and_field_accs_1 (str, node);
3553 /* This function collects accesses of the fields of the structures
3554 that appear at function FN. */
3557 collect_accesses_in_func (struct function *fn)
3564 /* Collect accesses for each basic blocks separately. */
3565 FOR_EACH_BB_FN (bb, fn)
3566 collect_accesses_in_bb (bb);
3569 /* This function summarizes counts of the fields into the structure count. */
3572 sum_counts (d_str str, gcov_type *hottest)
3577 for (i = 0; i < str->num_fields; i++)
3581 fprintf (dump_file, "\nCounter of field \"");
3582 print_generic_expr (dump_file, str->fields[i].decl, 0);
3583 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3584 str->fields[i].count);
3586 str->count += str->fields[i].count;
3591 fprintf (dump_file, "\nCounter of struct \"");
3592 print_generic_expr (dump_file, str->decl, 0);
3593 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3596 if (str->count > *hottest)
3597 *hottest = str->count;
3600 /* This function peels the field into separate structure if it's
3601 sufficiently hot, i.e. if its count provides at least 90% of
3602 the maximum field count in the structure. */
3605 peel_hot_fields (d_str str)
3607 gcov_type max_field_count;
3608 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3611 sbitmap_ones (fields_left);
3613 (gcov_type) (get_max_field_count (str)/100)*90;
3615 str->struct_clustering = NULL;
3617 for (i = 0; i < str->num_fields; i++)
3619 if (str->count >= max_field_count)
3621 RESET_BIT (fields_left, i);
3622 peel_field (i, str);
3626 i = sbitmap_first_set_bit (fields_left);
3628 gen_cluster (fields_left, str);
3630 sbitmap_free (fields_left);
3633 /* This function is a helper for do_reorg. It goes over
3634 functions in call graph and performs actual transformation
3640 struct cgraph_node *node;
3642 /* Initialize the default bitmap obstack. */
3643 bitmap_obstack_initialize (NULL);
3645 for (node = cgraph_nodes; node; node = node->next)
3646 if (node->analyzed && node->decl && !node->next_clone)
3648 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3649 current_function_decl = node->decl;
3651 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3652 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3653 do_reorg_for_func (node);
3654 free_dominance_info (CDI_DOMINATORS);
3655 free_dominance_info (CDI_POST_DOMINATORS);
3656 current_function_decl = NULL;
3661 bitmap_obstack_release (NULL);
3664 /* This function creates new global struct variables.
3665 For each original variable, the set of new variables
3666 is created with the new structure types corresponding
3667 to the structure type of original variable.
3668 Only VAR_DECL variables are treated by this function. */
3671 create_new_global_vars (void)
3673 struct varpool_node *current_varpool;
3674 unsigned HOST_WIDE_INT i;
3675 unsigned HOST_WIDE_INT varpool_size = 0;
3677 for (i = 0; i < 2; i++)
3680 new_global_vars = htab_create (varpool_size,
3681 new_var_hash, new_var_eq, NULL);
3682 FOR_EACH_STATIC_VARIABLE(current_varpool)
3684 tree var_decl = current_varpool->decl;
3686 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3691 create_new_var (var_decl, new_global_vars);
3695 if (new_global_vars)
3696 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3699 /* Dump all new types generated by this optimization. */
3702 dump_new_types (void)
3711 fprintf (dump_file, "\nThe following are the new types generated by"
3712 " this optimization:\n");
3714 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3718 fprintf (dump_file, "\nFor type ");
3719 dump_struct_type (str->decl, 2, 0);
3720 fprintf (dump_file, "\nthe number of new types is %d\n",
3721 VEC_length (tree, str->new_types));
3723 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3724 dump_struct_type (type, 2, 0);
3728 /* This function creates new types to replace old structure types. */
3731 create_new_types (void)
3737 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3738 create_new_type (str, &str_num);
3741 /* Free allocation sites hashtable. */
3744 free_alloc_sites (void)
3747 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3748 htab_delete (alloc_sites);
3752 /* This function collects structures potential
3753 for peeling transformation, and inserts
3754 them into structures hashtable. */
3757 collect_structures (void)
3759 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3761 structures = VEC_alloc (structure, heap, 32);
3763 /* If program contains user defined mallocs, we give up. */
3764 if (program_redefines_malloc_p ())
3767 /* Build data structures hashtable of all data structures
3769 build_data_structure (&unsuitable_types);
3771 /* This function analyzes whether the form of
3772 structure is such that we are capable to transform it.
3773 Nested structures are checked here. */
3774 analyze_struct_form (&unsuitable_types);
3776 /* This function excludes those structure types
3777 that escape compilation unit. */
3778 exclude_escaping_types (&unsuitable_types);
3780 /* We do not want to change data layout of the structures with bitfields. */
3781 exclude_types_with_bit_fields (&unsuitable_types);
3783 remove_unsuitable_types (unsuitable_types);
3784 VEC_free (tree, heap, unsuitable_types);
3787 /* Collect structure allocation sites. In case of arrays
3788 we have nothing to do. */
3791 collect_allocation_sites (void)
3793 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3794 collect_alloc_sites ();
3797 /* This function collects data accesses for the
3798 structures to be transformed. For each structure
3799 field it updates the count field in field_entry. */
3802 collect_data_accesses (void)
3804 struct cgraph_node *c_node;
3806 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3808 enum availability avail = cgraph_function_body_availability (c_node);
3810 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3812 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3814 if (!c_node->next_clone)
3815 collect_accesses_in_func (func);
3816 exclude_alloc_and_field_accs (c_node);
3820 check_cond_exprs ();
3821 /* Print collected accesses. */
3825 /* We do not bother to transform cold structures.
3826 Coldness of the structure is defined relatively
3827 to the highest structure count among the structures
3828 to be transformed. It's triggered by the compiler parameter
3830 --param struct-reorg-cold-struct-ratio=<value>
3832 where <value> ranges from 0 to 100. Structures with count ratios
3833 that are less than this parameter are considered to be cold. */
3836 exclude_cold_structs (void)
3838 gcov_type hottest = 0;
3842 /* We summarize counts of fields of a structure into the structure count. */
3843 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3844 sum_counts (str, &hottest);
3846 /* Remove cold structures from structures vector. */
3848 while (VEC_iterate (structure, structures, i, str))
3849 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3853 fprintf (dump_file, "\nThe structure ");
3854 print_generic_expr (dump_file, str->decl, 0);
3855 fprintf (dump_file, " is cold.");
3857 remove_structure (i);
3863 /* This function decomposes original structure into substructures,
3872 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3873 peel_hot_fields (str);
3877 /* Do the actual transformation for each structure
3878 from the structures hashtable. */
3883 /* Check that there is a work to do. */
3884 if (!VEC_length (structure, structures))
3887 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3894 fprintf (dump_file, "\nNumber of structures to transform is %d",
3895 VEC_length (structure, structures));
3899 /* Generate new types. */
3900 create_new_types ();
3903 /* Create new global variables. */
3904 create_new_global_vars ();
3905 dump_new_vars (new_global_vars);
3907 /* Decompose structures for each function separately. */
3910 /* Free auxiliary data collected for global variables. */
3911 free_new_vars_htab (new_global_vars);
3914 /* Free all auxiliary data used by this optimization. */
3917 free_data_structs (void)
3920 free_alloc_sites ();
3923 /* Perform structure decomposition (peeling). */
3926 reorg_structs (void)
3930 /* Collect structure types. */
3931 collect_structures ();
3933 /* Collect structure allocation sites. */
3934 collect_allocation_sites ();
3936 /* Collect structure accesses. */
3937 collect_data_accesses ();
3939 /* We transform only hot structures. */
3940 exclude_cold_structs ();
3943 /* Decompose structures into substructures, i.e. clusters. */
3947 /* Do the actual transformation for each structure
3948 from the structures hashtable. */
3951 /* Free all auxiliary data used by this optimization. */
3952 free_data_structs ();
3955 /* Struct-reorg optimization entry point function. */
3958 reorg_structs_drive (void)
3964 /* Struct-reorg optimization gate function. */
3967 struct_reorg_gate (void)
3969 return flag_ipa_struct_reorg
3970 && flag_whole_program
3974 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
3978 "ipa_struct_reorg", /* name */
3979 struct_reorg_gate, /* gate */
3980 reorg_structs_drive, /* execute */
3983 0, /* static_pass_number */
3984 TV_INTEGRATION, /* tv_id */
3985 0, /* properties_required */
3986 0, /* properties_provided */
3987 0, /* properties_destroyed */
3988 TODO_verify_ssa, /* todo_flags_start */
3989 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */