1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008, 2009 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 3, 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 COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
31 #include "tree-inline.h"
32 #include "tree-flow.h"
33 #include "tree-flow-inline.h"
34 #include "langhooks.h"
35 #include "pointer-set.h"
42 #include "diagnostic.h"
48 #include "basic-block.h"
49 #include "tree-iterator.h"
50 #include "tree-pass.h"
51 #include "ipa-struct-reorg.h"
53 #include "ipa-type-escape.h"
54 #include "tree-dump.h"
57 /* This optimization implements structure peeling.
59 For example, given a structure type:
67 it can be peeled into two structure types as follows:
69 typedef struct and typedef struct
75 or can be fully peeled:
92 When structure type is peeled all instances and their accesses
93 in the program are updated accordingly. For example, if there is
98 and structure type str_t was peeled into two structures str_t_0
99 and str_t_1 as it was shown above, then array A will be replaced
100 by two arrays as follows:
105 The field access of field a of element i of array A: A[i].a will be
106 replaced by an access to field a of element i of array A_0: A_0[i].a.
108 This optimization also supports dynamically allocated arrays.
109 If array of structures was allocated by malloc function:
111 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
113 the allocation site will be replaced to reflect new structure types:
115 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
116 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
118 The field access through the pointer p[i].a will be changed by p_0[i].a.
120 The goal of structure peeling is to improve spatial locality.
121 For example, if one of the fields of a structure is accessed frequently
124 for (i = 0; i < N; i++)
129 the allocation of field a of str_t contiguously in memory will
130 increase the chances of fetching the field from cache.
132 The analysis part of this optimization is based on the frequency of
133 field accesses, which are collected all over the program.
134 Then the fields with the frequencies that satisfy the following condition
135 get peeled out of the structure:
137 freq(f) > C * max_field_freq_in_struct
139 where max_field_freq_in_struct is the maximum field frequency
140 in the structure. C is a constant defining which portion of
141 max_field_freq_in_struct the fields should have in order to be peeled.
143 If profiling information is provided, it is used to calculate the
144 frequency of field accesses. Otherwise, the structure is fully peeled.
146 IPA type-escape analysis is used to determine when it is safe
149 The optimization is activated by flag -fipa-struct-reorg. */
151 /* New variables created by this optimization.
152 When doing struct peeling, each variable of
153 the original struct type will be replaced by
154 the set of new variables corresponding to
155 the new structure types. */
156 struct new_var_data
{
157 /* VAR_DECL for original struct type. */
159 /* Vector of new variables. */
160 VEC(tree
, heap
) *new_vars
;
163 typedef struct new_var_data
*new_var
;
164 typedef const struct new_var_data
*const_new_var
;
166 /* This structure represents allocation site of the structure. */
167 typedef struct alloc_site
173 DEF_VEC_O (alloc_site_t
);
174 DEF_VEC_ALLOC_O (alloc_site_t
, heap
);
176 /* Allocation sites that belong to the same function. */
177 struct func_alloc_sites
180 /* Vector of allocation sites for function. */
181 VEC (alloc_site_t
, heap
) *allocs
;
184 typedef struct func_alloc_sites
*fallocs_t
;
185 typedef const struct func_alloc_sites
*const_fallocs_t
;
187 /* All allocation sites in the program. */
188 htab_t alloc_sites
= NULL
;
190 /* New global variables. Generated once for whole program. */
191 htab_t new_global_vars
;
193 /* New local variables. Generated per-function. */
194 htab_t new_local_vars
;
196 /* Vector of structures to be transformed. */
197 typedef struct data_structure structure
;
198 DEF_VEC_O (structure
);
199 DEF_VEC_ALLOC_O (structure
, heap
);
200 VEC (structure
, heap
) *structures
;
202 /* Forward declarations. */
203 static bool is_equal_types (tree
, tree
);
205 /* Strip structure TYPE from pointers and arrays. */
208 strip_type (tree type
)
210 gcc_assert (TYPE_P (type
));
212 while (POINTER_TYPE_P (type
)
213 || TREE_CODE (type
) == ARRAY_TYPE
)
214 type
= TREE_TYPE (type
);
219 /* This function returns type of VAR. */
222 get_type_of_var (tree var
)
227 if (TREE_CODE (var
) == PARM_DECL
)
228 return DECL_ARG_TYPE (var
);
230 return TREE_TYPE (var
);
233 /* Set of actions we do for each newly generated STMT. */
236 finalize_stmt (gimple stmt
)
239 mark_symbols_for_renaming (stmt
);
242 /* This function finalizes STMT and appends it to the list STMTS. */
245 finalize_stmt_and_append (gimple_seq
*stmts
, gimple stmt
)
247 gimple_seq_add_stmt (stmts
, stmt
);
248 finalize_stmt (stmt
);
251 /* This function returns true if two fields FIELD1 and FIELD2 are
252 semantically equal, and false otherwise. */
255 compare_fields (tree field1
, tree field2
)
257 if (DECL_NAME (field1
) && DECL_NAME (field2
))
259 const char *name1
= IDENTIFIER_POINTER (DECL_NAME (field1
));
260 const char *name2
= IDENTIFIER_POINTER (DECL_NAME (field2
));
262 gcc_assert (name1
&& name2
);
264 if (strcmp (name1
, name2
))
268 else if (DECL_NAME (field1
) || DECL_NAME (field2
))
271 if (!is_equal_types (TREE_TYPE (field1
), TREE_TYPE (field2
)))
277 /* Given structure type SRT_TYPE and field FIELD,
278 this function is looking for a field with the same name
279 and type as FIELD in STR_TYPE. It returns it if found,
280 or NULL_TREE otherwise. */
283 find_field_in_struct_1 (tree str_type
, tree field
)
287 if (!DECL_NAME (field
))
290 for (str_field
= TYPE_FIELDS (str_type
); str_field
;
291 str_field
= TREE_CHAIN (str_field
))
294 if (!DECL_NAME (str_field
))
297 if (compare_fields (field
, str_field
))
304 /* Given a field declaration FIELD_DECL, this function
305 returns corresponding field entry in structure STR. */
307 static struct field_entry
*
308 find_field_in_struct (d_str str
, tree field_decl
)
312 tree field
= find_field_in_struct_1 (str
->decl
, field_decl
);
314 for (i
= 0; i
< str
->num_fields
; i
++)
315 if (str
->fields
[i
].decl
== field
)
316 return &(str
->fields
[i
]);
321 /* This function checks whether ARG is a result of multiplication
322 of some number by STRUCT_SIZE. If yes, the function returns true
323 and this number is filled into NUM. */
326 is_result_of_mult (tree arg
, tree
*num
, tree struct_size
)
328 gimple size_def_stmt
= SSA_NAME_DEF_STMT (arg
);
330 /* If the allocation statement was of the form
331 D.2229_10 = <alloc_func> (D.2228_9);
332 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
334 if (size_def_stmt
&& is_gimple_assign (size_def_stmt
))
336 tree lhs
= gimple_assign_lhs (size_def_stmt
);
338 /* We expect temporary here. */
339 if (!is_gimple_reg (lhs
))
342 if (gimple_assign_rhs_code (size_def_stmt
) == MULT_EXPR
)
344 tree arg0
= gimple_assign_rhs1 (size_def_stmt
);
345 tree arg1
= gimple_assign_rhs2 (size_def_stmt
);
347 if (operand_equal_p (arg0
, struct_size
, OEP_ONLY_CONST
))
353 if (operand_equal_p (arg1
, struct_size
, OEP_ONLY_CONST
))
366 /* This function returns true if access ACC corresponds to the pattern
367 generated by compiler when an address of element i of an array
368 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
369 pattern is recognized correctly, this function returns true
370 and fills missing fields in ACC. Otherwise it returns false. */
373 decompose_indirect_ref_acc (tree str_decl
, struct field_access_site
*acc
)
376 tree struct_size
, op0
, op1
;
378 enum tree_code rhs_code
;
380 ref_var
= TREE_OPERAND (acc
->ref
, 0);
382 if (TREE_CODE (ref_var
) != SSA_NAME
)
385 acc
->ref_def_stmt
= SSA_NAME_DEF_STMT (ref_var
);
386 if (!(acc
->ref_def_stmt
)
387 || (gimple_code (acc
->ref_def_stmt
) != GIMPLE_ASSIGN
))
390 rhs_code
= gimple_assign_rhs_code (acc
->ref_def_stmt
);
392 if (rhs_code
!= PLUS_EXPR
393 && rhs_code
!= MINUS_EXPR
394 && rhs_code
!= POINTER_PLUS_EXPR
)
397 op0
= gimple_assign_rhs1 (acc
->ref_def_stmt
);
398 op1
= gimple_assign_rhs2 (acc
->ref_def_stmt
);
400 if (!is_array_access_through_pointer_and_index (rhs_code
, op0
, op1
,
401 &acc
->base
, &acc
->offset
,
406 before_cast
= SINGLE_SSA_TREE_OPERAND (acc
->cast_stmt
, SSA_OP_USE
);
408 before_cast
= acc
->offset
;
414 if (SSA_NAME_IS_DEFAULT_DEF (before_cast
))
417 struct_size
= TYPE_SIZE_UNIT (str_decl
);
419 if (!is_result_of_mult (before_cast
, &acc
->num
, struct_size
))
426 /* This function checks whether the access ACC of structure type STR
427 is of the form suitable for transformation. If yes, it returns true.
431 decompose_access (tree str_decl
, struct field_access_site
*acc
)
433 gcc_assert (acc
->ref
);
435 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
)
436 return decompose_indirect_ref_acc (str_decl
, acc
);
437 else if (TREE_CODE (acc
->ref
) == ARRAY_REF
)
439 else if (TREE_CODE (acc
->ref
) == VAR_DECL
)
445 /* This function creates empty field_access_site node. */
447 static inline struct field_access_site
*
448 make_field_acc_node (void)
450 int size
= sizeof (struct field_access_site
);
452 return (struct field_access_site
*) xcalloc (1, size
);
455 /* This function returns the structure field access, defined by STMT,
456 if it is already in hashtable of function accesses F_ACCS. */
458 static struct field_access_site
*
459 is_in_field_accs (gimple stmt
, htab_t f_accs
)
461 return (struct field_access_site
*)
462 htab_find_with_hash (f_accs
, stmt
, htab_hash_pointer (stmt
));
465 /* This function adds an access ACC to the hashtable
466 F_ACCS of field accesses. */
469 add_field_acc_to_acc_sites (struct field_access_site
*acc
,
474 gcc_assert (!is_in_field_accs (acc
->stmt
, f_accs
));
475 slot
= htab_find_slot_with_hash (f_accs
, acc
->stmt
,
476 htab_hash_pointer (acc
->stmt
),
481 /* This function adds the VAR to vector of variables of
482 an access site defined by statement STMT. If access entry
483 with statement STMT does not exist in hashtable of
484 accesses ACCS, this function creates it. */
487 add_access_to_acc_sites (gimple stmt
, tree var
, htab_t accs
)
489 struct access_site
*acc
;
491 acc
= (struct access_site
*)
492 htab_find_with_hash (accs
, stmt
, htab_hash_pointer (stmt
));
498 acc
= (struct access_site
*) xmalloc (sizeof (struct access_site
));
500 acc
->vars
= VEC_alloc (tree
, heap
, 10);
501 slot
= htab_find_slot_with_hash (accs
, stmt
,
502 htab_hash_pointer (stmt
), INSERT
);
506 VEC_safe_push (tree
, heap
, acc
->vars
, var
);
509 /* This function adds NEW_DECL to function
510 referenced vars, and marks it for renaming. */
513 finalize_var_creation (tree new_decl
)
515 add_referenced_var (new_decl
);
516 mark_sym_for_renaming (new_decl
);
519 /* This function finalizes VAR creation if it is a global VAR_DECL. */
522 finalize_global_creation (tree var
)
524 if (TREE_CODE (var
) == VAR_DECL
525 && is_global_var (var
))
526 finalize_var_creation (var
);
529 /* This function inserts NEW_DECL to varpool. */
532 insert_global_to_varpool (tree new_decl
)
534 struct varpool_node
*new_node
;
536 new_node
= varpool_node (new_decl
);
537 notice_global_symbol (new_decl
);
538 varpool_mark_needed_node (new_node
);
539 varpool_finalize_decl (new_decl
);
542 /* This function finalizes the creation of new variables,
543 defined by *SLOT->new_vars. */
546 finalize_new_vars_creation (void **slot
, void *data ATTRIBUTE_UNUSED
)
548 new_var n_var
= *(new_var
*) slot
;
552 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
553 finalize_var_creation (var
);
557 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
558 It returns it, if found, and NULL_TREE otherwise. */
561 find_var_in_new_vars_vec (new_var var
, tree new_type
)
566 for (i
= 0; VEC_iterate (tree
, var
->new_vars
, i
, n_var
); i
++)
568 tree type
= strip_type(get_type_of_var (n_var
));
571 if (type
== new_type
)
578 /* This function returns new_var node, the orig_var of which is DECL.
579 It looks for new_var's in NEW_VARS_HTAB. If not found,
580 the function returns NULL. */
583 is_in_new_vars_htab (tree decl
, htab_t new_vars_htab
)
585 return (new_var
) htab_find_with_hash (new_vars_htab
, decl
,
589 /* Given original variable ORIG_VAR, this function returns
590 new variable corresponding to it of NEW_TYPE type. */
593 find_new_var_of_type (tree orig_var
, tree new_type
)
596 gcc_assert (orig_var
&& new_type
);
598 if (TREE_CODE (orig_var
) == SSA_NAME
)
599 orig_var
= SSA_NAME_VAR (orig_var
);
601 var
= is_in_new_vars_htab (orig_var
, new_global_vars
);
603 var
= is_in_new_vars_htab (orig_var
, new_local_vars
);
605 return find_var_in_new_vars_vec (var
, new_type
);
608 /* This function generates stmt:
609 res = NUM * sizeof(TYPE) and returns it.
610 res is filled into RES. */
613 gen_size (tree num
, tree type
, tree
*res
)
615 tree struct_size
= TYPE_SIZE_UNIT (type
);
616 HOST_WIDE_INT struct_size_int
= TREE_INT_CST_LOW (struct_size
);
619 *res
= create_tmp_var (TREE_TYPE (num
), NULL
);
622 add_referenced_var (*res
);
624 if (exact_log2 (struct_size_int
) == -1)
626 tree size
= build_int_cst (TREE_TYPE (num
), struct_size_int
);
627 new_stmt
= gimple_build_assign (*res
, fold_build2 (MULT_EXPR
,
633 tree C
= build_int_cst (TREE_TYPE (num
), exact_log2 (struct_size_int
));
635 new_stmt
= gimple_build_assign (*res
, fold_build2 (LSHIFT_EXPR
,
640 finalize_stmt (new_stmt
);
644 /* This function generates and returns a statement, that cast variable
645 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
646 into RES_P. ORIG_CAST_STMT is the original cast statement. */
649 gen_cast_stmt (tree before_cast
, tree new_type
, gimple orig_cast_stmt
,
655 lhs
= gimple_assign_lhs (orig_cast_stmt
);
656 new_lhs
= find_new_var_of_type (lhs
, new_type
);
657 gcc_assert (new_lhs
);
659 new_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, new_lhs
, before_cast
, 0);
660 finalize_stmt (new_stmt
);
665 /* This function builds an edge between BB and E->dest and updates
666 phi nodes of E->dest. It returns newly created edge. */
669 make_edge_and_fix_phis_of_dest (basic_block bb
, edge e
)
673 gimple_stmt_iterator si
;
675 new_e
= make_edge (bb
, e
->dest
, e
->flags
);
677 for (si
= gsi_start_phis (new_e
->dest
); !gsi_end_p (si
); gsi_next (&si
))
679 gimple phi
= gsi_stmt (si
);
680 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
681 add_phi_arg (phi
, arg
, new_e
, gimple_phi_arg_location_from_edge (phi
, e
));
687 /* This function inserts NEW_STMT before STMT. */
690 insert_before_stmt (gimple stmt
, gimple new_stmt
)
692 gimple_stmt_iterator bsi
;
694 if (!stmt
|| !new_stmt
)
697 bsi
= gsi_for_stmt (stmt
);
698 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
701 /* Insert NEW_STMTS after STMT. */
704 insert_seq_after_stmt (gimple stmt
, gimple_seq new_stmts
)
706 gimple_stmt_iterator bsi
;
708 if (!stmt
|| !new_stmts
)
711 bsi
= gsi_for_stmt (stmt
);
712 gsi_insert_seq_after (&bsi
, new_stmts
, GSI_SAME_STMT
);
715 /* Insert NEW_STMT after STMT. */
718 insert_after_stmt (gimple stmt
, gimple new_stmt
)
720 gimple_stmt_iterator bsi
;
722 if (!stmt
|| !new_stmt
)
725 bsi
= gsi_for_stmt (stmt
);
726 gsi_insert_after (&bsi
, new_stmt
, GSI_SAME_STMT
);
729 /* This function returns vector of allocation sites
730 that appear in function FN_DECL. */
733 get_fallocs (tree fn_decl
)
735 return (fallocs_t
) htab_find_with_hash (alloc_sites
, fn_decl
,
736 htab_hash_pointer (fn_decl
));
739 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
740 and it is a part of allocation of a structure,
741 then it is usually followed by a cast stmt
742 p_8 = (struct str_t *) D.2225_7;
743 which is returned by this function. */
746 get_final_alloc_stmt (gimple alloc_stmt
)
755 if (!is_gimple_call (alloc_stmt
))
758 alloc_res
= gimple_get_lhs (alloc_stmt
);
760 if (TREE_CODE (alloc_res
) != SSA_NAME
)
763 if (!single_imm_use (alloc_res
, &use_p
, &final_stmt
))
769 /* This function returns true if STMT is one of allocation
770 sites of function FN_DECL. It returns false otherwise. */
773 is_part_of_malloc (gimple stmt
, tree fn_decl
)
775 fallocs_t fallocs
= get_fallocs (fn_decl
);
782 for (i
= 0; VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
); i
++)
783 if (call
->stmt
== stmt
784 || get_final_alloc_stmt (call
->stmt
) == stmt
)
790 /* Auxiliary structure for a lookup over field accesses. */
791 struct find_stmt_data
797 /* This function looks for DATA->stmt among
798 the statements involved in the field access,
799 defined by SLOT. It stops when it's found. */
802 find_in_field_accs (void **slot
, void *data
)
804 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
805 gimple stmt
= ((struct find_stmt_data
*)data
)->stmt
;
807 if (f_acc
->stmt
== stmt
808 || f_acc
->ref_def_stmt
== stmt
809 || f_acc
->cast_stmt
== stmt
)
811 ((struct find_stmt_data
*)data
)->found
= true;
818 /* This function checks whether STMT is part of field
819 accesses of structure STR. It returns true, if found,
820 and false otherwise. */
823 is_part_of_field_access (gimple stmt
, d_str str
)
827 for (i
= 0; i
< str
->num_fields
; i
++)
829 struct find_stmt_data data
;
833 if (str
->fields
[i
].acc_sites
)
834 htab_traverse (str
->fields
[i
].acc_sites
, find_in_field_accs
, &data
);
843 /* Auxiliary data for exclude_from_accs function. */
851 /* This function returns component_ref with the BASE and
852 field named FIELD_ID from structure TYPE. */
855 build_comp_ref (tree base
, tree field_id
, tree type
)
861 /* Find field of structure type with the same name as field_id. */
862 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
864 if (DECL_NAME (field
) == field_id
)
873 return build3 (COMPONENT_REF
, TREE_TYPE (field
), base
, field
, NULL_TREE
);
877 /* This struct represent data used for walk_tree
878 called from function find_pos_in_stmt.
879 - ref is a tree to be found,
880 - and pos is a pointer that points to ref in stmt. */
889 /* This is a callback function for walk_tree, called from
890 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
891 When *TP is equal to DATA->ref, the walk_tree stops,
892 and found position, equal to TP, is assigned to DATA->pos. */
895 find_pos_in_stmt_1 (tree
*tp
, int *walk_subtrees
, void * data
)
897 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
898 struct ref_pos
*r_pos
= (struct ref_pos
*) wi
->info
;
899 tree ref
= r_pos
->ref
;
902 if (t
== ref
|| (TREE_CODE (t
) == SSA_NAME
&& SSA_NAME_VAR (t
) == ref
))
908 r_pos
->container
= t
;
914 /* This function looks for the pointer of REF in STMT,
915 It returns it, if found, and NULL otherwise. */
918 find_pos_in_stmt (gimple stmt
, tree ref
, struct ref_pos
* r_pos
)
920 struct walk_stmt_info wi
;
924 r_pos
->container
= NULL_TREE
;
925 memset (&wi
, 0, sizeof (wi
));
927 walk_gimple_op (stmt
, find_pos_in_stmt_1
, &wi
);
932 /* This structure is used to represent array
933 or pointer-to wrappers of structure type.
934 For example, if type1 is structure type,
935 then for type1 ** we generate two type_wrapper
936 structures with wrap = 0 each one.
937 It's used to unwind the original type up to
938 structure type, replace it with the new structure type
939 and wrap it back in the opposite order. */
941 typedef struct type_wrapper
943 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
946 /* Relevant for arrays as domain or index. */
950 DEF_VEC_O (type_wrapper_t
);
951 DEF_VEC_ALLOC_O (type_wrapper_t
, heap
);
953 /* This function replace field access ACC by the new
954 field access of structure type NEW_TYPE. */
957 replace_field_acc (struct field_access_site
*acc
, tree new_type
)
959 tree ref_var
= acc
->ref
;
964 tree field_id
= DECL_NAME (acc
->field_decl
);
965 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
966 type_wrapper_t
*wr_p
= NULL
;
967 struct ref_pos r_pos
;
969 while (TREE_CODE (ref_var
) == INDIRECT_REF
970 || TREE_CODE (ref_var
) == ARRAY_REF
)
974 if ( TREE_CODE (ref_var
) == INDIRECT_REF
)
982 wr
.domain
= TREE_OPERAND (ref_var
, 1);
985 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
986 ref_var
= TREE_OPERAND (ref_var
, 0);
989 new_ref
= find_new_var_of_type (ref_var
, new_type
);
990 finalize_global_creation (new_ref
);
992 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
994 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
996 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
997 if (wr_p
->wrap
) /* Array. */
998 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
999 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
1001 new_ref
= build1 (INDIRECT_REF
, type
, new_ref
);
1002 VEC_pop (type_wrapper_t
, wrapper
);
1005 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
1006 VEC_free (type_wrapper_t
, heap
, wrapper
);
1008 if (is_gimple_assign (acc
->stmt
))
1010 lhs
= gimple_assign_lhs (acc
->stmt
);
1011 rhs
= gimple_assign_rhs1 (acc
->stmt
);
1013 if (lhs
== acc
->comp_ref
)
1014 gimple_assign_set_lhs (acc
->stmt
, new_acc
);
1015 else if (rhs
== acc
->comp_ref
)
1016 gimple_assign_set_rhs1 (acc
->stmt
, new_acc
);
1019 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
, &r_pos
);
1026 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
, &r_pos
);
1031 finalize_stmt (acc
->stmt
);
1034 /* This function replace field access ACC by a new field access
1035 of structure type NEW_TYPE. */
1038 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1041 if (TREE_CODE (acc
->ref
) == INDIRECT_REF
1042 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1043 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1044 replace_field_acc (acc
, new_type
);
1049 /* This function looks for d_str, represented by TYPE, in the structures
1050 vector. If found, it returns an index of found structure. Otherwise
1051 it returns a length of the structures vector. */
1054 find_structure (tree type
)
1059 type
= TYPE_MAIN_VARIANT (type
);
1061 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
1062 if (is_equal_types (str
->decl
, type
))
1065 return VEC_length (structure
, structures
);
1068 /* In this function we create new statements that have the same
1069 form as ORIG_STMT, but of type NEW_TYPE. The statements
1070 treated by this function are simple assignments,
1071 like assignments: p.8_7 = p; or statements with rhs of
1072 tree codes PLUS_EXPR and MINUS_EXPR. */
1075 create_base_plus_offset (gimple orig_stmt
, tree new_type
, tree offset
)
1080 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1082 lhs
= gimple_assign_lhs (orig_stmt
);
1084 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1085 || TREE_CODE (lhs
) == SSA_NAME
);
1087 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1088 gcc_assert (new_lhs
);
1089 finalize_var_creation (new_lhs
);
1091 switch (gimple_assign_rhs_code (orig_stmt
))
1095 case POINTER_PLUS_EXPR
:
1097 tree op0
= gimple_assign_rhs1 (orig_stmt
);
1098 tree op1
= gimple_assign_rhs2 (orig_stmt
);
1099 unsigned str0
, str1
;
1100 unsigned length
= VEC_length (structure
, structures
);
1103 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1104 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1105 gcc_assert ((str0
!= length
) || (str1
!= length
));
1108 new_op0
= find_new_var_of_type (op0
, new_type
);
1110 new_op1
= find_new_var_of_type (op1
, new_type
);
1123 new_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt
),
1124 new_lhs
, new_op0
, new_op1
);
1125 finalize_stmt (new_stmt
);
1130 /* Given a field access F_ACC of the FIELD, this function
1131 replaces it by the new field access. */
1134 create_new_field_access (struct field_access_site
*f_acc
,
1135 struct field_entry field
)
1137 tree new_type
= field
.field_mapping
;
1142 tree cast_res
= NULL
;
1146 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1147 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1150 if (f_acc
->cast_stmt
)
1152 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1153 f_acc
->cast_stmt
, &cast_res
);
1154 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1157 if (f_acc
->ref_def_stmt
)
1165 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1167 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1170 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1171 D.2162_18 by an appropriate variable of new_type type. */
1172 replace_field_access_stmt (f_acc
, new_type
);
1175 /* This function creates a new condition statement
1176 corresponding to the original COND_STMT, adds new basic block
1177 and redirects condition edges. NEW_VAR is a new condition
1178 variable located in the condition statement at the position POS. */
1181 create_new_stmts_for_cond_expr_1 (tree new_var
, gimple cond_stmt
, unsigned pos
)
1184 edge true_e
= NULL
, false_e
= NULL
;
1186 gimple_stmt_iterator si
;
1188 extract_true_false_edges_from_block (gimple_bb (cond_stmt
),
1191 new_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
1192 pos
== 0 ? new_var
: gimple_cond_lhs (cond_stmt
),
1193 pos
== 1 ? new_var
: gimple_cond_rhs (cond_stmt
),
1197 finalize_stmt (new_stmt
);
1199 /* Create new basic block after bb. */
1200 new_bb
= create_empty_bb (gimple_bb (cond_stmt
));
1202 /* Add new condition stmt to the new_bb. */
1203 si
= gsi_start_bb (new_bb
);
1204 gsi_insert_after (&si
, new_stmt
, GSI_NEW_STMT
);
1206 /* Create false and true edges from new_bb. */
1207 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1208 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1210 /* Redirect one of original edges to point to new_bb. */
1211 if (gimple_cond_code (cond_stmt
) == NE_EXPR
)
1212 redirect_edge_succ (true_e
, new_bb
);
1214 redirect_edge_succ (false_e
, new_bb
);
1217 /* This function creates new condition statements corresponding
1218 to original condition STMT, one for each new type, and
1219 recursively redirect edges to newly generated basic blocks. */
1222 create_new_stmts_for_cond_expr (gimple stmt
)
1224 tree arg0
, arg1
, arg
;
1225 unsigned str0
, str1
;
1231 unsigned length
= VEC_length (structure
, structures
);
1233 gcc_assert (gimple_cond_code (stmt
) == EQ_EXPR
1234 || gimple_cond_code (stmt
) == NE_EXPR
);
1236 arg0
= gimple_cond_lhs (stmt
);
1237 arg1
= gimple_cond_rhs (stmt
);
1239 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1240 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1242 s0
= (str0
!= length
) ? true : false;
1243 s1
= (str1
!= length
) ? true : false;
1245 gcc_assert (s0
|| s1
);
1246 /* For now we allow only comparison with 0 or NULL. */
1247 gcc_assert (integer_zerop (arg0
) || integer_zerop (arg1
));
1249 str
= integer_zerop (arg0
) ?
1250 VEC_index (structure
, structures
, str1
):
1251 VEC_index (structure
, structures
, str0
);
1252 arg
= integer_zerop (arg0
) ? arg1
: arg0
;
1253 pos
= integer_zerop (arg0
) ? 1 : 0;
1255 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1259 new_arg
= find_new_var_of_type (arg
, type
);
1260 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1264 /* This function looks for VAR in STMT, and replace it with NEW_VAR.
1265 If needed, it wraps NEW_VAR in pointers and indirect references
1266 before insertion. */
1269 insert_new_var_in_stmt (gimple stmt
, tree var
, tree new_var
)
1271 struct ref_pos r_pos
;
1274 pos
= find_pos_in_stmt (stmt
, var
, &r_pos
);
1277 while (r_pos
.container
&& (TREE_CODE(r_pos
.container
) == INDIRECT_REF
1278 || TREE_CODE(r_pos
.container
) == ADDR_EXPR
))
1280 tree type
= TREE_TYPE (TREE_TYPE (new_var
));
1282 if (TREE_CODE(r_pos
.container
) == INDIRECT_REF
)
1283 new_var
= build1 (INDIRECT_REF
, type
, new_var
);
1285 new_var
= build_fold_addr_expr (new_var
);
1286 pos
= find_pos_in_stmt (stmt
, r_pos
.container
, &r_pos
);
1293 /* Create a new general access to replace original access ACC
1294 for structure type NEW_TYPE. */
1297 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1299 gimple old_stmt
= acc
->stmt
;
1301 gimple new_stmt
= gimple_copy (old_stmt
);
1304 /* We are really building a new stmt, clear the virtual operands. */
1305 if (gimple_has_mem_ops (new_stmt
))
1307 gimple_set_vuse (new_stmt
, NULL_TREE
);
1308 gimple_set_vdef (new_stmt
, NULL_TREE
);
1311 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
1313 tree new_var
= find_new_var_of_type (var
, new_type
);
1314 tree lhs
, rhs
= NULL_TREE
;
1316 gcc_assert (new_var
);
1317 finalize_var_creation (new_var
);
1319 if (is_gimple_assign (new_stmt
))
1321 lhs
= gimple_assign_lhs (new_stmt
);
1323 if (TREE_CODE (lhs
) == SSA_NAME
)
1324 lhs
= SSA_NAME_VAR (lhs
);
1325 if (gimple_assign_rhs_code (new_stmt
) == SSA_NAME
)
1326 rhs
= SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt
));
1328 /* It can happen that rhs is a constructor.
1329 Then we have to replace it to be of new_type. */
1330 if (gimple_assign_rhs_code (new_stmt
) == CONSTRUCTOR
)
1332 /* Dealing only with empty constructors right now. */
1333 gcc_assert (VEC_empty (constructor_elt
,
1334 CONSTRUCTOR_ELTS (rhs
)));
1335 rhs
= build_constructor (new_type
, 0);
1336 gimple_assign_set_rhs1 (new_stmt
, rhs
);
1340 gimple_assign_set_lhs (new_stmt
, new_var
);
1341 else if (rhs
== var
)
1342 gimple_assign_set_rhs1 (new_stmt
, new_var
);
1344 insert_new_var_in_stmt (new_stmt
, var
, new_var
);
1347 insert_new_var_in_stmt (new_stmt
, var
, new_var
);
1350 finalize_stmt (new_stmt
);
1354 /* For each new type in STR this function creates new general accesses
1355 corresponding to the original access ACC. */
1358 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1361 gimple stmt
= acc
->stmt
;
1364 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
1368 new_stmt
= create_general_new_stmt (acc
, type
);
1369 insert_after_stmt (stmt
, new_stmt
);
1373 /* This function creates a new general access of structure STR
1374 to replace the access ACC. */
1377 create_new_general_access (struct access_site
*acc
, d_str str
)
1379 gimple stmt
= acc
->stmt
;
1380 switch (gimple_code (stmt
))
1383 create_new_stmts_for_cond_expr (stmt
);
1387 create_new_stmts_for_general_acc (acc
, str
);
1391 /* Auxiliary data for creation of accesses. */
1392 struct create_acc_data
1399 /* This function creates a new general access, defined by SLOT.
1400 DATA is a pointer to create_acc_data structure. */
1403 create_new_acc (void **slot
, void *data
)
1405 struct access_site
*acc
= *(struct access_site
**) slot
;
1406 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1407 d_str str
= ((struct create_acc_data
*)data
)->str
;
1409 if (gimple_bb (acc
->stmt
) == bb
)
1410 create_new_general_access (acc
, str
);
1414 /* This function creates a new field access, defined by SLOT.
1415 DATA is a pointer to create_acc_data structure. */
1418 create_new_field_acc (void **slot
, void *data
)
1420 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1421 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1422 d_str str
= ((struct create_acc_data
*)data
)->str
;
1423 int i
= ((struct create_acc_data
*)data
)->field_index
;
1425 if (gimple_bb (f_acc
->stmt
) == bb
)
1426 create_new_field_access (f_acc
, str
->fields
[i
]);
1430 /* This function creates new accesses for the structure
1431 type STR in basic block BB. */
1434 create_new_accs_for_struct (d_str str
, basic_block bb
)
1437 struct create_acc_data dt
;
1441 dt
.field_index
= -1;
1443 for (i
= 0; i
< str
->num_fields
; i
++)
1447 if (str
->fields
[i
].acc_sites
)
1448 htab_traverse (str
->fields
[i
].acc_sites
,
1449 create_new_field_acc
, &dt
);
1452 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1455 /* This function inserts new variables from new_var,
1456 defined by SLOT, into varpool. */
1459 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1461 new_var n_var
= *(new_var
*) slot
;
1465 for (i
= 0; VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1466 insert_global_to_varpool (var
);
1470 /* This function prints a field access site, defined by SLOT. */
1473 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1475 struct field_access_site
*f_acc
=
1476 *(struct field_access_site
**) slot
;
1478 fprintf(dump_file
, "\n");
1480 print_gimple_stmt (dump_file
, f_acc
->stmt
, 0, 0);
1481 if (f_acc
->ref_def_stmt
)
1482 print_gimple_stmt (dump_file
, f_acc
->ref_def_stmt
, 0, 0);
1483 if (f_acc
->cast_stmt
)
1484 print_gimple_stmt (dump_file
, f_acc
->cast_stmt
, 0, 0);
1488 /* Print field accesses from hashtable F_ACCS. */
1491 dump_field_acc_sites (htab_t f_accs
)
1497 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1500 /* Hash value for fallocs_t. */
1503 malloc_hash (const void *x
)
1505 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1508 /* This function returns nonzero if function of func_alloc_sites' X
1512 malloc_eq (const void *x
, const void *y
)
1514 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1517 /* This function is a callback for traversal over a structure accesses.
1518 It frees an access represented by SLOT. */
1521 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1523 struct access_site
* acc
= *(struct access_site
**) slot
;
1525 VEC_free (tree
, heap
, acc
->vars
);
1530 /* This is a callback function for traversal over field accesses.
1531 It frees a field access represented by SLOT. */
1534 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1536 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1542 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1543 if it is not there yet. */
1546 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1554 type
= TYPE_MAIN_VARIANT (type
);
1556 for (i
= 0; VEC_iterate (tree
, *unsuitable_types
, i
, t
); i
++)
1557 if (is_equal_types (t
, type
))
1560 if (i
== VEC_length (tree
, *unsuitable_types
))
1561 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1564 /* Given a type TYPE, this function returns the name of the type. */
1567 get_type_name (tree type
)
1569 if (! TYPE_NAME (type
))
1572 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1573 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1574 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1575 && DECL_NAME (TYPE_NAME (type
)))
1576 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1581 /* This function is a temporary hack to overcome the types problem.
1582 When several compilation units are compiled together
1583 with -combine, the TYPE_MAIN_VARIANT of the same type
1584 can appear differently in different compilation units.
1585 Therefore this function first compares type names.
1586 If there are no names, structure bodies are recursively
1590 is_equal_types (tree type1
, tree type2
)
1592 const char * name1
,* name2
;
1594 if ((!type1
&& type2
)
1595 ||(!type2
&& type1
))
1598 if (!type1
&& !type2
)
1601 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1607 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1610 name1
= get_type_name (type1
);
1611 name2
= get_type_name (type2
);
1614 return strcmp (name1
, name2
) == 0;
1616 switch (TREE_CODE (type1
))
1619 case REFERENCE_TYPE
:
1621 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1627 case QUAL_UNION_TYPE
:
1630 tree field1
, field2
;
1632 /* Compare fields of structure. */
1633 for (field1
= TYPE_FIELDS (type1
), field2
= TYPE_FIELDS (type2
);
1635 field1
= TREE_CHAIN (field1
), field2
= TREE_CHAIN (field2
))
1637 if (!compare_fields (field1
, field2
))
1640 if (field1
|| field2
)
1649 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1650 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1658 tree max1
, min1
, max2
, min2
;
1660 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1663 d1
= TYPE_DOMAIN (type1
);
1664 d2
= TYPE_DOMAIN (type2
);
1669 max1
= TYPE_MAX_VALUE (d1
);
1670 max2
= TYPE_MAX_VALUE (d2
);
1671 min1
= TYPE_MIN_VALUE (d1
);
1672 min2
= TYPE_MIN_VALUE (d2
);
1674 if (max1
&& max2
&& min1
&& min2
1675 && TREE_CODE (max1
) == TREE_CODE (max2
)
1676 && TREE_CODE (max1
) == INTEGER_CST
1677 && TREE_CODE (min1
) == TREE_CODE (min2
)
1678 && TREE_CODE (min1
) == INTEGER_CST
1679 && tree_int_cst_equal (max1
, max2
)
1680 && tree_int_cst_equal (min1
, min2
))
1692 /* This function free non-field accesses from hashtable ACCS. */
1695 free_accesses (htab_t accs
)
1698 htab_traverse (accs
, free_accs
, NULL
);
1702 /* This function free field accesses hashtable F_ACCS. */
1705 free_field_accesses (htab_t f_accs
)
1708 htab_traverse (f_accs
, free_field_accs
, NULL
);
1709 htab_delete (f_accs
);
1712 /* Update call graph with new edge generated by new MALLOC_STMT.
1713 The edge origin is CONTEXT function. */
1716 update_cgraph_with_malloc_call (gimple malloc_stmt
, tree context
)
1718 struct cgraph_node
*src
, *dest
;
1719 tree malloc_fn_decl
;
1724 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1726 src
= cgraph_node (context
);
1727 dest
= cgraph_node (malloc_fn_decl
);
1728 cgraph_create_edge (src
, dest
, malloc_stmt
,
1729 gimple_bb (malloc_stmt
)->count
,
1730 compute_call_stmt_bb_frequency
1731 (context
, gimple_bb (malloc_stmt
)),
1732 gimple_bb (malloc_stmt
)->loop_depth
);
1735 /* This function generates set of statements required
1736 to allocate number NUM of structures of type NEW_TYPE.
1737 The statements are stored in NEW_STMTS. The statement that contain
1738 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1741 create_new_malloc (gimple malloc_stmt
, tree new_type
, gimple_seq
*new_stmts
,
1744 tree new_malloc_size
;
1745 tree malloc_fn_decl
;
1748 gimple call_stmt
, final_stmt
;
1751 gcc_assert (num
&& malloc_stmt
&& new_type
);
1752 *new_stmts
= gimple_seq_alloc ();
1754 /* Generate argument to malloc as multiplication of num
1755 and size of new_type. */
1756 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1757 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1759 /* Generate new call for malloc. */
1760 malloc_res
= create_tmp_var (ptr_type_node
, NULL
);
1761 add_referenced_var (malloc_res
);
1763 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1764 call_stmt
= gimple_build_call (malloc_fn_decl
, 1, new_malloc_size
);
1765 gimple_call_set_lhs (call_stmt
, malloc_res
);
1766 finalize_stmt_and_append (new_stmts
, call_stmt
);
1768 /* Create new cast statement. */
1769 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1770 gcc_assert (final_stmt
);
1771 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1772 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1777 /* This function returns a tree representing
1778 the number of instances of structure STR_DECL allocated
1779 by allocation STMT. If new statements are generated,
1780 they are filled into NEW_STMTS_P. */
1783 gen_num_of_structs_in_malloc (gimple stmt
, tree str_decl
,
1784 gimple_seq
*new_stmts_p
)
1788 HOST_WIDE_INT struct_size_int
;
1793 /* Get malloc argument. */
1794 if (!is_gimple_call (stmt
))
1797 arg
= gimple_call_arg (stmt
, 0);
1799 if (TREE_CODE (arg
) != SSA_NAME
1800 && !TREE_CONSTANT (arg
))
1803 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1804 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1806 gcc_assert (struct_size
);
1808 if (TREE_CODE (arg
) == SSA_NAME
)
1813 if (is_result_of_mult (arg
, &num
, struct_size
))
1816 num
= create_tmp_var (integer_type_node
, NULL
);
1819 add_referenced_var (num
);
1821 if (exact_log2 (struct_size_int
) == -1)
1822 div_stmt
= gimple_build_assign_with_ops (TRUNC_DIV_EXPR
, num
, arg
,
1826 tree C
= build_int_cst (integer_type_node
,
1827 exact_log2 (struct_size_int
));
1829 div_stmt
= gimple_build_assign_with_ops (RSHIFT_EXPR
, num
, arg
, C
);
1831 gimple_seq_add_stmt (new_stmts_p
, div_stmt
);
1832 finalize_stmt (div_stmt
);
1836 if (CONSTANT_CLASS_P (arg
)
1837 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1838 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1843 /* This function is a callback for traversal on new_var's hashtable.
1844 SLOT is a pointer to new_var. This function prints to dump_file
1845 an original variable and all new variables from the new_var
1846 pointed by *SLOT. */
1849 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1851 new_var n_var
= *(new_var
*) slot
;
1856 var_type
= get_type_of_var (n_var
->orig_var
);
1858 fprintf (dump_file
, "\nOrig var: ");
1859 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1860 fprintf (dump_file
, " of type ");
1861 print_generic_expr (dump_file
, var_type
, 0);
1862 fprintf (dump_file
, "\n");
1865 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1867 var_type
= get_type_of_var (var
);
1869 fprintf (dump_file
, " ");
1870 print_generic_expr (dump_file
, var
, 0);
1871 fprintf (dump_file
, " of type ");
1872 print_generic_expr (dump_file
, var_type
, 0);
1873 fprintf (dump_file
, "\n");
1878 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1881 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1884 DECL_ARTIFICIAL (new_decl
) = 1;
1885 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1886 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1887 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1888 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1889 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1890 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1891 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1893 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1895 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1896 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1900 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1901 the same way as a structure type is wrapped in DECL.
1902 It returns the generated type. */
1905 gen_struct_type (tree decl
, tree new_str_type
)
1907 tree type_orig
= get_type_of_var (decl
);
1908 tree new_type
= new_str_type
;
1909 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1911 type_wrapper_t
*wr_p
;
1913 while (POINTER_TYPE_P (type_orig
)
1914 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1916 if (POINTER_TYPE_P (type_orig
))
1919 wr
.domain
= NULL_TREE
;
1923 gcc_assert (TREE_CODE (type_orig
) == ARRAY_TYPE
);
1925 wr
.domain
= TYPE_DOMAIN (type_orig
);
1927 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1928 type_orig
= TREE_TYPE (type_orig
);
1931 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1933 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1935 if (wr_p
->wrap
) /* Array. */
1936 new_type
= build_array_type (new_type
, wr_p
->domain
);
1938 new_type
= build_pointer_type (new_type
);
1940 VEC_pop (type_wrapper_t
, wrapper
);
1943 VEC_free (type_wrapper_t
, heap
, wrapper
);
1947 /* This function generates and returns new variable name based on
1948 ORIG_DECL name, combined with index I.
1949 The form of the new name is <orig_name>.<I> . */
1952 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1954 const char *old_name
;
1958 if (!DECL_NAME (orig_decl
)
1959 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1962 /* If the original variable has a name, create an
1963 appropriate new name for the new variable. */
1965 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1966 prefix
= XALLOCAVEC (char, strlen (old_name
) + 1);
1967 strcpy (prefix
, old_name
);
1968 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1969 return get_identifier (new_name
);
1972 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1975 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1979 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1980 DECL_UID (new_node
->orig_var
),
1985 /* This function creates and returns new_var_data node
1986 with empty new_vars and orig_var equal to VAR. */
1989 create_new_var_node (tree var
, d_str str
)
1993 node
= (new_var
) xmalloc (sizeof (struct new_var_data
));
1994 node
->orig_var
= var
;
1995 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
1999 /* Check whether the type of VAR is potential candidate for peeling.
2000 Returns true if yes, false otherwise. If yes, TYPE_P will contain
2001 candidate type. If VAR is initialized, the type of VAR will be added
2002 to UNSUITABLE_TYPES. */
2005 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
2008 bool initialized
= false;
2015 /* There is no support of initialized vars. */
2016 if (TREE_CODE (var
) == VAR_DECL
2017 && DECL_INITIAL (var
) != NULL_TREE
)
2020 type
= get_type_of_var (var
);
2024 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2025 if (TREE_CODE (type
) != RECORD_TYPE
)
2029 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2033 fprintf (dump_file
, "The type ");
2034 print_generic_expr (dump_file
, type
, 0);
2035 fprintf (dump_file
, " is initialized...Excluded.");
2037 add_unsuitable_type (unsuitable_types
, type
);
2047 /* Hash value for field_access_site. */
2050 field_acc_hash (const void *x
)
2052 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2055 /* This function returns nonzero if stmt of field_access_site X
2059 field_acc_eq (const void *x
, const void *y
)
2061 return ((const struct field_access_site
*)x
)->stmt
== (const_gimple
)y
;
2064 /* This function prints an access site, defined by SLOT. */
2067 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2069 struct access_site
*acc
= *(struct access_site
**) slot
;
2073 fprintf(dump_file
, "\n");
2075 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
2076 fprintf(dump_file
, " : ");
2078 for (i
= 0; VEC_iterate (tree
, acc
->vars
, i
, var
); i
++)
2080 print_generic_expr (dump_file
, var
, 0);
2081 fprintf(dump_file
, ", ");
2086 /* This function frees memory allocated for structure clusters,
2087 starting from CLUSTER. */
2090 free_struct_cluster (struct field_cluster
* cluster
)
2094 if (cluster
->fields_in_cluster
)
2095 sbitmap_free (cluster
->fields_in_cluster
);
2096 if (cluster
->sibling
)
2097 free_struct_cluster (cluster
->sibling
);
2102 /* Free all allocated memory under the structure node pointed by D_NODE. */
2105 free_data_struct (d_str d_node
)
2114 fprintf (dump_file
, "\nRemoving data structure \"");
2115 print_generic_expr (dump_file
, d_node
->decl
, 0);
2116 fprintf (dump_file
, "\" from data_struct_list.");
2119 /* Free all space under d_node. */
2122 for (i
= 0; i
< d_node
->num_fields
; i
++)
2123 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2124 free (d_node
->fields
);
2128 free_accesses (d_node
->accs
);
2130 if (d_node
->struct_clustering
)
2131 free_struct_cluster (d_node
->struct_clustering
);
2133 if (d_node
->new_types
)
2134 VEC_free (tree
, heap
, d_node
->new_types
);
2137 /* This function creates new general and field accesses in BB. */
2140 create_new_accesses_in_bb (basic_block bb
)
2145 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2146 create_new_accs_for_struct (str
, bb
);
2149 /* This function adds allocation sites for peeled structures.
2150 M_DATA is vector of allocation sites of function CONTEXT. */
2153 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2158 for (j
= 0; VEC_iterate (alloc_site_t
, m_data
->allocs
, j
, call
); j
++)
2160 gimple stmt
= call
->stmt
;
2161 d_str str
= call
->str
;
2163 gimple_seq new_stmts
= NULL
;
2164 gimple last_stmt
= get_final_alloc_stmt (stmt
);
2168 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2171 gimple last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2172 insert_seq_after_stmt (last_stmt
, new_stmts
);
2173 last_stmt
= last_stmt_tmp
;
2176 /* Generate an allocation sites for each new structure type. */
2177 for (i
= 0; VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2179 gimple new_malloc_stmt
= NULL
;
2180 gimple last_stmt_tmp
= NULL
;
2183 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2184 last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2185 insert_seq_after_stmt (last_stmt
, new_stmts
);
2186 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2187 last_stmt
= last_stmt_tmp
;
2192 /* This function prints new variables from hashtable
2193 NEW_VARS_HTAB to dump_file. */
2196 dump_new_vars (htab_t new_vars_htab
)
2202 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2205 /* Given an original variable ORIG_DECL of structure type STR,
2206 this function generates new variables of the types defined
2207 by STR->new_type. Generated types are saved in new_var node NODE.
2208 ORIG_DECL should has VAR_DECL tree_code. */
2211 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2217 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2219 tree new_decl
= NULL
;
2222 new_name
= gen_var_name (orig_decl
, i
);
2223 type
= gen_struct_type (orig_decl
, type
);
2225 if (is_global_var (orig_decl
))
2226 new_decl
= build_decl (DECL_SOURCE_LOCATION (orig_decl
),
2227 VAR_DECL
, new_name
, type
);
2230 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2231 new_decl
= create_tmp_var (type
, name
);
2234 copy_decl_attributes (new_decl
, orig_decl
);
2235 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2239 /* This function creates new variables to
2240 substitute the original variable VAR_DECL and adds
2241 them to the new_var's hashtable NEW_VARS_HTAB. */
2244 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2251 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2254 if (!is_candidate (var_decl
, &type
, NULL
))
2257 i
= find_structure (type
);
2258 if (i
== VEC_length (structure
, structures
))
2261 str
= VEC_index (structure
, structures
, i
);
2262 node
= create_new_var_node (var_decl
, str
);
2263 create_new_var_1 (var_decl
, str
, node
);
2264 add_to_new_vars_htab (node
, new_vars_htab
);
2267 /* Hash value for new_var. */
2270 new_var_hash (const void *x
)
2272 return DECL_UID (((const_new_var
)x
)->orig_var
);
2275 /* This function returns nonzero if orig_var of new_var X
2276 and tree Y have equal UIDs. */
2279 new_var_eq (const void *x
, const void *y
)
2281 if (DECL_P ((const_tree
)y
))
2282 return DECL_UID (((const_new_var
)x
)->orig_var
) == DECL_UID ((const_tree
)y
);
2287 /* This function check whether a structure type represented by STR
2288 escapes due to ipa-type-escape analysis. If yes, this type is added
2289 to UNSUITABLE_TYPES vector. */
2292 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2294 tree type
= str
->decl
;
2296 if (!ipa_type_escape_type_contained_p (type
))
2300 fprintf (dump_file
, "\nEscaping type is ");
2301 print_generic_expr (dump_file
, type
, 0);
2303 add_unsuitable_type (unsuitable_types
, type
);
2307 /* Hash value for access_site. */
2310 acc_hash (const void *x
)
2312 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2315 /* Return nonzero if stmt of access_site X is equal to Y. */
2318 acc_eq (const void *x
, const void *y
)
2320 return ((const struct access_site
*)x
)->stmt
== (const_gimple
)y
;
2323 /* Given a structure declaration STRUCT_DECL, and number of fields
2324 in the structure NUM_FIELDS, this function creates and returns
2325 corresponding field_entry's. */
2327 static struct field_entry
*
2328 get_fields (tree struct_decl
, int num_fields
)
2330 struct field_entry
*list
;
2331 tree t
= TYPE_FIELDS (struct_decl
);
2335 (struct field_entry
*) xmalloc (num_fields
* sizeof (struct field_entry
));
2337 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2338 if (TREE_CODE (t
) == FIELD_DECL
)
2340 list
[idx
].index
= idx
;
2342 list
[idx
].acc_sites
=
2343 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2344 list
[idx
].count
= 0;
2345 list
[idx
].field_mapping
= NULL_TREE
;
2351 /* Print non-field accesses from hashtable ACCS of structure. */
2354 dump_access_sites (htab_t accs
)
2360 htab_traverse (accs
, dump_acc
, NULL
);
2363 /* This function is a callback for alloc_sites hashtable
2364 traversal. SLOT is a pointer to fallocs_t. This function
2365 removes all allocations of the structure defined by DATA. */
2368 remove_str_allocs_in_func (void **slot
, void *data
)
2370 fallocs_t fallocs
= *(fallocs_t
*) slot
;
2374 while (VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
))
2376 if (call
->str
== (d_str
) data
)
2377 VEC_ordered_remove (alloc_site_t
, fallocs
->allocs
, i
);
2385 /* This function remove all entries corresponding to the STR structure
2386 from alloc_sites hashtable. */
2389 remove_str_allocs (d_str str
)
2395 htab_traverse (alloc_sites
, remove_str_allocs_in_func
, str
);
2398 /* This function removes the structure with index I from structures vector. */
2401 remove_structure (unsigned i
)
2405 if (i
>= VEC_length (structure
, structures
))
2408 str
= VEC_index (structure
, structures
, i
);
2410 /* Before removing the structure str, we have to remove its
2411 allocations from alloc_sites hashtable. */
2412 remove_str_allocs (str
);
2413 free_data_struct (str
);
2414 VEC_ordered_remove (structure
, structures
, i
);
2417 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2418 COND_STMT is a condition statement to check. */
2421 is_safe_cond_expr (gimple cond_stmt
)
2424 unsigned str0
, str1
;
2426 unsigned length
= VEC_length (structure
, structures
);
2428 if (gimple_cond_code (cond_stmt
) != EQ_EXPR
2429 && gimple_cond_code (cond_stmt
) != NE_EXPR
)
2432 arg0
= gimple_cond_lhs (cond_stmt
);
2433 arg1
= gimple_cond_rhs (cond_stmt
);
2435 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2436 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2438 s0
= (str0
!= length
) ? true : false;
2439 s1
= (str1
!= length
) ? true : false;
2444 /* For now we allow only comparison with 0 or NULL. */
2445 if (!integer_zerop (arg0
) && !integer_zerop (arg1
))
2451 /* This function excludes statements, that are
2452 part of allocation sites or field accesses, from the
2453 hashtable of general accesses. SLOT represents general
2454 access that will be checked. DATA is a pointer to
2455 exclude_data structure. */
2458 exclude_from_accs (void **slot
, void *data
)
2460 struct access_site
*acc
= *(struct access_site
**) slot
;
2461 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2462 d_str str
= ((struct exclude_data
*)data
)->str
;
2464 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2465 || is_part_of_field_access (acc
->stmt
, str
))
2467 VEC_free (tree
, heap
, acc
->vars
);
2469 htab_clear_slot (str
->accs
, slot
);
2474 /* Callback function for walk_tree called from collect_accesses_in_bb
2475 function. DATA is the statement which is analyzed. */
2478 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2480 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
2481 gimple stmt
= (gimple
) wi
->info
;
2487 switch (TREE_CODE (t
))
2491 tree var
= TREE_OPERAND(t
, 0);
2492 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2493 unsigned i
= find_structure (type
);
2495 if (i
!= VEC_length (structure
, structures
))
2499 fprintf (dump_file
, "\nThe type ");
2500 print_generic_expr (dump_file
, type
, 0);
2501 fprintf (dump_file
, " has bitfield.");
2503 remove_structure (i
);
2510 tree ref
= TREE_OPERAND (t
, 0);
2511 tree field_decl
= TREE_OPERAND (t
, 1);
2514 if ((TREE_CODE (ref
) == INDIRECT_REF
2515 || TREE_CODE (ref
) == ARRAY_REF
2516 || TREE_CODE (ref
) == VAR_DECL
)
2517 && TREE_CODE (field_decl
) == FIELD_DECL
)
2519 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2520 unsigned i
= find_structure (type
);
2522 if (i
!= VEC_length (structure
, structures
))
2524 d_str str
= VEC_index (structure
, structures
, i
);
2525 struct field_entry
* field
=
2526 find_field_in_struct (str
, field_decl
);
2530 struct field_access_site
*acc
= make_field_acc_node ();
2537 acc
->field_decl
= field_decl
;
2539 /* Check whether the access is of the form
2540 we can deal with. */
2541 if (!decompose_access (str
->decl
, acc
))
2545 fprintf (dump_file
, "\nThe type ");
2546 print_generic_expr (dump_file
, type
, 0);
2548 " has complicate access in statement ");
2549 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2552 remove_structure (i
);
2557 /* Increase count of field. */
2558 basic_block bb
= gimple_bb (stmt
);
2559 field
->count
+= bb
->count
;
2561 /* Add stmt to the acc_sites of field. */
2562 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2573 tree cond
= COND_EXPR_COND (t
);
2575 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2577 tree t
= TREE_OPERAND (cond
, i
);
2580 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2591 if (TREE_CODE (t
) == SSA_NAME
)
2592 t
= SSA_NAME_VAR (t
);
2594 i
= find_structure (strip_type (get_type_of_var (t
)));
2595 if (i
!= VEC_length (structure
, structures
))
2599 str
= VEC_index (structure
, structures
, i
);
2600 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2613 /* Free structures hashtable. */
2616 free_structures (void)
2621 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2622 free_data_struct (str
);
2624 VEC_free (structure
, heap
, structures
);
2628 /* This function is a callback for traversal over new_var's hashtable.
2629 SLOT is a pointer to new_var. This function frees memory allocated
2630 for new_var and pointed by *SLOT. */
2633 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2635 new_var n_var
= *(new_var
*) slot
;
2637 /* Free vector of new_vars. */
2638 VEC_free (tree
, heap
, n_var
->new_vars
);
2643 /* Free new_vars hashtable NEW_VARS_HTAB. */
2646 free_new_vars_htab (htab_t new_vars_htab
)
2649 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2650 htab_delete (new_vars_htab
);
2651 new_vars_htab
= NULL
;
2654 /* This function creates new general and field accesses that appear in cfun. */
2657 create_new_accesses_for_func (void)
2661 FOR_EACH_BB_FN (bb
, cfun
)
2662 create_new_accesses_in_bb (bb
);
2665 /* Create new allocation sites for the function represented by NODE. */
2668 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2670 fallocs_t fallocs
= get_fallocs (node
->decl
);
2673 create_new_alloc_sites (fallocs
, node
->decl
);
2676 /* For each local variable of structure type from the vector of structures
2677 this function generates new variable(s) to replace it. */
2680 create_new_local_vars (void)
2683 referenced_var_iterator rvi
;
2685 new_local_vars
= htab_create (num_referenced_vars
,
2686 new_var_hash
, new_var_eq
, NULL
);
2688 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2690 if (!is_global_var (var
))
2691 create_new_var (var
, new_local_vars
);
2695 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2696 dump_new_vars (new_local_vars
);
2699 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2702 print_shift (unsigned HOST_WIDE_INT shift
)
2704 unsigned HOST_WIDE_INT sh
= shift
;
2707 fprintf (dump_file
, " ");
2710 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2713 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2714 struct field_entry
* fields
, int num_fields
)
2718 for (i
= 0; i
< num_fields
; i
++)
2719 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2720 fields
[i
].field_mapping
= new_type
;
2723 /* This functions builds structure with FIELDS,
2724 NAME and attributes similar to ORIG_STRUCT.
2725 It returns the newly created structure. */
2728 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2730 tree attributes
= NULL_TREE
;
2734 if (TYPE_ATTRIBUTES (orig_struct
))
2735 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2736 ref
= make_node (RECORD_TYPE
);
2737 TYPE_SIZE (ref
) = 0;
2738 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2739 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2740 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2742 DECL_CONTEXT (x
) = ref
;
2743 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2745 TYPE_FIELDS (ref
) = fields
;
2747 TYPE_NAME (ref
) = name
;
2752 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2753 of preparation for new structure building. NUM_FIELDS is a total
2754 number of fields in the structure. The function returns newly
2755 generated fields. */
2758 create_fields (struct field_cluster
* cluster
,
2759 struct field_entry
* fields
, int num_fields
)
2762 tree new_types
= NULL_TREE
;
2763 tree last
= NULL_TREE
;
2765 for (i
= 0; i
< num_fields
; i
++)
2766 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2768 tree new_decl
= unshare_expr (fields
[i
].decl
);
2771 new_types
= new_decl
;
2773 TREE_CHAIN (last
) = new_decl
;
2777 TREE_CHAIN (last
) = NULL_TREE
;
2782 /* This function creates a cluster name. The name is based on
2783 the original structure name, if it is present. It has a form:
2785 <original_struct_name>_sub.<CLUST_NUM>
2787 The original structure name is taken from the type of DECL.
2788 If an original structure name is not present, it's generated to be:
2792 The function returns identifier of the new cluster name. */
2795 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2797 const char * orig_name
= get_type_name (decl
);
2798 char * tmp_name
= NULL
;
2804 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2806 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2807 prefix
= XALLOCAVEC (char, len
+ 1);
2808 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2809 strlen (tmp_name
? tmp_name
: orig_name
));
2810 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2812 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2813 return get_identifier (new_name
);
2816 /* This function checks whether the structure STR has bitfields.
2817 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2820 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2822 tree type
= str
->decl
;
2825 for (i
= 0; i
< str
->num_fields
; i
++)
2826 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2828 add_unsuitable_type (unsuitable_types
, type
);
2831 fprintf (dump_file
, "\nType ");
2832 print_generic_expr (dump_file
, type
, 0);
2833 fprintf (dump_file
, "\nescapes due to bitfield ");
2834 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2840 /* This function adds to UNSUITABLE_TYPES those types that escape
2841 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2844 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2849 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
2850 check_type_escape (str
, unsuitable_types
);
2853 /* If a structure type is a return type of any function,
2854 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2857 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2859 struct cgraph_node
*c_node
;
2861 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2863 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2867 ret_t
= strip_type (ret_t
);
2868 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2870 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2873 fprintf (dump_file
, "\nThe type \"");
2874 print_generic_expr (dump_file
, ret_t
, 0);
2876 "\" is return type of function...Excluded.");
2883 /* This function looks for parameters of local functions
2884 which are of structure types, or derived from them (arrays
2885 of structures, pointers to structures, or their combinations).
2886 We are not handling peeling of such structures right now.
2887 The found structures types are added to UNSUITABLE_TYPES vector. */
2890 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2892 struct cgraph_node
*c_node
;
2894 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2895 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2897 tree fn
= c_node
->decl
;
2900 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= TREE_CHAIN (arg
))
2902 tree type
= TREE_TYPE (arg
);
2904 type
= strip_type (type
);
2905 if (TREE_CODE (type
) == RECORD_TYPE
)
2907 add_unsuitable_type (unsuitable_types
,
2908 TYPE_MAIN_VARIANT (type
));
2911 fprintf (dump_file
, "\nPointer to type \"");
2912 print_generic_expr (dump_file
, type
, 0);
2914 "\" is passed to local function...Excluded.");
2921 /* This function analyzes structure form of structures
2922 potential for transformation. If we are not capable to transform
2923 structure of some form, we remove it from the structures hashtable.
2924 Right now we cannot handle nested structs, when nesting is
2925 through any level of pointers or arrays.
2927 TBD: release these constrains in future.
2929 Note, that in this function we suppose that all structures
2930 in the program are members of the structures hashtable right now,
2931 without excluding escaping types. */
2934 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2938 for (i
= 0; i
< str
->num_fields
; i
++)
2940 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2942 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2944 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2945 add_unsuitable_type (unsuitable_types
, str
->decl
);
2948 fprintf (dump_file
, "\nType ");
2949 print_generic_expr (dump_file
, f_type
, 0);
2950 fprintf (dump_file
, " is a field in the structure ");
2951 print_generic_expr (dump_file
, str
->decl
, 0);
2952 fprintf (dump_file
, ". Escaping...");
2958 /* This function adds a structure TYPE to the vector of structures,
2959 if it's not already there. */
2962 add_structure (tree type
)
2964 struct data_structure node
;
2968 type
= TYPE_MAIN_VARIANT (type
);
2970 i
= find_structure (type
);
2972 if (i
!= VEC_length (structure
, structures
))
2975 num_fields
= fields_length (type
);
2977 node
.num_fields
= num_fields
;
2978 node
.fields
= get_fields (type
, num_fields
);
2979 node
.struct_clustering
= NULL
;
2980 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
2981 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
2984 VEC_safe_push (structure
, heap
, structures
, &node
);
2988 fprintf (dump_file
, "\nAdding data structure \"");
2989 print_generic_expr (dump_file
, type
, 0);
2990 fprintf (dump_file
, "\" to data_struct_list.");
2994 /* This function adds an allocation site to alloc_sites hashtable.
2995 The allocation site appears in STMT of function FN_DECL and
2996 allocates the structure represented by STR. */
2999 add_alloc_site (tree fn_decl
, gimple stmt
, d_str str
)
3001 fallocs_t fallocs
= NULL
;
3002 alloc_site_t m_call
;
3008 (fallocs_t
) htab_find_with_hash (alloc_sites
,
3009 fn_decl
, htab_hash_pointer (fn_decl
));
3015 fallocs
= (fallocs_t
)
3016 xmalloc (sizeof (struct func_alloc_sites
));
3017 fallocs
->func
= fn_decl
;
3018 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
3019 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
3020 htab_hash_pointer (fn_decl
), INSERT
);
3023 VEC_safe_push (alloc_site_t
, heap
,
3024 fallocs
->allocs
, &m_call
);
3028 fprintf (dump_file
, "\nAdding stmt ");
3029 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3030 fprintf (dump_file
, " to list of mallocs.");
3034 /* This function returns true if the result of STMT, that contains a call
3035 to an allocation function, is cast to one of the structure types.
3036 STMT should be of the form: T.2 = <alloc_func> (T.1);
3037 If true, I_P contains an index of an allocated structure.
3038 Otherwise I_P contains the length of the vector of structures. */
3041 is_alloc_of_struct (gimple stmt
, unsigned *i_p
)
3047 final_stmt
= get_final_alloc_stmt (stmt
);
3052 /* final_stmt should be of the form:
3053 T.3 = (struct_type *) T.2; */
3055 if (gimple_code (final_stmt
) != GIMPLE_ASSIGN
)
3058 lhs
= gimple_assign_lhs (final_stmt
);
3060 type
= get_type_of_var (lhs
);
3065 if (!POINTER_TYPE_P (type
)
3066 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3069 *i_p
= find_structure (strip_type (type
));
3071 if (*i_p
== VEC_length (structure
, structures
))
3077 /* This function prints non-field and field accesses
3078 of the structure STR. */
3081 dump_accs (d_str str
)
3085 fprintf (dump_file
, "\nAccess sites of struct ");
3086 print_generic_expr (dump_file
, str
->decl
, 0);
3088 for (i
= 0; i
< str
->num_fields
; i
++)
3090 fprintf (dump_file
, "\nAccess site of field ");
3091 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3092 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3093 fprintf (dump_file
, ":\n");
3095 fprintf (dump_file
, "\nGeneral access sites\n");
3096 dump_access_sites (str
->accs
);
3099 /* This function checks whether an access statement, pointed by SLOT,
3100 is a condition we are capable to transform. It returns false if not,
3101 setting bool *DATA to false. */
3104 safe_cond_expr_check (void **slot
, void *data
)
3106 struct access_site
*acc
= *(struct access_site
**) slot
;
3108 if (gimple_code (acc
->stmt
) == GIMPLE_COND
3109 && !is_safe_cond_expr (acc
->stmt
))
3113 fprintf (dump_file
, "\nUnsafe conditional statement ");
3114 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
3116 *(bool *) data
= false;
3122 /* This function excludes statements that are part of allocation sites and
3123 field accesses from the hashtable of general accesses of the structure
3124 type STR. Only accesses that belong to the function represented by
3125 NODE are treated. */
3128 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3130 struct exclude_data dt
;
3132 dt
.fn_decl
= node
->decl
;
3135 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3138 /* Collect accesses to the structure types that appear in basic block BB. */
3141 collect_accesses_in_bb (basic_block bb
)
3143 gimple_stmt_iterator bsi
;
3144 struct walk_stmt_info wi
;
3146 memset (&wi
, 0, sizeof (wi
));
3148 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3150 gimple stmt
= gsi_stmt (bsi
);
3152 /* In asm stmt we cannot always track the arguments,
3153 so we just give up. */
3154 if (gimple_code (stmt
) == GIMPLE_ASM
)
3160 wi
.info
= (void *) stmt
;
3161 walk_gimple_op (stmt
, get_stmt_accesses
, &wi
);
3165 /* This function generates cluster substructure that contains FIELDS.
3166 The cluster added to the set of clusters of the structure STR. */
3169 gen_cluster (sbitmap fields
, d_str str
)
3171 struct field_cluster
*crr_cluster
= NULL
;
3174 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3175 crr_cluster
->sibling
= str
->struct_clustering
;
3176 str
->struct_clustering
= crr_cluster
;
3177 crr_cluster
->fields_in_cluster
= fields
;
3180 /* This function peels a field with the index I from the structure DS. */
3183 peel_field (int i
, d_str ds
)
3185 struct field_cluster
*crr_cluster
= NULL
;
3188 (struct field_cluster
*) xcalloc (1, sizeof (struct field_cluster
));
3189 crr_cluster
->sibling
= ds
->struct_clustering
;
3190 ds
->struct_clustering
= crr_cluster
;
3191 crr_cluster
->fields_in_cluster
=
3192 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3193 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3194 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3197 /* This function calculates maximum field count in
3198 the structure STR. */
3201 get_max_field_count (d_str str
)
3206 for (i
= 0; i
< str
->num_fields
; i
++)
3207 if (str
->fields
[i
].count
> max
)
3208 max
= str
->fields
[i
].count
;
3213 /* Do struct-reorg transformation for individual function
3214 represented by NODE. All structure types relevant
3215 for this function are transformed. */
3218 do_reorg_for_func (struct cgraph_node
*node
)
3220 create_new_local_vars ();
3221 create_new_alloc_sites_for_func (node
);
3222 create_new_accesses_for_func ();
3223 update_ssa (TODO_update_ssa
);
3224 cleanup_tree_cfg ();
3226 /* Free auxiliary data representing local variables. */
3227 free_new_vars_htab (new_local_vars
);
3230 /* Print structure TYPE, its name, if it exists, and body.
3231 INDENT defines the level of indentation (similar
3232 to the option -i of indent command). SHIFT parameter
3233 defines a number of spaces by which a structure will
3234 be shifted right. */
3237 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3238 unsigned HOST_WIDE_INT shift
)
3240 const char *struct_name
;
3243 if (!type
|| !dump_file
)
3246 if (TREE_CODE (type
) != RECORD_TYPE
)
3248 print_generic_expr (dump_file
, type
, 0);
3252 print_shift (shift
);
3253 struct_name
= get_type_name (type
);
3254 fprintf (dump_file
, "struct ");
3256 fprintf (dump_file
, "%s\n",struct_name
);
3257 print_shift (shift
);
3258 fprintf (dump_file
, "{\n");
3260 for (field
= TYPE_FIELDS (type
); field
;
3261 field
= TREE_CHAIN (field
))
3263 unsigned HOST_WIDE_INT s
= indent
;
3264 tree f_type
= TREE_TYPE (field
);
3266 print_shift (shift
);
3268 fprintf (dump_file
, " ");
3269 dump_struct_type (f_type
, indent
, shift
+ indent
);
3270 fprintf(dump_file
, " ");
3271 print_generic_expr (dump_file
, field
, 0);
3272 fprintf(dump_file
, ";\n");
3274 print_shift (shift
);
3275 fprintf (dump_file
, "}\n");
3278 /* This function creates new structure types to replace original type,
3279 indicated by STR->decl. The names of the new structure types are
3280 derived from the original structure type. If the original structure
3281 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3284 create_new_type (d_str str
, int *str_num
)
3286 int cluster_num
= 0;
3288 struct field_cluster
*cluster
= str
->struct_clustering
;
3291 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3297 fields
= create_fields (cluster
, str
->fields
,
3299 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3301 update_fields_mapping (cluster
, new_type
,
3302 str
->fields
, str
->num_fields
);
3304 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3305 cluster
= cluster
->sibling
;
3310 /* This function is a callback for alloc_sites hashtable
3311 traversal. SLOT is a pointer to fallocs_t.
3312 This function frees memory pointed by *SLOT. */
3315 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3317 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3319 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3324 /* Remove structures collected in UNSUITABLE_TYPES
3325 from structures vector. */
3328 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3334 for (j
= 0; VEC_iterate (tree
, unsuitable_types
, j
, type
); j
++)
3335 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3336 if (is_equal_types (str
->decl
, type
))
3338 remove_structure (i
);
3343 /* Exclude structure types with bitfields.
3344 We would not want to interfere with other optimizations
3345 that can be done in this case. The structure types with
3346 bitfields are added to UNSUITABLE_TYPES vector. */
3349 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3354 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3355 check_bitfields (str
, unsuitable_types
);
3358 /* This function checks three types of escape. A structure type escapes:
3360 1. if it's a type of parameter of a local function.
3361 2. if it's a type of function return value.
3362 3. if it escapes as a result of ipa-type-escape analysis.
3364 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3367 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3369 exclude_types_passed_to_local_func (unsuitable_types
);
3370 exclude_returned_types (unsuitable_types
);
3371 exclude_escaping_types_1 (unsuitable_types
);
3374 /* This function analyzes whether the form of
3375 structure is such that we are capable to transform it.
3376 Nested structures are checked here. Unsuitable structure
3377 types are added to UNSUITABLE_TYPE vector. */
3380 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3385 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3386 check_struct_form (str
, unsuitable_types
);
3389 /* This function looks for structure types instantiated in the program.
3390 The candidate types are added to the structures vector.
3391 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3394 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3398 struct varpool_node
*current_varpool
;
3399 struct cgraph_node
*c_node
;
3401 /* Check global variables. */
3402 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3404 var
= current_varpool
->decl
;
3405 if (is_candidate (var
, &type
, unsuitable_types
))
3406 add_structure (type
);
3409 /* Now add structures that are types of function parameters and
3411 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3413 enum availability avail
=
3414 cgraph_function_body_availability (c_node
);
3416 /* We need AVAIL_AVAILABLE for main function. */
3417 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3419 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3421 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3422 var
= TREE_CHAIN (var
))
3423 if (is_candidate (var
, &type
, unsuitable_types
))
3424 add_structure (type
);
3428 /* Skip cones that haven't been materialized yet. */
3429 gcc_assert (c_node
->clone_of
3430 && c_node
->clone_of
->decl
!= c_node
->decl
);
3434 /* Check function local variables. */
3435 for (var_list
= fn
->local_decls
; var_list
;
3436 var_list
= TREE_CHAIN (var_list
))
3438 var
= TREE_VALUE (var_list
);
3440 if (is_candidate (var
, &type
, unsuitable_types
))
3441 add_structure (type
);
3447 /* This function returns true if the program contains
3448 a call to user defined allocation function, or other
3449 functions that can interfere with struct-reorg optimizations. */
3452 program_redefines_malloc_p (void)
3454 struct cgraph_node
*c_node
;
3455 struct cgraph_node
*c_node2
;
3456 struct cgraph_edge
*c_edge
;
3459 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3461 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3463 c_node2
= c_edge
->callee
;
3464 fndecl2
= c_node2
->decl
;
3465 if (is_gimple_call (c_edge
->call_stmt
))
3467 const char * fname
= get_name (fndecl2
);
3469 if ((gimple_call_flags (c_edge
->call_stmt
) & ECF_MALLOC
)
3470 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
)
3471 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
)
3472 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3475 /* Check that there is no __builtin_object_size,
3476 __builtin_offsetof, or realloc's in the program. */
3477 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3478 || !strcmp (fname
, "__builtin_offsetof")
3479 || !strcmp (fname
, "realloc"))
3488 /* In this function we assume that an allocation statement
3490 var = (type_cast) malloc (size);
3492 is converted into the following set of statements:
3496 T.3 = (type_cast) T.2;
3499 In this function we collect into alloc_sites the allocation
3500 sites of variables of structure types that are present
3501 in structures vector. */
3504 collect_alloc_sites (void)
3506 struct cgraph_node
*node
;
3507 struct cgraph_edge
*cs
;
3509 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3510 if (node
->analyzed
&& node
->decl
)
3512 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3514 gimple stmt
= cs
->call_stmt
;
3520 if (is_gimple_call (stmt
)
3521 && (decl
= gimple_call_fndecl (stmt
))
3522 && gimple_call_lhs (stmt
))
3526 if (is_alloc_of_struct (stmt
, &i
))
3528 /* We support only malloc now. */
3529 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3533 str
= VEC_index (structure
, structures
, i
);
3534 add_alloc_site (node
->decl
, stmt
, str
);
3541 "\nUnsupported allocation function ");
3542 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3544 remove_structure (i
);
3553 /* Print collected accesses. */
3556 dump_accesses (void)
3564 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3568 /* This function checks whether the accesses of structures in condition
3569 expressions are of the kind we are capable to transform.
3570 If not, such structures are removed from the vector of structures. */
3573 check_cond_exprs (void)
3579 while (VEC_iterate (structure
, structures
, i
, str
))
3584 htab_traverse (str
->accs
, safe_cond_expr_check
, &safe_p
);
3586 remove_structure (i
);
3592 /* We exclude from non-field accesses of the structure
3593 all statements that will be treated as part of the structure
3594 allocation sites or field accesses. */
3597 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3602 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3603 exclude_alloc_and_field_accs_1 (str
, node
);
3606 /* This function collects accesses of the fields of the structures
3607 that appear at function FN. */
3610 collect_accesses_in_func (struct function
*fn
)
3617 /* Collect accesses for each basic blocks separately. */
3618 FOR_EACH_BB_FN (bb
, fn
)
3619 collect_accesses_in_bb (bb
);
3622 /* This function summarizes counts of the fields into the structure count. */
3625 sum_counts (d_str str
, gcov_type
*hottest
)
3630 for (i
= 0; i
< str
->num_fields
; i
++)
3634 fprintf (dump_file
, "\nCounter of field \"");
3635 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3636 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3637 str
->fields
[i
].count
);
3639 str
->count
+= str
->fields
[i
].count
;
3644 fprintf (dump_file
, "\nCounter of struct \"");
3645 print_generic_expr (dump_file
, str
->decl
, 0);
3646 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3649 if (str
->count
> *hottest
)
3650 *hottest
= str
->count
;
3653 /* This function peels the field into separate structure if it's
3654 sufficiently hot, i.e. if its count provides at least 90% of
3655 the maximum field count in the structure. */
3658 peel_hot_fields (d_str str
)
3660 gcov_type max_field_count
;
3661 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3664 sbitmap_ones (fields_left
);
3666 (gcov_type
) (get_max_field_count (str
)/100)*90;
3668 str
->struct_clustering
= NULL
;
3670 for (i
= 0; i
< str
->num_fields
; i
++)
3672 if (str
->count
>= max_field_count
)
3674 RESET_BIT (fields_left
, i
);
3675 peel_field (i
, str
);
3679 i
= sbitmap_first_set_bit (fields_left
);
3681 gen_cluster (fields_left
, str
);
3683 sbitmap_free (fields_left
);
3686 /* This function is a helper for do_reorg. It goes over
3687 functions in call graph and performs actual transformation
3693 struct cgraph_node
*node
;
3695 /* Initialize the default bitmap obstack. */
3696 bitmap_obstack_initialize (NULL
);
3698 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3699 if (node
->analyzed
&& node
->decl
)
3701 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3702 current_function_decl
= node
->decl
;
3704 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3705 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3706 do_reorg_for_func (node
);
3707 free_dominance_info (CDI_DOMINATORS
);
3708 free_dominance_info (CDI_POST_DOMINATORS
);
3709 current_function_decl
= NULL
;
3714 bitmap_obstack_release (NULL
);
3717 /* This function creates new global struct variables.
3718 For each original variable, the set of new variables
3719 is created with the new structure types corresponding
3720 to the structure type of original variable.
3721 Only VAR_DECL variables are treated by this function. */
3724 create_new_global_vars (void)
3726 struct varpool_node
*current_varpool
;
3727 unsigned HOST_WIDE_INT i
;
3728 unsigned HOST_WIDE_INT varpool_size
= 0;
3730 for (i
= 0; i
< 2; i
++)
3733 new_global_vars
= htab_create (varpool_size
,
3734 new_var_hash
, new_var_eq
, NULL
);
3735 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3737 tree var_decl
= current_varpool
->decl
;
3739 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3744 create_new_var (var_decl
, new_global_vars
);
3748 if (new_global_vars
)
3749 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3752 /* Dump all new types generated by this optimization. */
3755 dump_new_types (void)
3764 fprintf (dump_file
, "\nThe following are the new types generated by"
3765 " this optimization:\n");
3767 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3771 fprintf (dump_file
, "\nFor type ");
3772 dump_struct_type (str
->decl
, 2, 0);
3773 fprintf (dump_file
, "\nthe number of new types is %d\n",
3774 VEC_length (tree
, str
->new_types
));
3776 for (j
= 0; VEC_iterate (tree
, str
->new_types
, j
, type
); j
++)
3777 dump_struct_type (type
, 2, 0);
3781 /* This function creates new types to replace old structure types. */
3784 create_new_types (void)
3790 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3791 create_new_type (str
, &str_num
);
3794 /* Free allocation sites hashtable. */
3797 free_alloc_sites (void)
3800 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3801 htab_delete (alloc_sites
);
3805 /* This function collects structures potential
3806 for peeling transformation, and inserts
3807 them into structures hashtable. */
3810 collect_structures (void)
3812 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3814 structures
= VEC_alloc (structure
, heap
, 32);
3816 /* If program contains user defined mallocs, we give up. */
3817 if (program_redefines_malloc_p ())
3820 /* Build data structures hashtable of all data structures
3822 build_data_structure (&unsuitable_types
);
3824 /* This function analyzes whether the form of
3825 structure is such that we are capable to transform it.
3826 Nested structures are checked here. */
3827 analyze_struct_form (&unsuitable_types
);
3829 /* This function excludes those structure types
3830 that escape compilation unit. */
3831 exclude_escaping_types (&unsuitable_types
);
3833 /* We do not want to change data layout of the structures with bitfields. */
3834 exclude_types_with_bit_fields (&unsuitable_types
);
3836 remove_unsuitable_types (unsuitable_types
);
3837 VEC_free (tree
, heap
, unsuitable_types
);
3840 /* Collect structure allocation sites. In case of arrays
3841 we have nothing to do. */
3844 collect_allocation_sites (void)
3846 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3847 collect_alloc_sites ();
3850 /* This function collects data accesses for the
3851 structures to be transformed. For each structure
3852 field it updates the count field in field_entry. */
3855 collect_data_accesses (void)
3857 struct cgraph_node
*c_node
;
3859 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3861 enum availability avail
= cgraph_function_body_availability (c_node
);
3863 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3865 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3867 collect_accesses_in_func (func
);
3868 exclude_alloc_and_field_accs (c_node
);
3872 check_cond_exprs ();
3873 /* Print collected accesses. */
3877 /* We do not bother to transform cold structures.
3878 Coldness of the structure is defined relatively
3879 to the highest structure count among the structures
3880 to be transformed. It's triggered by the compiler parameter
3882 --param struct-reorg-cold-struct-ratio=<value>
3884 where <value> ranges from 0 to 100. Structures with count ratios
3885 that are less than this parameter are considered to be cold. */
3888 exclude_cold_structs (void)
3890 gcov_type hottest
= 0;
3894 /* We summarize counts of fields of a structure into the structure count. */
3895 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3896 sum_counts (str
, &hottest
);
3898 /* Remove cold structures from structures vector. */
3900 while (VEC_iterate (structure
, structures
, i
, str
))
3901 if (str
->count
* 100 < (hottest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3905 fprintf (dump_file
, "\nThe structure ");
3906 print_generic_expr (dump_file
, str
->decl
, 0);
3907 fprintf (dump_file
, " is cold.");
3909 remove_structure (i
);
3915 /* This function decomposes original structure into substructures,
3924 for (i
= 0; VEC_iterate (structure
, structures
, i
, str
); i
++)
3925 peel_hot_fields (str
);
3929 /* Do the actual transformation for each structure
3930 from the structures hashtable. */
3935 /* Check that there is a work to do. */
3936 if (!VEC_length (structure
, structures
))
3939 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3946 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3947 VEC_length (structure
, structures
));
3951 /* Generate new types. */
3952 create_new_types ();
3955 /* Create new global variables. */
3956 create_new_global_vars ();
3957 dump_new_vars (new_global_vars
);
3959 /* Decompose structures for each function separately. */
3962 /* Free auxiliary data collected for global variables. */
3963 free_new_vars_htab (new_global_vars
);
3966 /* Free all auxiliary data used by this optimization. */
3969 free_data_structs (void)
3972 free_alloc_sites ();
3975 /* Perform structure decomposition (peeling). */
3978 reorg_structs (void)
3982 /* Collect structure types. */
3983 collect_structures ();
3985 /* Collect structure allocation sites. */
3986 collect_allocation_sites ();
3988 /* Collect structure accesses. */
3989 collect_data_accesses ();
3991 /* We transform only hot structures. */
3992 exclude_cold_structs ();
3995 /* Decompose structures into substructures, i.e. clusters. */
3999 /* Do the actual transformation for each structure
4000 from the structures hashtable. */
4003 /* Free all auxiliary data used by this optimization. */
4004 free_data_structs ();
4007 /* Struct-reorg optimization entry point function. */
4010 reorg_structs_drive (void)
4016 /* Struct-reorg optimization gate function. */
4019 struct_reorg_gate (void)
4021 return flag_ipa_struct_reorg
4022 && flag_whole_program
4026 struct simple_ipa_opt_pass pass_ipa_struct_reorg
=
4030 "ipa_struct_reorg", /* name */
4031 struct_reorg_gate
, /* gate */
4032 reorg_structs_drive
, /* execute */
4035 0, /* static_pass_number */
4036 TV_INTEGRATION
, /* tv_id */
4037 0, /* properties_required */
4038 0, /* properties_provided */
4039 0, /* properties_destroyed */
4040 TODO_verify_ssa
, /* todo_flags_start */
4041 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */