1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Olga Golovanevsky <olga@il.ibm.com>
4 (Initial version of this code was developed
5 by Caroline Tice and Mostafa Hagog.)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-flow-inline.h"
34 #include "langhooks.h"
35 #include "pointer-set.h"
42 #include "diagnostic.h"
48 #include "basic-block.h"
49 #include "tree-iterator.h"
50 #include "tree-pass.h"
51 #include "ipa-struct-reorg.h"
53 #include "ipa-type-escape.h"
54 #include "tree-dump.h"
57 /* This optimization implements structure peeling.
59 For example, given a structure type:
67 it can be peeled into two structure types as follows:
69 typedef struct and typedef struct
75 or can be fully peeled:
92 When structure type is peeled all instances and their accesses
93 in the program are updated accordingly. For example, if there is
98 and structure type str_t was peeled into two structures str_t_0
99 and str_t_1 as it was shown above, then array A will be replaced
100 by two arrays as follows:
105 The field access of field a of element i of array A: A[i].a will be
106 replaced by an access to field a of element i of array A_0: A_0[i].a.
108 This optimization also supports dynamically allocated arrays.
109 If array of structures was allocated by malloc function:
111 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
113 the allocation site will be replaced to reflect new structure types:
115 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
116 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
118 The field access through the pointer p[i].a will be changed by p_0[i].a.
120 The goal of structure peeling is to improve spatial locality.
121 For example, if one of the fields of a structure is accessed frequently
124 for (i = 0; i < N; i++)
129 the allocation of field a of str_t contiguously in memory will
130 increase the chances of fetching the field from cache.
132 The analysis part of this optimization is based on the frequency of
133 field accesses, which are collected all over the program.
134 Then the fields with the frequencies that satisfy the following condition
135 get peeled out of the structure:
137 freq(f) > C * max_field_freq_in_struct
139 where max_field_freq_in_struct is the maximum field frequency
140 in the structure. C is a constant defining which portion of
141 max_field_freq_in_struct the fields should have in order to be peeled.
143 If profiling information is provided, it is used to calculate the
144 frequency of field accesses. Otherwise, the structure is fully peeled.
146 IPA type-escape analysis is used to determine when it is safe
149 The optimization is activated by flag -fipa-struct-reorg. */
151 /* New variables created by this optimization.
152 When doing struct peeling, each variable of
153 the original struct type will be replaced by
154 the set of new variables corresponding to
155 the new structure types. */
156 struct new_var_data {
157 /* VAR_DECL for original struct type. */
159 /* Vector of new variables. */
160 VEC(tree, heap) *new_vars;
163 typedef struct new_var_data *new_var;
164 typedef const struct new_var_data *const_new_var;
166 /* This structure represents allocation site of the structure. */
167 typedef struct alloc_site
173 DEF_VEC_O (alloc_site_t);
174 DEF_VEC_ALLOC_O (alloc_site_t, heap);
176 /* Allocation sites that belong to the same function. */
177 struct func_alloc_sites
180 /* Vector of allocation sites for function. */
181 VEC (alloc_site_t, heap) *allocs;
184 typedef struct func_alloc_sites *fallocs_t;
185 typedef const struct func_alloc_sites *const_fallocs_t;
187 /* All allocation sites in the program. */
188 htab_t alloc_sites = NULL;
190 /* New global variables. Generated once for whole program. */
191 htab_t new_global_vars;
193 /* New local variables. Generated per-function. */
194 htab_t new_local_vars;
196 /* Vector of structures to be transformed. */
197 typedef struct data_structure structure;
198 DEF_VEC_O (structure);
199 DEF_VEC_ALLOC_O (structure, heap);
200 VEC (structure, heap) *structures;
202 /* Forward declarations. */
203 static bool is_equal_types (tree, tree);
205 /* Strip structure TYPE from pointers and arrays. */
208 strip_type (tree type)
210 gcc_assert (TYPE_P (type));
212 while (POINTER_TYPE_P (type)
213 || TREE_CODE (type) == ARRAY_TYPE)
214 type = TREE_TYPE (type);
219 /* This function returns type of VAR. */
222 get_type_of_var (tree var)
227 if (TREE_CODE (var) == PARM_DECL)
228 return DECL_ARG_TYPE (var);
230 return TREE_TYPE (var);
233 /* Set of actions we do for each newly generated STMT. */
236 finalize_stmt (gimple stmt)
239 mark_symbols_for_renaming (stmt);
242 /* This function finalizes STMT and appends it to the list STMTS. */
245 finalize_stmt_and_append (gimple_seq *stmts, gimple stmt)
247 gimple_seq_add_stmt (stmts, stmt);
248 finalize_stmt (stmt);
251 /* Given structure type SRT_TYPE and field FIELD,
252 this function is looking for a field with the same name
253 and type as FIELD in STR_TYPE. It returns it if found,
254 or NULL_TREE otherwise. */
257 find_field_in_struct_1 (tree str_type, tree field)
261 if (!DECL_NAME (field))
264 for (str_field = TYPE_FIELDS (str_type); str_field;
265 str_field = TREE_CHAIN (str_field))
267 const char *str_field_name;
268 const char *field_name;
270 if (!DECL_NAME (str_field))
273 str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
274 field_name = IDENTIFIER_POINTER (DECL_NAME (field));
276 gcc_assert (str_field_name);
277 gcc_assert (field_name);
279 if (!strcmp (str_field_name, field_name))
281 /* Check field types. */
282 if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
290 /* Given a field declaration FIELD_DECL, this function
291 returns corresponding field entry in structure STR. */
293 static struct field_entry *
294 find_field_in_struct (d_str str, tree field_decl)
298 tree field = find_field_in_struct_1 (str->decl, field_decl);
300 for (i = 0; i < str->num_fields; i++)
301 if (str->fields[i].decl == field)
302 return &(str->fields[i]);
307 /* This function checks whether ARG is a result of multiplication
308 of some number by STRUCT_SIZE. If yes, the function returns true
309 and this number is filled into NUM. */
312 is_result_of_mult (tree arg, tree *num, tree struct_size)
314 gimple size_def_stmt = SSA_NAME_DEF_STMT (arg);
316 /* If the allocation statement was of the form
317 D.2229_10 = <alloc_func> (D.2228_9);
318 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
320 if (size_def_stmt && is_gimple_assign (size_def_stmt))
322 tree lhs = gimple_assign_lhs (size_def_stmt);
324 /* We expect temporary here. */
325 if (!is_gimple_reg (lhs))
328 if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR)
330 tree arg0 = gimple_assign_rhs1 (size_def_stmt);
331 tree arg1 = gimple_assign_rhs2 (size_def_stmt);
333 if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
339 if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
352 /* This function returns true if access ACC corresponds to the pattern
353 generated by compiler when an address of element i of an array
354 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
355 pattern is recognized correctly, this function returns true
356 and fills missing fields in ACC. Otherwise it returns false. */
359 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
362 tree struct_size, op0, op1;
364 enum tree_code rhs_code;
366 ref_var = TREE_OPERAND (acc->ref, 0);
368 if (TREE_CODE (ref_var) != SSA_NAME)
371 acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
372 if (!(acc->ref_def_stmt)
373 || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN))
376 rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt);
378 if (rhs_code != PLUS_EXPR
379 && rhs_code != MINUS_EXPR
380 && rhs_code != POINTER_PLUS_EXPR)
383 op0 = gimple_assign_rhs1 (acc->ref_def_stmt);
384 op1 = gimple_assign_rhs2 (acc->ref_def_stmt);
386 if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1,
387 &acc->base, &acc->offset,
392 before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
394 before_cast = acc->offset;
400 if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
403 struct_size = TYPE_SIZE_UNIT (str_decl);
405 if (!is_result_of_mult (before_cast, &acc->num, struct_size))
412 /* This function checks whether the access ACC of structure type STR
413 is of the form suitable for transformation. If yes, it returns true.
417 decompose_access (tree str_decl, struct field_access_site *acc)
419 gcc_assert (acc->ref);
421 if (TREE_CODE (acc->ref) == INDIRECT_REF)
422 return decompose_indirect_ref_acc (str_decl, acc);
423 else if (TREE_CODE (acc->ref) == ARRAY_REF)
425 else if (TREE_CODE (acc->ref) == VAR_DECL)
431 /* This function creates empty field_access_site node. */
433 static inline struct field_access_site *
434 make_field_acc_node (void)
436 int size = sizeof (struct field_access_site);
438 return (struct field_access_site *) xcalloc (1, size);
441 /* This function returns the structure field access, defined by STMT,
442 if it is already in hashtable of function accesses F_ACCS. */
444 static struct field_access_site *
445 is_in_field_accs (gimple stmt, htab_t f_accs)
447 return (struct field_access_site *)
448 htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
451 /* This function adds an access ACC to the hashtable
452 F_ACCS of field accesses. */
455 add_field_acc_to_acc_sites (struct field_access_site *acc,
460 gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
461 slot = htab_find_slot_with_hash (f_accs, acc->stmt,
462 htab_hash_pointer (acc->stmt),
467 /* This function adds the VAR to vector of variables of
468 an access site defined by statement STMT. If access entry
469 with statement STMT does not exist in hashtable of
470 accesses ACCS, this function creates it. */
473 add_access_to_acc_sites (gimple stmt, tree var, htab_t accs)
475 struct access_site *acc;
477 acc = (struct access_site *)
478 htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
484 acc = (struct access_site *) xmalloc (sizeof (struct access_site));
486 acc->vars = VEC_alloc (tree, heap, 10);
487 slot = htab_find_slot_with_hash (accs, stmt,
488 htab_hash_pointer (stmt), INSERT);
492 VEC_safe_push (tree, heap, acc->vars, var);
495 /* This function adds NEW_DECL to function
496 referenced vars, and marks it for renaming. */
499 finalize_var_creation (tree new_decl)
501 add_referenced_var (new_decl);
502 mark_sym_for_renaming (new_decl);
505 /* This function finalizes VAR creation if it is a global VAR_DECL. */
508 finalize_global_creation (tree var)
510 if (TREE_CODE (var) == VAR_DECL
511 && is_global_var (var))
512 finalize_var_creation (var);
515 /* This function inserts NEW_DECL to varpool. */
518 insert_global_to_varpool (tree new_decl)
520 struct varpool_node *new_node;
522 new_node = varpool_node (new_decl);
523 notice_global_symbol (new_decl);
524 varpool_mark_needed_node (new_node);
525 varpool_finalize_decl (new_decl);
528 /* This function finalizes the creation of new variables,
529 defined by *SLOT->new_vars. */
532 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
534 new_var n_var = *(new_var *) slot;
538 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
539 finalize_var_creation (var);
543 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
544 It returns it, if found, and NULL_TREE otherwise. */
547 find_var_in_new_vars_vec (new_var var, tree new_type)
552 for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
554 tree type = strip_type(get_type_of_var (n_var));
557 if (type == new_type)
564 /* This function returns new_var node, the orig_var of which is DECL.
565 It looks for new_var's in NEW_VARS_HTAB. If not found,
566 the function returns NULL. */
569 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
571 return (new_var) htab_find_with_hash (new_vars_htab, decl,
572 htab_hash_pointer (decl));
575 /* Given original variable ORIG_VAR, this function returns
576 new variable corresponding to it of NEW_TYPE type. */
579 find_new_var_of_type (tree orig_var, tree new_type)
582 gcc_assert (orig_var && new_type);
584 if (TREE_CODE (orig_var) == SSA_NAME)
585 orig_var = SSA_NAME_VAR (orig_var);
587 var = is_in_new_vars_htab (orig_var, new_global_vars);
589 var = is_in_new_vars_htab (orig_var, new_local_vars);
591 return find_var_in_new_vars_vec (var, new_type);
594 /* This function generates stmt:
595 res = NUM * sizeof(TYPE) and returns it.
596 res is filled into RES. */
599 gen_size (tree num, tree type, tree *res)
601 tree struct_size = TYPE_SIZE_UNIT (type);
602 HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
605 *res = create_tmp_var (TREE_TYPE (num), NULL);
608 add_referenced_var (*res);
610 if (exact_log2 (struct_size_int) == -1)
612 tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
613 new_stmt = gimple_build_assign (*res, fold_build2 (MULT_EXPR,
619 tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
621 new_stmt = gimple_build_assign (*res, fold_build2 (LSHIFT_EXPR,
626 finalize_stmt (new_stmt);
630 /* This function generates and returns a statement, that cast variable
631 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
632 into RES_P. ORIG_CAST_STMT is the original cast statement. */
635 gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt,
641 lhs = gimple_assign_lhs (orig_cast_stmt);
642 new_lhs = find_new_var_of_type (lhs, new_type);
643 gcc_assert (new_lhs);
645 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0);
646 finalize_stmt (new_stmt);
651 /* This function builds an edge between BB and E->dest and updates
652 phi nodes of E->dest. It returns newly created edge. */
655 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
659 gimple_stmt_iterator si;
661 new_e = make_edge (bb, e->dest, e->flags);
663 for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si))
665 gimple phi = gsi_stmt (si);
666 arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
667 add_phi_arg (phi, arg, new_e, gimple_phi_arg_location_from_edge (phi, e));
673 /* This function inserts NEW_STMT before STMT. */
676 insert_before_stmt (gimple stmt, gimple new_stmt)
678 gimple_stmt_iterator bsi;
680 if (!stmt || !new_stmt)
683 bsi = gsi_for_stmt (stmt);
684 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
687 /* Insert NEW_STMTS after STMT. */
690 insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts)
692 gimple_stmt_iterator bsi;
694 if (!stmt || !new_stmts)
697 bsi = gsi_for_stmt (stmt);
698 gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT);
701 /* Insert NEW_STMT after STMT. */
704 insert_after_stmt (gimple stmt, gimple new_stmt)
706 gimple_stmt_iterator bsi;
708 if (!stmt || !new_stmt)
711 bsi = gsi_for_stmt (stmt);
712 gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT);
715 /* This function returns vector of allocation sites
716 that appear in function FN_DECL. */
719 get_fallocs (tree fn_decl)
721 return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
722 htab_hash_pointer (fn_decl));
725 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
726 and it is a part of allocation of a structure,
727 then it is usually followed by a cast stmt
728 p_8 = (struct str_t *) D.2225_7;
729 which is returned by this function. */
732 get_final_alloc_stmt (gimple alloc_stmt)
741 if (!is_gimple_call (alloc_stmt))
744 alloc_res = gimple_get_lhs (alloc_stmt);
746 if (TREE_CODE (alloc_res) != SSA_NAME)
749 if (!single_imm_use (alloc_res, &use_p, &final_stmt))
755 /* This function returns true if STMT is one of allocation
756 sites of function FN_DECL. It returns false otherwise. */
759 is_part_of_malloc (gimple stmt, tree fn_decl)
761 fallocs_t fallocs = get_fallocs (fn_decl);
768 for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
769 if (call->stmt == stmt
770 || get_final_alloc_stmt (call->stmt) == stmt)
776 /* Auxiliary structure for a lookup over field accesses. */
777 struct find_stmt_data
783 /* This function looks for DATA->stmt among
784 the statements involved in the field access,
785 defined by SLOT. It stops when it's found. */
788 find_in_field_accs (void **slot, void *data)
790 struct field_access_site *f_acc = *(struct field_access_site **) slot;
791 gimple stmt = ((struct find_stmt_data *)data)->stmt;
793 if (f_acc->stmt == stmt
794 || f_acc->ref_def_stmt == stmt
795 || f_acc->cast_stmt == stmt)
797 ((struct find_stmt_data *)data)->found = true;
804 /* This function checks whether STMT is part of field
805 accesses of structure STR. It returns true, if found,
806 and false otherwise. */
809 is_part_of_field_access (gimple stmt, d_str str)
813 for (i = 0; i < str->num_fields; i++)
815 struct find_stmt_data data;
819 if (str->fields[i].acc_sites)
820 htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
829 /* Auxiliary data for exclude_from_accs function. */
837 /* This function returns component_ref with the BASE and
838 field named FIELD_ID from structure TYPE. */
841 build_comp_ref (tree base, tree field_id, tree type)
847 /* Find field of structure type with the same name as field_id. */
848 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
850 if (DECL_NAME (field) == field_id)
859 return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
863 /* This struct represent data used for walk_tree
864 called from function find_pos_in_stmt.
865 - ref is a tree to be found,
866 - and pos is a pointer that points to ref in stmt. */
874 /* This is a callback function for walk_tree, called from
875 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
876 When *TP is equal to DATA->ref, the walk_tree stops,
877 and found position, equal to TP, is assigned to DATA->pos. */
880 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
882 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
883 struct ref_pos *r_pos = (struct ref_pos *) wi->info;
884 tree ref = r_pos->ref;
887 if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref))
898 /* This function looks for the pointer of REF in STMT,
899 It returns it, if found, and NULL otherwise. */
902 find_pos_in_stmt (gimple stmt, tree ref)
904 struct ref_pos r_pos;
905 struct walk_stmt_info wi;
909 memset (&wi, 0, sizeof (wi));
911 walk_gimple_op (stmt, find_pos_in_stmt_1, &wi);
916 /* This structure is used to represent array
917 or pointer-to wrappers of structure type.
918 For example, if type1 is structure type,
919 then for type1 ** we generate two type_wrapper
920 structures with wrap = 0 each one.
921 It's used to unwind the original type up to
922 structure type, replace it with the new structure type
923 and wrap it back in the opposite order. */
925 typedef struct type_wrapper
927 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
930 /* Relevant for arrays as domain or index. */
934 DEF_VEC_O (type_wrapper_t);
935 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
937 /* This function replace field access ACC by the new
938 field access of structure type NEW_TYPE. */
941 replace_field_acc (struct field_access_site *acc, tree new_type)
943 tree ref_var = acc->ref;
948 tree field_id = DECL_NAME (acc->field_decl);
949 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
950 type_wrapper_t *wr_p = NULL;
952 while (TREE_CODE (ref_var) == INDIRECT_REF
953 || TREE_CODE (ref_var) == ARRAY_REF)
957 if ( TREE_CODE (ref_var) == INDIRECT_REF)
965 wr.domain = TREE_OPERAND (ref_var, 1);
968 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
969 ref_var = TREE_OPERAND (ref_var, 0);
972 new_ref = find_new_var_of_type (ref_var, new_type);
973 finalize_global_creation (new_ref);
975 while (VEC_length (type_wrapper_t, wrapper) != 0)
977 tree type = TREE_TYPE (TREE_TYPE (new_ref));
979 wr_p = VEC_last (type_wrapper_t, wrapper);
980 if (wr_p->wrap) /* Array. */
981 new_ref = build4 (ARRAY_REF, type, new_ref,
982 wr_p->domain, NULL_TREE, NULL_TREE);
984 new_ref = build1 (INDIRECT_REF, type, new_ref);
985 VEC_pop (type_wrapper_t, wrapper);
988 new_acc = build_comp_ref (new_ref, field_id, new_type);
989 VEC_free (type_wrapper_t, heap, wrapper);
991 if (is_gimple_assign (acc->stmt))
993 lhs = gimple_assign_lhs (acc->stmt);
994 rhs = gimple_assign_rhs1 (acc->stmt);
996 if (lhs == acc->comp_ref)
997 gimple_assign_set_lhs (acc->stmt, new_acc);
998 else if (rhs == acc->comp_ref)
999 gimple_assign_set_rhs1 (acc->stmt, new_acc);
1002 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1009 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1014 finalize_stmt (acc->stmt);
1017 /* This function replace field access ACC by a new field access
1018 of structure type NEW_TYPE. */
1021 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1024 if (TREE_CODE (acc->ref) == INDIRECT_REF
1025 ||TREE_CODE (acc->ref) == ARRAY_REF
1026 ||TREE_CODE (acc->ref) == VAR_DECL)
1027 replace_field_acc (acc, new_type);
1032 /* This function looks for d_str, represented by TYPE, in the structures
1033 vector. If found, it returns an index of found structure. Otherwise
1034 it returns a length of the structures vector. */
1037 find_structure (tree type)
1042 type = TYPE_MAIN_VARIANT (type);
1044 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1045 if (is_equal_types (str->decl, type))
1048 return VEC_length (structure, structures);
1051 /* In this function we create new statements that have the same
1052 form as ORIG_STMT, but of type NEW_TYPE. The statements
1053 treated by this function are simple assignments,
1054 like assignments: p.8_7 = p; or statements with rhs of
1055 tree codes PLUS_EXPR and MINUS_EXPR. */
1058 create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset)
1063 tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1065 lhs = gimple_assign_lhs (orig_stmt);
1067 gcc_assert (TREE_CODE (lhs) == VAR_DECL
1068 || TREE_CODE (lhs) == SSA_NAME);
1070 new_lhs = find_new_var_of_type (lhs, new_type);
1071 gcc_assert (new_lhs);
1072 finalize_var_creation (new_lhs);
1074 switch (gimple_assign_rhs_code (orig_stmt))
1078 case POINTER_PLUS_EXPR:
1080 tree op0 = gimple_assign_rhs1 (orig_stmt);
1081 tree op1 = gimple_assign_rhs2 (orig_stmt);
1082 unsigned str0, str1;
1083 unsigned length = VEC_length (structure, structures);
1086 str0 = find_structure (strip_type (get_type_of_var (op0)));
1087 str1 = find_structure (strip_type (get_type_of_var (op1)));
1088 gcc_assert ((str0 != length) || (str1 != length));
1091 new_op0 = find_new_var_of_type (op0, new_type);
1093 new_op1 = find_new_var_of_type (op1, new_type);
1106 new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt),
1107 new_lhs, new_op0, new_op1);
1108 finalize_stmt (new_stmt);
1113 /* Given a field access F_ACC of the FIELD, this function
1114 replaces it by the new field access. */
1117 create_new_field_access (struct field_access_site *f_acc,
1118 struct field_entry field)
1120 tree new_type = field.field_mapping;
1125 tree cast_res = NULL;
1129 mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1130 insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1133 if (f_acc->cast_stmt)
1135 cast_stmt = gen_cast_stmt (size_res, new_type,
1136 f_acc->cast_stmt, &cast_res);
1137 insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1140 if (f_acc->ref_def_stmt)
1148 new_stmt = create_base_plus_offset (f_acc->ref_def_stmt,
1150 insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1153 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1154 D.2162_18 by an appropriate variable of new_type type. */
1155 replace_field_access_stmt (f_acc, new_type);
1158 /* This function creates a new condition statement
1159 corresponding to the original COND_STMT, adds new basic block
1160 and redirects condition edges. NEW_VAR is a new condition
1161 variable located in the condition statement at the position POS. */
1164 create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos)
1167 edge true_e = NULL, false_e = NULL;
1169 gimple_stmt_iterator si;
1171 extract_true_false_edges_from_block (gimple_bb (cond_stmt),
1174 new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1175 pos == 0 ? new_var : gimple_cond_lhs (cond_stmt),
1176 pos == 1 ? new_var : gimple_cond_rhs (cond_stmt),
1180 finalize_stmt (new_stmt);
1182 /* Create new basic block after bb. */
1183 new_bb = create_empty_bb (gimple_bb (cond_stmt));
1185 /* Add new condition stmt to the new_bb. */
1186 si = gsi_start_bb (new_bb);
1187 gsi_insert_after (&si, new_stmt, GSI_NEW_STMT);
1189 /* Create false and true edges from new_bb. */
1190 make_edge_and_fix_phis_of_dest (new_bb, true_e);
1191 make_edge_and_fix_phis_of_dest (new_bb, false_e);
1193 /* Redirect one of original edges to point to new_bb. */
1194 if (gimple_cond_code (cond_stmt) == NE_EXPR)
1195 redirect_edge_succ (true_e, new_bb);
1197 redirect_edge_succ (false_e, new_bb);
1200 /* This function creates new condition statements corresponding
1201 to original condition STMT, one for each new type, and
1202 recursively redirect edges to newly generated basic blocks. */
1205 create_new_stmts_for_cond_expr (gimple stmt)
1207 tree arg0, arg1, arg;
1208 unsigned str0, str1;
1214 unsigned length = VEC_length (structure, structures);
1216 gcc_assert (gimple_cond_code (stmt) == EQ_EXPR
1217 || gimple_cond_code (stmt) == NE_EXPR);
1219 arg0 = gimple_cond_lhs (stmt);
1220 arg1 = gimple_cond_rhs (stmt);
1222 str0 = find_structure (strip_type (get_type_of_var (arg0)));
1223 str1 = find_structure (strip_type (get_type_of_var (arg1)));
1225 s0 = (str0 != length) ? true : false;
1226 s1 = (str1 != length) ? true : false;
1228 gcc_assert (s0 || s1);
1229 /* For now we allow only comparison with 0 or NULL. */
1230 gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1232 str = integer_zerop (arg0) ?
1233 VEC_index (structure, structures, str1):
1234 VEC_index (structure, structures, str0);
1235 arg = integer_zerop (arg0) ? arg1 : arg0;
1236 pos = integer_zerop (arg0) ? 1 : 0;
1238 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1242 new_arg = find_new_var_of_type (arg, type);
1243 create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1247 /* Create a new general access to replace original access ACC
1248 for structure type NEW_TYPE. */
1251 create_general_new_stmt (struct access_site *acc, tree new_type)
1253 gimple old_stmt = acc->stmt;
1255 gimple new_stmt = gimple_copy (old_stmt);
1258 /* We are really building a new stmt, clear the virtual operands. */
1259 if (gimple_has_mem_ops (new_stmt))
1261 gimple_set_vuse (new_stmt, NULL_TREE);
1262 gimple_set_vdef (new_stmt, NULL_TREE);
1265 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1268 tree new_var = find_new_var_of_type (var, new_type);
1269 tree lhs, rhs = NULL_TREE;
1271 gcc_assert (new_var);
1272 finalize_var_creation (new_var);
1274 if (is_gimple_assign (new_stmt))
1276 lhs = gimple_assign_lhs (new_stmt);
1278 if (TREE_CODE (lhs) == SSA_NAME)
1279 lhs = SSA_NAME_VAR (lhs);
1280 if (gimple_assign_rhs_code (new_stmt) == SSA_NAME)
1281 rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt));
1283 /* It can happen that rhs is a constructor.
1284 Then we have to replace it to be of new_type. */
1285 if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR)
1287 /* Dealing only with empty constructors right now. */
1288 gcc_assert (VEC_empty (constructor_elt,
1289 CONSTRUCTOR_ELTS (rhs)));
1290 rhs = build_constructor (new_type, 0);
1291 gimple_assign_set_rhs1 (new_stmt, rhs);
1295 gimple_assign_set_lhs (new_stmt, new_var);
1296 else if (rhs == var)
1297 gimple_assign_set_rhs1 (new_stmt, new_var);
1300 pos = find_pos_in_stmt (new_stmt, var);
1302 /* ??? This misses adjustments to the type of the
1303 INDIRECT_REF we possibly replace the operand of. */
1309 pos = find_pos_in_stmt (new_stmt, var);
1315 finalize_stmt (new_stmt);
1319 /* For each new type in STR this function creates new general accesses
1320 corresponding to the original access ACC. */
1323 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1326 gimple stmt = acc->stmt;
1329 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1333 new_stmt = create_general_new_stmt (acc, type);
1334 insert_after_stmt (stmt, new_stmt);
1338 /* This function creates a new general access of structure STR
1339 to replace the access ACC. */
1342 create_new_general_access (struct access_site *acc, d_str str)
1344 gimple stmt = acc->stmt;
1345 switch (gimple_code (stmt))
1348 create_new_stmts_for_cond_expr (stmt);
1352 create_new_stmts_for_general_acc (acc, str);
1356 /* Auxiliary data for creation of accesses. */
1357 struct create_acc_data
1364 /* This function creates a new general access, defined by SLOT.
1365 DATA is a pointer to create_acc_data structure. */
1368 create_new_acc (void **slot, void *data)
1370 struct access_site *acc = *(struct access_site **) slot;
1371 basic_block bb = ((struct create_acc_data *)data)->bb;
1372 d_str str = ((struct create_acc_data *)data)->str;
1374 if (gimple_bb (acc->stmt) == bb)
1375 create_new_general_access (acc, str);
1379 /* This function creates a new field access, defined by SLOT.
1380 DATA is a pointer to create_acc_data structure. */
1383 create_new_field_acc (void **slot, void *data)
1385 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1386 basic_block bb = ((struct create_acc_data *)data)->bb;
1387 d_str str = ((struct create_acc_data *)data)->str;
1388 int i = ((struct create_acc_data *)data)->field_index;
1390 if (gimple_bb (f_acc->stmt) == bb)
1391 create_new_field_access (f_acc, str->fields[i]);
1395 /* This function creates new accesses for the structure
1396 type STR in basic block BB. */
1399 create_new_accs_for_struct (d_str str, basic_block bb)
1402 struct create_acc_data dt;
1406 dt.field_index = -1;
1408 for (i = 0; i < str->num_fields; i++)
1412 if (str->fields[i].acc_sites)
1413 htab_traverse (str->fields[i].acc_sites,
1414 create_new_field_acc, &dt);
1417 htab_traverse (str->accs, create_new_acc, &dt);
1420 /* This function inserts new variables from new_var,
1421 defined by SLOT, into varpool. */
1424 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1426 new_var n_var = *(new_var *) slot;
1430 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1431 insert_global_to_varpool (var);
1435 /* This function prints a field access site, defined by SLOT. */
1438 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1440 struct field_access_site *f_acc =
1441 *(struct field_access_site **) slot;
1443 fprintf(dump_file, "\n");
1445 print_gimple_stmt (dump_file, f_acc->stmt, 0, 0);
1446 if (f_acc->ref_def_stmt)
1447 print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0);
1448 if (f_acc->cast_stmt)
1449 print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0);
1453 /* Print field accesses from hashtable F_ACCS. */
1456 dump_field_acc_sites (htab_t f_accs)
1462 htab_traverse (f_accs, dump_field_acc, NULL);
1465 /* Hash value for fallocs_t. */
1468 malloc_hash (const void *x)
1470 return htab_hash_pointer (((const_fallocs_t)x)->func);
1473 /* This function returns nonzero if function of func_alloc_sites' X
1477 malloc_eq (const void *x, const void *y)
1479 return ((const_fallocs_t)x)->func == (const_tree)y;
1482 /* This function is a callback for traversal over a structure accesses.
1483 It frees an access represented by SLOT. */
1486 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1488 struct access_site * acc = *(struct access_site **) slot;
1490 VEC_free (tree, heap, acc->vars);
1495 /* This is a callback function for traversal over field accesses.
1496 It frees a field access represented by SLOT. */
1499 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1501 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1507 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1508 if it is not there yet. */
1511 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1519 type = TYPE_MAIN_VARIANT (type);
1521 for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1522 if (is_equal_types (t, type))
1525 if (i == VEC_length (tree, *unsuitable_types))
1526 VEC_safe_push (tree, heap, *unsuitable_types, type);
1529 /* Given a type TYPE, this function returns the name of the type. */
1532 get_type_name (tree type)
1534 if (! TYPE_NAME (type))
1537 if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1538 return IDENTIFIER_POINTER (TYPE_NAME (type));
1539 else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1540 && DECL_NAME (TYPE_NAME (type)))
1541 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1546 /* This function is a temporary hack to overcome the types problem.
1547 When several compilation units are compiled together
1548 with -combine, the TYPE_MAIN_VARIANT of the same type
1549 can appear differently in different compilation units.
1550 Therefore this function first compares type names.
1551 If there are no names, structure bodies are recursively
1555 is_equal_types (tree type1, tree type2)
1557 const char * name1,* name2;
1559 if ((!type1 && type2)
1560 ||(!type2 && type1))
1563 if (!type1 && !type2)
1566 if (TREE_CODE (type1) != TREE_CODE (type2))
1572 if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1575 name1 = get_type_name (type1);
1576 name2 = get_type_name (type2);
1578 if (name1 && name2 && !strcmp (name1, name2))
1581 if (name1 && name2 && strcmp (name1, name2))
1584 switch (TREE_CODE (type1))
1587 case REFERENCE_TYPE:
1589 return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1595 case QUAL_UNION_TYPE:
1599 /* Compare fields of structure. */
1600 for (field1 = TYPE_FIELDS (type1); field1;
1601 field1 = TREE_CHAIN (field1))
1603 tree field2 = find_field_in_struct_1 (type2, field1);
1613 if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1614 && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1622 tree max1, min1, max2, min2;
1624 if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1627 d1 = TYPE_DOMAIN (type1);
1628 d2 = TYPE_DOMAIN (type2);
1633 max1 = TYPE_MAX_VALUE (d1);
1634 max2 = TYPE_MAX_VALUE (d2);
1635 min1 = TYPE_MIN_VALUE (d1);
1636 min2 = TYPE_MIN_VALUE (d2);
1638 if (max1 && max2 && min1 && min2
1639 && TREE_CODE (max1) == TREE_CODE (max2)
1640 && TREE_CODE (max1) == INTEGER_CST
1641 && TREE_CODE (min1) == TREE_CODE (min2)
1642 && TREE_CODE (min1) == INTEGER_CST
1643 && tree_int_cst_equal (max1, max2)
1644 && tree_int_cst_equal (min1, min2))
1656 /* This function free non-field accesses from hashtable ACCS. */
1659 free_accesses (htab_t accs)
1662 htab_traverse (accs, free_accs, NULL);
1666 /* This function free field accesses hashtable F_ACCS. */
1669 free_field_accesses (htab_t f_accs)
1672 htab_traverse (f_accs, free_field_accs, NULL);
1673 htab_delete (f_accs);
1676 /* Update call graph with new edge generated by new MALLOC_STMT.
1677 The edge origin is CONTEXT function. */
1680 update_cgraph_with_malloc_call (gimple malloc_stmt, tree context)
1682 struct cgraph_node *src, *dest;
1683 tree malloc_fn_decl;
1688 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1690 src = cgraph_node (context);
1691 dest = cgraph_node (malloc_fn_decl);
1692 cgraph_create_edge (src, dest, malloc_stmt,
1693 gimple_bb (malloc_stmt)->count,
1694 compute_call_stmt_bb_frequency
1695 (context, gimple_bb (malloc_stmt)),
1696 gimple_bb (malloc_stmt)->loop_depth);
1699 /* This function generates set of statements required
1700 to allocate number NUM of structures of type NEW_TYPE.
1701 The statements are stored in NEW_STMTS. The statement that contain
1702 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1705 create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts,
1708 tree new_malloc_size;
1709 tree malloc_fn_decl;
1712 gimple call_stmt, final_stmt;
1715 gcc_assert (num && malloc_stmt && new_type);
1716 *new_stmts = gimple_seq_alloc ();
1718 /* Generate argument to malloc as multiplication of num
1719 and size of new_type. */
1720 new_stmt = gen_size (num, new_type, &new_malloc_size);
1721 gimple_seq_add_stmt (new_stmts, new_stmt);
1723 /* Generate new call for malloc. */
1724 malloc_res = create_tmp_var (ptr_type_node, NULL);
1725 add_referenced_var (malloc_res);
1727 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1728 call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size);
1729 gimple_call_set_lhs (call_stmt, malloc_res);
1730 finalize_stmt_and_append (new_stmts, call_stmt);
1732 /* Create new cast statement. */
1733 final_stmt = get_final_alloc_stmt (malloc_stmt);
1734 gcc_assert (final_stmt);
1735 new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1736 gimple_seq_add_stmt (new_stmts, new_stmt);
1741 /* This function returns a tree representing
1742 the number of instances of structure STR_DECL allocated
1743 by allocation STMT. If new statements are generated,
1744 they are filled into NEW_STMTS_P. */
1747 gen_num_of_structs_in_malloc (gimple stmt, tree str_decl,
1748 gimple_seq *new_stmts_p)
1752 HOST_WIDE_INT struct_size_int;
1757 /* Get malloc argument. */
1758 if (!is_gimple_call (stmt))
1761 arg = gimple_call_arg (stmt, 0);
1763 if (TREE_CODE (arg) != SSA_NAME
1764 && !TREE_CONSTANT (arg))
1767 struct_size = TYPE_SIZE_UNIT (str_decl);
1768 struct_size_int = TREE_INT_CST_LOW (struct_size);
1770 gcc_assert (struct_size);
1772 if (TREE_CODE (arg) == SSA_NAME)
1777 if (is_result_of_mult (arg, &num, struct_size))
1780 num = create_tmp_var (integer_type_node, NULL);
1783 add_referenced_var (num);
1785 if (exact_log2 (struct_size_int) == -1)
1786 div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg,
1790 tree C = build_int_cst (integer_type_node,
1791 exact_log2 (struct_size_int));
1793 div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C);
1795 gimple_seq_add_stmt (new_stmts_p, div_stmt);
1796 finalize_stmt (div_stmt);
1800 if (CONSTANT_CLASS_P (arg)
1801 && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))
1802 return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1807 /* This function is a callback for traversal on new_var's hashtable.
1808 SLOT is a pointer to new_var. This function prints to dump_file
1809 an original variable and all new variables from the new_var
1810 pointed by *SLOT. */
1813 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1815 new_var n_var = *(new_var *) slot;
1820 var_type = get_type_of_var (n_var->orig_var);
1822 fprintf (dump_file, "\nOrig var: ");
1823 print_generic_expr (dump_file, n_var->orig_var, 0);
1824 fprintf (dump_file, " of type ");
1825 print_generic_expr (dump_file, var_type, 0);
1826 fprintf (dump_file, "\n");
1829 VEC_iterate (tree, n_var->new_vars, i, var); i++)
1831 var_type = get_type_of_var (var);
1833 fprintf (dump_file, " ");
1834 print_generic_expr (dump_file, var, 0);
1835 fprintf (dump_file, " of type ");
1836 print_generic_expr (dump_file, var_type, 0);
1837 fprintf (dump_file, "\n");
1842 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1845 copy_decl_attributes (tree new_decl, tree orig_decl)
1848 DECL_ARTIFICIAL (new_decl) = 1;
1849 DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1850 TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1851 TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1852 TREE_USED (new_decl) = TREE_USED (orig_decl);
1853 DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1854 TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1855 TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1857 if (TREE_CODE (orig_decl) == VAR_DECL)
1859 TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1860 DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1864 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1865 the same way as a structure type is wrapped in DECL.
1866 It returns the generated type. */
1869 gen_struct_type (tree decl, tree new_str_type)
1871 tree type_orig = get_type_of_var (decl);
1872 tree new_type = new_str_type;
1873 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1875 type_wrapper_t *wr_p;
1877 while (POINTER_TYPE_P (type_orig)
1878 || TREE_CODE (type_orig) == ARRAY_TYPE)
1880 if (POINTER_TYPE_P (type_orig))
1883 wr.domain = NULL_TREE;
1887 gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1889 wr.domain = TYPE_DOMAIN (type_orig);
1891 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1892 type_orig = TREE_TYPE (type_orig);
1895 while (VEC_length (type_wrapper_t, wrapper) != 0)
1897 wr_p = VEC_last (type_wrapper_t, wrapper);
1899 if (wr_p->wrap) /* Array. */
1900 new_type = build_array_type (new_type, wr_p->domain);
1902 new_type = build_pointer_type (new_type);
1904 VEC_pop (type_wrapper_t, wrapper);
1907 VEC_free (type_wrapper_t, heap, wrapper);
1911 /* This function generates and returns new variable name based on
1912 ORIG_DECL name, combined with index I.
1913 The form of the new name is <orig_name>.<I> . */
1916 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1918 const char *old_name;
1922 if (!DECL_NAME (orig_decl)
1923 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1926 /* If the original variable has a name, create an
1927 appropriate new name for the new variable. */
1929 old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1930 prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1931 strcpy (prefix, old_name);
1932 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1933 return get_identifier (new_name);
1936 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1939 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1943 slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1944 htab_hash_pointer (new_node->orig_var),
1949 /* This function creates and returns new_var_data node
1950 with empty new_vars and orig_var equal to VAR. */
1953 create_new_var_node (tree var, d_str str)
1957 node = (new_var) xmalloc (sizeof (struct new_var_data));
1958 node->orig_var = var;
1959 node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1963 /* Check whether the type of VAR is potential candidate for peeling.
1964 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1965 candidate type. If VAR is initialized, the type of VAR will be added
1966 to UNSUITABLE_TYPES. */
1969 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1972 bool initialized = false;
1979 /* There is no support of initialized vars. */
1980 if (TREE_CODE (var) == VAR_DECL
1981 && DECL_INITIAL (var) != NULL_TREE)
1984 type = get_type_of_var (var);
1988 type = TYPE_MAIN_VARIANT (strip_type (type));
1989 if (TREE_CODE (type) != RECORD_TYPE)
1993 if (initialized && unsuitable_types && *unsuitable_types)
1997 fprintf (dump_file, "The type ");
1998 print_generic_expr (dump_file, type, 0);
1999 fprintf (dump_file, " is initialized...Excluded.");
2001 add_unsuitable_type (unsuitable_types, type);
2011 /* Hash value for field_access_site. */
2014 field_acc_hash (const void *x)
2016 return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2019 /* This function returns nonzero if stmt of field_access_site X
2023 field_acc_eq (const void *x, const void *y)
2025 return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2028 /* This function prints an access site, defined by SLOT. */
2031 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2033 struct access_site *acc = *(struct access_site **) slot;
2037 fprintf(dump_file, "\n");
2039 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2040 fprintf(dump_file, " : ");
2042 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2044 print_generic_expr (dump_file, var, 0);
2045 fprintf(dump_file, ", ");
2050 /* This function frees memory allocated for structure clusters,
2051 starting from CLUSTER. */
2054 free_struct_cluster (struct field_cluster* cluster)
2058 if (cluster->fields_in_cluster)
2059 sbitmap_free (cluster->fields_in_cluster);
2060 if (cluster->sibling)
2061 free_struct_cluster (cluster->sibling);
2066 /* Free all allocated memory under the structure node pointed by D_NODE. */
2069 free_data_struct (d_str d_node)
2078 fprintf (dump_file, "\nRemoving data structure \"");
2079 print_generic_expr (dump_file, d_node->decl, 0);
2080 fprintf (dump_file, "\" from data_struct_list.");
2083 /* Free all space under d_node. */
2086 for (i = 0; i < d_node->num_fields; i++)
2087 free_field_accesses (d_node->fields[i].acc_sites);
2088 free (d_node->fields);
2092 free_accesses (d_node->accs);
2094 if (d_node->struct_clustering)
2095 free_struct_cluster (d_node->struct_clustering);
2097 if (d_node->new_types)
2098 VEC_free (tree, heap, d_node->new_types);
2101 /* This function creates new general and field accesses in BB. */
2104 create_new_accesses_in_bb (basic_block bb)
2109 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2110 create_new_accs_for_struct (str, bb);
2113 /* This function adds allocation sites for peeled structures.
2114 M_DATA is vector of allocation sites of function CONTEXT. */
2117 create_new_alloc_sites (fallocs_t m_data, tree context)
2122 for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2124 gimple stmt = call->stmt;
2125 d_str str = call->str;
2127 gimple_seq new_stmts = NULL;
2128 gimple last_stmt = get_final_alloc_stmt (stmt);
2132 num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2135 gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2136 insert_seq_after_stmt (last_stmt, new_stmts);
2137 last_stmt = last_stmt_tmp;
2140 /* Generate an allocation sites for each new structure type. */
2141 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
2143 gimple new_malloc_stmt = NULL;
2144 gimple last_stmt_tmp = NULL;
2147 new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2148 last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2149 insert_seq_after_stmt (last_stmt, new_stmts);
2150 update_cgraph_with_malloc_call (new_malloc_stmt, context);
2151 last_stmt = last_stmt_tmp;
2156 /* This function prints new variables from hashtable
2157 NEW_VARS_HTAB to dump_file. */
2160 dump_new_vars (htab_t new_vars_htab)
2166 htab_traverse (new_vars_htab, dump_new_var, NULL);
2169 /* Given an original variable ORIG_DECL of structure type STR,
2170 this function generates new variables of the types defined
2171 by STR->new_type. Generated types are saved in new_var node NODE.
2172 ORIG_DECL should has VAR_DECL tree_code. */
2175 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2181 VEC_iterate (tree, str->new_types, i, type); i++)
2183 tree new_decl = NULL;
2186 new_name = gen_var_name (orig_decl, i);
2187 type = gen_struct_type (orig_decl, type);
2189 if (is_global_var (orig_decl))
2190 new_decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
2191 VAR_DECL, new_name, type);
2194 const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2195 new_decl = create_tmp_var (type, name);
2198 copy_decl_attributes (new_decl, orig_decl);
2199 VEC_safe_push (tree, heap, node->new_vars, new_decl);
2203 /* This function creates new variables to
2204 substitute the original variable VAR_DECL and adds
2205 them to the new_var's hashtable NEW_VARS_HTAB. */
2208 create_new_var (tree var_decl, htab_t new_vars_htab)
2215 if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2218 if (!is_candidate (var_decl, &type, NULL))
2221 i = find_structure (type);
2222 if (i == VEC_length (structure, structures))
2225 str = VEC_index (structure, structures, i);
2226 node = create_new_var_node (var_decl, str);
2227 create_new_var_1 (var_decl, str, node);
2228 add_to_new_vars_htab (node, new_vars_htab);
2231 /* Hash value for new_var. */
2234 new_var_hash (const void *x)
2236 return htab_hash_pointer (((const_new_var)x)->orig_var);
2239 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2242 new_var_eq (const void *x, const void *y)
2244 return ((const_new_var)x)->orig_var == (const_tree)y;
2247 /* This function check whether a structure type represented by STR
2248 escapes due to ipa-type-escape analysis. If yes, this type is added
2249 to UNSUITABLE_TYPES vector. */
2252 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2254 tree type = str->decl;
2256 if (!ipa_type_escape_type_contained_p (type))
2260 fprintf (dump_file, "\nEscaping type is ");
2261 print_generic_expr (dump_file, type, 0);
2263 add_unsuitable_type (unsuitable_types, type);
2267 /* Hash value for access_site. */
2270 acc_hash (const void *x)
2272 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2275 /* Return nonzero if stmt of access_site X is equal to Y. */
2278 acc_eq (const void *x, const void *y)
2280 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2283 /* Given a structure declaration STRUCT_DECL, and number of fields
2284 in the structure NUM_FIELDS, this function creates and returns
2285 corresponding field_entry's. */
2287 static struct field_entry *
2288 get_fields (tree struct_decl, int num_fields)
2290 struct field_entry *list;
2291 tree t = TYPE_FIELDS (struct_decl);
2295 (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2297 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2298 if (TREE_CODE (t) == FIELD_DECL)
2300 list[idx].index = idx;
2302 list[idx].acc_sites =
2303 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2304 list[idx].count = 0;
2305 list[idx].field_mapping = NULL_TREE;
2311 /* Print non-field accesses from hashtable ACCS of structure. */
2314 dump_access_sites (htab_t accs)
2320 htab_traverse (accs, dump_acc, NULL);
2323 /* This function is a callback for alloc_sites hashtable
2324 traversal. SLOT is a pointer to fallocs_t. This function
2325 removes all allocations of the structure defined by DATA. */
2328 remove_str_allocs_in_func (void **slot, void *data)
2330 fallocs_t fallocs = *(fallocs_t *) slot;
2334 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2336 if (call->str == (d_str) data)
2337 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2345 /* This function remove all entries corresponding to the STR structure
2346 from alloc_sites hashtable. */
2349 remove_str_allocs (d_str str)
2355 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2358 /* This function removes the structure with index I from structures vector. */
2361 remove_structure (unsigned i)
2365 if (i >= VEC_length (structure, structures))
2368 str = VEC_index (structure, structures, i);
2370 /* Before removing the structure str, we have to remove its
2371 allocations from alloc_sites hashtable. */
2372 remove_str_allocs (str);
2373 free_data_struct (str);
2374 VEC_ordered_remove (structure, structures, i);
2377 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2378 COND_STMT is a condition statement to check. */
2381 is_safe_cond_expr (gimple cond_stmt)
2384 unsigned str0, str1;
2386 unsigned length = VEC_length (structure, structures);
2388 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2389 && gimple_cond_code (cond_stmt) != NE_EXPR)
2392 arg0 = gimple_cond_lhs (cond_stmt);
2393 arg1 = gimple_cond_rhs (cond_stmt);
2395 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2396 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2398 s0 = (str0 != length) ? true : false;
2399 s1 = (str1 != length) ? true : false;
2404 /* For now we allow only comparison with 0 or NULL. */
2405 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2411 /* This function excludes statements, that are
2412 part of allocation sites or field accesses, from the
2413 hashtable of general accesses. SLOT represents general
2414 access that will be checked. DATA is a pointer to
2415 exclude_data structure. */
2418 exclude_from_accs (void **slot, void *data)
2420 struct access_site *acc = *(struct access_site **) slot;
2421 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2422 d_str str = ((struct exclude_data *)data)->str;
2424 if (is_part_of_malloc (acc->stmt, fn_decl)
2425 || is_part_of_field_access (acc->stmt, str))
2427 VEC_free (tree, heap, acc->vars);
2429 htab_clear_slot (str->accs, slot);
2434 /* Callback function for walk_tree called from collect_accesses_in_bb
2435 function. DATA is the statement which is analyzed. */
2438 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2440 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2441 gimple stmt = (gimple) wi->info;
2447 switch (TREE_CODE (t))
2451 tree var = TREE_OPERAND(t, 0);
2452 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2453 unsigned i = find_structure (type);
2455 if (i != VEC_length (structure, structures))
2459 fprintf (dump_file, "\nThe type ");
2460 print_generic_expr (dump_file, type, 0);
2461 fprintf (dump_file, " has bitfield.");
2463 remove_structure (i);
2470 tree ref = TREE_OPERAND (t, 0);
2471 tree field_decl = TREE_OPERAND (t, 1);
2474 if ((TREE_CODE (ref) == INDIRECT_REF
2475 || TREE_CODE (ref) == ARRAY_REF
2476 || TREE_CODE (ref) == VAR_DECL)
2477 && TREE_CODE (field_decl) == FIELD_DECL)
2479 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2480 unsigned i = find_structure (type);
2482 if (i != VEC_length (structure, structures))
2484 d_str str = VEC_index (structure, structures, i);
2485 struct field_entry * field =
2486 find_field_in_struct (str, field_decl);
2490 struct field_access_site *acc = make_field_acc_node ();
2497 acc->field_decl = field_decl;
2499 /* Check whether the access is of the form
2500 we can deal with. */
2501 if (!decompose_access (str->decl, acc))
2505 fprintf (dump_file, "\nThe type ");
2506 print_generic_expr (dump_file, type, 0);
2508 " has complicate access in statement ");
2509 print_gimple_stmt (dump_file, stmt, 0, 0);
2512 remove_structure (i);
2517 /* Increase count of field. */
2518 basic_block bb = gimple_bb (stmt);
2519 field->count += bb->count;
2521 /* Add stmt to the acc_sites of field. */
2522 add_field_acc_to_acc_sites (acc, field->acc_sites);
2533 tree cond = COND_EXPR_COND (t);
2535 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2537 tree t = TREE_OPERAND (cond, i);
2540 walk_tree (&t, get_stmt_accesses, data, NULL);
2551 if (TREE_CODE (t) == SSA_NAME)
2552 t = SSA_NAME_VAR (t);
2554 i = find_structure (strip_type (get_type_of_var (t)));
2555 if (i != VEC_length (structure, structures))
2559 str = VEC_index (structure, structures, i);
2560 add_access_to_acc_sites (stmt, t, str->accs);
2573 /* Free structures hashtable. */
2576 free_structures (void)
2581 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2582 free_data_struct (str);
2584 VEC_free (structure, heap, structures);
2588 /* This function is a callback for traversal over new_var's hashtable.
2589 SLOT is a pointer to new_var. This function frees memory allocated
2590 for new_var and pointed by *SLOT. */
2593 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2595 new_var n_var = *(new_var *) slot;
2597 /* Free vector of new_vars. */
2598 VEC_free (tree, heap, n_var->new_vars);
2603 /* Free new_vars hashtable NEW_VARS_HTAB. */
2606 free_new_vars_htab (htab_t new_vars_htab)
2609 htab_traverse (new_vars_htab, free_new_var, NULL);
2610 htab_delete (new_vars_htab);
2611 new_vars_htab = NULL;
2614 /* This function creates new general and field accesses that appear in cfun. */
2617 create_new_accesses_for_func (void)
2621 FOR_EACH_BB_FN (bb, cfun)
2622 create_new_accesses_in_bb (bb);
2625 /* Create new allocation sites for the function represented by NODE. */
2628 create_new_alloc_sites_for_func (struct cgraph_node *node)
2630 fallocs_t fallocs = get_fallocs (node->decl);
2633 create_new_alloc_sites (fallocs, node->decl);
2636 /* For each local variable of structure type from the vector of structures
2637 this function generates new variable(s) to replace it. */
2640 create_new_local_vars (void)
2643 referenced_var_iterator rvi;
2645 new_local_vars = htab_create (num_referenced_vars,
2646 new_var_hash, new_var_eq, NULL);
2648 FOR_EACH_REFERENCED_VAR (var, rvi)
2650 if (!is_global_var (var))
2651 create_new_var (var, new_local_vars);
2655 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2656 dump_new_vars (new_local_vars);
2659 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2662 print_shift (unsigned HOST_WIDE_INT shift)
2664 unsigned HOST_WIDE_INT sh = shift;
2667 fprintf (dump_file, " ");
2670 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2673 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2674 struct field_entry * fields, int num_fields)
2678 for (i = 0; i < num_fields; i++)
2679 if (TEST_BIT (cluster->fields_in_cluster, i))
2680 fields[i].field_mapping = new_type;
2683 /* This functions builds structure with FIELDS,
2684 NAME and attributes similar to ORIG_STRUCT.
2685 It returns the newly created structure. */
2688 build_basic_struct (tree fields, tree name, tree orig_struct)
2690 tree attributes = NULL_TREE;
2694 if (TYPE_ATTRIBUTES (orig_struct))
2695 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2696 ref = make_node (RECORD_TYPE);
2697 TYPE_SIZE (ref) = 0;
2698 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2699 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2700 for (x = fields; x; x = TREE_CHAIN (x))
2702 DECL_CONTEXT (x) = ref;
2703 DECL_PACKED (x) |= TYPE_PACKED (ref);
2705 TYPE_FIELDS (ref) = fields;
2707 TYPE_NAME (ref) = name;
2712 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2713 of preparation for new structure building. NUM_FIELDS is a total
2714 number of fields in the structure. The function returns newly
2715 generated fields. */
2718 create_fields (struct field_cluster * cluster,
2719 struct field_entry * fields, int num_fields)
2722 tree new_types = NULL_TREE;
2723 tree last = NULL_TREE;
2725 for (i = 0; i < num_fields; i++)
2726 if (TEST_BIT (cluster->fields_in_cluster, i))
2728 tree new_decl = unshare_expr (fields[i].decl);
2731 new_types = new_decl;
2733 TREE_CHAIN (last) = new_decl;
2737 TREE_CHAIN (last) = NULL_TREE;
2742 /* This function creates a cluster name. The name is based on
2743 the original structure name, if it is present. It has a form:
2745 <original_struct_name>_sub.<CLUST_NUM>
2747 The original structure name is taken from the type of DECL.
2748 If an original structure name is not present, it's generated to be:
2752 The function returns identifier of the new cluster name. */
2755 gen_cluster_name (tree decl, int clust_num, int str_num)
2757 const char * orig_name = get_type_name (decl);
2758 char * tmp_name = NULL;
2764 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2766 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2767 prefix = XALLOCAVEC (char, len + 1);
2768 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2769 strlen (tmp_name ? tmp_name : orig_name));
2770 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2772 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2773 return get_identifier (new_name);
2776 /* This function checks whether the structure STR has bitfields.
2777 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2780 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2782 tree type = str->decl;
2785 for (i = 0; i < str->num_fields; i++)
2786 if (DECL_BIT_FIELD (str->fields[i].decl))
2788 add_unsuitable_type (unsuitable_types, type);
2791 fprintf (dump_file, "\nType ");
2792 print_generic_expr (dump_file, type, 0);
2793 fprintf (dump_file, "\nescapes due to bitfield ");
2794 print_generic_expr (dump_file, str->fields[i].decl, 0);
2800 /* This function adds to UNSUITABLE_TYPES those types that escape
2801 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2804 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2809 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2810 check_type_escape (str, unsuitable_types);
2813 /* If a structure type is a return type of any function,
2814 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2817 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2819 struct cgraph_node *c_node;
2821 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2823 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2827 ret_t = strip_type (ret_t);
2828 if (TREE_CODE (ret_t) == RECORD_TYPE)
2830 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2833 fprintf (dump_file, "\nThe type \"");
2834 print_generic_expr (dump_file, ret_t, 0);
2836 "\" is return type of function...Excluded.");
2843 /* This function looks for parameters of local functions
2844 which are of structure types, or derived from them (arrays
2845 of structures, pointers to structures, or their combinations).
2846 We are not handling peeling of such structures right now.
2847 The found structures types are added to UNSUITABLE_TYPES vector. */
2850 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2852 struct cgraph_node *c_node;
2854 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2855 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2857 tree fn = c_node->decl;
2860 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2862 tree type = TREE_TYPE (arg);
2864 type = strip_type (type);
2865 if (TREE_CODE (type) == RECORD_TYPE)
2867 add_unsuitable_type (unsuitable_types,
2868 TYPE_MAIN_VARIANT (type));
2871 fprintf (dump_file, "\nPointer to type \"");
2872 print_generic_expr (dump_file, type, 0);
2874 "\" is passed to local function...Excluded.");
2881 /* This function analyzes structure form of structures
2882 potential for transformation. If we are not capable to transform
2883 structure of some form, we remove it from the structures hashtable.
2884 Right now we cannot handle nested structs, when nesting is
2885 through any level of pointers or arrays.
2887 TBD: release these constrains in future.
2889 Note, that in this function we suppose that all structures
2890 in the program are members of the structures hashtable right now,
2891 without excluding escaping types. */
2894 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2898 for (i = 0; i < str->num_fields; i++)
2900 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2902 if (TREE_CODE (f_type) == RECORD_TYPE)
2904 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2905 add_unsuitable_type (unsuitable_types, str->decl);
2908 fprintf (dump_file, "\nType ");
2909 print_generic_expr (dump_file, f_type, 0);
2910 fprintf (dump_file, " is a field in the structure ");
2911 print_generic_expr (dump_file, str->decl, 0);
2912 fprintf (dump_file, ". Escaping...");
2918 /* This function adds a structure TYPE to the vector of structures,
2919 if it's not already there. */
2922 add_structure (tree type)
2924 struct data_structure node;
2928 type = TYPE_MAIN_VARIANT (type);
2930 i = find_structure (type);
2932 if (i != VEC_length (structure, structures))
2935 num_fields = fields_length (type);
2937 node.num_fields = num_fields;
2938 node.fields = get_fields (type, num_fields);
2939 node.struct_clustering = NULL;
2940 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2941 node.new_types = VEC_alloc (tree, heap, num_fields);
2944 VEC_safe_push (structure, heap, structures, &node);
2948 fprintf (dump_file, "\nAdding data structure \"");
2949 print_generic_expr (dump_file, type, 0);
2950 fprintf (dump_file, "\" to data_struct_list.");
2954 /* This function adds an allocation site to alloc_sites hashtable.
2955 The allocation site appears in STMT of function FN_DECL and
2956 allocates the structure represented by STR. */
2959 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2961 fallocs_t fallocs = NULL;
2962 alloc_site_t m_call;
2968 (fallocs_t) htab_find_with_hash (alloc_sites,
2969 fn_decl, htab_hash_pointer (fn_decl));
2975 fallocs = (fallocs_t)
2976 xmalloc (sizeof (struct func_alloc_sites));
2977 fallocs->func = fn_decl;
2978 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
2979 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
2980 htab_hash_pointer (fn_decl), INSERT);
2983 VEC_safe_push (alloc_site_t, heap,
2984 fallocs->allocs, &m_call);
2988 fprintf (dump_file, "\nAdding stmt ");
2989 print_gimple_stmt (dump_file, stmt, 0, 0);
2990 fprintf (dump_file, " to list of mallocs.");
2994 /* This function returns true if the result of STMT, that contains a call
2995 to an allocation function, is cast to one of the structure types.
2996 STMT should be of the form: T.2 = <alloc_func> (T.1);
2997 If true, I_P contains an index of an allocated structure.
2998 Otherwise I_P contains the length of the vector of structures. */
3001 is_alloc_of_struct (gimple stmt, unsigned *i_p)
3007 final_stmt = get_final_alloc_stmt (stmt);
3012 /* final_stmt should be of the form:
3013 T.3 = (struct_type *) T.2; */
3015 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3018 lhs = gimple_assign_lhs (final_stmt);
3020 type = get_type_of_var (lhs);
3025 if (!POINTER_TYPE_P (type)
3026 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3029 *i_p = find_structure (strip_type (type));
3031 if (*i_p == VEC_length (structure, structures))
3037 /* This function prints non-field and field accesses
3038 of the structure STR. */
3041 dump_accs (d_str str)
3045 fprintf (dump_file, "\nAccess sites of struct ");
3046 print_generic_expr (dump_file, str->decl, 0);
3048 for (i = 0; i < str->num_fields; i++)
3050 fprintf (dump_file, "\nAccess site of field ");
3051 print_generic_expr (dump_file, str->fields[i].decl, 0);
3052 dump_field_acc_sites (str->fields[i].acc_sites);
3053 fprintf (dump_file, ":\n");
3055 fprintf (dump_file, "\nGeneral access sites\n");
3056 dump_access_sites (str->accs);
3059 /* This function checks whether an access statement, pointed by SLOT,
3060 is a condition we are capable to transform. It returns false if not,
3061 setting bool *DATA to false. */
3064 safe_cond_expr_check (void **slot, void *data)
3066 struct access_site *acc = *(struct access_site **) slot;
3068 if (gimple_code (acc->stmt) == GIMPLE_COND
3069 && !is_safe_cond_expr (acc->stmt))
3073 fprintf (dump_file, "\nUnsafe conditional statement ");
3074 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3076 *(bool *) data = false;
3082 /* This function excludes statements that are part of allocation sites and
3083 field accesses from the hashtable of general accesses of the structure
3084 type STR. Only accesses that belong to the function represented by
3085 NODE are treated. */
3088 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3090 struct exclude_data dt;
3092 dt.fn_decl = node->decl;
3095 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3098 /* Collect accesses to the structure types that appear in basic block BB. */
3101 collect_accesses_in_bb (basic_block bb)
3103 gimple_stmt_iterator bsi;
3104 struct walk_stmt_info wi;
3106 memset (&wi, 0, sizeof (wi));
3108 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3110 gimple stmt = gsi_stmt (bsi);
3112 /* In asm stmt we cannot always track the arguments,
3113 so we just give up. */
3114 if (gimple_code (stmt) == GIMPLE_ASM)
3120 wi.info = (void *) stmt;
3121 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3125 /* This function generates cluster substructure that contains FIELDS.
3126 The cluster added to the set of clusters of the structure STR. */
3129 gen_cluster (sbitmap fields, d_str str)
3131 struct field_cluster *crr_cluster = NULL;
3134 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3135 crr_cluster->sibling = str->struct_clustering;
3136 str->struct_clustering = crr_cluster;
3137 crr_cluster->fields_in_cluster = fields;
3140 /* This function peels a field with the index I from the structure DS. */
3143 peel_field (int i, d_str ds)
3145 struct field_cluster *crr_cluster = NULL;
3148 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3149 crr_cluster->sibling = ds->struct_clustering;
3150 ds->struct_clustering = crr_cluster;
3151 crr_cluster->fields_in_cluster =
3152 sbitmap_alloc ((unsigned int) ds->num_fields);
3153 sbitmap_zero (crr_cluster->fields_in_cluster);
3154 SET_BIT (crr_cluster->fields_in_cluster, i);
3157 /* This function calculates maximum field count in
3158 the structure STR. */
3161 get_max_field_count (d_str str)
3166 for (i = 0; i < str->num_fields; i++)
3167 if (str->fields[i].count > max)
3168 max = str->fields[i].count;
3173 /* Do struct-reorg transformation for individual function
3174 represented by NODE. All structure types relevant
3175 for this function are transformed. */
3178 do_reorg_for_func (struct cgraph_node *node)
3180 create_new_local_vars ();
3181 create_new_alloc_sites_for_func (node);
3182 create_new_accesses_for_func ();
3183 update_ssa (TODO_update_ssa);
3184 cleanup_tree_cfg ();
3186 /* Free auxiliary data representing local variables. */
3187 free_new_vars_htab (new_local_vars);
3190 /* Print structure TYPE, its name, if it exists, and body.
3191 INDENT defines the level of indentation (similar
3192 to the option -i of indent command). SHIFT parameter
3193 defines a number of spaces by which a structure will
3194 be shifted right. */
3197 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3198 unsigned HOST_WIDE_INT shift)
3200 const char *struct_name;
3203 if (!type || !dump_file)
3206 if (TREE_CODE (type) != RECORD_TYPE)
3208 print_generic_expr (dump_file, type, 0);
3212 print_shift (shift);
3213 struct_name = get_type_name (type);
3214 fprintf (dump_file, "struct ");
3216 fprintf (dump_file, "%s\n",struct_name);
3217 print_shift (shift);
3218 fprintf (dump_file, "{\n");
3220 for (field = TYPE_FIELDS (type); field;
3221 field = TREE_CHAIN (field))
3223 unsigned HOST_WIDE_INT s = indent;
3224 tree f_type = TREE_TYPE (field);
3226 print_shift (shift);
3228 fprintf (dump_file, " ");
3229 dump_struct_type (f_type, indent, shift + indent);
3230 fprintf(dump_file, " ");
3231 print_generic_expr (dump_file, field, 0);
3232 fprintf(dump_file, ";\n");
3234 print_shift (shift);
3235 fprintf (dump_file, "}\n");
3238 /* This function creates new structure types to replace original type,
3239 indicated by STR->decl. The names of the new structure types are
3240 derived from the original structure type. If the original structure
3241 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3244 create_new_type (d_str str, int *str_num)
3246 int cluster_num = 0;
3248 struct field_cluster *cluster = str->struct_clustering;
3251 tree name = gen_cluster_name (str->decl, cluster_num,
3257 fields = create_fields (cluster, str->fields,
3259 new_type = build_basic_struct (fields, name, str->decl);
3261 update_fields_mapping (cluster, new_type,
3262 str->fields, str->num_fields);
3264 VEC_safe_push (tree, heap, str->new_types, new_type);
3265 cluster = cluster->sibling;
3270 /* This function is a callback for alloc_sites hashtable
3271 traversal. SLOT is a pointer to fallocs_t.
3272 This function frees memory pointed by *SLOT. */
3275 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3277 fallocs_t fallocs = *(fallocs_t *) slot;
3279 VEC_free (alloc_site_t, heap, fallocs->allocs);
3284 /* Remove structures collected in UNSUITABLE_TYPES
3285 from structures vector. */
3288 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3294 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3295 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3296 if (is_equal_types (str->decl, type))
3298 remove_structure (i);
3303 /* Exclude structure types with bitfields.
3304 We would not want to interfere with other optimizations
3305 that can be done in this case. The structure types with
3306 bitfields are added to UNSUITABLE_TYPES vector. */
3309 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3314 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3315 check_bitfields (str, unsuitable_types);
3318 /* This function checks three types of escape. A structure type escapes:
3320 1. if it's a type of parameter of a local function.
3321 2. if it's a type of function return value.
3322 3. if it escapes as a result of ipa-type-escape analysis.
3324 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3327 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3329 exclude_types_passed_to_local_func (unsuitable_types);
3330 exclude_returned_types (unsuitable_types);
3331 exclude_escaping_types_1 (unsuitable_types);
3334 /* This function analyzes whether the form of
3335 structure is such that we are capable to transform it.
3336 Nested structures are checked here. Unsuitable structure
3337 types are added to UNSUITABLE_TYPE vector. */
3340 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3345 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3346 check_struct_form (str, unsuitable_types);
3349 /* This function looks for structure types instantiated in the program.
3350 The candidate types are added to the structures vector.
3351 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3354 build_data_structure (VEC (tree, heap) **unsuitable_types)
3358 struct varpool_node *current_varpool;
3359 struct cgraph_node *c_node;
3361 /* Check global variables. */
3362 FOR_EACH_STATIC_VARIABLE (current_varpool)
3364 var = current_varpool->decl;
3365 if (is_candidate (var, &type, unsuitable_types))
3366 add_structure (type);
3369 /* Now add structures that are types of function parameters and
3371 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3373 enum availability avail =
3374 cgraph_function_body_availability (c_node);
3376 /* We need AVAIL_AVAILABLE for main function. */
3377 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3379 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3381 for (var = DECL_ARGUMENTS (c_node->decl); var;
3382 var = TREE_CHAIN (var))
3383 if (is_candidate (var, &type, unsuitable_types))
3384 add_structure (type);
3388 /* Skip cones that haven't been materialized yet. */
3389 gcc_assert (c_node->clone_of
3390 && c_node->clone_of->decl != c_node->decl);
3394 /* Check function local variables. */
3395 for (var_list = fn->local_decls; var_list;
3396 var_list = TREE_CHAIN (var_list))
3398 var = TREE_VALUE (var_list);
3400 if (is_candidate (var, &type, unsuitable_types))
3401 add_structure (type);
3407 /* This function returns true if the program contains
3408 a call to user defined allocation function, or other
3409 functions that can interfere with struct-reorg optimizations. */
3412 program_redefines_malloc_p (void)
3414 struct cgraph_node *c_node;
3415 struct cgraph_node *c_node2;
3416 struct cgraph_edge *c_edge;
3420 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3422 fndecl = c_node->decl;
3424 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3426 c_node2 = c_edge->callee;
3427 fndecl2 = c_node2->decl;
3428 if (is_gimple_call (c_edge->call_stmt))
3430 const char * fname = get_name (fndecl2);
3432 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3433 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3434 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3435 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3438 /* Check that there is no __builtin_object_size,
3439 __builtin_offsetof, or realloc's in the program. */
3440 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3441 || !strcmp (fname, "__builtin_offsetof")
3442 || !strcmp (fname, "realloc"))
3451 /* In this function we assume that an allocation statement
3453 var = (type_cast) malloc (size);
3455 is converted into the following set of statements:
3459 T.3 = (type_cast) T.2;
3462 In this function we collect into alloc_sites the allocation
3463 sites of variables of structure types that are present
3464 in structures vector. */
3467 collect_alloc_sites (void)
3469 struct cgraph_node *node;
3470 struct cgraph_edge *cs;
3472 for (node = cgraph_nodes; node; node = node->next)
3473 if (node->analyzed && node->decl)
3475 for (cs = node->callees; cs; cs = cs->next_callee)
3477 gimple stmt = cs->call_stmt;
3483 if (is_gimple_call (stmt)
3484 && (decl = gimple_call_fndecl (stmt))
3485 && gimple_call_lhs (stmt))
3489 if (is_alloc_of_struct (stmt, &i))
3491 /* We support only malloc now. */
3492 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3496 str = VEC_index (structure, structures, i);
3497 add_alloc_site (node->decl, stmt, str);
3504 "\nUnsupported allocation function ");
3505 print_gimple_stmt (dump_file, stmt, 0, 0);
3507 remove_structure (i);
3516 /* Print collected accesses. */
3519 dump_accesses (void)
3527 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3531 /* This function checks whether the accesses of structures in condition
3532 expressions are of the kind we are capable to transform.
3533 If not, such structures are removed from the vector of structures. */
3536 check_cond_exprs (void)
3542 while (VEC_iterate (structure, structures, i, str))
3547 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3549 remove_structure (i);
3555 /* We exclude from non-field accesses of the structure
3556 all statements that will be treated as part of the structure
3557 allocation sites or field accesses. */
3560 exclude_alloc_and_field_accs (struct cgraph_node *node)
3565 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3566 exclude_alloc_and_field_accs_1 (str, node);
3569 /* This function collects accesses of the fields of the structures
3570 that appear at function FN. */
3573 collect_accesses_in_func (struct function *fn)
3580 /* Collect accesses for each basic blocks separately. */
3581 FOR_EACH_BB_FN (bb, fn)
3582 collect_accesses_in_bb (bb);
3585 /* This function summarizes counts of the fields into the structure count. */
3588 sum_counts (d_str str, gcov_type *hottest)
3593 for (i = 0; i < str->num_fields; i++)
3597 fprintf (dump_file, "\nCounter of field \"");
3598 print_generic_expr (dump_file, str->fields[i].decl, 0);
3599 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3600 str->fields[i].count);
3602 str->count += str->fields[i].count;
3607 fprintf (dump_file, "\nCounter of struct \"");
3608 print_generic_expr (dump_file, str->decl, 0);
3609 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3612 if (str->count > *hottest)
3613 *hottest = str->count;
3616 /* This function peels the field into separate structure if it's
3617 sufficiently hot, i.e. if its count provides at least 90% of
3618 the maximum field count in the structure. */
3621 peel_hot_fields (d_str str)
3623 gcov_type max_field_count;
3624 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3627 sbitmap_ones (fields_left);
3629 (gcov_type) (get_max_field_count (str)/100)*90;
3631 str->struct_clustering = NULL;
3633 for (i = 0; i < str->num_fields; i++)
3635 if (str->count >= max_field_count)
3637 RESET_BIT (fields_left, i);
3638 peel_field (i, str);
3642 i = sbitmap_first_set_bit (fields_left);
3644 gen_cluster (fields_left, str);
3646 sbitmap_free (fields_left);
3649 /* This function is a helper for do_reorg. It goes over
3650 functions in call graph and performs actual transformation
3656 struct cgraph_node *node;
3658 /* Initialize the default bitmap obstack. */
3659 bitmap_obstack_initialize (NULL);
3661 for (node = cgraph_nodes; node; node = node->next)
3662 if (node->analyzed && node->decl)
3664 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3665 current_function_decl = node->decl;
3667 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3668 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3669 do_reorg_for_func (node);
3670 free_dominance_info (CDI_DOMINATORS);
3671 free_dominance_info (CDI_POST_DOMINATORS);
3672 current_function_decl = NULL;
3677 bitmap_obstack_release (NULL);
3680 /* This function creates new global struct variables.
3681 For each original variable, the set of new variables
3682 is created with the new structure types corresponding
3683 to the structure type of original variable.
3684 Only VAR_DECL variables are treated by this function. */
3687 create_new_global_vars (void)
3689 struct varpool_node *current_varpool;
3690 unsigned HOST_WIDE_INT i;
3691 unsigned HOST_WIDE_INT varpool_size = 0;
3693 for (i = 0; i < 2; i++)
3696 new_global_vars = htab_create (varpool_size,
3697 new_var_hash, new_var_eq, NULL);
3698 FOR_EACH_STATIC_VARIABLE(current_varpool)
3700 tree var_decl = current_varpool->decl;
3702 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3707 create_new_var (var_decl, new_global_vars);
3711 if (new_global_vars)
3712 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3715 /* Dump all new types generated by this optimization. */
3718 dump_new_types (void)
3727 fprintf (dump_file, "\nThe following are the new types generated by"
3728 " this optimization:\n");
3730 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3734 fprintf (dump_file, "\nFor type ");
3735 dump_struct_type (str->decl, 2, 0);
3736 fprintf (dump_file, "\nthe number of new types is %d\n",
3737 VEC_length (tree, str->new_types));
3739 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3740 dump_struct_type (type, 2, 0);
3744 /* This function creates new types to replace old structure types. */
3747 create_new_types (void)
3753 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3754 create_new_type (str, &str_num);
3757 /* Free allocation sites hashtable. */
3760 free_alloc_sites (void)
3763 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3764 htab_delete (alloc_sites);
3768 /* This function collects structures potential
3769 for peeling transformation, and inserts
3770 them into structures hashtable. */
3773 collect_structures (void)
3775 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3777 structures = VEC_alloc (structure, heap, 32);
3779 /* If program contains user defined mallocs, we give up. */
3780 if (program_redefines_malloc_p ())
3783 /* Build data structures hashtable of all data structures
3785 build_data_structure (&unsuitable_types);
3787 /* This function analyzes whether the form of
3788 structure is such that we are capable to transform it.
3789 Nested structures are checked here. */
3790 analyze_struct_form (&unsuitable_types);
3792 /* This function excludes those structure types
3793 that escape compilation unit. */
3794 exclude_escaping_types (&unsuitable_types);
3796 /* We do not want to change data layout of the structures with bitfields. */
3797 exclude_types_with_bit_fields (&unsuitable_types);
3799 remove_unsuitable_types (unsuitable_types);
3800 VEC_free (tree, heap, unsuitable_types);
3803 /* Collect structure allocation sites. In case of arrays
3804 we have nothing to do. */
3807 collect_allocation_sites (void)
3809 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3810 collect_alloc_sites ();
3813 /* This function collects data accesses for the
3814 structures to be transformed. For each structure
3815 field it updates the count field in field_entry. */
3818 collect_data_accesses (void)
3820 struct cgraph_node *c_node;
3822 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3824 enum availability avail = cgraph_function_body_availability (c_node);
3826 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3828 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3830 collect_accesses_in_func (func);
3831 exclude_alloc_and_field_accs (c_node);
3835 check_cond_exprs ();
3836 /* Print collected accesses. */
3840 /* We do not bother to transform cold structures.
3841 Coldness of the structure is defined relatively
3842 to the highest structure count among the structures
3843 to be transformed. It's triggered by the compiler parameter
3845 --param struct-reorg-cold-struct-ratio=<value>
3847 where <value> ranges from 0 to 100. Structures with count ratios
3848 that are less than this parameter are considered to be cold. */
3851 exclude_cold_structs (void)
3853 gcov_type hottest = 0;
3857 /* We summarize counts of fields of a structure into the structure count. */
3858 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3859 sum_counts (str, &hottest);
3861 /* Remove cold structures from structures vector. */
3863 while (VEC_iterate (structure, structures, i, str))
3864 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3868 fprintf (dump_file, "\nThe structure ");
3869 print_generic_expr (dump_file, str->decl, 0);
3870 fprintf (dump_file, " is cold.");
3872 remove_structure (i);
3878 /* This function decomposes original structure into substructures,
3887 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3888 peel_hot_fields (str);
3892 /* Do the actual transformation for each structure
3893 from the structures hashtable. */
3898 /* Check that there is a work to do. */
3899 if (!VEC_length (structure, structures))
3902 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3909 fprintf (dump_file, "\nNumber of structures to transform is %d",
3910 VEC_length (structure, structures));
3914 /* Generate new types. */
3915 create_new_types ();
3918 /* Create new global variables. */
3919 create_new_global_vars ();
3920 dump_new_vars (new_global_vars);
3922 /* Decompose structures for each function separately. */
3925 /* Free auxiliary data collected for global variables. */
3926 free_new_vars_htab (new_global_vars);
3929 /* Free all auxiliary data used by this optimization. */
3932 free_data_structs (void)
3935 free_alloc_sites ();
3938 /* Perform structure decomposition (peeling). */
3941 reorg_structs (void)
3945 /* Collect structure types. */
3946 collect_structures ();
3948 /* Collect structure allocation sites. */
3949 collect_allocation_sites ();
3951 /* Collect structure accesses. */
3952 collect_data_accesses ();
3954 /* We transform only hot structures. */
3955 exclude_cold_structs ();
3958 /* Decompose structures into substructures, i.e. clusters. */
3962 /* Do the actual transformation for each structure
3963 from the structures hashtable. */
3966 /* Free all auxiliary data used by this optimization. */
3967 free_data_structs ();
3970 /* Struct-reorg optimization entry point function. */
3973 reorg_structs_drive (void)
3979 /* Struct-reorg optimization gate function. */
3982 struct_reorg_gate (void)
3984 return flag_ipa_struct_reorg
3985 && flag_whole_program
3989 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
3993 "ipa_struct_reorg", /* name */
3994 struct_reorg_gate, /* gate */
3995 reorg_structs_drive, /* execute */
3998 0, /* static_pass_number */
3999 TV_INTEGRATION, /* tv_id */
4000 0, /* properties_required */
4001 0, /* properties_provided */
4002 0, /* properties_destroyed */
4003 TODO_verify_ssa, /* todo_flags_start */
4004 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */