1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008 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. */
190 htab_t alloc_sites
= NULL
;
192 /* New global variables. Generated once for whole program. */
193 htab_t new_global_vars
;
195 /* New local variables. Generated per-function. */
196 htab_t new_local_vars
;
198 /* Vector of structures to be transformed. */
199 typedef struct data_structure structure
;
200 DEF_VEC_O (structure
);
201 DEF_VEC_ALLOC_O (structure
, heap
);
202 VEC (structure
, heap
) *structures
;
204 /* Forward declarations. */
205 static bool is_equal_types (tree
, tree
);
207 /* Strip structure TYPE from pointers and arrays. */
210 strip_type (tree type
)
212 gcc_assert (TYPE_P (type
));
214 while (POINTER_TYPE_P (type
)
215 || TREE_CODE (type
) == ARRAY_TYPE
)
216 type
= TREE_TYPE (type
);
221 /* This function returns type of VAR. */
224 get_type_of_var (tree var
)
229 if (TREE_CODE (var
) == PARM_DECL
)
230 return DECL_ARG_TYPE (var
);
232 return TREE_TYPE (var
);
235 /* Set of actions we do for each newly generated STMT. */
238 finalize_stmt (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 the allocation statement was of the form
313 D.2229_10 = <alloc_func> (D.2228_9);
314 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
316 if (size_def_stmt
&& 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 transformation. If yes, it returns true.
413 decompose_access (tree str_decl
, struct field_access_site
*acc
)
415 gcc_assert (acc
->ref
);
417 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
)
418 return decompose_indirect_ref_acc (str_decl
, acc
);
419 else if (TREE_CODE (acc
->ref
) == ARRAY_REF
)
421 else if (TREE_CODE (acc
->ref
) == VAR_DECL
)
427 /* This function creates empty field_access_site node. */
429 static inline struct field_access_site
*
430 make_field_acc_node (void)
432 int size
= sizeof (struct field_access_site
);
434 return (struct field_access_site
*) xcalloc (1, size
);
437 /* This function returns the structure field access, defined by STMT,
438 if it is already in hashtable of function accesses F_ACCS. */
440 static struct field_access_site
*
441 is_in_field_accs (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 function 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 variable ORIG_VAR, this function returns
591 new variable corresponding to it of NEW_TYPE type. */
594 find_new_var_of_type (tree orig_var
, tree new_type
)
597 gcc_assert (orig_var
&& new_type
);
599 if (TREE_CODE (orig_var
) == SSA_NAME
)
600 orig_var
= SSA_NAME_VAR (orig_var
);
602 var
= is_in_new_vars_htab (orig_var
, new_global_vars
);
604 var
= is_in_new_vars_htab (orig_var
, new_local_vars
);
606 return find_var_in_new_vars_vec (var
, new_type
);
609 /* This function generates stmt:
610 res = NUM * sizeof(TYPE) and returns it.
611 res is filled into RES. */
614 gen_size (tree num
, tree type
, tree
*res
)
616 tree struct_size
= TYPE_SIZE_UNIT (type
);
617 HOST_WIDE_INT struct_size_int
= TREE_INT_CST_LOW (struct_size
);
620 *res
= create_tmp_var (TREE_TYPE (num
), NULL
);
623 add_referenced_var (*res
);
625 if (exact_log2 (struct_size_int
) == -1)
627 tree size
= build_int_cst (TREE_TYPE (num
), struct_size_int
);
628 new_stmt
= build_gimple_modify_stmt (*res
, build2 (MULT_EXPR
,
634 tree C
= build_int_cst (TREE_TYPE (num
), exact_log2 (struct_size_int
));
636 new_stmt
= build_gimple_modify_stmt (*res
, build2 (LSHIFT_EXPR
,
641 finalize_stmt (new_stmt
);
645 /* This function generates and returns a statement, that cast variable
646 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
647 into RES_P. ORIG_CAST_STMT is the original cast statement. */
650 gen_cast_stmt (tree before_cast
, tree new_type
, tree orig_cast_stmt
,
653 tree lhs
, new_lhs
, new_stmt
;
654 gcc_assert (TREE_CODE (orig_cast_stmt
) == GIMPLE_MODIFY_STMT
);
656 lhs
= GIMPLE_STMT_OPERAND (orig_cast_stmt
, 0);
657 new_lhs
= find_new_var_of_type (lhs
, new_type
);
658 gcc_assert (new_lhs
);
660 new_stmt
= build_gimple_modify_stmt (new_lhs
,
664 finalize_stmt (new_stmt
);
669 /* This function builds an edge between BB and E->dest and updates
670 phi nodes of E->dest. It returns newly created edge. */
673 make_edge_and_fix_phis_of_dest (basic_block bb
, edge e
)
678 new_e
= make_edge (bb
, e
->dest
, e
->flags
);
680 for (phi
= phi_nodes (new_e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
682 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
683 add_phi_arg (phi
, arg
, new_e
);
689 /* This function inserts NEW_STMTS before STMT. */
692 insert_before_stmt (tree stmt
, tree new_stmts
)
694 block_stmt_iterator bsi
;
696 if (!stmt
|| !new_stmts
)
699 bsi
= bsi_for_stmt (stmt
);
700 bsi_insert_before (&bsi
, new_stmts
, BSI_SAME_STMT
);
703 /* Insert NEW_STMTS after STMT. */
706 insert_after_stmt (tree stmt
, tree new_stmts
)
708 block_stmt_iterator bsi
;
710 if (!stmt
|| !new_stmts
)
713 bsi
= bsi_for_stmt (stmt
);
714 bsi_insert_after (&bsi
, new_stmts
, BSI_SAME_STMT
);
717 /* This function returns vector of allocation sites
718 that appear in function FN_DECL. */
721 get_fallocs (tree fn_decl
)
723 return (fallocs_t
) htab_find_with_hash (alloc_sites
, fn_decl
,
724 htab_hash_pointer (fn_decl
));
727 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
728 and it is a part of allocation of a structure,
729 then it is usually followed by a cast stmt
730 p_8 = (struct str_t *) D.2225_7;
731 which is returned by this function. */
734 get_final_alloc_stmt (tree alloc_stmt
)
743 if (TREE_CODE (alloc_stmt
) != GIMPLE_MODIFY_STMT
)
746 alloc_res
= GIMPLE_STMT_OPERAND (alloc_stmt
, 0);
748 if (TREE_CODE (alloc_res
) != SSA_NAME
)
751 if (!single_imm_use (alloc_res
, &use_p
, &final_stmt
))
757 /* This function returns true if STMT is one of allocation
758 sites of function FN_DECL. It returns false otherwise. */
761 is_part_of_malloc (tree stmt
, tree fn_decl
)
763 fallocs_t fallocs
= get_fallocs (fn_decl
);
771 VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
); i
++)
772 if (call
->stmt
== stmt
773 || get_final_alloc_stmt (call
->stmt
) == stmt
)
779 /* Auxiliary structure for a lookup over field accesses. */
780 struct find_stmt_data
786 /* This function looks for DATA->stmt among
787 the statements involved in the field access,
788 defined by SLOT. It stops when it's found. */
791 find_in_field_accs (void **slot
, void *data
)
793 struct field_access_site
*f_acc
=
794 *(struct field_access_site
**) slot
;
795 tree stmt
= ((struct find_stmt_data
*)data
)->stmt
;
797 if (f_acc
->stmt
== stmt
798 || f_acc
->ref_def_stmt
== stmt
799 || f_acc
->cast_stmt
== stmt
)
801 ((struct find_stmt_data
*)data
)->found
= true;
808 /* This function checks whether STMT is part of field
809 accesses of structure STR. It returns true, if found,
810 and false otherwise. */
813 is_part_of_field_access (tree stmt
, d_str str
)
817 for (i
= 0; i
< str
->num_fields
; i
++)
819 struct find_stmt_data data
;
823 if (str
->fields
[i
].acc_sites
)
824 htab_traverse (str
->fields
[i
].acc_sites
, find_in_field_accs
, &data
);
833 /* Auxiliary data for exclude_from_accs function. */
841 /* This function returns component_ref with the BASE and
842 field named FIELD_ID from structure TYPE. */
845 build_comp_ref (tree base
, tree field_id
, tree type
)
851 /* Find field of structure type with the same name as field_id. */
852 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
854 if (DECL_NAME (field
) == field_id
)
863 return build3 (COMPONENT_REF
, TREE_TYPE (field
), base
, field
, NULL_TREE
);
867 /* This struct represent data used for walk_tree
868 called from function find_pos_in_stmt.
869 - ref is a tree to be found,
870 - and pos is a pointer that points to ref in stmt. */
878 /* This is a callback function for walk_tree, called from
879 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
880 When *TP is equal to DATA->ref, the walk_tree stops,
881 and found position, equal to TP, is assigned to DATA->pos. */
884 find_pos_in_stmt_1 (tree
*tp
, int *walk_subtrees
, void * data
)
886 struct ref_pos
* r_pos
= (struct ref_pos
*) data
;
887 tree ref
= r_pos
->ref
;
890 if (t
== ref
|| (TREE_CODE (t
) == SSA_NAME
&& SSA_NAME_VAR (t
) == ref
))
896 switch (TREE_CODE (t
))
898 case GIMPLE_MODIFY_STMT
:
900 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
901 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
903 walk_tree (&lhs
, find_pos_in_stmt_1
, data
, NULL
);
904 walk_tree (&rhs
, find_pos_in_stmt_1
, data
, NULL
);
916 /* This function looks for the pointer of REF in STMT,
917 It returns it, if found, and NULL otherwise. */
920 find_pos_in_stmt (tree stmt
, tree ref
)
922 struct ref_pos r_pos
;
926 walk_tree (&stmt
, find_pos_in_stmt_1
, &r_pos
, NULL
);
931 /* This structure is used to represent array
932 or pointer-to wrappers of structure type.
933 For example, if type1 is structure type,
934 then for type1 ** we generate two type_wrapper
935 structures with wrap = 0 each one.
936 It's used to unwind the original type up to
937 structure type, replace it with the new structure type
938 and wrap it back in the opposite order. */
940 typedef struct type_wrapper
942 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
945 /* Relevant for arrays as domain or index. */
949 DEF_VEC_O (type_wrapper_t
);
950 DEF_VEC_ALLOC_O (type_wrapper_t
, heap
);
952 /* This function replace field access ACC by the new
953 field access of structure type NEW_TYPE. */
956 replace_field_acc (struct field_access_site
*acc
, tree new_type
)
958 tree ref_var
= acc
->ref
;
963 tree field_id
= DECL_NAME (acc
->field_decl
);
964 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
965 type_wrapper_t
*wr_p
= NULL
;
967 while (TREE_CODE (ref_var
) == INDIRECT_REF
968 || TREE_CODE (ref_var
) == ARRAY_REF
)
972 if ( TREE_CODE (ref_var
) == INDIRECT_REF
)
980 wr
.domain
= TREE_OPERAND (ref_var
, 1);
983 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
984 ref_var
= TREE_OPERAND (ref_var
, 0);
987 new_ref
= find_new_var_of_type (ref_var
, new_type
);
988 finalize_global_creation (new_ref
);
990 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
992 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
994 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
995 if (wr_p
->wrap
) /* Array. */
996 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
997 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
999 new_ref
= build1 (INDIRECT_REF
, type
, new_ref
);
1000 VEC_pop (type_wrapper_t
, wrapper
);
1003 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
1004 VEC_free (type_wrapper_t
, heap
, wrapper
);
1006 if (TREE_CODE (acc
->stmt
) == GIMPLE_MODIFY_STMT
)
1008 lhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 0);
1009 rhs
= GIMPLE_STMT_OPERAND (acc
->stmt
, 1);
1012 if (lhs
== acc
->comp_ref
)
1013 GIMPLE_STMT_OPERAND (acc
->stmt
, 0) = new_acc
;
1014 else if (rhs
== acc
->comp_ref
)
1015 GIMPLE_STMT_OPERAND (acc
->stmt
, 1) = new_acc
;
1018 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1025 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1030 finalize_stmt (acc
->stmt
);
1033 /* This function replace field access ACC by a new field access
1034 of structure type NEW_TYPE. */
1037 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1040 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
1041 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1042 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1043 replace_field_acc (acc
, new_type
);
1048 /* This function looks for d_str, represented by TYPE, in the structures
1049 vector. If found, it returns an index of found structure. Otherwise
1050 it returns a length of the structures vector. */
1053 find_structure (tree type
)
1058 type
= TYPE_MAIN_VARIANT (type
);
1060 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
1061 if (is_equal_types (str
->decl
, type
))
1064 return VEC_length (structure
, structures
);
1067 /* In this function we create new statements that have the same
1068 form as ORIG_STMT, but of type NEW_TYPE. The statements
1069 treated by this function are simple assignments,
1070 like assignments: p.8_7 = p; or statements with rhs of
1071 tree codes PLUS_EXPR and MINUS_EXPR. */
1074 create_base_plus_offset (tree orig_stmt
, tree new_type
,
1078 tree new_lhs
, new_rhs
;
1081 gcc_assert (TREE_CODE (orig_stmt
) == GIMPLE_MODIFY_STMT
);
1083 lhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 0);
1084 rhs
= GIMPLE_STMT_OPERAND (orig_stmt
, 1);
1086 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1087 || TREE_CODE (lhs
) == SSA_NAME
);
1089 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1090 gcc_assert (new_lhs
);
1091 finalize_var_creation (new_lhs
);
1093 switch (TREE_CODE (rhs
))
1097 case POINTER_PLUS_EXPR
:
1099 tree op0
= TREE_OPERAND (rhs
, 0);
1100 tree op1
= TREE_OPERAND (rhs
, 1);
1101 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1102 unsigned str0
, str1
;
1103 unsigned length
= VEC_length (structure
, structures
);
1106 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1107 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1108 gcc_assert ((str0
!= length
) || (str1
!= length
));
1111 new_op0
= find_new_var_of_type (op0
, new_type
);
1113 new_op1
= find_new_var_of_type (op1
, new_type
);
1120 new_rhs
= build2 (TREE_CODE (rhs
), TREE_TYPE (new_op0
),
1129 new_stmt
= build_gimple_modify_stmt (new_lhs
, new_rhs
);
1130 finalize_stmt (new_stmt
);
1135 /* Given a field access F_ACC of the FIELD, this function
1136 replaces it by the new field access. */
1139 create_new_field_access (struct field_access_site
*f_acc
,
1140 struct field_entry field
)
1142 tree new_type
= field
.field_mapping
;
1145 tree mult_stmt
, cast_stmt
;
1146 tree cast_res
= NULL
;
1150 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1151 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1154 if (f_acc
->cast_stmt
)
1156 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1157 f_acc
->cast_stmt
, &cast_res
);
1158 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1161 if (f_acc
->ref_def_stmt
)
1169 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1171 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1174 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1175 D.2162_18 by an appropriate variable of new_type type. */
1176 replace_field_access_stmt (f_acc
, new_type
);
1179 /* This function creates a new condition statement
1180 corresponding to the original COND_STMT, adds new basic block
1181 and redirects condition edges. NEW_VAR is a new condition
1182 variable located in the condition statement at the position POS. */
1185 create_new_stmts_for_cond_expr_1 (tree new_var
, tree cond_stmt
, bool pos
)
1189 edge true_e
= NULL
, false_e
= NULL
;
1193 extract_true_false_edges_from_block (bb_for_stmt (cond_stmt
),
1196 new_cond
= unshare_expr (COND_EXPR_COND (cond_stmt
));
1198 TREE_OPERAND (new_cond
, pos
) = new_var
;
1200 new_stmt
= build3 (COND_EXPR
, TREE_TYPE (cond_stmt
),
1201 new_cond
, NULL_TREE
, NULL_TREE
);
1203 finalize_stmt (new_stmt
);
1205 /* Create new basic block after bb. */
1206 new_bb
= create_empty_bb (bb_for_stmt (cond_stmt
));
1208 /* Add new condition stmt to the new_bb. */
1209 stmt_list
= bb_stmt_list (new_bb
);
1210 append_to_statement_list (new_stmt
, &stmt_list
);
1211 add_bb_info (new_bb
, stmt_list
);
1214 /* Create false and true edges from new_bb. */
1215 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1216 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1218 /* Redirect one of original edges to point to new_bb. */
1219 if (TREE_CODE (cond_stmt
) == NE_EXPR
)
1220 redirect_edge_succ (true_e
, new_bb
);
1222 redirect_edge_succ (false_e
, new_bb
);
1225 /* This function creates new condition statements corresponding
1226 to original condition STMT, one for each new type, and
1227 recursively redirect edges to newly generated basic blocks. */
1230 create_new_stmts_for_cond_expr (tree stmt
)
1232 tree cond
= COND_EXPR_COND (stmt
);
1233 tree arg0
, arg1
, arg
;
1234 unsigned str0
, str1
;
1240 unsigned length
= VEC_length (structure
, structures
);
1242 gcc_assert (TREE_CODE (cond
) == EQ_EXPR
1243 || TREE_CODE (cond
) == NE_EXPR
);
1245 arg0
= TREE_OPERAND (cond
, 0);
1246 arg1
= TREE_OPERAND (cond
, 1);
1248 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1249 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1251 s0
= (str0
!= length
) ? true : false;
1252 s1
= (str1
!= length
) ? true : false;
1254 gcc_assert (s0
|| s1
);
1255 /* For now we allow only comparison with 0 or NULL. */
1256 gcc_assert (integer_zerop (arg0
) || integer_zerop (arg1
));
1258 str
= integer_zerop (arg0
) ?
1259 VEC_index (structure
, structures
, str1
):
1260 VEC_index (structure
, structures
, str0
);
1261 arg
= integer_zerop (arg0
) ? arg1
: arg0
;
1262 pos
= integer_zerop (arg0
) ? 1 : 0;
1264 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1268 new_arg
= find_new_var_of_type (arg
, type
);
1269 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1273 /* Create a new general access to replace original access ACC
1274 for structure type NEW_TYPE. */
1277 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1279 tree old_stmt
= acc
->stmt
;
1281 tree new_stmt
= unshare_expr (old_stmt
);
1285 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1288 tree new_var
= find_new_var_of_type (var
, new_type
);
1291 gcc_assert (new_var
);
1292 finalize_var_creation (new_var
);
1294 if (TREE_CODE (new_stmt
) == GIMPLE_MODIFY_STMT
)
1297 lhs
= GIMPLE_STMT_OPERAND (new_stmt
, 0);
1298 rhs
= GIMPLE_STMT_OPERAND (new_stmt
, 1);
1300 if (TREE_CODE (lhs
) == SSA_NAME
)
1301 lhs
= SSA_NAME_VAR (lhs
);
1302 if (TREE_CODE (rhs
) == SSA_NAME
)
1303 rhs
= SSA_NAME_VAR (rhs
);
1305 /* It can happen that rhs is a constructor.
1306 Then we have to replace it to be of new_type. */
1307 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
1309 /* Dealing only with empty constructors right now. */
1310 gcc_assert (VEC_empty (constructor_elt
,
1311 CONSTRUCTOR_ELTS (rhs
)));
1312 rhs
= build_constructor (new_type
, 0);
1313 GIMPLE_STMT_OPERAND (new_stmt
, 1) = rhs
;
1317 GIMPLE_STMT_OPERAND (new_stmt
, 0) = new_var
;
1318 else if (rhs
== var
)
1319 GIMPLE_STMT_OPERAND (new_stmt
, 1) = new_var
;
1322 pos
= find_pos_in_stmt (new_stmt
, var
);
1329 pos
= find_pos_in_stmt (new_stmt
, var
);
1335 finalize_stmt (new_stmt
);
1339 /* For each new type in STR this function creates new general accesses
1340 corresponding to the original access ACC. */
1343 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1346 tree stmt
= acc
->stmt
;
1349 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1353 new_stmt
= create_general_new_stmt (acc
, type
);
1354 insert_after_stmt (stmt
, new_stmt
);
1358 /* This function creates a new general access of structure STR
1359 to replace the access ACC. */
1362 create_new_general_access (struct access_site
*acc
, d_str str
)
1364 tree stmt
= acc
->stmt
;
1365 switch (TREE_CODE (stmt
))
1368 create_new_stmts_for_cond_expr (stmt
);
1372 create_new_stmts_for_general_acc (acc
, str
);
1376 /* Auxiliary data for creation of accesses. */
1377 struct create_acc_data
1384 /* This function creates a new general access, defined by SLOT.
1385 DATA is a pointer to create_acc_data structure. */
1388 create_new_acc (void **slot
, void *data
)
1390 struct access_site
*acc
= *(struct access_site
**) slot
;
1391 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1392 d_str str
= ((struct create_acc_data
*)data
)->str
;
1394 if (bb_for_stmt (acc
->stmt
) == bb
)
1395 create_new_general_access (acc
, str
);
1399 /* This function creates a new field access, defined by SLOT.
1400 DATA is a pointer to create_acc_data structure. */
1403 create_new_field_acc (void **slot
, void *data
)
1405 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1406 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1407 d_str str
= ((struct create_acc_data
*)data
)->str
;
1408 int i
= ((struct create_acc_data
*)data
)->field_index
;
1410 if (bb_for_stmt (f_acc
->stmt
) == bb
)
1411 create_new_field_access (f_acc
, str
->fields
[i
]);
1415 /* This function creates new accesses for the structure
1416 type STR in basic block BB. */
1419 create_new_accs_for_struct (d_str str
, basic_block bb
)
1422 struct create_acc_data dt
;
1426 dt
.field_index
= -1;
1428 for (i
= 0; i
< str
->num_fields
; i
++)
1432 if (str
->fields
[i
].acc_sites
)
1433 htab_traverse (str
->fields
[i
].acc_sites
,
1434 create_new_field_acc
, &dt
);
1437 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1440 /* This function inserts new variables from new_var,
1441 defined by SLOT, into varpool. */
1444 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1446 new_var n_var
= *(new_var
*) slot
;
1450 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1451 insert_global_to_varpool (var
);
1455 /* This function prints a field access site, defined by SLOT. */
1458 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1460 struct field_access_site
*f_acc
=
1461 *(struct field_access_site
**) slot
;
1463 fprintf(dump_file
, "\n");
1465 print_generic_stmt (dump_file
, f_acc
->stmt
, 0);
1466 if (f_acc
->ref_def_stmt
)
1467 print_generic_stmt (dump_file
, f_acc
->ref_def_stmt
, 0);
1468 if (f_acc
->cast_stmt
)
1469 print_generic_stmt (dump_file
, f_acc
->cast_stmt
, 0);
1473 /* Print field accesses from hashtable F_ACCS. */
1476 dump_field_acc_sites (htab_t f_accs
)
1482 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1485 /* Hash value for fallocs_t. */
1488 malloc_hash (const void *x
)
1490 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1493 /* This function returns nonzero if function of func_alloc_sites' X
1497 malloc_eq (const void *x
, const void *y
)
1499 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1502 /* This function is a callback for traversal over a structure accesses.
1503 It frees an access represented by SLOT. */
1506 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1508 struct access_site
* acc
= *(struct access_site
**) slot
;
1510 VEC_free (tree
, heap
, acc
->vars
);
1515 /* This is a callback function for traversal over field accesses.
1516 It frees a field access represented by SLOT. */
1519 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1521 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1527 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1528 if it is not there yet. */
1531 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1539 type
= TYPE_MAIN_VARIANT (type
);
1541 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1542 if (is_equal_types (t
, type
))
1545 if (i
== VEC_length (tree
, *unsuitable_types
))
1546 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1549 /* Given a type TYPE, this function returns the name of the type. */
1552 get_type_name (tree type
)
1554 if (! TYPE_NAME (type
))
1557 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1558 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1559 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1560 && DECL_NAME (TYPE_NAME (type
)))
1561 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1566 /* This function is a temporary hack to overcome the types problem.
1567 When several compilation units are compiled together
1568 with -combine, the TYPE_MAIN_VARIANT of the same type
1569 can appear differently in different compilation units.
1570 Therefore this function first compares type names.
1571 If there are no names, structure bodies are recursively
1575 is_equal_types (tree type1
, tree type2
)
1577 const char * name1
,* name2
;
1579 if ((!type1
&& type2
)
1580 ||(!type2
&& type1
))
1583 if (!type1
&& !type2
)
1586 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1592 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1595 name1
= get_type_name (type1
);
1596 name2
= get_type_name (type2
);
1598 if (name1
&& name2
&& !strcmp (name1
, name2
))
1601 if (name1
&& name2
&& strcmp (name1
, name2
))
1604 switch (TREE_CODE (type1
))
1607 case REFERENCE_TYPE
:
1609 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1615 case QUAL_UNION_TYPE
:
1619 /* Compare fields of structure. */
1620 for (field1
= TYPE_FIELDS (type1
); field1
;
1621 field1
= TREE_CHAIN (field1
))
1623 tree field2
= find_field_in_struct_1 (type2
, field1
);
1633 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1634 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1642 tree max1
, min1
, max2
, min2
;
1644 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1647 d1
= TYPE_DOMAIN (type1
);
1648 d2
= TYPE_DOMAIN (type2
);
1653 max1
= TYPE_MAX_VALUE (d1
);
1654 max2
= TYPE_MAX_VALUE (d2
);
1655 min1
= TYPE_MIN_VALUE (d1
);
1656 min2
= TYPE_MIN_VALUE (d2
);
1658 if (max1
&& max2
&& min1
&& min2
1659 && TREE_CODE (max1
) == TREE_CODE (max2
)
1660 && TREE_CODE (max1
) == INTEGER_CST
1661 && TREE_CODE (min1
) == TREE_CODE (min2
)
1662 && TREE_CODE (min1
) == INTEGER_CST
1663 && tree_int_cst_equal (max1
, max2
)
1664 && tree_int_cst_equal (min1
, min2
))
1676 /* This function free non-field accesses from hashtable ACCS. */
1679 free_accesses (htab_t accs
)
1682 htab_traverse (accs
, free_accs
, NULL
);
1686 /* This function free field accesses hashtable F_ACCS. */
1689 free_field_accesses (htab_t f_accs
)
1692 htab_traverse (f_accs
, free_field_accs
, NULL
);
1693 htab_delete (f_accs
);
1696 /* Update call graph with new edge generated by new MALLOC_STMT.
1697 The edge origin is CONTEXT function. */
1700 update_cgraph_with_malloc_call (tree malloc_stmt
, tree context
)
1703 struct cgraph_node
*src
, *dest
;
1704 tree malloc_fn_decl
;
1709 call_expr
= get_call_expr_in (malloc_stmt
);
1710 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1712 src
= cgraph_node (context
);
1713 dest
= cgraph_node (malloc_fn_decl
);
1714 cgraph_create_edge (src
, dest
, malloc_stmt
,
1715 0, 0, bb_for_stmt (malloc_stmt
)->loop_depth
);
1718 /* This function generates set of statements required
1719 to allocate number NUM of structures of type NEW_TYPE.
1720 The statements are stored in NEW_STMTS. The statement that contain
1721 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1724 create_new_malloc (tree malloc_stmt
, tree new_type
, tree
*new_stmts
, tree num
)
1726 tree new_malloc_size
;
1727 tree call_expr
, malloc_fn_decl
;
1728 tree new_stmt
, malloc_res
;
1729 tree call_stmt
, final_stmt
;
1732 gcc_assert (num
&& malloc_stmt
&& new_type
);
1733 *new_stmts
= alloc_stmt_list ();
1735 /* Generate argument to malloc as multiplication of num
1736 and size of new_type. */
1737 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1738 append_to_statement_list (new_stmt
, new_stmts
);
1740 /* Generate new call for malloc. */
1741 malloc_res
= create_tmp_var (ptr_type_node
, NULL
);
1744 add_referenced_var (malloc_res
);
1746 call_expr
= get_call_expr_in (malloc_stmt
);
1747 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1748 call_expr
= build_call_expr (malloc_fn_decl
, 1, new_malloc_size
);
1749 call_stmt
= build_gimple_modify_stmt (malloc_res
, call_expr
);
1750 finalize_stmt_and_append (new_stmts
, call_stmt
);
1752 /* Create new cast statement. */
1753 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1754 gcc_assert (final_stmt
);
1755 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1756 append_to_statement_list (new_stmt
, new_stmts
);
1761 /* This function returns a tree representing
1762 the number of instances of structure STR_DECL allocated
1763 by allocation STMT. If new statements are generated,
1764 they are filled into NEW_STMTS_P. */
1767 gen_num_of_structs_in_malloc (tree stmt
, tree str_decl
, tree
*new_stmts_p
)
1769 call_expr_arg_iterator iter
;
1773 HOST_WIDE_INT struct_size_int
;
1778 /* Get malloc argument. */
1779 call_expr
= get_call_expr_in (stmt
);
1783 arg
= first_call_expr_arg (call_expr
, &iter
);
1785 if (TREE_CODE (arg
) != SSA_NAME
1786 && !TREE_CONSTANT (arg
))
1789 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1790 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1792 gcc_assert (struct_size
);
1794 if (TREE_CODE (arg
) == SSA_NAME
)
1798 if (is_result_of_mult (arg
, &num
, struct_size
))
1801 num
= create_tmp_var (integer_type_node
, NULL
);
1804 add_referenced_var (num
);
1806 if (exact_log2 (struct_size_int
) == -1)
1807 div_stmt
= build_gimple_modify_stmt (num
,
1808 build2 (TRUNC_DIV_EXPR
,
1813 tree C
= build_int_cst (integer_type_node
,
1814 exact_log2 (struct_size_int
));
1817 build_gimple_modify_stmt (num
, build2 (RSHIFT_EXPR
,
1821 *new_stmts_p
= alloc_stmt_list ();
1822 append_to_statement_list (div_stmt
,
1824 finalize_stmt (div_stmt
);
1828 if (CONSTANT_CLASS_P (arg
)
1829 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1830 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1835 /* This function is a callback for traversal on new_var's hashtable.
1836 SLOT is a pointer to new_var. This function prints to dump_file
1837 an original variable and all new variables from the new_var
1838 pointed by *SLOT. */
1841 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1843 new_var n_var
= *(new_var
*) slot
;
1848 var_type
= get_type_of_var (n_var
->orig_var
);
1850 fprintf (dump_file
, "\nOrig var: ");
1851 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1852 fprintf (dump_file
, " of type ");
1853 print_generic_expr (dump_file
, var_type
, 0);
1854 fprintf (dump_file
, "\n");
1857 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1859 var_type
= get_type_of_var (var
);
1861 fprintf (dump_file
, " ");
1862 print_generic_expr (dump_file
, var
, 0);
1863 fprintf (dump_file
, " of type ");
1864 print_generic_expr (dump_file
, var_type
, 0);
1865 fprintf (dump_file
, "\n");
1870 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1873 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1876 DECL_ARTIFICIAL (new_decl
) = 1;
1877 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1878 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1879 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1880 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1881 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1882 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1883 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1885 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1887 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1888 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1892 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1893 the same way as a structure type is wrapped in DECL.
1894 It returns the generated type. */
1897 gen_struct_type (tree decl
, tree new_str_type
)
1899 tree type_orig
= get_type_of_var (decl
);
1900 tree new_type
= new_str_type
;
1901 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1903 type_wrapper_t
*wr_p
;
1905 while (POINTER_TYPE_P (type_orig
)
1906 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1908 if (POINTER_TYPE_P (type_orig
))
1911 wr
.domain
= NULL_TREE
;
1913 else if (TREE_CODE (type_orig
) == ARRAY_TYPE
)
1916 wr
.domain
= TYPE_DOMAIN (type_orig
);
1918 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1919 type_orig
= TREE_TYPE (type_orig
);
1922 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1924 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1926 if (wr_p
->wrap
) /* Array. */
1927 new_type
= build_array_type (new_type
, wr_p
->domain
);
1929 new_type
= build_pointer_type (new_type
);
1931 VEC_pop (type_wrapper_t
, wrapper
);
1934 VEC_free (type_wrapper_t
, heap
, wrapper
);
1938 /* This function generates and returns new variable name based on
1939 ORIG_DECL name, combined with index I.
1940 The form of the new name is <orig_name>.<I> . */
1943 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1945 const char *old_name
;
1949 if (!DECL_NAME (orig_decl
)
1950 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1953 /* If the original variable has a name, create an
1954 appropriate new name for the new variable. */
1956 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1957 prefix
= alloca (strlen (old_name
) + 1);
1958 strcpy (prefix
, old_name
);
1959 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1960 return get_identifier (new_name
);
1963 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1966 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1970 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1971 htab_hash_pointer (new_node
->orig_var
),
1976 /* This function creates and returns new_var_data node
1977 with empty new_vars and orig_var equal to VAR. */
1980 create_new_var_node (tree var
, d_str str
)
1984 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1985 node
->orig_var
= var
;
1986 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1990 /* Check whether the type of VAR is potential candidate for peeling.
1991 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1992 candidate type. If VAR is initialized, the type of VAR will be added
1993 to UNSUITABLE_TYPES. */
1996 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
1999 bool initialized
= false;
2006 /* There is no support of initialized vars. */
2007 if (TREE_CODE (var
) == VAR_DECL
2008 && DECL_INITIAL (var
) != NULL_TREE
)
2011 type
= get_type_of_var (var
);
2015 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2016 if (TREE_CODE (type
) != RECORD_TYPE
)
2020 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2024 fprintf (dump_file
, "The type ");
2025 print_generic_expr (dump_file
, type
, 0);
2026 fprintf (dump_file
, " is initialized...Excluded.");
2028 add_unsuitable_type (unsuitable_types
, type
);
2038 /* Hash value for field_access_site. */
2041 field_acc_hash (const void *x
)
2043 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2046 /* This function returns nonzero if stmt of field_access_site X
2050 field_acc_eq (const void *x
, const void *y
)
2052 return ((const struct field_access_site
*)x
)->stmt
== (const_tree
)y
;
2055 /* This function prints an access site, defined by SLOT. */
2058 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2060 struct access_site
*acc
= *(struct access_site
**) slot
;
2064 fprintf(dump_file
, "\n");
2066 print_generic_stmt (dump_file
, acc
->stmt
, 0);
2067 fprintf(dump_file
, " : ");
2069 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2071 print_generic_expr (dump_file
, var
, 0);
2072 fprintf(dump_file
, ", ");
2077 /* This function frees memory allocated for structure clusters,
2078 starting from CLUSTER. */
2081 free_struct_cluster (struct field_cluster
* cluster
)
2085 if (cluster
->fields_in_cluster
)
2086 sbitmap_free (cluster
->fields_in_cluster
);
2087 if (cluster
->sibling
)
2088 free_struct_cluster (cluster
->sibling
);
2093 /* Free all allocated memory under the structure node pointed by D_NODE. */
2096 free_data_struct (d_str d_node
)
2105 fprintf (dump_file
, "\nRemoving data structure \"");
2106 print_generic_expr (dump_file
, d_node
->decl
, 0);
2107 fprintf (dump_file
, "\" from data_struct_list.");
2110 /* Free all space under d_node. */
2113 for (i
= 0; i
< d_node
->num_fields
; i
++)
2114 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2115 free (d_node
->fields
);
2119 free_accesses (d_node
->accs
);
2121 if (d_node
->struct_clustering
)
2122 free_struct_cluster (d_node
->struct_clustering
);
2124 if (d_node
->new_types
)
2125 VEC_free (tree
, heap
, d_node
->new_types
);
2128 /* This function creates new general and field accesses in BB. */
2131 create_new_accesses_in_bb (basic_block bb
)
2136 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2137 create_new_accs_for_struct (str
, bb
);
2140 /* This function adds allocation sites for peeled structures.
2141 M_DATA is vector of allocation sites of function CONTEXT. */
2144 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2150 VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2152 tree stmt
= call
->stmt
;
2153 d_str str
= call
->str
;
2155 tree new_stmts
= NULL_TREE
;
2156 tree last_stmt
= get_final_alloc_stmt (stmt
);
2160 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2163 last_stmt
= tsi_stmt (tsi_last (new_stmts
));
2164 insert_after_stmt (last_stmt
, new_stmts
);
2167 /* Generate an allocation sites for each new structure type. */
2169 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2171 tree new_malloc_stmt
= NULL_TREE
;
2172 tree last_stmt_tmp
= NULL_TREE
;
2174 new_stmts
= NULL_TREE
;
2175 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2176 last_stmt_tmp
= tsi_stmt (tsi_last (new_stmts
));
2177 insert_after_stmt (last_stmt
, new_stmts
);
2178 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2179 last_stmt
= last_stmt_tmp
;
2184 /* This function prints new variables from hashtable
2185 NEW_VARS_HTAB to dump_file. */
2188 dump_new_vars (htab_t new_vars_htab
)
2194 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2197 /* Given an original variable ORIG_DECL of structure type STR,
2198 this function generates new variables of the types defined
2199 by STR->new_type. Generated types are saved in new_var node NODE.
2200 ORIG_DECL should has VAR_DECL tree_code. */
2203 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2209 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2211 tree new_decl
= NULL
;
2214 new_name
= gen_var_name (orig_decl
, i
);
2215 type
= gen_struct_type (orig_decl
, type
);
2217 if (is_global_var (orig_decl
))
2218 new_decl
= build_decl (VAR_DECL
, new_name
, type
);
2221 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2222 new_decl
= create_tmp_var (type
, name
);
2225 copy_decl_attributes (new_decl
, orig_decl
);
2226 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2230 /* This function creates new variables to
2231 substitute the original variable VAR_DECL and adds
2232 them to the new_var's hashtable NEW_VARS_HTAB. */
2235 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2242 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2245 if (!is_candidate (var_decl
, &type
, NULL
))
2248 i
= find_structure (type
);
2249 if (i
== VEC_length (structure
, structures
))
2252 str
= VEC_index (structure
, structures
, i
);
2253 node
= create_new_var_node (var_decl
, str
);
2254 create_new_var_1 (var_decl
, str
, node
);
2255 add_to_new_vars_htab (node
, new_vars_htab
);
2258 /* Hash value for new_var. */
2261 new_var_hash (const void *x
)
2263 return htab_hash_pointer (((const_new_var
)x
)->orig_var
);
2266 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2269 new_var_eq (const void *x
, const void *y
)
2271 return ((const_new_var
)x
)->orig_var
== (const_tree
)y
;
2274 /* This function check whether a structure type represented by STR
2275 escapes due to ipa-type-escape analysis. If yes, this type is added
2276 to UNSUITABLE_TYPES vector. */
2279 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2281 tree type
= str
->decl
;
2283 if (!ipa_type_escape_type_contained_p (type
))
2287 fprintf (dump_file
, "\nEscaping type is ");
2288 print_generic_expr (dump_file
, type
, 0);
2290 add_unsuitable_type (unsuitable_types
, type
);
2294 /* Hash value for access_site. */
2297 acc_hash (const void *x
)
2299 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2302 /* Return nonzero if stmt of access_site X is equal to Y. */
2305 acc_eq (const void *x
, const void *y
)
2307 return ((const struct access_site
*)x
)->stmt
== (const_tree
)y
;
2310 /* Given a structure declaration STRUCT_DECL, and number of fields
2311 in the structure NUM_FIELDS, this function creates and returns
2312 corresponding field_entry's. */
2314 static struct field_entry
*
2315 get_fields (tree struct_decl
, int num_fields
)
2317 struct field_entry
*list
;
2318 tree t
= TYPE_FIELDS (struct_decl
);
2322 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2324 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2325 if (TREE_CODE (t
) == FIELD_DECL
)
2327 list
[idx
].index
= idx
;
2329 list
[idx
].acc_sites
=
2330 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2331 list
[idx
].count
= 0;
2332 list
[idx
].field_mapping
= NULL_TREE
;
2338 /* Print non-field accesses from hashtable ACCS of structure. */
2341 dump_access_sites (htab_t accs
)
2347 htab_traverse (accs
, dump_acc
, NULL
);
2350 /* This function is a callback for alloc_sites hashtable
2351 traversal. SLOT is a pointer to fallocs_t. This function
2352 removes all allocations of the structure defined by DATA. */
2355 remove_str_allocs_in_func (void **slot
, void *data
)
2357 fallocs_t fallocs
= *(fallocs_t
*) slot
;
2361 while (VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
))
2363 if (call
->str
== (d_str
) data
)
2364 VEC_ordered_remove (alloc_site_t
, fallocs
->allocs
, i
);
2372 /* This function remove all entries corresponding to the STR structure
2373 from alloc_sites hashtable. */
2376 remove_str_allocs (d_str str
)
2382 htab_traverse (alloc_sites
, remove_str_allocs_in_func
, str
);
2385 /* This function removes the structure with index I from structures vector. */
2388 remove_structure (unsigned i
)
2392 if (i
>= VEC_length (structure
, structures
))
2395 str
= VEC_index (structure
, structures
, i
);
2397 /* Before removing the structure str, we have to remove its
2398 allocations from alloc_sites hashtable. */
2399 remove_str_allocs (str
);
2400 free_data_struct (str
);
2401 VEC_ordered_remove (structure
, structures
, i
);
2404 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2405 COND_STMT is a condition statement to check. */
2408 is_safe_cond_expr (tree cond_stmt
)
2412 unsigned str0
, str1
;
2414 unsigned length
= VEC_length (structure
, structures
);
2416 tree cond
= COND_EXPR_COND (cond_stmt
);
2418 if (TREE_CODE (cond
) != EQ_EXPR
2419 && TREE_CODE (cond
) != NE_EXPR
)
2422 if (TREE_CODE_LENGTH (TREE_CODE (cond
)) != 2)
2425 arg0
= TREE_OPERAND (cond
, 0);
2426 arg1
= TREE_OPERAND (cond
, 1);
2428 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2429 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2431 s0
= (str0
!= length
) ? true : false;
2432 s1
= (str1
!= length
) ? true : false;
2437 /* For now we allow only comparison with 0 or NULL. */
2438 if (!integer_zerop (arg0
) && !integer_zerop (arg1
))
2444 /* This function excludes statements, that are
2445 part of allocation sites or field accesses, from the
2446 hashtable of general accesses. SLOT represents general
2447 access that will be checked. DATA is a pointer to
2448 exclude_data structure. */
2451 exclude_from_accs (void **slot
, void *data
)
2453 struct access_site
*acc
= *(struct access_site
**) slot
;
2454 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2455 d_str str
= ((struct exclude_data
*)data
)->str
;
2457 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2458 || is_part_of_field_access (acc
->stmt
, str
))
2460 VEC_free (tree
, heap
, acc
->vars
);
2462 htab_clear_slot (str
->accs
, slot
);
2467 /* Callback function for walk_tree called from collect_accesses_in_bb
2468 function. DATA is the statement which is analyzed. */
2471 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2473 tree stmt
= (tree
) data
;
2479 switch (TREE_CODE (t
))
2481 case GIMPLE_MODIFY_STMT
:
2483 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
2484 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
2486 walk_tree (&lhs
, get_stmt_accesses
, data
, NULL
);
2487 walk_tree (&rhs
, get_stmt_accesses
, data
, NULL
);
2494 tree var
= TREE_OPERAND(t
, 0);
2495 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2496 unsigned i
= find_structure (type
);
2498 if (i
!= VEC_length (structure
, structures
))
2502 fprintf (dump_file
, "\nThe type ");
2503 print_generic_expr (dump_file
, type
, 0);
2504 fprintf (dump_file
, " has bitfield.");
2506 remove_structure (i
);
2513 tree ref
= TREE_OPERAND (t
, 0);
2514 tree field_decl
= TREE_OPERAND (t
, 1);
2517 if ((TREE_CODE (ref
) == INDIRECT_REF
2518 || TREE_CODE (ref
) == ARRAY_REF
2519 || TREE_CODE (ref
) == VAR_DECL
)
2520 && TREE_CODE (field_decl
) == FIELD_DECL
)
2522 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2523 unsigned i
= find_structure (type
);
2525 if (i
!= VEC_length (structure
, structures
))
2527 d_str str
= VEC_index (structure
, structures
, i
);
2528 struct field_entry
* field
=
2529 find_field_in_struct (str
, field_decl
);
2533 struct field_access_site
*acc
= make_field_acc_node ();
2540 acc
->field_decl
= field_decl
;
2542 /* Check whether the access is of the form
2543 we can deal with. */
2544 if (!decompose_access (str
->decl
, acc
))
2548 fprintf (dump_file
, "\nThe type ");
2549 print_generic_expr (dump_file
, type
, 0);
2551 " has complicate access in statement ");
2552 print_generic_stmt (dump_file
, stmt
, 0);
2555 remove_structure (i
);
2560 /* Increase count of field. */
2561 basic_block bb
= bb_for_stmt (stmt
);
2562 field
->count
+= bb
->count
;
2564 /* Add stmt to the acc_sites of field. */
2565 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2577 tree op0
= TREE_OPERAND (t
, 0);
2578 tree op1
= TREE_OPERAND (t
, 1);
2580 walk_tree (&op0
, get_stmt_accesses
, data
, NULL
);
2581 walk_tree (&op1
, get_stmt_accesses
, data
, NULL
);
2588 tree cond
= COND_EXPR_COND (t
);
2590 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2592 tree t
= TREE_OPERAND (cond
, i
);
2595 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2606 if (TREE_CODE (t
) == SSA_NAME
)
2607 t
= SSA_NAME_VAR (t
);
2609 i
= find_structure (strip_type (get_type_of_var (t
)));
2610 if (i
!= VEC_length (structure
, structures
))
2614 str
= VEC_index (structure
, structures
, i
);
2615 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2623 /* It was checked as part of stage1 that structures
2624 to be transformed cannot be passed as parameters of functions. */
2636 /* Free structures hashtable. */
2639 free_structures (void)
2644 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2645 free_data_struct (str
);
2647 VEC_free (structure
, heap
, structures
);
2651 /* This function is a callback for traversal over new_var's hashtable.
2652 SLOT is a pointer to new_var. This function frees memory allocated
2653 for new_var and pointed by *SLOT. */
2656 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2658 new_var n_var
= *(new_var
*) slot
;
2660 /* Free vector of new_vars. */
2661 VEC_free (tree
, heap
, n_var
->new_vars
);
2666 /* Free new_vars hashtable NEW_VARS_HTAB. */
2669 free_new_vars_htab (htab_t new_vars_htab
)
2672 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2673 htab_delete (new_vars_htab
);
2674 new_vars_htab
= NULL
;
2677 /* This function creates new general and field accesses that appear in cfun. */
2680 create_new_accesses_for_func (void)
2684 FOR_EACH_BB_FN (bb
, cfun
)
2685 create_new_accesses_in_bb (bb
);
2688 /* Create new allocation sites for the function represented by NODE. */
2691 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2693 fallocs_t fallocs
= get_fallocs (node
->decl
);
2696 create_new_alloc_sites (fallocs
, node
->decl
);
2699 /* For each local variable of structure type from the vector of structures
2700 this function generates new variable(s) to replace it. */
2703 create_new_local_vars (void)
2706 referenced_var_iterator rvi
;
2708 new_local_vars
= htab_create (num_referenced_vars
,
2709 new_var_hash
, new_var_eq
, NULL
);
2711 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2713 if (!is_global_var (var
))
2714 create_new_var (var
, new_local_vars
);
2718 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2719 dump_new_vars (new_local_vars
);
2722 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2725 print_shift (unsigned HOST_WIDE_INT shift
)
2727 unsigned HOST_WIDE_INT sh
= shift
;
2730 fprintf (dump_file
, " ");
2733 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2736 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2737 struct field_entry
* fields
, int num_fields
)
2741 for (i
= 0; i
< num_fields
; i
++)
2742 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2743 fields
[i
].field_mapping
= new_type
;
2746 /* This functions builds structure with FIELDS,
2747 NAME and attributes similar to ORIG_STRUCT.
2748 It returns the newly created structure. */
2751 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2753 tree attributes
= NULL_TREE
;
2757 if (TYPE_ATTRIBUTES (orig_struct
))
2758 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2759 ref
= make_node (RECORD_TYPE
);
2760 TYPE_SIZE (ref
) = 0;
2761 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2762 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2763 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2765 DECL_CONTEXT (x
) = ref
;
2766 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2768 TYPE_FIELDS (ref
) = fields
;
2770 TYPE_NAME (ref
) = name
;
2775 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2776 of preparation for new structure building. NUM_FIELDS is a total
2777 number of fields in the structure. The function returns newly
2778 generated fields. */
2781 create_fields (struct field_cluster
* cluster
,
2782 struct field_entry
* fields
, int num_fields
)
2785 tree new_types
= NULL_TREE
;
2786 tree last
= NULL_TREE
;
2788 for (i
= 0; i
< num_fields
; i
++)
2789 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2791 tree new_decl
= unshare_expr (fields
[i
].decl
);
2794 new_types
= new_decl
;
2796 TREE_CHAIN (last
) = new_decl
;
2800 TREE_CHAIN (last
) = NULL_TREE
;
2805 /* This function creates a cluster name. The name is based on
2806 the original structure name, if it is present. It has a form:
2808 <original_struct_name>_sub.<CLUST_NUM>
2810 The original structure name is taken from the type of DECL.
2811 If an original structure name is not present, it's generated to be:
2815 The function returns identifier of the new cluster name. */
2818 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2820 const char * orig_name
= get_type_name (decl
);
2821 char * tmp_name
= NULL
;
2827 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2829 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2830 prefix
= alloca (len
+ 1);
2831 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2832 strlen (tmp_name
? tmp_name
: orig_name
));
2833 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2835 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2836 return get_identifier (new_name
);
2839 /* This function checks whether the structure STR has bitfields.
2840 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2843 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2845 tree type
= str
->decl
;
2848 for (i
= 0; i
< str
->num_fields
; i
++)
2849 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2851 add_unsuitable_type (unsuitable_types
, type
);
2854 fprintf (dump_file
, "\nType ");
2855 print_generic_expr (dump_file
, type
, 0);
2856 fprintf (dump_file
, "\nescapes due to bitfield ");
2857 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2863 /* This function adds to UNSUITABLE_TYPES those types that escape
2864 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2867 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2872 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2873 check_type_escape (str
, unsuitable_types
);
2876 /* If a structure type is a return type of any function,
2877 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2880 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2882 struct cgraph_node
*c_node
;
2884 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2886 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2890 ret_t
= strip_type (ret_t
);
2891 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2893 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2896 fprintf (dump_file
, "\nThe type \"");
2897 print_generic_expr (dump_file
, ret_t
, 0);
2899 "\" is return type of function...Excluded.");
2906 /* This function looks for parameters of local functions
2907 which are of structure types, or derived from them (arrays
2908 of structures, pointers to structures, or their combinations).
2909 We are not handling peeling of such structures right now.
2910 The found structures types are added to UNSUITABLE_TYPES vector. */
2913 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2915 struct cgraph_node
*c_node
;
2917 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2918 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2920 tree fn
= c_node
->decl
;
2923 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2925 tree type
= TREE_TYPE (arg
);
2927 type
= strip_type (type
);
2928 if (TREE_CODE (type
) == RECORD_TYPE
)
2930 add_unsuitable_type (unsuitable_types
,
2931 TYPE_MAIN_VARIANT (type
));
2934 fprintf (dump_file
, "\nPointer to type \"");
2935 print_generic_expr (dump_file
, type
, 0);
2937 "\" is passed to local function...Excluded.");
2944 /* This function analyzes structure form of structures
2945 potential for transformation. If we are not capable to transform
2946 structure of some form, we remove it from the structures hashtable.
2947 Right now we cannot handle nested structs, when nesting is
2948 through any level of pointers or arrays.
2950 TBD: release these constrains in future.
2952 Note, that in this function we suppose that all structures
2953 in the program are members of the structures hashtable right now,
2954 without excluding escaping types. */
2957 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2961 for (i
= 0; i
< str
->num_fields
; i
++)
2963 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2965 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2967 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2968 add_unsuitable_type (unsuitable_types
, str
->decl
);
2971 fprintf (dump_file
, "\nType ");
2972 print_generic_expr (dump_file
, f_type
, 0);
2973 fprintf (dump_file
, " is a field in the structure ");
2974 print_generic_expr (dump_file
, str
->decl
, 0);
2975 fprintf (dump_file
, ". Escaping...");
2981 /* This function adds a structure TYPE to the vector of structures,
2982 if it's not already there. */
2985 add_structure (tree type
)
2987 struct data_structure node
;
2991 type
= TYPE_MAIN_VARIANT (type
);
2993 i
= find_structure (type
);
2995 if (i
!= VEC_length (structure
, structures
))
2998 num_fields
= fields_length (type
);
3000 node
.num_fields
= num_fields
;
3001 node
.fields
= get_fields (type
, num_fields
);
3002 node
.struct_clustering
= NULL
;
3003 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
3004 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
3007 VEC_safe_push (structure
, heap
, structures
, &node
);
3011 fprintf (dump_file
, "\nAdding data structure \"");
3012 print_generic_expr (dump_file
, type
, 0);
3013 fprintf (dump_file
, "\" to data_struct_list.");
3017 /* This function adds an allocation site to alloc_sites hashtable.
3018 The allocation site appears in STMT of function FN_DECL and
3019 allocates the structure represented by STR. */
3022 add_alloc_site (tree fn_decl
, tree stmt
, d_str str
)
3024 fallocs_t fallocs
= NULL
;
3025 alloc_site_t m_call
;
3031 (fallocs_t
) htab_find_with_hash (alloc_sites
,
3032 fn_decl
, htab_hash_pointer (fn_decl
));
3038 fallocs
= (fallocs_t
)
3039 xmalloc (sizeof (struct func_alloc_sites
));
3040 fallocs
->func
= fn_decl
;
3041 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
3042 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
3043 htab_hash_pointer (fn_decl
), INSERT
);
3046 VEC_safe_push (alloc_site_t
, heap
,
3047 fallocs
->allocs
, &m_call
);
3051 fprintf (dump_file
, "\nAdding stmt ");
3052 print_generic_stmt (dump_file
, stmt
, 0);
3053 fprintf (dump_file
, " to list of mallocs.");
3057 /* This function returns true if the result of STMT, that contains a call
3058 to an allocation function, is cast to one of the structure types.
3059 STMT should be of the form: T.2 = <alloc_func> (T.1);
3060 If true, I_P contains an index of an allocated structure.
3061 Otherwise I_P contains the length of the vector of structures. */
3064 is_alloc_of_struct (tree stmt
, unsigned *i_p
)
3070 final_stmt
= get_final_alloc_stmt (stmt
);
3075 /* final_stmt should be of the form:
3076 T.3 = (struct_type *) T.2; */
3078 if (TREE_CODE (final_stmt
) != GIMPLE_MODIFY_STMT
)
3081 lhs
= GIMPLE_STMT_OPERAND (final_stmt
, 0);
3083 type
= get_type_of_var (lhs
);
3088 if (!POINTER_TYPE_P (type
)
3089 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3092 *i_p
= find_structure (strip_type (type
));
3094 if (*i_p
== VEC_length (structure
, structures
))
3100 /* This function prints non-field and field accesses
3101 of the structure STR. */
3104 dump_accs (d_str str
)
3108 fprintf (dump_file
, "\nAccess sites of struct ");
3109 print_generic_expr (dump_file
, str
->decl
, 0);
3111 for (i
= 0; i
< str
->num_fields
; i
++)
3113 fprintf (dump_file
, "\nAccess site of field ");
3114 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3115 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3116 fprintf (dump_file
, ":\n");
3118 fprintf (dump_file
, "\nGeneral access sites\n");
3119 dump_access_sites (str
->accs
);
3122 /* This function checks whether an access statement, pointed by SLOT,
3123 is a condition we are capable to transform. It returns false if not,
3124 setting bool *DATA to false. */
3127 safe_cond_expr_check (void **slot
, void *data
)
3129 struct access_site
*acc
= *(struct access_site
**) slot
;
3131 if (TREE_CODE (acc
->stmt
) == COND_EXPR
3132 && !is_safe_cond_expr (acc
->stmt
))
3136 fprintf (dump_file
, "\nUnsafe conditional statement ");
3137 print_generic_stmt (dump_file
, acc
->stmt
, 0);
3139 *(bool *) data
= false;
3145 /* This function excludes statements that are part of allocation sites and
3146 field accesses from the hashtable of general accesses of the structure
3147 type STR. Only accesses that belong to the function represented by
3148 NODE are treated. */
3151 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3153 struct exclude_data dt
;
3155 dt
.fn_decl
= node
->decl
;
3158 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3161 /* Collect accesses to the structure types that appear in basic block BB. */
3164 collect_accesses_in_bb (basic_block bb
)
3166 block_stmt_iterator bsi
;
3168 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
3170 tree stmt
= bsi_stmt (bsi
);
3172 /* In asm stmt we cannot always track the arguments,
3173 so we just give up. */
3174 if (TREE_CODE (stmt
) == ASM_EXPR
)
3180 walk_tree (&stmt
, get_stmt_accesses
, stmt
, NULL
);
3184 /* This function generates cluster substructure that contains FIELDS.
3185 The cluster added to the set of clusters of the structure STR. */
3188 gen_cluster (sbitmap fields
, d_str str
)
3190 struct field_cluster
*crr_cluster
= NULL
;
3193 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3194 crr_cluster
->sibling
= str
->struct_clustering
;
3195 str
->struct_clustering
= crr_cluster
;
3196 crr_cluster
->fields_in_cluster
= fields
;
3199 /* This function peels a field with the index I from the structure DS. */
3202 peel_field (int i
, d_str ds
)
3204 struct field_cluster
*crr_cluster
= NULL
;
3207 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3208 crr_cluster
->sibling
= ds
->struct_clustering
;
3209 ds
->struct_clustering
= crr_cluster
;
3210 crr_cluster
->fields_in_cluster
=
3211 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3212 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3213 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3216 /* This function calculates maximum field count in
3217 the structure STR. */
3220 get_max_field_count (d_str str
)
3225 for (i
= 0; i
< str
->num_fields
; i
++)
3226 if (str
->fields
[i
].count
> max
)
3227 max
= str
->fields
[i
].count
;
3232 /* Do struct-reorg transformation for individual function
3233 represented by NODE. All structure types relevant
3234 for this function are transformed. */
3237 do_reorg_for_func (struct cgraph_node
*node
)
3239 create_new_local_vars ();
3240 create_new_alloc_sites_for_func (node
);
3241 create_new_accesses_for_func ();
3242 update_ssa (TODO_update_ssa
);
3243 cleanup_tree_cfg ();
3245 /* Free auxiliary data representing local variables. */
3246 free_new_vars_htab (new_local_vars
);
3249 /* Print structure TYPE, its name, if it exists, and body.
3250 INDENT defines the level of indentation (similar
3251 to the option -i of indent command). SHIFT parameter
3252 defines a number of spaces by which a structure will
3253 be shifted right. */
3256 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3257 unsigned HOST_WIDE_INT shift
)
3259 const char *struct_name
;
3262 if (!type
|| !dump_file
)
3265 if (TREE_CODE (type
) != RECORD_TYPE
)
3267 print_generic_expr (dump_file
, type
, 0);
3271 print_shift (shift
);
3272 struct_name
= get_type_name (type
);
3273 fprintf (dump_file
, "struct ");
3275 fprintf (dump_file
, "%s\n",struct_name
);
3276 print_shift (shift
);
3277 fprintf (dump_file
, "{\n");
3279 for (field
= TYPE_FIELDS (type
); field
;
3280 field
= TREE_CHAIN (field
))
3282 unsigned HOST_WIDE_INT s
= indent
;
3283 tree f_type
= TREE_TYPE (field
);
3285 print_shift (shift
);
3287 fprintf (dump_file
, " ");
3288 dump_struct_type (f_type
, indent
, shift
+ indent
);
3289 fprintf(dump_file
, " ");
3290 print_generic_expr (dump_file
, field
, 0);
3291 fprintf(dump_file
, ";\n");
3293 print_shift (shift
);
3294 fprintf (dump_file
, "}\n");
3297 /* This function creates new structure types to replace original type,
3298 indicated by STR->decl. The names of the new structure types are
3299 derived from the original structure type. If the original structure
3300 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3303 create_new_type (d_str str
, int *str_num
)
3305 int cluster_num
= 0;
3307 struct field_cluster
*cluster
= str
->struct_clustering
;
3310 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3316 fields
= create_fields (cluster
, str
->fields
,
3318 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3320 update_fields_mapping (cluster
, new_type
,
3321 str
->fields
, str
->num_fields
);
3323 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3324 cluster
= cluster
->sibling
;
3329 /* This function is a callback for alloc_sites hashtable
3330 traversal. SLOT is a pointer to fallocs_t.
3331 This function frees memory pointed by *SLOT. */
3334 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3336 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3338 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3343 /* Remove structures collected in UNSUITABLE_TYPES
3344 from structures vector. */
3347 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3353 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3354 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3355 if (is_equal_types (str
->decl
, type
))
3357 remove_structure (i
);
3362 /* Exclude structure types with bitfields.
3363 We would not want to interfere with other optimizations
3364 that can be done in this case. The structure types with
3365 bitfields are added to UNSUITABLE_TYPES vector. */
3368 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3373 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3374 check_bitfields (str
, unsuitable_types
);
3377 /* This function checks three types of escape. A structure type escapes:
3379 1. if it's a type of parameter of a local function.
3380 2. if it's a type of function return value.
3381 3. if it escapes as a result of ipa-type-escape analysis.
3383 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3386 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3388 exclude_types_passed_to_local_func (unsuitable_types
);
3389 exclude_returned_types (unsuitable_types
);
3390 exclude_escaping_types_1 (unsuitable_types
);
3393 /* This function analyzes whether the form of
3394 structure is such that we are capable to transform it.
3395 Nested structures are checked here. Unsuitable structure
3396 types are added to UNSUITABLE_TYPE vector. */
3399 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3404 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3405 check_struct_form (str
, unsuitable_types
);
3408 /* This function looks for structure types instantiated in the program.
3409 The candidate types are added to the structures vector.
3410 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3413 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3417 struct varpool_node
*current_varpool
;
3418 struct cgraph_node
*c_node
;
3420 /* Check global variables. */
3421 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3423 var
= current_varpool
->decl
;
3424 if (is_candidate (var
, &type
, unsuitable_types
))
3425 add_structure (type
);
3428 /* Now add structures that are types of function parameters and
3430 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3432 enum availability avail
=
3433 cgraph_function_body_availability (c_node
);
3435 /* We need AVAIL_AVAILABLE for main function. */
3436 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3438 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3440 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3441 var
= TREE_CHAIN (var
))
3442 if (is_candidate (var
, &type
, unsuitable_types
))
3443 add_structure (type
);
3445 /* Check function local variables. */
3446 for (var_list
= fn
->local_decls
; var_list
;
3447 var_list
= TREE_CHAIN (var_list
))
3449 var
= TREE_VALUE (var_list
);
3451 if (is_candidate (var
, &type
, unsuitable_types
))
3452 add_structure (type
);
3458 /* This function returns true if the program contains
3459 a call to user defined allocation function, or other
3460 functions that can interfere with struct-reorg optimizations. */
3463 program_redefines_malloc_p (void)
3465 struct cgraph_node
*c_node
;
3466 struct cgraph_node
*c_node2
;
3467 struct cgraph_edge
*c_edge
;
3472 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3474 fndecl
= c_node
->decl
;
3476 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3478 call_expr
= get_call_expr_in (c_edge
->call_stmt
);
3479 c_node2
= c_edge
->callee
;
3480 fndecl2
= c_node2
->decl
;
3483 const char * fname
= get_name (fndecl2
);
3485 if ((call_expr_flags (call_expr
) & ECF_MALLOC
) &&
3486 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
) &&
3487 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
) &&
3488 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3491 /* Check that there is no __builtin_object_size,
3492 __builtin_offsetof, or realloc's in the program. */
3493 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3494 || !strcmp (fname
, "__builtin_offsetof")
3495 || !strcmp (fname
, "realloc"))
3504 /* In this function we assume that an allocation statement
3506 var = (type_cast) malloc (size);
3508 is converted into the following set of statements:
3512 T.3 = (type_cast) T.2;
3515 In this function we collect into alloc_sites the allocation
3516 sites of variables of structure types that are present
3517 in structures vector. */
3520 collect_alloc_sites (void)
3522 struct cgraph_node
*node
;
3523 struct cgraph_edge
*cs
;
3525 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3526 if (node
->analyzed
&& node
->decl
)
3528 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3530 tree stmt
= cs
->call_stmt
;
3534 tree call
= get_call_expr_in (stmt
);
3537 if (call
&& (decl
= get_callee_fndecl (call
))
3538 && TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3542 if (is_alloc_of_struct (stmt
, &i
))
3544 /* We support only malloc now. */
3545 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3549 str
= VEC_index (structure
, structures
, i
);
3550 add_alloc_site (node
->decl
, stmt
, str
);
3557 "\nUnsupported allocation function ");
3558 print_generic_stmt (dump_file
, stmt
, 0);
3560 remove_structure (i
);
3569 /* Print collected accesses. */
3572 dump_accesses (void)
3580 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3584 /* This function checks whether the accesses of structures in condition
3585 expressions are of the kind we are capable to transform.
3586 If not, such structures are removed from the vector of structures. */
3589 check_cond_exprs (void)
3595 while (VEC_iterate (structure
, structures
, i
, str
))
3600 htab_traverse (str
->accs
, safe_cond_expr_check
, &safe_p
);
3602 remove_structure (i
);
3608 /* We exclude from non-field accesses of the structure
3609 all statements that will be treated as part of the structure
3610 allocation sites or field accesses. */
3613 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3618 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3619 exclude_alloc_and_field_accs_1 (str
, node
);
3622 /* This function collects accesses of the fields of the structures
3623 that appear at function FN. */
3626 collect_accesses_in_func (struct function
*fn
)
3633 /* Collect accesses for each basic blocks separately. */
3634 FOR_EACH_BB_FN (bb
, fn
)
3635 collect_accesses_in_bb (bb
);
3638 /* This function summarizes counts of the fields into the structure count. */
3641 sum_counts (d_str str
, gcov_type
*hottest
)
3646 for (i
= 0; i
< str
->num_fields
; i
++)
3650 fprintf (dump_file
, "\nCounter of field \"");
3651 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3652 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3653 str
->fields
[i
].count
);
3655 str
->count
+= str
->fields
[i
].count
;
3660 fprintf (dump_file
, "\nCounter of struct \"");
3661 print_generic_expr (dump_file
, str
->decl
, 0);
3662 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3665 if (str
->count
> *hottest
)
3666 *hottest
= str
->count
;
3669 /* This function peels the field into separate structure if it's
3670 sufficiently hot, i.e. if its count provides at least 90% of
3671 the maximum field count in the structure. */
3674 peel_hot_fields (d_str str
)
3676 gcov_type max_field_count
;
3677 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3680 sbitmap_ones (fields_left
);
3682 (gcov_type
) (get_max_field_count (str
)/100)*90;
3684 str
->struct_clustering
= NULL
;
3686 for (i
= 0; i
< str
->num_fields
; i
++)
3688 if (str
->count
>= max_field_count
)
3690 RESET_BIT (fields_left
, i
);
3691 peel_field (i
, str
);
3695 i
= sbitmap_first_set_bit (fields_left
);
3697 gen_cluster (fields_left
, str
);
3699 sbitmap_free (fields_left
);
3702 /* This function is a helper for do_reorg. It goes over
3703 functions in call graph and performs actual transformation
3709 struct cgraph_node
*node
;
3711 /* Initialize the default bitmap obstack. */
3712 bitmap_obstack_initialize (NULL
);
3714 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3715 if (node
->analyzed
&& node
->decl
&& !node
->next_clone
)
3717 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3718 current_function_decl
= node
->decl
;
3720 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3721 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3722 do_reorg_for_func (node
);
3723 free_dominance_info (CDI_DOMINATORS
);
3724 free_dominance_info (CDI_POST_DOMINATORS
);
3725 current_function_decl
= NULL
;
3730 bitmap_obstack_release (NULL
);
3733 /* This function creates new global struct variables.
3734 For each original variable, the set of new variables
3735 is created with the new structure types corresponding
3736 to the structure type of original variable.
3737 Only VAR_DECL variables are treated by this function. */
3740 create_new_global_vars (void)
3742 struct varpool_node
*current_varpool
;
3743 unsigned HOST_WIDE_INT i
;
3744 unsigned HOST_WIDE_INT varpool_size
= 0;
3746 for (i
= 0; i
< 2; i
++)
3749 new_global_vars
= htab_create (varpool_size
,
3750 new_var_hash
, new_var_eq
, NULL
);
3751 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3753 tree var_decl
= current_varpool
->decl
;
3755 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3760 create_new_var (var_decl
, new_global_vars
);
3764 if (new_global_vars
)
3765 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3768 /* Dump all new types generated by this optimization. */
3771 dump_new_types (void)
3780 fprintf (dump_file
, "\nThe following are the new types generated by"
3781 " this optimization:\n");
3783 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3787 fprintf (dump_file
, "\nFor type ");
3788 dump_struct_type (str
->decl
, 2, 0);
3789 fprintf (dump_file
, "\nthe number of new types is %d\n",
3790 VEC_length (tree
, str
->new_types
));
3792 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3793 dump_struct_type (type
, 2, 0);
3797 /* This function creates new types to replace old structure types. */
3800 create_new_types (void)
3806 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3807 create_new_type (str
, &str_num
);
3810 /* Free allocation sites hashtable. */
3813 free_alloc_sites (void)
3816 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3817 htab_delete (alloc_sites
);
3821 /* This function collects structures potential
3822 for peeling transformation, and inserts
3823 them into structures hashtable. */
3826 collect_structures (void)
3828 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3830 structures
= VEC_alloc (structure
, heap
, 32);
3832 /* If program contains user defined mallocs, we give up. */
3833 if (program_redefines_malloc_p ())
3836 /* Build data structures hashtable of all data structures
3838 build_data_structure (&unsuitable_types
);
3840 /* This function analyzes whether the form of
3841 structure is such that we are capable to transform it.
3842 Nested structures are checked here. */
3843 analyze_struct_form (&unsuitable_types
);
3845 /* This function excludes those structure types
3846 that escape compilation unit. */
3847 exclude_escaping_types (&unsuitable_types
);
3849 /* We do not want to change data layout of the structures with bitfields. */
3850 exclude_types_with_bit_fields (&unsuitable_types
);
3852 remove_unsuitable_types (unsuitable_types
);
3853 VEC_free (tree
, heap
, unsuitable_types
);
3856 /* Collect structure allocation sites. In case of arrays
3857 we have nothing to do. */
3860 collect_allocation_sites (void)
3862 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3863 collect_alloc_sites ();
3866 /* This function collects data accesses for the
3867 structures to be transformed. For each structure
3868 field it updates the count field in field_entry. */
3871 collect_data_accesses (void)
3873 struct cgraph_node
*c_node
;
3875 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3877 enum availability avail
= cgraph_function_body_availability (c_node
);
3879 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3881 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3883 if (!c_node
->next_clone
)
3884 collect_accesses_in_func (func
);
3885 exclude_alloc_and_field_accs (c_node
);
3889 check_cond_exprs ();
3890 /* Print collected accesses. */
3894 /* We do not bother to transform cold structures.
3895 Coldness of the structure is defined relatively
3896 to the highest structure count among the structures
3897 to be transformed. It's triggered by the compiler parameter
3899 --param struct-reorg-cold-struct-ratio=<value>
3901 where <value> ranges from 0 to 100. Structures with count ratios
3902 that are less than this parameter are considered to be cold. */
3905 exclude_cold_structs (void)
3907 gcov_type hottest
= 0;
3911 /* We summarize counts of fields of a structure into the structure count. */
3912 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3913 sum_counts (str
, &hottest
);
3915 /* Remove cold structures from structures vector. */
3917 while (VEC_iterate (structure
, structures
, i
, str
))
3918 if (str
->count
* 100 < (hottest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3922 fprintf (dump_file
, "\nThe structure ");
3923 print_generic_expr (dump_file
, str
->decl
, 0);
3924 fprintf (dump_file
, " is cold.");
3926 remove_structure (i
);
3932 /* This function decomposes original structure into substructures,
3941 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3942 peel_hot_fields (str
);
3946 /* Do the actual transformation for each structure
3947 from the structures hashtable. */
3952 /* Check that there is a work to do. */
3953 if (!VEC_length (structure
, structures
))
3956 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3963 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3964 VEC_length (structure
, structures
));
3968 /* Generate new types. */
3969 create_new_types ();
3972 /* Create new global variables. */
3973 create_new_global_vars ();
3974 dump_new_vars (new_global_vars
);
3976 /* Decompose structures for each function separately. */
3979 /* Free auxiliary data collected for global variables. */
3980 free_new_vars_htab (new_global_vars
);
3983 /* Free all auxiliary data used by this optimization. */
3986 free_data_structs (void)
3989 free_alloc_sites ();
3992 /* Perform structure decomposition (peeling). */
3995 reorg_structs (void)
3999 /* Collect structure types. */
4000 collect_structures ();
4002 /* Collect structure allocation sites. */
4003 collect_allocation_sites ();
4005 /* Collect structure accesses. */
4006 collect_data_accesses ();
4008 /* We transform only hot structures. */
4009 exclude_cold_structs ();
4012 /* Decompose structures into substructures, i.e. clusters. */
4016 /* Do the actual transformation for each structure
4017 from the structures hashtable. */
4020 /* Free all auxiliary data used by this optimization. */
4021 free_data_structs ();
4024 /* Struct-reorg optimization entry point function. */
4027 reorg_structs_drive (void)
4033 /* Struct-reorg optimization gate function. */
4036 struct_reorg_gate (void)
4038 return flag_ipa_struct_reorg
&& flag_whole_program
4042 struct simple_ipa_opt_pass pass_ipa_struct_reorg
=
4046 "ipa_struct_reorg", /* name */
4047 struct_reorg_gate
, /* gate */
4048 reorg_structs_drive
, /* execute */
4051 0, /* static_pass_number */
4052 TV_INTEGRATION
, /* tv_id */
4053 0, /* properties_required */
4054 0, /* properties_provided */
4055 0, /* properties_destroyed */
4056 TODO_verify_ssa
, /* todo_flags_start */
4057 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */