1 /* Struct-reorg optimization.
2 Copyright (C) 2007 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 2, 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 COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
31 #include "tree-gimple.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-flow-inline.h"
35 #include "langhooks.h"
36 #include "pointer-set.h"
44 #include "diagnostic.h"
50 #include "basic-block.h"
51 #include "tree-iterator.h"
52 #include "tree-pass.h"
53 #include "ipa-struct-reorg.h"
55 #include "ipa-type-escape.h"
56 #include "tree-dump.h"
59 /* This optimization implements structure peeling.
61 For example, given a structure type:
69 it can be peeled into two structure types as follows:
71 typedef struct and typedef struct
77 or can be fully peeled:
94 When structure type is peeled all instances and their accesses
95 in the program are updated accordingly. For example, if there is
100 and structure type str_t was peeled into two structures str_t_0
101 and str_t_1 as it was shown above, then array A will be replaced
102 by two arrays as follows:
107 The field access of field a of element i of array A: A[i].a will be
108 replaced by an access to field a of element i of array A_0: A_0[i].a.
110 This optimization also supports dynamically allocated arrays.
111 If array of structures was allocated by malloc function:
113 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
115 the allocation site will be replaced to reflect new structure types:
117 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
118 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
120 The field access through the pointer p[i].a will be changed by p_0[i].a.
122 The goal of structure peeling is to improve spatial locality.
123 For example, if one of the fields of a structure is accessed frequently
126 for (i = 0; i < N; i++)
131 the allocation of field a of str_t contiguously in memory will
132 increase the chances of fetching the field from cache.
134 The analysis part of this optimization is based on the frequency of
135 field accesses, which are collected all over the program.
136 Then the fields with the frequencies that satisfy the following condition
137 get peeled out of the structure:
139 freq(f) > C * max_field_freq_in_struct
141 where max_field_freq_in_struct is the maximum field frequency
142 in the structure. C is a constant defining which portion of
143 max_field_freq_in_struct the fields should have in order to be peeled.
145 If profiling information is provided, it is used to calculate the
146 frequency of field accesses. Otherwise, the structure is fully peeled.
148 IPA type-escape analysis is used to determine when it is safe
151 The optimization is activated by flag -fipa-struct-reorg. */
153 /* New variables created by this optimization.
154 When doing struct peeling, each variable of
155 the original struct type will be replaced by
156 the set of new variables corresponding to
157 the new structure types. */
158 struct new_var_data
{
159 /* VAR_DECL for original struct type. */
161 /* Vector of new variables. */
162 VEC(tree
, heap
) *new_vars
;
165 typedef struct new_var_data
*new_var
;
166 typedef const struct new_var_data
*const_new_var
;
168 /* This structure represents allocation site of the structure. */
169 typedef struct alloc_site
175 DEF_VEC_O (alloc_site_t
);
176 DEF_VEC_ALLOC_O (alloc_site_t
, heap
);
178 /* Allocation sites that belong to the same function. */
179 struct func_alloc_sites
182 /* Vector of allocation sites for function. */
183 VEC (alloc_site_t
, heap
) *allocs
;
186 typedef struct func_alloc_sites
*fallocs_t
;
187 typedef const struct func_alloc_sites
*const_fallocs_t
;
189 /* All allocation sites in the program. */
192 /* New global variables. Generated once for whole program. */
193 htab_t new_global_vars
;
195 /* New local variables. Generated per-function. */
196 htab_t new_local_vars
;
198 /* Vector of structures to be transformed. */
199 typedef struct data_structure structure
;
200 DEF_VEC_O (structure
);
201 DEF_VEC_ALLOC_O (structure
, heap
);
202 VEC (structure
, heap
) *structures
;
204 /* Forward declarations. */
205 static bool is_equal_types (tree
, tree
);
207 /* Strip structure TYPE from pointers and arrays. */
210 strip_type (tree type
)
212 gcc_assert (TYPE_P (type
));
214 while (POINTER_TYPE_P (type
)
215 || TREE_CODE (type
) == ARRAY_TYPE
)
216 type
= TREE_TYPE (type
);
221 /* This function returns type of VAR. */
224 get_type_of_var (tree var
)
229 if (TREE_CODE (var
) == PARM_DECL
)
230 return DECL_ARG_TYPE (var
);
232 return TREE_TYPE (var
);
235 /* Set of actions we do for each newly generated STMT. */
238 finalize_stmt (tree stmt
)
241 mark_symbols_for_renaming (stmt
);
244 /* This function finalizes STMT and appends it to the list STMTS. */
247 finalize_stmt_and_append (tree
*stmts
, tree stmt
)
249 append_to_statement_list (stmt
, stmts
);
250 finalize_stmt (stmt
);
253 /* Given structure type SRT_TYPE and field FIELD,
254 this function is looking for a field with the same name
255 and type as FIELD in STR_TYPE. It returns it if found,
256 or NULL_TREE otherwise. */
259 find_field_in_struct_1 (tree str_type
, tree field
)
263 for (str_field
= TYPE_FIELDS (str_type
); str_field
;
264 str_field
= TREE_CHAIN (str_field
))
266 const char * str_field_name
;
267 const char * field_name
;
269 str_field_name
= IDENTIFIER_POINTER (DECL_NAME (str_field
));
270 field_name
= IDENTIFIER_POINTER (DECL_NAME (field
));
272 gcc_assert (str_field_name
);
273 gcc_assert (field_name
);
275 if (!strcmp (str_field_name
, field_name
))
277 /* Check field types. */
278 if (is_equal_types (TREE_TYPE (str_field
), TREE_TYPE (field
)))
286 /* Given a field declaration FIELD_DECL, this function
287 returns corresponding field entry in structure STR. */
289 static struct field_entry
*
290 find_field_in_struct (d_str str
, tree field_decl
)
294 tree field
= find_field_in_struct_1 (str
->decl
, field_decl
);
296 for (i
= 0; i
< str
->num_fields
; i
++)
297 if (str
->fields
[i
].decl
== field
)
298 return &(str
->fields
[i
]);
303 /* This function checks whether ARG is a result of multiplication
304 of some number by STRUCT_SIZE. If yes, the function returns true
305 and this number is filled into NUM. */
308 is_result_of_mult (tree arg
, tree
*num
, tree struct_size
)
310 tree size_def_stmt
= SSA_NAME_DEF_STMT (arg
);
312 /* If allocation statementt was of the form
313 D.2229_10 = <alloc_func> (D.2228_9);
314 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
316 if (size_def_stmt
&& TREE_CODE (size_def_stmt
) == GIMPLE_MODIFY_STMT
)
318 tree lhs
= GIMPLE_STMT_OPERAND (size_def_stmt
, 0);
319 tree rhs
= GIMPLE_STMT_OPERAND (size_def_stmt
, 1);
321 /* We expect temporary here. */
322 if (!is_gimple_reg (lhs
))
325 if (TREE_CODE (rhs
) == MULT_EXPR
)
327 tree arg0
= TREE_OPERAND (rhs
, 0);
328 tree arg1
= TREE_OPERAND (rhs
, 1);
330 if (operand_equal_p (arg0
, struct_size
, OEP_ONLY_CONST
))
336 if (operand_equal_p (arg1
, struct_size
, OEP_ONLY_CONST
))
349 /* This function returns true if access ACC corresponds to the pattern
350 generated by compiler when an address of element i of an array
351 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
352 pattern is recognized correctly, this function returns true
353 and fills missing fields in ACC. Otherwise it returns false. */
356 decompose_indirect_ref_acc (tree str_decl
, struct field_access_site
*acc
)
359 tree rhs
, struct_size
, op0
, op1
;
362 ref_var
= TREE_OPERAND (acc
->ref
, 0);
364 if (TREE_CODE (ref_var
) != SSA_NAME
)
367 acc
->ref_def_stmt
= SSA_NAME_DEF_STMT (ref_var
);
368 if (!(acc
->ref_def_stmt
)
369 || (TREE_CODE (acc
->ref_def_stmt
) != GIMPLE_MODIFY_STMT
))
372 rhs
= GIMPLE_STMT_OPERAND (acc
->ref_def_stmt
, 1);
374 if (TREE_CODE (rhs
) != PLUS_EXPR
375 && TREE_CODE (rhs
)!= MINUS_EXPR
376 && TREE_CODE (rhs
) != POINTER_PLUS_EXPR
)
379 op0
= TREE_OPERAND (rhs
, 0);
380 op1
= TREE_OPERAND (rhs
, 1);
382 if (!is_array_access_through_pointer_and_index (TREE_CODE (rhs
), op0
, op1
,
383 &acc
->base
, &acc
->offset
,
388 before_cast
= SINGLE_SSA_TREE_OPERAND (acc
->cast_stmt
, SSA_OP_USE
);
390 before_cast
= acc
->offset
;
396 if (SSA_NAME_IS_DEFAULT_DEF (before_cast
))
399 struct_size
= TYPE_SIZE_UNIT (str_decl
);
401 if (!is_result_of_mult (before_cast
, &acc
->num
, struct_size
))
408 /* This function checks whether the access ACC of structure type STR
409 is of the form suitable for tranformation. If yes, it returns true.
413 decompose_access (tree str_decl
, struct field_access_site
*acc
)
415 gcc_assert (acc
->ref
);
417 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
)
418 return decompose_indirect_ref_acc (str_decl
, acc
);
419 else if (TREE_CODE (acc
->ref
) == ARRAY_REF
)
421 else if (TREE_CODE (acc
->ref
) == VAR_DECL
)
427 /* This function creates empty field_access_site node. */
429 static inline struct field_access_site
*
430 make_field_acc_node (void)
432 int size
= sizeof (struct field_access_site
);
434 return (struct field_access_site
*) xcalloc (1, size
);
437 /* This function returns the structure field access, defined by STMT,
438 if it is aready in hashtable of function accesses F_ACCS. */
440 static struct field_access_site
*
441 is_in_field_accs (tree stmt
, htab_t f_accs
)
443 return (struct field_access_site
*)
444 htab_find_with_hash (f_accs
, stmt
, htab_hash_pointer (stmt
));
447 /* This function adds an access ACC to the hashtable
448 F_ACCS of field accesses. */
451 add_field_acc_to_acc_sites (struct field_access_site
*acc
,
456 gcc_assert (!is_in_field_accs (acc
->stmt
, f_accs
));
457 slot
= htab_find_slot_with_hash (f_accs
, acc
->stmt
,
458 htab_hash_pointer (acc
->stmt
),
463 /* This function adds the VAR to vector of variables of
464 an access site defined by statement STMT. If access entry
465 with statement STMT does not exist in hashtable of
466 accesses ACCS, this function creates it. */
469 add_access_to_acc_sites (tree stmt
, tree var
, htab_t accs
)
471 struct access_site
*acc
;
473 acc
= (struct access_site
*)
474 htab_find_with_hash (accs
, stmt
, htab_hash_pointer (stmt
));
480 acc
= (struct access_site
*) xmalloc (sizeof (struct access_site
));
482 acc
->vars
= VEC_alloc (tree
, heap
, 10);
483 slot
= htab_find_slot_with_hash (accs
, stmt
,
484 htab_hash_pointer (stmt
), INSERT
);
488 VEC_safe_push (tree
, heap
, acc
->vars
, var
);
491 /* This function adds NEW_DECL to function
492 referenced vars, and marks it for renaming. */
495 finalize_var_creation (tree new_decl
)
497 add_referenced_var (new_decl
);
498 if (is_global_var (new_decl
))
499 mark_call_clobbered (new_decl
, ESCAPE_UNKNOWN
);
500 mark_sym_for_renaming (new_decl
);
503 /* This function finalizes VAR creation if it is a global VAR_DECL. */
506 finalize_global_creation (tree var
)
508 if (TREE_CODE (var
) == VAR_DECL
509 && is_global_var (var
))
510 finalize_var_creation (var
);
513 /* This function inserts NEW_DECL to varpool. */
516 insert_global_to_varpool (tree new_decl
)
518 struct varpool_node
*new_node
;
520 new_node
= varpool_node (new_decl
);
521 notice_global_symbol (new_decl
);
522 varpool_mark_needed_node (new_node
);
523 varpool_finalize_decl (new_decl
);
526 /* This function finalizes the creation of new variables,
527 defined by *SLOT->new_vars. */
530 finalize_new_vars_creation (void **slot
, void *data ATTRIBUTE_UNUSED
)
532 new_var n_var
= *(new_var
*) slot
;
536 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
537 finalize_var_creation (var
);
541 /* This funciton updates statements in STMT_LIST with BB info. */
544 add_bb_info (basic_block bb
, tree stmt_list
)
546 if (TREE_CODE (stmt_list
) == STATEMENT_LIST
)
548 tree_stmt_iterator tsi
;
549 for (tsi
= tsi_start (stmt_list
); !tsi_end_p (tsi
); tsi_next (&tsi
))
551 tree stmt
= tsi_stmt (tsi
);
553 set_bb_for_stmt (stmt
, bb
);
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
,
587 htab_hash_pointer (decl
));
590 /* Given original varaiable 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)
626 new_stmt
= build_gimple_modify_stmt (num
, struct_size
);
629 tree C
= build_int_cst (TREE_TYPE (num
), exact_log2 (struct_size_int
));
631 new_stmt
= build_gimple_modify_stmt (*res
, build2 (LSHIFT_EXPR
,
636 finalize_stmt (new_stmt
);
640 /* This function generates and returns a statement, that cast variable
641 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
642 into RES_P. ORIG_CAST_STMT is the original cast statement. */
645 gen_cast_stmt (tree before_cast
, tree new_type
, tree orig_cast_stmt
,
648 tree lhs
, new_lhs
, new_stmt
;
649 gcc_assert (TREE_CODE (orig_cast_stmt
) == GIMPLE_MODIFY_STMT
);
651 lhs
= GIMPLE_STMT_OPERAND (orig_cast_stmt
, 0);
652 new_lhs
= find_new_var_of_type (lhs
, new_type
);
653 gcc_assert (new_lhs
);
655 new_stmt
= build_gimple_modify_stmt (new_lhs
,
659 finalize_stmt (new_stmt
);
664 /* This function builds an edge between BB and E->dest and updates
665 phi nodes of E->dest. It returns newly created edge. */
668 make_edge_and_fix_phis_of_dest (basic_block bb
, edge e
)
673 new_e
= make_edge (bb
, e
->dest
, e
->flags
);
675 for (phi
= phi_nodes (new_e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
677 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
678 add_phi_arg (phi
, arg
, new_e
);
684 /* This function inserts NEW_STMTS before STMT. */
687 insert_before_stmt (tree stmt
, tree new_stmts
)
689 block_stmt_iterator bsi
;
691 if (!stmt
|| !new_stmts
)
694 bsi
= bsi_for_stmt (stmt
);
695 bsi_insert_before (&bsi
, new_stmts
, BSI_SAME_STMT
);
698 /* Insert NEW_STMTS after STMT. */
701 insert_after_stmt (tree stmt
, tree new_stmts
)
703 block_stmt_iterator bsi
;
705 if (!stmt
|| !new_stmts
)
708 bsi
= bsi_for_stmt (stmt
);
709 bsi_insert_after (&bsi
, new_stmts
, BSI_SAME_STMT
);
712 /* This function returns vector of allocation sites
713 that appear in function FN_DECL. */
716 get_fallocs (tree fn_decl
)
718 return (fallocs_t
) htab_find_with_hash (alloc_sites
, fn_decl
,
719 htab_hash_pointer (fn_decl
));
722 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
723 and it is a part of allocation of a structure,
724 then it is usually followed by a cast stmt
725 p_8 = (struct str_t *) D.2225_7;
726 which is returned by this function. */
729 get_final_alloc_stmt (tree alloc_stmt
)
738 if (TREE_CODE (alloc_stmt
) != GIMPLE_MODIFY_STMT
)
741 alloc_res
= GIMPLE_STMT_OPERAND (alloc_stmt
, 0);
743 if (TREE_CODE (alloc_res
) != SSA_NAME
)
746 if (!single_imm_use (alloc_res
, &use_p
, &final_stmt
))
752 /* This function returns true if STMT is one of allocation
753 sites of function FN_DECL. It returns false otherwise. */
756 is_part_of_malloc (tree stmt
, tree fn_decl
)
758 fallocs_t fallocs
= get_fallocs (fn_decl
);
766 VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
); i
++)
767 if (call
->stmt
== stmt
768 || get_final_alloc_stmt (call
->stmt
) == stmt
)
774 /* Auxiliary structure for a lookup over field accesses. */
775 struct find_stmt_data
781 /* This function looks for DATA->stmt among
782 the statements involved in the field access,
783 defined by SLOT. It stops when it's found. */
786 find_in_field_accs (void **slot
, void *data
)
788 struct field_access_site
*f_acc
=
789 *(struct field_access_site
**) slot
;
790 tree stmt
= ((struct find_stmt_data
*)data
)->stmt
;
792 if (f_acc
->stmt
== stmt
793 || f_acc
->ref_def_stmt
== stmt
794 || f_acc
->cast_stmt
== stmt
)
796 ((struct find_stmt_data
*)data
)->found
= true;
803 /* This function checks whether STMT is part of field
804 accesses of structure STR. It returns true, if found,
805 and false otherwise. */
808 is_part_of_field_access (tree stmt
, d_str str
)
812 for (i
= 0; i
< str
->num_fields
; i
++)
814 struct find_stmt_data data
;
818 if (str
->fields
[i
].acc_sites
)
819 htab_traverse (str
->fields
[i
].acc_sites
, find_in_field_accs
, &data
);
828 /* Auxiliary data for exclude_from_accs function. */
836 /* This function returns component_ref with the BASE and
837 field named FIELD_ID from structure TYPE. */
840 build_comp_ref (tree base
, tree field_id
, tree type
)
846 /* Find field of structure type with the same name as field_id. */
847 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
849 if (DECL_NAME (field
) == field_id
)
858 return build3 (COMPONENT_REF
, TREE_TYPE (field
), base
, field
, NULL_TREE
);
862 /* This struct represent data used for walk_tree
863 called from function find_pos_in_stmt.
864 - ref is a tree to be found,
865 - and pos is a pointer that points to ref in stmt. */
873 /* This is a callback function for walk_tree, called from
874 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
875 When *TP is equal to DATA->ref, the walk_tree stops,
876 and found position, equal to TP, is assigned to DATA->pos. */
879 find_pos_in_stmt_1 (tree
*tp
, int *walk_subtrees
, void * data
)
881 struct ref_pos
* r_pos
= (struct ref_pos
*) data
;
882 tree ref
= r_pos
->ref
;
891 switch (TREE_CODE (t
))
893 case GIMPLE_MODIFY_STMT
:
895 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
896 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
898 walk_tree (&lhs
, find_pos_in_stmt_1
, data
, NULL
);
899 walk_tree (&rhs
, find_pos_in_stmt_1
, data
, NULL
);
911 /* This function looks for the pointer of REF in STMT,
912 It returns it, if found, and NULL otherwise. */
915 find_pos_in_stmt (tree stmt
, tree ref
)
917 struct ref_pos r_pos
;
921 walk_tree (&stmt
, find_pos_in_stmt_1
, &r_pos
, NULL
);
926 /* This structure is used to represent array
927 or pointer-to wrappers of structure type.
928 For example, if type1 is structure type,
929 then for type1 ** we generate two type_wrapper
930 structures with wrap = 0 each one.
931 It's used to unwind the original type up to
932 structure type, replace it with the new structure type
933 and wrap it back in the opposite order. */
935 typedef struct type_wrapper
937 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
940 /* Relevant for arrays as domain or index. */
944 DEF_VEC_O (type_wrapper_t
);
945 DEF_VEC_ALLOC_O (type_wrapper_t
, heap
);
947 /* This function replace field access ACC by the new
948 field access of structure type NEW_TYPE. */
951 replace_field_acc (struct field_access_site
*acc
, tree new_type
)
953 tree ref_var
= acc
->ref
;
958 tree field_id
= DECL_NAME (acc
->field_decl
);
959 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
960 type_wrapper_t
*wr_p
= NULL
;
962 while (TREE_CODE (ref_var
) == INDIRECT_REF
963 || TREE_CODE (ref_var
) == ARRAY_REF
)
967 if ( TREE_CODE (ref_var
) == INDIRECT_REF
)
975 wr
.domain
= TREE_OPERAND (ref_var
, 1);
978 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
979 ref_var
= TREE_OPERAND (ref_var
, 0);
982 new_ref
= find_new_var_of_type (ref_var
, new_type
);
983 finalize_global_creation (new_ref
);
985 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
987 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
989 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
990 if (wr_p
->wrap
) /* Array. */
991 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
992 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
994 new_ref
= build1 (INDIRECT_REF
, type
, new_ref
);
995 VEC_pop (type_wrapper_t
, wrapper
);
998 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
999 VEC_free (type_wrapper_t
, heap
, wrapper
);
1001 if (TREE_CODE (acc
->stmt
) == GIMPLE_MODIFY_STMT
)
1003 lhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 0);
1004 rhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 1);
1007 if (lhs
== acc
->comp_ref
)
1008 GIMPLE_STMT_OPERAND (acc
->stmt
, 0) = new_acc
;
1009 else if (rhs
== acc
->comp_ref
)
1010 GIMPLE_STMT_OPERAND (acc
->stmt
, 1) = new_acc
;
1013 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1020 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1025 finalize_stmt (acc
->stmt
);
1028 /* This function replace field access ACC by a new field access
1029 of structure type NEW_TYPE. */
1032 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1035 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
1036 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1037 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1038 replace_field_acc (acc
, new_type
);
1043 /* This function looks for d_str, represented by TYPE, in the structures
1044 vector. If found, it returns an index of found structure. Otherwise
1045 it returns a length of the structures vector. */
1048 find_structure (tree type
)
1053 type
= TYPE_MAIN_VARIANT (type
);
1055 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
1056 if (is_equal_types (str
->decl
, type
))
1059 return VEC_length (structure
, structures
);
1062 /* In this function we create new statements that have the same
1063 form as ORIG_STMT, but of type NEW_TYPE. The statements
1064 treated by this function are simple assignments,
1065 like assignments: p.8_7 = p; or statements with rhs of
1066 tree codes PLUS_EXPR and MINUS_EXPR. */
1069 create_base_plus_offset (tree orig_stmt
, tree new_type
,
1073 tree new_lhs
, new_rhs
;
1076 gcc_assert (TREE_CODE (orig_stmt
) == GIMPLE_MODIFY_STMT
);
1078 lhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 0);
1079 rhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 1);
1081 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1082 || TREE_CODE (lhs
) == SSA_NAME
);
1084 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1085 gcc_assert (new_lhs
);
1086 finalize_var_creation (new_lhs
);
1088 switch (TREE_CODE (rhs
))
1092 case POINTER_PLUS_EXPR
:
1094 tree op0
= TREE_OPERAND (rhs
, 0);
1095 tree op1
= TREE_OPERAND (rhs
, 1);
1096 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1097 unsigned str0
, str1
;
1098 unsigned length
= VEC_length (structure
, structures
);
1101 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1102 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1103 gcc_assert ((str0
!= length
) || (str1
!= length
));
1106 new_op0
= find_new_var_of_type (op0
, new_type
);
1108 new_op1
= find_new_var_of_type (op1
, new_type
);
1115 new_rhs
= build2 (TREE_CODE (rhs
), TREE_TYPE (new_op0
),
1124 new_stmt
= build_gimple_modify_stmt (new_lhs
, new_rhs
);
1125 finalize_stmt (new_stmt
);
1130 /* Given a field access F_ACC of the FIELD, this function
1131 replaces it by the new field access. */
1134 create_new_field_access (struct field_access_site
*f_acc
,
1135 struct field_entry field
)
1137 tree new_type
= field
.field_mapping
;
1140 tree mult_stmt
, cast_stmt
;
1141 tree cast_res
= NULL
;
1145 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1146 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1149 if (f_acc
->cast_stmt
)
1151 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1152 f_acc
->cast_stmt
, &cast_res
);
1153 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1156 if (f_acc
->ref_def_stmt
)
1164 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1166 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1169 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1170 D.2162_18 by an appropriate variable of new_type type. */
1171 replace_field_access_stmt (f_acc
, new_type
);
1174 /* This function creates a new condition statement
1175 corresponding to the original COND_STMT, adds new basic block
1176 and redirects condition edges. NEW_VAR is a new condition
1177 variable located in the condition statement at the position POS. */
1180 create_new_stmts_for_cond_expr_1 (tree new_var
, tree cond_stmt
, bool pos
)
1184 edge true_e
= NULL
, false_e
= NULL
;
1188 extract_true_false_edges_from_block (bb_for_stmt (cond_stmt
),
1191 new_cond
= unshare_expr (COND_EXPR_COND (cond_stmt
));
1193 TREE_OPERAND (new_cond
, pos
) = new_var
;
1195 new_stmt
= build3 (COND_EXPR
, TREE_TYPE (cond_stmt
),
1196 new_cond
, NULL_TREE
, NULL_TREE
);
1198 finalize_stmt (new_stmt
);
1200 /* Create new basic block after bb. */
1201 new_bb
= create_empty_bb (bb_for_stmt (cond_stmt
));
1203 /* Add new condition stmt to the new_bb. */
1204 stmt_list
= bb_stmt_list (new_bb
);
1205 append_to_statement_list (new_stmt
, &stmt_list
);
1206 add_bb_info (new_bb
, stmt_list
);
1209 /* Create false and true edges from new_bb. */
1210 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1211 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1213 /* Redirect one of original edges to point to new_bb. */
1214 if (TREE_CODE (cond_stmt
) == NE_EXPR
)
1215 redirect_edge_succ (true_e
, new_bb
);
1217 redirect_edge_succ (false_e
, new_bb
);
1220 /* This function creates new condition statements corresponding
1221 to original condition STMT, one for each new type, and
1222 recursively redirect edges to newly generated basic blocks. */
1225 create_new_stmts_for_cond_expr (tree stmt
)
1227 tree cond
= COND_EXPR_COND (stmt
);
1228 tree arg0
, arg1
, arg
;
1229 unsigned str0
, str1
;
1235 unsigned length
= VEC_length (structure
, structures
);
1237 gcc_assert (TREE_CODE (cond
) == EQ_EXPR
1238 || TREE_CODE (cond
) == NE_EXPR
);
1240 arg0
= TREE_OPERAND (cond
, 0);
1241 arg1
= TREE_OPERAND (cond
, 1);
1243 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1244 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1246 s0
= (str0
!= length
) ? true : false;
1247 s1
= (str1
!= length
) ? true : false;
1249 gcc_assert ((!s0
&& s1
) || (!s1
&& s0
));
1251 str
= s0
? VEC_index (structure
, structures
, str0
):
1252 VEC_index (structure
, structures
, str1
);
1253 arg
= s0
? arg0
: arg1
;
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 /* Create a new general access to replace original access ACC
1266 for structure type NEW_TYPE. */
1269 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1271 tree old_stmt
= acc
->stmt
;
1273 tree new_stmt
= unshare_expr (old_stmt
);
1277 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1280 tree new_var
= find_new_var_of_type (var
, new_type
);
1283 gcc_assert (new_var
);
1284 finalize_var_creation (new_var
);
1286 if (TREE_CODE (new_stmt
) == GIMPLE_MODIFY_STMT
)
1289 lhs
= GIMPLE_STMT_OPERAND (new_stmt
, 0);
1290 rhs
= GIMPLE_STMT_OPERAND (new_stmt
, 1);
1292 if (TREE_CODE (lhs
) == SSA_NAME
)
1293 lhs
= SSA_NAME_VAR (lhs
);
1294 if (TREE_CODE (rhs
) == SSA_NAME
)
1295 rhs
= SSA_NAME_VAR (rhs
);
1297 /* It can happen that rhs is a constructor.
1298 Then we have to replace it to be of new_type. */
1299 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
1301 /* Dealing only with empty constructors right now. */
1302 gcc_assert (VEC_empty (constructor_elt
,
1303 CONSTRUCTOR_ELTS (rhs
)));
1304 rhs
= build_constructor (new_type
, 0);
1305 GIMPLE_STMT_OPERAND (new_stmt
, 1) = rhs
;
1309 GIMPLE_STMT_OPERAND (new_stmt
, 0) = new_var
;
1310 else if (rhs
== var
)
1311 GIMPLE_STMT_OPERAND (new_stmt
, 1) = new_var
;
1314 pos
= find_pos_in_stmt (new_stmt
, var
);
1321 pos
= find_pos_in_stmt (new_stmt
, var
);
1327 finalize_stmt (new_stmt
);
1331 /* For each new type in STR this function creates new general accesses
1332 corresponding to the original access ACC. */
1335 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1338 tree stmt
= acc
->stmt
;
1341 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1345 new_stmt
= create_general_new_stmt (acc
, type
);
1346 insert_after_stmt (stmt
, new_stmt
);
1350 /* This function creates a new general access of structure STR
1351 to replace the access ACC. */
1354 create_new_general_access (struct access_site
*acc
, d_str str
)
1356 tree stmt
= acc
->stmt
;
1357 switch (TREE_CODE (stmt
))
1360 create_new_stmts_for_cond_expr (stmt
);
1364 create_new_stmts_for_general_acc (acc
, str
);
1368 /* Auxiliary data for creation of accesses. */
1369 struct create_acc_data
1376 /* This function creates a new general access, defined by SLOT.
1377 DATA is a pointer to create_acc_data structure. */
1380 create_new_acc (void **slot
, void *data
)
1382 struct access_site
*acc
= *(struct access_site
**) slot
;
1383 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1384 d_str str
= ((struct create_acc_data
*)data
)->str
;
1386 if (bb_for_stmt (acc
->stmt
) == bb
)
1387 create_new_general_access (acc
, str
);
1391 /* This function creates a new field access, defined by SLOT.
1392 DATA is a pointer to create_acc_data structure. */
1395 create_new_field_acc (void **slot
, void *data
)
1397 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1398 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1399 d_str str
= ((struct create_acc_data
*)data
)->str
;
1400 int i
= ((struct create_acc_data
*)data
)->field_index
;
1402 if (bb_for_stmt (f_acc
->stmt
) == bb
)
1403 create_new_field_access (f_acc
, str
->fields
[i
]);
1407 /* This function creates new accesses for the structure
1408 type STR in basic block BB. */
1411 create_new_accs_for_struct (d_str str
, basic_block bb
)
1414 struct create_acc_data dt
;
1418 dt
.field_index
= -1;
1420 for (i
= 0; i
< str
->num_fields
; i
++)
1424 if (str
->fields
[i
].acc_sites
)
1425 htab_traverse (str
->fields
[i
].acc_sites
,
1426 create_new_field_acc
, &dt
);
1429 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1432 /* This function inserts new variables from new_var,
1433 defined by SLOT, into varpool. */
1436 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1438 new_var n_var
= *(new_var
*) slot
;
1442 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1443 insert_global_to_varpool (var
);
1447 /* This function prints a field access site, defined by SLOT. */
1450 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1452 struct field_access_site
*f_acc
=
1453 *(struct field_access_site
**) slot
;
1455 fprintf(dump_file
, "\n");
1457 print_generic_stmt (dump_file
, f_acc
->stmt
, 0);
1458 if (f_acc
->ref_def_stmt
)
1459 print_generic_stmt (dump_file
, f_acc
->ref_def_stmt
, 0);
1460 if (f_acc
->cast_stmt
)
1461 print_generic_stmt (dump_file
, f_acc
->cast_stmt
, 0);
1465 /* Print field accesses from hashtable F_ACCS. */
1468 dump_field_acc_sites (htab_t f_accs
)
1474 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1477 /* Hash value for fallocs_t. */
1480 malloc_hash (const void *x
)
1482 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1485 /* This function returns nonzero if function of func_alloc_sites' X
1489 malloc_eq (const void *x
, const void *y
)
1491 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1494 /* This function is a callback for traversal over a structure accesses.
1495 It frees an access represented by SLOT. */
1498 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1500 struct access_site
* acc
= *(struct access_site
**) slot
;
1502 VEC_free (tree
, heap
, acc
->vars
);
1507 /* This is a callback function for traversal over field accesses.
1508 It frees a field access represented by SLOT. */
1511 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1513 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1519 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1520 if it is not there yet. */
1523 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1531 type
= TYPE_MAIN_VARIANT (type
);
1533 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1534 if (is_equal_types (t
, type
))
1537 if (i
== VEC_length (tree
, *unsuitable_types
))
1538 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1541 /* Given a type TYPE, this function returns the name of the type. */
1544 get_type_name (tree type
)
1546 if (! TYPE_NAME (type
))
1549 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1550 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1551 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1552 && DECL_NAME (TYPE_NAME (type
)))
1553 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1558 /* This function is a temporary hack to overcome the types problem.
1559 When several compilation units are compiled together
1560 with -combine, the TYPE_MAIN_VARIANT of the same type
1561 can appear differently in different compilation units.
1562 Therefore this function first compares type names.
1563 If there are no names, structure bodies are recursively
1567 is_equal_types (tree type1
, tree type2
)
1569 const char * name1
,* name2
;
1571 if ((!type1
&& type2
)
1572 ||(!type2
&& type1
))
1575 if (!type1
&& !type2
)
1578 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1584 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1587 name1
= get_type_name (type1
);
1588 name2
= get_type_name (type2
);
1590 if (name1
&& name2
&& !strcmp (name1
, name2
))
1593 if (name1
&& name2
&& strcmp (name1
, name2
))
1596 switch (TREE_CODE (type1
))
1599 case REFERENCE_TYPE
:
1601 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1607 case QUAL_UNION_TYPE
:
1611 /* Compare fields of struture. */
1612 for (field1
= TYPE_FIELDS (type1
); field1
;
1613 field1
= TREE_CHAIN (field1
))
1615 tree field2
= find_field_in_struct_1 (type2
, field1
);
1625 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1626 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1634 tree max1
, min1
, max2
, min2
;
1636 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1639 d1
= TYPE_DOMAIN (type1
);
1640 d2
= TYPE_DOMAIN (type2
);
1645 max1
= TYPE_MAX_VALUE (d1
);
1646 max2
= TYPE_MAX_VALUE (d2
);
1647 min1
= TYPE_MIN_VALUE (d1
);
1648 min2
= TYPE_MIN_VALUE (d2
);
1650 if (max1
&& max2
&& min1
&& min2
1651 && TREE_CODE (max1
) == TREE_CODE (max2
)
1652 && TREE_CODE (max1
) == INTEGER_CST
1653 && TREE_CODE (min1
) == TREE_CODE (min2
)
1654 && TREE_CODE (min1
) == INTEGER_CST
1655 && tree_int_cst_equal (max1
, max2
)
1656 && tree_int_cst_equal (min1
, min2
))
1668 /* This function free non-field accesses from hashtable ACCS. */
1671 free_accesses (htab_t accs
)
1674 htab_traverse (accs
, free_accs
, NULL
);
1678 /* This function free field accesses hashtable F_ACCS. */
1681 free_field_accesses (htab_t f_accs
)
1684 htab_traverse (f_accs
, free_field_accs
, NULL
);
1685 htab_delete (f_accs
);
1688 /* Update call graph with new edge generated by new MALLOC_STMT.
1689 The edge origin is CONTEXT function. */
1692 update_cgraph_with_malloc_call (tree malloc_stmt
, tree context
)
1695 struct cgraph_node
*src
, *dest
;
1696 tree malloc_fn_decl
;
1701 call_expr
= get_call_expr_in (malloc_stmt
);
1702 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1704 src
= cgraph_node (context
);
1705 dest
= cgraph_node (malloc_fn_decl
);
1706 cgraph_create_edge (src
, dest
, malloc_stmt
,
1707 0, 0, bb_for_stmt (malloc_stmt
)->loop_depth
);
1710 /* This function generates set of statements required
1711 to allocate number NUM of structures of type NEW_TYPE.
1712 The statements are stored in NEW_STMTS. The statement that contain
1713 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1716 create_new_malloc (tree malloc_stmt
, tree new_type
, tree
*new_stmts
, tree num
)
1718 tree new_malloc_size
;
1719 tree call_expr
, malloc_fn_decl
;
1720 tree new_stmt
, malloc_res
;
1721 tree call_stmt
, final_stmt
;
1724 gcc_assert (num
&& malloc_stmt
&& new_type
);
1725 *new_stmts
= alloc_stmt_list ();
1727 /* Generate argument to malloc as multiplication of num
1728 and size of new_type. */
1729 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1730 append_to_statement_list (new_stmt
, new_stmts
);
1732 /* Generate new call for malloc. */
1733 malloc_res
= create_tmp_var (integer_type_node
, NULL
);
1736 add_referenced_var (malloc_res
);
1738 call_expr
= get_call_expr_in (malloc_stmt
);
1739 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1740 call_expr
= build_call_expr (malloc_fn_decl
, 1, new_malloc_size
);
1741 call_stmt
= build_gimple_modify_stmt (malloc_res
, call_expr
);
1742 finalize_stmt_and_append (new_stmts
, call_stmt
);
1744 /* Create new cast statement. */
1745 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1746 gcc_assert (final_stmt
);
1747 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1748 append_to_statement_list (new_stmt
, new_stmts
);
1753 /* This function returns a tree representing
1754 the number of instances of structure STR_DECL allocated
1755 by allocation STMT. If new statments are generated,
1756 they are filled into NEW_STMTS_P. */
1759 gen_num_of_structs_in_malloc (tree stmt
, tree str_decl
, tree
*new_stmts_p
)
1761 call_expr_arg_iterator iter
;
1765 HOST_WIDE_INT struct_size_int
;
1770 /* Get malloc argument. */
1771 call_expr
= get_call_expr_in (stmt
);
1775 arg
= first_call_expr_arg (call_expr
, &iter
);
1777 if (TREE_CODE (arg
) != SSA_NAME
1778 && !TREE_CONSTANT (arg
))
1781 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1782 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1784 gcc_assert (struct_size
);
1786 if (TREE_CODE (arg
) == SSA_NAME
)
1790 if (is_result_of_mult (arg
, &num
, struct_size
))
1793 num
= create_tmp_var (integer_type_node
, NULL
);
1796 add_referenced_var (num
);
1798 if (exact_log2 (struct_size_int
) == -1)
1799 div_stmt
= build_gimple_modify_stmt (num
,
1800 build2 (TRUNC_DIV_EXPR
,
1805 tree C
= build_int_cst (integer_type_node
,
1806 exact_log2 (struct_size_int
));
1809 build_gimple_modify_stmt (num
, build2 (RSHIFT_EXPR
,
1813 *new_stmts_p
= alloc_stmt_list ();
1814 append_to_statement_list (div_stmt
,
1816 finalize_stmt (div_stmt
);
1820 if (CONSTANT_CLASS_P (arg
)
1821 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1822 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1827 /* This function is a callback for traversal on new_var's hashtable.
1828 SLOT is a pointer to new_var. This function prints to dump_file
1829 an original variable and all new variables from the new_var
1830 pointed by *SLOT. */
1833 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1835 new_var n_var
= *(new_var
*) slot
;
1840 var_type
= get_type_of_var (n_var
->orig_var
);
1842 fprintf (dump_file
, "\nOrig var: ");
1843 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1844 fprintf (dump_file
, " of type ");
1845 print_generic_expr (dump_file
, var_type
, 0);
1846 fprintf (dump_file
, "\n");
1849 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1851 var_type
= get_type_of_var (var
);
1853 fprintf (dump_file
, " ");
1854 print_generic_expr (dump_file
, var
, 0);
1855 fprintf (dump_file
, " of type ");
1856 print_generic_expr (dump_file
, var_type
, 0);
1857 fprintf (dump_file
, "\n");
1862 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1865 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1868 DECL_ARTIFICIAL (new_decl
) = 1;
1869 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1870 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1871 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1872 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1873 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1874 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1875 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1877 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1879 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1880 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1884 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1885 the same way as a structure type is wrapped in DECL.
1886 It returns the generated type. */
1889 gen_struct_type (tree decl
, tree new_str_type
)
1891 tree type_orig
= get_type_of_var (decl
);
1892 tree new_type
= new_str_type
;
1893 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1895 type_wrapper_t
*wr_p
;
1897 while (POINTER_TYPE_P (type_orig
)
1898 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1900 if (POINTER_TYPE_P (type_orig
))
1903 wr
.domain
= NULL_TREE
;
1905 else if (TREE_CODE (type_orig
) == ARRAY_TYPE
)
1908 wr
.domain
= TYPE_DOMAIN (type_orig
);
1910 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1911 type_orig
= TREE_TYPE (type_orig
);
1914 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1916 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1918 if (wr_p
->wrap
) /* Array. */
1919 new_type
= build_array_type (new_type
, wr_p
->domain
);
1921 new_type
= build_pointer_type (new_type
);
1923 VEC_pop (type_wrapper_t
, wrapper
);
1926 VEC_free (type_wrapper_t
, heap
, wrapper
);
1930 /* This function generates and returns new variable name based on
1931 ORIG_DECL name, combined with index I.
1932 The form of the new name is <orig_name>.<I> . */
1935 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1937 const char *old_name
;
1941 if (!DECL_NAME (orig_decl
)
1942 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1945 /* If the original variable has a name, create an
1946 appropriate new name for the new variable. */
1948 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1949 prefix
= alloca (strlen (old_name
) + 1);
1950 strcpy (prefix
, old_name
);
1951 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1952 return get_identifier (new_name
);
1955 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1958 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1962 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1963 htab_hash_pointer (new_node
->orig_var
),
1968 /* This function creates and returns new_var_data node
1969 with empty new_vars and orig_var equal to VAR. */
1972 create_new_var_node (tree var
, d_str str
)
1976 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1977 node
->orig_var
= var
;
1978 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1982 /* Check whether the type of VAR is potential candidate for peeling.
1983 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1984 candidate type. If VAR is initialized, the type of VAR will be added
1985 to UNSUITABLE_TYPES. */
1988 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
1991 bool initialized
= false;
1998 /* There is no support of initialized vars. */
1999 if (TREE_CODE (var
) == VAR_DECL
2000 && DECL_INITIAL (var
) != NULL_TREE
)
2003 type
= get_type_of_var (var
);
2007 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2008 if (TREE_CODE (type
) != RECORD_TYPE
)
2012 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2016 fprintf (dump_file
, "The type ");
2017 print_generic_expr (dump_file
, type
, 0);
2018 fprintf (dump_file
, " is initialized...Excluded.");
2020 add_unsuitable_type (unsuitable_types
, type
);
2030 /* Hash value for field_access_site. */
2033 field_acc_hash (const void *x
)
2035 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2038 /* This function returns nonzero if stmt of field_access_site X
2042 field_acc_eq (const void *x
, const void *y
)
2044 return ((const struct field_access_site
*)x
)->stmt
== (const_tree
)y
;
2047 /* This function prints an access site, defined by SLOT. */
2050 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2052 struct access_site
*acc
= *(struct access_site
**) slot
;
2056 fprintf(dump_file
, "\n");
2058 print_generic_stmt (dump_file
, acc
->stmt
, 0);
2059 fprintf(dump_file
, " : ");
2061 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2063 print_generic_expr (dump_file
, var
, 0);
2064 fprintf(dump_file
, ", ");
2069 /* This function frees memory allocated for strcuture clusters,
2070 starting from CLUSTER. */
2073 free_struct_cluster (struct field_cluster
* cluster
)
2077 if (cluster
->fields_in_cluster
)
2078 sbitmap_free (cluster
->fields_in_cluster
);
2079 if (cluster
->sibling
)
2080 free_struct_cluster (cluster
->sibling
);
2085 /* Free all allocated memory under the structure node pointed by D_NODE. */
2088 free_data_struct (d_str d_node
)
2097 fprintf (dump_file
, "\nRemoving data structure \"");
2098 print_generic_expr (dump_file
, d_node
->decl
, 0);
2099 fprintf (dump_file
, "\" from data_struct_list.");
2102 /* Free all space under d_node. */
2105 for (i
= 0; i
< d_node
->num_fields
; i
++)
2106 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2107 free (d_node
->fields
);
2111 free_accesses (d_node
->accs
);
2113 if (d_node
->struct_clustering
)
2114 free_struct_cluster (d_node
->struct_clustering
);
2116 if (d_node
->new_types
)
2117 VEC_free (tree
, heap
, d_node
->new_types
);
2120 /* This function creates new general and field accesses in BB. */
2123 create_new_accesses_in_bb (basic_block bb
)
2128 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2129 create_new_accs_for_struct (str
, bb
);
2132 /* This function adds allocation sites for peeled structures.
2133 M_DATA is vector of allocation sites of function CONTEXT. */
2136 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2142 VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2144 tree stmt
= call
->stmt
;
2145 d_str str
= call
->str
;
2147 tree new_stmts
= NULL_TREE
;
2148 tree last_stmt
= get_final_alloc_stmt (stmt
);
2152 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2155 last_stmt
= tsi_stmt (tsi_last (new_stmts
));
2156 insert_after_stmt (last_stmt
, new_stmts
);
2159 /* Generate an allocation sites for each new structure type. */
2161 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2163 tree new_malloc_stmt
= NULL_TREE
;
2164 tree last_stmt_tmp
= NULL_TREE
;
2166 new_stmts
= NULL_TREE
;
2167 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2168 last_stmt_tmp
= tsi_stmt (tsi_last (new_stmts
));
2169 insert_after_stmt (last_stmt
, new_stmts
);
2170 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2171 last_stmt
= last_stmt_tmp
;
2176 /* This function prints new variables from hashtable
2177 NEW_VARS_HTAB to dump_file. */
2180 dump_new_vars (htab_t new_vars_htab
)
2186 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2189 /* Given an original variable ORIG_DECL of structure type STR,
2190 this function generates new variables of the types defined
2191 by STR->new_type. Generated types are saved in new_var node NODE.
2192 ORIG_DECL should has VAR_DECL tree_code. */
2195 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2201 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2203 tree new_decl
= NULL
;
2206 new_name
= gen_var_name (orig_decl
, i
);
2207 type
= gen_struct_type (orig_decl
, type
);
2209 if (is_global_var (orig_decl
))
2210 new_decl
= build_decl (VAR_DECL
, new_name
, type
);
2213 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2214 new_decl
= create_tmp_var (type
, name
);
2217 copy_decl_attributes (new_decl
, orig_decl
);
2218 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2222 /* This function creates new variables to
2223 substitute the original variable VAR_DECL and adds
2224 them to the new_var's hashtable NEW_VARS_HTAB. */
2227 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2234 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2237 if (!is_candidate (var_decl
, &type
, NULL
))
2240 i
= find_structure (type
);
2241 if (i
== VEC_length (structure
, structures
))
2244 str
= VEC_index (structure
, structures
, i
);
2245 node
= create_new_var_node (var_decl
, str
);
2246 create_new_var_1 (var_decl
, str
, node
);
2247 add_to_new_vars_htab (node
, new_vars_htab
);
2250 /* Hash value for new_var. */
2253 new_var_hash (const void *x
)
2255 return htab_hash_pointer (((const_new_var
)x
)->orig_var
);
2258 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2261 new_var_eq (const void *x
, const void *y
)
2263 return ((const_new_var
)x
)->orig_var
== (const_tree
)y
;
2266 /* This function check whether a structure type represented by STR
2267 escapes due to ipa-type-escape analysis. If yes, this type is added
2268 to UNSUITABLE_TYPES vector. */
2271 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2273 tree type
= str
->decl
;
2275 if (!ipa_type_escape_type_contained_p (type
))
2279 fprintf (dump_file
, "\nEscaping type is ");
2280 print_generic_expr (dump_file
, type
, 0);
2282 add_unsuitable_type (unsuitable_types
, type
);
2286 /* Hash value for access_site. */
2289 acc_hash (const void *x
)
2291 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2294 /* Return nonzero if stmt of access_site X is equal to Y. */
2297 acc_eq (const void *x
, const void *y
)
2299 return ((const struct access_site
*)x
)->stmt
== (const_tree
)y
;
2302 /* Given a structure declaration STRUCT_DECL, and number of fields
2303 in the structure NUM_FIELDS, this function creates and returns
2304 corresponding field_entry's. */
2306 static struct field_entry
*
2307 get_fields (tree struct_decl
, int num_fields
)
2309 struct field_entry
*list
;
2310 tree t
= TYPE_FIELDS (struct_decl
);
2314 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2316 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2317 if (TREE_CODE (t
) == FIELD_DECL
)
2319 list
[idx
].index
= idx
;
2321 list
[idx
].acc_sites
=
2322 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2323 list
[idx
].count
= 0;
2324 list
[idx
].field_mapping
= NULL_TREE
;
2330 /* Print non-field accesses from hashtable ACCS of structure. */
2333 dump_access_sites (htab_t accs
)
2339 htab_traverse (accs
, dump_acc
, NULL
);
2342 /* This function removes the structure with index I from structures vector. */
2345 remove_structure (unsigned i
)
2349 if (i
>= VEC_length (structure
, structures
))
2352 str
= VEC_index (structure
, structures
, i
);
2353 free_data_struct (str
);
2354 VEC_ordered_remove (structure
, structures
, i
);
2357 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2358 COND_STNT is a condition statement to check. */
2361 is_safe_cond_expr (tree cond_stmt
)
2365 unsigned str0
, str1
;
2367 unsigned length
= VEC_length (structure
, structures
);
2369 tree cond
= COND_EXPR_COND (cond_stmt
);
2371 if (TREE_CODE (cond
) != EQ_EXPR
2372 && TREE_CODE (cond
) != NE_EXPR
)
2375 if (TREE_CODE_LENGTH (TREE_CODE (cond
)) != 2)
2378 arg0
= TREE_OPERAND (cond
, 0);
2379 arg1
= TREE_OPERAND (cond
, 1);
2381 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2382 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2384 s0
= (str0
!= length
) ? true : false;
2385 s1
= (str1
!= length
) ? true : false;
2387 if (!((!s0
&& s1
) || (!s1
&& s0
)))
2393 /* This function excludes statements, that are
2394 part of allocation sites or field accesses, from the
2395 hashtable of general accesses. SLOT represents general
2396 access that will be checked. DATA is a pointer to
2397 exclude_data structure. */
2400 exclude_from_accs (void **slot
, void *data
)
2402 struct access_site
*acc
= *(struct access_site
**) slot
;
2403 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2404 d_str str
= ((struct exclude_data
*)data
)->str
;
2406 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2407 || is_part_of_field_access (acc
->stmt
, str
))
2409 VEC_free (tree
, heap
, acc
->vars
);
2411 htab_clear_slot (str
->accs
, slot
);
2416 /* Callback function for walk_tree called from collect_accesses_in_bb
2417 function. DATA is the statement which is analyzed. */
2420 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2422 tree stmt
= (tree
) data
;
2428 switch (TREE_CODE (t
))
2430 case GIMPLE_MODIFY_STMT
:
2432 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
2433 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
2435 walk_tree (&lhs
, get_stmt_accesses
, data
, NULL
);
2436 walk_tree (&rhs
, get_stmt_accesses
, data
, NULL
);
2443 tree var
= TREE_OPERAND(t
, 0);
2444 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2445 unsigned i
= find_structure (type
);
2447 if (i
!= VEC_length (structure
, structures
))
2451 fprintf (dump_file
, "\nThe type ");
2452 print_generic_expr (dump_file
, type
, 0);
2453 fprintf (dump_file
, " has bitfield.");
2455 remove_structure (i
);
2462 tree ref
= TREE_OPERAND (t
, 0);
2463 tree field_decl
= TREE_OPERAND (t
, 1);
2466 if ((TREE_CODE (ref
) == INDIRECT_REF
2467 || TREE_CODE (ref
) == ARRAY_REF
2468 || TREE_CODE (ref
) == VAR_DECL
)
2469 && TREE_CODE (field_decl
) == FIELD_DECL
)
2471 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2472 unsigned i
= find_structure (type
);
2474 if (i
!= VEC_length (structure
, structures
))
2476 d_str str
= VEC_index (structure
, structures
, i
);
2477 struct field_entry
* field
=
2478 find_field_in_struct (str
, field_decl
);
2482 struct field_access_site
*acc
= make_field_acc_node ();
2489 acc
->field_decl
= field_decl
;
2491 /* Check whether the access is of the form
2492 we can deal with. */
2493 if (!decompose_access (str
->decl
, acc
))
2497 fprintf (dump_file
, "\nThe type ");
2498 print_generic_expr (dump_file
, type
, 0);
2500 " has complicate access in statement ");
2501 print_generic_stmt (dump_file
, stmt
, 0);
2504 remove_structure (i
);
2509 /* Increase count of field. */
2510 basic_block bb
= bb_for_stmt (stmt
);
2511 field
->count
+= bb
->count
;
2513 /* Add stmt to the acc_sites of field. */
2514 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2526 tree op0
= TREE_OPERAND (t
, 0);
2527 tree op1
= TREE_OPERAND (t
, 1);
2529 walk_tree (&op0
, get_stmt_accesses
, data
, NULL
);
2530 walk_tree (&op1
, get_stmt_accesses
, data
, NULL
);
2537 tree cond
= COND_EXPR_COND (t
);
2539 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2541 tree t
= TREE_OPERAND (cond
, i
);
2544 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2555 if (TREE_CODE (t
) == SSA_NAME
)
2556 t
= SSA_NAME_VAR (t
);
2558 i
= find_structure (strip_type (get_type_of_var (t
)));
2559 if (i
!= VEC_length (structure
, structures
))
2563 str
= VEC_index (structure
, structures
, i
);
2564 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2572 /* It was checked as part of stage1 that structures
2573 to be transformed cannot be passed as parameters of functions. */
2585 /* Free structures hashtable. */
2588 free_structures (void)
2593 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2594 free_data_struct (str
);
2596 VEC_free (structure
, heap
, structures
);
2600 /* This function is a callback for traversal over new_var's hashtable.
2601 SLOT is a pointer to new_var. This function frees memory allocated
2602 for new_var and pointed by *SLOT. */
2605 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2607 new_var n_var
= *(new_var
*) slot
;
2609 /* Free vector of new_vars. */
2610 VEC_free (tree
, heap
, n_var
->new_vars
);
2615 /* Free new_vars hashtable NEW_VARS_HTAB. */
2618 free_new_vars_htab (htab_t new_vars_htab
)
2621 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2622 htab_delete (new_vars_htab
);
2623 new_vars_htab
= NULL
;
2626 /* This function creates new general and field accesses that appear in cfun. */
2629 create_new_accesses_for_func (void)
2633 FOR_EACH_BB_FN (bb
, cfun
)
2634 create_new_accesses_in_bb (bb
);
2637 /* Create new allocation sites for the function represented by NODE. */
2640 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2642 fallocs_t fallocs
= get_fallocs (node
->decl
);
2645 create_new_alloc_sites (fallocs
, node
->decl
);
2648 /* For each local variable of structure type from the vector of structures
2649 this function generates new variable(s) to replace it. */
2652 create_new_local_vars (void)
2655 referenced_var_iterator rvi
;
2657 new_local_vars
= htab_create (num_referenced_vars
,
2658 new_var_hash
, new_var_eq
, NULL
);
2660 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2662 if (!is_global_var (var
))
2663 create_new_var (var
, new_local_vars
);
2667 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2668 dump_new_vars (new_local_vars
);
2671 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2674 print_shift (unsigned HOST_WIDE_INT shift
)
2676 unsigned HOST_WIDE_INT sh
= shift
;
2679 fprintf (dump_file
, " ");
2682 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2685 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2686 struct field_entry
* fields
, int num_fields
)
2690 for (i
= 0; i
< num_fields
; i
++)
2691 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2692 fields
[i
].field_mapping
= new_type
;
2695 /* This functions builds structure with FIELDS,
2696 NAME and attributes similar to ORIG_STRUCT.
2697 It returns the newly created structure. */
2700 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2702 tree attributes
= NULL_TREE
;
2706 if (TYPE_ATTRIBUTES (orig_struct
))
2707 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2708 ref
= make_node (RECORD_TYPE
);
2709 TYPE_SIZE (ref
) = 0;
2710 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2711 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2712 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2714 DECL_CONTEXT (x
) = ref
;
2715 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2717 TYPE_FIELDS (ref
) = fields
;
2719 TYPE_NAME (ref
) = name
;
2724 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2725 of preparation for new structure building. NUM_FIELDS is a total
2726 number of fields in the structure. The function returns newly
2727 generated fields. */
2730 create_fields (struct field_cluster
* cluster
,
2731 struct field_entry
* fields
, int num_fields
)
2734 tree new_types
= NULL_TREE
;
2735 tree last
= NULL_TREE
;
2737 for (i
= 0; i
< num_fields
; i
++)
2738 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2740 tree new_decl
= unshare_expr (fields
[i
].decl
);
2743 new_types
= new_decl
;
2745 TREE_CHAIN (last
) = new_decl
;
2749 TREE_CHAIN (last
) = NULL_TREE
;
2754 /* This function creates a cluster name. The name is based on
2755 the original structure name, if it is present. It has a form:
2757 <original_struct_name>_sub.<CLUST_NUM>
2759 The original structure name is taken from the type of DECL.
2760 If an original structure name is not present, it's generated to be:
2764 The function returns identifier of the new cluster name. */
2767 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2769 const char * orig_name
= get_type_name (decl
);
2770 char * tmp_name
= NULL
;
2776 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2778 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2779 prefix
= alloca (len
+ 1);
2780 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2781 strlen (tmp_name
? tmp_name
: orig_name
));
2782 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2784 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2785 return get_identifier (new_name
);
2788 /* This function checks whether the structure STR has bitfields.
2789 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2792 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2794 tree type
= str
->decl
;
2797 for (i
= 0; i
< str
->num_fields
; i
++)
2798 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2800 add_unsuitable_type (unsuitable_types
, type
);
2803 fprintf (dump_file
, "\nType ");
2804 print_generic_expr (dump_file
, type
, 0);
2805 fprintf (dump_file
, "\nescapes due to bitfield ");
2806 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2812 /* This function adds to UNSUITABLE_TYPES those types that escape
2813 due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h]. */
2816 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2821 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2822 check_type_escape (str
, unsuitable_types
);
2825 /* If a structure type is a return type of any function,
2826 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2829 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2831 struct cgraph_node
*c_node
;
2833 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2835 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2839 ret_t
= strip_type (ret_t
);
2840 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2842 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2845 fprintf (dump_file
, "\nThe type \"");
2846 print_generic_expr (dump_file
, ret_t
, 0);
2848 "\" is return type of function...Excluded.");
2855 /* This function looks for parameters of local functions
2856 which are of structure types, or derived from them (arrays
2857 of structures, pointers to structures, or their combinations).
2858 We are not handling peeling of such structures right now.
2859 The found structures types are added to UNSUITABLE_TYPES vector. */
2862 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2864 struct cgraph_node
*c_node
;
2866 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2867 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2869 tree fn
= c_node
->decl
;
2872 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2874 tree type
= TREE_TYPE (arg
);
2876 type
= strip_type (type
);
2877 if (TREE_CODE (type
) == RECORD_TYPE
)
2879 add_unsuitable_type (unsuitable_types
,
2880 TYPE_MAIN_VARIANT (type
));
2883 fprintf (dump_file
, "\nPointer to type \"");
2884 print_generic_expr (dump_file
, type
, 0);
2886 "\" is passed to local function...Excluded.");
2893 /* This function analyzes structure form of structures
2894 potential for transformation. If we are not capable to transform
2895 structure of some form, we remove it from the structures hashtable.
2896 Right now we cannot handle nested structs, when nesting is
2897 through any level of pointers or arrays.
2899 TBD: release these constrains in future.
2901 Note, that in this function we suppose that all structures
2902 in the program are members of the structures hashtable right now,
2903 without excluding escaping types. */
2906 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2910 for (i
= 0; i
< str
->num_fields
; i
++)
2912 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2914 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2916 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2917 add_unsuitable_type (unsuitable_types
, str
->decl
);
2920 fprintf (dump_file
, "\nType ");
2921 print_generic_expr (dump_file
, f_type
, 0);
2922 fprintf (dump_file
, " is a field in the structure ");
2923 print_generic_expr (dump_file
, str
->decl
, 0);
2924 fprintf (dump_file
, ". Escaping...");
2930 /* This function adds a structure TYPE to the vector of structures,
2931 if it's not already there. */
2934 add_structure (tree type
)
2936 struct data_structure node
;
2940 type
= TYPE_MAIN_VARIANT (type
);
2942 i
= find_structure (type
);
2944 if (i
!= VEC_length (structure
, structures
))
2947 num_fields
= fields_length (type
);
2949 node
.num_fields
= num_fields
;
2950 node
.fields
= get_fields (type
, num_fields
);
2951 node
.struct_clustering
= NULL
;
2952 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
2953 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
2956 VEC_safe_push (structure
, heap
, structures
, &node
);
2960 fprintf (dump_file
, "\nAdding data structure \"");
2961 print_generic_expr (dump_file
, type
, 0);
2962 fprintf (dump_file
, "\" to data_struct_list.");
2966 /* This function adds an allocation site to alloc_sites hashtable.
2967 The allocation site appears in STMT of function FN_DECL and
2968 allocates the structure represented by STR. */
2971 add_alloc_site (tree fn_decl
, tree stmt
, d_str str
)
2973 fallocs_t fallocs
= NULL
;
2974 alloc_site_t m_call
;
2980 (fallocs_t
) htab_find_with_hash (alloc_sites
,
2981 fn_decl
, htab_hash_pointer (fn_decl
));
2987 fallocs
= (fallocs_t
)
2988 xmalloc (sizeof (struct func_alloc_sites
));
2989 fallocs
->func
= fn_decl
;
2990 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
2991 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
2992 htab_hash_pointer (fn_decl
), INSERT
);
2995 VEC_safe_push (alloc_site_t
, heap
,
2996 fallocs
->allocs
, &m_call
);
3000 fprintf (dump_file
, "\nAdding stmt ");
3001 print_generic_stmt (dump_file
, stmt
, 0);
3002 fprintf (dump_file
, " to list of mallocs.");
3006 /* This function returns true if the result of STMT, that contains a call
3007 to an allocation function, is cast to one of the structure types.
3008 STMT should be of the form: T.2 = <alloc_func> (T.1);
3009 If true, I_P contains an index of an allocated structure.
3010 Otherwise I_P contains the length of the vector of structures. */
3013 is_alloc_of_struct (tree stmt
, unsigned *i_p
)
3019 final_stmt
= get_final_alloc_stmt (stmt
);
3024 /* final_stmt should be of the form:
3025 T.3 = (struct_type *) T.2; */
3027 if (TREE_CODE (final_stmt
) != GIMPLE_MODIFY_STMT
)
3030 lhs
= GIMPLE_STMT_OPERAND (final_stmt
, 0);
3032 type
= get_type_of_var (lhs
);
3037 if (!POINTER_TYPE_P (type
)
3038 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3041 *i_p
= find_structure (strip_type (type
));
3043 if (*i_p
== VEC_length (structure
, structures
))
3049 /* This function prints non-field and field accesses
3050 of the structure STR. */
3053 dump_accs (d_str str
)
3057 fprintf (dump_file
, "\nAccess sites of struct ");
3058 print_generic_expr (dump_file
, str
->decl
, 0);
3060 for (i
= 0; i
< str
->num_fields
; i
++)
3062 fprintf (dump_file
, "\nAccess site of field ");
3063 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3064 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3065 fprintf (dump_file
, ":\n");
3067 fprintf (dump_file
, "\nGeneral access sites\n");
3068 dump_access_sites (str
->accs
);
3071 /* This function checks whether an access statement, pointed by SLOT,
3072 is a condition we are capable to transform. If not, it removes
3073 the structure with index, represented by DATA, from the vector
3077 safe_cond_expr_check (void **slot
, void *data
)
3079 struct access_site
*acc
= *(struct access_site
**) slot
;
3081 if (TREE_CODE (acc
->stmt
) == COND_EXPR
)
3083 if (!is_safe_cond_expr (acc
->stmt
))
3087 fprintf (dump_file
, "\nUnsafe conditional statement ");
3088 print_generic_stmt (dump_file
, acc
->stmt
, 0);
3090 remove_structure (*(unsigned *) data
);
3096 /* This function excludes statements that are part of allocation sites and
3097 field accesses from the hashtable of general accesses of the structure
3098 type STR. Only accesses that belong to the function represented by
3099 NODE are treated. */
3102 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3104 struct exclude_data dt
;
3106 dt
.fn_decl
= node
->decl
;
3109 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3112 /* Collect accesses to the structure types that apear in basic bloack BB. */
3115 collect_accesses_in_bb (basic_block bb
)
3117 block_stmt_iterator bsi
;
3119 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
3121 tree stmt
= bsi_stmt (bsi
);
3123 /* In asm stmt we cannot always track the arguments,
3124 so we just give up. */
3125 if (TREE_CODE (stmt
) == ASM_EXPR
)
3131 walk_tree (&stmt
, get_stmt_accesses
, stmt
, NULL
);
3135 /* This function generates cluster substructure that cointains FIELDS.
3136 The cluster added to the set of clusters of the structure SRT. */
3139 gen_cluster (sbitmap fields
, d_str str
)
3141 struct field_cluster
*crr_cluster
= NULL
;
3144 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3145 crr_cluster
->sibling
= str
->struct_clustering
;
3146 str
->struct_clustering
= crr_cluster
;
3147 crr_cluster
->fields_in_cluster
= fields
;
3150 /* This function peels a field with the index I from the structure DS. */
3153 peel_field (int i
, d_str ds
)
3155 struct field_cluster
*crr_cluster
= NULL
;
3158 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3159 crr_cluster
->sibling
= ds
->struct_clustering
;
3160 ds
->struct_clustering
= crr_cluster
;
3161 crr_cluster
->fields_in_cluster
=
3162 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3163 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3164 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3167 /* This function calculates maximum field count in
3168 the structure STR. */
3171 get_max_field_count (d_str str
)
3176 for (i
= 0; i
< str
->num_fields
; i
++)
3177 if (str
->fields
[i
].count
> max
)
3178 max
= str
->fields
[i
].count
;
3183 /* Do struct-reorg transformation for individual function
3184 represented by NODE. All structure types relevant
3185 for this function are transformed. */
3188 do_reorg_for_func (struct cgraph_node
*node
)
3190 create_new_local_vars ();
3191 create_new_alloc_sites_for_func (node
);
3192 create_new_accesses_for_func ();
3193 update_ssa (TODO_update_ssa
);
3194 cleanup_tree_cfg ();
3196 /* Free auxiliary data representing local variables. */
3197 free_new_vars_htab (new_local_vars
);
3200 /* Print structure TYPE, its name, if it exists, and body.
3201 INDENT defines the level of indentation (similar
3202 to the option -i of indent command). SHIFT parameter
3203 defines a number of spaces by which a structure will
3204 be shifted right. */
3207 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3208 unsigned HOST_WIDE_INT shift
)
3210 const char *struct_name
;
3213 if (!type
|| !dump_file
)
3216 if (TREE_CODE (type
) != RECORD_TYPE
)
3218 print_generic_expr (dump_file
, type
, 0);
3222 print_shift (shift
);
3223 struct_name
= get_type_name (type
);
3224 fprintf (dump_file
, "struct ");
3226 fprintf (dump_file
, "%s\n",struct_name
);
3227 print_shift (shift
);
3228 fprintf (dump_file
, "{\n");
3230 for (field
= TYPE_FIELDS (type
); field
;
3231 field
= TREE_CHAIN (field
))
3233 unsigned HOST_WIDE_INT s
= indent
;
3234 tree f_type
= TREE_TYPE (field
);
3236 print_shift (shift
);
3238 fprintf (dump_file
, " ");
3239 dump_struct_type (f_type
, indent
, shift
+ indent
);
3240 fprintf(dump_file
, " ");
3241 print_generic_expr (dump_file
, field
, 0);
3242 fprintf(dump_file
, ";\n");
3244 print_shift (shift
);
3245 fprintf (dump_file
, "}\n");
3248 /* This function creates new structure types to replace original type,
3249 indicated by STR->decl. The names of the new structure types are
3250 derived from the original structure type. If the original structure
3251 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3254 create_new_type (d_str str
, int *str_num
)
3256 int cluster_num
= 0;
3258 struct field_cluster
*cluster
= str
->struct_clustering
;
3261 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3267 fields
= create_fields (cluster
, str
->fields
,
3269 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3271 update_fields_mapping (cluster
, new_type
,
3272 str
->fields
, str
->num_fields
);
3274 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3275 cluster
= cluster
->sibling
;
3280 /* This function is a callback for alloc_sites hashtable
3281 traversal. SLOT is a pointer to fallocs_t.
3282 This function frees memory pointed by *SLOT. */
3285 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3287 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3289 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3294 /* Remove structures collected in UNSUITABLE_TYPES
3295 from structures vector. */
3298 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3304 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3305 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3306 if (is_equal_types (str
->decl
, type
))
3308 remove_structure (i
);
3313 /* Exclude structure types with bitfields.
3314 We would not want to interfere with other optimizations
3315 that can be done in this case. The structure types with
3316 bitfields are added to UNSUITABLE_TYPES vector. */
3319 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3324 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3325 check_bitfields (str
, unsuitable_types
);
3328 /* This function checks three types of escape. A structure type escapes:
3330 1. if it's a type of parameter of a local function.
3331 2. if it's a type of function return value.
3332 3. if it escapes as a result of ipa-type-escape analysis.
3334 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3337 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3339 exclude_types_passed_to_local_func (unsuitable_types
);
3340 exclude_returned_types (unsuitable_types
);
3341 exclude_escaping_types_1 (unsuitable_types
);
3344 /* This function analyzes whether the form of
3345 structure is such that we are capable to transform it.
3346 Nested structures are checked here. Unsuitable structure
3347 types are added to UNSUITABLE_TYPE vector. */
3350 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3355 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3356 check_struct_form (str
, unsuitable_types
);
3359 /* This function looks for structure types instantiated in the program.
3360 The candidate types are added to the structures vector.
3361 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3364 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3368 struct varpool_node
*current_varpool
;
3369 struct cgraph_node
*c_node
;
3371 /* Check global variables. */
3372 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3374 var
= current_varpool
->decl
;
3375 if (is_candidate (var
, &type
, unsuitable_types
))
3376 add_structure (type
);
3379 /* Now add structures that are types of function parameters and
3381 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3383 enum availability avail
=
3384 cgraph_function_body_availability (c_node
);
3386 /* We need AVAIL_AVAILABLE for main function. */
3387 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3389 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3391 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3392 var
= TREE_CHAIN (var
))
3393 if (is_candidate (var
, &type
, unsuitable_types
))
3394 add_structure (type
);
3396 /* Check function local variables. */
3397 for (var_list
= fn
->unexpanded_var_list
; var_list
;
3398 var_list
= TREE_CHAIN (var_list
))
3400 var
= TREE_VALUE (var_list
);
3402 if (is_candidate (var
, &type
, unsuitable_types
))
3403 add_structure (type
);
3409 /* This function returns true if the program contains
3410 a call to user defined allocation function, or other
3411 functions that can interfere with struct-reorg optimizations. */
3414 program_redefines_malloc_p (void)
3416 struct cgraph_node
*c_node
;
3417 struct cgraph_node
*c_node2
;
3418 struct cgraph_edge
*c_edge
;
3423 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3425 fndecl
= c_node
->decl
;
3427 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3429 call_expr
= get_call_expr_in (c_edge
->call_stmt
);
3430 c_node2
= c_edge
->callee
;
3431 fndecl2
= c_node2
->decl
;
3434 const char * fname
= get_name (fndecl2
);
3436 if ((call_expr_flags (call_expr
) & ECF_MALLOC
) &&
3437 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
) &&
3438 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
) &&
3439 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3442 /* Check that there is no __builtin_object_size,
3443 __builtin_offsetof, or realloc's in the program. */
3444 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3445 || !strcmp (fname
, "__builtin_offsetof")
3446 || !strcmp (fname
, "realloc"))
3455 /* In this function we assume that an allocation statement
3457 var = (type_cast) malloc (size);
3459 is converted into the following set of statements:
3463 T.3 = (type_cast) T.2;
3466 In this function we collect into alloc_sites the allocation
3467 sites of variables of structure types that are present
3468 in structures vector. */
3471 collect_alloc_sites (void)
3473 struct cgraph_node
*node
;
3474 struct cgraph_edge
*cs
;
3476 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3477 if (node
->analyzed
&& node
->decl
)
3479 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3481 tree stmt
= cs
->call_stmt
;
3485 tree call
= get_call_expr_in (stmt
);
3488 if (call
&& (decl
= get_callee_fndecl (call
))
3489 && TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3493 if (is_alloc_of_struct (stmt
, &i
))
3495 /* We support only malloc now. */
3496 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3500 str
= VEC_index (structure
, structures
, i
);
3501 add_alloc_site (node
->decl
, stmt
, str
);
3508 "\nUnsupported allocation function ");
3509 print_generic_stmt (dump_file
, stmt
, 0);
3511 remove_structure (i
);
3520 /* Print collected accesses. */
3523 dump_accesses (void)
3531 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3535 /* This function checks whether the accesses of structures in condition
3536 expressions are of the kind we are capable to transform.
3537 If not, such structures are removed from the vector of structures. */
3540 check_cond_exprs (void)
3545 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3547 htab_traverse (str
->accs
, safe_cond_expr_check
, &i
);
3550 /* We exclude from non-field accesses of the structure
3551 all statements that will be treated as part of the structure
3552 allocation sites or field accesses. */
3555 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3560 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3561 exclude_alloc_and_field_accs_1 (str
, node
);
3564 /* This function collects accesses of the fields of the structures
3565 that appear at function FN. */
3568 collect_accesses_in_func (struct function
*fn
)
3575 /* Collect accesses for each basic blocks separately. */
3576 FOR_EACH_BB_FN (bb
, fn
)
3577 collect_accesses_in_bb (bb
);
3580 /* This function summarizes counts of the fields into the structure count. */
3583 sum_counts (d_str str
, gcov_type
*hotest
)
3588 for (i
= 0; i
< str
->num_fields
; i
++)
3592 fprintf (dump_file
, "\nCounter of field \"");
3593 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3594 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3595 str
->fields
[i
].count
);
3597 str
->count
+= str
->fields
[i
].count
;
3602 fprintf (dump_file
, "\nCounter of struct \"");
3603 print_generic_expr (dump_file
, str
->decl
, 0);
3604 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3607 if (str
->count
> *hotest
)
3608 *hotest
= str
->count
;
3611 /* This function peels the field into separate structure if it's
3612 sufficiently hot, i.e. if its count provides at least 90% of
3613 the maximum field count in the structure. */
3616 peel_hot_fields (d_str str
)
3618 gcov_type max_field_count
;
3619 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3622 sbitmap_ones (fields_left
);
3624 (gcov_type
) (get_max_field_count (str
)/100)*90;
3626 str
->struct_clustering
= NULL
;
3628 for (i
= 0; i
< str
->num_fields
; i
++)
3630 if (str
->count
>= max_field_count
)
3632 RESET_BIT (fields_left
, i
);
3633 peel_field (i
, str
);
3637 i
= sbitmap_first_set_bit (fields_left
);
3639 gen_cluster (fields_left
, str
);
3641 sbitmap_free (fields_left
);
3644 /* This function is a helper for do_reorg. It goes over
3645 functions in call graph and performs actual transformation
3651 struct cgraph_node
*node
;
3653 /* Initialize the default bitmap obstack. */
3654 bitmap_obstack_initialize (NULL
);
3656 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3657 if (node
->analyzed
&& node
->decl
&& !node
->next_clone
)
3659 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3660 current_function_decl
= node
->decl
;
3662 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3663 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3664 do_reorg_for_func (node
);
3665 free_dominance_info (CDI_DOMINATORS
);
3666 free_dominance_info (CDI_POST_DOMINATORS
);
3667 current_function_decl
= NULL
;
3674 /* This function creates new global struct variables.
3675 For each original variable, the set of new variables
3676 is created with the new structure types corresponding
3677 to the structure type of original variable.
3678 Only VAR_DECL variables are treated by this function. */
3681 create_new_global_vars (void)
3683 struct varpool_node
*current_varpool
;
3684 unsigned HOST_WIDE_INT i
;
3685 unsigned HOST_WIDE_INT varpool_size
= 0;
3687 for (i
= 0; i
< 2; i
++)
3690 new_global_vars
= htab_create (varpool_size
,
3691 new_var_hash
, new_var_eq
, NULL
);
3692 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3694 tree var_decl
= current_varpool
->decl
;
3696 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3701 create_new_var (var_decl
, new_global_vars
);
3705 if (new_global_vars
)
3706 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3709 /* Dump all new types generated by this optimization. */
3712 dump_new_types (void)
3721 fprintf (dump_file
, "\nThe following are the new types generated by"
3722 " this optimization:\n");
3724 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3728 fprintf (dump_file
, "\nFor type ");
3729 dump_struct_type (str
->decl
, 2, 0);
3730 fprintf (dump_file
, "\nthe number of new types is %d\n",
3731 VEC_length (tree
, str
->new_types
));
3733 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3734 dump_struct_type (type
, 2, 0);
3738 /* This function creates new types to replace old structure types. */
3741 create_new_types (void)
3747 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3748 create_new_type (str
, &str_num
);
3751 /* Free allocation sites hashtable. */
3754 free_alloc_sites (void)
3757 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3758 htab_delete (alloc_sites
);
3762 /* This function collects structures potential
3763 for peeling transformation, and inserts
3764 them into structures hashtable. */
3767 collect_structures (void)
3769 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3771 structures
= VEC_alloc (structure
, heap
, 32);
3773 /* If program contains user defined mallocs, we give up. */
3774 if (program_redefines_malloc_p ())
3777 /* Build data structures hashtable of all data structures
3779 build_data_structure (&unsuitable_types
);
3781 /* This function analyzes whether the form of
3782 structure is such that we are capable to transform it.
3783 Nested structures are checked here. */
3784 analyze_struct_form (&unsuitable_types
);
3786 /* This function excludes those structure types
3787 that escape compilation unit. */
3788 exclude_escaping_types (&unsuitable_types
);
3790 /* We do not want to change data layout of the structures with bitfields. */
3791 exclude_types_with_bit_fields (&unsuitable_types
);
3793 remove_unsuitable_types (unsuitable_types
);
3794 VEC_free (tree
, heap
, unsuitable_types
);
3797 /* Collect structure allocation sites. In case of arrays
3798 we have nothing to do. */
3801 collect_allocation_sites (void)
3803 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3804 collect_alloc_sites ();
3807 /* This function collects data accesses for the
3808 structures to be transformed. For each structure
3809 field it updates the count field in field_entry. */
3812 collect_data_accesses (void)
3814 struct cgraph_node
*c_node
;
3816 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3818 enum availability avail
= cgraph_function_body_availability (c_node
);
3820 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3822 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3824 if (!c_node
->next_clone
)
3825 collect_accesses_in_func (func
);
3826 exclude_alloc_and_field_accs (c_node
);
3830 check_cond_exprs ();
3831 /* Print collected accesses. */
3835 /* We do not bother to transform cold structures.
3836 Coldness of the structure is defined relatively
3837 to the highest structure count among the structures
3838 to be transformed. It's triggered by the compiler parameter
3840 --param struct-reorg-cold-struct-ratio=<value>
3842 where <value> ranges from 0 to 100. Structures with count ratios
3843 that are less than this parameter are considered to be cold. */
3846 exclude_cold_structs (void)
3848 gcov_type hotest
= 0;
3852 /* We summarize counts of fields of a structure into the structure count. */
3853 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3854 sum_counts (str
, &hotest
);
3856 /* Remove cold structures from structures vector. */
3857 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3858 if (str
->count
* 100 < (hotest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3862 fprintf (dump_file
, "\nThe structure ");
3863 print_generic_expr (dump_file
, str
->decl
, 0);
3864 fprintf (dump_file
, " is cold.");
3866 remove_structure (i
);
3870 /* This function decomposes original structure into substructures,
3879 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3880 peel_hot_fields (str
);
3884 /* Do the actual transformation for each structure
3885 from the structures hashtable. */
3890 /* Check that there is a work to do. */
3891 if (!VEC_length (structure
, structures
))
3894 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3901 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3902 VEC_length (structure
, structures
));
3906 /* Generate new types. */
3907 create_new_types ();
3910 /* Create new global variables. */
3911 create_new_global_vars ();
3912 dump_new_vars (new_global_vars
);
3914 /* Decompose structures for each function separately. */
3917 /* Free auxiliary data collected for global variables. */
3918 free_new_vars_htab (new_global_vars
);
3921 /* Free all auxiliary data used by this optimization. */
3924 free_data_structs (void)
3927 free_alloc_sites ();
3930 /* Perform structure decomposition (peeling). */
3933 reorg_structs (void)
3937 /* Collect structure types. */
3938 collect_structures ();
3940 /* Collect structure allocation sites. */
3941 collect_allocation_sites ();
3943 /* Collect structure accesses. */
3944 collect_data_accesses ();
3946 /* We transform only hot structures. */
3947 exclude_cold_structs ();
3950 /* Decompose structures into substructures, i.e. clusters. */
3954 /* Do the actual transformation for each structure
3955 from the structures hashtable. */
3958 /* Free all auxiliary data used by this optimization. */
3959 free_data_structs ();
3962 /* Struct-reorg optimization entry point function. */
3965 reorg_structs_drive (void)
3971 /* Struct-reorg optimization gate function. */
3974 struct_reorg_gate (void)
3976 return flag_ipa_struct_reorg
&& flag_whole_program
3980 struct tree_opt_pass pass_ipa_struct_reorg
=
3982 "ipa_struct_reorg", /* name */
3983 struct_reorg_gate
, /* gate */
3984 reorg_structs_drive
, /* execute */
3987 0, /* static_pass_number */
3988 TV_INTEGRATION
, /* tv_id */
3989 0, /* properties_required */
3990 0, /* properties_provided */
3991 0, /* properties_destroyed */
3992 TODO_verify_ssa
, /* todo_flags_start */
3993 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */