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);
961 type_wrapper_t
*wr_p
= NULL
;
963 while (TREE_CODE (ref_var
) == INDIRECT_REF
964 || TREE_CODE (ref_var
) == ARRAY_REF
)
966 if ( TREE_CODE (ref_var
) == INDIRECT_REF
)
971 else if (TREE_CODE (ref_var
) == ARRAY_REF
)
974 wr
.domain
= TREE_OPERAND (ref_var
, 1);
977 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
978 ref_var
= TREE_OPERAND (ref_var
, 0);
981 new_ref
= find_new_var_of_type (ref_var
, new_type
);
982 finalize_global_creation (new_ref
);
984 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
986 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
988 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
989 if (wr_p
->wrap
) /* Array. */
990 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
991 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
993 new_ref
= build1 (INDIRECT_REF
, type
, new_ref
);
994 VEC_pop (type_wrapper_t
, wrapper
);
997 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
998 VEC_free (type_wrapper_t
, heap
, wrapper
);
1000 if (TREE_CODE (acc
->stmt
) == GIMPLE_MODIFY_STMT
)
1002 lhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 0);
1003 rhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 1);
1006 if (lhs
== acc
->comp_ref
)
1007 GIMPLE_STMT_OPERAND (acc
->stmt
, 0) = new_acc
;
1008 else if (rhs
== acc
->comp_ref
)
1009 GIMPLE_STMT_OPERAND (acc
->stmt
, 1) = new_acc
;
1012 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1019 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1024 finalize_stmt (acc
->stmt
);
1027 /* This function replace field access ACC by a new field access
1028 of structure type NEW_TYPE. */
1031 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1034 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
1035 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1036 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1037 replace_field_acc (acc
, new_type
);
1042 /* This function looks for d_str, represented by TYPE, in the structures
1043 vector. If found, it returns an index of found structure. Otherwise
1044 it returns a length of the structures vector. */
1047 find_structure (tree type
)
1052 type
= TYPE_MAIN_VARIANT (type
);
1054 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
1055 if (is_equal_types (str
->decl
, type
))
1058 return VEC_length (structure
, structures
);
1061 /* In this function we create new statements that have the same
1062 form as ORIG_STMT, but of type NEW_TYPE. The statements
1063 treated by this function are simple assignments,
1064 like assignments: p.8_7 = p; or statements with rhs of
1065 tree codes PLUS_EXPR and MINUS_EXPR. */
1068 create_base_plus_offset (tree orig_stmt
, tree new_type
,
1072 tree new_lhs
, new_rhs
;
1075 gcc_assert (TREE_CODE (orig_stmt
) == GIMPLE_MODIFY_STMT
);
1077 lhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 0);
1078 rhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 1);
1080 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1081 || TREE_CODE (lhs
) == SSA_NAME
);
1083 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1084 gcc_assert (new_lhs
);
1085 finalize_var_creation (new_lhs
);
1087 switch (TREE_CODE (rhs
))
1091 case POINTER_PLUS_EXPR
:
1093 tree op0
= TREE_OPERAND (rhs
, 0);
1094 tree op1
= TREE_OPERAND (rhs
, 1);
1095 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1096 unsigned str0
, str1
;
1097 unsigned length
= VEC_length (structure
, structures
);
1100 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1101 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1102 gcc_assert ((str0
!= length
) || (str1
!= length
));
1105 new_op0
= find_new_var_of_type (op0
, new_type
);
1107 new_op1
= find_new_var_of_type (op1
, new_type
);
1114 new_rhs
= build2 (TREE_CODE (rhs
), TREE_TYPE (new_op0
),
1123 new_stmt
= build_gimple_modify_stmt (new_lhs
, new_rhs
);
1124 finalize_stmt (new_stmt
);
1129 /* Given a field access F_ACC of the FIELD, this function
1130 replaces it by the new field access. */
1133 create_new_field_access (struct field_access_site
*f_acc
,
1134 struct field_entry field
)
1136 tree new_type
= field
.field_mapping
;
1139 tree mult_stmt
, cast_stmt
;
1140 tree cast_res
= NULL
;
1144 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1145 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1148 if (f_acc
->cast_stmt
)
1150 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1151 f_acc
->cast_stmt
, &cast_res
);
1152 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1155 if (f_acc
->ref_def_stmt
)
1163 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1165 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1168 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1169 D.2162_18 by an appropriate variable of new_type type. */
1170 replace_field_access_stmt (f_acc
, new_type
);
1173 /* This function creates a new condition statement
1174 corresponding to the original COND_STMT, adds new basic block
1175 and redirects condition edges. NEW_VAR is a new condition
1176 variable located in the condition statement at the position POS. */
1179 create_new_stmts_for_cond_expr_1 (tree new_var
, tree cond_stmt
, bool pos
)
1183 edge true_e
= NULL
, false_e
= NULL
;
1187 extract_true_false_edges_from_block (bb_for_stmt (cond_stmt
),
1190 new_cond
= unshare_expr (COND_EXPR_COND (cond_stmt
));
1192 TREE_OPERAND (new_cond
, pos
) = new_var
;
1194 new_stmt
= build3 (COND_EXPR
, TREE_TYPE (cond_stmt
),
1195 new_cond
, NULL_TREE
, NULL_TREE
);
1197 finalize_stmt (new_stmt
);
1199 /* Create new basic block after bb. */
1200 new_bb
= create_empty_bb (bb_for_stmt (cond_stmt
));
1202 /* Add new condition stmt to the new_bb. */
1203 stmt_list
= bb_stmt_list (new_bb
);
1204 append_to_statement_list (new_stmt
, &stmt_list
);
1205 add_bb_info (new_bb
, stmt_list
);
1208 /* Create false and true edges from new_bb. */
1209 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1210 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1212 /* Redirect one of original edges to point to new_bb. */
1213 if (TREE_CODE (cond_stmt
) == NE_EXPR
)
1214 redirect_edge_succ (true_e
, new_bb
);
1216 redirect_edge_succ (false_e
, new_bb
);
1219 /* This function creates new condition statements corresponding
1220 to original condition STMT, one for each new type, and
1221 recursively redirect edges to newly generated basic blocks. */
1224 create_new_stmts_for_cond_expr (tree stmt
)
1226 tree cond
= COND_EXPR_COND (stmt
);
1227 tree arg0
, arg1
, arg
;
1228 unsigned str0
, str1
;
1234 unsigned length
= VEC_length (structure
, structures
);
1236 gcc_assert (TREE_CODE (cond
) == EQ_EXPR
1237 || TREE_CODE (cond
) == NE_EXPR
);
1239 arg0
= TREE_OPERAND (cond
, 0);
1240 arg1
= TREE_OPERAND (cond
, 1);
1242 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1243 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1245 s0
= (str0
!= length
) ? true : false;
1246 s1
= (str1
!= length
) ? true : false;
1248 gcc_assert ((!s0
&& s1
) || (!s1
&& s0
));
1250 str
= s0
? VEC_index (structure
, structures
, str0
):
1251 VEC_index (structure
, structures
, str1
);
1252 arg
= s0
? arg0
: arg1
;
1255 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1259 new_arg
= find_new_var_of_type (arg
, type
);
1260 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1264 /* Create a new general access to replace original access ACC
1265 for structure type NEW_TYPE. */
1268 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1270 tree old_stmt
= acc
->stmt
;
1272 tree new_stmt
= unshare_expr (old_stmt
);
1276 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1279 tree new_var
= find_new_var_of_type (var
, new_type
);
1282 gcc_assert (new_var
);
1283 finalize_var_creation (new_var
);
1285 if (TREE_CODE (new_stmt
) == GIMPLE_MODIFY_STMT
)
1288 lhs
= GIMPLE_STMT_OPERAND (new_stmt
, 0);
1289 rhs
= GIMPLE_STMT_OPERAND (new_stmt
, 1);
1291 if (TREE_CODE (lhs
) == SSA_NAME
)
1292 lhs
= SSA_NAME_VAR (lhs
);
1293 if (TREE_CODE (rhs
) == SSA_NAME
)
1294 rhs
= SSA_NAME_VAR (rhs
);
1296 /* It can happen that rhs is a constructor.
1297 Then we have to replace it to be of new_type. */
1298 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
1300 /* Dealing only with empty constructors right now. */
1301 gcc_assert (VEC_empty (constructor_elt
,
1302 CONSTRUCTOR_ELTS (rhs
)));
1303 rhs
= build_constructor (new_type
, 0);
1304 GIMPLE_STMT_OPERAND (new_stmt
, 1) = rhs
;
1308 GIMPLE_STMT_OPERAND (new_stmt
, 0) = new_var
;
1309 else if (rhs
== var
)
1310 GIMPLE_STMT_OPERAND (new_stmt
, 1) = new_var
;
1313 pos
= find_pos_in_stmt (new_stmt
, var
);
1320 pos
= find_pos_in_stmt (new_stmt
, var
);
1326 finalize_stmt (new_stmt
);
1330 /* For each new type in STR this function creates new general accesses
1331 corresponding to the original access ACC. */
1334 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1337 tree stmt
= acc
->stmt
;
1340 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1344 new_stmt
= create_general_new_stmt (acc
, type
);
1345 insert_after_stmt (stmt
, new_stmt
);
1349 /* This function creates a new general access of structure STR
1350 to replace the access ACC. */
1353 create_new_general_access (struct access_site
*acc
, d_str str
)
1355 tree stmt
= acc
->stmt
;
1356 switch (TREE_CODE (stmt
))
1359 create_new_stmts_for_cond_expr (stmt
);
1363 create_new_stmts_for_general_acc (acc
, str
);
1367 /* Auxiliary data for creation of accesses. */
1368 struct create_acc_data
1375 /* This function creates a new general access, defined by SLOT.
1376 DATA is a pointer to create_acc_data structure. */
1379 create_new_acc (void **slot
, void *data
)
1381 struct access_site
*acc
= *(struct access_site
**) slot
;
1382 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1383 d_str str
= ((struct create_acc_data
*)data
)->str
;
1385 if (bb_for_stmt (acc
->stmt
) == bb
)
1386 create_new_general_access (acc
, str
);
1390 /* This function creates a new field access, defined by SLOT.
1391 DATA is a pointer to create_acc_data structure. */
1394 create_new_field_acc (void **slot
, void *data
)
1396 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1397 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1398 d_str str
= ((struct create_acc_data
*)data
)->str
;
1399 int i
= ((struct create_acc_data
*)data
)->field_index
;
1401 if (bb_for_stmt (f_acc
->stmt
) == bb
)
1402 create_new_field_access (f_acc
, str
->fields
[i
]);
1406 /* This function creates new accesses for the structure
1407 type STR in basic block BB. */
1410 create_new_accs_for_struct (d_str str
, basic_block bb
)
1413 struct create_acc_data dt
;
1417 dt
.field_index
= -1;
1419 for (i
= 0; i
< str
->num_fields
; i
++)
1423 if (str
->fields
[i
].acc_sites
)
1424 htab_traverse (str
->fields
[i
].acc_sites
,
1425 create_new_field_acc
, &dt
);
1428 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1431 /* This function inserts new variables from new_var,
1432 defined by SLOT, into varpool. */
1435 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1437 new_var n_var
= *(new_var
*) slot
;
1441 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1442 insert_global_to_varpool (var
);
1446 /* This function prints a field access site, defined by SLOT. */
1449 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1451 struct field_access_site
*f_acc
=
1452 *(struct field_access_site
**) slot
;
1454 fprintf(dump_file
, "\n");
1456 print_generic_stmt (dump_file
, f_acc
->stmt
, 0);
1457 if (f_acc
->ref_def_stmt
)
1458 print_generic_stmt (dump_file
, f_acc
->ref_def_stmt
, 0);
1459 if (f_acc
->cast_stmt
)
1460 print_generic_stmt (dump_file
, f_acc
->cast_stmt
, 0);
1464 /* Print field accesses from hashtable F_ACCS. */
1467 dump_field_acc_sites (htab_t f_accs
)
1473 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1476 /* Hash value for fallocs_t. */
1479 malloc_hash (const void *x
)
1481 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1484 /* This function returns nonzero if function of func_alloc_sites' X
1488 malloc_eq (const void *x
, const void *y
)
1490 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1493 /* This function is a callback for traversal over a structure accesses.
1494 It frees an access represented by SLOT. */
1497 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1499 struct access_site
* acc
= *(struct access_site
**) slot
;
1501 VEC_free (tree
, heap
, acc
->vars
);
1506 /* This is a callback function for traversal over field accesses.
1507 It frees a field access represented by SLOT. */
1510 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1512 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1518 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1519 if it is not there yet. */
1522 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1530 type
= TYPE_MAIN_VARIANT (type
);
1532 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1533 if (is_equal_types (t
, type
))
1536 if (i
== VEC_length (tree
, *unsuitable_types
))
1537 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1540 /* Given a type TYPE, this function returns the name of the type. */
1543 get_type_name (tree type
)
1545 if (! TYPE_NAME (type
))
1548 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1549 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1550 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1551 && DECL_NAME (TYPE_NAME (type
)))
1552 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1557 /* This function is a temporary hack to overcome the types problem.
1558 When several compilation units are compiled together
1559 with -combine, the TYPE_MAIN_VARIANT of the same type
1560 can appear differently in different compilation units.
1561 Therefore this function first compares type names.
1562 If there are no names, structure bodies are recursively
1566 is_equal_types (tree type1
, tree type2
)
1568 const char * name1
,* name2
;
1570 if ((!type1
&& type2
)
1571 ||(!type2
&& type1
))
1574 if (!type1
&& !type2
)
1577 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1583 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1586 name1
= get_type_name (type1
);
1587 name2
= get_type_name (type2
);
1589 if (name1
&& name2
&& !strcmp (name1
, name2
))
1592 if (name1
&& name2
&& strcmp (name1
, name2
))
1595 switch (TREE_CODE (type1
))
1598 case REFERENCE_TYPE
:
1600 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1606 case QUAL_UNION_TYPE
:
1610 /* Compare fields of struture. */
1611 for (field1
= TYPE_FIELDS (type1
); field1
;
1612 field1
= TREE_CHAIN (field1
))
1614 tree field2
= find_field_in_struct_1 (type2
, field1
);
1624 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1625 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1633 tree max1
, min1
, max2
, min2
;
1635 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1638 d1
= TYPE_DOMAIN (type1
);
1639 d2
= TYPE_DOMAIN (type2
);
1644 max1
= TYPE_MAX_VALUE (d1
);
1645 max2
= TYPE_MAX_VALUE (d2
);
1646 min1
= TYPE_MIN_VALUE (d1
);
1647 min2
= TYPE_MIN_VALUE (d2
);
1649 if (max1
&& max2
&& min1
&& min2
1650 && TREE_CODE (max1
) == TREE_CODE (max2
)
1651 && TREE_CODE (max1
) == INTEGER_CST
1652 && TREE_CODE (min1
) == TREE_CODE (min2
)
1653 && TREE_CODE (min1
) == INTEGER_CST
1654 && tree_int_cst_equal (max1
, max2
)
1655 && tree_int_cst_equal (min1
, min2
))
1667 /* This function free non-field accesses from hashtable ACCS. */
1670 free_accesses (htab_t accs
)
1673 htab_traverse (accs
, free_accs
, NULL
);
1677 /* This function free field accesses hashtable F_ACCS. */
1680 free_field_accesses (htab_t f_accs
)
1683 htab_traverse (f_accs
, free_field_accs
, NULL
);
1684 htab_delete (f_accs
);
1687 /* Update call graph with new edge generated by new MALLOC_STMT.
1688 The edge origin is CONTEXT function. */
1691 update_cgraph_with_malloc_call (tree malloc_stmt
, tree context
)
1694 struct cgraph_node
*src
, *dest
;
1695 tree malloc_fn_decl
;
1700 call_expr
= get_call_expr_in (malloc_stmt
);
1701 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1703 src
= cgraph_node (context
);
1704 dest
= cgraph_node (malloc_fn_decl
);
1705 cgraph_create_edge (src
, dest
, malloc_stmt
,
1706 0, 0, bb_for_stmt (malloc_stmt
)->loop_depth
);
1709 /* This function generates set of statements required
1710 to allocate number NUM of structures of type NEW_TYPE.
1711 The statements are stored in NEW_STMTS. The statement that contain
1712 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1715 create_new_malloc (tree malloc_stmt
, tree new_type
, tree
*new_stmts
, tree num
)
1717 tree new_malloc_size
;
1718 tree call_expr
, malloc_fn_decl
;
1719 tree new_stmt
, malloc_res
;
1720 tree call_stmt
, final_stmt
;
1723 gcc_assert (num
&& malloc_stmt
&& new_type
);
1724 *new_stmts
= alloc_stmt_list ();
1726 /* Generate argument to malloc as multiplication of num
1727 and size of new_type. */
1728 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1729 append_to_statement_list (new_stmt
, new_stmts
);
1731 /* Generate new call for malloc. */
1732 malloc_res
= create_tmp_var (integer_type_node
, NULL
);
1735 add_referenced_var (malloc_res
);
1737 call_expr
= get_call_expr_in (malloc_stmt
);
1738 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1739 call_expr
= build_call_expr (malloc_fn_decl
, 1, new_malloc_size
);
1740 call_stmt
= build_gimple_modify_stmt (malloc_res
, call_expr
);
1741 finalize_stmt_and_append (new_stmts
, call_stmt
);
1743 /* Create new cast statement. */
1744 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1745 gcc_assert (final_stmt
);
1746 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1747 append_to_statement_list (new_stmt
, new_stmts
);
1752 /* This function returns a tree representing
1753 the number of instances of structure STR_DECL allocated
1754 by allocation STMT. If new statments are generated,
1755 they are filled into NEW_STMTS_P. */
1758 gen_num_of_structs_in_malloc (tree stmt
, tree str_decl
, tree
*new_stmts_p
)
1760 call_expr_arg_iterator iter
;
1764 HOST_WIDE_INT struct_size_int
;
1769 /* Get malloc argument. */
1770 call_expr
= get_call_expr_in (stmt
);
1774 arg
= first_call_expr_arg (call_expr
, &iter
);
1776 if (TREE_CODE (arg
) != SSA_NAME
1777 && !TREE_CONSTANT (arg
))
1780 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1781 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1783 gcc_assert (struct_size
);
1785 if (TREE_CODE (arg
) == SSA_NAME
)
1789 if (is_result_of_mult (arg
, &num
, struct_size
))
1792 num
= create_tmp_var (integer_type_node
, NULL
);
1795 add_referenced_var (num
);
1797 if (exact_log2 (struct_size_int
) == -1)
1798 div_stmt
= build_gimple_modify_stmt (num
,
1799 build2 (TRUNC_DIV_EXPR
,
1804 tree C
= build_int_cst (integer_type_node
,
1805 exact_log2 (struct_size_int
));
1808 build_gimple_modify_stmt (num
, build2 (RSHIFT_EXPR
,
1812 *new_stmts_p
= alloc_stmt_list ();
1813 append_to_statement_list (div_stmt
,
1815 finalize_stmt (div_stmt
);
1819 if (CONSTANT_CLASS_P (arg
)
1820 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1821 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1826 /* This function is a callback for traversal on new_var's hashtable.
1827 SLOT is a pointer to new_var. This function prints to dump_file
1828 an original variable and all new variables from the new_var
1829 pointed by *SLOT. */
1832 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1834 new_var n_var
= *(new_var
*) slot
;
1839 var_type
= get_type_of_var (n_var
->orig_var
);
1841 fprintf (dump_file
, "\nOrig var: ");
1842 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1843 fprintf (dump_file
, " of type ");
1844 print_generic_expr (dump_file
, var_type
, 0);
1845 fprintf (dump_file
, "\n");
1848 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1850 var_type
= get_type_of_var (var
);
1852 fprintf (dump_file
, " ");
1853 print_generic_expr (dump_file
, var
, 0);
1854 fprintf (dump_file
, " of type ");
1855 print_generic_expr (dump_file
, var_type
, 0);
1856 fprintf (dump_file
, "\n");
1861 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1864 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1867 DECL_ARTIFICIAL (new_decl
) = 1;
1868 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1869 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1870 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1871 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1872 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1873 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1874 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1876 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1878 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1879 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1883 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1884 the same way as a structure type is wrapped in DECL.
1885 It returns the generated type. */
1888 gen_struct_type (tree decl
, tree new_str_type
)
1890 tree type_orig
= get_type_of_var (decl
);
1891 tree new_type
= new_str_type
;
1892 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1894 type_wrapper_t
*wr_p
;
1896 while (POINTER_TYPE_P (type_orig
)
1897 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1899 if (POINTER_TYPE_P (type_orig
))
1902 wr
.domain
= NULL_TREE
;
1904 else if (TREE_CODE (type_orig
) == ARRAY_TYPE
)
1907 wr
.domain
= TYPE_DOMAIN (type_orig
);
1909 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1910 type_orig
= TREE_TYPE (type_orig
);
1913 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1915 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1917 if (wr_p
->wrap
) /* Array. */
1918 new_type
= build_array_type (new_type
, wr_p
->domain
);
1920 new_type
= build_pointer_type (new_type
);
1922 VEC_pop (type_wrapper_t
, wrapper
);
1925 VEC_free (type_wrapper_t
, heap
, wrapper
);
1929 /* This function generates and returns new variable name based on
1930 ORIG_DECL name, combined with index I.
1931 The form of the new name is <orig_name>.<I> . */
1934 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1936 const char *old_name
;
1940 if (!DECL_NAME (orig_decl
)
1941 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1944 /* If the original variable has a name, create an
1945 appropriate new name for the new variable. */
1947 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1948 prefix
= alloca (strlen (old_name
) + 1);
1949 strcpy (prefix
, old_name
);
1950 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1951 return get_identifier (new_name
);
1954 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1957 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1961 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1962 htab_hash_pointer (new_node
->orig_var
),
1967 /* This function creates and returns new_var_data node
1968 with empty new_vars and orig_var equal to VAR. */
1971 create_new_var_node (tree var
, d_str str
)
1975 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1976 node
->orig_var
= var
;
1977 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1981 /* Check whether the type of VAR is potential candidate for peeling.
1982 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1983 candidate type. If VAR is initialized, the type of VAR will be added
1984 to UNSUITABLE_TYPES. */
1987 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
1990 bool initialized
= false;
1997 /* There is no support of initialized vars. */
1998 if (TREE_CODE (var
) == VAR_DECL
1999 && DECL_INITIAL (var
) != NULL_TREE
)
2002 type
= get_type_of_var (var
);
2006 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2007 if (TREE_CODE (type
) != RECORD_TYPE
)
2011 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2012 add_unsuitable_type (unsuitable_types
, type
);
2021 /* Hash value for field_access_site. */
2024 field_acc_hash (const void *x
)
2026 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2029 /* This function returns nonzero if stmt of field_access_site X
2033 field_acc_eq (const void *x
, const void *y
)
2035 return ((const struct field_access_site
*)x
)->stmt
== (const_tree
)y
;
2038 /* This function prints an access site, defined by SLOT. */
2041 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2043 struct access_site
*acc
= *(struct access_site
**) slot
;
2047 fprintf(dump_file
, "\n");
2049 print_generic_stmt (dump_file
, acc
->stmt
, 0);
2050 fprintf(dump_file
, " : ");
2052 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2054 print_generic_expr (dump_file
, var
, 0);
2055 fprintf(dump_file
, ", ");
2060 /* This function frees memory allocated for strcuture clusters,
2061 starting from CLUSTER. */
2064 free_struct_cluster (struct field_cluster
* cluster
)
2068 if (cluster
->fields_in_cluster
)
2069 sbitmap_free (cluster
->fields_in_cluster
);
2070 if (cluster
->sibling
)
2071 free_struct_cluster (cluster
->sibling
);
2076 /* Free all allocated memory under the structure node pointed by D_NODE. */
2079 free_data_struct (d_str d_node
)
2088 fprintf (dump_file
, "\nRemoving data structure \"");
2089 print_generic_expr (dump_file
, d_node
->decl
, 0);
2090 fprintf (dump_file
, "\" from data_struct_list.");
2093 /* Free all space under d_node. */
2096 for (i
= 0; i
< d_node
->num_fields
; i
++)
2097 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2098 free (d_node
->fields
);
2102 free_accesses (d_node
->accs
);
2104 if (d_node
->struct_clustering
)
2105 free_struct_cluster (d_node
->struct_clustering
);
2107 if (d_node
->new_types
)
2108 VEC_free (tree
, heap
, d_node
->new_types
);
2111 /* This function creates new general and field accesses in BB. */
2114 create_new_accesses_in_bb (basic_block bb
)
2119 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2120 create_new_accs_for_struct (str
, bb
);
2123 /* This function adds allocation sites for peeled structures.
2124 M_DATA is vector of allocation sites of function CONTEXT. */
2127 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2133 VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2135 tree stmt
= call
->stmt
;
2136 d_str str
= call
->str
;
2138 tree new_stmts
= NULL_TREE
;
2139 tree last_stmt
= get_final_alloc_stmt (stmt
);
2143 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2146 last_stmt
= tsi_stmt (tsi_last (new_stmts
));
2147 insert_after_stmt (last_stmt
, new_stmts
);
2150 /* Generate an allocation sites for each new structure type. */
2152 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2154 tree new_malloc_stmt
= NULL_TREE
;
2155 tree last_stmt_tmp
= NULL_TREE
;
2157 new_stmts
= NULL_TREE
;
2158 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2159 last_stmt_tmp
= tsi_stmt (tsi_last (new_stmts
));
2160 insert_after_stmt (last_stmt
, new_stmts
);
2161 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2162 last_stmt
= last_stmt_tmp
;
2167 /* This function prints new variables from hashtable
2168 NEW_VARS_HTAB to dump_file. */
2171 dump_new_vars (htab_t new_vars_htab
)
2177 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2180 /* Given an original variable ORIG_DECL of structure type STR,
2181 this function generates new variables of the types defined
2182 by STR->new_type. Generated types are saved in new_var node NODE.
2183 ORIG_DECL should has VAR_DECL tree_code. */
2186 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2192 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2194 tree new_decl
= NULL
;
2197 new_name
= gen_var_name (orig_decl
, i
);
2198 type
= gen_struct_type (orig_decl
, type
);
2200 if (is_global_var (orig_decl
))
2201 new_decl
= build_decl (VAR_DECL
, new_name
, type
);
2204 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2205 new_decl
= create_tmp_var (type
, name
);
2208 copy_decl_attributes (new_decl
, orig_decl
);
2209 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2213 /* This function creates new variables to
2214 substitute the original variable VAR_DECL and adds
2215 them to the new_var's hashtable NEW_VARS_HTAB. */
2218 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2225 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2228 if (!is_candidate (var_decl
, &type
, NULL
))
2231 i
= find_structure (type
);
2232 if (i
== VEC_length (structure
, structures
))
2235 str
= VEC_index (structure
, structures
, i
);
2236 node
= create_new_var_node (var_decl
, str
);
2237 create_new_var_1 (var_decl
, str
, node
);
2238 add_to_new_vars_htab (node
, new_vars_htab
);
2241 /* Hash value for new_var. */
2244 new_var_hash (const void *x
)
2246 return htab_hash_pointer (((const_new_var
)x
)->orig_var
);
2249 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2252 new_var_eq (const void *x
, const void *y
)
2254 return ((const_new_var
)x
)->orig_var
== (const_tree
)y
;
2257 /* This function check whether a structure type represented by STR
2258 escapes due to ipa-type-escape analysis. If yes, this type is added
2259 to UNSUITABLE_TYPES vector. */
2262 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2264 tree type
= str
->decl
;
2266 if (!ipa_type_escape_type_contained_p (type
))
2270 fprintf (dump_file
, "\nEscaping type is ");
2271 print_generic_expr (dump_file
, type
, 0);
2273 add_unsuitable_type (unsuitable_types
, type
);
2277 /* Hash value for access_site. */
2280 acc_hash (const void *x
)
2282 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2285 /* Return nonzero if stmt of access_site X is equal to Y. */
2288 acc_eq (const void *x
, const void *y
)
2290 return ((const struct access_site
*)x
)->stmt
== (const_tree
)y
;
2293 /* Given a structure declaration STRUCT_DECL, and number of fields
2294 in the structure NUM_FIELDS, this function creates and returns
2295 corresponding field_entry's. */
2297 static struct field_entry
*
2298 get_fields (tree struct_decl
, int num_fields
)
2300 struct field_entry
*list
;
2301 tree t
= TYPE_FIELDS (struct_decl
);
2305 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2307 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2308 if (TREE_CODE (t
) == FIELD_DECL
)
2310 list
[idx
].index
= idx
;
2312 list
[idx
].acc_sites
=
2313 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2314 list
[idx
].count
= 0;
2315 list
[idx
].field_mapping
= NULL_TREE
;
2321 /* Print non-field accesses from hashtable ACCS of structure. */
2324 dump_access_sites (htab_t accs
)
2330 htab_traverse (accs
, dump_acc
, NULL
);
2333 /* This function removes the structure with index I from structures vector. */
2336 remove_structure (unsigned i
)
2340 if (i
>= VEC_length (structure
, structures
))
2343 str
= VEC_index (structure
, structures
, i
);
2344 free_data_struct (str
);
2345 VEC_ordered_remove (structure
, structures
, i
);
2348 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2349 COND_STNT is a condition statement to check. */
2352 is_safe_cond_expr (tree cond_stmt
)
2356 unsigned str0
, str1
;
2358 unsigned length
= VEC_length (structure
, structures
);
2360 tree cond
= COND_EXPR_COND (cond_stmt
);
2362 if (TREE_CODE (cond
) != EQ_EXPR
2363 && TREE_CODE (cond
) != NE_EXPR
)
2366 if (TREE_CODE_LENGTH (TREE_CODE (cond
)) != 2)
2369 arg0
= TREE_OPERAND (cond
, 0);
2370 arg1
= TREE_OPERAND (cond
, 1);
2372 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2373 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2375 s0
= (str0
!= length
) ? true : false;
2376 s1
= (str1
!= length
) ? true : false;
2378 if (!((!s0
&& s1
) || (!s1
&& s0
)))
2384 /* This function excludes statements, that are
2385 part of allocation sites or field accesses, from the
2386 hashtable of general accesses. SLOT represents general
2387 access that will be checked. DATA is a pointer to
2388 exclude_data structure. */
2391 exclude_from_accs (void **slot
, void *data
)
2393 struct access_site
*acc
= *(struct access_site
**) slot
;
2394 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2395 d_str str
= ((struct exclude_data
*)data
)->str
;
2397 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2398 || is_part_of_field_access (acc
->stmt
, str
))
2400 VEC_free (tree
, heap
, acc
->vars
);
2402 htab_clear_slot (str
->accs
, slot
);
2407 /* Callback function for walk_tree called from collect_accesses_in_bb
2408 function. DATA is the statement which is analyzed. */
2411 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2413 tree stmt
= (tree
) data
;
2419 switch (TREE_CODE (t
))
2421 case GIMPLE_MODIFY_STMT
:
2423 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
2424 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
2426 walk_tree (&lhs
, get_stmt_accesses
, data
, NULL
);
2427 walk_tree (&rhs
, get_stmt_accesses
, data
, NULL
);
2434 tree var
= TREE_OPERAND(t
, 0);
2435 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2436 unsigned i
= find_structure (type
);
2438 if (i
!= VEC_length (structure
, structures
))
2439 remove_structure (i
);
2445 tree ref
= TREE_OPERAND (t
, 0);
2446 tree field_decl
= TREE_OPERAND (t
, 1);
2449 if ((TREE_CODE (ref
) == INDIRECT_REF
2450 || TREE_CODE (ref
) == ARRAY_REF
2451 || TREE_CODE (ref
) == VAR_DECL
)
2452 && TREE_CODE (field_decl
) == FIELD_DECL
)
2454 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2455 unsigned i
= find_structure (type
);
2457 if (i
!= VEC_length (structure
, structures
))
2459 d_str str
= VEC_index (structure
, structures
, i
);
2460 struct field_entry
* field
=
2461 find_field_in_struct (str
, field_decl
);
2465 struct field_access_site
*acc
= make_field_acc_node ();
2472 acc
->field_decl
= field_decl
;
2474 /* Check whether the access is of the form
2475 we can deal with. */
2476 if (!decompose_access (str
->decl
, acc
))
2478 remove_structure (i
);
2483 /* Increase count of field. */
2484 basic_block bb
= bb_for_stmt (stmt
);
2485 field
->count
+= bb
->count
;
2487 /* Add stmt to the acc_sites of field. */
2488 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2500 tree op0
= TREE_OPERAND (t
, 0);
2501 tree op1
= TREE_OPERAND (t
, 1);
2503 walk_tree (&op0
, get_stmt_accesses
, data
, NULL
);
2504 walk_tree (&op1
, get_stmt_accesses
, data
, NULL
);
2511 tree cond
= COND_EXPR_COND (t
);
2513 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2515 tree t
= TREE_OPERAND (cond
, i
);
2518 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2529 if (TREE_CODE (t
) == SSA_NAME
)
2530 t
= SSA_NAME_VAR (t
);
2532 i
= find_structure (strip_type (get_type_of_var (t
)));
2533 if (i
!= VEC_length (structure
, structures
))
2537 str
= VEC_index (structure
, structures
, i
);
2538 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2546 /* It was checked as part of stage1 that structures
2547 to be transformed cannot be passed as parameters of functions. */
2559 /* Free structures hashtable. */
2562 free_structures (void)
2567 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2568 free_data_struct (str
);
2570 VEC_free (structure
, heap
, structures
);
2574 /* This function is a callback for traversal over new_var's hashtable.
2575 SLOT is a pointer to new_var. This function frees memory allocated
2576 for new_var and pointed by *SLOT. */
2579 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2581 new_var n_var
= *(new_var
*) slot
;
2583 /* Free vector of new_vars. */
2584 VEC_free (tree
, heap
, n_var
->new_vars
);
2589 /* Free new_vars hashtable NEW_VARS_HTAB. */
2592 free_new_vars_htab (htab_t new_vars_htab
)
2595 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2596 htab_delete (new_vars_htab
);
2597 new_vars_htab
= NULL
;
2600 /* This function creates new general and field accesses that appear in cfun. */
2603 create_new_accesses_for_func (void)
2607 FOR_EACH_BB_FN (bb
, cfun
)
2608 create_new_accesses_in_bb (bb
);
2611 /* Create new allocation sites for the function represented by NODE. */
2614 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2616 fallocs_t fallocs
= get_fallocs (node
->decl
);
2619 create_new_alloc_sites (fallocs
, node
->decl
);
2622 /* For each local variable of structure type from the vector of structures
2623 this function generates new variable(s) to replace it. */
2626 create_new_local_vars (void)
2629 referenced_var_iterator rvi
;
2631 new_local_vars
= htab_create (num_referenced_vars
,
2632 new_var_hash
, new_var_eq
, NULL
);
2634 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2636 if (!is_global_var (var
))
2637 create_new_var (var
, new_local_vars
);
2641 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2642 dump_new_vars (new_local_vars
);
2645 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2648 print_shift (unsigned HOST_WIDE_INT shift
)
2650 unsigned HOST_WIDE_INT sh
= shift
;
2653 fprintf (dump_file
, " ");
2656 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2659 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2660 struct field_entry
* fields
, int num_fields
)
2664 for (i
= 0; i
< num_fields
; i
++)
2665 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2666 fields
[i
].field_mapping
= new_type
;
2669 /* This functions builds structure with FIELDS,
2670 NAME and attributes similar to ORIG_STRUCT.
2671 It returns the newly created structure. */
2674 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2676 tree attributes
= NULL_TREE
;
2680 if (TYPE_ATTRIBUTES (orig_struct
))
2681 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2682 ref
= make_node (RECORD_TYPE
);
2683 TYPE_SIZE (ref
) = 0;
2684 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2685 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2686 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2688 DECL_CONTEXT (x
) = ref
;
2689 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2691 TYPE_FIELDS (ref
) = fields
;
2693 TYPE_NAME (ref
) = name
;
2698 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2699 of preparation for new structure building. NUM_FIELDS is a total
2700 number of fields in the structure. The function returns newly
2701 generated fields. */
2704 create_fields (struct field_cluster
* cluster
,
2705 struct field_entry
* fields
, int num_fields
)
2708 tree new_types
= NULL_TREE
;
2709 tree last
= NULL_TREE
;
2711 for (i
= 0; i
< num_fields
; i
++)
2712 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2714 tree new_decl
= unshare_expr (fields
[i
].decl
);
2717 new_types
= new_decl
;
2719 TREE_CHAIN (last
) = new_decl
;
2723 TREE_CHAIN (last
) = NULL_TREE
;
2728 /* This function creates a cluster name. The name is based on
2729 the original structure name, if it is present. It has a form:
2731 <original_struct_name>_sub.<CLUST_NUM>
2733 The original structure name is taken from the type of DECL.
2734 If an original structure name is not present, it's generated to be:
2738 The function returns identifier of the new cluster name. */
2741 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2743 const char * orig_name
= get_type_name (decl
);
2744 char * tmp_name
= NULL
;
2750 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2752 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2753 prefix
= alloca (len
+ 1);
2754 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2755 strlen (tmp_name
? tmp_name
: orig_name
));
2756 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2758 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2759 return get_identifier (new_name
);
2762 /* This function checks whether the structure STR has bitfields.
2763 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2766 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2768 tree type
= str
->decl
;
2771 for (i
= 0; i
< str
->num_fields
; i
++)
2772 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2774 add_unsuitable_type (unsuitable_types
, type
);
2777 fprintf (dump_file
, "\nType ");
2778 print_generic_expr (dump_file
, type
, 0);
2779 fprintf (dump_file
, "\nescapes due to bitfield ");
2780 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2786 /* This function adds to UNSUITABLE_TYPES those types that escape
2787 due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h]. */
2790 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2795 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2796 check_type_escape (str
, unsuitable_types
);
2799 /* If a structure type is a return type of any function,
2800 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2803 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2805 struct cgraph_node
*c_node
;
2807 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2809 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2813 ret_t
= strip_type (ret_t
);
2814 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2816 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2819 fprintf (dump_file
, "\nThe type \"");
2820 print_generic_expr (dump_file
, ret_t
, 0);
2822 "\" is return type of function...Excluded.");
2829 /* This function looks for parameters of local functions
2830 which are of structure types, or derived from them (arrays
2831 of structures, pointers to structures, or their combinations).
2832 We are not handling peeling of such structures right now.
2833 The found structures types are added to UNSUITABLE_TYPES vector. */
2836 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2838 struct cgraph_node
*c_node
;
2840 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2841 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2843 tree fn
= c_node
->decl
;
2846 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2848 tree type
= TREE_TYPE (arg
);
2850 type
= strip_type (type
);
2851 if (TREE_CODE (type
) == RECORD_TYPE
)
2853 add_unsuitable_type (unsuitable_types
,
2854 TYPE_MAIN_VARIANT (type
));
2857 fprintf (dump_file
, "\nPointer to type \"");
2858 print_generic_expr (dump_file
, type
, 0);
2860 "\" is passed to local function...Excluded.");
2867 /* This function analyzes structure form of structures
2868 potential for transformation. If we are not capable to transform
2869 structure of some form, we remove it from the structures hashtable.
2870 Right now we cannot handle nested structs, when nesting is
2871 through any level of pointers or arrays.
2873 TBD: release these constrains in future.
2875 Note, that in this function we suppose that all structures
2876 in the program are members of the structures hashtable right now,
2877 without excluding escaping types. */
2880 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2884 for (i
= 0; i
< str
->num_fields
; i
++)
2886 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2888 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2890 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2891 add_unsuitable_type (unsuitable_types
, str
->decl
);
2894 fprintf (dump_file
, "\nType ");
2895 print_generic_expr (dump_file
, f_type
, 0);
2896 fprintf (dump_file
, " is a field in the structure ");
2897 print_generic_expr (dump_file
, str
->decl
, 0);
2898 fprintf (dump_file
, ". Escaping...");
2904 /* This function adds a structure TYPE to the vector of structures,
2905 if it's not already there. */
2908 add_structure (tree type
)
2910 struct data_structure node
;
2914 type
= TYPE_MAIN_VARIANT (type
);
2916 i
= find_structure (type
);
2918 if (i
!= VEC_length (structure
, structures
))
2921 num_fields
= fields_length (type
);
2923 node
.num_fields
= num_fields
;
2924 node
.fields
= get_fields (type
, num_fields
);
2925 node
.struct_clustering
= NULL
;
2926 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
2927 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
2930 VEC_safe_push (structure
, heap
, structures
, &node
);
2934 fprintf (dump_file
, "\nAdding data structure \"");
2935 print_generic_expr (dump_file
, type
, 0);
2936 fprintf (dump_file
, "\" to data_struct_list.");
2940 /* This function adds an allocation site to alloc_sites hashtable.
2941 The allocation site appears in STMT of function FN_DECL and
2942 allocates the structure represented by STR. */
2945 add_alloc_site (tree fn_decl
, tree stmt
, d_str str
)
2947 fallocs_t fallocs
= NULL
;
2948 alloc_site_t m_call
;
2954 (fallocs_t
) htab_find_with_hash (alloc_sites
,
2955 fn_decl
, htab_hash_pointer (fn_decl
));
2961 fallocs
= (fallocs_t
)
2962 xmalloc (sizeof (struct func_alloc_sites
));
2963 fallocs
->func
= fn_decl
;
2964 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
2965 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
2966 htab_hash_pointer (fn_decl
), INSERT
);
2969 VEC_safe_push (alloc_site_t
, heap
,
2970 fallocs
->allocs
, &m_call
);
2974 fprintf (dump_file
, "\nAdding stmt ");
2975 print_generic_stmt (dump_file
, stmt
, 0);
2976 fprintf (dump_file
, " to list of mallocs.");
2980 /* This function returns true if the result of STMT, that contains a call
2981 to an allocation function, is cast to one of the structure types.
2982 STMT should be of the form: T.2 = <alloc_func> (T.1);
2983 If true, I_P contains an index of an allocated structure.
2984 Otherwise I_P contains the length of the vector of structures. */
2987 is_alloc_of_struct (tree stmt
, unsigned *i_p
)
2993 final_stmt
= get_final_alloc_stmt (stmt
);
2998 /* final_stmt should be of the form:
2999 T.3 = (struct_type *) T.2; */
3001 if (TREE_CODE (final_stmt
) != GIMPLE_MODIFY_STMT
)
3004 lhs
= GIMPLE_STMT_OPERAND (final_stmt
, 0);
3006 type
= get_type_of_var (lhs
);
3011 if (!POINTER_TYPE_P (type
)
3012 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3015 *i_p
= find_structure (strip_type (type
));
3017 if (*i_p
== VEC_length (structure
, structures
))
3023 /* This function prints non-field and field accesses
3024 of the structure STR. */
3027 dump_accs (d_str str
)
3031 fprintf (dump_file
, "\nAccess sites of struct ");
3032 print_generic_expr (dump_file
, str
->decl
, 0);
3034 for (i
= 0; i
< str
->num_fields
; i
++)
3036 fprintf (dump_file
, "\nAccess site of field ");
3037 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3038 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3039 fprintf (dump_file
, ":\n");
3041 fprintf (dump_file
, "\nGeneral access sites\n");
3042 dump_access_sites (str
->accs
);
3045 /* This function checks whether an access statement, pointed by SLOT,
3046 is a condition we are capable to transform. If not, it removes
3047 the structure with index, represented by DATA, from the vector
3051 safe_cond_expr_check (void **slot
, void *data
)
3053 struct access_site
*acc
= *(struct access_site
**) slot
;
3055 if (TREE_CODE (acc
->stmt
) == COND_EXPR
)
3057 if (!is_safe_cond_expr (acc
->stmt
))
3058 remove_structure (*(unsigned *) data
);
3063 /* This function excludes statements that are part of allocation sites and
3064 field accesses from the hashtable of general accesses of the structure
3065 type STR. Only accesses that belong to the function represented by
3066 NODE are treated. */
3069 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3071 struct exclude_data dt
;
3073 dt
.fn_decl
= node
->decl
;
3076 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3079 /* Collect accesses to the structure types that apear in basic bloack BB. */
3082 collect_accesses_in_bb (basic_block bb
)
3084 block_stmt_iterator bsi
;
3086 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
3088 tree stmt
= bsi_stmt (bsi
);
3090 /* In asm stmt we cannot always track the arguments,
3091 so we just give up. */
3092 if (TREE_CODE (stmt
) == ASM_EXPR
)
3098 walk_tree (&stmt
, get_stmt_accesses
, stmt
, NULL
);
3102 /* This function generates cluster substructure that cointains FIELDS.
3103 The cluster added to the set of clusters of the structure SRT. */
3106 gen_cluster (sbitmap fields
, d_str str
)
3108 struct field_cluster
*crr_cluster
= NULL
;
3111 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3112 crr_cluster
->sibling
= str
->struct_clustering
;
3113 str
->struct_clustering
= crr_cluster
;
3114 crr_cluster
->fields_in_cluster
= fields
;
3117 /* This function peels a field with the index I from the structure DS. */
3120 peel_field (int i
, d_str ds
)
3122 struct field_cluster
*crr_cluster
= NULL
;
3125 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3126 crr_cluster
->sibling
= ds
->struct_clustering
;
3127 ds
->struct_clustering
= crr_cluster
;
3128 crr_cluster
->fields_in_cluster
=
3129 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3130 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3131 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3134 /* This function calculates maximum field count in
3135 the structure STR. */
3138 get_max_field_count (d_str str
)
3143 for (i
= 0; i
< str
->num_fields
; i
++)
3144 if (str
->fields
[i
].count
> max
)
3145 max
= str
->fields
[i
].count
;
3150 /* Do struct-reorg transformation for individual function
3151 represented by NODE. All structure types relevant
3152 for this function are transformed. */
3155 do_reorg_for_func (struct cgraph_node
*node
)
3157 create_new_local_vars ();
3158 create_new_alloc_sites_for_func (node
);
3159 create_new_accesses_for_func ();
3160 update_ssa (TODO_update_ssa
);
3161 cleanup_tree_cfg ();
3163 /* Free auxiliary data representing local variables. */
3164 free_new_vars_htab (new_local_vars
);
3167 /* Print structure TYPE, its name, if it exists, and body.
3168 INDENT defines the level of indentation (similar
3169 to the option -i of indent command). SHIFT parameter
3170 defines a number of spaces by which a structure will
3171 be shifted right. */
3174 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3175 unsigned HOST_WIDE_INT shift
)
3177 const char *struct_name
;
3180 if (!type
|| !dump_file
)
3183 if (TREE_CODE (type
) != RECORD_TYPE
)
3185 print_generic_expr (dump_file
, type
, 0);
3189 print_shift (shift
);
3190 struct_name
= get_type_name (type
);
3191 fprintf (dump_file
, "struct ");
3193 fprintf (dump_file
, "%s\n",struct_name
);
3194 print_shift (shift
);
3195 fprintf (dump_file
, "{\n");
3197 for (field
= TYPE_FIELDS (type
); field
;
3198 field
= TREE_CHAIN (field
))
3200 unsigned HOST_WIDE_INT s
= indent
;
3201 tree f_type
= TREE_TYPE (field
);
3203 print_shift (shift
);
3205 fprintf (dump_file
, " ");
3206 dump_struct_type (f_type
, indent
, shift
+ indent
);
3207 fprintf(dump_file
, " ");
3208 print_generic_expr (dump_file
, field
, 0);
3209 fprintf(dump_file
, ";\n");
3211 print_shift (shift
);
3212 fprintf (dump_file
, "}\n");
3215 /* This function creates new structure types to replace original type,
3216 indicated by STR->decl. The names of the new structure types are
3217 derived from the original structure type. If the original structure
3218 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3221 create_new_type (d_str str
, int *str_num
)
3223 int cluster_num
= 0;
3225 struct field_cluster
*cluster
= str
->struct_clustering
;
3228 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3234 fields
= create_fields (cluster
, str
->fields
,
3236 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3238 update_fields_mapping (cluster
, new_type
,
3239 str
->fields
, str
->num_fields
);
3241 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3242 cluster
= cluster
->sibling
;
3247 /* This function is a callback for alloc_sites hashtable
3248 traversal. SLOT is a pointer to fallocs_t.
3249 This function frees memory pointed by *SLOT. */
3252 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3254 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3256 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3261 /* Remove structures collected in UNSUITABLE_TYPES
3262 from structures vector. */
3265 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3271 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3272 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3273 if (is_equal_types (str
->decl
, type
))
3275 remove_structure (i
);
3280 /* Exclude structure types with bitfields.
3281 We would not want to interfere with other optimizations
3282 that can be done in this case. The structure types with
3283 bitfields are added to UNSUITABLE_TYPES vector. */
3286 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3291 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3292 check_bitfields (str
, unsuitable_types
);
3295 /* This function checks three types of escape. A structure type escapes:
3297 1. if it's a type of parameter of a local function.
3298 2. if it's a type of function return value.
3299 3. if it escapes as a result of ipa-type-escape analysis.
3301 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3304 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3306 exclude_types_passed_to_local_func (unsuitable_types
);
3307 exclude_returned_types (unsuitable_types
);
3308 exclude_escaping_types_1 (unsuitable_types
);
3311 /* This function analyzes whether the form of
3312 structure is such that we are capable to transform it.
3313 Nested structures are checked here. Unsuitable structure
3314 types are added to UNSUITABLE_TYPE vector. */
3317 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3322 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3323 check_struct_form (str
, unsuitable_types
);
3326 /* This function looks for structure types instantiated in the program.
3327 The candidate types are added to the structures vector.
3328 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3331 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3335 struct varpool_node
*current_varpool
;
3336 struct cgraph_node
*c_node
;
3338 /* Check global variables. */
3339 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3341 var
= current_varpool
->decl
;
3342 if (is_candidate (var
, &type
, unsuitable_types
))
3343 add_structure (type
);
3346 /* Now add structures that are types of function parameters and
3348 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3350 enum availability avail
=
3351 cgraph_function_body_availability (c_node
);
3353 /* We need AVAIL_AVAILABLE for main function. */
3354 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3356 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3358 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3359 var
= TREE_CHAIN (var
))
3360 if (is_candidate (var
, &type
, unsuitable_types
))
3361 add_structure (type
);
3363 /* Check function local variables. */
3364 for (var_list
= fn
->unexpanded_var_list
; var_list
;
3365 var_list
= TREE_CHAIN (var_list
))
3367 var
= TREE_VALUE (var_list
);
3369 if (is_candidate (var
, &type
, unsuitable_types
))
3370 add_structure (type
);
3376 /* This function returns true if the program contains
3377 a call to user defined allocation function, or other
3378 functions that can interfere with struct-reorg optimizations. */
3381 program_redefines_malloc_p (void)
3383 struct cgraph_node
*c_node
;
3384 struct cgraph_node
*c_node2
;
3385 struct cgraph_edge
*c_edge
;
3390 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3392 fndecl
= c_node
->decl
;
3394 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3396 call_expr
= get_call_expr_in (c_edge
->call_stmt
);
3397 c_node2
= c_edge
->callee
;
3398 fndecl2
= c_node2
->decl
;
3401 const char * fname
= get_name (fndecl2
);
3403 if ((call_expr_flags (call_expr
) & ECF_MALLOC
) &&
3404 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
) &&
3405 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
) &&
3406 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3409 /* Check that there is no __builtin_object_size,
3410 __builtin_offsetof, or realloc's in the program. */
3411 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3412 || !strcmp (fname
, "__builtin_offsetof")
3413 || !strcmp (fname
, "realloc"))
3422 /* In this function we assume that an allocation statement
3424 var = (type_cast) malloc (size);
3426 is converted into the following set of statements:
3430 T.3 = (type_cast) T.2;
3433 In this function we collect into alloc_sites the allocation
3434 sites of variables of structure types that are present
3435 in structures vector. */
3438 collect_alloc_sites (void)
3440 struct cgraph_node
*node
;
3441 struct cgraph_edge
*cs
;
3443 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3444 if (node
->analyzed
&& node
->decl
)
3446 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3448 tree stmt
= cs
->call_stmt
;
3452 tree call
= get_call_expr_in (stmt
);
3455 if (call
&& (decl
= get_callee_fndecl (call
))
3456 && TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3460 if (is_alloc_of_struct (stmt
, &i
))
3462 /* We support only malloc now. */
3463 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3467 str
= VEC_index (structure
, structures
, i
);
3468 add_alloc_site (node
->decl
, stmt
, str
);
3471 remove_structure (i
);
3479 /* Print collected accesses. */
3482 dump_accesses (void)
3490 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3494 /* This function checks whether the accesses of structures in condition
3495 expressions are of the kind we are capable to transform.
3496 If not, such structures are removed from the vector of structures. */
3499 check_cond_exprs (void)
3504 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3506 htab_traverse (str
->accs
, safe_cond_expr_check
, &i
);
3509 /* We exclude from non-field accesses of the structure
3510 all statements that will be treated as part of the structure
3511 allocation sites or field accesses. */
3514 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3519 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3520 exclude_alloc_and_field_accs_1 (str
, node
);
3523 /* This function collects accesses of the fields of the structures
3524 that appear at function FN. */
3527 collect_accesses_in_func (struct function
*fn
)
3534 /* Collect accesses for each basic blocks separately. */
3535 FOR_EACH_BB_FN (bb
, fn
)
3536 collect_accesses_in_bb (bb
);
3539 /* This function summarizes counts of the fields into the structure count. */
3542 sum_counts (d_str str
, gcov_type
*hotest
)
3547 for (i
= 0; i
< str
->num_fields
; i
++)
3551 fprintf (dump_file
, "\nCounter of field \"");
3552 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3553 fprintf (dump_file
, "\" is " HOST_WIDE_INT_PRINT_DEC
,
3554 str
->fields
[i
].count
);
3556 str
->count
+= str
->fields
[i
].count
;
3561 fprintf (dump_file
, "\nCounter of struct \"");
3562 print_generic_expr (dump_file
, str
->decl
, 0);
3563 fprintf (dump_file
, "\" is " HOST_WIDE_INT_PRINT_DEC
, str
->count
);
3566 if (str
->count
> *hotest
)
3567 *hotest
= str
->count
;
3570 /* This function peels the field into separate structure if it's
3571 sufficiently hot, i.e. if its count provides at least 90% of
3572 the maximum field count in the structure. */
3575 peel_hot_fields (d_str str
)
3577 gcov_type max_field_count
;
3578 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3581 sbitmap_ones (fields_left
);
3583 (gcov_type
) (get_max_field_count (str
)/100)*90;
3585 str
->struct_clustering
= NULL
;
3587 for (i
= 0; i
< str
->num_fields
; i
++)
3589 if (str
->count
>= max_field_count
)
3591 RESET_BIT (fields_left
, i
);
3592 peel_field (i
, str
);
3596 i
= sbitmap_first_set_bit (fields_left
);
3598 gen_cluster (fields_left
, str
);
3600 sbitmap_free (fields_left
);
3603 /* This function is a helper for do_reorg. It goes over
3604 functions in call graph and performs actual transformation
3610 struct cgraph_node
*node
;
3612 /* Initialize the default bitmap obstack. */
3613 bitmap_obstack_initialize (NULL
);
3615 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3616 if (node
->analyzed
&& node
->decl
&& !node
->next_clone
)
3618 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3619 current_function_decl
= node
->decl
;
3621 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3622 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3623 do_reorg_for_func (node
);
3624 free_dominance_info (CDI_DOMINATORS
);
3625 free_dominance_info (CDI_POST_DOMINATORS
);
3626 current_function_decl
= NULL
;
3633 /* This function creates new global struct variables.
3634 For each original variable, the set of new variables
3635 is created with the new structure types corresponding
3636 to the structure type of original variable.
3637 Only VAR_DECL variables are treated by this function. */
3640 create_new_global_vars (void)
3642 struct varpool_node
*current_varpool
;
3643 unsigned HOST_WIDE_INT i
;
3644 unsigned HOST_WIDE_INT varpool_size
= 0;
3646 for (i
= 0; i
< 2; i
++)
3649 new_global_vars
= htab_create (varpool_size
,
3650 new_var_hash
, new_var_eq
, NULL
);
3651 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3653 tree var_decl
= current_varpool
->decl
;
3655 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3660 create_new_var (var_decl
, new_global_vars
);
3664 if (new_global_vars
)
3665 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3668 /* Dump all new types generated by this optimization. */
3671 dump_new_types (void)
3680 fprintf (dump_file
, "\nThe following are the new types generated by"
3681 " this optimization:\n");
3683 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3684 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3685 dump_struct_type (type
, 2, 0);
3688 /* This function creates new types to replace old structure types. */
3691 create_new_types (void)
3697 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3698 create_new_type (str
, &str_num
);
3701 /* Free allocation sites hashtable. */
3704 free_alloc_sites (void)
3707 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3708 htab_delete (alloc_sites
);
3712 /* This function collects structures potential
3713 for peeling transformation, and inserts
3714 them into structures hashtable. */
3717 collect_structures (void)
3719 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3721 structures
= VEC_alloc (structure
, heap
, 32);
3723 /* If program contains user defined mallocs, we give up. */
3724 if (program_redefines_malloc_p ())
3727 /* Build data structures hashtable of all data structures
3729 build_data_structure (&unsuitable_types
);
3731 /* This function analyzes whether the form of
3732 structure is such that we are capable to transform it.
3733 Nested structures are checked here. */
3734 analyze_struct_form (&unsuitable_types
);
3736 /* This function excludes those structure types
3737 that escape compilation unit. */
3738 exclude_escaping_types (&unsuitable_types
);
3740 /* We do not want to change data layout of the structures with bitfields. */
3741 exclude_types_with_bit_fields (&unsuitable_types
);
3743 remove_unsuitable_types (unsuitable_types
);
3744 VEC_free (tree
, heap
, unsuitable_types
);
3746 if (!VEC_length (structure
, structures
))
3749 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3754 /* Collect structure allocation sites. In case of arrays
3755 we have nothing to do. */
3758 collect_allocation_sites (void)
3760 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3761 collect_alloc_sites ();
3764 /* This function collects data accesses for the
3765 structures to be transformed. For each structure
3766 field it updates the count field in field_entry. */
3769 collect_data_accesses (void)
3771 struct cgraph_node
*c_node
;
3773 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3775 enum availability avail
= cgraph_function_body_availability (c_node
);
3777 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3779 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3781 if (!c_node
->next_clone
)
3782 collect_accesses_in_func (func
);
3783 exclude_alloc_and_field_accs (c_node
);
3787 check_cond_exprs ();
3788 /* Print collected accesses. */
3792 /* We do not bother to transform cold structures.
3793 Coldness of the structure is defined relatively
3794 to the highest structure count among the structures
3795 to be transformed. It's triggered by the compiler parameter
3797 --param struct-reorg-cold-struct-ratio=<value>
3799 where <value> ranges from 0 to 100. Structures with count ratios
3800 that are less than this parameter are considered to be cold. */
3803 exclude_cold_structs (void)
3805 gcov_type hotest
= 0;
3809 /* We summarize counts of fields of a structure into the structure count. */
3810 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3811 sum_counts (str
, &hotest
);
3813 /* Remove cold structures from structures vector. */
3814 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3815 if (str
->count
* 100 < (hotest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3816 remove_structure (i
);
3819 /* This function decomposes original structure into substructures,
3828 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3829 peel_hot_fields (str
);
3833 /* Do the actual transformation for each structure
3834 from the structures hashtable. */
3839 /* Check that there is a work to do. */
3840 if (!VEC_length (structure
, structures
))
3843 /* Generate new types. */
3844 create_new_types ();
3847 /* Create new global variables. */
3848 create_new_global_vars ();
3849 dump_new_vars (new_global_vars
);
3851 /* Decompose structures for each function separately. */
3854 /* Free auxiliary data collected for global variables. */
3855 free_new_vars_htab (new_global_vars
);
3858 /* Free all auxiliary data used by this optimization. */
3861 free_data_structs (void)
3864 free_alloc_sites ();
3867 /* Perform structure decomposition (peeling). */
3870 reorg_structs (void)
3874 /* Collect structure types. */
3875 collect_structures ();
3877 /* Collect structure allocation sites. */
3878 collect_allocation_sites ();
3880 /* Collect structure accesses. */
3881 collect_data_accesses ();
3883 /* We transform only hot structures. */
3884 exclude_cold_structs ();
3887 /* Decompose structures into substructures, i.e. clusters. */
3891 /* Do the actual transformation for each structure
3892 from the structures hashtable. */
3895 /* Free all auxiliary data used by this optimization. */
3896 free_data_structs ();
3899 /* Struct-reorg optimization entry point function. */
3902 reorg_structs_drive (void)
3908 /* Struct-reorg optimization gate function. */
3911 struct_reorg_gate (void)
3913 return flag_ipa_struct_reorg
&& flag_whole_program
3917 struct tree_opt_pass pass_ipa_struct_reorg
=
3919 "ipa_struct_reorg", /* name */
3920 struct_reorg_gate
, /* gate */
3921 reorg_structs_drive
, /* execute */
3924 0, /* static_pass_number */
3925 TV_INTEGRATION
, /* tv_id */
3926 0, /* properties_required */
3927 0, /* properties_provided */
3928 0, /* properties_destroyed */
3929 TODO_verify_ssa
, /* todo_flags_start */
3930 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */