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)
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
;
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
) || (!s1
&& s0
));
1256 str
= s0
? VEC_index (structure
, structures
, str0
):
1257 VEC_index (structure
, structures
, str1
);
1258 arg
= s0
? arg0
: arg1
;
1261 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1265 new_arg
= find_new_var_of_type (arg
, type
);
1266 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1270 /* Create a new general access to replace original access ACC
1271 for structure type NEW_TYPE. */
1274 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1276 tree old_stmt
= acc
->stmt
;
1278 tree new_stmt
= unshare_expr (old_stmt
);
1282 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1285 tree new_var
= find_new_var_of_type (var
, new_type
);
1288 gcc_assert (new_var
);
1289 finalize_var_creation (new_var
);
1291 if (TREE_CODE (new_stmt
) == GIMPLE_MODIFY_STMT
)
1294 lhs
= GIMPLE_STMT_OPERAND (new_stmt
, 0);
1295 rhs
= GIMPLE_STMT_OPERAND (new_stmt
, 1);
1297 if (TREE_CODE (lhs
) == SSA_NAME
)
1298 lhs
= SSA_NAME_VAR (lhs
);
1299 if (TREE_CODE (rhs
) == SSA_NAME
)
1300 rhs
= SSA_NAME_VAR (rhs
);
1302 /* It can happen that rhs is a constructor.
1303 Then we have to replace it to be of new_type. */
1304 if (TREE_CODE (rhs
) == CONSTRUCTOR
)
1306 /* Dealing only with empty constructors right now. */
1307 gcc_assert (VEC_empty (constructor_elt
,
1308 CONSTRUCTOR_ELTS (rhs
)));
1309 rhs
= build_constructor (new_type
, 0);
1310 GIMPLE_STMT_OPERAND (new_stmt
, 1) = rhs
;
1314 GIMPLE_STMT_OPERAND (new_stmt
, 0) = new_var
;
1315 else if (rhs
== var
)
1316 GIMPLE_STMT_OPERAND (new_stmt
, 1) = new_var
;
1319 pos
= find_pos_in_stmt (new_stmt
, var
);
1326 pos
= find_pos_in_stmt (new_stmt
, var
);
1332 finalize_stmt (new_stmt
);
1336 /* For each new type in STR this function creates new general accesses
1337 corresponding to the original access ACC. */
1340 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1343 tree stmt
= acc
->stmt
;
1346 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1350 new_stmt
= create_general_new_stmt (acc
, type
);
1351 insert_after_stmt (stmt
, new_stmt
);
1355 /* This function creates a new general access of structure STR
1356 to replace the access ACC. */
1359 create_new_general_access (struct access_site
*acc
, d_str str
)
1361 tree stmt
= acc
->stmt
;
1362 switch (TREE_CODE (stmt
))
1365 create_new_stmts_for_cond_expr (stmt
);
1369 create_new_stmts_for_general_acc (acc
, str
);
1373 /* Auxiliary data for creation of accesses. */
1374 struct create_acc_data
1381 /* This function creates a new general access, defined by SLOT.
1382 DATA is a pointer to create_acc_data structure. */
1385 create_new_acc (void **slot
, void *data
)
1387 struct access_site
*acc
= *(struct access_site
**) slot
;
1388 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1389 d_str str
= ((struct create_acc_data
*)data
)->str
;
1391 if (bb_for_stmt (acc
->stmt
) == bb
)
1392 create_new_general_access (acc
, str
);
1396 /* This function creates a new field access, defined by SLOT.
1397 DATA is a pointer to create_acc_data structure. */
1400 create_new_field_acc (void **slot
, void *data
)
1402 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1403 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1404 d_str str
= ((struct create_acc_data
*)data
)->str
;
1405 int i
= ((struct create_acc_data
*)data
)->field_index
;
1407 if (bb_for_stmt (f_acc
->stmt
) == bb
)
1408 create_new_field_access (f_acc
, str
->fields
[i
]);
1412 /* This function creates new accesses for the structure
1413 type STR in basic block BB. */
1416 create_new_accs_for_struct (d_str str
, basic_block bb
)
1419 struct create_acc_data dt
;
1423 dt
.field_index
= -1;
1425 for (i
= 0; i
< str
->num_fields
; i
++)
1429 if (str
->fields
[i
].acc_sites
)
1430 htab_traverse (str
->fields
[i
].acc_sites
,
1431 create_new_field_acc
, &dt
);
1434 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1437 /* This function inserts new variables from new_var,
1438 defined by SLOT, into varpool. */
1441 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1443 new_var n_var
= *(new_var
*) slot
;
1447 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1448 insert_global_to_varpool (var
);
1452 /* This function prints a field access site, defined by SLOT. */
1455 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1457 struct field_access_site
*f_acc
=
1458 *(struct field_access_site
**) slot
;
1460 fprintf(dump_file
, "\n");
1462 print_generic_stmt (dump_file
, f_acc
->stmt
, 0);
1463 if (f_acc
->ref_def_stmt
)
1464 print_generic_stmt (dump_file
, f_acc
->ref_def_stmt
, 0);
1465 if (f_acc
->cast_stmt
)
1466 print_generic_stmt (dump_file
, f_acc
->cast_stmt
, 0);
1470 /* Print field accesses from hashtable F_ACCS. */
1473 dump_field_acc_sites (htab_t f_accs
)
1479 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1482 /* Hash value for fallocs_t. */
1485 malloc_hash (const void *x
)
1487 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1490 /* This function returns nonzero if function of func_alloc_sites' X
1494 malloc_eq (const void *x
, const void *y
)
1496 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1499 /* This function is a callback for traversal over a structure accesses.
1500 It frees an access represented by SLOT. */
1503 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1505 struct access_site
* acc
= *(struct access_site
**) slot
;
1507 VEC_free (tree
, heap
, acc
->vars
);
1512 /* This is a callback function for traversal over field accesses.
1513 It frees a field access represented by SLOT. */
1516 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1518 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1524 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1525 if it is not there yet. */
1528 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1536 type
= TYPE_MAIN_VARIANT (type
);
1538 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1539 if (is_equal_types (t
, type
))
1542 if (i
== VEC_length (tree
, *unsuitable_types
))
1543 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1546 /* Given a type TYPE, this function returns the name of the type. */
1549 get_type_name (tree type
)
1551 if (! TYPE_NAME (type
))
1554 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1555 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1556 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1557 && DECL_NAME (TYPE_NAME (type
)))
1558 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1563 /* This function is a temporary hack to overcome the types problem.
1564 When several compilation units are compiled together
1565 with -combine, the TYPE_MAIN_VARIANT of the same type
1566 can appear differently in different compilation units.
1567 Therefore this function first compares type names.
1568 If there are no names, structure bodies are recursively
1572 is_equal_types (tree type1
, tree type2
)
1574 const char * name1
,* name2
;
1576 if ((!type1
&& type2
)
1577 ||(!type2
&& type1
))
1580 if (!type1
&& !type2
)
1583 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1589 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1592 name1
= get_type_name (type1
);
1593 name2
= get_type_name (type2
);
1595 if (name1
&& name2
&& !strcmp (name1
, name2
))
1598 if (name1
&& name2
&& strcmp (name1
, name2
))
1601 switch (TREE_CODE (type1
))
1604 case REFERENCE_TYPE
:
1606 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1612 case QUAL_UNION_TYPE
:
1616 /* Compare fields of struture. */
1617 for (field1
= TYPE_FIELDS (type1
); field1
;
1618 field1
= TREE_CHAIN (field1
))
1620 tree field2
= find_field_in_struct_1 (type2
, field1
);
1630 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1631 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1639 tree max1
, min1
, max2
, min2
;
1641 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1644 d1
= TYPE_DOMAIN (type1
);
1645 d2
= TYPE_DOMAIN (type2
);
1650 max1
= TYPE_MAX_VALUE (d1
);
1651 max2
= TYPE_MAX_VALUE (d2
);
1652 min1
= TYPE_MIN_VALUE (d1
);
1653 min2
= TYPE_MIN_VALUE (d2
);
1655 if (max1
&& max2
&& min1
&& min2
1656 && TREE_CODE (max1
) == TREE_CODE (max2
)
1657 && TREE_CODE (max1
) == INTEGER_CST
1658 && TREE_CODE (min1
) == TREE_CODE (min2
)
1659 && TREE_CODE (min1
) == INTEGER_CST
1660 && tree_int_cst_equal (max1
, max2
)
1661 && tree_int_cst_equal (min1
, min2
))
1673 /* This function free non-field accesses from hashtable ACCS. */
1676 free_accesses (htab_t accs
)
1679 htab_traverse (accs
, free_accs
, NULL
);
1683 /* This function free field accesses hashtable F_ACCS. */
1686 free_field_accesses (htab_t f_accs
)
1689 htab_traverse (f_accs
, free_field_accs
, NULL
);
1690 htab_delete (f_accs
);
1693 /* Update call graph with new edge generated by new MALLOC_STMT.
1694 The edge origin is CONTEXT function. */
1697 update_cgraph_with_malloc_call (tree malloc_stmt
, tree context
)
1700 struct cgraph_node
*src
, *dest
;
1701 tree malloc_fn_decl
;
1706 call_expr
= get_call_expr_in (malloc_stmt
);
1707 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1709 src
= cgraph_node (context
);
1710 dest
= cgraph_node (malloc_fn_decl
);
1711 cgraph_create_edge (src
, dest
, malloc_stmt
,
1712 0, 0, bb_for_stmt (malloc_stmt
)->loop_depth
);
1715 /* This function generates set of statements required
1716 to allocate number NUM of structures of type NEW_TYPE.
1717 The statements are stored in NEW_STMTS. The statement that contain
1718 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1721 create_new_malloc (tree malloc_stmt
, tree new_type
, tree
*new_stmts
, tree num
)
1723 tree new_malloc_size
;
1724 tree call_expr
, malloc_fn_decl
;
1725 tree new_stmt
, malloc_res
;
1726 tree call_stmt
, final_stmt
;
1729 gcc_assert (num
&& malloc_stmt
&& new_type
);
1730 *new_stmts
= alloc_stmt_list ();
1732 /* Generate argument to malloc as multiplication of num
1733 and size of new_type. */
1734 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1735 append_to_statement_list (new_stmt
, new_stmts
);
1737 /* Generate new call for malloc. */
1738 malloc_res
= create_tmp_var (ptr_type_node
, NULL
);
1741 add_referenced_var (malloc_res
);
1743 call_expr
= get_call_expr_in (malloc_stmt
);
1744 malloc_fn_decl
= get_callee_fndecl (call_expr
);
1745 call_expr
= build_call_expr (malloc_fn_decl
, 1, new_malloc_size
);
1746 call_stmt
= build_gimple_modify_stmt (malloc_res
, call_expr
);
1747 finalize_stmt_and_append (new_stmts
, call_stmt
);
1749 /* Create new cast statement. */
1750 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1751 gcc_assert (final_stmt
);
1752 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1753 append_to_statement_list (new_stmt
, new_stmts
);
1758 /* This function returns a tree representing
1759 the number of instances of structure STR_DECL allocated
1760 by allocation STMT. If new statments are generated,
1761 they are filled into NEW_STMTS_P. */
1764 gen_num_of_structs_in_malloc (tree stmt
, tree str_decl
, tree
*new_stmts_p
)
1766 call_expr_arg_iterator iter
;
1770 HOST_WIDE_INT struct_size_int
;
1775 /* Get malloc argument. */
1776 call_expr
= get_call_expr_in (stmt
);
1780 arg
= first_call_expr_arg (call_expr
, &iter
);
1782 if (TREE_CODE (arg
) != SSA_NAME
1783 && !TREE_CONSTANT (arg
))
1786 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1787 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1789 gcc_assert (struct_size
);
1791 if (TREE_CODE (arg
) == SSA_NAME
)
1795 if (is_result_of_mult (arg
, &num
, struct_size
))
1798 num
= create_tmp_var (integer_type_node
, NULL
);
1801 add_referenced_var (num
);
1803 if (exact_log2 (struct_size_int
) == -1)
1804 div_stmt
= build_gimple_modify_stmt (num
,
1805 build2 (TRUNC_DIV_EXPR
,
1810 tree C
= build_int_cst (integer_type_node
,
1811 exact_log2 (struct_size_int
));
1814 build_gimple_modify_stmt (num
, build2 (RSHIFT_EXPR
,
1818 *new_stmts_p
= alloc_stmt_list ();
1819 append_to_statement_list (div_stmt
,
1821 finalize_stmt (div_stmt
);
1825 if (CONSTANT_CLASS_P (arg
)
1826 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1827 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1832 /* This function is a callback for traversal on new_var's hashtable.
1833 SLOT is a pointer to new_var. This function prints to dump_file
1834 an original variable and all new variables from the new_var
1835 pointed by *SLOT. */
1838 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1840 new_var n_var
= *(new_var
*) slot
;
1845 var_type
= get_type_of_var (n_var
->orig_var
);
1847 fprintf (dump_file
, "\nOrig var: ");
1848 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1849 fprintf (dump_file
, " of type ");
1850 print_generic_expr (dump_file
, var_type
, 0);
1851 fprintf (dump_file
, "\n");
1854 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1856 var_type
= get_type_of_var (var
);
1858 fprintf (dump_file
, " ");
1859 print_generic_expr (dump_file
, var
, 0);
1860 fprintf (dump_file
, " of type ");
1861 print_generic_expr (dump_file
, var_type
, 0);
1862 fprintf (dump_file
, "\n");
1867 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1870 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1873 DECL_ARTIFICIAL (new_decl
) = 1;
1874 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1875 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1876 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1877 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1878 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1879 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1880 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1882 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1884 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1885 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1889 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1890 the same way as a structure type is wrapped in DECL.
1891 It returns the generated type. */
1894 gen_struct_type (tree decl
, tree new_str_type
)
1896 tree type_orig
= get_type_of_var (decl
);
1897 tree new_type
= new_str_type
;
1898 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1900 type_wrapper_t
*wr_p
;
1902 while (POINTER_TYPE_P (type_orig
)
1903 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1905 if (POINTER_TYPE_P (type_orig
))
1908 wr
.domain
= NULL_TREE
;
1910 else if (TREE_CODE (type_orig
) == ARRAY_TYPE
)
1913 wr
.domain
= TYPE_DOMAIN (type_orig
);
1915 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1916 type_orig
= TREE_TYPE (type_orig
);
1919 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1921 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1923 if (wr_p
->wrap
) /* Array. */
1924 new_type
= build_array_type (new_type
, wr_p
->domain
);
1926 new_type
= build_pointer_type (new_type
);
1928 VEC_pop (type_wrapper_t
, wrapper
);
1931 VEC_free (type_wrapper_t
, heap
, wrapper
);
1935 /* This function generates and returns new variable name based on
1936 ORIG_DECL name, combined with index I.
1937 The form of the new name is <orig_name>.<I> . */
1940 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1942 const char *old_name
;
1946 if (!DECL_NAME (orig_decl
)
1947 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1950 /* If the original variable has a name, create an
1951 appropriate new name for the new variable. */
1953 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1954 prefix
= alloca (strlen (old_name
) + 1);
1955 strcpy (prefix
, old_name
);
1956 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1957 return get_identifier (new_name
);
1960 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1963 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1967 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1968 htab_hash_pointer (new_node
->orig_var
),
1973 /* This function creates and returns new_var_data node
1974 with empty new_vars and orig_var equal to VAR. */
1977 create_new_var_node (tree var
, d_str str
)
1981 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1982 node
->orig_var
= var
;
1983 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1987 /* Check whether the type of VAR is potential candidate for peeling.
1988 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1989 candidate type. If VAR is initialized, the type of VAR will be added
1990 to UNSUITABLE_TYPES. */
1993 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
1996 bool initialized
= false;
2003 /* There is no support of initialized vars. */
2004 if (TREE_CODE (var
) == VAR_DECL
2005 && DECL_INITIAL (var
) != NULL_TREE
)
2008 type
= get_type_of_var (var
);
2012 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2013 if (TREE_CODE (type
) != RECORD_TYPE
)
2017 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2021 fprintf (dump_file
, "The type ");
2022 print_generic_expr (dump_file
, type
, 0);
2023 fprintf (dump_file
, " is initialized...Excluded.");
2025 add_unsuitable_type (unsuitable_types
, type
);
2035 /* Hash value for field_access_site. */
2038 field_acc_hash (const void *x
)
2040 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2043 /* This function returns nonzero if stmt of field_access_site X
2047 field_acc_eq (const void *x
, const void *y
)
2049 return ((const struct field_access_site
*)x
)->stmt
== (const_tree
)y
;
2052 /* This function prints an access site, defined by SLOT. */
2055 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2057 struct access_site
*acc
= *(struct access_site
**) slot
;
2061 fprintf(dump_file
, "\n");
2063 print_generic_stmt (dump_file
, acc
->stmt
, 0);
2064 fprintf(dump_file
, " : ");
2066 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2068 print_generic_expr (dump_file
, var
, 0);
2069 fprintf(dump_file
, ", ");
2074 /* This function frees memory allocated for strcuture clusters,
2075 starting from CLUSTER. */
2078 free_struct_cluster (struct field_cluster
* cluster
)
2082 if (cluster
->fields_in_cluster
)
2083 sbitmap_free (cluster
->fields_in_cluster
);
2084 if (cluster
->sibling
)
2085 free_struct_cluster (cluster
->sibling
);
2090 /* Free all allocated memory under the structure node pointed by D_NODE. */
2093 free_data_struct (d_str d_node
)
2102 fprintf (dump_file
, "\nRemoving data structure \"");
2103 print_generic_expr (dump_file
, d_node
->decl
, 0);
2104 fprintf (dump_file
, "\" from data_struct_list.");
2107 /* Free all space under d_node. */
2110 for (i
= 0; i
< d_node
->num_fields
; i
++)
2111 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2112 free (d_node
->fields
);
2116 free_accesses (d_node
->accs
);
2118 if (d_node
->struct_clustering
)
2119 free_struct_cluster (d_node
->struct_clustering
);
2121 if (d_node
->new_types
)
2122 VEC_free (tree
, heap
, d_node
->new_types
);
2125 /* This function creates new general and field accesses in BB. */
2128 create_new_accesses_in_bb (basic_block bb
)
2133 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2134 create_new_accs_for_struct (str
, bb
);
2137 /* This function adds allocation sites for peeled structures.
2138 M_DATA is vector of allocation sites of function CONTEXT. */
2141 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2147 VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2149 tree stmt
= call
->stmt
;
2150 d_str str
= call
->str
;
2152 tree new_stmts
= NULL_TREE
;
2153 tree last_stmt
= get_final_alloc_stmt (stmt
);
2157 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2160 last_stmt
= tsi_stmt (tsi_last (new_stmts
));
2161 insert_after_stmt (last_stmt
, new_stmts
);
2164 /* Generate an allocation sites for each new structure type. */
2166 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2168 tree new_malloc_stmt
= NULL_TREE
;
2169 tree last_stmt_tmp
= NULL_TREE
;
2171 new_stmts
= NULL_TREE
;
2172 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2173 last_stmt_tmp
= tsi_stmt (tsi_last (new_stmts
));
2174 insert_after_stmt (last_stmt
, new_stmts
);
2175 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2176 last_stmt
= last_stmt_tmp
;
2181 /* This function prints new variables from hashtable
2182 NEW_VARS_HTAB to dump_file. */
2185 dump_new_vars (htab_t new_vars_htab
)
2191 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2194 /* Given an original variable ORIG_DECL of structure type STR,
2195 this function generates new variables of the types defined
2196 by STR->new_type. Generated types are saved in new_var node NODE.
2197 ORIG_DECL should has VAR_DECL tree_code. */
2200 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2206 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2208 tree new_decl
= NULL
;
2211 new_name
= gen_var_name (orig_decl
, i
);
2212 type
= gen_struct_type (orig_decl
, type
);
2214 if (is_global_var (orig_decl
))
2215 new_decl
= build_decl (VAR_DECL
, new_name
, type
);
2218 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2219 new_decl
= create_tmp_var (type
, name
);
2222 copy_decl_attributes (new_decl
, orig_decl
);
2223 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2227 /* This function creates new variables to
2228 substitute the original variable VAR_DECL and adds
2229 them to the new_var's hashtable NEW_VARS_HTAB. */
2232 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2239 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2242 if (!is_candidate (var_decl
, &type
, NULL
))
2245 i
= find_structure (type
);
2246 if (i
== VEC_length (structure
, structures
))
2249 str
= VEC_index (structure
, structures
, i
);
2250 node
= create_new_var_node (var_decl
, str
);
2251 create_new_var_1 (var_decl
, str
, node
);
2252 add_to_new_vars_htab (node
, new_vars_htab
);
2255 /* Hash value for new_var. */
2258 new_var_hash (const void *x
)
2260 return htab_hash_pointer (((const_new_var
)x
)->orig_var
);
2263 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2266 new_var_eq (const void *x
, const void *y
)
2268 return ((const_new_var
)x
)->orig_var
== (const_tree
)y
;
2271 /* This function check whether a structure type represented by STR
2272 escapes due to ipa-type-escape analysis. If yes, this type is added
2273 to UNSUITABLE_TYPES vector. */
2276 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2278 tree type
= str
->decl
;
2280 if (!ipa_type_escape_type_contained_p (type
))
2284 fprintf (dump_file
, "\nEscaping type is ");
2285 print_generic_expr (dump_file
, type
, 0);
2287 add_unsuitable_type (unsuitable_types
, type
);
2291 /* Hash value for access_site. */
2294 acc_hash (const void *x
)
2296 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2299 /* Return nonzero if stmt of access_site X is equal to Y. */
2302 acc_eq (const void *x
, const void *y
)
2304 return ((const struct access_site
*)x
)->stmt
== (const_tree
)y
;
2307 /* Given a structure declaration STRUCT_DECL, and number of fields
2308 in the structure NUM_FIELDS, this function creates and returns
2309 corresponding field_entry's. */
2311 static struct field_entry
*
2312 get_fields (tree struct_decl
, int num_fields
)
2314 struct field_entry
*list
;
2315 tree t
= TYPE_FIELDS (struct_decl
);
2319 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2321 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2322 if (TREE_CODE (t
) == FIELD_DECL
)
2324 list
[idx
].index
= idx
;
2326 list
[idx
].acc_sites
=
2327 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2328 list
[idx
].count
= 0;
2329 list
[idx
].field_mapping
= NULL_TREE
;
2335 /* Print non-field accesses from hashtable ACCS of structure. */
2338 dump_access_sites (htab_t accs
)
2344 htab_traverse (accs
, dump_acc
, NULL
);
2347 /* This function removes the structure with index I from structures vector. */
2350 remove_structure (unsigned i
)
2354 if (i
>= VEC_length (structure
, structures
))
2357 str
= VEC_index (structure
, structures
, i
);
2358 free_data_struct (str
);
2359 VEC_ordered_remove (structure
, structures
, i
);
2362 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2363 COND_STNT is a condition statement to check. */
2366 is_safe_cond_expr (tree cond_stmt
)
2370 unsigned str0
, str1
;
2372 unsigned length
= VEC_length (structure
, structures
);
2374 tree cond
= COND_EXPR_COND (cond_stmt
);
2376 if (TREE_CODE (cond
) != EQ_EXPR
2377 && TREE_CODE (cond
) != NE_EXPR
)
2380 if (TREE_CODE_LENGTH (TREE_CODE (cond
)) != 2)
2383 arg0
= TREE_OPERAND (cond
, 0);
2384 arg1
= TREE_OPERAND (cond
, 1);
2386 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2387 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2389 s0
= (str0
!= length
) ? true : false;
2390 s1
= (str1
!= length
) ? true : false;
2392 if (!((!s0
&& s1
) || (!s1
&& s0
)))
2398 /* This function excludes statements, that are
2399 part of allocation sites or field accesses, from the
2400 hashtable of general accesses. SLOT represents general
2401 access that will be checked. DATA is a pointer to
2402 exclude_data structure. */
2405 exclude_from_accs (void **slot
, void *data
)
2407 struct access_site
*acc
= *(struct access_site
**) slot
;
2408 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2409 d_str str
= ((struct exclude_data
*)data
)->str
;
2411 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2412 || is_part_of_field_access (acc
->stmt
, str
))
2414 VEC_free (tree
, heap
, acc
->vars
);
2416 htab_clear_slot (str
->accs
, slot
);
2421 /* Callback function for walk_tree called from collect_accesses_in_bb
2422 function. DATA is the statement which is analyzed. */
2425 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2427 tree stmt
= (tree
) data
;
2433 switch (TREE_CODE (t
))
2435 case GIMPLE_MODIFY_STMT
:
2437 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
2438 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
2440 walk_tree (&lhs
, get_stmt_accesses
, data
, NULL
);
2441 walk_tree (&rhs
, get_stmt_accesses
, data
, NULL
);
2448 tree var
= TREE_OPERAND(t
, 0);
2449 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2450 unsigned i
= find_structure (type
);
2452 if (i
!= VEC_length (structure
, structures
))
2456 fprintf (dump_file
, "\nThe type ");
2457 print_generic_expr (dump_file
, type
, 0);
2458 fprintf (dump_file
, " has bitfield.");
2460 remove_structure (i
);
2467 tree ref
= TREE_OPERAND (t
, 0);
2468 tree field_decl
= TREE_OPERAND (t
, 1);
2471 if ((TREE_CODE (ref
) == INDIRECT_REF
2472 || TREE_CODE (ref
) == ARRAY_REF
2473 || TREE_CODE (ref
) == VAR_DECL
)
2474 && TREE_CODE (field_decl
) == FIELD_DECL
)
2476 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2477 unsigned i
= find_structure (type
);
2479 if (i
!= VEC_length (structure
, structures
))
2481 d_str str
= VEC_index (structure
, structures
, i
);
2482 struct field_entry
* field
=
2483 find_field_in_struct (str
, field_decl
);
2487 struct field_access_site
*acc
= make_field_acc_node ();
2494 acc
->field_decl
= field_decl
;
2496 /* Check whether the access is of the form
2497 we can deal with. */
2498 if (!decompose_access (str
->decl
, acc
))
2502 fprintf (dump_file
, "\nThe type ");
2503 print_generic_expr (dump_file
, type
, 0);
2505 " has complicate access in statement ");
2506 print_generic_stmt (dump_file
, stmt
, 0);
2509 remove_structure (i
);
2514 /* Increase count of field. */
2515 basic_block bb
= bb_for_stmt (stmt
);
2516 field
->count
+= bb
->count
;
2518 /* Add stmt to the acc_sites of field. */
2519 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2531 tree op0
= TREE_OPERAND (t
, 0);
2532 tree op1
= TREE_OPERAND (t
, 1);
2534 walk_tree (&op0
, get_stmt_accesses
, data
, NULL
);
2535 walk_tree (&op1
, get_stmt_accesses
, data
, NULL
);
2542 tree cond
= COND_EXPR_COND (t
);
2544 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2546 tree t
= TREE_OPERAND (cond
, i
);
2549 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2560 if (TREE_CODE (t
) == SSA_NAME
)
2561 t
= SSA_NAME_VAR (t
);
2563 i
= find_structure (strip_type (get_type_of_var (t
)));
2564 if (i
!= VEC_length (structure
, structures
))
2568 str
= VEC_index (structure
, structures
, i
);
2569 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2577 /* It was checked as part of stage1 that structures
2578 to be transformed cannot be passed as parameters of functions. */
2590 /* Free structures hashtable. */
2593 free_structures (void)
2598 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2599 free_data_struct (str
);
2601 VEC_free (structure
, heap
, structures
);
2605 /* This function is a callback for traversal over new_var's hashtable.
2606 SLOT is a pointer to new_var. This function frees memory allocated
2607 for new_var and pointed by *SLOT. */
2610 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2612 new_var n_var
= *(new_var
*) slot
;
2614 /* Free vector of new_vars. */
2615 VEC_free (tree
, heap
, n_var
->new_vars
);
2620 /* Free new_vars hashtable NEW_VARS_HTAB. */
2623 free_new_vars_htab (htab_t new_vars_htab
)
2626 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2627 htab_delete (new_vars_htab
);
2628 new_vars_htab
= NULL
;
2631 /* This function creates new general and field accesses that appear in cfun. */
2634 create_new_accesses_for_func (void)
2638 FOR_EACH_BB_FN (bb
, cfun
)
2639 create_new_accesses_in_bb (bb
);
2642 /* Create new allocation sites for the function represented by NODE. */
2645 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2647 fallocs_t fallocs
= get_fallocs (node
->decl
);
2650 create_new_alloc_sites (fallocs
, node
->decl
);
2653 /* For each local variable of structure type from the vector of structures
2654 this function generates new variable(s) to replace it. */
2657 create_new_local_vars (void)
2660 referenced_var_iterator rvi
;
2662 new_local_vars
= htab_create (num_referenced_vars
,
2663 new_var_hash
, new_var_eq
, NULL
);
2665 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2667 if (!is_global_var (var
))
2668 create_new_var (var
, new_local_vars
);
2672 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2673 dump_new_vars (new_local_vars
);
2676 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2679 print_shift (unsigned HOST_WIDE_INT shift
)
2681 unsigned HOST_WIDE_INT sh
= shift
;
2684 fprintf (dump_file
, " ");
2687 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2690 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2691 struct field_entry
* fields
, int num_fields
)
2695 for (i
= 0; i
< num_fields
; i
++)
2696 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2697 fields
[i
].field_mapping
= new_type
;
2700 /* This functions builds structure with FIELDS,
2701 NAME and attributes similar to ORIG_STRUCT.
2702 It returns the newly created structure. */
2705 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2707 tree attributes
= NULL_TREE
;
2711 if (TYPE_ATTRIBUTES (orig_struct
))
2712 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2713 ref
= make_node (RECORD_TYPE
);
2714 TYPE_SIZE (ref
) = 0;
2715 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2716 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2717 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2719 DECL_CONTEXT (x
) = ref
;
2720 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2722 TYPE_FIELDS (ref
) = fields
;
2724 TYPE_NAME (ref
) = name
;
2729 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2730 of preparation for new structure building. NUM_FIELDS is a total
2731 number of fields in the structure. The function returns newly
2732 generated fields. */
2735 create_fields (struct field_cluster
* cluster
,
2736 struct field_entry
* fields
, int num_fields
)
2739 tree new_types
= NULL_TREE
;
2740 tree last
= NULL_TREE
;
2742 for (i
= 0; i
< num_fields
; i
++)
2743 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2745 tree new_decl
= unshare_expr (fields
[i
].decl
);
2748 new_types
= new_decl
;
2750 TREE_CHAIN (last
) = new_decl
;
2754 TREE_CHAIN (last
) = NULL_TREE
;
2759 /* This function creates a cluster name. The name is based on
2760 the original structure name, if it is present. It has a form:
2762 <original_struct_name>_sub.<CLUST_NUM>
2764 The original structure name is taken from the type of DECL.
2765 If an original structure name is not present, it's generated to be:
2769 The function returns identifier of the new cluster name. */
2772 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2774 const char * orig_name
= get_type_name (decl
);
2775 char * tmp_name
= NULL
;
2781 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2783 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2784 prefix
= alloca (len
+ 1);
2785 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2786 strlen (tmp_name
? tmp_name
: orig_name
));
2787 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2789 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2790 return get_identifier (new_name
);
2793 /* This function checks whether the structure STR has bitfields.
2794 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2797 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2799 tree type
= str
->decl
;
2802 for (i
= 0; i
< str
->num_fields
; i
++)
2803 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2805 add_unsuitable_type (unsuitable_types
, type
);
2808 fprintf (dump_file
, "\nType ");
2809 print_generic_expr (dump_file
, type
, 0);
2810 fprintf (dump_file
, "\nescapes due to bitfield ");
2811 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2817 /* This function adds to UNSUITABLE_TYPES those types that escape
2818 due to results of ipa-type-escpae analysis. See ipa-type-escpae.[c,h]. */
2821 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2826 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2827 check_type_escape (str
, unsuitable_types
);
2830 /* If a structure type is a return type of any function,
2831 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2834 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2836 struct cgraph_node
*c_node
;
2838 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2840 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2844 ret_t
= strip_type (ret_t
);
2845 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2847 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2850 fprintf (dump_file
, "\nThe type \"");
2851 print_generic_expr (dump_file
, ret_t
, 0);
2853 "\" is return type of function...Excluded.");
2860 /* This function looks for parameters of local functions
2861 which are of structure types, or derived from them (arrays
2862 of structures, pointers to structures, or their combinations).
2863 We are not handling peeling of such structures right now.
2864 The found structures types are added to UNSUITABLE_TYPES vector. */
2867 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2869 struct cgraph_node
*c_node
;
2871 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2872 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2874 tree fn
= c_node
->decl
;
2877 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2879 tree type
= TREE_TYPE (arg
);
2881 type
= strip_type (type
);
2882 if (TREE_CODE (type
) == RECORD_TYPE
)
2884 add_unsuitable_type (unsuitable_types
,
2885 TYPE_MAIN_VARIANT (type
));
2888 fprintf (dump_file
, "\nPointer to type \"");
2889 print_generic_expr (dump_file
, type
, 0);
2891 "\" is passed to local function...Excluded.");
2898 /* This function analyzes structure form of structures
2899 potential for transformation. If we are not capable to transform
2900 structure of some form, we remove it from the structures hashtable.
2901 Right now we cannot handle nested structs, when nesting is
2902 through any level of pointers or arrays.
2904 TBD: release these constrains in future.
2906 Note, that in this function we suppose that all structures
2907 in the program are members of the structures hashtable right now,
2908 without excluding escaping types. */
2911 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2915 for (i
= 0; i
< str
->num_fields
; i
++)
2917 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2919 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2921 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2922 add_unsuitable_type (unsuitable_types
, str
->decl
);
2925 fprintf (dump_file
, "\nType ");
2926 print_generic_expr (dump_file
, f_type
, 0);
2927 fprintf (dump_file
, " is a field in the structure ");
2928 print_generic_expr (dump_file
, str
->decl
, 0);
2929 fprintf (dump_file
, ". Escaping...");
2935 /* This function adds a structure TYPE to the vector of structures,
2936 if it's not already there. */
2939 add_structure (tree type
)
2941 struct data_structure node
;
2945 type
= TYPE_MAIN_VARIANT (type
);
2947 i
= find_structure (type
);
2949 if (i
!= VEC_length (structure
, structures
))
2952 num_fields
= fields_length (type
);
2954 node
.num_fields
= num_fields
;
2955 node
.fields
= get_fields (type
, num_fields
);
2956 node
.struct_clustering
= NULL
;
2957 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
2958 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
2961 VEC_safe_push (structure
, heap
, structures
, &node
);
2965 fprintf (dump_file
, "\nAdding data structure \"");
2966 print_generic_expr (dump_file
, type
, 0);
2967 fprintf (dump_file
, "\" to data_struct_list.");
2971 /* This function adds an allocation site to alloc_sites hashtable.
2972 The allocation site appears in STMT of function FN_DECL and
2973 allocates the structure represented by STR. */
2976 add_alloc_site (tree fn_decl
, tree stmt
, d_str str
)
2978 fallocs_t fallocs
= NULL
;
2979 alloc_site_t m_call
;
2985 (fallocs_t
) htab_find_with_hash (alloc_sites
,
2986 fn_decl
, htab_hash_pointer (fn_decl
));
2992 fallocs
= (fallocs_t
)
2993 xmalloc (sizeof (struct func_alloc_sites
));
2994 fallocs
->func
= fn_decl
;
2995 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
2996 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
2997 htab_hash_pointer (fn_decl
), INSERT
);
3000 VEC_safe_push (alloc_site_t
, heap
,
3001 fallocs
->allocs
, &m_call
);
3005 fprintf (dump_file
, "\nAdding stmt ");
3006 print_generic_stmt (dump_file
, stmt
, 0);
3007 fprintf (dump_file
, " to list of mallocs.");
3011 /* This function returns true if the result of STMT, that contains a call
3012 to an allocation function, is cast to one of the structure types.
3013 STMT should be of the form: T.2 = <alloc_func> (T.1);
3014 If true, I_P contains an index of an allocated structure.
3015 Otherwise I_P contains the length of the vector of structures. */
3018 is_alloc_of_struct (tree stmt
, unsigned *i_p
)
3024 final_stmt
= get_final_alloc_stmt (stmt
);
3029 /* final_stmt should be of the form:
3030 T.3 = (struct_type *) T.2; */
3032 if (TREE_CODE (final_stmt
) != GIMPLE_MODIFY_STMT
)
3035 lhs
= GIMPLE_STMT_OPERAND (final_stmt
, 0);
3037 type
= get_type_of_var (lhs
);
3042 if (!POINTER_TYPE_P (type
)
3043 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3046 *i_p
= find_structure (strip_type (type
));
3048 if (*i_p
== VEC_length (structure
, structures
))
3054 /* This function prints non-field and field accesses
3055 of the structure STR. */
3058 dump_accs (d_str str
)
3062 fprintf (dump_file
, "\nAccess sites of struct ");
3063 print_generic_expr (dump_file
, str
->decl
, 0);
3065 for (i
= 0; i
< str
->num_fields
; i
++)
3067 fprintf (dump_file
, "\nAccess site of field ");
3068 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3069 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3070 fprintf (dump_file
, ":\n");
3072 fprintf (dump_file
, "\nGeneral access sites\n");
3073 dump_access_sites (str
->accs
);
3076 /* This function checks whether an access statement, pointed by SLOT,
3077 is a condition we are capable to transform. If not, it removes
3078 the structure with index, represented by DATA, from the vector
3082 safe_cond_expr_check (void **slot
, void *data
)
3084 struct access_site
*acc
= *(struct access_site
**) slot
;
3086 if (TREE_CODE (acc
->stmt
) == COND_EXPR
)
3088 if (!is_safe_cond_expr (acc
->stmt
))
3092 fprintf (dump_file
, "\nUnsafe conditional statement ");
3093 print_generic_stmt (dump_file
, acc
->stmt
, 0);
3095 remove_structure (*(unsigned *) data
);
3101 /* This function excludes statements that are part of allocation sites and
3102 field accesses from the hashtable of general accesses of the structure
3103 type STR. Only accesses that belong to the function represented by
3104 NODE are treated. */
3107 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3109 struct exclude_data dt
;
3111 dt
.fn_decl
= node
->decl
;
3114 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3117 /* Collect accesses to the structure types that apear in basic bloack BB. */
3120 collect_accesses_in_bb (basic_block bb
)
3122 block_stmt_iterator bsi
;
3124 for (bsi
= bsi_start (bb
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
3126 tree stmt
= bsi_stmt (bsi
);
3128 /* In asm stmt we cannot always track the arguments,
3129 so we just give up. */
3130 if (TREE_CODE (stmt
) == ASM_EXPR
)
3136 walk_tree (&stmt
, get_stmt_accesses
, stmt
, NULL
);
3140 /* This function generates cluster substructure that cointains FIELDS.
3141 The cluster added to the set of clusters of the structure SRT. */
3144 gen_cluster (sbitmap fields
, d_str str
)
3146 struct field_cluster
*crr_cluster
= NULL
;
3149 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3150 crr_cluster
->sibling
= str
->struct_clustering
;
3151 str
->struct_clustering
= crr_cluster
;
3152 crr_cluster
->fields_in_cluster
= fields
;
3155 /* This function peels a field with the index I from the structure DS. */
3158 peel_field (int i
, d_str ds
)
3160 struct field_cluster
*crr_cluster
= NULL
;
3163 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3164 crr_cluster
->sibling
= ds
->struct_clustering
;
3165 ds
->struct_clustering
= crr_cluster
;
3166 crr_cluster
->fields_in_cluster
=
3167 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3168 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3169 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3172 /* This function calculates maximum field count in
3173 the structure STR. */
3176 get_max_field_count (d_str str
)
3181 for (i
= 0; i
< str
->num_fields
; i
++)
3182 if (str
->fields
[i
].count
> max
)
3183 max
= str
->fields
[i
].count
;
3188 /* Do struct-reorg transformation for individual function
3189 represented by NODE. All structure types relevant
3190 for this function are transformed. */
3193 do_reorg_for_func (struct cgraph_node
*node
)
3195 create_new_local_vars ();
3196 create_new_alloc_sites_for_func (node
);
3197 create_new_accesses_for_func ();
3198 update_ssa (TODO_update_ssa
);
3199 cleanup_tree_cfg ();
3201 /* Free auxiliary data representing local variables. */
3202 free_new_vars_htab (new_local_vars
);
3205 /* Print structure TYPE, its name, if it exists, and body.
3206 INDENT defines the level of indentation (similar
3207 to the option -i of indent command). SHIFT parameter
3208 defines a number of spaces by which a structure will
3209 be shifted right. */
3212 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3213 unsigned HOST_WIDE_INT shift
)
3215 const char *struct_name
;
3218 if (!type
|| !dump_file
)
3221 if (TREE_CODE (type
) != RECORD_TYPE
)
3223 print_generic_expr (dump_file
, type
, 0);
3227 print_shift (shift
);
3228 struct_name
= get_type_name (type
);
3229 fprintf (dump_file
, "struct ");
3231 fprintf (dump_file
, "%s\n",struct_name
);
3232 print_shift (shift
);
3233 fprintf (dump_file
, "{\n");
3235 for (field
= TYPE_FIELDS (type
); field
;
3236 field
= TREE_CHAIN (field
))
3238 unsigned HOST_WIDE_INT s
= indent
;
3239 tree f_type
= TREE_TYPE (field
);
3241 print_shift (shift
);
3243 fprintf (dump_file
, " ");
3244 dump_struct_type (f_type
, indent
, shift
+ indent
);
3245 fprintf(dump_file
, " ");
3246 print_generic_expr (dump_file
, field
, 0);
3247 fprintf(dump_file
, ";\n");
3249 print_shift (shift
);
3250 fprintf (dump_file
, "}\n");
3253 /* This function creates new structure types to replace original type,
3254 indicated by STR->decl. The names of the new structure types are
3255 derived from the original structure type. If the original structure
3256 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3259 create_new_type (d_str str
, int *str_num
)
3261 int cluster_num
= 0;
3263 struct field_cluster
*cluster
= str
->struct_clustering
;
3266 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3272 fields
= create_fields (cluster
, str
->fields
,
3274 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3276 update_fields_mapping (cluster
, new_type
,
3277 str
->fields
, str
->num_fields
);
3279 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3280 cluster
= cluster
->sibling
;
3285 /* This function is a callback for alloc_sites hashtable
3286 traversal. SLOT is a pointer to fallocs_t.
3287 This function frees memory pointed by *SLOT. */
3290 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3292 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3294 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3299 /* Remove structures collected in UNSUITABLE_TYPES
3300 from structures vector. */
3303 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3309 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3310 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3311 if (is_equal_types (str
->decl
, type
))
3313 remove_structure (i
);
3318 /* Exclude structure types with bitfields.
3319 We would not want to interfere with other optimizations
3320 that can be done in this case. The structure types with
3321 bitfields are added to UNSUITABLE_TYPES vector. */
3324 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3329 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3330 check_bitfields (str
, unsuitable_types
);
3333 /* This function checks three types of escape. A structure type escapes:
3335 1. if it's a type of parameter of a local function.
3336 2. if it's a type of function return value.
3337 3. if it escapes as a result of ipa-type-escape analysis.
3339 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3342 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3344 exclude_types_passed_to_local_func (unsuitable_types
);
3345 exclude_returned_types (unsuitable_types
);
3346 exclude_escaping_types_1 (unsuitable_types
);
3349 /* This function analyzes whether the form of
3350 structure is such that we are capable to transform it.
3351 Nested structures are checked here. Unsuitable structure
3352 types are added to UNSUITABLE_TYPE vector. */
3355 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3360 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3361 check_struct_form (str
, unsuitable_types
);
3364 /* This function looks for structure types instantiated in the program.
3365 The candidate types are added to the structures vector.
3366 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3369 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3373 struct varpool_node
*current_varpool
;
3374 struct cgraph_node
*c_node
;
3376 /* Check global variables. */
3377 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3379 var
= current_varpool
->decl
;
3380 if (is_candidate (var
, &type
, unsuitable_types
))
3381 add_structure (type
);
3384 /* Now add structures that are types of function parameters and
3386 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3388 enum availability avail
=
3389 cgraph_function_body_availability (c_node
);
3391 /* We need AVAIL_AVAILABLE for main function. */
3392 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3394 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3396 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3397 var
= TREE_CHAIN (var
))
3398 if (is_candidate (var
, &type
, unsuitable_types
))
3399 add_structure (type
);
3401 /* Check function local variables. */
3402 for (var_list
= fn
->unexpanded_var_list
; var_list
;
3403 var_list
= TREE_CHAIN (var_list
))
3405 var
= TREE_VALUE (var_list
);
3407 if (is_candidate (var
, &type
, unsuitable_types
))
3408 add_structure (type
);
3414 /* This function returns true if the program contains
3415 a call to user defined allocation function, or other
3416 functions that can interfere with struct-reorg optimizations. */
3419 program_redefines_malloc_p (void)
3421 struct cgraph_node
*c_node
;
3422 struct cgraph_node
*c_node2
;
3423 struct cgraph_edge
*c_edge
;
3428 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3430 fndecl
= c_node
->decl
;
3432 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3434 call_expr
= get_call_expr_in (c_edge
->call_stmt
);
3435 c_node2
= c_edge
->callee
;
3436 fndecl2
= c_node2
->decl
;
3439 const char * fname
= get_name (fndecl2
);
3441 if ((call_expr_flags (call_expr
) & ECF_MALLOC
) &&
3442 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
) &&
3443 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
) &&
3444 (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3447 /* Check that there is no __builtin_object_size,
3448 __builtin_offsetof, or realloc's in the program. */
3449 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3450 || !strcmp (fname
, "__builtin_offsetof")
3451 || !strcmp (fname
, "realloc"))
3460 /* In this function we assume that an allocation statement
3462 var = (type_cast) malloc (size);
3464 is converted into the following set of statements:
3468 T.3 = (type_cast) T.2;
3471 In this function we collect into alloc_sites the allocation
3472 sites of variables of structure types that are present
3473 in structures vector. */
3476 collect_alloc_sites (void)
3478 struct cgraph_node
*node
;
3479 struct cgraph_edge
*cs
;
3481 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3482 if (node
->analyzed
&& node
->decl
)
3484 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3486 tree stmt
= cs
->call_stmt
;
3490 tree call
= get_call_expr_in (stmt
);
3493 if (call
&& (decl
= get_callee_fndecl (call
))
3494 && TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
3498 if (is_alloc_of_struct (stmt
, &i
))
3500 /* We support only malloc now. */
3501 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3505 str
= VEC_index (structure
, structures
, i
);
3506 add_alloc_site (node
->decl
, stmt
, str
);
3513 "\nUnsupported allocation function ");
3514 print_generic_stmt (dump_file
, stmt
, 0);
3516 remove_structure (i
);
3525 /* Print collected accesses. */
3528 dump_accesses (void)
3536 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3540 /* This function checks whether the accesses of structures in condition
3541 expressions are of the kind we are capable to transform.
3542 If not, such structures are removed from the vector of structures. */
3545 check_cond_exprs (void)
3550 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3552 htab_traverse (str
->accs
, safe_cond_expr_check
, &i
);
3555 /* We exclude from non-field accesses of the structure
3556 all statements that will be treated as part of the structure
3557 allocation sites or field accesses. */
3560 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3565 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3566 exclude_alloc_and_field_accs_1 (str
, node
);
3569 /* This function collects accesses of the fields of the structures
3570 that appear at function FN. */
3573 collect_accesses_in_func (struct function
*fn
)
3580 /* Collect accesses for each basic blocks separately. */
3581 FOR_EACH_BB_FN (bb
, fn
)
3582 collect_accesses_in_bb (bb
);
3585 /* This function summarizes counts of the fields into the structure count. */
3588 sum_counts (d_str str
, gcov_type
*hotest
)
3593 for (i
= 0; i
< str
->num_fields
; i
++)
3597 fprintf (dump_file
, "\nCounter of field \"");
3598 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3599 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3600 str
->fields
[i
].count
);
3602 str
->count
+= str
->fields
[i
].count
;
3607 fprintf (dump_file
, "\nCounter of struct \"");
3608 print_generic_expr (dump_file
, str
->decl
, 0);
3609 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3612 if (str
->count
> *hotest
)
3613 *hotest
= str
->count
;
3616 /* This function peels the field into separate structure if it's
3617 sufficiently hot, i.e. if its count provides at least 90% of
3618 the maximum field count in the structure. */
3621 peel_hot_fields (d_str str
)
3623 gcov_type max_field_count
;
3624 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3627 sbitmap_ones (fields_left
);
3629 (gcov_type
) (get_max_field_count (str
)/100)*90;
3631 str
->struct_clustering
= NULL
;
3633 for (i
= 0; i
< str
->num_fields
; i
++)
3635 if (str
->count
>= max_field_count
)
3637 RESET_BIT (fields_left
, i
);
3638 peel_field (i
, str
);
3642 i
= sbitmap_first_set_bit (fields_left
);
3644 gen_cluster (fields_left
, str
);
3646 sbitmap_free (fields_left
);
3649 /* This function is a helper for do_reorg. It goes over
3650 functions in call graph and performs actual transformation
3656 struct cgraph_node
*node
;
3658 /* Initialize the default bitmap obstack. */
3659 bitmap_obstack_initialize (NULL
);
3661 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3662 if (node
->analyzed
&& node
->decl
&& !node
->next_clone
)
3664 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3665 current_function_decl
= node
->decl
;
3667 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3668 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3669 do_reorg_for_func (node
);
3670 free_dominance_info (CDI_DOMINATORS
);
3671 free_dominance_info (CDI_POST_DOMINATORS
);
3672 current_function_decl
= NULL
;
3679 /* This function creates new global struct variables.
3680 For each original variable, the set of new variables
3681 is created with the new structure types corresponding
3682 to the structure type of original variable.
3683 Only VAR_DECL variables are treated by this function. */
3686 create_new_global_vars (void)
3688 struct varpool_node
*current_varpool
;
3689 unsigned HOST_WIDE_INT i
;
3690 unsigned HOST_WIDE_INT varpool_size
= 0;
3692 for (i
= 0; i
< 2; i
++)
3695 new_global_vars
= htab_create (varpool_size
,
3696 new_var_hash
, new_var_eq
, NULL
);
3697 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3699 tree var_decl
= current_varpool
->decl
;
3701 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3706 create_new_var (var_decl
, new_global_vars
);
3710 if (new_global_vars
)
3711 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3714 /* Dump all new types generated by this optimization. */
3717 dump_new_types (void)
3726 fprintf (dump_file
, "\nThe following are the new types generated by"
3727 " this optimization:\n");
3729 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3733 fprintf (dump_file
, "\nFor type ");
3734 dump_struct_type (str
->decl
, 2, 0);
3735 fprintf (dump_file
, "\nthe number of new types is %d\n",
3736 VEC_length (tree
, str
->new_types
));
3738 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3739 dump_struct_type (type
, 2, 0);
3743 /* This function creates new types to replace old structure types. */
3746 create_new_types (void)
3752 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3753 create_new_type (str
, &str_num
);
3756 /* Free allocation sites hashtable. */
3759 free_alloc_sites (void)
3762 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3763 htab_delete (alloc_sites
);
3767 /* This function collects structures potential
3768 for peeling transformation, and inserts
3769 them into structures hashtable. */
3772 collect_structures (void)
3774 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3776 structures
= VEC_alloc (structure
, heap
, 32);
3778 /* If program contains user defined mallocs, we give up. */
3779 if (program_redefines_malloc_p ())
3782 /* Build data structures hashtable of all data structures
3784 build_data_structure (&unsuitable_types
);
3786 /* This function analyzes whether the form of
3787 structure is such that we are capable to transform it.
3788 Nested structures are checked here. */
3789 analyze_struct_form (&unsuitable_types
);
3791 /* This function excludes those structure types
3792 that escape compilation unit. */
3793 exclude_escaping_types (&unsuitable_types
);
3795 /* We do not want to change data layout of the structures with bitfields. */
3796 exclude_types_with_bit_fields (&unsuitable_types
);
3798 remove_unsuitable_types (unsuitable_types
);
3799 VEC_free (tree
, heap
, unsuitable_types
);
3802 /* Collect structure allocation sites. In case of arrays
3803 we have nothing to do. */
3806 collect_allocation_sites (void)
3808 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3809 collect_alloc_sites ();
3812 /* This function collects data accesses for the
3813 structures to be transformed. For each structure
3814 field it updates the count field in field_entry. */
3817 collect_data_accesses (void)
3819 struct cgraph_node
*c_node
;
3821 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3823 enum availability avail
= cgraph_function_body_availability (c_node
);
3825 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3827 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3829 if (!c_node
->next_clone
)
3830 collect_accesses_in_func (func
);
3831 exclude_alloc_and_field_accs (c_node
);
3835 check_cond_exprs ();
3836 /* Print collected accesses. */
3840 /* We do not bother to transform cold structures.
3841 Coldness of the structure is defined relatively
3842 to the highest structure count among the structures
3843 to be transformed. It's triggered by the compiler parameter
3845 --param struct-reorg-cold-struct-ratio=<value>
3847 where <value> ranges from 0 to 100. Structures with count ratios
3848 that are less than this parameter are considered to be cold. */
3851 exclude_cold_structs (void)
3853 gcov_type hotest
= 0;
3857 /* We summarize counts of fields of a structure into the structure count. */
3858 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3859 sum_counts (str
, &hotest
);
3861 /* Remove cold structures from structures vector. */
3862 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3863 if (str
->count
* 100 < (hotest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3867 fprintf (dump_file
, "\nThe structure ");
3868 print_generic_expr (dump_file
, str
->decl
, 0);
3869 fprintf (dump_file
, " is cold.");
3871 remove_structure (i
);
3875 /* This function decomposes original structure into substructures,
3884 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3885 peel_hot_fields (str
);
3889 /* Do the actual transformation for each structure
3890 from the structures hashtable. */
3895 /* Check that there is a work to do. */
3896 if (!VEC_length (structure
, structures
))
3899 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3906 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3907 VEC_length (structure
, structures
));
3911 /* Generate new types. */
3912 create_new_types ();
3915 /* Create new global variables. */
3916 create_new_global_vars ();
3917 dump_new_vars (new_global_vars
);
3919 /* Decompose structures for each function separately. */
3922 /* Free auxiliary data collected for global variables. */
3923 free_new_vars_htab (new_global_vars
);
3926 /* Free all auxiliary data used by this optimization. */
3929 free_data_structs (void)
3932 free_alloc_sites ();
3935 /* Perform structure decomposition (peeling). */
3938 reorg_structs (void)
3942 /* Collect structure types. */
3943 collect_structures ();
3945 /* Collect structure allocation sites. */
3946 collect_allocation_sites ();
3948 /* Collect structure accesses. */
3949 collect_data_accesses ();
3951 /* We transform only hot structures. */
3952 exclude_cold_structs ();
3955 /* Decompose structures into substructures, i.e. clusters. */
3959 /* Do the actual transformation for each structure
3960 from the structures hashtable. */
3963 /* Free all auxiliary data used by this optimization. */
3964 free_data_structs ();
3967 /* Struct-reorg optimization entry point function. */
3970 reorg_structs_drive (void)
3976 /* Struct-reorg optimization gate function. */
3979 struct_reorg_gate (void)
3981 return flag_ipa_struct_reorg
&& flag_whole_program
3985 struct tree_opt_pass pass_ipa_struct_reorg
=
3987 "ipa_struct_reorg", /* name */
3988 struct_reorg_gate
, /* gate */
3989 reorg_structs_drive
, /* execute */
3992 0, /* static_pass_number */
3993 TV_INTEGRATION
, /* tv_id */
3994 0, /* properties_required */
3995 0, /* properties_provided */
3996 0, /* properties_destroyed */
3997 TODO_verify_ssa
, /* todo_flags_start */
3998 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */