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"
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"
60 /* This optimization implements structure peeling.
62 For example, given a structure type:
70 it can be peeled into two structure types as follows:
72 typedef struct and typedef struct
78 or can be fully peeled:
95 When structure type is peeled all instances and their accesses
96 in the program are updated accordingly. For example, if there is
101 and structure type str_t was peeled into two structures str_t_0
102 and str_t_1 as it was shown above, then array A will be replaced
103 by two arrays as follows:
108 The field access of field a of element i of array A: A[i].a will be
109 replaced by an access to field a of element i of array A_0: A_0[i].a.
111 This optimization also supports dynamically allocated arrays.
112 If array of structures was allocated by malloc function:
114 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
116 the allocation site will be replaced to reflect new structure types:
118 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
119 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
121 The field access through the pointer p[i].a will be changed by p_0[i].a.
123 The goal of structure peeling is to improve spatial locality.
124 For example, if one of the fields of a structure is accessed frequently
127 for (i = 0; i < N; i++)
132 the allocation of field a of str_t contiguously in memory will
133 increase the chances of fetching the field from cache.
135 The analysis part of this optimization is based on the frequency of
136 field accesses, which are collected all over the program.
137 Then the fields with the frequencies that satisfy the following condition
138 get peeled out of the structure:
140 freq(f) > C * max_field_freq_in_struct
142 where max_field_freq_in_struct is the maximum field frequency
143 in the structure. C is a constant defining which portion of
144 max_field_freq_in_struct the fields should have in order to be peeled.
146 If profiling information is provided, it is used to calculate the
147 frequency of field accesses. Otherwise, the structure is fully peeled.
149 IPA type-escape analysis is used to determine when it is safe
152 The optimization is activated by flag -fipa-struct-reorg. */
154 /* New variables created by this optimization.
155 When doing struct peeling, each variable of
156 the original struct type will be replaced by
157 the set of new variables corresponding to
158 the new structure types. */
159 struct new_var_data
{
160 /* VAR_DECL for original struct type. */
162 /* Vector of new variables. */
163 VEC(tree
, heap
) *new_vars
;
166 typedef struct new_var_data
*new_var
;
167 typedef const struct new_var_data
*const_new_var
;
169 /* This structure represents allocation site of the structure. */
170 typedef struct alloc_site
176 DEF_VEC_O (alloc_site_t
);
177 DEF_VEC_ALLOC_O (alloc_site_t
, heap
);
179 /* Allocation sites that belong to the same function. */
180 struct func_alloc_sites
183 /* Vector of allocation sites for function. */
184 VEC (alloc_site_t
, heap
) *allocs
;
187 typedef struct func_alloc_sites
*fallocs_t
;
188 typedef const struct func_alloc_sites
*const_fallocs_t
;
190 /* All allocation sites in the program. */
191 htab_t alloc_sites
= NULL
;
193 /* New global variables. Generated once for whole program. */
194 htab_t new_global_vars
;
196 /* New local variables. Generated per-function. */
197 htab_t new_local_vars
;
199 /* Vector of structures to be transformed. */
200 typedef struct data_structure structure
;
201 DEF_VEC_O (structure
);
202 DEF_VEC_ALLOC_O (structure
, heap
);
203 VEC (structure
, heap
) *structures
;
205 /* Forward declarations. */
206 static bool is_equal_types (tree
, tree
);
208 /* Strip structure TYPE from pointers and arrays. */
211 strip_type (tree type
)
213 gcc_assert (TYPE_P (type
));
215 while (POINTER_TYPE_P (type
)
216 || TREE_CODE (type
) == ARRAY_TYPE
)
217 type
= TREE_TYPE (type
);
222 /* This function returns type of VAR. */
225 get_type_of_var (tree var
)
230 if (TREE_CODE (var
) == PARM_DECL
)
231 return DECL_ARG_TYPE (var
);
233 return TREE_TYPE (var
);
236 /* Set of actions we do for each newly generated STMT. */
239 finalize_stmt (gimple stmt
)
242 mark_symbols_for_renaming (stmt
);
245 /* This function finalizes STMT and appends it to the list STMTS. */
248 finalize_stmt_and_append (gimple_seq
*stmts
, gimple stmt
)
250 gimple_seq_add_stmt (stmts
, stmt
);
251 finalize_stmt (stmt
);
254 /* Given structure type SRT_TYPE and field FIELD,
255 this function is looking for a field with the same name
256 and type as FIELD in STR_TYPE. It returns it if found,
257 or NULL_TREE otherwise. */
260 find_field_in_struct_1 (tree str_type
, tree field
)
264 for (str_field
= TYPE_FIELDS (str_type
); str_field
;
265 str_field
= TREE_CHAIN (str_field
))
267 const char * str_field_name
;
268 const char * field_name
;
270 str_field_name
= IDENTIFIER_POINTER (DECL_NAME (str_field
));
271 field_name
= IDENTIFIER_POINTER (DECL_NAME (field
));
273 gcc_assert (str_field_name
);
274 gcc_assert (field_name
);
276 if (!strcmp (str_field_name
, field_name
))
278 /* Check field types. */
279 if (is_equal_types (TREE_TYPE (str_field
), TREE_TYPE (field
)))
287 /* Given a field declaration FIELD_DECL, this function
288 returns corresponding field entry in structure STR. */
290 static struct field_entry
*
291 find_field_in_struct (d_str str
, tree field_decl
)
295 tree field
= find_field_in_struct_1 (str
->decl
, field_decl
);
297 for (i
= 0; i
< str
->num_fields
; i
++)
298 if (str
->fields
[i
].decl
== field
)
299 return &(str
->fields
[i
]);
304 /* This function checks whether ARG is a result of multiplication
305 of some number by STRUCT_SIZE. If yes, the function returns true
306 and this number is filled into NUM. */
309 is_result_of_mult (tree arg
, tree
*num
, tree struct_size
)
311 gimple size_def_stmt
= SSA_NAME_DEF_STMT (arg
);
313 /* If the allocation statement was of the form
314 D.2229_10 = <alloc_func> (D.2228_9);
315 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
317 if (size_def_stmt
&& is_gimple_assign (size_def_stmt
))
319 tree lhs
= gimple_assign_lhs (size_def_stmt
);
321 /* We expect temporary here. */
322 if (!is_gimple_reg (lhs
))
325 if (gimple_assign_rhs_code (size_def_stmt
) == MULT_EXPR
)
327 tree arg0
= gimple_assign_rhs1 (size_def_stmt
);
328 tree arg1
= gimple_assign_rhs2 (size_def_stmt
);
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 struct_size
, op0
, op1
;
361 enum tree_code rhs_code
;
363 ref_var
= TREE_OPERAND (acc
->ref
, 0);
365 if (TREE_CODE (ref_var
) != SSA_NAME
)
368 acc
->ref_def_stmt
= SSA_NAME_DEF_STMT (ref_var
);
369 if (!(acc
->ref_def_stmt
)
370 || (gimple_code (acc
->ref_def_stmt
) != GIMPLE_ASSIGN
))
373 rhs_code
= gimple_assign_rhs_code (acc
->ref_def_stmt
);
375 if (rhs_code
!= PLUS_EXPR
376 && rhs_code
!= MINUS_EXPR
377 && rhs_code
!= POINTER_PLUS_EXPR
)
380 op0
= gimple_assign_rhs1 (acc
->ref_def_stmt
);
381 op1
= gimple_assign_rhs2 (acc
->ref_def_stmt
);
383 if (!is_array_access_through_pointer_and_index (rhs_code
, op0
, op1
,
384 &acc
->base
, &acc
->offset
,
389 before_cast
= SINGLE_SSA_TREE_OPERAND (acc
->cast_stmt
, SSA_OP_USE
);
391 before_cast
= acc
->offset
;
397 if (SSA_NAME_IS_DEFAULT_DEF (before_cast
))
400 struct_size
= TYPE_SIZE_UNIT (str_decl
);
402 if (!is_result_of_mult (before_cast
, &acc
->num
, struct_size
))
409 /* This function checks whether the access ACC of structure type STR
410 is of the form suitable for transformation. If yes, it returns true.
414 decompose_access (tree str_decl
, struct field_access_site
*acc
)
416 gcc_assert (acc
->ref
);
418 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
)
419 return decompose_indirect_ref_acc (str_decl
, acc
);
420 else if (TREE_CODE (acc
->ref
) == ARRAY_REF
)
422 else if (TREE_CODE (acc
->ref
) == VAR_DECL
)
428 /* This function creates empty field_access_site node. */
430 static inline struct field_access_site
*
431 make_field_acc_node (void)
433 int size
= sizeof (struct field_access_site
);
435 return (struct field_access_site
*) xcalloc (1, size
);
438 /* This function returns the structure field access, defined by STMT,
439 if it is already in hashtable of function accesses F_ACCS. */
441 static struct field_access_site
*
442 is_in_field_accs (gimple stmt
, htab_t f_accs
)
444 return (struct field_access_site
*)
445 htab_find_with_hash (f_accs
, stmt
, htab_hash_pointer (stmt
));
448 /* This function adds an access ACC to the hashtable
449 F_ACCS of field accesses. */
452 add_field_acc_to_acc_sites (struct field_access_site
*acc
,
457 gcc_assert (!is_in_field_accs (acc
->stmt
, f_accs
));
458 slot
= htab_find_slot_with_hash (f_accs
, acc
->stmt
,
459 htab_hash_pointer (acc
->stmt
),
464 /* This function adds the VAR to vector of variables of
465 an access site defined by statement STMT. If access entry
466 with statement STMT does not exist in hashtable of
467 accesses ACCS, this function creates it. */
470 add_access_to_acc_sites (gimple stmt
, tree var
, htab_t accs
)
472 struct access_site
*acc
;
474 acc
= (struct access_site
*)
475 htab_find_with_hash (accs
, stmt
, htab_hash_pointer (stmt
));
481 acc
= (struct access_site
*) xmalloc (sizeof (struct access_site
));
483 acc
->vars
= VEC_alloc (tree
, heap
, 10);
484 slot
= htab_find_slot_with_hash (accs
, stmt
,
485 htab_hash_pointer (stmt
), INSERT
);
489 VEC_safe_push (tree
, heap
, acc
->vars
, var
);
492 /* This function adds NEW_DECL to function
493 referenced vars, and marks it for renaming. */
496 finalize_var_creation (tree new_decl
)
498 add_referenced_var (new_decl
);
499 if (is_global_var (new_decl
))
500 mark_call_clobbered (new_decl
, ESCAPE_UNKNOWN
);
501 mark_sym_for_renaming (new_decl
);
504 /* This function finalizes VAR creation if it is a global VAR_DECL. */
507 finalize_global_creation (tree var
)
509 if (TREE_CODE (var
) == VAR_DECL
510 && is_global_var (var
))
511 finalize_var_creation (var
);
514 /* This function inserts NEW_DECL to varpool. */
517 insert_global_to_varpool (tree new_decl
)
519 struct varpool_node
*new_node
;
521 new_node
= varpool_node (new_decl
);
522 notice_global_symbol (new_decl
);
523 varpool_mark_needed_node (new_node
);
524 varpool_finalize_decl (new_decl
);
527 /* This function finalizes the creation of new variables,
528 defined by *SLOT->new_vars. */
531 finalize_new_vars_creation (void **slot
, void *data ATTRIBUTE_UNUSED
)
533 new_var n_var
= *(new_var
*) slot
;
537 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
538 finalize_var_creation (var
);
542 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
543 It returns it, if found, and NULL_TREE otherwise. */
546 find_var_in_new_vars_vec (new_var var
, tree new_type
)
551 for (i
= 0; VEC_iterate (tree
, var
->new_vars
, i
, n_var
); i
++)
553 tree type
= strip_type(get_type_of_var (n_var
));
556 if (type
== new_type
)
563 /* This function returns new_var node, the orig_var of which is DECL.
564 It looks for new_var's in NEW_VARS_HTAB. If not found,
565 the function returns NULL. */
568 is_in_new_vars_htab (tree decl
, htab_t new_vars_htab
)
570 return (new_var
) htab_find_with_hash (new_vars_htab
, decl
,
571 htab_hash_pointer (decl
));
574 /* Given original variable ORIG_VAR, this function returns
575 new variable corresponding to it of NEW_TYPE type. */
578 find_new_var_of_type (tree orig_var
, tree new_type
)
581 gcc_assert (orig_var
&& new_type
);
583 if (TREE_CODE (orig_var
) == SSA_NAME
)
584 orig_var
= SSA_NAME_VAR (orig_var
);
586 var
= is_in_new_vars_htab (orig_var
, new_global_vars
);
588 var
= is_in_new_vars_htab (orig_var
, new_local_vars
);
590 return find_var_in_new_vars_vec (var
, new_type
);
593 /* This function generates stmt:
594 res = NUM * sizeof(TYPE) and returns it.
595 res is filled into RES. */
598 gen_size (tree num
, tree type
, tree
*res
)
600 tree struct_size
= TYPE_SIZE_UNIT (type
);
601 HOST_WIDE_INT struct_size_int
= TREE_INT_CST_LOW (struct_size
);
604 *res
= create_tmp_var (TREE_TYPE (num
), NULL
);
607 add_referenced_var (*res
);
609 if (exact_log2 (struct_size_int
) == -1)
611 tree size
= build_int_cst (TREE_TYPE (num
), struct_size_int
);
612 new_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, *res
, num
, size
);
616 tree C
= build_int_cst (TREE_TYPE (num
), exact_log2 (struct_size_int
));
618 new_stmt
= gimple_build_assign_with_ops (LSHIFT_EXPR
, *res
, num
, C
);
621 finalize_stmt (new_stmt
);
625 /* This function generates and returns a statement, that cast variable
626 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
627 into RES_P. ORIG_CAST_STMT is the original cast statement. */
630 gen_cast_stmt (tree before_cast
, tree new_type
, gimple orig_cast_stmt
,
636 lhs
= gimple_assign_lhs (orig_cast_stmt
);
637 new_lhs
= find_new_var_of_type (lhs
, new_type
);
638 gcc_assert (new_lhs
);
640 new_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, new_lhs
, before_cast
, 0);
641 finalize_stmt (new_stmt
);
646 /* This function builds an edge between BB and E->dest and updates
647 phi nodes of E->dest. It returns newly created edge. */
650 make_edge_and_fix_phis_of_dest (basic_block bb
, edge e
)
654 gimple_stmt_iterator si
;
656 new_e
= make_edge (bb
, e
->dest
, e
->flags
);
658 for (si
= gsi_start_phis (new_e
->dest
); !gsi_end_p (si
); gsi_next (&si
))
660 gimple phi
= gsi_stmt (si
);
661 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
662 add_phi_arg (phi
, arg
, new_e
);
668 /* This function inserts NEW_STMT before STMT. */
671 insert_before_stmt (gimple stmt
, gimple new_stmt
)
673 gimple_stmt_iterator bsi
;
675 if (!stmt
|| !new_stmt
)
678 bsi
= gsi_for_stmt (stmt
);
679 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
682 /* Insert NEW_STMTS after STMT. */
685 insert_seq_after_stmt (gimple stmt
, gimple_seq new_stmts
)
687 gimple_stmt_iterator bsi
;
689 if (!stmt
|| !new_stmts
)
692 bsi
= gsi_for_stmt (stmt
);
693 gsi_insert_seq_after (&bsi
, new_stmts
, GSI_SAME_STMT
);
696 /* Insert NEW_STMT after STMT. */
699 insert_after_stmt (gimple stmt
, gimple new_stmt
)
701 gimple_stmt_iterator bsi
;
703 if (!stmt
|| !new_stmt
)
706 bsi
= gsi_for_stmt (stmt
);
707 gsi_insert_after (&bsi
, new_stmt
, GSI_SAME_STMT
);
710 /* This function returns vector of allocation sites
711 that appear in function FN_DECL. */
714 get_fallocs (tree fn_decl
)
716 return (fallocs_t
) htab_find_with_hash (alloc_sites
, fn_decl
,
717 htab_hash_pointer (fn_decl
));
720 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
721 and it is a part of allocation of a structure,
722 then it is usually followed by a cast stmt
723 p_8 = (struct str_t *) D.2225_7;
724 which is returned by this function. */
727 get_final_alloc_stmt (gimple alloc_stmt
)
736 if (!is_gimple_call (alloc_stmt
))
739 alloc_res
= gimple_get_lhs (alloc_stmt
);
741 if (TREE_CODE (alloc_res
) != SSA_NAME
)
744 if (!single_imm_use (alloc_res
, &use_p
, &final_stmt
))
750 /* This function returns true if STMT is one of allocation
751 sites of function FN_DECL. It returns false otherwise. */
754 is_part_of_malloc (gimple stmt
, tree fn_decl
)
756 fallocs_t fallocs
= get_fallocs (fn_decl
);
763 for (i
= 0; VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
); i
++)
764 if (call
->stmt
== stmt
765 || get_final_alloc_stmt (call
->stmt
) == stmt
)
771 /* Auxiliary structure for a lookup over field accesses. */
772 struct find_stmt_data
778 /* This function looks for DATA->stmt among
779 the statements involved in the field access,
780 defined by SLOT. It stops when it's found. */
783 find_in_field_accs (void **slot
, void *data
)
785 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
786 gimple stmt
= ((struct find_stmt_data
*)data
)->stmt
;
788 if (f_acc
->stmt
== stmt
789 || f_acc
->ref_def_stmt
== stmt
790 || f_acc
->cast_stmt
== stmt
)
792 ((struct find_stmt_data
*)data
)->found
= true;
799 /* This function checks whether STMT is part of field
800 accesses of structure STR. It returns true, if found,
801 and false otherwise. */
804 is_part_of_field_access (gimple stmt
, d_str str
)
808 for (i
= 0; i
< str
->num_fields
; i
++)
810 struct find_stmt_data data
;
814 if (str
->fields
[i
].acc_sites
)
815 htab_traverse (str
->fields
[i
].acc_sites
, find_in_field_accs
, &data
);
824 /* Auxiliary data for exclude_from_accs function. */
832 /* This function returns component_ref with the BASE and
833 field named FIELD_ID from structure TYPE. */
836 build_comp_ref (tree base
, tree field_id
, tree type
)
842 /* Find field of structure type with the same name as field_id. */
843 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
845 if (DECL_NAME (field
) == field_id
)
854 return build3 (COMPONENT_REF
, TREE_TYPE (field
), base
, field
, NULL_TREE
);
858 /* This struct represent data used for walk_tree
859 called from function find_pos_in_stmt.
860 - ref is a tree to be found,
861 - and pos is a pointer that points to ref in stmt. */
869 /* This is a callback function for walk_tree, called from
870 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
871 When *TP is equal to DATA->ref, the walk_tree stops,
872 and found position, equal to TP, is assigned to DATA->pos. */
875 find_pos_in_stmt_1 (tree
*tp
, int *walk_subtrees
, void * data
)
877 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
878 struct ref_pos
*r_pos
= (struct ref_pos
*) wi
->info
;
879 tree ref
= r_pos
->ref
;
882 if (t
== ref
|| (TREE_CODE (t
) == SSA_NAME
&& SSA_NAME_VAR (t
) == ref
))
893 /* This function looks for the pointer of REF in STMT,
894 It returns it, if found, and NULL otherwise. */
897 find_pos_in_stmt (gimple stmt
, tree ref
)
899 struct ref_pos r_pos
;
900 struct walk_stmt_info wi
;
904 memset (&wi
, 0, sizeof (wi
));
906 walk_gimple_op (stmt
, find_pos_in_stmt_1
, &wi
);
911 /* This structure is used to represent array
912 or pointer-to wrappers of structure type.
913 For example, if type1 is structure type,
914 then for type1 ** we generate two type_wrapper
915 structures with wrap = 0 each one.
916 It's used to unwind the original type up to
917 structure type, replace it with the new structure type
918 and wrap it back in the opposite order. */
920 typedef struct type_wrapper
922 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
925 /* Relevant for arrays as domain or index. */
929 DEF_VEC_O (type_wrapper_t
);
930 DEF_VEC_ALLOC_O (type_wrapper_t
, heap
);
932 /* This function replace field access ACC by the new
933 field access of structure type NEW_TYPE. */
936 replace_field_acc (struct field_access_site
*acc
, tree new_type
)
938 tree ref_var
= acc
->ref
;
943 tree field_id
= DECL_NAME (acc
->field_decl
);
944 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
945 type_wrapper_t
*wr_p
= NULL
;
947 while (TREE_CODE (ref_var
) == INDIRECT_REF
948 || TREE_CODE (ref_var
) == ARRAY_REF
)
952 if ( TREE_CODE (ref_var
) == INDIRECT_REF
)
960 wr
.domain
= TREE_OPERAND (ref_var
, 1);
963 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
964 ref_var
= TREE_OPERAND (ref_var
, 0);
967 new_ref
= find_new_var_of_type (ref_var
, new_type
);
968 finalize_global_creation (new_ref
);
970 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
972 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
974 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
975 if (wr_p
->wrap
) /* Array. */
976 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
977 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
979 new_ref
= build1 (INDIRECT_REF
, type
, new_ref
);
980 VEC_pop (type_wrapper_t
, wrapper
);
983 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
984 VEC_free (type_wrapper_t
, heap
, wrapper
);
986 if (is_gimple_assign (acc
->stmt
))
988 lhs
= gimple_assign_lhs (acc
->stmt
);
989 rhs
= gimple_assign_rhs1 (acc
->stmt
);
991 if (lhs
== acc
->comp_ref
)
992 gimple_assign_set_lhs (acc
->stmt
, new_acc
);
993 else if (rhs
== acc
->comp_ref
)
994 gimple_assign_set_rhs1 (acc
->stmt
, new_acc
);
997 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1004 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
);
1009 finalize_stmt (acc
->stmt
);
1012 /* This function replace field access ACC by a new field access
1013 of structure type NEW_TYPE. */
1016 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1019 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
1020 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1021 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1022 replace_field_acc (acc
, new_type
);
1027 /* This function looks for d_str, represented by TYPE, in the structures
1028 vector. If found, it returns an index of found structure. Otherwise
1029 it returns a length of the structures vector. */
1032 find_structure (tree type
)
1037 type
= TYPE_MAIN_VARIANT (type
);
1039 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
1040 if (is_equal_types (str
->decl
, type
))
1043 return VEC_length (structure
, structures
);
1046 /* In this function we create new statements that have the same
1047 form as ORIG_STMT, but of type NEW_TYPE. The statements
1048 treated by this function are simple assignments,
1049 like assignments: p.8_7 = p; or statements with rhs of
1050 tree codes PLUS_EXPR and MINUS_EXPR. */
1053 create_base_plus_offset (gimple orig_stmt
, tree new_type
, tree offset
)
1058 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1060 lhs
= gimple_assign_lhs (orig_stmt
);
1062 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1063 || TREE_CODE (lhs
) == SSA_NAME
);
1065 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1066 gcc_assert (new_lhs
);
1067 finalize_var_creation (new_lhs
);
1069 switch (gimple_assign_rhs_code (orig_stmt
))
1073 case POINTER_PLUS_EXPR
:
1075 tree op0
= gimple_assign_rhs1 (orig_stmt
);
1076 tree op1
= gimple_assign_rhs2 (orig_stmt
);
1077 unsigned str0
, str1
;
1078 unsigned length
= VEC_length (structure
, structures
);
1081 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1082 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1083 gcc_assert ((str0
!= length
) || (str1
!= length
));
1086 new_op0
= find_new_var_of_type (op0
, new_type
);
1088 new_op1
= find_new_var_of_type (op1
, new_type
);
1101 new_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt
),
1102 new_lhs
, new_op0
, new_op1
);
1103 finalize_stmt (new_stmt
);
1108 /* Given a field access F_ACC of the FIELD, this function
1109 replaces it by the new field access. */
1112 create_new_field_access (struct field_access_site
*f_acc
,
1113 struct field_entry field
)
1115 tree new_type
= field
.field_mapping
;
1120 tree cast_res
= NULL
;
1124 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1125 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1128 if (f_acc
->cast_stmt
)
1130 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1131 f_acc
->cast_stmt
, &cast_res
);
1132 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1135 if (f_acc
->ref_def_stmt
)
1143 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1145 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1148 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1149 D.2162_18 by an appropriate variable of new_type type. */
1150 replace_field_access_stmt (f_acc
, new_type
);
1153 /* This function creates a new condition statement
1154 corresponding to the original COND_STMT, adds new basic block
1155 and redirects condition edges. NEW_VAR is a new condition
1156 variable located in the condition statement at the position POS. */
1159 create_new_stmts_for_cond_expr_1 (tree new_var
, gimple cond_stmt
, unsigned pos
)
1162 edge true_e
= NULL
, false_e
= NULL
;
1164 gimple_stmt_iterator si
;
1166 extract_true_false_edges_from_block (gimple_bb (cond_stmt
),
1169 new_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
1170 pos
== 0 ? new_var
: gimple_cond_lhs (cond_stmt
),
1171 pos
== 1 ? new_var
: gimple_cond_rhs (cond_stmt
),
1175 finalize_stmt (new_stmt
);
1177 /* Create new basic block after bb. */
1178 new_bb
= create_empty_bb (gimple_bb (cond_stmt
));
1180 /* Add new condition stmt to the new_bb. */
1181 si
= gsi_start_bb (new_bb
);
1182 gsi_insert_after (&si
, new_stmt
, GSI_NEW_STMT
);
1184 /* Create false and true edges from new_bb. */
1185 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1186 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1188 /* Redirect one of original edges to point to new_bb. */
1189 if (gimple_cond_code (cond_stmt
) == NE_EXPR
)
1190 redirect_edge_succ (true_e
, new_bb
);
1192 redirect_edge_succ (false_e
, new_bb
);
1195 /* This function creates new condition statements corresponding
1196 to original condition STMT, one for each new type, and
1197 recursively redirect edges to newly generated basic blocks. */
1200 create_new_stmts_for_cond_expr (gimple stmt
)
1202 tree arg0
, arg1
, arg
;
1203 unsigned str0
, str1
;
1209 unsigned length
= VEC_length (structure
, structures
);
1211 gcc_assert (gimple_cond_code (stmt
) == EQ_EXPR
1212 || gimple_cond_code (stmt
) == NE_EXPR
);
1214 arg0
= gimple_cond_lhs (stmt
);
1215 arg1
= gimple_cond_rhs (stmt
);
1217 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1218 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1220 s0
= (str0
!= length
) ? true : false;
1221 s1
= (str1
!= length
) ? true : false;
1223 gcc_assert (s0
|| s1
);
1224 /* For now we allow only comparison with 0 or NULL. */
1225 gcc_assert (integer_zerop (arg0
) || integer_zerop (arg1
));
1227 str
= integer_zerop (arg0
) ?
1228 VEC_index (structure
, structures
, str1
):
1229 VEC_index (structure
, structures
, str0
);
1230 arg
= integer_zerop (arg0
) ? arg1
: arg0
;
1231 pos
= integer_zerop (arg0
) ? 1 : 0;
1233 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1237 new_arg
= find_new_var_of_type (arg
, type
);
1238 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1242 /* Create a new general access to replace original access ACC
1243 for structure type NEW_TYPE. */
1246 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1248 gimple old_stmt
= acc
->stmt
;
1250 gimple new_stmt
= gimple_copy (old_stmt
);
1253 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1256 tree new_var
= find_new_var_of_type (var
, new_type
);
1259 gcc_assert (new_var
);
1260 finalize_var_creation (new_var
);
1262 if (is_gimple_assign (new_stmt
))
1264 lhs
= gimple_assign_lhs (new_stmt
);
1266 if (TREE_CODE (lhs
) == SSA_NAME
)
1267 lhs
= SSA_NAME_VAR (lhs
);
1268 if (gimple_assign_rhs_code (new_stmt
) == SSA_NAME
)
1269 rhs
= SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt
));
1271 /* It can happen that rhs is a constructor.
1272 Then we have to replace it to be of new_type. */
1273 if (gimple_assign_rhs_code (new_stmt
) == CONSTRUCTOR
)
1275 /* Dealing only with empty constructors right now. */
1276 gcc_assert (VEC_empty (constructor_elt
,
1277 CONSTRUCTOR_ELTS (rhs
)));
1278 rhs
= build_constructor (new_type
, 0);
1279 gimple_assign_set_rhs1 (new_stmt
, rhs
);
1283 gimple_assign_set_lhs (new_stmt
, new_var
);
1284 else if (rhs
== var
)
1285 gimple_assign_set_rhs1 (new_stmt
, new_var
);
1288 pos
= find_pos_in_stmt (new_stmt
, var
);
1295 pos
= find_pos_in_stmt (new_stmt
, var
);
1301 finalize_stmt (new_stmt
);
1305 /* For each new type in STR this function creates new general accesses
1306 corresponding to the original access ACC. */
1309 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1312 gimple stmt
= acc
->stmt
;
1315 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1319 new_stmt
= create_general_new_stmt (acc
, type
);
1320 insert_after_stmt (stmt
, new_stmt
);
1324 /* This function creates a new general access of structure STR
1325 to replace the access ACC. */
1328 create_new_general_access (struct access_site
*acc
, d_str str
)
1330 gimple stmt
= acc
->stmt
;
1331 switch (gimple_code (stmt
))
1334 create_new_stmts_for_cond_expr (stmt
);
1338 create_new_stmts_for_general_acc (acc
, str
);
1342 /* Auxiliary data for creation of accesses. */
1343 struct create_acc_data
1350 /* This function creates a new general access, defined by SLOT.
1351 DATA is a pointer to create_acc_data structure. */
1354 create_new_acc (void **slot
, void *data
)
1356 struct access_site
*acc
= *(struct access_site
**) slot
;
1357 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1358 d_str str
= ((struct create_acc_data
*)data
)->str
;
1360 if (gimple_bb (acc
->stmt
) == bb
)
1361 create_new_general_access (acc
, str
);
1365 /* This function creates a new field access, defined by SLOT.
1366 DATA is a pointer to create_acc_data structure. */
1369 create_new_field_acc (void **slot
, void *data
)
1371 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1372 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1373 d_str str
= ((struct create_acc_data
*)data
)->str
;
1374 int i
= ((struct create_acc_data
*)data
)->field_index
;
1376 if (gimple_bb (f_acc
->stmt
) == bb
)
1377 create_new_field_access (f_acc
, str
->fields
[i
]);
1381 /* This function creates new accesses for the structure
1382 type STR in basic block BB. */
1385 create_new_accs_for_struct (d_str str
, basic_block bb
)
1388 struct create_acc_data dt
;
1392 dt
.field_index
= -1;
1394 for (i
= 0; i
< str
->num_fields
; i
++)
1398 if (str
->fields
[i
].acc_sites
)
1399 htab_traverse (str
->fields
[i
].acc_sites
,
1400 create_new_field_acc
, &dt
);
1403 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1406 /* This function inserts new variables from new_var,
1407 defined by SLOT, into varpool. */
1410 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1412 new_var n_var
= *(new_var
*) slot
;
1416 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1417 insert_global_to_varpool (var
);
1421 /* This function prints a field access site, defined by SLOT. */
1424 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1426 struct field_access_site
*f_acc
=
1427 *(struct field_access_site
**) slot
;
1429 fprintf(dump_file
, "\n");
1431 print_gimple_stmt (dump_file
, f_acc
->stmt
, 0, 0);
1432 if (f_acc
->ref_def_stmt
)
1433 print_gimple_stmt (dump_file
, f_acc
->ref_def_stmt
, 0, 0);
1434 if (f_acc
->cast_stmt
)
1435 print_gimple_stmt (dump_file
, f_acc
->cast_stmt
, 0, 0);
1439 /* Print field accesses from hashtable F_ACCS. */
1442 dump_field_acc_sites (htab_t f_accs
)
1448 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1451 /* Hash value for fallocs_t. */
1454 malloc_hash (const void *x
)
1456 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1459 /* This function returns nonzero if function of func_alloc_sites' X
1463 malloc_eq (const void *x
, const void *y
)
1465 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1468 /* This function is a callback for traversal over a structure accesses.
1469 It frees an access represented by SLOT. */
1472 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1474 struct access_site
* acc
= *(struct access_site
**) slot
;
1476 VEC_free (tree
, heap
, acc
->vars
);
1481 /* This is a callback function for traversal over field accesses.
1482 It frees a field access represented by SLOT. */
1485 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1487 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1493 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1494 if it is not there yet. */
1497 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1505 type
= TYPE_MAIN_VARIANT (type
);
1507 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1508 if (is_equal_types (t
, type
))
1511 if (i
== VEC_length (tree
, *unsuitable_types
))
1512 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1515 /* Given a type TYPE, this function returns the name of the type. */
1518 get_type_name (tree type
)
1520 if (! TYPE_NAME (type
))
1523 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1524 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1525 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1526 && DECL_NAME (TYPE_NAME (type
)))
1527 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1532 /* This function is a temporary hack to overcome the types problem.
1533 When several compilation units are compiled together
1534 with -combine, the TYPE_MAIN_VARIANT of the same type
1535 can appear differently in different compilation units.
1536 Therefore this function first compares type names.
1537 If there are no names, structure bodies are recursively
1541 is_equal_types (tree type1
, tree type2
)
1543 const char * name1
,* name2
;
1545 if ((!type1
&& type2
)
1546 ||(!type2
&& type1
))
1549 if (!type1
&& !type2
)
1552 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1558 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1561 name1
= get_type_name (type1
);
1562 name2
= get_type_name (type2
);
1564 if (name1
&& name2
&& !strcmp (name1
, name2
))
1567 if (name1
&& name2
&& strcmp (name1
, name2
))
1570 switch (TREE_CODE (type1
))
1573 case REFERENCE_TYPE
:
1575 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1581 case QUAL_UNION_TYPE
:
1585 /* Compare fields of structure. */
1586 for (field1
= TYPE_FIELDS (type1
); field1
;
1587 field1
= TREE_CHAIN (field1
))
1589 tree field2
= find_field_in_struct_1 (type2
, field1
);
1599 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1600 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1608 tree max1
, min1
, max2
, min2
;
1610 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1613 d1
= TYPE_DOMAIN (type1
);
1614 d2
= TYPE_DOMAIN (type2
);
1619 max1
= TYPE_MAX_VALUE (d1
);
1620 max2
= TYPE_MAX_VALUE (d2
);
1621 min1
= TYPE_MIN_VALUE (d1
);
1622 min2
= TYPE_MIN_VALUE (d2
);
1624 if (max1
&& max2
&& min1
&& min2
1625 && TREE_CODE (max1
) == TREE_CODE (max2
)
1626 && TREE_CODE (max1
) == INTEGER_CST
1627 && TREE_CODE (min1
) == TREE_CODE (min2
)
1628 && TREE_CODE (min1
) == INTEGER_CST
1629 && tree_int_cst_equal (max1
, max2
)
1630 && tree_int_cst_equal (min1
, min2
))
1642 /* This function free non-field accesses from hashtable ACCS. */
1645 free_accesses (htab_t accs
)
1648 htab_traverse (accs
, free_accs
, NULL
);
1652 /* This function free field accesses hashtable F_ACCS. */
1655 free_field_accesses (htab_t f_accs
)
1658 htab_traverse (f_accs
, free_field_accs
, NULL
);
1659 htab_delete (f_accs
);
1662 /* Update call graph with new edge generated by new MALLOC_STMT.
1663 The edge origin is CONTEXT function. */
1666 update_cgraph_with_malloc_call (gimple malloc_stmt
, tree context
)
1668 struct cgraph_node
*src
, *dest
;
1669 tree malloc_fn_decl
;
1674 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1676 src
= cgraph_node (context
);
1677 dest
= cgraph_node (malloc_fn_decl
);
1678 cgraph_create_edge (src
, dest
, malloc_stmt
,
1679 0, 0, gimple_bb (malloc_stmt
)->loop_depth
);
1682 /* This function generates set of statements required
1683 to allocate number NUM of structures of type NEW_TYPE.
1684 The statements are stored in NEW_STMTS. The statement that contain
1685 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1688 create_new_malloc (gimple malloc_stmt
, tree new_type
, gimple_seq
*new_stmts
,
1691 tree new_malloc_size
;
1692 tree malloc_fn_decl
;
1695 gimple call_stmt
, final_stmt
;
1698 gcc_assert (num
&& malloc_stmt
&& new_type
);
1699 *new_stmts
= gimple_seq_alloc ();
1701 /* Generate argument to malloc as multiplication of num
1702 and size of new_type. */
1703 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1704 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1706 /* Generate new call for malloc. */
1707 malloc_res
= create_tmp_var (ptr_type_node
, NULL
);
1708 add_referenced_var (malloc_res
);
1710 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1711 call_stmt
= gimple_build_call (malloc_fn_decl
, 1, new_malloc_size
);
1712 gimple_call_set_lhs (call_stmt
, malloc_res
);
1713 finalize_stmt_and_append (new_stmts
, call_stmt
);
1715 /* Create new cast statement. */
1716 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1717 gcc_assert (final_stmt
);
1718 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1719 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1724 /* This function returns a tree representing
1725 the number of instances of structure STR_DECL allocated
1726 by allocation STMT. If new statements are generated,
1727 they are filled into NEW_STMTS_P. */
1730 gen_num_of_structs_in_malloc (gimple stmt
, tree str_decl
,
1731 gimple_seq
*new_stmts_p
)
1735 HOST_WIDE_INT struct_size_int
;
1740 /* Get malloc argument. */
1741 if (!is_gimple_call (stmt
))
1744 arg
= gimple_call_arg (stmt
, 0);
1746 if (TREE_CODE (arg
) != SSA_NAME
1747 && !TREE_CONSTANT (arg
))
1750 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1751 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1753 gcc_assert (struct_size
);
1755 if (TREE_CODE (arg
) == SSA_NAME
)
1760 if (is_result_of_mult (arg
, &num
, struct_size
))
1763 num
= create_tmp_var (integer_type_node
, NULL
);
1766 add_referenced_var (num
);
1768 if (exact_log2 (struct_size_int
) == -1)
1769 div_stmt
= gimple_build_assign_with_ops (TRUNC_DIV_EXPR
, num
, arg
,
1773 tree C
= build_int_cst (integer_type_node
,
1774 exact_log2 (struct_size_int
));
1776 div_stmt
= gimple_build_assign_with_ops (RSHIFT_EXPR
, num
, arg
, C
);
1778 gimple_seq_add_stmt (new_stmts_p
, div_stmt
);
1779 finalize_stmt (div_stmt
);
1783 if (CONSTANT_CLASS_P (arg
)
1784 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1785 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1790 /* This function is a callback for traversal on new_var's hashtable.
1791 SLOT is a pointer to new_var. This function prints to dump_file
1792 an original variable and all new variables from the new_var
1793 pointed by *SLOT. */
1796 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1798 new_var n_var
= *(new_var
*) slot
;
1803 var_type
= get_type_of_var (n_var
->orig_var
);
1805 fprintf (dump_file
, "\nOrig var: ");
1806 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1807 fprintf (dump_file
, " of type ");
1808 print_generic_expr (dump_file
, var_type
, 0);
1809 fprintf (dump_file
, "\n");
1812 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1814 var_type
= get_type_of_var (var
);
1816 fprintf (dump_file
, " ");
1817 print_generic_expr (dump_file
, var
, 0);
1818 fprintf (dump_file
, " of type ");
1819 print_generic_expr (dump_file
, var_type
, 0);
1820 fprintf (dump_file
, "\n");
1825 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1828 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1831 DECL_ARTIFICIAL (new_decl
) = 1;
1832 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1833 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1834 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1835 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1836 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1837 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1838 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1840 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1842 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1843 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1847 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1848 the same way as a structure type is wrapped in DECL.
1849 It returns the generated type. */
1852 gen_struct_type (tree decl
, tree new_str_type
)
1854 tree type_orig
= get_type_of_var (decl
);
1855 tree new_type
= new_str_type
;
1856 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1858 type_wrapper_t
*wr_p
;
1860 while (POINTER_TYPE_P (type_orig
)
1861 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1863 if (POINTER_TYPE_P (type_orig
))
1866 wr
.domain
= NULL_TREE
;
1868 else if (TREE_CODE (type_orig
) == ARRAY_TYPE
)
1871 wr
.domain
= TYPE_DOMAIN (type_orig
);
1873 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1874 type_orig
= TREE_TYPE (type_orig
);
1877 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1879 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1881 if (wr_p
->wrap
) /* Array. */
1882 new_type
= build_array_type (new_type
, wr_p
->domain
);
1884 new_type
= build_pointer_type (new_type
);
1886 VEC_pop (type_wrapper_t
, wrapper
);
1889 VEC_free (type_wrapper_t
, heap
, wrapper
);
1893 /* This function generates and returns new variable name based on
1894 ORIG_DECL name, combined with index I.
1895 The form of the new name is <orig_name>.<I> . */
1898 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1900 const char *old_name
;
1904 if (!DECL_NAME (orig_decl
)
1905 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1908 /* If the original variable has a name, create an
1909 appropriate new name for the new variable. */
1911 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1912 prefix
= XALLOCAVEC (char, strlen (old_name
) + 1);
1913 strcpy (prefix
, old_name
);
1914 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1915 return get_identifier (new_name
);
1918 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1921 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1925 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1926 htab_hash_pointer (new_node
->orig_var
),
1931 /* This function creates and returns new_var_data node
1932 with empty new_vars and orig_var equal to VAR. */
1935 create_new_var_node (tree var
, d_str str
)
1939 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1940 node
->orig_var
= var
;
1941 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1945 /* Check whether the type of VAR is potential candidate for peeling.
1946 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1947 candidate type. If VAR is initialized, the type of VAR will be added
1948 to UNSUITABLE_TYPES. */
1951 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
1954 bool initialized
= false;
1961 /* There is no support of initialized vars. */
1962 if (TREE_CODE (var
) == VAR_DECL
1963 && DECL_INITIAL (var
) != NULL_TREE
)
1966 type
= get_type_of_var (var
);
1970 type
= TYPE_MAIN_VARIANT (strip_type (type
));
1971 if (TREE_CODE (type
) != RECORD_TYPE
)
1975 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
1979 fprintf (dump_file
, "The type ");
1980 print_generic_expr (dump_file
, type
, 0);
1981 fprintf (dump_file
, " is initialized...Excluded.");
1983 add_unsuitable_type (unsuitable_types
, type
);
1993 /* Hash value for field_access_site. */
1996 field_acc_hash (const void *x
)
1998 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2001 /* This function returns nonzero if stmt of field_access_site X
2005 field_acc_eq (const void *x
, const void *y
)
2007 return ((const struct field_access_site
*)x
)->stmt
== (const_gimple
)y
;
2010 /* This function prints an access site, defined by SLOT. */
2013 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2015 struct access_site
*acc
= *(struct access_site
**) slot
;
2019 fprintf(dump_file
, "\n");
2021 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
2022 fprintf(dump_file
, " : ");
2024 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2026 print_generic_expr (dump_file
, var
, 0);
2027 fprintf(dump_file
, ", ");
2032 /* This function frees memory allocated for structure clusters,
2033 starting from CLUSTER. */
2036 free_struct_cluster (struct field_cluster
* cluster
)
2040 if (cluster
->fields_in_cluster
)
2041 sbitmap_free (cluster
->fields_in_cluster
);
2042 if (cluster
->sibling
)
2043 free_struct_cluster (cluster
->sibling
);
2048 /* Free all allocated memory under the structure node pointed by D_NODE. */
2051 free_data_struct (d_str d_node
)
2060 fprintf (dump_file
, "\nRemoving data structure \"");
2061 print_generic_expr (dump_file
, d_node
->decl
, 0);
2062 fprintf (dump_file
, "\" from data_struct_list.");
2065 /* Free all space under d_node. */
2068 for (i
= 0; i
< d_node
->num_fields
; i
++)
2069 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2070 free (d_node
->fields
);
2074 free_accesses (d_node
->accs
);
2076 if (d_node
->struct_clustering
)
2077 free_struct_cluster (d_node
->struct_clustering
);
2079 if (d_node
->new_types
)
2080 VEC_free (tree
, heap
, d_node
->new_types
);
2083 /* This function creates new general and field accesses in BB. */
2086 create_new_accesses_in_bb (basic_block bb
)
2091 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2092 create_new_accs_for_struct (str
, bb
);
2095 /* This function adds allocation sites for peeled structures.
2096 M_DATA is vector of allocation sites of function CONTEXT. */
2099 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2104 for (j
= 0; VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2106 gimple stmt
= call
->stmt
;
2107 d_str str
= call
->str
;
2109 gimple_seq new_stmts
= NULL
;
2110 gimple last_stmt
= get_final_alloc_stmt (stmt
);
2114 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2117 gimple last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2118 insert_seq_after_stmt (last_stmt
, new_stmts
);
2119 last_stmt
= last_stmt_tmp
;
2122 /* Generate an allocation sites for each new structure type. */
2123 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2125 gimple new_malloc_stmt
= NULL
;
2126 gimple last_stmt_tmp
= NULL
;
2129 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2130 last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2131 insert_seq_after_stmt (last_stmt
, new_stmts
);
2132 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2133 last_stmt
= last_stmt_tmp
;
2138 /* This function prints new variables from hashtable
2139 NEW_VARS_HTAB to dump_file. */
2142 dump_new_vars (htab_t new_vars_htab
)
2148 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2151 /* Given an original variable ORIG_DECL of structure type STR,
2152 this function generates new variables of the types defined
2153 by STR->new_type. Generated types are saved in new_var node NODE.
2154 ORIG_DECL should has VAR_DECL tree_code. */
2157 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2163 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2165 tree new_decl
= NULL
;
2168 new_name
= gen_var_name (orig_decl
, i
);
2169 type
= gen_struct_type (orig_decl
, type
);
2171 if (is_global_var (orig_decl
))
2172 new_decl
= build_decl (VAR_DECL
, new_name
, type
);
2175 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2176 new_decl
= create_tmp_var (type
, name
);
2179 copy_decl_attributes (new_decl
, orig_decl
);
2180 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2184 /* This function creates new variables to
2185 substitute the original variable VAR_DECL and adds
2186 them to the new_var's hashtable NEW_VARS_HTAB. */
2189 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2196 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2199 if (!is_candidate (var_decl
, &type
, NULL
))
2202 i
= find_structure (type
);
2203 if (i
== VEC_length (structure
, structures
))
2206 str
= VEC_index (structure
, structures
, i
);
2207 node
= create_new_var_node (var_decl
, str
);
2208 create_new_var_1 (var_decl
, str
, node
);
2209 add_to_new_vars_htab (node
, new_vars_htab
);
2212 /* Hash value for new_var. */
2215 new_var_hash (const void *x
)
2217 return htab_hash_pointer (((const_new_var
)x
)->orig_var
);
2220 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2223 new_var_eq (const void *x
, const void *y
)
2225 return ((const_new_var
)x
)->orig_var
== (const_tree
)y
;
2228 /* This function check whether a structure type represented by STR
2229 escapes due to ipa-type-escape analysis. If yes, this type is added
2230 to UNSUITABLE_TYPES vector. */
2233 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2235 tree type
= str
->decl
;
2237 if (!ipa_type_escape_type_contained_p (type
))
2241 fprintf (dump_file
, "\nEscaping type is ");
2242 print_generic_expr (dump_file
, type
, 0);
2244 add_unsuitable_type (unsuitable_types
, type
);
2248 /* Hash value for access_site. */
2251 acc_hash (const void *x
)
2253 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2256 /* Return nonzero if stmt of access_site X is equal to Y. */
2259 acc_eq (const void *x
, const void *y
)
2261 return ((const struct access_site
*)x
)->stmt
== (const_gimple
)y
;
2264 /* Given a structure declaration STRUCT_DECL, and number of fields
2265 in the structure NUM_FIELDS, this function creates and returns
2266 corresponding field_entry's. */
2268 static struct field_entry
*
2269 get_fields (tree struct_decl
, int num_fields
)
2271 struct field_entry
*list
;
2272 tree t
= TYPE_FIELDS (struct_decl
);
2276 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2278 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2279 if (TREE_CODE (t
) == FIELD_DECL
)
2281 list
[idx
].index
= idx
;
2283 list
[idx
].acc_sites
=
2284 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2285 list
[idx
].count
= 0;
2286 list
[idx
].field_mapping
= NULL_TREE
;
2292 /* Print non-field accesses from hashtable ACCS of structure. */
2295 dump_access_sites (htab_t accs
)
2301 htab_traverse (accs
, dump_acc
, NULL
);
2304 /* This function is a callback for alloc_sites hashtable
2305 traversal. SLOT is a pointer to fallocs_t. This function
2306 removes all allocations of the structure defined by DATA. */
2309 remove_str_allocs_in_func (void **slot
, void *data
)
2311 fallocs_t fallocs
= *(fallocs_t
*) slot
;
2315 while (VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
))
2317 if (call
->str
== (d_str
) data
)
2318 VEC_ordered_remove (alloc_site_t
, fallocs
->allocs
, i
);
2326 /* This function remove all entries corresponding to the STR structure
2327 from alloc_sites hashtable. */
2330 remove_str_allocs (d_str str
)
2336 htab_traverse (alloc_sites
, remove_str_allocs_in_func
, str
);
2339 /* This function removes the structure with index I from structures vector. */
2342 remove_structure (unsigned i
)
2346 if (i
>= VEC_length (structure
, structures
))
2349 str
= VEC_index (structure
, structures
, i
);
2351 /* Before removing the structure str, we have to remove its
2352 allocations from alloc_sites hashtable. */
2353 remove_str_allocs (str
);
2354 free_data_struct (str
);
2355 VEC_ordered_remove (structure
, structures
, i
);
2358 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2359 COND_STMT is a condition statement to check. */
2362 is_safe_cond_expr (gimple cond_stmt
)
2365 unsigned str0
, str1
;
2367 unsigned length
= VEC_length (structure
, structures
);
2369 if (gimple_cond_code (cond_stmt
) != EQ_EXPR
2370 && gimple_cond_code (cond_stmt
) != NE_EXPR
)
2373 arg0
= gimple_cond_lhs (cond_stmt
);
2374 arg1
= gimple_cond_rhs (cond_stmt
);
2376 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2377 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2379 s0
= (str0
!= length
) ? true : false;
2380 s1
= (str1
!= length
) ? true : false;
2385 /* For now we allow only comparison with 0 or NULL. */
2386 if (!integer_zerop (arg0
) && !integer_zerop (arg1
))
2392 /* This function excludes statements, that are
2393 part of allocation sites or field accesses, from the
2394 hashtable of general accesses. SLOT represents general
2395 access that will be checked. DATA is a pointer to
2396 exclude_data structure. */
2399 exclude_from_accs (void **slot
, void *data
)
2401 struct access_site
*acc
= *(struct access_site
**) slot
;
2402 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2403 d_str str
= ((struct exclude_data
*)data
)->str
;
2405 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2406 || is_part_of_field_access (acc
->stmt
, str
))
2408 VEC_free (tree
, heap
, acc
->vars
);
2410 htab_clear_slot (str
->accs
, slot
);
2415 /* Callback function for walk_tree called from collect_accesses_in_bb
2416 function. DATA is the statement which is analyzed. */
2419 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2421 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
2422 gimple stmt
= (gimple
) wi
->info
;
2428 switch (TREE_CODE (t
))
2432 tree var
= TREE_OPERAND(t
, 0);
2433 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2434 unsigned i
= find_structure (type
);
2436 if (i
!= VEC_length (structure
, structures
))
2440 fprintf (dump_file
, "\nThe type ");
2441 print_generic_expr (dump_file
, type
, 0);
2442 fprintf (dump_file
, " has bitfield.");
2444 remove_structure (i
);
2451 tree ref
= TREE_OPERAND (t
, 0);
2452 tree field_decl
= TREE_OPERAND (t
, 1);
2455 if ((TREE_CODE (ref
) == INDIRECT_REF
2456 || TREE_CODE (ref
) == ARRAY_REF
2457 || TREE_CODE (ref
) == VAR_DECL
)
2458 && TREE_CODE (field_decl
) == FIELD_DECL
)
2460 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2461 unsigned i
= find_structure (type
);
2463 if (i
!= VEC_length (structure
, structures
))
2465 d_str str
= VEC_index (structure
, structures
, i
);
2466 struct field_entry
* field
=
2467 find_field_in_struct (str
, field_decl
);
2471 struct field_access_site
*acc
= make_field_acc_node ();
2478 acc
->field_decl
= field_decl
;
2480 /* Check whether the access is of the form
2481 we can deal with. */
2482 if (!decompose_access (str
->decl
, acc
))
2486 fprintf (dump_file
, "\nThe type ");
2487 print_generic_expr (dump_file
, type
, 0);
2489 " has complicate access in statement ");
2490 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2493 remove_structure (i
);
2498 /* Increase count of field. */
2499 basic_block bb
= gimple_bb (stmt
);
2500 field
->count
+= bb
->count
;
2502 /* Add stmt to the acc_sites of field. */
2503 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2514 tree cond
= COND_EXPR_COND (t
);
2516 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2518 tree t
= TREE_OPERAND (cond
, i
);
2521 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2532 if (TREE_CODE (t
) == SSA_NAME
)
2533 t
= SSA_NAME_VAR (t
);
2535 i
= find_structure (strip_type (get_type_of_var (t
)));
2536 if (i
!= VEC_length (structure
, structures
))
2540 str
= VEC_index (structure
, structures
, i
);
2541 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2554 /* Free structures hashtable. */
2557 free_structures (void)
2562 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2563 free_data_struct (str
);
2565 VEC_free (structure
, heap
, structures
);
2569 /* This function is a callback for traversal over new_var's hashtable.
2570 SLOT is a pointer to new_var. This function frees memory allocated
2571 for new_var and pointed by *SLOT. */
2574 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2576 new_var n_var
= *(new_var
*) slot
;
2578 /* Free vector of new_vars. */
2579 VEC_free (tree
, heap
, n_var
->new_vars
);
2584 /* Free new_vars hashtable NEW_VARS_HTAB. */
2587 free_new_vars_htab (htab_t new_vars_htab
)
2590 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2591 htab_delete (new_vars_htab
);
2592 new_vars_htab
= NULL
;
2595 /* This function creates new general and field accesses that appear in cfun. */
2598 create_new_accesses_for_func (void)
2602 FOR_EACH_BB_FN (bb
, cfun
)
2603 create_new_accesses_in_bb (bb
);
2606 /* Create new allocation sites for the function represented by NODE. */
2609 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2611 fallocs_t fallocs
= get_fallocs (node
->decl
);
2614 create_new_alloc_sites (fallocs
, node
->decl
);
2617 /* For each local variable of structure type from the vector of structures
2618 this function generates new variable(s) to replace it. */
2621 create_new_local_vars (void)
2624 referenced_var_iterator rvi
;
2626 new_local_vars
= htab_create (num_referenced_vars
,
2627 new_var_hash
, new_var_eq
, NULL
);
2629 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2631 if (!is_global_var (var
))
2632 create_new_var (var
, new_local_vars
);
2636 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2637 dump_new_vars (new_local_vars
);
2640 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2643 print_shift (unsigned HOST_WIDE_INT shift
)
2645 unsigned HOST_WIDE_INT sh
= shift
;
2648 fprintf (dump_file
, " ");
2651 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2654 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2655 struct field_entry
* fields
, int num_fields
)
2659 for (i
= 0; i
< num_fields
; i
++)
2660 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2661 fields
[i
].field_mapping
= new_type
;
2664 /* This functions builds structure with FIELDS,
2665 NAME and attributes similar to ORIG_STRUCT.
2666 It returns the newly created structure. */
2669 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2671 tree attributes
= NULL_TREE
;
2675 if (TYPE_ATTRIBUTES (orig_struct
))
2676 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2677 ref
= make_node (RECORD_TYPE
);
2678 TYPE_SIZE (ref
) = 0;
2679 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2680 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2681 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2683 DECL_CONTEXT (x
) = ref
;
2684 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2686 TYPE_FIELDS (ref
) = fields
;
2688 TYPE_NAME (ref
) = name
;
2693 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2694 of preparation for new structure building. NUM_FIELDS is a total
2695 number of fields in the structure. The function returns newly
2696 generated fields. */
2699 create_fields (struct field_cluster
* cluster
,
2700 struct field_entry
* fields
, int num_fields
)
2703 tree new_types
= NULL_TREE
;
2704 tree last
= NULL_TREE
;
2706 for (i
= 0; i
< num_fields
; i
++)
2707 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2709 tree new_decl
= unshare_expr (fields
[i
].decl
);
2712 new_types
= new_decl
;
2714 TREE_CHAIN (last
) = new_decl
;
2718 TREE_CHAIN (last
) = NULL_TREE
;
2723 /* This function creates a cluster name. The name is based on
2724 the original structure name, if it is present. It has a form:
2726 <original_struct_name>_sub.<CLUST_NUM>
2728 The original structure name is taken from the type of DECL.
2729 If an original structure name is not present, it's generated to be:
2733 The function returns identifier of the new cluster name. */
2736 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2738 const char * orig_name
= get_type_name (decl
);
2739 char * tmp_name
= NULL
;
2745 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2747 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2748 prefix
= XALLOCAVEC (char, len
+ 1);
2749 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2750 strlen (tmp_name
? tmp_name
: orig_name
));
2751 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2753 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2754 return get_identifier (new_name
);
2757 /* This function checks whether the structure STR has bitfields.
2758 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2761 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2763 tree type
= str
->decl
;
2766 for (i
= 0; i
< str
->num_fields
; i
++)
2767 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2769 add_unsuitable_type (unsuitable_types
, type
);
2772 fprintf (dump_file
, "\nType ");
2773 print_generic_expr (dump_file
, type
, 0);
2774 fprintf (dump_file
, "\nescapes due to bitfield ");
2775 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2781 /* This function adds to UNSUITABLE_TYPES those types that escape
2782 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2785 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2790 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2791 check_type_escape (str
, unsuitable_types
);
2794 /* If a structure type is a return type of any function,
2795 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2798 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2800 struct cgraph_node
*c_node
;
2802 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2804 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2808 ret_t
= strip_type (ret_t
);
2809 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2811 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2814 fprintf (dump_file
, "\nThe type \"");
2815 print_generic_expr (dump_file
, ret_t
, 0);
2817 "\" is return type of function...Excluded.");
2824 /* This function looks for parameters of local functions
2825 which are of structure types, or derived from them (arrays
2826 of structures, pointers to structures, or their combinations).
2827 We are not handling peeling of such structures right now.
2828 The found structures types are added to UNSUITABLE_TYPES vector. */
2831 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2833 struct cgraph_node
*c_node
;
2835 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2836 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2838 tree fn
= c_node
->decl
;
2841 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2843 tree type
= TREE_TYPE (arg
);
2845 type
= strip_type (type
);
2846 if (TREE_CODE (type
) == RECORD_TYPE
)
2848 add_unsuitable_type (unsuitable_types
,
2849 TYPE_MAIN_VARIANT (type
));
2852 fprintf (dump_file
, "\nPointer to type \"");
2853 print_generic_expr (dump_file
, type
, 0);
2855 "\" is passed to local function...Excluded.");
2862 /* This function analyzes structure form of structures
2863 potential for transformation. If we are not capable to transform
2864 structure of some form, we remove it from the structures hashtable.
2865 Right now we cannot handle nested structs, when nesting is
2866 through any level of pointers or arrays.
2868 TBD: release these constrains in future.
2870 Note, that in this function we suppose that all structures
2871 in the program are members of the structures hashtable right now,
2872 without excluding escaping types. */
2875 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2879 for (i
= 0; i
< str
->num_fields
; i
++)
2881 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2883 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2885 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2886 add_unsuitable_type (unsuitable_types
, str
->decl
);
2889 fprintf (dump_file
, "\nType ");
2890 print_generic_expr (dump_file
, f_type
, 0);
2891 fprintf (dump_file
, " is a field in the structure ");
2892 print_generic_expr (dump_file
, str
->decl
, 0);
2893 fprintf (dump_file
, ". Escaping...");
2899 /* This function adds a structure TYPE to the vector of structures,
2900 if it's not already there. */
2903 add_structure (tree type
)
2905 struct data_structure node
;
2909 type
= TYPE_MAIN_VARIANT (type
);
2911 i
= find_structure (type
);
2913 if (i
!= VEC_length (structure
, structures
))
2916 num_fields
= fields_length (type
);
2918 node
.num_fields
= num_fields
;
2919 node
.fields
= get_fields (type
, num_fields
);
2920 node
.struct_clustering
= NULL
;
2921 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
2922 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
2925 VEC_safe_push (structure
, heap
, structures
, &node
);
2929 fprintf (dump_file
, "\nAdding data structure \"");
2930 print_generic_expr (dump_file
, type
, 0);
2931 fprintf (dump_file
, "\" to data_struct_list.");
2935 /* This function adds an allocation site to alloc_sites hashtable.
2936 The allocation site appears in STMT of function FN_DECL and
2937 allocates the structure represented by STR. */
2940 add_alloc_site (tree fn_decl
, gimple stmt
, d_str str
)
2942 fallocs_t fallocs
= NULL
;
2943 alloc_site_t m_call
;
2949 (fallocs_t
) htab_find_with_hash (alloc_sites
,
2950 fn_decl
, htab_hash_pointer (fn_decl
));
2956 fallocs
= (fallocs_t
)
2957 xmalloc (sizeof (struct func_alloc_sites
));
2958 fallocs
->func
= fn_decl
;
2959 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
2960 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
2961 htab_hash_pointer (fn_decl
), INSERT
);
2964 VEC_safe_push (alloc_site_t
, heap
,
2965 fallocs
->allocs
, &m_call
);
2969 fprintf (dump_file
, "\nAdding stmt ");
2970 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2971 fprintf (dump_file
, " to list of mallocs.");
2975 /* This function returns true if the result of STMT, that contains a call
2976 to an allocation function, is cast to one of the structure types.
2977 STMT should be of the form: T.2 = <alloc_func> (T.1);
2978 If true, I_P contains an index of an allocated structure.
2979 Otherwise I_P contains the length of the vector of structures. */
2982 is_alloc_of_struct (gimple stmt
, unsigned *i_p
)
2988 final_stmt
= get_final_alloc_stmt (stmt
);
2993 /* final_stmt should be of the form:
2994 T.3 = (struct_type *) T.2; */
2996 if (gimple_code (final_stmt
) != GIMPLE_ASSIGN
)
2999 lhs
= gimple_assign_lhs (final_stmt
);
3001 type
= get_type_of_var (lhs
);
3006 if (!POINTER_TYPE_P (type
)
3007 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3010 *i_p
= find_structure (strip_type (type
));
3012 if (*i_p
== VEC_length (structure
, structures
))
3018 /* This function prints non-field and field accesses
3019 of the structure STR. */
3022 dump_accs (d_str str
)
3026 fprintf (dump_file
, "\nAccess sites of struct ");
3027 print_generic_expr (dump_file
, str
->decl
, 0);
3029 for (i
= 0; i
< str
->num_fields
; i
++)
3031 fprintf (dump_file
, "\nAccess site of field ");
3032 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3033 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3034 fprintf (dump_file
, ":\n");
3036 fprintf (dump_file
, "\nGeneral access sites\n");
3037 dump_access_sites (str
->accs
);
3040 /* This function checks whether an access statement, pointed by SLOT,
3041 is a condition we are capable to transform. It returns false if not,
3042 setting bool *DATA to false. */
3045 safe_cond_expr_check (void **slot
, void *data
)
3047 struct access_site
*acc
= *(struct access_site
**) slot
;
3049 if (gimple_code (acc
->stmt
) == GIMPLE_COND
3050 && !is_safe_cond_expr (acc
->stmt
))
3054 fprintf (dump_file
, "\nUnsafe conditional statement ");
3055 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
3057 *(bool *) data
= false;
3063 /* This function excludes statements that are part of allocation sites and
3064 field accesses from the hashtable of general accesses of the structure
3065 type STR. Only accesses that belong to the function represented by
3066 NODE are treated. */
3069 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3071 struct exclude_data dt
;
3073 dt
.fn_decl
= node
->decl
;
3076 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3079 /* Collect accesses to the structure types that appear in basic block BB. */
3082 collect_accesses_in_bb (basic_block bb
)
3084 gimple_stmt_iterator bsi
;
3085 struct walk_stmt_info wi
;
3087 memset (&wi
, 0, sizeof (wi
));
3089 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3091 gimple stmt
= gsi_stmt (bsi
);
3093 /* In asm stmt we cannot always track the arguments,
3094 so we just give up. */
3095 if (gimple_code (stmt
) == GIMPLE_ASM
)
3101 wi
.info
= (void *) stmt
;
3102 walk_gimple_op (stmt
, get_stmt_accesses
, &wi
);
3106 /* This function generates cluster substructure that contains FIELDS.
3107 The cluster added to the set of clusters of the structure STR. */
3110 gen_cluster (sbitmap fields
, d_str str
)
3112 struct field_cluster
*crr_cluster
= NULL
;
3115 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3116 crr_cluster
->sibling
= str
->struct_clustering
;
3117 str
->struct_clustering
= crr_cluster
;
3118 crr_cluster
->fields_in_cluster
= fields
;
3121 /* This function peels a field with the index I from the structure DS. */
3124 peel_field (int i
, d_str ds
)
3126 struct field_cluster
*crr_cluster
= NULL
;
3129 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3130 crr_cluster
->sibling
= ds
->struct_clustering
;
3131 ds
->struct_clustering
= crr_cluster
;
3132 crr_cluster
->fields_in_cluster
=
3133 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3134 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3135 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3138 /* This function calculates maximum field count in
3139 the structure STR. */
3142 get_max_field_count (d_str str
)
3147 for (i
= 0; i
< str
->num_fields
; i
++)
3148 if (str
->fields
[i
].count
> max
)
3149 max
= str
->fields
[i
].count
;
3154 /* Do struct-reorg transformation for individual function
3155 represented by NODE. All structure types relevant
3156 for this function are transformed. */
3159 do_reorg_for_func (struct cgraph_node
*node
)
3161 create_new_local_vars ();
3162 create_new_alloc_sites_for_func (node
);
3163 create_new_accesses_for_func ();
3164 update_ssa (TODO_update_ssa
);
3165 cleanup_tree_cfg ();
3167 /* Free auxiliary data representing local variables. */
3168 free_new_vars_htab (new_local_vars
);
3171 /* Print structure TYPE, its name, if it exists, and body.
3172 INDENT defines the level of indentation (similar
3173 to the option -i of indent command). SHIFT parameter
3174 defines a number of spaces by which a structure will
3175 be shifted right. */
3178 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3179 unsigned HOST_WIDE_INT shift
)
3181 const char *struct_name
;
3184 if (!type
|| !dump_file
)
3187 if (TREE_CODE (type
) != RECORD_TYPE
)
3189 print_generic_expr (dump_file
, type
, 0);
3193 print_shift (shift
);
3194 struct_name
= get_type_name (type
);
3195 fprintf (dump_file
, "struct ");
3197 fprintf (dump_file
, "%s\n",struct_name
);
3198 print_shift (shift
);
3199 fprintf (dump_file
, "{\n");
3201 for (field
= TYPE_FIELDS (type
); field
;
3202 field
= TREE_CHAIN (field
))
3204 unsigned HOST_WIDE_INT s
= indent
;
3205 tree f_type
= TREE_TYPE (field
);
3207 print_shift (shift
);
3209 fprintf (dump_file
, " ");
3210 dump_struct_type (f_type
, indent
, shift
+ indent
);
3211 fprintf(dump_file
, " ");
3212 print_generic_expr (dump_file
, field
, 0);
3213 fprintf(dump_file
, ";\n");
3215 print_shift (shift
);
3216 fprintf (dump_file
, "}\n");
3219 /* This function creates new structure types to replace original type,
3220 indicated by STR->decl. The names of the new structure types are
3221 derived from the original structure type. If the original structure
3222 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3225 create_new_type (d_str str
, int *str_num
)
3227 int cluster_num
= 0;
3229 struct field_cluster
*cluster
= str
->struct_clustering
;
3232 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3238 fields
= create_fields (cluster
, str
->fields
,
3240 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3242 update_fields_mapping (cluster
, new_type
,
3243 str
->fields
, str
->num_fields
);
3245 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3246 cluster
= cluster
->sibling
;
3251 /* This function is a callback for alloc_sites hashtable
3252 traversal. SLOT is a pointer to fallocs_t.
3253 This function frees memory pointed by *SLOT. */
3256 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3258 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3260 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3265 /* Remove structures collected in UNSUITABLE_TYPES
3266 from structures vector. */
3269 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3275 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3276 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3277 if (is_equal_types (str
->decl
, type
))
3279 remove_structure (i
);
3284 /* Exclude structure types with bitfields.
3285 We would not want to interfere with other optimizations
3286 that can be done in this case. The structure types with
3287 bitfields are added to UNSUITABLE_TYPES vector. */
3290 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3295 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3296 check_bitfields (str
, unsuitable_types
);
3299 /* This function checks three types of escape. A structure type escapes:
3301 1. if it's a type of parameter of a local function.
3302 2. if it's a type of function return value.
3303 3. if it escapes as a result of ipa-type-escape analysis.
3305 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3308 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3310 exclude_types_passed_to_local_func (unsuitable_types
);
3311 exclude_returned_types (unsuitable_types
);
3312 exclude_escaping_types_1 (unsuitable_types
);
3315 /* This function analyzes whether the form of
3316 structure is such that we are capable to transform it.
3317 Nested structures are checked here. Unsuitable structure
3318 types are added to UNSUITABLE_TYPE vector. */
3321 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3326 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3327 check_struct_form (str
, unsuitable_types
);
3330 /* This function looks for structure types instantiated in the program.
3331 The candidate types are added to the structures vector.
3332 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3335 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3339 struct varpool_node
*current_varpool
;
3340 struct cgraph_node
*c_node
;
3342 /* Check global variables. */
3343 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3345 var
= current_varpool
->decl
;
3346 if (is_candidate (var
, &type
, unsuitable_types
))
3347 add_structure (type
);
3350 /* Now add structures that are types of function parameters and
3352 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3354 enum availability avail
=
3355 cgraph_function_body_availability (c_node
);
3357 /* We need AVAIL_AVAILABLE for main function. */
3358 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3360 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3362 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3363 var
= TREE_CHAIN (var
))
3364 if (is_candidate (var
, &type
, unsuitable_types
))
3365 add_structure (type
);
3367 /* Check function local variables. */
3368 for (var_list
= fn
->local_decls
; var_list
;
3369 var_list
= TREE_CHAIN (var_list
))
3371 var
= TREE_VALUE (var_list
);
3373 if (is_candidate (var
, &type
, unsuitable_types
))
3374 add_structure (type
);
3380 /* This function returns true if the program contains
3381 a call to user defined allocation function, or other
3382 functions that can interfere with struct-reorg optimizations. */
3385 program_redefines_malloc_p (void)
3387 struct cgraph_node
*c_node
;
3388 struct cgraph_node
*c_node2
;
3389 struct cgraph_edge
*c_edge
;
3393 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3395 fndecl
= c_node
->decl
;
3397 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3399 c_node2
= c_edge
->callee
;
3400 fndecl2
= c_node2
->decl
;
3401 if (is_gimple_call (c_edge
->call_stmt
))
3403 const char * fname
= get_name (fndecl2
);
3405 if ((gimple_call_flags (c_edge
->call_stmt
) & ECF_MALLOC
)
3406 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
)
3407 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
)
3408 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3411 /* Check that there is no __builtin_object_size,
3412 __builtin_offsetof, or realloc's in the program. */
3413 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3414 || !strcmp (fname
, "__builtin_offsetof")
3415 || !strcmp (fname
, "realloc"))
3424 /* In this function we assume that an allocation statement
3426 var = (type_cast) malloc (size);
3428 is converted into the following set of statements:
3432 T.3 = (type_cast) T.2;
3435 In this function we collect into alloc_sites the allocation
3436 sites of variables of structure types that are present
3437 in structures vector. */
3440 collect_alloc_sites (void)
3442 struct cgraph_node
*node
;
3443 struct cgraph_edge
*cs
;
3445 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3446 if (node
->analyzed
&& node
->decl
)
3448 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3450 gimple stmt
= cs
->call_stmt
;
3456 if (is_gimple_call (stmt
)
3457 && (decl
= gimple_call_fndecl (stmt
))
3458 && gimple_call_lhs (stmt
))
3462 if (is_alloc_of_struct (stmt
, &i
))
3464 /* We support only malloc now. */
3465 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3469 str
= VEC_index (structure
, structures
, i
);
3470 add_alloc_site (node
->decl
, stmt
, str
);
3477 "\nUnsupported allocation function ");
3478 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3480 remove_structure (i
);
3489 /* Print collected accesses. */
3492 dump_accesses (void)
3500 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3504 /* This function checks whether the accesses of structures in condition
3505 expressions are of the kind we are capable to transform.
3506 If not, such structures are removed from the vector of structures. */
3509 check_cond_exprs (void)
3515 while (VEC_iterate (structure
, structures
, i
, str
))
3520 htab_traverse (str
->accs
, safe_cond_expr_check
, &safe_p
);
3522 remove_structure (i
);
3528 /* We exclude from non-field accesses of the structure
3529 all statements that will be treated as part of the structure
3530 allocation sites or field accesses. */
3533 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3538 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3539 exclude_alloc_and_field_accs_1 (str
, node
);
3542 /* This function collects accesses of the fields of the structures
3543 that appear at function FN. */
3546 collect_accesses_in_func (struct function
*fn
)
3553 /* Collect accesses for each basic blocks separately. */
3554 FOR_EACH_BB_FN (bb
, fn
)
3555 collect_accesses_in_bb (bb
);
3558 /* This function summarizes counts of the fields into the structure count. */
3561 sum_counts (d_str str
, gcov_type
*hottest
)
3566 for (i
= 0; i
< str
->num_fields
; i
++)
3570 fprintf (dump_file
, "\nCounter of field \"");
3571 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3572 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3573 str
->fields
[i
].count
);
3575 str
->count
+= str
->fields
[i
].count
;
3580 fprintf (dump_file
, "\nCounter of struct \"");
3581 print_generic_expr (dump_file
, str
->decl
, 0);
3582 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3585 if (str
->count
> *hottest
)
3586 *hottest
= str
->count
;
3589 /* This function peels the field into separate structure if it's
3590 sufficiently hot, i.e. if its count provides at least 90% of
3591 the maximum field count in the structure. */
3594 peel_hot_fields (d_str str
)
3596 gcov_type max_field_count
;
3597 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3600 sbitmap_ones (fields_left
);
3602 (gcov_type
) (get_max_field_count (str
)/100)*90;
3604 str
->struct_clustering
= NULL
;
3606 for (i
= 0; i
< str
->num_fields
; i
++)
3608 if (str
->count
>= max_field_count
)
3610 RESET_BIT (fields_left
, i
);
3611 peel_field (i
, str
);
3615 i
= sbitmap_first_set_bit (fields_left
);
3617 gen_cluster (fields_left
, str
);
3619 sbitmap_free (fields_left
);
3622 /* This function is a helper for do_reorg. It goes over
3623 functions in call graph and performs actual transformation
3629 struct cgraph_node
*node
;
3631 /* Initialize the default bitmap obstack. */
3632 bitmap_obstack_initialize (NULL
);
3634 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3635 if (node
->analyzed
&& node
->decl
&& !node
->next_clone
)
3637 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3638 current_function_decl
= node
->decl
;
3640 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3641 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3642 do_reorg_for_func (node
);
3643 free_dominance_info (CDI_DOMINATORS
);
3644 free_dominance_info (CDI_POST_DOMINATORS
);
3645 current_function_decl
= NULL
;
3650 bitmap_obstack_release (NULL
);
3653 /* This function creates new global struct variables.
3654 For each original variable, the set of new variables
3655 is created with the new structure types corresponding
3656 to the structure type of original variable.
3657 Only VAR_DECL variables are treated by this function. */
3660 create_new_global_vars (void)
3662 struct varpool_node
*current_varpool
;
3663 unsigned HOST_WIDE_INT i
;
3664 unsigned HOST_WIDE_INT varpool_size
= 0;
3666 for (i
= 0; i
< 2; i
++)
3669 new_global_vars
= htab_create (varpool_size
,
3670 new_var_hash
, new_var_eq
, NULL
);
3671 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3673 tree var_decl
= current_varpool
->decl
;
3675 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3680 create_new_var (var_decl
, new_global_vars
);
3684 if (new_global_vars
)
3685 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3688 /* Dump all new types generated by this optimization. */
3691 dump_new_types (void)
3700 fprintf (dump_file
, "\nThe following are the new types generated by"
3701 " this optimization:\n");
3703 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3707 fprintf (dump_file
, "\nFor type ");
3708 dump_struct_type (str
->decl
, 2, 0);
3709 fprintf (dump_file
, "\nthe number of new types is %d\n",
3710 VEC_length (tree
, str
->new_types
));
3712 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3713 dump_struct_type (type
, 2, 0);
3717 /* This function creates new types to replace old structure types. */
3720 create_new_types (void)
3726 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3727 create_new_type (str
, &str_num
);
3730 /* Free allocation sites hashtable. */
3733 free_alloc_sites (void)
3736 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3737 htab_delete (alloc_sites
);
3741 /* This function collects structures potential
3742 for peeling transformation, and inserts
3743 them into structures hashtable. */
3746 collect_structures (void)
3748 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3750 structures
= VEC_alloc (structure
, heap
, 32);
3752 /* If program contains user defined mallocs, we give up. */
3753 if (program_redefines_malloc_p ())
3756 /* Build data structures hashtable of all data structures
3758 build_data_structure (&unsuitable_types
);
3760 /* This function analyzes whether the form of
3761 structure is such that we are capable to transform it.
3762 Nested structures are checked here. */
3763 analyze_struct_form (&unsuitable_types
);
3765 /* This function excludes those structure types
3766 that escape compilation unit. */
3767 exclude_escaping_types (&unsuitable_types
);
3769 /* We do not want to change data layout of the structures with bitfields. */
3770 exclude_types_with_bit_fields (&unsuitable_types
);
3772 remove_unsuitable_types (unsuitable_types
);
3773 VEC_free (tree
, heap
, unsuitable_types
);
3776 /* Collect structure allocation sites. In case of arrays
3777 we have nothing to do. */
3780 collect_allocation_sites (void)
3782 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3783 collect_alloc_sites ();
3786 /* This function collects data accesses for the
3787 structures to be transformed. For each structure
3788 field it updates the count field in field_entry. */
3791 collect_data_accesses (void)
3793 struct cgraph_node
*c_node
;
3795 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3797 enum availability avail
= cgraph_function_body_availability (c_node
);
3799 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3801 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3803 if (!c_node
->next_clone
)
3804 collect_accesses_in_func (func
);
3805 exclude_alloc_and_field_accs (c_node
);
3809 check_cond_exprs ();
3810 /* Print collected accesses. */
3814 /* We do not bother to transform cold structures.
3815 Coldness of the structure is defined relatively
3816 to the highest structure count among the structures
3817 to be transformed. It's triggered by the compiler parameter
3819 --param struct-reorg-cold-struct-ratio=<value>
3821 where <value> ranges from 0 to 100. Structures with count ratios
3822 that are less than this parameter are considered to be cold. */
3825 exclude_cold_structs (void)
3827 gcov_type hottest
= 0;
3831 /* We summarize counts of fields of a structure into the structure count. */
3832 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3833 sum_counts (str
, &hottest
);
3835 /* Remove cold structures from structures vector. */
3837 while (VEC_iterate (structure
, structures
, i
, str
))
3838 if (str
->count
* 100 < (hottest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3842 fprintf (dump_file
, "\nThe structure ");
3843 print_generic_expr (dump_file
, str
->decl
, 0);
3844 fprintf (dump_file
, " is cold.");
3846 remove_structure (i
);
3852 /* This function decomposes original structure into substructures,
3861 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3862 peel_hot_fields (str
);
3866 /* Do the actual transformation for each structure
3867 from the structures hashtable. */
3872 /* Check that there is a work to do. */
3873 if (!VEC_length (structure
, structures
))
3876 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3883 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3884 VEC_length (structure
, structures
));
3888 /* Generate new types. */
3889 create_new_types ();
3892 /* Create new global variables. */
3893 create_new_global_vars ();
3894 dump_new_vars (new_global_vars
);
3896 /* Decompose structures for each function separately. */
3899 /* Free auxiliary data collected for global variables. */
3900 free_new_vars_htab (new_global_vars
);
3903 /* Free all auxiliary data used by this optimization. */
3906 free_data_structs (void)
3909 free_alloc_sites ();
3912 /* Perform structure decomposition (peeling). */
3915 reorg_structs (void)
3919 /* Collect structure types. */
3920 collect_structures ();
3922 /* Collect structure allocation sites. */
3923 collect_allocation_sites ();
3925 /* Collect structure accesses. */
3926 collect_data_accesses ();
3928 /* We transform only hot structures. */
3929 exclude_cold_structs ();
3932 /* Decompose structures into substructures, i.e. clusters. */
3936 /* Do the actual transformation for each structure
3937 from the structures hashtable. */
3940 /* Free all auxiliary data used by this optimization. */
3941 free_data_structs ();
3944 /* Struct-reorg optimization entry point function. */
3947 reorg_structs_drive (void)
3953 /* Struct-reorg optimization gate function. */
3956 struct_reorg_gate (void)
3958 return flag_ipa_struct_reorg
3959 && flag_whole_program
3963 struct simple_ipa_opt_pass pass_ipa_struct_reorg
=
3967 "ipa_struct_reorg", /* name */
3968 struct_reorg_gate
, /* gate */
3969 reorg_structs_drive
, /* execute */
3972 0, /* static_pass_number */
3973 TV_INTEGRATION
, /* tv_id */
3974 0, /* properties_required */
3975 0, /* properties_provided */
3976 0, /* properties_destroyed */
3977 TODO_verify_ssa
, /* todo_flags_start */
3978 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */