1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008, 2009, 2010 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 /* This function returns true if two fields FIELD1 and FIELD2 are
252 semantically equal, and false otherwise. */
255 compare_fields (tree field1, tree field2)
257 if (DECL_NAME (field1) && DECL_NAME (field2))
259 const char *name1 = IDENTIFIER_POINTER (DECL_NAME (field1));
260 const char *name2 = IDENTIFIER_POINTER (DECL_NAME (field2));
262 gcc_assert (name1 && name2);
264 if (strcmp (name1, name2))
268 else if (DECL_NAME (field1) || DECL_NAME (field2))
271 if (!is_equal_types (TREE_TYPE (field1), TREE_TYPE (field2)))
277 /* Given structure type SRT_TYPE and field FIELD,
278 this function is looking for a field with the same name
279 and type as FIELD in STR_TYPE. It returns it if found,
280 or NULL_TREE otherwise. */
283 find_field_in_struct_1 (tree str_type, tree field)
287 if (!DECL_NAME (field))
290 for (str_field = TYPE_FIELDS (str_type); str_field;
291 str_field = TREE_CHAIN (str_field))
294 if (!DECL_NAME (str_field))
297 if (compare_fields (field, str_field))
304 /* Given a field declaration FIELD_DECL, this function
305 returns corresponding field entry in structure STR. */
307 static struct field_entry *
308 find_field_in_struct (d_str str, tree field_decl)
312 tree field = find_field_in_struct_1 (str->decl, field_decl);
314 for (i = 0; i < str->num_fields; i++)
315 if (str->fields[i].decl == field)
316 return &(str->fields[i]);
321 /* This function checks whether ARG is a result of multiplication
322 of some number by STRUCT_SIZE. If yes, the function returns true
323 and this number is filled into NUM. */
326 is_result_of_mult (tree arg, tree *num, tree struct_size)
328 gimple size_def_stmt = SSA_NAME_DEF_STMT (arg);
330 /* If the allocation statement was of the form
331 D.2229_10 = <alloc_func> (D.2228_9);
332 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
334 if (size_def_stmt && is_gimple_assign (size_def_stmt))
336 tree lhs = gimple_assign_lhs (size_def_stmt);
338 /* We expect temporary here. */
339 if (!is_gimple_reg (lhs))
342 if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR)
344 tree arg0 = gimple_assign_rhs1 (size_def_stmt);
345 tree arg1 = gimple_assign_rhs2 (size_def_stmt);
347 if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
353 if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
366 /* This function returns true if access ACC corresponds to the pattern
367 generated by compiler when an address of element i of an array
368 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
369 pattern is recognized correctly, this function returns true
370 and fills missing fields in ACC. Otherwise it returns false. */
373 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
376 tree struct_size, op0, op1;
378 enum tree_code rhs_code;
380 ref_var = TREE_OPERAND (acc->ref, 0);
382 if (TREE_CODE (ref_var) != SSA_NAME)
385 acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
386 if (!(acc->ref_def_stmt)
387 || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN))
390 rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt);
392 if (rhs_code != PLUS_EXPR
393 && rhs_code != MINUS_EXPR
394 && rhs_code != POINTER_PLUS_EXPR)
397 op0 = gimple_assign_rhs1 (acc->ref_def_stmt);
398 op1 = gimple_assign_rhs2 (acc->ref_def_stmt);
400 if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1,
401 &acc->base, &acc->offset,
406 before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
408 before_cast = acc->offset;
414 if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
417 struct_size = TYPE_SIZE_UNIT (str_decl);
419 if (!is_result_of_mult (before_cast, &acc->num, struct_size))
426 /* This function checks whether the access ACC of structure type STR
427 is of the form suitable for transformation. If yes, it returns true.
431 decompose_access (tree str_decl, struct field_access_site *acc)
433 gcc_assert (acc->ref);
435 if (TREE_CODE (acc->ref) == INDIRECT_REF)
436 return decompose_indirect_ref_acc (str_decl, acc);
437 else if (TREE_CODE (acc->ref) == ARRAY_REF)
439 else if (TREE_CODE (acc->ref) == VAR_DECL)
445 /* This function creates empty field_access_site node. */
447 static inline struct field_access_site *
448 make_field_acc_node (void)
450 return XCNEW (struct field_access_site);
453 /* This function returns the structure field access, defined by STMT,
454 if it is already in hashtable of function accesses F_ACCS. */
456 static struct field_access_site *
457 is_in_field_accs (gimple stmt, htab_t f_accs)
459 return (struct field_access_site *)
460 htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
463 /* This function adds an access ACC to the hashtable
464 F_ACCS of field accesses. */
467 add_field_acc_to_acc_sites (struct field_access_site *acc,
472 gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
473 slot = htab_find_slot_with_hash (f_accs, acc->stmt,
474 htab_hash_pointer (acc->stmt),
479 /* This function adds the VAR to vector of variables of
480 an access site defined by statement STMT. If access entry
481 with statement STMT does not exist in hashtable of
482 accesses ACCS, this function creates it. */
485 add_access_to_acc_sites (gimple stmt, tree var, htab_t accs)
487 struct access_site *acc;
489 acc = (struct access_site *)
490 htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
496 acc = XNEW (struct access_site);
498 if (!is_gimple_debug (stmt))
499 acc->vars = VEC_alloc (tree, heap, 10);
502 slot = htab_find_slot_with_hash (accs, stmt,
503 htab_hash_pointer (stmt), INSERT);
506 if (!is_gimple_debug (stmt))
507 VEC_safe_push (tree, heap, acc->vars, var);
510 /* This function adds NEW_DECL to function
511 referenced vars, and marks it for renaming. */
514 finalize_var_creation (tree new_decl)
516 add_referenced_var (new_decl);
517 mark_sym_for_renaming (new_decl);
520 /* This function finalizes VAR creation if it is a global VAR_DECL. */
523 finalize_global_creation (tree var)
525 if (TREE_CODE (var) == VAR_DECL
526 && is_global_var (var))
527 finalize_var_creation (var);
530 /* This function inserts NEW_DECL to varpool. */
533 insert_global_to_varpool (tree new_decl)
535 struct varpool_node *new_node;
537 new_node = varpool_node (new_decl);
538 notice_global_symbol (new_decl);
539 varpool_mark_needed_node (new_node);
540 varpool_finalize_decl (new_decl);
543 /* This function finalizes the creation of new variables,
544 defined by *SLOT->new_vars. */
547 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
549 new_var n_var = *(new_var *) slot;
553 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
554 finalize_var_creation (var);
558 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
559 It returns it, if found, and NULL_TREE otherwise. */
562 find_var_in_new_vars_vec (new_var var, tree new_type)
567 for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
569 tree type = strip_type(get_type_of_var (n_var));
572 if (type == new_type)
579 /* This function returns new_var node, the orig_var of which is DECL.
580 It looks for new_var's in NEW_VARS_HTAB. If not found,
581 the function returns NULL. */
584 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
586 return (new_var) htab_find_with_hash (new_vars_htab, decl,
590 /* Given original variable ORIG_VAR, this function returns
591 new variable corresponding to it of NEW_TYPE type. */
594 find_new_var_of_type (tree orig_var, tree new_type)
597 gcc_assert (orig_var && new_type);
599 if (TREE_CODE (orig_var) == SSA_NAME)
600 orig_var = SSA_NAME_VAR (orig_var);
602 var = is_in_new_vars_htab (orig_var, new_global_vars);
604 var = is_in_new_vars_htab (orig_var, new_local_vars);
606 return find_var_in_new_vars_vec (var, new_type);
609 /* This function generates stmt:
610 res = NUM * sizeof(TYPE) and returns it.
611 res is filled into RES. */
614 gen_size (tree num, tree type, tree *res)
616 tree struct_size = TYPE_SIZE_UNIT (type);
617 HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
620 *res = create_tmp_var (TREE_TYPE (num), NULL);
623 add_referenced_var (*res);
625 if (exact_log2 (struct_size_int) == -1)
627 tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
628 new_stmt = gimple_build_assign (*res, fold_build2 (MULT_EXPR,
634 tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
636 new_stmt = gimple_build_assign (*res, fold_build2 (LSHIFT_EXPR,
641 finalize_stmt (new_stmt);
645 /* This function generates and returns a statement, that cast variable
646 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
647 into RES_P. ORIG_CAST_STMT is the original cast statement. */
650 gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt,
656 lhs = gimple_assign_lhs (orig_cast_stmt);
657 new_lhs = find_new_var_of_type (lhs, new_type);
658 gcc_assert (new_lhs);
660 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0);
661 finalize_stmt (new_stmt);
666 /* This function builds an edge between BB and E->dest and updates
667 phi nodes of E->dest. It returns newly created edge. */
670 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
674 gimple_stmt_iterator si;
676 new_e = make_edge (bb, e->dest, e->flags);
678 for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si))
680 gimple phi = gsi_stmt (si);
681 arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
682 add_phi_arg (phi, arg, new_e, gimple_phi_arg_location_from_edge (phi, e));
688 /* This function inserts NEW_STMT before STMT. */
691 insert_before_stmt (gimple stmt, gimple new_stmt)
693 gimple_stmt_iterator bsi;
695 if (!stmt || !new_stmt)
698 bsi = gsi_for_stmt (stmt);
699 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
702 /* Insert NEW_STMTS after STMT. */
705 insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts)
707 gimple_stmt_iterator bsi;
709 if (!stmt || !new_stmts)
712 bsi = gsi_for_stmt (stmt);
713 gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT);
716 /* Insert NEW_STMT after STMT. */
719 insert_after_stmt (gimple stmt, gimple new_stmt)
721 gimple_stmt_iterator bsi;
723 if (!stmt || !new_stmt)
726 bsi = gsi_for_stmt (stmt);
727 gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT);
730 /* This function returns vector of allocation sites
731 that appear in function FN_DECL. */
734 get_fallocs (tree fn_decl)
736 return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
737 htab_hash_pointer (fn_decl));
740 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
741 and it is a part of allocation of a structure,
742 then it is usually followed by a cast stmt
743 p_8 = (struct str_t *) D.2225_7;
744 which is returned by this function. */
747 get_final_alloc_stmt (gimple alloc_stmt)
756 if (!is_gimple_call (alloc_stmt))
759 alloc_res = gimple_get_lhs (alloc_stmt);
761 if (TREE_CODE (alloc_res) != SSA_NAME)
764 if (!single_imm_use (alloc_res, &use_p, &final_stmt))
770 /* This function returns true if STMT is one of allocation
771 sites of function FN_DECL. It returns false otherwise. */
774 is_part_of_malloc (gimple stmt, tree fn_decl)
776 fallocs_t fallocs = get_fallocs (fn_decl);
783 for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
784 if (call->stmt == stmt
785 || get_final_alloc_stmt (call->stmt) == stmt)
791 /* Auxiliary structure for a lookup over field accesses. */
792 struct find_stmt_data
798 /* This function looks for DATA->stmt among
799 the statements involved in the field access,
800 defined by SLOT. It stops when it's found. */
803 find_in_field_accs (void **slot, void *data)
805 struct field_access_site *f_acc = *(struct field_access_site **) slot;
806 gimple stmt = ((struct find_stmt_data *)data)->stmt;
808 if (f_acc->stmt == stmt
809 || f_acc->ref_def_stmt == stmt
810 || f_acc->cast_stmt == stmt)
812 ((struct find_stmt_data *)data)->found = true;
819 /* This function checks whether STMT is part of field
820 accesses of structure STR. It returns true, if found,
821 and false otherwise. */
824 is_part_of_field_access (gimple stmt, d_str str)
828 for (i = 0; i < str->num_fields; i++)
830 struct find_stmt_data data;
834 if (str->fields[i].acc_sites)
835 htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
844 /* Auxiliary data for exclude_from_accs function. */
852 /* This function returns component_ref with the BASE and
853 field named FIELD_ID from structure TYPE. */
856 build_comp_ref (tree base, tree field_id, tree type)
862 /* Find field of structure type with the same name as field_id. */
863 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
865 if (DECL_NAME (field) == field_id)
874 return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
878 /* This struct represent data used for walk_tree
879 called from function find_pos_in_stmt.
880 - ref is a tree to be found,
881 - and pos is a pointer that points to ref in stmt. */
890 /* This is a callback function for walk_tree, called from
891 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
892 When *TP is equal to DATA->ref, the walk_tree stops,
893 and found position, equal to TP, is assigned to DATA->pos. */
896 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
898 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
899 struct ref_pos *r_pos = (struct ref_pos *) wi->info;
900 tree ref = r_pos->ref;
903 if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref))
909 r_pos->container = t;
915 /* This function looks for the pointer of REF in STMT,
916 It returns it, if found, and NULL otherwise. */
919 find_pos_in_stmt (gimple stmt, tree ref, struct ref_pos * r_pos)
921 struct walk_stmt_info wi;
925 r_pos->container = NULL_TREE;
926 memset (&wi, 0, sizeof (wi));
928 walk_gimple_op (stmt, find_pos_in_stmt_1, &wi);
933 /* This structure is used to represent array
934 or pointer-to wrappers of structure type.
935 For example, if type1 is structure type,
936 then for type1 ** we generate two type_wrapper
937 structures with wrap = 0 each one.
938 It's used to unwind the original type up to
939 structure type, replace it with the new structure type
940 and wrap it back in the opposite order. */
942 typedef struct type_wrapper
944 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
947 /* Relevant for arrays as domain or index. */
951 DEF_VEC_O (type_wrapper_t);
952 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
954 /* This function replace field access ACC by the new
955 field access of structure type NEW_TYPE. */
958 replace_field_acc (struct field_access_site *acc, tree new_type)
960 tree ref_var = acc->ref;
965 tree field_id = DECL_NAME (acc->field_decl);
966 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
967 type_wrapper_t *wr_p = NULL;
968 struct ref_pos r_pos;
970 while (TREE_CODE (ref_var) == INDIRECT_REF
971 || TREE_CODE (ref_var) == ARRAY_REF)
975 if ( TREE_CODE (ref_var) == INDIRECT_REF)
983 wr.domain = TREE_OPERAND (ref_var, 1);
986 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
987 ref_var = TREE_OPERAND (ref_var, 0);
990 new_ref = find_new_var_of_type (ref_var, new_type);
991 finalize_global_creation (new_ref);
993 while (VEC_length (type_wrapper_t, wrapper) != 0)
995 tree type = TREE_TYPE (TREE_TYPE (new_ref));
997 wr_p = VEC_last (type_wrapper_t, wrapper);
998 if (wr_p->wrap) /* Array. */
999 new_ref = build4 (ARRAY_REF, type, new_ref,
1000 wr_p->domain, NULL_TREE, NULL_TREE);
1002 new_ref = build1 (INDIRECT_REF, type, new_ref);
1003 VEC_pop (type_wrapper_t, wrapper);
1006 new_acc = build_comp_ref (new_ref, field_id, new_type);
1007 VEC_free (type_wrapper_t, heap, wrapper);
1009 if (is_gimple_assign (acc->stmt))
1011 lhs = gimple_assign_lhs (acc->stmt);
1012 rhs = gimple_assign_rhs1 (acc->stmt);
1014 if (lhs == acc->comp_ref)
1015 gimple_assign_set_lhs (acc->stmt, new_acc);
1016 else if (rhs == acc->comp_ref)
1017 gimple_assign_set_rhs1 (acc->stmt, new_acc);
1020 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos);
1027 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos);
1032 finalize_stmt (acc->stmt);
1035 /* This function replace field access ACC by a new field access
1036 of structure type NEW_TYPE. */
1039 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1042 if (TREE_CODE (acc->ref) == INDIRECT_REF
1043 ||TREE_CODE (acc->ref) == ARRAY_REF
1044 ||TREE_CODE (acc->ref) == VAR_DECL)
1045 replace_field_acc (acc, new_type);
1050 /* This function looks for d_str, represented by TYPE, in the structures
1051 vector. If found, it returns an index of found structure. Otherwise
1052 it returns a length of the structures vector. */
1055 find_structure (tree type)
1060 type = TYPE_MAIN_VARIANT (type);
1062 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1063 if (is_equal_types (str->decl, type))
1066 return VEC_length (structure, structures);
1069 /* In this function we create new statements that have the same
1070 form as ORIG_STMT, but of type NEW_TYPE. The statements
1071 treated by this function are simple assignments,
1072 like assignments: p.8_7 = p; or statements with rhs of
1073 tree codes PLUS_EXPR and MINUS_EXPR. */
1076 create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset)
1081 tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1083 lhs = gimple_assign_lhs (orig_stmt);
1085 gcc_assert (TREE_CODE (lhs) == VAR_DECL
1086 || TREE_CODE (lhs) == SSA_NAME);
1088 new_lhs = find_new_var_of_type (lhs, new_type);
1089 gcc_assert (new_lhs);
1090 finalize_var_creation (new_lhs);
1092 switch (gimple_assign_rhs_code (orig_stmt))
1096 case POINTER_PLUS_EXPR:
1098 tree op0 = gimple_assign_rhs1 (orig_stmt);
1099 tree op1 = gimple_assign_rhs2 (orig_stmt);
1100 unsigned str0, str1;
1101 unsigned length = VEC_length (structure, structures);
1104 str0 = find_structure (strip_type (get_type_of_var (op0)));
1105 str1 = find_structure (strip_type (get_type_of_var (op1)));
1106 gcc_assert ((str0 != length) || (str1 != length));
1109 new_op0 = find_new_var_of_type (op0, new_type);
1111 new_op1 = find_new_var_of_type (op1, new_type);
1124 new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt),
1125 new_lhs, new_op0, new_op1);
1126 finalize_stmt (new_stmt);
1131 /* Given a field access F_ACC of the FIELD, this function
1132 replaces it by the new field access. */
1135 create_new_field_access (struct field_access_site *f_acc,
1136 struct field_entry field)
1138 tree new_type = field.field_mapping;
1143 tree cast_res = NULL;
1147 mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1148 insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1151 if (f_acc->cast_stmt)
1153 cast_stmt = gen_cast_stmt (size_res, new_type,
1154 f_acc->cast_stmt, &cast_res);
1155 insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1158 if (f_acc->ref_def_stmt)
1166 new_stmt = create_base_plus_offset (f_acc->ref_def_stmt,
1168 insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1171 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1172 D.2162_18 by an appropriate variable of new_type type. */
1173 replace_field_access_stmt (f_acc, new_type);
1176 /* This function creates a new condition statement
1177 corresponding to the original COND_STMT, adds new basic block
1178 and redirects condition edges. NEW_VAR is a new condition
1179 variable located in the condition statement at the position POS. */
1182 create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos)
1185 edge true_e = NULL, false_e = NULL;
1187 gimple_stmt_iterator si;
1189 extract_true_false_edges_from_block (gimple_bb (cond_stmt),
1192 new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1193 pos == 0 ? new_var : gimple_cond_lhs (cond_stmt),
1194 pos == 1 ? new_var : gimple_cond_rhs (cond_stmt),
1198 finalize_stmt (new_stmt);
1200 /* Create new basic block after bb. */
1201 new_bb = create_empty_bb (gimple_bb (cond_stmt));
1203 /* Add new condition stmt to the new_bb. */
1204 si = gsi_start_bb (new_bb);
1205 gsi_insert_after (&si, new_stmt, GSI_NEW_STMT);
1207 /* Create false and true edges from new_bb. */
1208 make_edge_and_fix_phis_of_dest (new_bb, true_e);
1209 make_edge_and_fix_phis_of_dest (new_bb, false_e);
1211 /* Redirect one of original edges to point to new_bb. */
1212 if (gimple_cond_code (cond_stmt) == NE_EXPR)
1213 redirect_edge_succ (true_e, new_bb);
1215 redirect_edge_succ (false_e, new_bb);
1218 /* This function creates new condition statements corresponding
1219 to original condition STMT, one for each new type, and
1220 recursively redirect edges to newly generated basic blocks. */
1223 create_new_stmts_for_cond_expr (gimple stmt)
1225 tree arg0, arg1, arg;
1226 unsigned str0, str1;
1232 unsigned length = VEC_length (structure, structures);
1234 gcc_assert (gimple_cond_code (stmt) == EQ_EXPR
1235 || gimple_cond_code (stmt) == NE_EXPR);
1237 arg0 = gimple_cond_lhs (stmt);
1238 arg1 = gimple_cond_rhs (stmt);
1240 str0 = find_structure (strip_type (get_type_of_var (arg0)));
1241 str1 = find_structure (strip_type (get_type_of_var (arg1)));
1243 s0 = (str0 != length) ? true : false;
1244 s1 = (str1 != length) ? true : false;
1246 gcc_assert (s0 || s1);
1247 /* For now we allow only comparison with 0 or NULL. */
1248 gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1250 str = integer_zerop (arg0) ?
1251 VEC_index (structure, structures, str1):
1252 VEC_index (structure, structures, str0);
1253 arg = integer_zerop (arg0) ? arg1 : arg0;
1254 pos = integer_zerop (arg0) ? 1 : 0;
1256 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1260 new_arg = find_new_var_of_type (arg, type);
1261 create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1265 /* This function looks for VAR in STMT, and replace it with NEW_VAR.
1266 If needed, it wraps NEW_VAR in pointers and indirect references
1267 before insertion. */
1270 insert_new_var_in_stmt (gimple stmt, tree var, tree new_var)
1272 struct ref_pos r_pos;
1275 pos = find_pos_in_stmt (stmt, var, &r_pos);
1278 while (r_pos.container && (TREE_CODE(r_pos.container) == INDIRECT_REF
1279 || TREE_CODE(r_pos.container) == ADDR_EXPR))
1281 tree type = TREE_TYPE (TREE_TYPE (new_var));
1283 if (TREE_CODE(r_pos.container) == INDIRECT_REF)
1284 new_var = build1 (INDIRECT_REF, type, new_var);
1286 new_var = build_fold_addr_expr (new_var);
1287 pos = find_pos_in_stmt (stmt, r_pos.container, &r_pos);
1294 /* Create a new general access to replace original access ACC
1295 for structure type NEW_TYPE. */
1298 create_general_new_stmt (struct access_site *acc, tree new_type)
1300 gimple old_stmt = acc->stmt;
1302 gimple new_stmt = gimple_copy (old_stmt);
1305 /* We are really building a new stmt, clear the virtual operands. */
1306 if (gimple_has_mem_ops (new_stmt))
1308 gimple_set_vuse (new_stmt, NULL_TREE);
1309 gimple_set_vdef (new_stmt, NULL_TREE);
1312 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1314 tree new_var = find_new_var_of_type (var, new_type);
1315 tree lhs, rhs = NULL_TREE;
1317 gcc_assert (new_var);
1318 finalize_var_creation (new_var);
1320 if (is_gimple_assign (new_stmt))
1322 lhs = gimple_assign_lhs (new_stmt);
1324 if (TREE_CODE (lhs) == SSA_NAME)
1325 lhs = SSA_NAME_VAR (lhs);
1326 if (gimple_assign_rhs_code (new_stmt) == SSA_NAME)
1327 rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt));
1329 /* It can happen that rhs is a constructor.
1330 Then we have to replace it to be of new_type. */
1331 if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR)
1333 /* Dealing only with empty constructors right now. */
1334 gcc_assert (VEC_empty (constructor_elt,
1335 CONSTRUCTOR_ELTS (rhs)));
1336 rhs = build_constructor (new_type, 0);
1337 gimple_assign_set_rhs1 (new_stmt, rhs);
1341 gimple_assign_set_lhs (new_stmt, new_var);
1342 else if (rhs == var)
1343 gimple_assign_set_rhs1 (new_stmt, new_var);
1345 insert_new_var_in_stmt (new_stmt, var, new_var);
1348 insert_new_var_in_stmt (new_stmt, var, new_var);
1351 finalize_stmt (new_stmt);
1355 /* For each new type in STR this function creates new general accesses
1356 corresponding to the original access ACC. */
1359 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1362 gimple stmt = acc->stmt;
1365 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1369 new_stmt = create_general_new_stmt (acc, type);
1370 insert_after_stmt (stmt, new_stmt);
1374 /* This function creates a new general access of structure STR
1375 to replace the access ACC. */
1378 create_new_general_access (struct access_site *acc, d_str str)
1380 gimple stmt = acc->stmt;
1381 switch (gimple_code (stmt))
1384 create_new_stmts_for_cond_expr (stmt);
1388 /* It is very hard to maintain usable debug info after struct peeling,
1389 for now just reset all debug stmts referencing objects that have
1391 gimple_debug_bind_reset_value (stmt);
1395 create_new_stmts_for_general_acc (acc, str);
1399 /* Auxiliary data for creation of accesses. */
1400 struct create_acc_data
1407 /* This function creates a new general access, defined by SLOT.
1408 DATA is a pointer to create_acc_data structure. */
1411 create_new_acc (void **slot, void *data)
1413 struct access_site *acc = *(struct access_site **) slot;
1414 basic_block bb = ((struct create_acc_data *)data)->bb;
1415 d_str str = ((struct create_acc_data *)data)->str;
1417 if (gimple_bb (acc->stmt) == bb)
1418 create_new_general_access (acc, str);
1422 /* This function creates a new field access, defined by SLOT.
1423 DATA is a pointer to create_acc_data structure. */
1426 create_new_field_acc (void **slot, void *data)
1428 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1429 basic_block bb = ((struct create_acc_data *)data)->bb;
1430 d_str str = ((struct create_acc_data *)data)->str;
1431 int i = ((struct create_acc_data *)data)->field_index;
1433 if (gimple_bb (f_acc->stmt) == bb)
1434 create_new_field_access (f_acc, str->fields[i]);
1438 /* This function creates new accesses for the structure
1439 type STR in basic block BB. */
1442 create_new_accs_for_struct (d_str str, basic_block bb)
1445 struct create_acc_data dt;
1449 dt.field_index = -1;
1451 for (i = 0; i < str->num_fields; i++)
1455 if (str->fields[i].acc_sites)
1456 htab_traverse (str->fields[i].acc_sites,
1457 create_new_field_acc, &dt);
1460 htab_traverse (str->accs, create_new_acc, &dt);
1463 /* This function inserts new variables from new_var,
1464 defined by SLOT, into varpool. */
1467 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1469 new_var n_var = *(new_var *) slot;
1473 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1474 insert_global_to_varpool (var);
1478 /* This function prints a field access site, defined by SLOT. */
1481 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1483 struct field_access_site *f_acc =
1484 *(struct field_access_site **) slot;
1486 fprintf(dump_file, "\n");
1488 print_gimple_stmt (dump_file, f_acc->stmt, 0, 0);
1489 if (f_acc->ref_def_stmt)
1490 print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0);
1491 if (f_acc->cast_stmt)
1492 print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0);
1496 /* Print field accesses from hashtable F_ACCS. */
1499 dump_field_acc_sites (htab_t f_accs)
1505 htab_traverse (f_accs, dump_field_acc, NULL);
1508 /* Hash value for fallocs_t. */
1511 malloc_hash (const void *x)
1513 return htab_hash_pointer (((const_fallocs_t)x)->func);
1516 /* This function returns nonzero if function of func_alloc_sites' X
1520 malloc_eq (const void *x, const void *y)
1522 return ((const_fallocs_t)x)->func == (const_tree)y;
1525 /* This function is a callback for traversal over a structure accesses.
1526 It frees an access represented by SLOT. */
1529 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1531 struct access_site * acc = *(struct access_site **) slot;
1533 VEC_free (tree, heap, acc->vars);
1538 /* This is a callback function for traversal over field accesses.
1539 It frees a field access represented by SLOT. */
1542 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1544 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1550 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1551 if it is not there yet. */
1554 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1562 type = TYPE_MAIN_VARIANT (type);
1564 for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1565 if (is_equal_types (t, type))
1568 if (i == VEC_length (tree, *unsuitable_types))
1569 VEC_safe_push (tree, heap, *unsuitable_types, type);
1572 /* Given a type TYPE, this function returns the name of the type. */
1575 get_type_name (tree type)
1577 if (! TYPE_NAME (type))
1580 if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1581 return IDENTIFIER_POINTER (TYPE_NAME (type));
1582 else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1583 && DECL_NAME (TYPE_NAME (type)))
1584 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1589 /* This function is a temporary hack to overcome the types problem.
1590 When several compilation units are compiled together
1591 with -combine, the TYPE_MAIN_VARIANT of the same type
1592 can appear differently in different compilation units.
1593 Therefore this function first compares type names.
1594 If there are no names, structure bodies are recursively
1598 is_equal_types (tree type1, tree type2)
1600 const char * name1,* name2;
1602 if ((!type1 && type2)
1603 ||(!type2 && type1))
1606 if (!type1 && !type2)
1609 if (TREE_CODE (type1) != TREE_CODE (type2))
1615 if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1618 name1 = get_type_name (type1);
1619 name2 = get_type_name (type2);
1622 return strcmp (name1, name2) == 0;
1624 switch (TREE_CODE (type1))
1627 case REFERENCE_TYPE:
1629 return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1635 case QUAL_UNION_TYPE:
1638 tree field1, field2;
1640 /* Compare fields of structure. */
1641 for (field1 = TYPE_FIELDS (type1), field2 = TYPE_FIELDS (type2);
1643 field1 = TREE_CHAIN (field1), field2 = TREE_CHAIN (field2))
1645 if (!compare_fields (field1, field2))
1648 if (field1 || field2)
1657 if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1658 && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1666 tree max1, min1, max2, min2;
1668 if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1671 d1 = TYPE_DOMAIN (type1);
1672 d2 = TYPE_DOMAIN (type2);
1677 max1 = TYPE_MAX_VALUE (d1);
1678 max2 = TYPE_MAX_VALUE (d2);
1679 min1 = TYPE_MIN_VALUE (d1);
1680 min2 = TYPE_MIN_VALUE (d2);
1682 if (max1 && max2 && min1 && min2
1683 && TREE_CODE (max1) == TREE_CODE (max2)
1684 && TREE_CODE (max1) == INTEGER_CST
1685 && TREE_CODE (min1) == TREE_CODE (min2)
1686 && TREE_CODE (min1) == INTEGER_CST
1687 && tree_int_cst_equal (max1, max2)
1688 && tree_int_cst_equal (min1, min2))
1700 /* This function free non-field accesses from hashtable ACCS. */
1703 free_accesses (htab_t accs)
1706 htab_traverse (accs, free_accs, NULL);
1710 /* This function free field accesses hashtable F_ACCS. */
1713 free_field_accesses (htab_t f_accs)
1716 htab_traverse (f_accs, free_field_accs, NULL);
1717 htab_delete (f_accs);
1720 /* Update call graph with new edge generated by new MALLOC_STMT.
1721 The edge origin is CONTEXT function. */
1724 update_cgraph_with_malloc_call (gimple malloc_stmt, tree context)
1726 struct cgraph_node *src, *dest;
1727 tree malloc_fn_decl;
1732 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1734 src = cgraph_node (context);
1735 dest = cgraph_node (malloc_fn_decl);
1736 cgraph_create_edge (src, dest, malloc_stmt,
1737 gimple_bb (malloc_stmt)->count,
1738 compute_call_stmt_bb_frequency
1739 (context, gimple_bb (malloc_stmt)),
1740 gimple_bb (malloc_stmt)->loop_depth);
1743 /* This function generates set of statements required
1744 to allocate number NUM of structures of type NEW_TYPE.
1745 The statements are stored in NEW_STMTS. The statement that contain
1746 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1749 create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts,
1752 tree new_malloc_size;
1753 tree malloc_fn_decl;
1756 gimple call_stmt, final_stmt;
1759 gcc_assert (num && malloc_stmt && new_type);
1760 *new_stmts = gimple_seq_alloc ();
1762 /* Generate argument to malloc as multiplication of num
1763 and size of new_type. */
1764 new_stmt = gen_size (num, new_type, &new_malloc_size);
1765 gimple_seq_add_stmt (new_stmts, new_stmt);
1767 /* Generate new call for malloc. */
1768 malloc_res = create_tmp_var (ptr_type_node, NULL);
1769 add_referenced_var (malloc_res);
1771 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1772 call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size);
1773 gimple_call_set_lhs (call_stmt, malloc_res);
1774 finalize_stmt_and_append (new_stmts, call_stmt);
1776 /* Create new cast statement. */
1777 final_stmt = get_final_alloc_stmt (malloc_stmt);
1778 gcc_assert (final_stmt);
1779 new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1780 gimple_seq_add_stmt (new_stmts, new_stmt);
1785 /* This function returns a tree representing
1786 the number of instances of structure STR_DECL allocated
1787 by allocation STMT. If new statements are generated,
1788 they are filled into NEW_STMTS_P. */
1791 gen_num_of_structs_in_malloc (gimple stmt, tree str_decl,
1792 gimple_seq *new_stmts_p)
1796 HOST_WIDE_INT struct_size_int;
1801 /* Get malloc argument. */
1802 if (!is_gimple_call (stmt))
1805 arg = gimple_call_arg (stmt, 0);
1807 if (TREE_CODE (arg) != SSA_NAME
1808 && !TREE_CONSTANT (arg))
1811 struct_size = TYPE_SIZE_UNIT (str_decl);
1812 struct_size_int = TREE_INT_CST_LOW (struct_size);
1814 gcc_assert (struct_size);
1816 if (TREE_CODE (arg) == SSA_NAME)
1821 if (is_result_of_mult (arg, &num, struct_size))
1824 num = create_tmp_var (integer_type_node, NULL);
1827 add_referenced_var (num);
1829 if (exact_log2 (struct_size_int) == -1)
1830 div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg,
1834 tree C = build_int_cst (integer_type_node,
1835 exact_log2 (struct_size_int));
1837 div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C);
1839 gimple_seq_add_stmt (new_stmts_p, div_stmt);
1840 finalize_stmt (div_stmt);
1844 if (CONSTANT_CLASS_P (arg)
1845 && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))
1846 return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1851 /* This function is a callback for traversal on new_var's hashtable.
1852 SLOT is a pointer to new_var. This function prints to dump_file
1853 an original variable and all new variables from the new_var
1854 pointed by *SLOT. */
1857 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1859 new_var n_var = *(new_var *) slot;
1864 var_type = get_type_of_var (n_var->orig_var);
1866 fprintf (dump_file, "\nOrig var: ");
1867 print_generic_expr (dump_file, n_var->orig_var, 0);
1868 fprintf (dump_file, " of type ");
1869 print_generic_expr (dump_file, var_type, 0);
1870 fprintf (dump_file, "\n");
1873 VEC_iterate (tree, n_var->new_vars, i, var); i++)
1875 var_type = get_type_of_var (var);
1877 fprintf (dump_file, " ");
1878 print_generic_expr (dump_file, var, 0);
1879 fprintf (dump_file, " of type ");
1880 print_generic_expr (dump_file, var_type, 0);
1881 fprintf (dump_file, "\n");
1886 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1889 copy_decl_attributes (tree new_decl, tree orig_decl)
1892 DECL_ARTIFICIAL (new_decl) = 1;
1893 DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1894 TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1895 TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1896 TREE_USED (new_decl) = TREE_USED (orig_decl);
1897 DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1898 TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1899 TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1901 if (TREE_CODE (orig_decl) == VAR_DECL)
1903 TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1904 DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1908 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1909 the same way as a structure type is wrapped in DECL.
1910 It returns the generated type. */
1913 gen_struct_type (tree decl, tree new_str_type)
1915 tree type_orig = get_type_of_var (decl);
1916 tree new_type = new_str_type;
1917 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1919 type_wrapper_t *wr_p;
1921 while (POINTER_TYPE_P (type_orig)
1922 || TREE_CODE (type_orig) == ARRAY_TYPE)
1924 if (POINTER_TYPE_P (type_orig))
1927 wr.domain = NULL_TREE;
1931 gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1933 wr.domain = TYPE_DOMAIN (type_orig);
1935 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1936 type_orig = TREE_TYPE (type_orig);
1939 while (VEC_length (type_wrapper_t, wrapper) != 0)
1941 wr_p = VEC_last (type_wrapper_t, wrapper);
1943 if (wr_p->wrap) /* Array. */
1944 new_type = build_array_type (new_type, wr_p->domain);
1946 new_type = build_pointer_type (new_type);
1948 VEC_pop (type_wrapper_t, wrapper);
1951 VEC_free (type_wrapper_t, heap, wrapper);
1955 /* This function generates and returns new variable name based on
1956 ORIG_DECL name, combined with index I.
1957 The form of the new name is <orig_name>.<I> . */
1960 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1962 const char *old_name;
1966 if (!DECL_NAME (orig_decl)
1967 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1970 /* If the original variable has a name, create an
1971 appropriate new name for the new variable. */
1973 old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1974 prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1975 strcpy (prefix, old_name);
1976 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1977 return get_identifier (new_name);
1980 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1983 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1987 slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1988 DECL_UID (new_node->orig_var),
1993 /* This function creates and returns new_var_data node
1994 with empty new_vars and orig_var equal to VAR. */
1997 create_new_var_node (tree var, d_str str)
2001 node = XNEW (struct new_var_data);
2002 node->orig_var = var;
2003 node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
2007 /* Check whether the type of VAR is potential candidate for peeling.
2008 Returns true if yes, false otherwise. If yes, TYPE_P will contain
2009 candidate type. If VAR is initialized, the type of VAR will be added
2010 to UNSUITABLE_TYPES. */
2013 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
2016 bool initialized = false;
2023 /* There is no support of initialized vars. */
2024 if (TREE_CODE (var) == VAR_DECL
2025 && DECL_INITIAL (var) != NULL_TREE)
2028 type = get_type_of_var (var);
2032 type = TYPE_MAIN_VARIANT (strip_type (type));
2033 if (TREE_CODE (type) != RECORD_TYPE)
2037 if (initialized && unsuitable_types && *unsuitable_types)
2041 fprintf (dump_file, "The type ");
2042 print_generic_expr (dump_file, type, 0);
2043 fprintf (dump_file, " is initialized...Excluded.");
2045 add_unsuitable_type (unsuitable_types, type);
2055 /* Hash value for field_access_site. */
2058 field_acc_hash (const void *x)
2060 return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2063 /* This function returns nonzero if stmt of field_access_site X
2067 field_acc_eq (const void *x, const void *y)
2069 return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2072 /* This function prints an access site, defined by SLOT. */
2075 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2077 struct access_site *acc = *(struct access_site **) slot;
2081 fprintf(dump_file, "\n");
2083 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2084 fprintf(dump_file, " : ");
2086 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2088 print_generic_expr (dump_file, var, 0);
2089 fprintf(dump_file, ", ");
2094 /* This function frees memory allocated for structure clusters,
2095 starting from CLUSTER. */
2098 free_struct_cluster (struct field_cluster* cluster)
2102 if (cluster->fields_in_cluster)
2103 sbitmap_free (cluster->fields_in_cluster);
2104 if (cluster->sibling)
2105 free_struct_cluster (cluster->sibling);
2110 /* Free all allocated memory under the structure node pointed by D_NODE. */
2113 free_data_struct (d_str d_node)
2122 fprintf (dump_file, "\nRemoving data structure \"");
2123 print_generic_expr (dump_file, d_node->decl, 0);
2124 fprintf (dump_file, "\" from data_struct_list.");
2127 /* Free all space under d_node. */
2130 for (i = 0; i < d_node->num_fields; i++)
2131 free_field_accesses (d_node->fields[i].acc_sites);
2132 free (d_node->fields);
2136 free_accesses (d_node->accs);
2138 if (d_node->struct_clustering)
2139 free_struct_cluster (d_node->struct_clustering);
2141 if (d_node->new_types)
2142 VEC_free (tree, heap, d_node->new_types);
2145 /* This function creates new general and field accesses in BB. */
2148 create_new_accesses_in_bb (basic_block bb)
2153 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2154 create_new_accs_for_struct (str, bb);
2157 /* This function adds allocation sites for peeled structures.
2158 M_DATA is vector of allocation sites of function CONTEXT. */
2161 create_new_alloc_sites (fallocs_t m_data, tree context)
2166 for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2168 gimple stmt = call->stmt;
2169 d_str str = call->str;
2171 gimple_seq new_stmts = NULL;
2172 gimple last_stmt = get_final_alloc_stmt (stmt);
2176 num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2179 gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2180 insert_seq_after_stmt (last_stmt, new_stmts);
2181 last_stmt = last_stmt_tmp;
2184 /* Generate an allocation sites for each new structure type. */
2185 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
2187 gimple new_malloc_stmt = NULL;
2188 gimple last_stmt_tmp = NULL;
2191 new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2192 last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2193 insert_seq_after_stmt (last_stmt, new_stmts);
2194 update_cgraph_with_malloc_call (new_malloc_stmt, context);
2195 last_stmt = last_stmt_tmp;
2200 /* This function prints new variables from hashtable
2201 NEW_VARS_HTAB to dump_file. */
2204 dump_new_vars (htab_t new_vars_htab)
2210 htab_traverse (new_vars_htab, dump_new_var, NULL);
2213 /* Given an original variable ORIG_DECL of structure type STR,
2214 this function generates new variables of the types defined
2215 by STR->new_type. Generated types are saved in new_var node NODE.
2216 ORIG_DECL should has VAR_DECL tree_code. */
2219 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2225 VEC_iterate (tree, str->new_types, i, type); i++)
2227 tree new_decl = NULL;
2230 new_name = gen_var_name (orig_decl, i);
2231 type = gen_struct_type (orig_decl, type);
2233 if (is_global_var (orig_decl))
2234 new_decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
2235 VAR_DECL, new_name, type);
2238 const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2239 new_decl = create_tmp_var (type, name);
2242 copy_decl_attributes (new_decl, orig_decl);
2243 VEC_safe_push (tree, heap, node->new_vars, new_decl);
2247 /* This function creates new variables to
2248 substitute the original variable VAR_DECL and adds
2249 them to the new_var's hashtable NEW_VARS_HTAB. */
2252 create_new_var (tree var_decl, htab_t new_vars_htab)
2259 if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2262 if (!is_candidate (var_decl, &type, NULL))
2265 i = find_structure (type);
2266 if (i == VEC_length (structure, structures))
2269 str = VEC_index (structure, structures, i);
2270 node = create_new_var_node (var_decl, str);
2271 create_new_var_1 (var_decl, str, node);
2272 add_to_new_vars_htab (node, new_vars_htab);
2275 /* Hash value for new_var. */
2278 new_var_hash (const void *x)
2280 return DECL_UID (((const_new_var)x)->orig_var);
2283 /* This function returns nonzero if orig_var of new_var X
2284 and tree Y have equal UIDs. */
2287 new_var_eq (const void *x, const void *y)
2289 if (DECL_P ((const_tree)y))
2290 return DECL_UID (((const_new_var)x)->orig_var) == DECL_UID ((const_tree)y);
2295 /* This function check whether a structure type represented by STR
2296 escapes due to ipa-type-escape analysis. If yes, this type is added
2297 to UNSUITABLE_TYPES vector. */
2300 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2302 tree type = str->decl;
2304 if (!ipa_type_escape_type_contained_p (type))
2308 fprintf (dump_file, "\nEscaping type is ");
2309 print_generic_expr (dump_file, type, 0);
2311 add_unsuitable_type (unsuitable_types, type);
2315 /* Hash value for access_site. */
2318 acc_hash (const void *x)
2320 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2323 /* Return nonzero if stmt of access_site X is equal to Y. */
2326 acc_eq (const void *x, const void *y)
2328 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2331 /* Given a structure declaration STRUCT_DECL, and number of fields
2332 in the structure NUM_FIELDS, this function creates and returns
2333 corresponding field_entry's. */
2335 static struct field_entry *
2336 get_fields (tree struct_decl, int num_fields)
2338 struct field_entry *list;
2339 tree t = TYPE_FIELDS (struct_decl);
2342 list = XNEWVEC (struct field_entry, num_fields);
2344 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2345 if (TREE_CODE (t) == FIELD_DECL)
2347 list[idx].index = idx;
2349 list[idx].acc_sites =
2350 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2351 list[idx].count = 0;
2352 list[idx].field_mapping = NULL_TREE;
2358 /* Print non-field accesses from hashtable ACCS of structure. */
2361 dump_access_sites (htab_t accs)
2367 htab_traverse (accs, dump_acc, NULL);
2370 /* This function is a callback for alloc_sites hashtable
2371 traversal. SLOT is a pointer to fallocs_t. This function
2372 removes all allocations of the structure defined by DATA. */
2375 remove_str_allocs_in_func (void **slot, void *data)
2377 fallocs_t fallocs = *(fallocs_t *) slot;
2381 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2383 if (call->str == (d_str) data)
2384 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2392 /* This function remove all entries corresponding to the STR structure
2393 from alloc_sites hashtable. */
2396 remove_str_allocs (d_str str)
2402 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2405 /* This function removes the structure with index I from structures vector. */
2408 remove_structure (unsigned i)
2412 if (i >= VEC_length (structure, structures))
2415 str = VEC_index (structure, structures, i);
2417 /* Before removing the structure str, we have to remove its
2418 allocations from alloc_sites hashtable. */
2419 remove_str_allocs (str);
2420 free_data_struct (str);
2421 VEC_ordered_remove (structure, structures, i);
2424 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2425 COND_STMT is a condition statement to check. */
2428 is_safe_cond_expr (gimple cond_stmt)
2431 unsigned str0, str1;
2433 unsigned length = VEC_length (structure, structures);
2435 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2436 && gimple_cond_code (cond_stmt) != NE_EXPR)
2439 arg0 = gimple_cond_lhs (cond_stmt);
2440 arg1 = gimple_cond_rhs (cond_stmt);
2442 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2443 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2445 s0 = (str0 != length) ? true : false;
2446 s1 = (str1 != length) ? true : false;
2451 /* For now we allow only comparison with 0 or NULL. */
2452 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2458 /* This function excludes statements, that are
2459 part of allocation sites or field accesses, from the
2460 hashtable of general accesses. SLOT represents general
2461 access that will be checked. DATA is a pointer to
2462 exclude_data structure. */
2465 exclude_from_accs (void **slot, void *data)
2467 struct access_site *acc = *(struct access_site **) slot;
2468 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2469 d_str str = ((struct exclude_data *)data)->str;
2471 if (is_part_of_malloc (acc->stmt, fn_decl)
2472 || is_part_of_field_access (acc->stmt, str))
2474 VEC_free (tree, heap, acc->vars);
2476 htab_clear_slot (str->accs, slot);
2481 /* Callback function for walk_tree called from collect_accesses_in_bb
2482 function. DATA is the statement which is analyzed. */
2485 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2487 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2488 gimple stmt = (gimple) wi->info;
2494 switch (TREE_CODE (t))
2498 tree var = TREE_OPERAND(t, 0);
2499 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2500 unsigned i = find_structure (type);
2502 if (i != VEC_length (structure, structures))
2504 if (is_gimple_debug (stmt))
2508 str = VEC_index (structure, structures, i);
2509 add_access_to_acc_sites (stmt, NULL, str->accs);
2515 fprintf (dump_file, "\nThe type ");
2516 print_generic_expr (dump_file, type, 0);
2517 fprintf (dump_file, " has bitfield.");
2519 remove_structure (i);
2526 tree ref = TREE_OPERAND (t, 0);
2527 tree field_decl = TREE_OPERAND (t, 1);
2530 if ((TREE_CODE (ref) == INDIRECT_REF
2531 || TREE_CODE (ref) == ARRAY_REF
2532 || TREE_CODE (ref) == VAR_DECL)
2533 && TREE_CODE (field_decl) == FIELD_DECL)
2535 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2536 unsigned i = find_structure (type);
2538 if (i != VEC_length (structure, structures))
2540 d_str str = VEC_index (structure, structures, i);
2541 struct field_entry * field =
2542 find_field_in_struct (str, field_decl);
2544 if (is_gimple_debug (stmt))
2546 add_access_to_acc_sites (stmt, NULL, str->accs);
2553 struct field_access_site *acc = make_field_acc_node ();
2560 acc->field_decl = field_decl;
2562 /* Check whether the access is of the form
2563 we can deal with. */
2564 if (!decompose_access (str->decl, acc))
2568 fprintf (dump_file, "\nThe type ");
2569 print_generic_expr (dump_file, type, 0);
2571 " has complicate access in statement ");
2572 print_gimple_stmt (dump_file, stmt, 0, 0);
2575 remove_structure (i);
2580 /* Increase count of field. */
2581 basic_block bb = gimple_bb (stmt);
2582 field->count += bb->count;
2584 /* Add stmt to the acc_sites of field. */
2585 add_field_acc_to_acc_sites (acc, field->acc_sites);
2596 tree cond = COND_EXPR_COND (t);
2598 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2600 tree t = TREE_OPERAND (cond, i);
2603 walk_tree (&t, get_stmt_accesses, data, NULL);
2614 if (TREE_CODE (t) == SSA_NAME)
2615 t = SSA_NAME_VAR (t);
2617 i = find_structure (strip_type (get_type_of_var (t)));
2618 if (i != VEC_length (structure, structures))
2622 str = VEC_index (structure, structures, i);
2623 add_access_to_acc_sites (stmt, t, str->accs);
2636 /* Free structures hashtable. */
2639 free_structures (void)
2644 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2645 free_data_struct (str);
2647 VEC_free (structure, heap, structures);
2651 /* This function is a callback for traversal over new_var's hashtable.
2652 SLOT is a pointer to new_var. This function frees memory allocated
2653 for new_var and pointed by *SLOT. */
2656 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2658 new_var n_var = *(new_var *) slot;
2660 /* Free vector of new_vars. */
2661 VEC_free (tree, heap, n_var->new_vars);
2666 /* Free new_vars hashtable NEW_VARS_HTAB. */
2669 free_new_vars_htab (htab_t new_vars_htab)
2672 htab_traverse (new_vars_htab, free_new_var, NULL);
2673 htab_delete (new_vars_htab);
2674 new_vars_htab = NULL;
2677 /* This function creates new general and field accesses that appear in cfun. */
2680 create_new_accesses_for_func (void)
2684 FOR_EACH_BB_FN (bb, cfun)
2685 create_new_accesses_in_bb (bb);
2688 /* Create new allocation sites for the function represented by NODE. */
2691 create_new_alloc_sites_for_func (struct cgraph_node *node)
2693 fallocs_t fallocs = get_fallocs (node->decl);
2696 create_new_alloc_sites (fallocs, node->decl);
2699 /* For each local variable of structure type from the vector of structures
2700 this function generates new variable(s) to replace it. */
2703 create_new_local_vars (void)
2706 referenced_var_iterator rvi;
2708 new_local_vars = htab_create (num_referenced_vars,
2709 new_var_hash, new_var_eq, NULL);
2711 FOR_EACH_REFERENCED_VAR (var, rvi)
2713 if (!is_global_var (var))
2714 create_new_var (var, new_local_vars);
2718 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2719 dump_new_vars (new_local_vars);
2722 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2725 print_shift (unsigned HOST_WIDE_INT shift)
2727 unsigned HOST_WIDE_INT sh = shift;
2730 fprintf (dump_file, " ");
2733 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2736 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2737 struct field_entry * fields, int num_fields)
2741 for (i = 0; i < num_fields; i++)
2742 if (TEST_BIT (cluster->fields_in_cluster, i))
2743 fields[i].field_mapping = new_type;
2746 /* This functions builds structure with FIELDS,
2747 NAME and attributes similar to ORIG_STRUCT.
2748 It returns the newly created structure. */
2751 build_basic_struct (tree fields, tree name, tree orig_struct)
2753 tree attributes = NULL_TREE;
2757 if (TYPE_ATTRIBUTES (orig_struct))
2758 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2759 ref = make_node (RECORD_TYPE);
2760 TYPE_SIZE (ref) = 0;
2761 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2762 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2763 for (x = fields; x; x = TREE_CHAIN (x))
2765 DECL_CONTEXT (x) = ref;
2766 DECL_PACKED (x) |= TYPE_PACKED (ref);
2768 TYPE_FIELDS (ref) = fields;
2770 TYPE_NAME (ref) = name;
2775 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2776 of preparation for new structure building. NUM_FIELDS is a total
2777 number of fields in the structure. The function returns newly
2778 generated fields. */
2781 create_fields (struct field_cluster * cluster,
2782 struct field_entry * fields, int num_fields)
2785 tree new_types = NULL_TREE;
2786 tree last = NULL_TREE;
2788 for (i = 0; i < num_fields; i++)
2789 if (TEST_BIT (cluster->fields_in_cluster, i))
2791 tree new_decl = unshare_expr (fields[i].decl);
2794 new_types = new_decl;
2796 TREE_CHAIN (last) = new_decl;
2800 TREE_CHAIN (last) = NULL_TREE;
2805 /* This function creates a cluster name. The name is based on
2806 the original structure name, if it is present. It has a form:
2808 <original_struct_name>_sub.<CLUST_NUM>
2810 The original structure name is taken from the type of DECL.
2811 If an original structure name is not present, it's generated to be:
2815 The function returns identifier of the new cluster name. */
2818 gen_cluster_name (tree decl, int clust_num, int str_num)
2820 const char * orig_name = get_type_name (decl);
2821 char * tmp_name = NULL;
2827 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2829 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2830 prefix = XALLOCAVEC (char, len + 1);
2831 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2832 strlen (tmp_name ? tmp_name : orig_name));
2833 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2835 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2836 return get_identifier (new_name);
2839 /* This function checks whether the structure STR has bitfields.
2840 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2843 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2845 tree type = str->decl;
2848 for (i = 0; i < str->num_fields; i++)
2849 if (DECL_BIT_FIELD (str->fields[i].decl))
2851 add_unsuitable_type (unsuitable_types, type);
2854 fprintf (dump_file, "\nType ");
2855 print_generic_expr (dump_file, type, 0);
2856 fprintf (dump_file, "\nescapes due to bitfield ");
2857 print_generic_expr (dump_file, str->fields[i].decl, 0);
2863 /* This function adds to UNSUITABLE_TYPES those types that escape
2864 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2867 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2872 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2873 check_type_escape (str, unsuitable_types);
2876 /* If a structure type is a return type of any function,
2877 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2880 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2882 struct cgraph_node *c_node;
2884 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2886 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2890 ret_t = strip_type (ret_t);
2891 if (TREE_CODE (ret_t) == RECORD_TYPE)
2893 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2896 fprintf (dump_file, "\nThe type \"");
2897 print_generic_expr (dump_file, ret_t, 0);
2899 "\" is return type of function...Excluded.");
2906 /* This function looks for parameters of local functions
2907 which are of structure types, or derived from them (arrays
2908 of structures, pointers to structures, or their combinations).
2909 We are not handling peeling of such structures right now.
2910 The found structures types are added to UNSUITABLE_TYPES vector. */
2913 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2915 struct cgraph_node *c_node;
2917 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2918 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2920 tree fn = c_node->decl;
2923 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2925 tree type = TREE_TYPE (arg);
2927 type = strip_type (type);
2928 if (TREE_CODE (type) == RECORD_TYPE)
2930 add_unsuitable_type (unsuitable_types,
2931 TYPE_MAIN_VARIANT (type));
2934 fprintf (dump_file, "\nPointer to type \"");
2935 print_generic_expr (dump_file, type, 0);
2937 "\" is passed to local function...Excluded.");
2944 /* This function analyzes structure form of structures
2945 potential for transformation. If we are not capable to transform
2946 structure of some form, we remove it from the structures hashtable.
2947 Right now we cannot handle nested structs, when nesting is
2948 through any level of pointers or arrays.
2950 TBD: release these constrains in future.
2952 Note, that in this function we suppose that all structures
2953 in the program are members of the structures hashtable right now,
2954 without excluding escaping types. */
2957 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2961 for (i = 0; i < str->num_fields; i++)
2963 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2965 if (TREE_CODE (f_type) == RECORD_TYPE)
2967 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2968 add_unsuitable_type (unsuitable_types, str->decl);
2971 fprintf (dump_file, "\nType ");
2972 print_generic_expr (dump_file, f_type, 0);
2973 fprintf (dump_file, " is a field in the structure ");
2974 print_generic_expr (dump_file, str->decl, 0);
2975 fprintf (dump_file, ". Escaping...");
2981 /* This function adds a structure TYPE to the vector of structures,
2982 if it's not already there. */
2985 add_structure (tree type)
2987 struct data_structure node;
2991 type = TYPE_MAIN_VARIANT (type);
2993 i = find_structure (type);
2995 if (i != VEC_length (structure, structures))
2998 num_fields = fields_length (type);
3000 node.num_fields = num_fields;
3001 node.fields = get_fields (type, num_fields);
3002 node.struct_clustering = NULL;
3003 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
3004 node.new_types = VEC_alloc (tree, heap, num_fields);
3007 VEC_safe_push (structure, heap, structures, &node);
3011 fprintf (dump_file, "\nAdding data structure \"");
3012 print_generic_expr (dump_file, type, 0);
3013 fprintf (dump_file, "\" to data_struct_list.");
3017 /* This function adds an allocation site to alloc_sites hashtable.
3018 The allocation site appears in STMT of function FN_DECL and
3019 allocates the structure represented by STR. */
3022 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
3024 fallocs_t fallocs = NULL;
3025 alloc_site_t m_call;
3031 (fallocs_t) htab_find_with_hash (alloc_sites,
3032 fn_decl, htab_hash_pointer (fn_decl));
3038 fallocs = XNEW (struct func_alloc_sites);
3039 fallocs->func = fn_decl;
3040 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
3041 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
3042 htab_hash_pointer (fn_decl), INSERT);
3045 VEC_safe_push (alloc_site_t, heap,
3046 fallocs->allocs, &m_call);
3050 fprintf (dump_file, "\nAdding stmt ");
3051 print_gimple_stmt (dump_file, stmt, 0, 0);
3052 fprintf (dump_file, " to list of mallocs.");
3056 /* This function returns true if the result of STMT, that contains a call
3057 to an allocation function, is cast to one of the structure types.
3058 STMT should be of the form: T.2 = <alloc_func> (T.1);
3059 If true, I_P contains an index of an allocated structure.
3060 Otherwise I_P contains the length of the vector of structures. */
3063 is_alloc_of_struct (gimple stmt, unsigned *i_p)
3069 final_stmt = get_final_alloc_stmt (stmt);
3074 /* final_stmt should be of the form:
3075 T.3 = (struct_type *) T.2; */
3077 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3080 lhs = gimple_assign_lhs (final_stmt);
3082 type = get_type_of_var (lhs);
3087 if (!POINTER_TYPE_P (type)
3088 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3091 *i_p = find_structure (strip_type (type));
3093 if (*i_p == VEC_length (structure, structures))
3099 /* This function prints non-field and field accesses
3100 of the structure STR. */
3103 dump_accs (d_str str)
3107 fprintf (dump_file, "\nAccess sites of struct ");
3108 print_generic_expr (dump_file, str->decl, 0);
3110 for (i = 0; i < str->num_fields; i++)
3112 fprintf (dump_file, "\nAccess site of field ");
3113 print_generic_expr (dump_file, str->fields[i].decl, 0);
3114 dump_field_acc_sites (str->fields[i].acc_sites);
3115 fprintf (dump_file, ":\n");
3117 fprintf (dump_file, "\nGeneral access sites\n");
3118 dump_access_sites (str->accs);
3121 /* This function checks whether an access statement, pointed by SLOT,
3122 is a condition we are capable to transform. It returns false if not,
3123 setting bool *DATA to false. */
3126 safe_cond_expr_check (void **slot, void *data)
3128 struct access_site *acc = *(struct access_site **) slot;
3130 if (gimple_code (acc->stmt) == GIMPLE_COND
3131 && !is_safe_cond_expr (acc->stmt))
3135 fprintf (dump_file, "\nUnsafe conditional statement ");
3136 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3138 *(bool *) data = false;
3144 /* This function excludes statements that are part of allocation sites and
3145 field accesses from the hashtable of general accesses of the structure
3146 type STR. Only accesses that belong to the function represented by
3147 NODE are treated. */
3150 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3152 struct exclude_data dt;
3154 dt.fn_decl = node->decl;
3157 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3160 /* Collect accesses to the structure types that appear in basic block BB. */
3163 collect_accesses_in_bb (basic_block bb)
3165 gimple_stmt_iterator bsi;
3166 struct walk_stmt_info wi;
3168 memset (&wi, 0, sizeof (wi));
3170 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3172 gimple stmt = gsi_stmt (bsi);
3174 /* In asm stmt we cannot always track the arguments,
3175 so we just give up. */
3176 if (gimple_code (stmt) == GIMPLE_ASM)
3182 wi.info = (void *) stmt;
3183 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3187 /* This function generates cluster substructure that contains FIELDS.
3188 The cluster added to the set of clusters of the structure STR. */
3191 gen_cluster (sbitmap fields, d_str str)
3193 struct field_cluster *crr_cluster = XCNEW (struct field_cluster);
3195 crr_cluster->sibling = str->struct_clustering;
3196 str->struct_clustering = crr_cluster;
3197 crr_cluster->fields_in_cluster = fields;
3200 /* This function peels a field with the index I from the structure DS. */
3203 peel_field (int i, d_str ds)
3205 struct field_cluster *crr_cluster = XCNEW (struct field_cluster);
3207 crr_cluster->sibling = ds->struct_clustering;
3208 ds->struct_clustering = crr_cluster;
3209 crr_cluster->fields_in_cluster =
3210 sbitmap_alloc ((unsigned int) ds->num_fields);
3211 sbitmap_zero (crr_cluster->fields_in_cluster);
3212 SET_BIT (crr_cluster->fields_in_cluster, i);
3215 /* This function calculates maximum field count in
3216 the structure STR. */
3219 get_max_field_count (d_str str)
3224 for (i = 0; i < str->num_fields; i++)
3225 if (str->fields[i].count > max)
3226 max = str->fields[i].count;
3231 /* Do struct-reorg transformation for individual function
3232 represented by NODE. All structure types relevant
3233 for this function are transformed. */
3236 do_reorg_for_func (struct cgraph_node *node)
3238 create_new_local_vars ();
3239 create_new_alloc_sites_for_func (node);
3240 create_new_accesses_for_func ();
3241 update_ssa (TODO_update_ssa);
3242 cleanup_tree_cfg ();
3244 /* Free auxiliary data representing local variables. */
3245 free_new_vars_htab (new_local_vars);
3248 /* Print structure TYPE, its name, if it exists, and body.
3249 INDENT defines the level of indentation (similar
3250 to the option -i of indent command). SHIFT parameter
3251 defines a number of spaces by which a structure will
3252 be shifted right. */
3255 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3256 unsigned HOST_WIDE_INT shift)
3258 const char *struct_name;
3261 if (!type || !dump_file)
3264 if (TREE_CODE (type) != RECORD_TYPE)
3266 print_generic_expr (dump_file, type, 0);
3270 print_shift (shift);
3271 struct_name = get_type_name (type);
3272 fprintf (dump_file, "struct ");
3274 fprintf (dump_file, "%s\n",struct_name);
3275 print_shift (shift);
3276 fprintf (dump_file, "{\n");
3278 for (field = TYPE_FIELDS (type); field;
3279 field = TREE_CHAIN (field))
3281 unsigned HOST_WIDE_INT s = indent;
3282 tree f_type = TREE_TYPE (field);
3284 print_shift (shift);
3286 fprintf (dump_file, " ");
3287 dump_struct_type (f_type, indent, shift + indent);
3288 fprintf(dump_file, " ");
3289 print_generic_expr (dump_file, field, 0);
3290 fprintf(dump_file, ";\n");
3292 print_shift (shift);
3293 fprintf (dump_file, "}\n");
3296 /* This function creates new structure types to replace original type,
3297 indicated by STR->decl. The names of the new structure types are
3298 derived from the original structure type. If the original structure
3299 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3302 create_new_type (d_str str, int *str_num)
3304 int cluster_num = 0;
3306 struct field_cluster *cluster = str->struct_clustering;
3309 tree name = gen_cluster_name (str->decl, cluster_num,
3315 fields = create_fields (cluster, str->fields,
3317 new_type = build_basic_struct (fields, name, str->decl);
3319 update_fields_mapping (cluster, new_type,
3320 str->fields, str->num_fields);
3322 VEC_safe_push (tree, heap, str->new_types, new_type);
3323 cluster = cluster->sibling;
3328 /* This function is a callback for alloc_sites hashtable
3329 traversal. SLOT is a pointer to fallocs_t.
3330 This function frees memory pointed by *SLOT. */
3333 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3335 fallocs_t fallocs = *(fallocs_t *) slot;
3337 VEC_free (alloc_site_t, heap, fallocs->allocs);
3342 /* Remove structures collected in UNSUITABLE_TYPES
3343 from structures vector. */
3346 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3352 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3353 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3354 if (is_equal_types (str->decl, type))
3356 remove_structure (i);
3361 /* Exclude structure types with bitfields.
3362 We would not want to interfere with other optimizations
3363 that can be done in this case. The structure types with
3364 bitfields are added to UNSUITABLE_TYPES vector. */
3367 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3372 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3373 check_bitfields (str, unsuitable_types);
3376 /* This function checks three types of escape. A structure type escapes:
3378 1. if it's a type of parameter of a local function.
3379 2. if it's a type of function return value.
3380 3. if it escapes as a result of ipa-type-escape analysis.
3382 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3385 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3387 exclude_types_passed_to_local_func (unsuitable_types);
3388 exclude_returned_types (unsuitable_types);
3389 exclude_escaping_types_1 (unsuitable_types);
3392 /* This function analyzes whether the form of
3393 structure is such that we are capable to transform it.
3394 Nested structures are checked here. Unsuitable structure
3395 types are added to UNSUITABLE_TYPE vector. */
3398 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3403 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3404 check_struct_form (str, unsuitable_types);
3407 /* This function looks for structure types instantiated in the program.
3408 The candidate types are added to the structures vector.
3409 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3412 build_data_structure (VEC (tree, heap) **unsuitable_types)
3416 struct varpool_node *current_varpool;
3417 struct cgraph_node *c_node;
3419 /* Check global variables. */
3420 FOR_EACH_STATIC_VARIABLE (current_varpool)
3422 var = current_varpool->decl;
3423 if (is_candidate (var, &type, unsuitable_types))
3424 add_structure (type);
3427 /* Now add structures that are types of function parameters and
3429 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3431 enum availability avail =
3432 cgraph_function_body_availability (c_node);
3434 /* We need AVAIL_AVAILABLE for main function. */
3435 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3437 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3439 for (var = DECL_ARGUMENTS (c_node->decl); var;
3440 var = TREE_CHAIN (var))
3441 if (is_candidate (var, &type, unsuitable_types))
3442 add_structure (type);
3446 /* Skip cones that haven't been materialized yet. */
3447 gcc_assert (c_node->clone_of
3448 && c_node->clone_of->decl != c_node->decl);
3452 /* Check function local variables. */
3453 for (var_list = fn->local_decls; var_list;
3454 var_list = TREE_CHAIN (var_list))
3456 var = TREE_VALUE (var_list);
3458 if (is_candidate (var, &type, unsuitable_types))
3459 add_structure (type);
3465 /* This function returns true if the program contains
3466 a call to user defined allocation function, or other
3467 functions that can interfere with struct-reorg optimizations. */
3470 program_redefines_malloc_p (void)
3472 struct cgraph_node *c_node;
3473 struct cgraph_node *c_node2;
3474 struct cgraph_edge *c_edge;
3477 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3479 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3481 c_node2 = c_edge->callee;
3482 fndecl2 = c_node2->decl;
3483 if (is_gimple_call (c_edge->call_stmt))
3485 const char * fname = get_name (fndecl2);
3487 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3488 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3489 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3490 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3493 /* Check that there is no __builtin_object_size,
3494 __builtin_offsetof, or realloc's in the program. */
3495 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3496 || !strcmp (fname, "__builtin_offsetof")
3497 || !strcmp (fname, "realloc"))
3506 /* In this function we assume that an allocation statement
3508 var = (type_cast) malloc (size);
3510 is converted into the following set of statements:
3514 T.3 = (type_cast) T.2;
3517 In this function we collect into alloc_sites the allocation
3518 sites of variables of structure types that are present
3519 in structures vector. */
3522 collect_alloc_sites (void)
3524 struct cgraph_node *node;
3525 struct cgraph_edge *cs;
3527 for (node = cgraph_nodes; node; node = node->next)
3528 if (node->analyzed && node->decl)
3530 for (cs = node->callees; cs; cs = cs->next_callee)
3532 gimple stmt = cs->call_stmt;
3538 if (is_gimple_call (stmt)
3539 && (decl = gimple_call_fndecl (stmt))
3540 && gimple_call_lhs (stmt))
3544 if (is_alloc_of_struct (stmt, &i))
3546 /* We support only malloc now. */
3547 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3551 str = VEC_index (structure, structures, i);
3552 add_alloc_site (node->decl, stmt, str);
3559 "\nUnsupported allocation function ");
3560 print_gimple_stmt (dump_file, stmt, 0, 0);
3562 remove_structure (i);
3571 /* Print collected accesses. */
3574 dump_accesses (void)
3582 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3586 /* This function checks whether the accesses of structures in condition
3587 expressions are of the kind we are capable to transform.
3588 If not, such structures are removed from the vector of structures. */
3591 check_cond_exprs (void)
3597 while (VEC_iterate (structure, structures, i, str))
3602 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3604 remove_structure (i);
3610 /* We exclude from non-field accesses of the structure
3611 all statements that will be treated as part of the structure
3612 allocation sites or field accesses. */
3615 exclude_alloc_and_field_accs (struct cgraph_node *node)
3620 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3621 exclude_alloc_and_field_accs_1 (str, node);
3624 /* This function collects accesses of the fields of the structures
3625 that appear at function FN. */
3628 collect_accesses_in_func (struct function *fn)
3635 /* Collect accesses for each basic blocks separately. */
3636 FOR_EACH_BB_FN (bb, fn)
3637 collect_accesses_in_bb (bb);
3640 /* This function summarizes counts of the fields into the structure count. */
3643 sum_counts (d_str str, gcov_type *hottest)
3648 for (i = 0; i < str->num_fields; i++)
3652 fprintf (dump_file, "\nCounter of field \"");
3653 print_generic_expr (dump_file, str->fields[i].decl, 0);
3654 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3655 str->fields[i].count);
3657 str->count += str->fields[i].count;
3662 fprintf (dump_file, "\nCounter of struct \"");
3663 print_generic_expr (dump_file, str->decl, 0);
3664 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3667 if (str->count > *hottest)
3668 *hottest = str->count;
3671 /* This function peels the field into separate structure if it's
3672 sufficiently hot, i.e. if its count provides at least 90% of
3673 the maximum field count in the structure. */
3676 peel_hot_fields (d_str str)
3678 gcov_type max_field_count;
3679 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3682 sbitmap_ones (fields_left);
3684 (gcov_type) (get_max_field_count (str)/100)*90;
3686 str->struct_clustering = NULL;
3688 for (i = 0; i < str->num_fields; i++)
3690 if (str->count >= max_field_count)
3692 RESET_BIT (fields_left, i);
3693 peel_field (i, str);
3697 i = sbitmap_first_set_bit (fields_left);
3699 gen_cluster (fields_left, str);
3701 sbitmap_free (fields_left);
3704 /* This function is a helper for do_reorg. It goes over
3705 functions in call graph and performs actual transformation
3711 struct cgraph_node *node;
3713 /* Initialize the default bitmap obstack. */
3714 bitmap_obstack_initialize (NULL);
3716 for (node = cgraph_nodes; node; node = node->next)
3717 if (node->analyzed && node->decl)
3719 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3720 current_function_decl = node->decl;
3722 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3723 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3724 do_reorg_for_func (node);
3725 free_dominance_info (CDI_DOMINATORS);
3726 free_dominance_info (CDI_POST_DOMINATORS);
3727 current_function_decl = NULL;
3732 bitmap_obstack_release (NULL);
3735 /* This function creates new global struct variables.
3736 For each original variable, the set of new variables
3737 is created with the new structure types corresponding
3738 to the structure type of original variable.
3739 Only VAR_DECL variables are treated by this function. */
3742 create_new_global_vars (void)
3744 struct varpool_node *current_varpool;
3745 unsigned HOST_WIDE_INT i;
3746 unsigned HOST_WIDE_INT varpool_size = 0;
3748 for (i = 0; i < 2; i++)
3751 new_global_vars = htab_create (varpool_size,
3752 new_var_hash, new_var_eq, NULL);
3753 FOR_EACH_STATIC_VARIABLE(current_varpool)
3755 tree var_decl = current_varpool->decl;
3757 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3762 create_new_var (var_decl, new_global_vars);
3766 if (new_global_vars)
3767 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3770 /* Dump all new types generated by this optimization. */
3773 dump_new_types (void)
3782 fprintf (dump_file, "\nThe following are the new types generated by"
3783 " this optimization:\n");
3785 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3789 fprintf (dump_file, "\nFor type ");
3790 dump_struct_type (str->decl, 2, 0);
3791 fprintf (dump_file, "\nthe number of new types is %d\n",
3792 VEC_length (tree, str->new_types));
3794 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3795 dump_struct_type (type, 2, 0);
3799 /* This function creates new types to replace old structure types. */
3802 create_new_types (void)
3808 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3809 create_new_type (str, &str_num);
3812 /* Free allocation sites hashtable. */
3815 free_alloc_sites (void)
3818 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3819 htab_delete (alloc_sites);
3823 /* This function collects structures potential
3824 for peeling transformation, and inserts
3825 them into structures hashtable. */
3828 collect_structures (void)
3830 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3832 structures = VEC_alloc (structure, heap, 32);
3834 /* If program contains user defined mallocs, we give up. */
3835 if (program_redefines_malloc_p ())
3838 /* Build data structures hashtable of all data structures
3840 build_data_structure (&unsuitable_types);
3842 /* This function analyzes whether the form of
3843 structure is such that we are capable to transform it.
3844 Nested structures are checked here. */
3845 analyze_struct_form (&unsuitable_types);
3847 /* This function excludes those structure types
3848 that escape compilation unit. */
3849 exclude_escaping_types (&unsuitable_types);
3851 /* We do not want to change data layout of the structures with bitfields. */
3852 exclude_types_with_bit_fields (&unsuitable_types);
3854 remove_unsuitable_types (unsuitable_types);
3855 VEC_free (tree, heap, unsuitable_types);
3858 /* Collect structure allocation sites. In case of arrays
3859 we have nothing to do. */
3862 collect_allocation_sites (void)
3864 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3865 collect_alloc_sites ();
3868 /* This function collects data accesses for the
3869 structures to be transformed. For each structure
3870 field it updates the count field in field_entry. */
3873 collect_data_accesses (void)
3875 struct cgraph_node *c_node;
3877 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3879 enum availability avail = cgraph_function_body_availability (c_node);
3881 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3883 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3885 collect_accesses_in_func (func);
3886 exclude_alloc_and_field_accs (c_node);
3890 check_cond_exprs ();
3891 /* Print collected accesses. */
3895 /* We do not bother to transform cold structures.
3896 Coldness of the structure is defined relatively
3897 to the highest structure count among the structures
3898 to be transformed. It's triggered by the compiler parameter
3900 --param struct-reorg-cold-struct-ratio=<value>
3902 where <value> ranges from 0 to 100. Structures with count ratios
3903 that are less than this parameter are considered to be cold. */
3906 exclude_cold_structs (void)
3908 gcov_type hottest = 0;
3912 /* We summarize counts of fields of a structure into the structure count. */
3913 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3914 sum_counts (str, &hottest);
3916 /* Remove cold structures from structures vector. */
3918 while (VEC_iterate (structure, structures, i, str))
3919 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3923 fprintf (dump_file, "\nThe structure ");
3924 print_generic_expr (dump_file, str->decl, 0);
3925 fprintf (dump_file, " is cold.");
3927 remove_structure (i);
3933 /* This function decomposes original structure into substructures,
3942 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3943 peel_hot_fields (str);
3947 /* Do the actual transformation for each structure
3948 from the structures hashtable. */
3953 /* Check that there is a work to do. */
3954 if (!VEC_length (structure, structures))
3957 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3964 fprintf (dump_file, "\nNumber of structures to transform is %d",
3965 VEC_length (structure, structures));
3969 /* Generate new types. */
3970 create_new_types ();
3973 /* Create new global variables. */
3974 create_new_global_vars ();
3975 dump_new_vars (new_global_vars);
3977 /* Decompose structures for each function separately. */
3980 /* Free auxiliary data collected for global variables. */
3981 free_new_vars_htab (new_global_vars);
3984 /* Free all auxiliary data used by this optimization. */
3987 free_data_structs (void)
3990 free_alloc_sites ();
3993 /* Perform structure decomposition (peeling). */
3996 reorg_structs (void)
4000 /* Collect structure types. */
4001 collect_structures ();
4003 /* Collect structure allocation sites. */
4004 collect_allocation_sites ();
4006 /* Collect structure accesses. */
4007 collect_data_accesses ();
4009 /* We transform only hot structures. */
4010 exclude_cold_structs ();
4013 /* Decompose structures into substructures, i.e. clusters. */
4017 /* Do the actual transformation for each structure
4018 from the structures hashtable. */
4021 /* Free all auxiliary data used by this optimization. */
4022 free_data_structs ();
4025 /* Struct-reorg optimization entry point function. */
4028 reorg_structs_drive (void)
4034 /* Struct-reorg optimization gate function. */
4037 struct_reorg_gate (void)
4039 return flag_ipa_struct_reorg
4040 && flag_whole_program
4044 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
4048 "ipa_struct_reorg", /* name */
4049 struct_reorg_gate, /* gate */
4050 reorg_structs_drive, /* execute */
4053 0, /* static_pass_number */
4054 TV_INTEGRATION, /* tv_id */
4055 0, /* properties_required */
4056 0, /* properties_provided */
4057 0, /* properties_destroyed */
4058 TODO_verify_ssa, /* todo_flags_start */
4059 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */