1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008, 2009, 2010 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"
41 #include "diagnostic.h"
42 #include "tree-pretty-print.h"
43 #include "gimple-pretty-print.h"
49 #include "basic-block.h"
50 #include "tree-iterator.h"
51 #include "tree-pass.h"
52 #include "ipa-struct-reorg.h"
54 #include "ipa-type-escape.h"
55 #include "tree-dump.h"
58 /* This optimization implements structure peeling.
60 For example, given a structure type:
68 it can be peeled into two structure types as follows:
70 typedef struct and typedef struct
76 or can be fully peeled:
93 When structure type is peeled all instances and their accesses
94 in the program are updated accordingly. For example, if there is
99 and structure type str_t was peeled into two structures str_t_0
100 and str_t_1 as it was shown above, then array A will be replaced
101 by two arrays as follows:
106 The field access of field a of element i of array A: A[i].a will be
107 replaced by an access to field a of element i of array A_0: A_0[i].a.
109 This optimization also supports dynamically allocated arrays.
110 If array of structures was allocated by malloc function:
112 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
114 the allocation site will be replaced to reflect new structure types:
116 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
117 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
119 The field access through the pointer p[i].a will be changed by p_0[i].a.
121 The goal of structure peeling is to improve spatial locality.
122 For example, if one of the fields of a structure is accessed frequently
125 for (i = 0; i < N; i++)
130 the allocation of field a of str_t contiguously in memory will
131 increase the chances of fetching the field from cache.
133 The analysis part of this optimization is based on the frequency of
134 field accesses, which are collected all over the program.
135 Then the fields with the frequencies that satisfy the following condition
136 get peeled out of the structure:
138 freq(f) > C * max_field_freq_in_struct
140 where max_field_freq_in_struct is the maximum field frequency
141 in the structure. C is a constant defining which portion of
142 max_field_freq_in_struct the fields should have in order to be peeled.
144 If profiling information is provided, it is used to calculate the
145 frequency of field accesses. Otherwise, the structure is fully peeled.
147 IPA type-escape analysis is used to determine when it is safe
150 The optimization is activated by flag -fipa-struct-reorg. */
152 /* New variables created by this optimization.
153 When doing struct peeling, each variable of
154 the original struct type will be replaced by
155 the set of new variables corresponding to
156 the new structure types. */
157 struct new_var_data
{
158 /* VAR_DECL for original struct type. */
160 /* Vector of new variables. */
161 VEC(tree
, heap
) *new_vars
;
164 typedef struct new_var_data
*new_var
;
165 typedef const struct new_var_data
*const_new_var
;
167 /* This structure represents allocation site of the structure. */
168 typedef struct alloc_site
174 DEF_VEC_O (alloc_site_t
);
175 DEF_VEC_ALLOC_O (alloc_site_t
, heap
);
177 /* Allocation sites that belong to the same function. */
178 struct func_alloc_sites
181 /* Vector of allocation sites for function. */
182 VEC (alloc_site_t
, heap
) *allocs
;
185 typedef struct func_alloc_sites
*fallocs_t
;
186 typedef const struct func_alloc_sites
*const_fallocs_t
;
188 /* All allocation sites in the program. */
189 htab_t alloc_sites
= NULL
;
191 /* New global variables. Generated once for whole program. */
192 htab_t new_global_vars
;
194 /* New local variables. Generated per-function. */
195 htab_t new_local_vars
;
197 /* Vector of structures to be transformed. */
198 typedef struct data_structure structure
;
199 DEF_VEC_O (structure
);
200 DEF_VEC_ALLOC_O (structure
, heap
);
201 VEC (structure
, heap
) *structures
;
203 /* Forward declarations. */
204 static bool is_equal_types (tree
, tree
);
206 /* Strip structure TYPE from pointers and arrays. */
209 strip_type (tree type
)
211 gcc_assert (TYPE_P (type
));
213 while (POINTER_TYPE_P (type
)
214 || TREE_CODE (type
) == ARRAY_TYPE
)
215 type
= TREE_TYPE (type
);
220 /* This function returns type of VAR. */
223 get_type_of_var (tree var
)
228 if (TREE_CODE (var
) == PARM_DECL
)
229 return DECL_ARG_TYPE (var
);
231 return TREE_TYPE (var
);
234 /* Set of actions we do for each newly generated STMT. */
237 finalize_stmt (gimple stmt
)
240 mark_symbols_for_renaming (stmt
);
243 /* This function finalizes STMT and appends it to the list STMTS. */
246 finalize_stmt_and_append (gimple_seq
*stmts
, gimple stmt
)
248 gimple_seq_add_stmt (stmts
, stmt
);
249 finalize_stmt (stmt
);
252 /* This function returns true if two fields FIELD1 and FIELD2 are
253 semantically equal, and false otherwise. */
256 compare_fields (tree field1
, tree field2
)
258 if (DECL_NAME (field1
) && DECL_NAME (field2
))
260 const char *name1
= IDENTIFIER_POINTER (DECL_NAME (field1
));
261 const char *name2
= IDENTIFIER_POINTER (DECL_NAME (field2
));
263 gcc_assert (name1
&& name2
);
265 if (strcmp (name1
, name2
))
269 else if (DECL_NAME (field1
) || DECL_NAME (field2
))
272 if (!is_equal_types (TREE_TYPE (field1
), TREE_TYPE (field2
)))
278 /* Given structure type SRT_TYPE and field FIELD,
279 this function is looking for a field with the same name
280 and type as FIELD in STR_TYPE. It returns it if found,
281 or NULL_TREE otherwise. */
284 find_field_in_struct_1 (tree str_type
, tree field
)
288 if (!DECL_NAME (field
))
291 for (str_field
= TYPE_FIELDS (str_type
); str_field
;
292 str_field
= TREE_CHAIN (str_field
))
295 if (!DECL_NAME (str_field
))
298 if (compare_fields (field
, str_field
))
305 /* Given a field declaration FIELD_DECL, this function
306 returns corresponding field entry in structure STR. */
308 static struct field_entry
*
309 find_field_in_struct (d_str str
, tree field_decl
)
313 tree field
= find_field_in_struct_1 (str
->decl
, field_decl
);
315 for (i
= 0; i
< str
->num_fields
; i
++)
316 if (str
->fields
[i
].decl
== field
)
317 return &(str
->fields
[i
]);
322 /* This function checks whether ARG is a result of multiplication
323 of some number by STRUCT_SIZE. If yes, the function returns true
324 and this number is filled into NUM. */
327 is_result_of_mult (tree arg
, tree
*num
, tree struct_size
)
329 gimple size_def_stmt
= SSA_NAME_DEF_STMT (arg
);
331 /* If the allocation statement was of the form
332 D.2229_10 = <alloc_func> (D.2228_9);
333 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
335 if (size_def_stmt
&& is_gimple_assign (size_def_stmt
))
337 tree lhs
= gimple_assign_lhs (size_def_stmt
);
339 /* We expect temporary here. */
340 if (!is_gimple_reg (lhs
))
343 if (gimple_assign_rhs_code (size_def_stmt
) == MULT_EXPR
)
345 tree arg0
= gimple_assign_rhs1 (size_def_stmt
);
346 tree arg1
= gimple_assign_rhs2 (size_def_stmt
);
348 if (operand_equal_p (arg0
, struct_size
, OEP_ONLY_CONST
))
354 if (operand_equal_p (arg1
, struct_size
, OEP_ONLY_CONST
))
367 /* This function returns true if access ACC corresponds to the pattern
368 generated by compiler when an address of element i of an array
369 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
370 pattern is recognized correctly, this function returns true
371 and fills missing fields in ACC. Otherwise it returns false. */
374 decompose_indirect_ref_acc (tree str_decl
, struct field_access_site
*acc
)
377 tree struct_size
, op0
, op1
;
379 enum tree_code rhs_code
;
381 ref_var
= TREE_OPERAND (acc
->ref
, 0);
383 if (TREE_CODE (ref_var
) != SSA_NAME
)
386 acc
->ref_def_stmt
= SSA_NAME_DEF_STMT (ref_var
);
387 if (!(acc
->ref_def_stmt
)
388 || (gimple_code (acc
->ref_def_stmt
) != GIMPLE_ASSIGN
))
391 rhs_code
= gimple_assign_rhs_code (acc
->ref_def_stmt
);
393 if (rhs_code
!= PLUS_EXPR
394 && rhs_code
!= MINUS_EXPR
395 && rhs_code
!= POINTER_PLUS_EXPR
)
398 op0
= gimple_assign_rhs1 (acc
->ref_def_stmt
);
399 op1
= gimple_assign_rhs2 (acc
->ref_def_stmt
);
401 if (!is_array_access_through_pointer_and_index (rhs_code
, op0
, op1
,
402 &acc
->base
, &acc
->offset
,
407 before_cast
= SINGLE_SSA_TREE_OPERAND (acc
->cast_stmt
, SSA_OP_USE
);
409 before_cast
= acc
->offset
;
415 if (SSA_NAME_IS_DEFAULT_DEF (before_cast
))
418 struct_size
= TYPE_SIZE_UNIT (str_decl
);
420 if (!is_result_of_mult (before_cast
, &acc
->num
, struct_size
))
423 /* ??? Add TREE_OPERAND (acc->ref, 1) to acc->offset. */
424 if (!integer_zerop (TREE_OPERAND (acc
->ref
, 1)))
431 /* This function checks whether the access ACC of structure type STR
432 is of the form suitable for transformation. If yes, it returns true.
436 decompose_access (tree str_decl
, struct field_access_site
*acc
)
438 gcc_assert (acc
->ref
);
440 if (TREE_CODE (acc
->ref
) == MEM_REF
)
441 return decompose_indirect_ref_acc (str_decl
, acc
);
442 else if (TREE_CODE (acc
->ref
) == ARRAY_REF
)
444 else if (TREE_CODE (acc
->ref
) == VAR_DECL
)
450 /* This function creates empty field_access_site node. */
452 static inline struct field_access_site
*
453 make_field_acc_node (void)
455 return XCNEW (struct field_access_site
);
458 /* This function returns the structure field access, defined by STMT,
459 if it is already in hashtable of function accesses F_ACCS. */
461 static struct field_access_site
*
462 is_in_field_accs (gimple stmt
, htab_t f_accs
)
464 return (struct field_access_site
*)
465 htab_find_with_hash (f_accs
, stmt
, htab_hash_pointer (stmt
));
468 /* This function adds an access ACC to the hashtable
469 F_ACCS of field accesses. */
472 add_field_acc_to_acc_sites (struct field_access_site
*acc
,
477 gcc_assert (!is_in_field_accs (acc
->stmt
, f_accs
));
478 slot
= htab_find_slot_with_hash (f_accs
, acc
->stmt
,
479 htab_hash_pointer (acc
->stmt
),
484 /* This function adds the VAR to vector of variables of
485 an access site defined by statement STMT. If access entry
486 with statement STMT does not exist in hashtable of
487 accesses ACCS, this function creates it. */
490 add_access_to_acc_sites (gimple stmt
, tree var
, htab_t accs
)
492 struct access_site
*acc
;
494 acc
= (struct access_site
*)
495 htab_find_with_hash (accs
, stmt
, htab_hash_pointer (stmt
));
501 acc
= XNEW (struct access_site
);
503 if (!is_gimple_debug (stmt
))
504 acc
->vars
= VEC_alloc (tree
, heap
, 10);
507 slot
= htab_find_slot_with_hash (accs
, stmt
,
508 htab_hash_pointer (stmt
), INSERT
);
511 if (!is_gimple_debug (stmt
))
512 VEC_safe_push (tree
, heap
, acc
->vars
, var
);
515 /* This function adds NEW_DECL to function
516 referenced vars, and marks it for renaming. */
519 finalize_var_creation (tree new_decl
)
521 add_referenced_var (new_decl
);
522 mark_sym_for_renaming (new_decl
);
525 /* This function finalizes VAR creation if it is a global VAR_DECL. */
528 finalize_global_creation (tree var
)
530 if (TREE_CODE (var
) == VAR_DECL
531 && is_global_var (var
))
532 finalize_var_creation (var
);
535 /* This function inserts NEW_DECL to varpool. */
538 insert_global_to_varpool (tree new_decl
)
540 struct varpool_node
*new_node
;
542 new_node
= varpool_node (new_decl
);
543 notice_global_symbol (new_decl
);
544 varpool_mark_needed_node (new_node
);
545 varpool_finalize_decl (new_decl
);
548 /* This function finalizes the creation of new variables,
549 defined by *SLOT->new_vars. */
552 finalize_new_vars_creation (void **slot
, void *data ATTRIBUTE_UNUSED
)
554 new_var n_var
= *(new_var
*) slot
;
558 FOR_EACH_VEC_ELT (tree
, n_var
->new_vars
, i
, var
)
559 finalize_var_creation (var
);
563 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
564 It returns it, if found, and NULL_TREE otherwise. */
567 find_var_in_new_vars_vec (new_var var
, tree new_type
)
572 FOR_EACH_VEC_ELT (tree
, var
->new_vars
, i
, n_var
)
574 tree type
= strip_type(get_type_of_var (n_var
));
577 if (type
== new_type
)
584 /* This function returns new_var node, the orig_var of which is DECL.
585 It looks for new_var's in NEW_VARS_HTAB. If not found,
586 the function returns NULL. */
589 is_in_new_vars_htab (tree decl
, htab_t new_vars_htab
)
591 return (new_var
) htab_find_with_hash (new_vars_htab
, decl
,
595 /* Given original variable ORIG_VAR, this function returns
596 new variable corresponding to it of NEW_TYPE type. */
599 find_new_var_of_type (tree orig_var
, tree new_type
)
602 gcc_assert (orig_var
&& new_type
);
604 if (TREE_CODE (orig_var
) == SSA_NAME
)
605 orig_var
= SSA_NAME_VAR (orig_var
);
607 var
= is_in_new_vars_htab (orig_var
, new_global_vars
);
609 var
= is_in_new_vars_htab (orig_var
, new_local_vars
);
611 return find_var_in_new_vars_vec (var
, new_type
);
614 /* This function generates stmt:
615 res = NUM * sizeof(TYPE) and returns it.
616 res is filled into RES. */
619 gen_size (tree num
, tree type
, tree
*res
)
621 tree struct_size
= TYPE_SIZE_UNIT (type
);
622 HOST_WIDE_INT struct_size_int
= TREE_INT_CST_LOW (struct_size
);
625 *res
= create_tmp_var (TREE_TYPE (num
), NULL
);
628 add_referenced_var (*res
);
630 if (exact_log2 (struct_size_int
) == -1)
632 tree size
= build_int_cst (TREE_TYPE (num
), struct_size_int
);
633 new_stmt
= gimple_build_assign (*res
, fold_build2 (MULT_EXPR
,
639 tree C
= build_int_cst (TREE_TYPE (num
), exact_log2 (struct_size_int
));
641 new_stmt
= gimple_build_assign (*res
, fold_build2 (LSHIFT_EXPR
,
646 finalize_stmt (new_stmt
);
650 /* This function generates and returns a statement, that cast variable
651 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
652 into RES_P. ORIG_CAST_STMT is the original cast statement. */
655 gen_cast_stmt (tree before_cast
, tree new_type
, gimple orig_cast_stmt
,
661 lhs
= gimple_assign_lhs (orig_cast_stmt
);
662 new_lhs
= find_new_var_of_type (lhs
, new_type
);
663 gcc_assert (new_lhs
);
665 new_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, new_lhs
, before_cast
, 0);
666 finalize_stmt (new_stmt
);
671 /* This function builds an edge between BB and E->dest and updates
672 phi nodes of E->dest. It returns newly created edge. */
675 make_edge_and_fix_phis_of_dest (basic_block bb
, edge e
)
679 gimple_stmt_iterator si
;
681 new_e
= make_edge (bb
, e
->dest
, e
->flags
);
683 for (si
= gsi_start_phis (new_e
->dest
); !gsi_end_p (si
); gsi_next (&si
))
685 gimple phi
= gsi_stmt (si
);
686 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
687 add_phi_arg (phi
, arg
, new_e
, gimple_phi_arg_location_from_edge (phi
, e
));
693 /* This function inserts NEW_STMT before STMT. */
696 insert_before_stmt (gimple stmt
, gimple new_stmt
)
698 gimple_stmt_iterator bsi
;
700 if (!stmt
|| !new_stmt
)
703 bsi
= gsi_for_stmt (stmt
);
704 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
707 /* Insert NEW_STMTS after STMT. */
710 insert_seq_after_stmt (gimple stmt
, gimple_seq new_stmts
)
712 gimple_stmt_iterator bsi
;
714 if (!stmt
|| !new_stmts
)
717 bsi
= gsi_for_stmt (stmt
);
718 gsi_insert_seq_after (&bsi
, new_stmts
, GSI_SAME_STMT
);
721 /* Insert NEW_STMT after STMT. */
724 insert_after_stmt (gimple stmt
, gimple new_stmt
)
726 gimple_stmt_iterator bsi
;
728 if (!stmt
|| !new_stmt
)
731 bsi
= gsi_for_stmt (stmt
);
732 gsi_insert_after (&bsi
, new_stmt
, GSI_SAME_STMT
);
735 /* This function returns vector of allocation sites
736 that appear in function FN_DECL. */
739 get_fallocs (tree fn_decl
)
741 return (fallocs_t
) htab_find_with_hash (alloc_sites
, fn_decl
,
742 htab_hash_pointer (fn_decl
));
745 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
746 and it is a part of allocation of a structure,
747 then it is usually followed by a cast stmt
748 p_8 = (struct str_t *) D.2225_7;
749 which is returned by this function. */
752 get_final_alloc_stmt (gimple alloc_stmt
)
761 if (!is_gimple_call (alloc_stmt
))
764 alloc_res
= gimple_get_lhs (alloc_stmt
);
766 if (TREE_CODE (alloc_res
) != SSA_NAME
)
769 if (!single_imm_use (alloc_res
, &use_p
, &final_stmt
))
775 /* This function returns true if STMT is one of allocation
776 sites of function FN_DECL. It returns false otherwise. */
779 is_part_of_malloc (gimple stmt
, tree fn_decl
)
781 fallocs_t fallocs
= get_fallocs (fn_decl
);
788 FOR_EACH_VEC_ELT (alloc_site_t
, fallocs
->allocs
, i
, call
)
789 if (call
->stmt
== stmt
790 || get_final_alloc_stmt (call
->stmt
) == stmt
)
796 /* Auxiliary structure for a lookup over field accesses. */
797 struct find_stmt_data
803 /* This function looks for DATA->stmt among
804 the statements involved in the field access,
805 defined by SLOT. It stops when it's found. */
808 find_in_field_accs (void **slot
, void *data
)
810 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
811 gimple stmt
= ((struct find_stmt_data
*)data
)->stmt
;
813 if (f_acc
->stmt
== stmt
814 || f_acc
->ref_def_stmt
== stmt
815 || f_acc
->cast_stmt
== stmt
)
817 ((struct find_stmt_data
*)data
)->found
= true;
824 /* This function checks whether STMT is part of field
825 accesses of structure STR. It returns true, if found,
826 and false otherwise. */
829 is_part_of_field_access (gimple stmt
, d_str str
)
833 for (i
= 0; i
< str
->num_fields
; i
++)
835 struct find_stmt_data data
;
839 if (str
->fields
[i
].acc_sites
)
840 htab_traverse (str
->fields
[i
].acc_sites
, find_in_field_accs
, &data
);
849 /* Auxiliary data for exclude_from_accs function. */
857 /* This function returns component_ref with the BASE and
858 field named FIELD_ID from structure TYPE. */
861 build_comp_ref (tree base
, tree field_id
, tree type
)
867 /* Find field of structure type with the same name as field_id. */
868 for (field
= TYPE_FIELDS (type
); field
; field
= TREE_CHAIN (field
))
870 if (DECL_NAME (field
) == field_id
)
879 return build3 (COMPONENT_REF
, TREE_TYPE (field
), base
, field
, NULL_TREE
);
883 /* This struct represent data used for walk_tree
884 called from function find_pos_in_stmt.
885 - ref is a tree to be found,
886 - and pos is a pointer that points to ref in stmt. */
895 /* This is a callback function for walk_tree, called from
896 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
897 When *TP is equal to DATA->ref, the walk_tree stops,
898 and found position, equal to TP, is assigned to DATA->pos. */
901 find_pos_in_stmt_1 (tree
*tp
, int *walk_subtrees
, void * data
)
903 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
904 struct ref_pos
*r_pos
= (struct ref_pos
*) wi
->info
;
905 tree ref
= r_pos
->ref
;
908 if (t
== ref
|| (TREE_CODE (t
) == SSA_NAME
&& SSA_NAME_VAR (t
) == ref
))
914 r_pos
->container
= t
;
920 /* This function looks for the pointer of REF in STMT,
921 It returns it, if found, and NULL otherwise. */
924 find_pos_in_stmt (gimple stmt
, tree ref
, struct ref_pos
* r_pos
)
926 struct walk_stmt_info wi
;
930 r_pos
->container
= NULL_TREE
;
931 memset (&wi
, 0, sizeof (wi
));
933 walk_gimple_op (stmt
, find_pos_in_stmt_1
, &wi
);
938 /* This structure is used to represent array
939 or pointer-to wrappers of structure type.
940 For example, if type1 is structure type,
941 then for type1 ** we generate two type_wrapper
942 structures with wrap = 0 each one.
943 It's used to unwind the original type up to
944 structure type, replace it with the new structure type
945 and wrap it back in the opposite order. */
947 typedef struct type_wrapper
949 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
952 /* Relevant for arrays as domain or index. */
956 DEF_VEC_O (type_wrapper_t
);
957 DEF_VEC_ALLOC_O (type_wrapper_t
, heap
);
959 /* This function replace field access ACC by the new
960 field access of structure type NEW_TYPE. */
963 replace_field_acc (struct field_access_site
*acc
, tree new_type
)
965 tree ref_var
= acc
->ref
;
970 tree field_id
= DECL_NAME (acc
->field_decl
);
971 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
972 type_wrapper_t
*wr_p
= NULL
;
973 struct ref_pos r_pos
;
975 while (TREE_CODE (ref_var
) == MEM_REF
976 || TREE_CODE (ref_var
) == ARRAY_REF
)
980 if (TREE_CODE (ref_var
) == MEM_REF
)
988 wr
.domain
= TREE_OPERAND (ref_var
, 1);
991 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
992 ref_var
= TREE_OPERAND (ref_var
, 0);
995 new_ref
= find_new_var_of_type (ref_var
, new_type
);
996 finalize_global_creation (new_ref
);
998 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1000 tree type
= TREE_TYPE (TREE_TYPE (new_ref
));
1002 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1003 if (wr_p
->wrap
) /* Array. */
1004 new_ref
= build4 (ARRAY_REF
, type
, new_ref
,
1005 wr_p
->domain
, NULL_TREE
, NULL_TREE
);
1007 new_ref
= build_simple_mem_ref (new_ref
);
1008 VEC_pop (type_wrapper_t
, wrapper
);
1011 new_acc
= build_comp_ref (new_ref
, field_id
, new_type
);
1012 VEC_free (type_wrapper_t
, heap
, wrapper
);
1014 if (is_gimple_assign (acc
->stmt
))
1016 lhs
= gimple_assign_lhs (acc
->stmt
);
1017 rhs
= gimple_assign_rhs1 (acc
->stmt
);
1019 if (lhs
== acc
->comp_ref
)
1020 gimple_assign_set_lhs (acc
->stmt
, new_acc
);
1021 else if (rhs
== acc
->comp_ref
)
1022 gimple_assign_set_rhs1 (acc
->stmt
, new_acc
);
1025 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
, &r_pos
);
1032 pos
= find_pos_in_stmt (acc
->stmt
, acc
->comp_ref
, &r_pos
);
1037 finalize_stmt (acc
->stmt
);
1040 /* This function replace field access ACC by a new field access
1041 of structure type NEW_TYPE. */
1044 replace_field_access_stmt (struct field_access_site
*acc
, tree new_type
)
1047 if (TREE_CODE (acc
->ref
) == MEM_REF
1048 ||TREE_CODE (acc
->ref
) == ARRAY_REF
1049 ||TREE_CODE (acc
->ref
) == VAR_DECL
)
1050 replace_field_acc (acc
, new_type
);
1055 /* This function looks for d_str, represented by TYPE, in the structures
1056 vector. If found, it returns an index of found structure. Otherwise
1057 it returns a length of the structures vector. */
1060 find_structure (tree type
)
1065 type
= TYPE_MAIN_VARIANT (type
);
1067 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
1068 if (is_equal_types (str
->decl
, type
))
1071 return VEC_length (structure
, structures
);
1074 /* In this function we create new statements that have the same
1075 form as ORIG_STMT, but of type NEW_TYPE. The statements
1076 treated by this function are simple assignments,
1077 like assignments: p.8_7 = p; or statements with rhs of
1078 tree codes PLUS_EXPR and MINUS_EXPR. */
1081 create_base_plus_offset (gimple orig_stmt
, tree new_type
, tree offset
)
1086 tree new_op0
= NULL_TREE
, new_op1
= NULL_TREE
;
1088 lhs
= gimple_assign_lhs (orig_stmt
);
1090 gcc_assert (TREE_CODE (lhs
) == VAR_DECL
1091 || TREE_CODE (lhs
) == SSA_NAME
);
1093 new_lhs
= find_new_var_of_type (lhs
, new_type
);
1094 gcc_assert (new_lhs
);
1095 finalize_var_creation (new_lhs
);
1097 switch (gimple_assign_rhs_code (orig_stmt
))
1101 case POINTER_PLUS_EXPR
:
1103 tree op0
= gimple_assign_rhs1 (orig_stmt
);
1104 tree op1
= gimple_assign_rhs2 (orig_stmt
);
1105 unsigned str0
, str1
;
1106 unsigned length
= VEC_length (structure
, structures
);
1109 str0
= find_structure (strip_type (get_type_of_var (op0
)));
1110 str1
= find_structure (strip_type (get_type_of_var (op1
)));
1111 gcc_assert ((str0
!= length
) || (str1
!= length
));
1114 new_op0
= find_new_var_of_type (op0
, new_type
);
1116 new_op1
= find_new_var_of_type (op1
, new_type
);
1129 new_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt
),
1130 new_lhs
, new_op0
, new_op1
);
1131 finalize_stmt (new_stmt
);
1136 /* Given a field access F_ACC of the FIELD, this function
1137 replaces it by the new field access. */
1140 create_new_field_access (struct field_access_site
*f_acc
,
1141 struct field_entry field
)
1143 tree new_type
= field
.field_mapping
;
1148 tree cast_res
= NULL
;
1152 mult_stmt
= gen_size (f_acc
->num
, new_type
, &size_res
);
1153 insert_before_stmt (f_acc
->ref_def_stmt
, mult_stmt
);
1156 if (f_acc
->cast_stmt
)
1158 cast_stmt
= gen_cast_stmt (size_res
, new_type
,
1159 f_acc
->cast_stmt
, &cast_res
);
1160 insert_after_stmt (f_acc
->cast_stmt
, cast_stmt
);
1163 if (f_acc
->ref_def_stmt
)
1171 new_stmt
= create_base_plus_offset (f_acc
->ref_def_stmt
,
1173 insert_after_stmt (f_acc
->ref_def_stmt
, new_stmt
);
1176 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1177 D.2162_18 by an appropriate variable of new_type type. */
1178 replace_field_access_stmt (f_acc
, new_type
);
1181 /* This function creates a new condition statement
1182 corresponding to the original COND_STMT, adds new basic block
1183 and redirects condition edges. NEW_VAR is a new condition
1184 variable located in the condition statement at the position POS. */
1187 create_new_stmts_for_cond_expr_1 (tree new_var
, gimple cond_stmt
, unsigned pos
)
1190 edge true_e
= NULL
, false_e
= NULL
;
1192 gimple_stmt_iterator si
;
1194 extract_true_false_edges_from_block (gimple_bb (cond_stmt
),
1197 new_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
1198 pos
== 0 ? new_var
: gimple_cond_lhs (cond_stmt
),
1199 pos
== 1 ? new_var
: gimple_cond_rhs (cond_stmt
),
1203 finalize_stmt (new_stmt
);
1205 /* Create new basic block after bb. */
1206 new_bb
= create_empty_bb (gimple_bb (cond_stmt
));
1208 /* Add new condition stmt to the new_bb. */
1209 si
= gsi_start_bb (new_bb
);
1210 gsi_insert_after (&si
, new_stmt
, GSI_NEW_STMT
);
1212 /* Create false and true edges from new_bb. */
1213 make_edge_and_fix_phis_of_dest (new_bb
, true_e
);
1214 make_edge_and_fix_phis_of_dest (new_bb
, false_e
);
1216 /* Redirect one of original edges to point to new_bb. */
1217 if (gimple_cond_code (cond_stmt
) == NE_EXPR
)
1218 redirect_edge_succ (true_e
, new_bb
);
1220 redirect_edge_succ (false_e
, new_bb
);
1223 /* This function creates new condition statements corresponding
1224 to original condition STMT, one for each new type, and
1225 recursively redirect edges to newly generated basic blocks. */
1228 create_new_stmts_for_cond_expr (gimple stmt
)
1230 tree arg0
, arg1
, arg
;
1231 unsigned str0
, str1
;
1237 unsigned length
= VEC_length (structure
, structures
);
1239 gcc_assert (gimple_cond_code (stmt
) == EQ_EXPR
1240 || gimple_cond_code (stmt
) == NE_EXPR
);
1242 arg0
= gimple_cond_lhs (stmt
);
1243 arg1
= gimple_cond_rhs (stmt
);
1245 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
1246 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
1248 s0
= (str0
!= length
) ? true : false;
1249 s1
= (str1
!= length
) ? true : false;
1251 gcc_assert (s0
|| s1
);
1252 /* For now we allow only comparison with 0 or NULL. */
1253 gcc_assert (integer_zerop (arg0
) || integer_zerop (arg1
));
1255 str
= integer_zerop (arg0
) ?
1256 VEC_index (structure
, structures
, str1
):
1257 VEC_index (structure
, structures
, str0
);
1258 arg
= integer_zerop (arg0
) ? arg1
: arg0
;
1259 pos
= integer_zerop (arg0
) ? 1 : 0;
1261 FOR_EACH_VEC_ELT (tree
, str
->new_types
, i
, type
)
1265 new_arg
= find_new_var_of_type (arg
, type
);
1266 create_new_stmts_for_cond_expr_1 (new_arg
, stmt
, pos
);
1270 /* This function looks for VAR in STMT, and replace it with NEW_VAR.
1271 If needed, it wraps NEW_VAR in pointers and indirect references
1272 before insertion. */
1275 insert_new_var_in_stmt (gimple stmt
, tree var
, tree new_var
)
1277 struct ref_pos r_pos
;
1280 pos
= find_pos_in_stmt (stmt
, var
, &r_pos
);
1283 while (r_pos
.container
&& (TREE_CODE(r_pos
.container
) == MEM_REF
1284 || TREE_CODE(r_pos
.container
) == ADDR_EXPR
))
1286 if (TREE_CODE(r_pos
.container
) == MEM_REF
)
1287 new_var
= build_simple_mem_ref (new_var
);
1289 new_var
= build_fold_addr_expr (new_var
);
1290 pos
= find_pos_in_stmt (stmt
, r_pos
.container
, &r_pos
);
1297 /* Create a new general access to replace original access ACC
1298 for structure type NEW_TYPE. */
1301 create_general_new_stmt (struct access_site
*acc
, tree new_type
)
1303 gimple old_stmt
= acc
->stmt
;
1305 gimple new_stmt
= gimple_copy (old_stmt
);
1308 /* We are really building a new stmt, clear the virtual operands. */
1309 if (gimple_has_mem_ops (new_stmt
))
1311 gimple_set_vuse (new_stmt
, NULL_TREE
);
1312 gimple_set_vdef (new_stmt
, NULL_TREE
);
1315 FOR_EACH_VEC_ELT (tree
, acc
->vars
, i
, var
)
1317 tree new_var
= find_new_var_of_type (var
, new_type
);
1318 tree lhs
, rhs
= NULL_TREE
;
1320 gcc_assert (new_var
);
1321 finalize_var_creation (new_var
);
1323 if (is_gimple_assign (new_stmt
))
1325 lhs
= gimple_assign_lhs (new_stmt
);
1327 if (TREE_CODE (lhs
) == SSA_NAME
)
1328 lhs
= SSA_NAME_VAR (lhs
);
1329 if (gimple_assign_rhs_code (new_stmt
) == SSA_NAME
)
1330 rhs
= SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt
));
1332 /* It can happen that rhs is a constructor.
1333 Then we have to replace it to be of new_type. */
1334 if (gimple_assign_rhs_code (new_stmt
) == CONSTRUCTOR
)
1336 /* Dealing only with empty constructors right now. */
1337 gcc_assert (VEC_empty (constructor_elt
,
1338 CONSTRUCTOR_ELTS (rhs
)));
1339 rhs
= build_constructor (new_type
, 0);
1340 gimple_assign_set_rhs1 (new_stmt
, rhs
);
1344 gimple_assign_set_lhs (new_stmt
, new_var
);
1345 else if (rhs
== var
)
1346 gimple_assign_set_rhs1 (new_stmt
, new_var
);
1348 insert_new_var_in_stmt (new_stmt
, var
, new_var
);
1351 insert_new_var_in_stmt (new_stmt
, var
, new_var
);
1354 finalize_stmt (new_stmt
);
1358 /* For each new type in STR this function creates new general accesses
1359 corresponding to the original access ACC. */
1362 create_new_stmts_for_general_acc (struct access_site
*acc
, d_str str
)
1365 gimple stmt
= acc
->stmt
;
1368 FOR_EACH_VEC_ELT (tree
, str
->new_types
, i
, type
)
1372 new_stmt
= create_general_new_stmt (acc
, type
);
1373 insert_after_stmt (stmt
, new_stmt
);
1377 /* This function creates a new general access of structure STR
1378 to replace the access ACC. */
1381 create_new_general_access (struct access_site
*acc
, d_str str
)
1383 gimple stmt
= acc
->stmt
;
1384 switch (gimple_code (stmt
))
1387 create_new_stmts_for_cond_expr (stmt
);
1391 /* It is very hard to maintain usable debug info after struct peeling,
1392 for now just reset all debug stmts referencing objects that have
1394 gimple_debug_bind_reset_value (stmt
);
1399 create_new_stmts_for_general_acc (acc
, str
);
1403 /* Auxiliary data for creation of accesses. */
1404 struct create_acc_data
1411 /* This function creates a new general access, defined by SLOT.
1412 DATA is a pointer to create_acc_data structure. */
1415 create_new_acc (void **slot
, void *data
)
1417 struct access_site
*acc
= *(struct access_site
**) slot
;
1418 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1419 d_str str
= ((struct create_acc_data
*)data
)->str
;
1421 if (gimple_bb (acc
->stmt
) == bb
)
1422 create_new_general_access (acc
, str
);
1426 /* This function creates a new field access, defined by SLOT.
1427 DATA is a pointer to create_acc_data structure. */
1430 create_new_field_acc (void **slot
, void *data
)
1432 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1433 basic_block bb
= ((struct create_acc_data
*)data
)->bb
;
1434 d_str str
= ((struct create_acc_data
*)data
)->str
;
1435 int i
= ((struct create_acc_data
*)data
)->field_index
;
1437 if (gimple_bb (f_acc
->stmt
) == bb
)
1438 create_new_field_access (f_acc
, str
->fields
[i
]);
1442 /* This function creates new accesses for the structure
1443 type STR in basic block BB. */
1446 create_new_accs_for_struct (d_str str
, basic_block bb
)
1449 struct create_acc_data dt
;
1453 dt
.field_index
= -1;
1455 for (i
= 0; i
< str
->num_fields
; i
++)
1459 if (str
->fields
[i
].acc_sites
)
1460 htab_traverse (str
->fields
[i
].acc_sites
,
1461 create_new_field_acc
, &dt
);
1464 htab_traverse (str
->accs
, create_new_acc
, &dt
);
1467 /* This function inserts new variables from new_var,
1468 defined by SLOT, into varpool. */
1471 update_varpool_with_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1473 new_var n_var
= *(new_var
*) slot
;
1477 FOR_EACH_VEC_ELT (tree
, n_var
->new_vars
, i
, var
)
1478 insert_global_to_varpool (var
);
1482 /* This function prints a field access site, defined by SLOT. */
1485 dump_field_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
1487 struct field_access_site
*f_acc
=
1488 *(struct field_access_site
**) slot
;
1490 fprintf(dump_file
, "\n");
1492 print_gimple_stmt (dump_file
, f_acc
->stmt
, 0, 0);
1493 if (f_acc
->ref_def_stmt
)
1494 print_gimple_stmt (dump_file
, f_acc
->ref_def_stmt
, 0, 0);
1495 if (f_acc
->cast_stmt
)
1496 print_gimple_stmt (dump_file
, f_acc
->cast_stmt
, 0, 0);
1500 /* Print field accesses from hashtable F_ACCS. */
1503 dump_field_acc_sites (htab_t f_accs
)
1509 htab_traverse (f_accs
, dump_field_acc
, NULL
);
1512 /* Hash value for fallocs_t. */
1515 malloc_hash (const void *x
)
1517 return htab_hash_pointer (((const_fallocs_t
)x
)->func
);
1520 /* This function returns nonzero if function of func_alloc_sites' X
1524 malloc_eq (const void *x
, const void *y
)
1526 return ((const_fallocs_t
)x
)->func
== (const_tree
)y
;
1529 /* This function is a callback for traversal over a structure accesses.
1530 It frees an access represented by SLOT. */
1533 free_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1535 struct access_site
* acc
= *(struct access_site
**) slot
;
1537 VEC_free (tree
, heap
, acc
->vars
);
1542 /* This is a callback function for traversal over field accesses.
1543 It frees a field access represented by SLOT. */
1546 free_field_accs (void **slot
, void *data ATTRIBUTE_UNUSED
)
1548 struct field_access_site
*f_acc
= *(struct field_access_site
**) slot
;
1554 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1555 if it is not there yet. */
1558 add_unsuitable_type (VEC (tree
, heap
) **unsuitable_types
, tree type
)
1566 type
= TYPE_MAIN_VARIANT (type
);
1568 FOR_EACH_VEC_ELT (tree
, *unsuitable_types
, i
, t
)
1569 if (is_equal_types (t
, type
))
1572 if (i
== VEC_length (tree
, *unsuitable_types
))
1573 VEC_safe_push (tree
, heap
, *unsuitable_types
, type
);
1576 /* Given a type TYPE, this function returns the name of the type. */
1579 get_type_name (tree type
)
1581 if (! TYPE_NAME (type
))
1584 if (TREE_CODE (TYPE_NAME (type
)) == IDENTIFIER_NODE
)
1585 return IDENTIFIER_POINTER (TYPE_NAME (type
));
1586 else if (TREE_CODE (TYPE_NAME (type
)) == TYPE_DECL
1587 && DECL_NAME (TYPE_NAME (type
)))
1588 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type
)));
1593 /* This function is a temporary hack to overcome the types problem.
1594 When several compilation units are compiled together
1595 with -combine, the TYPE_MAIN_VARIANT of the same type
1596 can appear differently in different compilation units.
1597 Therefore this function first compares type names.
1598 If there are no names, structure bodies are recursively
1602 is_equal_types (tree type1
, tree type2
)
1604 const char * name1
,* name2
;
1606 if ((!type1
&& type2
)
1607 ||(!type2
&& type1
))
1610 if (!type1
&& !type2
)
1613 if (TREE_CODE (type1
) != TREE_CODE (type2
))
1619 if (TYPE_MAIN_VARIANT (type1
) == TYPE_MAIN_VARIANT (type2
))
1622 name1
= get_type_name (type1
);
1623 name2
= get_type_name (type2
);
1626 return strcmp (name1
, name2
) == 0;
1628 switch (TREE_CODE (type1
))
1631 case REFERENCE_TYPE
:
1633 return is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
));
1639 case QUAL_UNION_TYPE
:
1642 tree field1
, field2
;
1644 /* Compare fields of structure. */
1645 for (field1
= TYPE_FIELDS (type1
), field2
= TYPE_FIELDS (type2
);
1647 field1
= TREE_CHAIN (field1
), field2
= TREE_CHAIN (field2
))
1649 if (!compare_fields (field1
, field2
))
1652 if (field1
|| field2
)
1661 if (TYPE_UNSIGNED (type1
) == TYPE_UNSIGNED (type2
)
1662 && TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
))
1670 tree max1
, min1
, max2
, min2
;
1672 if (!is_equal_types (TREE_TYPE (type1
), TREE_TYPE (type2
)))
1675 d1
= TYPE_DOMAIN (type1
);
1676 d2
= TYPE_DOMAIN (type2
);
1681 max1
= TYPE_MAX_VALUE (d1
);
1682 max2
= TYPE_MAX_VALUE (d2
);
1683 min1
= TYPE_MIN_VALUE (d1
);
1684 min2
= TYPE_MIN_VALUE (d2
);
1686 if (max1
&& max2
&& min1
&& min2
1687 && TREE_CODE (max1
) == TREE_CODE (max2
)
1688 && TREE_CODE (max1
) == INTEGER_CST
1689 && TREE_CODE (min1
) == TREE_CODE (min2
)
1690 && TREE_CODE (min1
) == INTEGER_CST
1691 && tree_int_cst_equal (max1
, max2
)
1692 && tree_int_cst_equal (min1
, min2
))
1704 /* This function free non-field accesses from hashtable ACCS. */
1707 free_accesses (htab_t accs
)
1710 htab_traverse (accs
, free_accs
, NULL
);
1714 /* This function free field accesses hashtable F_ACCS. */
1717 free_field_accesses (htab_t f_accs
)
1720 htab_traverse (f_accs
, free_field_accs
, NULL
);
1721 htab_delete (f_accs
);
1724 /* Update call graph with new edge generated by new MALLOC_STMT.
1725 The edge origin is CONTEXT function. */
1728 update_cgraph_with_malloc_call (gimple malloc_stmt
, tree context
)
1730 struct cgraph_node
*src
, *dest
;
1731 tree malloc_fn_decl
;
1736 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1738 src
= cgraph_node (context
);
1739 dest
= cgraph_node (malloc_fn_decl
);
1740 cgraph_create_edge (src
, dest
, malloc_stmt
,
1741 gimple_bb (malloc_stmt
)->count
,
1742 compute_call_stmt_bb_frequency
1743 (context
, gimple_bb (malloc_stmt
)),
1744 gimple_bb (malloc_stmt
)->loop_depth
);
1747 /* This function generates set of statements required
1748 to allocate number NUM of structures of type NEW_TYPE.
1749 The statements are stored in NEW_STMTS. The statement that contain
1750 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1753 create_new_malloc (gimple malloc_stmt
, tree new_type
, gimple_seq
*new_stmts
,
1756 tree new_malloc_size
;
1757 tree malloc_fn_decl
;
1760 gimple call_stmt
, final_stmt
;
1763 gcc_assert (num
&& malloc_stmt
&& new_type
);
1764 *new_stmts
= gimple_seq_alloc ();
1766 /* Generate argument to malloc as multiplication of num
1767 and size of new_type. */
1768 new_stmt
= gen_size (num
, new_type
, &new_malloc_size
);
1769 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1771 /* Generate new call for malloc. */
1772 malloc_res
= create_tmp_var (ptr_type_node
, NULL
);
1773 add_referenced_var (malloc_res
);
1775 malloc_fn_decl
= gimple_call_fndecl (malloc_stmt
);
1776 call_stmt
= gimple_build_call (malloc_fn_decl
, 1, new_malloc_size
);
1777 gimple_call_set_lhs (call_stmt
, malloc_res
);
1778 finalize_stmt_and_append (new_stmts
, call_stmt
);
1780 /* Create new cast statement. */
1781 final_stmt
= get_final_alloc_stmt (malloc_stmt
);
1782 gcc_assert (final_stmt
);
1783 new_stmt
= gen_cast_stmt (malloc_res
, new_type
, final_stmt
, &cast_res
);
1784 gimple_seq_add_stmt (new_stmts
, new_stmt
);
1789 /* This function returns a tree representing
1790 the number of instances of structure STR_DECL allocated
1791 by allocation STMT. If new statements are generated,
1792 they are filled into NEW_STMTS_P. */
1795 gen_num_of_structs_in_malloc (gimple stmt
, tree str_decl
,
1796 gimple_seq
*new_stmts_p
)
1800 HOST_WIDE_INT struct_size_int
;
1805 /* Get malloc argument. */
1806 if (!is_gimple_call (stmt
))
1809 arg
= gimple_call_arg (stmt
, 0);
1811 if (TREE_CODE (arg
) != SSA_NAME
1812 && !TREE_CONSTANT (arg
))
1815 struct_size
= TYPE_SIZE_UNIT (str_decl
);
1816 struct_size_int
= TREE_INT_CST_LOW (struct_size
);
1818 gcc_assert (struct_size
);
1820 if (TREE_CODE (arg
) == SSA_NAME
)
1825 if (is_result_of_mult (arg
, &num
, struct_size
))
1828 num
= create_tmp_var (integer_type_node
, NULL
);
1831 add_referenced_var (num
);
1833 if (exact_log2 (struct_size_int
) == -1)
1834 div_stmt
= gimple_build_assign_with_ops (TRUNC_DIV_EXPR
, num
, arg
,
1838 tree C
= build_int_cst (integer_type_node
,
1839 exact_log2 (struct_size_int
));
1841 div_stmt
= gimple_build_assign_with_ops (RSHIFT_EXPR
, num
, arg
, C
);
1843 gimple_seq_add_stmt (new_stmts_p
, div_stmt
);
1844 finalize_stmt (div_stmt
);
1848 if (CONSTANT_CLASS_P (arg
)
1849 && multiple_of_p (TREE_TYPE (struct_size
), arg
, struct_size
))
1850 return int_const_binop (TRUNC_DIV_EXPR
, arg
, struct_size
, 0);
1855 /* This function is a callback for traversal on new_var's hashtable.
1856 SLOT is a pointer to new_var. This function prints to dump_file
1857 an original variable and all new variables from the new_var
1858 pointed by *SLOT. */
1861 dump_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
1863 new_var n_var
= *(new_var
*) slot
;
1868 var_type
= get_type_of_var (n_var
->orig_var
);
1870 fprintf (dump_file
, "\nOrig var: ");
1871 print_generic_expr (dump_file
, n_var
->orig_var
, 0);
1872 fprintf (dump_file
, " of type ");
1873 print_generic_expr (dump_file
, var_type
, 0);
1874 fprintf (dump_file
, "\n");
1877 VEC_iterate (tree
, n_var
->new_vars
, i
, var
); i
++)
1879 var_type
= get_type_of_var (var
);
1881 fprintf (dump_file
, " ");
1882 print_generic_expr (dump_file
, var
, 0);
1883 fprintf (dump_file
, " of type ");
1884 print_generic_expr (dump_file
, var_type
, 0);
1885 fprintf (dump_file
, "\n");
1890 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1893 copy_decl_attributes (tree new_decl
, tree orig_decl
)
1896 DECL_ARTIFICIAL (new_decl
) = 1;
1897 DECL_EXTERNAL (new_decl
) = DECL_EXTERNAL (orig_decl
);
1898 TREE_STATIC (new_decl
) = TREE_STATIC (orig_decl
);
1899 TREE_PUBLIC (new_decl
) = TREE_PUBLIC (orig_decl
);
1900 TREE_USED (new_decl
) = TREE_USED (orig_decl
);
1901 DECL_CONTEXT (new_decl
) = DECL_CONTEXT (orig_decl
);
1902 TREE_THIS_VOLATILE (new_decl
) = TREE_THIS_VOLATILE (orig_decl
);
1903 TREE_ADDRESSABLE (new_decl
) = TREE_ADDRESSABLE (orig_decl
);
1905 if (TREE_CODE (orig_decl
) == VAR_DECL
)
1907 TREE_READONLY (new_decl
) = TREE_READONLY (orig_decl
);
1908 DECL_TLS_MODEL (new_decl
) = DECL_TLS_MODEL (orig_decl
);
1912 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1913 the same way as a structure type is wrapped in DECL.
1914 It returns the generated type. */
1917 gen_struct_type (tree decl
, tree new_str_type
)
1919 tree type_orig
= get_type_of_var (decl
);
1920 tree new_type
= new_str_type
;
1921 VEC (type_wrapper_t
, heap
) *wrapper
= VEC_alloc (type_wrapper_t
, heap
, 10);
1923 type_wrapper_t
*wr_p
;
1925 while (POINTER_TYPE_P (type_orig
)
1926 || TREE_CODE (type_orig
) == ARRAY_TYPE
)
1928 if (POINTER_TYPE_P (type_orig
))
1931 wr
.domain
= NULL_TREE
;
1935 gcc_assert (TREE_CODE (type_orig
) == ARRAY_TYPE
);
1937 wr
.domain
= TYPE_DOMAIN (type_orig
);
1939 VEC_safe_push (type_wrapper_t
, heap
, wrapper
, &wr
);
1940 type_orig
= TREE_TYPE (type_orig
);
1943 while (VEC_length (type_wrapper_t
, wrapper
) != 0)
1945 wr_p
= VEC_last (type_wrapper_t
, wrapper
);
1947 if (wr_p
->wrap
) /* Array. */
1948 new_type
= build_array_type (new_type
, wr_p
->domain
);
1950 new_type
= build_pointer_type (new_type
);
1952 VEC_pop (type_wrapper_t
, wrapper
);
1955 VEC_free (type_wrapper_t
, heap
, wrapper
);
1959 /* This function generates and returns new variable name based on
1960 ORIG_DECL name, combined with index I.
1961 The form of the new name is <orig_name>.<I> . */
1964 gen_var_name (tree orig_decl
, unsigned HOST_WIDE_INT i
)
1966 const char *old_name
;
1970 if (!DECL_NAME (orig_decl
)
1971 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl
)))
1974 /* If the original variable has a name, create an
1975 appropriate new name for the new variable. */
1977 old_name
= IDENTIFIER_POINTER (DECL_NAME (orig_decl
));
1978 prefix
= XALLOCAVEC (char, strlen (old_name
) + 1);
1979 strcpy (prefix
, old_name
);
1980 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, i
);
1981 return get_identifier (new_name
);
1984 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1987 add_to_new_vars_htab (new_var new_node
, htab_t new_vars_htab
)
1991 slot
= htab_find_slot_with_hash (new_vars_htab
, new_node
->orig_var
,
1992 DECL_UID (new_node
->orig_var
),
1997 /* This function creates and returns new_var_data node
1998 with empty new_vars and orig_var equal to VAR. */
2001 create_new_var_node (tree var
, d_str str
)
2005 node
= XNEW (struct new_var_data
);
2006 node
->orig_var
= var
;
2007 node
->new_vars
= VEC_alloc (tree
, heap
, VEC_length (tree
, str
->new_types
));
2011 /* Check whether the type of VAR is potential candidate for peeling.
2012 Returns true if yes, false otherwise. If yes, TYPE_P will contain
2013 candidate type. If VAR is initialized, the type of VAR will be added
2014 to UNSUITABLE_TYPES. */
2017 is_candidate (tree var
, tree
*type_p
, VEC (tree
, heap
) **unsuitable_types
)
2020 bool initialized
= false;
2027 /* There is no support of initialized vars. */
2028 if (TREE_CODE (var
) == VAR_DECL
2029 && DECL_INITIAL (var
) != NULL_TREE
)
2032 type
= get_type_of_var (var
);
2036 type
= TYPE_MAIN_VARIANT (strip_type (type
));
2037 if (TREE_CODE (type
) != RECORD_TYPE
)
2041 if (initialized
&& unsuitable_types
&& *unsuitable_types
)
2045 fprintf (dump_file
, "The type ");
2046 print_generic_expr (dump_file
, type
, 0);
2047 fprintf (dump_file
, " is initialized...Excluded.");
2049 add_unsuitable_type (unsuitable_types
, type
);
2059 /* Hash value for field_access_site. */
2062 field_acc_hash (const void *x
)
2064 return htab_hash_pointer (((const struct field_access_site
*)x
)->stmt
);
2067 /* This function returns nonzero if stmt of field_access_site X
2071 field_acc_eq (const void *x
, const void *y
)
2073 return ((const struct field_access_site
*)x
)->stmt
== (const_gimple
)y
;
2076 /* This function prints an access site, defined by SLOT. */
2079 dump_acc (void **slot
, void *data ATTRIBUTE_UNUSED
)
2081 struct access_site
*acc
= *(struct access_site
**) slot
;
2085 fprintf(dump_file
, "\n");
2087 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
2088 fprintf(dump_file
, " : ");
2090 FOR_EACH_VEC_ELT (tree
, acc
->vars
, i
, var
)
2092 print_generic_expr (dump_file
, var
, 0);
2093 fprintf(dump_file
, ", ");
2098 /* This function frees memory allocated for structure clusters,
2099 starting from CLUSTER. */
2102 free_struct_cluster (struct field_cluster
* cluster
)
2106 if (cluster
->fields_in_cluster
)
2107 sbitmap_free (cluster
->fields_in_cluster
);
2108 if (cluster
->sibling
)
2109 free_struct_cluster (cluster
->sibling
);
2114 /* Free all allocated memory under the structure node pointed by D_NODE. */
2117 free_data_struct (d_str d_node
)
2126 fprintf (dump_file
, "\nRemoving data structure \"");
2127 print_generic_expr (dump_file
, d_node
->decl
, 0);
2128 fprintf (dump_file
, "\" from data_struct_list.");
2131 /* Free all space under d_node. */
2134 for (i
= 0; i
< d_node
->num_fields
; i
++)
2135 free_field_accesses (d_node
->fields
[i
].acc_sites
);
2136 free (d_node
->fields
);
2140 free_accesses (d_node
->accs
);
2142 if (d_node
->struct_clustering
)
2143 free_struct_cluster (d_node
->struct_clustering
);
2145 if (d_node
->new_types
)
2146 VEC_free (tree
, heap
, d_node
->new_types
);
2149 /* This function creates new general and field accesses in BB. */
2152 create_new_accesses_in_bb (basic_block bb
)
2157 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
2158 create_new_accs_for_struct (str
, bb
);
2161 /* This function adds allocation sites for peeled structures.
2162 M_DATA is vector of allocation sites of function CONTEXT. */
2165 create_new_alloc_sites (fallocs_t m_data
, tree context
)
2170 FOR_EACH_VEC_ELT (alloc_site_t
, m_data
->allocs
, j
, call
)
2172 gimple stmt
= call
->stmt
;
2173 d_str str
= call
->str
;
2175 gimple_seq new_stmts
= NULL
;
2176 gimple last_stmt
= get_final_alloc_stmt (stmt
);
2180 num
= gen_num_of_structs_in_malloc (stmt
, str
->decl
, &new_stmts
);
2183 gimple last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2184 insert_seq_after_stmt (last_stmt
, new_stmts
);
2185 last_stmt
= last_stmt_tmp
;
2188 /* Generate an allocation sites for each new structure type. */
2189 FOR_EACH_VEC_ELT (tree
, str
->new_types
, i
, type
)
2191 gimple new_malloc_stmt
= NULL
;
2192 gimple last_stmt_tmp
= NULL
;
2195 new_malloc_stmt
= create_new_malloc (stmt
, type
, &new_stmts
, num
);
2196 last_stmt_tmp
= gimple_seq_last_stmt (new_stmts
);
2197 insert_seq_after_stmt (last_stmt
, new_stmts
);
2198 update_cgraph_with_malloc_call (new_malloc_stmt
, context
);
2199 last_stmt
= last_stmt_tmp
;
2204 /* This function prints new variables from hashtable
2205 NEW_VARS_HTAB to dump_file. */
2208 dump_new_vars (htab_t new_vars_htab
)
2214 htab_traverse (new_vars_htab
, dump_new_var
, NULL
);
2217 /* Given an original variable ORIG_DECL of structure type STR,
2218 this function generates new variables of the types defined
2219 by STR->new_type. Generated types are saved in new_var node NODE.
2220 ORIG_DECL should has VAR_DECL tree_code. */
2223 create_new_var_1 (tree orig_decl
, d_str str
, new_var node
)
2229 VEC_iterate (tree
, str
->new_types
, i
, type
); i
++)
2231 tree new_decl
= NULL
;
2234 new_name
= gen_var_name (orig_decl
, i
);
2235 type
= gen_struct_type (orig_decl
, type
);
2237 if (is_global_var (orig_decl
))
2238 new_decl
= build_decl (DECL_SOURCE_LOCATION (orig_decl
),
2239 VAR_DECL
, new_name
, type
);
2242 const char *name
= new_name
? IDENTIFIER_POINTER (new_name
) : NULL
;
2243 new_decl
= create_tmp_var (type
, name
);
2246 copy_decl_attributes (new_decl
, orig_decl
);
2247 VEC_safe_push (tree
, heap
, node
->new_vars
, new_decl
);
2251 /* This function creates new variables to
2252 substitute the original variable VAR_DECL and adds
2253 them to the new_var's hashtable NEW_VARS_HTAB. */
2256 create_new_var (tree var_decl
, htab_t new_vars_htab
)
2263 if (!var_decl
|| is_in_new_vars_htab (var_decl
, new_vars_htab
))
2266 if (!is_candidate (var_decl
, &type
, NULL
))
2269 i
= find_structure (type
);
2270 if (i
== VEC_length (structure
, structures
))
2273 str
= VEC_index (structure
, structures
, i
);
2274 node
= create_new_var_node (var_decl
, str
);
2275 create_new_var_1 (var_decl
, str
, node
);
2276 add_to_new_vars_htab (node
, new_vars_htab
);
2279 /* Hash value for new_var. */
2282 new_var_hash (const void *x
)
2284 return DECL_UID (((const_new_var
)x
)->orig_var
);
2287 /* This function returns nonzero if orig_var of new_var X
2288 and tree Y have equal UIDs. */
2291 new_var_eq (const void *x
, const void *y
)
2293 if (DECL_P ((const_tree
)y
))
2294 return DECL_UID (((const_new_var
)x
)->orig_var
) == DECL_UID ((const_tree
)y
);
2299 /* This function check whether a structure type represented by STR
2300 escapes due to ipa-type-escape analysis. If yes, this type is added
2301 to UNSUITABLE_TYPES vector. */
2304 check_type_escape (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2306 tree type
= str
->decl
;
2308 if (!ipa_type_escape_type_contained_p (type
))
2312 fprintf (dump_file
, "\nEscaping type is ");
2313 print_generic_expr (dump_file
, type
, 0);
2315 add_unsuitable_type (unsuitable_types
, type
);
2319 /* Hash value for access_site. */
2322 acc_hash (const void *x
)
2324 return htab_hash_pointer (((const struct access_site
*)x
)->stmt
);
2327 /* Return nonzero if stmt of access_site X is equal to Y. */
2330 acc_eq (const void *x
, const void *y
)
2332 return ((const struct access_site
*)x
)->stmt
== (const_gimple
)y
;
2335 /* Given a structure declaration STRUCT_DECL, and number of fields
2336 in the structure NUM_FIELDS, this function creates and returns
2337 corresponding field_entry's. */
2339 static struct field_entry
*
2340 get_fields (tree struct_decl
, int num_fields
)
2342 struct field_entry
*list
;
2343 tree t
= TYPE_FIELDS (struct_decl
);
2346 list
= XNEWVEC (struct field_entry
, num_fields
);
2348 for (idx
= 0 ; t
; t
= TREE_CHAIN (t
), idx
++)
2349 if (TREE_CODE (t
) == FIELD_DECL
)
2351 list
[idx
].index
= idx
;
2353 list
[idx
].acc_sites
=
2354 htab_create (32, field_acc_hash
, field_acc_eq
, NULL
);
2355 list
[idx
].count
= 0;
2356 list
[idx
].field_mapping
= NULL_TREE
;
2362 /* Print non-field accesses from hashtable ACCS of structure. */
2365 dump_access_sites (htab_t accs
)
2371 htab_traverse (accs
, dump_acc
, NULL
);
2374 /* This function is a callback for alloc_sites hashtable
2375 traversal. SLOT is a pointer to fallocs_t. This function
2376 removes all allocations of the structure defined by DATA. */
2379 remove_str_allocs_in_func (void **slot
, void *data
)
2381 fallocs_t fallocs
= *(fallocs_t
*) slot
;
2385 while (VEC_iterate (alloc_site_t
, fallocs
->allocs
, i
, call
))
2387 if (call
->str
== (d_str
) data
)
2388 VEC_ordered_remove (alloc_site_t
, fallocs
->allocs
, i
);
2396 /* This function remove all entries corresponding to the STR structure
2397 from alloc_sites hashtable. */
2400 remove_str_allocs (d_str str
)
2406 htab_traverse (alloc_sites
, remove_str_allocs_in_func
, str
);
2409 /* This function removes the structure with index I from structures vector. */
2412 remove_structure (unsigned i
)
2416 if (i
>= VEC_length (structure
, structures
))
2419 str
= VEC_index (structure
, structures
, i
);
2421 /* Before removing the structure str, we have to remove its
2422 allocations from alloc_sites hashtable. */
2423 remove_str_allocs (str
);
2424 free_data_struct (str
);
2425 VEC_ordered_remove (structure
, structures
, i
);
2428 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2429 COND_STMT is a condition statement to check. */
2432 is_safe_cond_expr (gimple cond_stmt
)
2435 unsigned str0
, str1
;
2437 unsigned length
= VEC_length (structure
, structures
);
2439 if (gimple_cond_code (cond_stmt
) != EQ_EXPR
2440 && gimple_cond_code (cond_stmt
) != NE_EXPR
)
2443 arg0
= gimple_cond_lhs (cond_stmt
);
2444 arg1
= gimple_cond_rhs (cond_stmt
);
2446 str0
= find_structure (strip_type (get_type_of_var (arg0
)));
2447 str1
= find_structure (strip_type (get_type_of_var (arg1
)));
2449 s0
= (str0
!= length
) ? true : false;
2450 s1
= (str1
!= length
) ? true : false;
2455 /* For now we allow only comparison with 0 or NULL. */
2456 if (!integer_zerop (arg0
) && !integer_zerop (arg1
))
2462 /* This function excludes statements, that are
2463 part of allocation sites or field accesses, from the
2464 hashtable of general accesses. SLOT represents general
2465 access that will be checked. DATA is a pointer to
2466 exclude_data structure. */
2469 exclude_from_accs (void **slot
, void *data
)
2471 struct access_site
*acc
= *(struct access_site
**) slot
;
2472 tree fn_decl
= ((struct exclude_data
*)data
)->fn_decl
;
2473 d_str str
= ((struct exclude_data
*)data
)->str
;
2475 if (is_part_of_malloc (acc
->stmt
, fn_decl
)
2476 || is_part_of_field_access (acc
->stmt
, str
))
2478 VEC_free (tree
, heap
, acc
->vars
);
2480 htab_clear_slot (str
->accs
, slot
);
2485 /* Callback function for walk_tree called from collect_accesses_in_bb
2486 function. DATA is the statement which is analyzed. */
2489 get_stmt_accesses (tree
*tp
, int *walk_subtrees
, void *data
)
2491 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
2492 gimple stmt
= (gimple
) wi
->info
;
2498 switch (TREE_CODE (t
))
2502 tree var
= TREE_OPERAND(t
, 0);
2503 tree type
= TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var
)));
2504 unsigned i
= find_structure (type
);
2506 if (i
!= VEC_length (structure
, structures
))
2508 if (is_gimple_debug (stmt
))
2512 str
= VEC_index (structure
, structures
, i
);
2513 add_access_to_acc_sites (stmt
, NULL
, str
->accs
);
2519 fprintf (dump_file
, "\nThe type ");
2520 print_generic_expr (dump_file
, type
, 0);
2521 fprintf (dump_file
, " has bitfield.");
2523 remove_structure (i
);
2530 tree ref
= TREE_OPERAND (t
, 0);
2531 tree field_decl
= TREE_OPERAND (t
, 1);
2534 if ((TREE_CODE (ref
) == MEM_REF
2535 || TREE_CODE (ref
) == ARRAY_REF
2536 || TREE_CODE (ref
) == VAR_DECL
)
2537 && TREE_CODE (field_decl
) == FIELD_DECL
)
2539 tree type
= TYPE_MAIN_VARIANT (TREE_TYPE (ref
));
2540 unsigned i
= find_structure (type
);
2542 if (i
!= VEC_length (structure
, structures
))
2544 d_str str
= VEC_index (structure
, structures
, i
);
2545 struct field_entry
* field
=
2546 find_field_in_struct (str
, field_decl
);
2548 if (is_gimple_debug (stmt
))
2550 add_access_to_acc_sites (stmt
, NULL
, str
->accs
);
2557 struct field_access_site
*acc
= make_field_acc_node ();
2564 acc
->field_decl
= field_decl
;
2566 /* Check whether the access is of the form
2567 we can deal with. */
2568 if (!decompose_access (str
->decl
, acc
))
2572 fprintf (dump_file
, "\nThe type ");
2573 print_generic_expr (dump_file
, type
, 0);
2575 " has complicate access in statement ");
2576 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2579 remove_structure (i
);
2584 /* Increase count of field. */
2585 basic_block bb
= gimple_bb (stmt
);
2586 field
->count
+= bb
->count
;
2588 /* Add stmt to the acc_sites of field. */
2589 add_field_acc_to_acc_sites (acc
, field
->acc_sites
);
2600 tree cond
= COND_EXPR_COND (t
);
2602 for (i
= 0; i
< TREE_CODE_LENGTH (TREE_CODE (cond
)); i
++)
2604 tree t
= TREE_OPERAND (cond
, i
);
2607 walk_tree (&t
, get_stmt_accesses
, data
, NULL
);
2618 if (TREE_CODE (t
) == SSA_NAME
)
2619 t
= SSA_NAME_VAR (t
);
2621 i
= find_structure (strip_type (get_type_of_var (t
)));
2622 if (i
!= VEC_length (structure
, structures
))
2626 str
= VEC_index (structure
, structures
, i
);
2627 add_access_to_acc_sites (stmt
, t
, str
->accs
);
2640 /* Free structures hashtable. */
2643 free_structures (void)
2648 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
2649 free_data_struct (str
);
2651 VEC_free (structure
, heap
, structures
);
2655 /* This function is a callback for traversal over new_var's hashtable.
2656 SLOT is a pointer to new_var. This function frees memory allocated
2657 for new_var and pointed by *SLOT. */
2660 free_new_var (void **slot
, void *data ATTRIBUTE_UNUSED
)
2662 new_var n_var
= *(new_var
*) slot
;
2664 /* Free vector of new_vars. */
2665 VEC_free (tree
, heap
, n_var
->new_vars
);
2670 /* Free new_vars hashtable NEW_VARS_HTAB. */
2673 free_new_vars_htab (htab_t new_vars_htab
)
2676 htab_traverse (new_vars_htab
, free_new_var
, NULL
);
2677 htab_delete (new_vars_htab
);
2678 new_vars_htab
= NULL
;
2681 /* This function creates new general and field accesses that appear in cfun. */
2684 create_new_accesses_for_func (void)
2688 FOR_EACH_BB_FN (bb
, cfun
)
2689 create_new_accesses_in_bb (bb
);
2692 /* Create new allocation sites for the function represented by NODE. */
2695 create_new_alloc_sites_for_func (struct cgraph_node
*node
)
2697 fallocs_t fallocs
= get_fallocs (node
->decl
);
2700 create_new_alloc_sites (fallocs
, node
->decl
);
2703 /* For each local variable of structure type from the vector of structures
2704 this function generates new variable(s) to replace it. */
2707 create_new_local_vars (void)
2710 referenced_var_iterator rvi
;
2712 new_local_vars
= htab_create (num_referenced_vars
,
2713 new_var_hash
, new_var_eq
, NULL
);
2715 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2717 if (!is_global_var (var
))
2718 create_new_var (var
, new_local_vars
);
2722 htab_traverse (new_local_vars
, finalize_new_vars_creation
, NULL
);
2723 dump_new_vars (new_local_vars
);
2726 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2729 print_shift (unsigned HOST_WIDE_INT shift
)
2731 unsigned HOST_WIDE_INT sh
= shift
;
2734 fprintf (dump_file
, " ");
2737 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2740 update_fields_mapping (struct field_cluster
*cluster
, tree new_type
,
2741 struct field_entry
* fields
, int num_fields
)
2745 for (i
= 0; i
< num_fields
; i
++)
2746 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2747 fields
[i
].field_mapping
= new_type
;
2750 /* This functions builds structure with FIELDS,
2751 NAME and attributes similar to ORIG_STRUCT.
2752 It returns the newly created structure. */
2755 build_basic_struct (tree fields
, tree name
, tree orig_struct
)
2757 tree attributes
= NULL_TREE
;
2761 if (TYPE_ATTRIBUTES (orig_struct
))
2762 attributes
= unshare_expr (TYPE_ATTRIBUTES (orig_struct
));
2763 ref
= make_node (RECORD_TYPE
);
2764 TYPE_SIZE (ref
) = 0;
2765 decl_attributes (&ref
, attributes
, (int) ATTR_FLAG_TYPE_IN_PLACE
);
2766 TYPE_PACKED (ref
) = TYPE_PACKED (orig_struct
);
2767 for (x
= fields
; x
; x
= TREE_CHAIN (x
))
2769 DECL_CONTEXT (x
) = ref
;
2770 DECL_PACKED (x
) |= TYPE_PACKED (ref
);
2772 TYPE_FIELDS (ref
) = fields
;
2774 TYPE_NAME (ref
) = name
;
2779 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2780 of preparation for new structure building. NUM_FIELDS is a total
2781 number of fields in the structure. The function returns newly
2782 generated fields. */
2785 create_fields (struct field_cluster
* cluster
,
2786 struct field_entry
* fields
, int num_fields
)
2789 tree new_types
= NULL_TREE
;
2790 tree last
= NULL_TREE
;
2792 for (i
= 0; i
< num_fields
; i
++)
2793 if (TEST_BIT (cluster
->fields_in_cluster
, i
))
2795 tree new_decl
= unshare_expr (fields
[i
].decl
);
2798 new_types
= new_decl
;
2800 TREE_CHAIN (last
) = new_decl
;
2804 TREE_CHAIN (last
) = NULL_TREE
;
2809 /* This function creates a cluster name. The name is based on
2810 the original structure name, if it is present. It has a form:
2812 <original_struct_name>_sub.<CLUST_NUM>
2814 The original structure name is taken from the type of DECL.
2815 If an original structure name is not present, it's generated to be:
2819 The function returns identifier of the new cluster name. */
2822 gen_cluster_name (tree decl
, int clust_num
, int str_num
)
2824 const char * orig_name
= get_type_name (decl
);
2825 char * tmp_name
= NULL
;
2831 ASM_FORMAT_PRIVATE_NAME(tmp_name
, "struct", str_num
);
2833 len
= strlen (tmp_name
? tmp_name
: orig_name
) + strlen ("_sub");
2834 prefix
= XALLOCAVEC (char, len
+ 1);
2835 memcpy (prefix
, tmp_name
? tmp_name
: orig_name
,
2836 strlen (tmp_name
? tmp_name
: orig_name
));
2837 strcpy (prefix
+ strlen (tmp_name
? tmp_name
: orig_name
), "_sub");
2839 ASM_FORMAT_PRIVATE_NAME (new_name
, prefix
, clust_num
);
2840 return get_identifier (new_name
);
2843 /* This function checks whether the structure STR has bitfields.
2844 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2847 check_bitfields (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2849 tree type
= str
->decl
;
2852 for (i
= 0; i
< str
->num_fields
; i
++)
2853 if (DECL_BIT_FIELD (str
->fields
[i
].decl
))
2855 add_unsuitable_type (unsuitable_types
, type
);
2858 fprintf (dump_file
, "\nType ");
2859 print_generic_expr (dump_file
, type
, 0);
2860 fprintf (dump_file
, "\nescapes due to bitfield ");
2861 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
2867 /* This function adds to UNSUITABLE_TYPES those types that escape
2868 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2871 exclude_escaping_types_1 (VEC (tree
, heap
) **unsuitable_types
)
2876 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
2877 check_type_escape (str
, unsuitable_types
);
2880 /* If a structure type is a return type of any function,
2881 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2884 exclude_returned_types (VEC (tree
, heap
) **unsuitable_types
)
2886 struct cgraph_node
*c_node
;
2888 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2890 tree ret_t
= TREE_TYPE (TREE_TYPE (c_node
->decl
));
2894 ret_t
= strip_type (ret_t
);
2895 if (TREE_CODE (ret_t
) == RECORD_TYPE
)
2897 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (ret_t
));
2900 fprintf (dump_file
, "\nThe type \"");
2901 print_generic_expr (dump_file
, ret_t
, 0);
2903 "\" is return type of function...Excluded.");
2910 /* This function looks for parameters of local functions
2911 which are of structure types, or derived from them (arrays
2912 of structures, pointers to structures, or their combinations).
2913 We are not handling peeling of such structures right now.
2914 The found structures types are added to UNSUITABLE_TYPES vector. */
2917 exclude_types_passed_to_local_func (VEC (tree
, heap
) **unsuitable_types
)
2919 struct cgraph_node
*c_node
;
2921 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
2922 if (cgraph_function_body_availability (c_node
) == AVAIL_LOCAL
)
2924 tree fn
= c_node
->decl
;
2927 for (arg
= DECL_ARGUMENTS (fn
); arg
; arg
= DECL_CHAIN (arg
))
2929 tree type
= TREE_TYPE (arg
);
2931 type
= strip_type (type
);
2932 if (TREE_CODE (type
) == RECORD_TYPE
)
2934 add_unsuitable_type (unsuitable_types
,
2935 TYPE_MAIN_VARIANT (type
));
2938 fprintf (dump_file
, "\nPointer to type \"");
2939 print_generic_expr (dump_file
, type
, 0);
2941 "\" is passed to local function...Excluded.");
2948 /* This function analyzes structure form of structures
2949 potential for transformation. If we are not capable to transform
2950 structure of some form, we remove it from the structures hashtable.
2951 Right now we cannot handle nested structs, when nesting is
2952 through any level of pointers or arrays.
2954 TBD: release these constrains in future.
2956 Note, that in this function we suppose that all structures
2957 in the program are members of the structures hashtable right now,
2958 without excluding escaping types. */
2961 check_struct_form (d_str str
, VEC (tree
, heap
) **unsuitable_types
)
2965 for (i
= 0; i
< str
->num_fields
; i
++)
2967 tree f_type
= strip_type(TREE_TYPE (str
->fields
[i
].decl
));
2969 if (TREE_CODE (f_type
) == RECORD_TYPE
)
2971 add_unsuitable_type (unsuitable_types
, TYPE_MAIN_VARIANT (f_type
));
2972 add_unsuitable_type (unsuitable_types
, str
->decl
);
2975 fprintf (dump_file
, "\nType ");
2976 print_generic_expr (dump_file
, f_type
, 0);
2977 fprintf (dump_file
, " is a field in the structure ");
2978 print_generic_expr (dump_file
, str
->decl
, 0);
2979 fprintf (dump_file
, ". Escaping...");
2985 /* This function adds a structure TYPE to the vector of structures,
2986 if it's not already there. */
2989 add_structure (tree type
)
2991 struct data_structure node
;
2995 type
= TYPE_MAIN_VARIANT (type
);
2997 i
= find_structure (type
);
2999 if (i
!= VEC_length (structure
, structures
))
3002 num_fields
= fields_length (type
);
3004 node
.num_fields
= num_fields
;
3005 node
.fields
= get_fields (type
, num_fields
);
3006 node
.struct_clustering
= NULL
;
3007 node
.accs
= htab_create (32, acc_hash
, acc_eq
, NULL
);
3008 node
.new_types
= VEC_alloc (tree
, heap
, num_fields
);
3011 VEC_safe_push (structure
, heap
, structures
, &node
);
3015 fprintf (dump_file
, "\nAdding data structure \"");
3016 print_generic_expr (dump_file
, type
, 0);
3017 fprintf (dump_file
, "\" to data_struct_list.");
3021 /* This function adds an allocation site to alloc_sites hashtable.
3022 The allocation site appears in STMT of function FN_DECL and
3023 allocates the structure represented by STR. */
3026 add_alloc_site (tree fn_decl
, gimple stmt
, d_str str
)
3028 fallocs_t fallocs
= NULL
;
3029 alloc_site_t m_call
;
3035 (fallocs_t
) htab_find_with_hash (alloc_sites
,
3036 fn_decl
, htab_hash_pointer (fn_decl
));
3042 fallocs
= XNEW (struct func_alloc_sites
);
3043 fallocs
->func
= fn_decl
;
3044 fallocs
->allocs
= VEC_alloc (alloc_site_t
, heap
, 1);
3045 slot
= htab_find_slot_with_hash (alloc_sites
, fn_decl
,
3046 htab_hash_pointer (fn_decl
), INSERT
);
3049 VEC_safe_push (alloc_site_t
, heap
,
3050 fallocs
->allocs
, &m_call
);
3054 fprintf (dump_file
, "\nAdding stmt ");
3055 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3056 fprintf (dump_file
, " to list of mallocs.");
3060 /* This function returns true if the result of STMT, that contains a call
3061 to an allocation function, is cast to one of the structure types.
3062 STMT should be of the form: T.2 = <alloc_func> (T.1);
3063 If true, I_P contains an index of an allocated structure.
3064 Otherwise I_P contains the length of the vector of structures. */
3067 is_alloc_of_struct (gimple stmt
, unsigned *i_p
)
3073 final_stmt
= get_final_alloc_stmt (stmt
);
3078 /* final_stmt should be of the form:
3079 T.3 = (struct_type *) T.2; */
3081 if (gimple_code (final_stmt
) != GIMPLE_ASSIGN
)
3084 lhs
= gimple_assign_lhs (final_stmt
);
3086 type
= get_type_of_var (lhs
);
3091 if (!POINTER_TYPE_P (type
)
3092 || TREE_CODE (strip_type (type
)) != RECORD_TYPE
)
3095 *i_p
= find_structure (strip_type (type
));
3097 if (*i_p
== VEC_length (structure
, structures
))
3103 /* This function prints non-field and field accesses
3104 of the structure STR. */
3107 dump_accs (d_str str
)
3111 fprintf (dump_file
, "\nAccess sites of struct ");
3112 print_generic_expr (dump_file
, str
->decl
, 0);
3114 for (i
= 0; i
< str
->num_fields
; i
++)
3116 fprintf (dump_file
, "\nAccess site of field ");
3117 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3118 dump_field_acc_sites (str
->fields
[i
].acc_sites
);
3119 fprintf (dump_file
, ":\n");
3121 fprintf (dump_file
, "\nGeneral access sites\n");
3122 dump_access_sites (str
->accs
);
3125 /* This function checks whether an access statement, pointed by SLOT,
3126 is a condition we are capable to transform. It returns false if not,
3127 setting bool *DATA to false. */
3130 safe_cond_expr_check (void **slot
, void *data
)
3132 struct access_site
*acc
= *(struct access_site
**) slot
;
3134 if (gimple_code (acc
->stmt
) == GIMPLE_COND
3135 && !is_safe_cond_expr (acc
->stmt
))
3139 fprintf (dump_file
, "\nUnsafe conditional statement ");
3140 print_gimple_stmt (dump_file
, acc
->stmt
, 0, 0);
3142 *(bool *) data
= false;
3148 /* This function excludes statements that are part of allocation sites and
3149 field accesses from the hashtable of general accesses of the structure
3150 type STR. Only accesses that belong to the function represented by
3151 NODE are treated. */
3154 exclude_alloc_and_field_accs_1 (d_str str
, struct cgraph_node
*node
)
3156 struct exclude_data dt
;
3158 dt
.fn_decl
= node
->decl
;
3161 htab_traverse (dt
.str
->accs
, exclude_from_accs
, &dt
);
3164 /* Collect accesses to the structure types that appear in basic block BB. */
3167 collect_accesses_in_bb (basic_block bb
)
3169 gimple_stmt_iterator bsi
;
3170 struct walk_stmt_info wi
;
3172 memset (&wi
, 0, sizeof (wi
));
3174 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3176 gimple stmt
= gsi_stmt (bsi
);
3178 /* In asm stmt we cannot always track the arguments,
3179 so we just give up. */
3180 if (gimple_code (stmt
) == GIMPLE_ASM
)
3186 wi
.info
= (void *) stmt
;
3187 walk_gimple_op (stmt
, get_stmt_accesses
, &wi
);
3191 /* This function generates cluster substructure that contains FIELDS.
3192 The cluster added to the set of clusters of the structure STR. */
3195 gen_cluster (sbitmap fields
, d_str str
)
3197 struct field_cluster
*crr_cluster
= XCNEW (struct field_cluster
);
3199 crr_cluster
->sibling
= str
->struct_clustering
;
3200 str
->struct_clustering
= crr_cluster
;
3201 crr_cluster
->fields_in_cluster
= fields
;
3204 /* This function peels a field with the index I from the structure DS. */
3207 peel_field (int i
, d_str ds
)
3209 struct field_cluster
*crr_cluster
= XCNEW (struct field_cluster
);
3211 crr_cluster
->sibling
= ds
->struct_clustering
;
3212 ds
->struct_clustering
= crr_cluster
;
3213 crr_cluster
->fields_in_cluster
=
3214 sbitmap_alloc ((unsigned int) ds
->num_fields
);
3215 sbitmap_zero (crr_cluster
->fields_in_cluster
);
3216 SET_BIT (crr_cluster
->fields_in_cluster
, i
);
3219 /* This function calculates maximum field count in
3220 the structure STR. */
3223 get_max_field_count (d_str str
)
3228 for (i
= 0; i
< str
->num_fields
; i
++)
3229 if (str
->fields
[i
].count
> max
)
3230 max
= str
->fields
[i
].count
;
3235 /* Do struct-reorg transformation for individual function
3236 represented by NODE. All structure types relevant
3237 for this function are transformed. */
3240 do_reorg_for_func (struct cgraph_node
*node
)
3242 create_new_local_vars ();
3243 create_new_alloc_sites_for_func (node
);
3244 create_new_accesses_for_func ();
3245 update_ssa (TODO_update_ssa
);
3246 cleanup_tree_cfg ();
3247 cgraph_rebuild_references ();
3249 /* Free auxiliary data representing local variables. */
3250 free_new_vars_htab (new_local_vars
);
3253 /* Print structure TYPE, its name, if it exists, and body.
3254 INDENT defines the level of indentation (similar
3255 to the option -i of indent command). SHIFT parameter
3256 defines a number of spaces by which a structure will
3257 be shifted right. */
3260 dump_struct_type (tree type
, unsigned HOST_WIDE_INT indent
,
3261 unsigned HOST_WIDE_INT shift
)
3263 const char *struct_name
;
3266 if (!type
|| !dump_file
)
3269 if (TREE_CODE (type
) != RECORD_TYPE
)
3271 print_generic_expr (dump_file
, type
, 0);
3275 print_shift (shift
);
3276 struct_name
= get_type_name (type
);
3277 fprintf (dump_file
, "struct ");
3279 fprintf (dump_file
, "%s\n",struct_name
);
3280 print_shift (shift
);
3281 fprintf (dump_file
, "{\n");
3283 for (field
= TYPE_FIELDS (type
); field
;
3284 field
= TREE_CHAIN (field
))
3286 unsigned HOST_WIDE_INT s
= indent
;
3287 tree f_type
= TREE_TYPE (field
);
3289 print_shift (shift
);
3291 fprintf (dump_file
, " ");
3292 dump_struct_type (f_type
, indent
, shift
+ indent
);
3293 fprintf(dump_file
, " ");
3294 print_generic_expr (dump_file
, field
, 0);
3295 fprintf(dump_file
, ";\n");
3297 print_shift (shift
);
3298 fprintf (dump_file
, "}\n");
3301 /* This function creates new structure types to replace original type,
3302 indicated by STR->decl. The names of the new structure types are
3303 derived from the original structure type. If the original structure
3304 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3307 create_new_type (d_str str
, int *str_num
)
3309 int cluster_num
= 0;
3311 struct field_cluster
*cluster
= str
->struct_clustering
;
3314 tree name
= gen_cluster_name (str
->decl
, cluster_num
,
3320 fields
= create_fields (cluster
, str
->fields
,
3322 new_type
= build_basic_struct (fields
, name
, str
->decl
);
3324 update_fields_mapping (cluster
, new_type
,
3325 str
->fields
, str
->num_fields
);
3327 VEC_safe_push (tree
, heap
, str
->new_types
, new_type
);
3328 cluster
= cluster
->sibling
;
3333 /* This function is a callback for alloc_sites hashtable
3334 traversal. SLOT is a pointer to fallocs_t.
3335 This function frees memory pointed by *SLOT. */
3338 free_falloc_sites (void **slot
, void *data ATTRIBUTE_UNUSED
)
3340 fallocs_t fallocs
= *(fallocs_t
*) slot
;
3342 VEC_free (alloc_site_t
, heap
, fallocs
->allocs
);
3347 /* Remove structures collected in UNSUITABLE_TYPES
3348 from structures vector. */
3351 remove_unsuitable_types (VEC (tree
, heap
) *unsuitable_types
)
3357 FOR_EACH_VEC_ELT (tree
, unsuitable_types
, j
, type
)
3358 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3359 if (is_equal_types (str
->decl
, type
))
3361 remove_structure (i
);
3366 /* Exclude structure types with bitfields.
3367 We would not want to interfere with other optimizations
3368 that can be done in this case. The structure types with
3369 bitfields are added to UNSUITABLE_TYPES vector. */
3372 exclude_types_with_bit_fields (VEC (tree
, heap
) **unsuitable_types
)
3377 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3378 check_bitfields (str
, unsuitable_types
);
3381 /* This function checks three types of escape. A structure type escapes:
3383 1. if it's a type of parameter of a local function.
3384 2. if it's a type of function return value.
3385 3. if it escapes as a result of ipa-type-escape analysis.
3387 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3390 exclude_escaping_types (VEC (tree
, heap
) **unsuitable_types
)
3392 exclude_types_passed_to_local_func (unsuitable_types
);
3393 exclude_returned_types (unsuitable_types
);
3394 exclude_escaping_types_1 (unsuitable_types
);
3397 /* This function analyzes whether the form of
3398 structure is such that we are capable to transform it.
3399 Nested structures are checked here. Unsuitable structure
3400 types are added to UNSUITABLE_TYPE vector. */
3403 analyze_struct_form (VEC (tree
, heap
) **unsuitable_types
)
3408 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3409 check_struct_form (str
, unsuitable_types
);
3412 /* This function looks for structure types instantiated in the program.
3413 The candidate types are added to the structures vector.
3414 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3417 build_data_structure (VEC (tree
, heap
) **unsuitable_types
)
3420 struct varpool_node
*current_varpool
;
3421 struct cgraph_node
*c_node
;
3423 /* Check global variables. */
3424 FOR_EACH_STATIC_VARIABLE (current_varpool
)
3426 var
= current_varpool
->decl
;
3427 if (is_candidate (var
, &type
, unsuitable_types
))
3428 add_structure (type
);
3431 /* Now add structures that are types of function parameters and
3433 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3435 enum availability avail
=
3436 cgraph_function_body_availability (c_node
);
3438 /* We need AVAIL_AVAILABLE for main function. */
3439 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3441 struct function
*fn
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3444 for (var
= DECL_ARGUMENTS (c_node
->decl
); var
;
3445 var
= TREE_CHAIN (var
))
3446 if (is_candidate (var
, &type
, unsuitable_types
))
3447 add_structure (type
);
3451 /* Skip cones that haven't been materialized yet. */
3452 gcc_assert (c_node
->clone_of
3453 && c_node
->clone_of
->decl
!= c_node
->decl
);
3457 /* Check function local variables. */
3458 FOR_EACH_LOCAL_DECL (fn
, ix
, var
)
3459 if (is_candidate (var
, &type
, unsuitable_types
))
3460 add_structure (type
);
3465 /* This function returns true if the program contains
3466 a call to user defined allocation function, or other
3467 functions that can interfere with struct-reorg optimizations. */
3470 program_redefines_malloc_p (void)
3472 struct cgraph_node
*c_node
;
3473 struct cgraph_node
*c_node2
;
3474 struct cgraph_edge
*c_edge
;
3477 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3479 for (c_edge
= c_node
->callees
; c_edge
; c_edge
= c_edge
->next_callee
)
3481 c_node2
= c_edge
->callee
;
3482 fndecl2
= c_node2
->decl
;
3483 if (is_gimple_call (c_edge
->call_stmt
))
3485 const char * fname
= get_name (fndecl2
);
3487 if ((gimple_call_flags (c_edge
->call_stmt
) & ECF_MALLOC
)
3488 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_MALLOC
)
3489 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_CALLOC
)
3490 && (DECL_FUNCTION_CODE (fndecl2
) != BUILT_IN_ALLOCA
))
3493 /* Check that there is no __builtin_object_size,
3494 __builtin_offsetof, or realloc's in the program. */
3495 if (DECL_FUNCTION_CODE (fndecl2
) == BUILT_IN_OBJECT_SIZE
3496 || !strcmp (fname
, "__builtin_offsetof")
3497 || !strcmp (fname
, "realloc"))
3506 /* In this function we assume that an allocation statement
3508 var = (type_cast) malloc (size);
3510 is converted into the following set of statements:
3514 T.3 = (type_cast) T.2;
3517 In this function we collect into alloc_sites the allocation
3518 sites of variables of structure types that are present
3519 in structures vector. */
3522 collect_alloc_sites (void)
3524 struct cgraph_node
*node
;
3525 struct cgraph_edge
*cs
;
3527 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3528 if (node
->analyzed
&& node
->decl
)
3530 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
3532 gimple stmt
= cs
->call_stmt
;
3538 if (is_gimple_call (stmt
)
3539 && (decl
= gimple_call_fndecl (stmt
))
3540 && gimple_call_lhs (stmt
))
3544 if (is_alloc_of_struct (stmt
, &i
))
3546 /* We support only malloc now. */
3547 if (DECL_FUNCTION_CODE (decl
) == BUILT_IN_MALLOC
)
3551 str
= VEC_index (structure
, structures
, i
);
3552 add_alloc_site (node
->decl
, stmt
, str
);
3559 "\nUnsupported allocation function ");
3560 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3562 remove_structure (i
);
3571 /* Print collected accesses. */
3574 dump_accesses (void)
3582 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3586 /* This function checks whether the accesses of structures in condition
3587 expressions are of the kind we are capable to transform.
3588 If not, such structures are removed from the vector of structures. */
3591 check_cond_exprs (void)
3597 while (VEC_iterate (structure
, structures
, i
, str
))
3602 htab_traverse (str
->accs
, safe_cond_expr_check
, &safe_p
);
3604 remove_structure (i
);
3610 /* We exclude from non-field accesses of the structure
3611 all statements that will be treated as part of the structure
3612 allocation sites or field accesses. */
3615 exclude_alloc_and_field_accs (struct cgraph_node
*node
)
3620 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3621 exclude_alloc_and_field_accs_1 (str
, node
);
3624 /* This function collects accesses of the fields of the structures
3625 that appear at function FN. */
3628 collect_accesses_in_func (struct function
*fn
)
3635 /* Collect accesses for each basic blocks separately. */
3636 FOR_EACH_BB_FN (bb
, fn
)
3637 collect_accesses_in_bb (bb
);
3640 /* This function summarizes counts of the fields into the structure count. */
3643 sum_counts (d_str str
, gcov_type
*hottest
)
3648 for (i
= 0; i
< str
->num_fields
; i
++)
3652 fprintf (dump_file
, "\nCounter of field \"");
3653 print_generic_expr (dump_file
, str
->fields
[i
].decl
, 0);
3654 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
,
3655 str
->fields
[i
].count
);
3657 str
->count
+= str
->fields
[i
].count
;
3662 fprintf (dump_file
, "\nCounter of struct \"");
3663 print_generic_expr (dump_file
, str
->decl
, 0);
3664 fprintf (dump_file
, "\" is " HOST_WIDEST_INT_PRINT_DEC
, str
->count
);
3667 if (str
->count
> *hottest
)
3668 *hottest
= str
->count
;
3671 /* This function peels the field into separate structure if it's
3672 sufficiently hot, i.e. if its count provides at least 90% of
3673 the maximum field count in the structure. */
3676 peel_hot_fields (d_str str
)
3678 gcov_type max_field_count
;
3679 sbitmap fields_left
= sbitmap_alloc (str
->num_fields
);
3682 sbitmap_ones (fields_left
);
3684 (gcov_type
) (get_max_field_count (str
)/100)*90;
3686 str
->struct_clustering
= NULL
;
3688 for (i
= 0; i
< str
->num_fields
; i
++)
3690 if (str
->count
>= max_field_count
)
3692 RESET_BIT (fields_left
, i
);
3693 peel_field (i
, str
);
3697 i
= sbitmap_first_set_bit (fields_left
);
3699 gen_cluster (fields_left
, str
);
3701 sbitmap_free (fields_left
);
3704 /* This function is a helper for do_reorg. It goes over
3705 functions in call graph and performs actual transformation
3711 struct cgraph_node
*node
;
3713 /* Initialize the default bitmap obstack. */
3714 bitmap_obstack_initialize (NULL
);
3716 for (node
= cgraph_nodes
; node
; node
= node
->next
)
3717 if (node
->analyzed
&& node
->decl
)
3719 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3720 current_function_decl
= node
->decl
;
3722 fprintf (dump_file
, "\nFunction to do reorg is %s: \n",
3723 (const char *) IDENTIFIER_POINTER (DECL_NAME (node
->decl
)));
3724 do_reorg_for_func (node
);
3725 free_dominance_info (CDI_DOMINATORS
);
3726 free_dominance_info (CDI_POST_DOMINATORS
);
3727 current_function_decl
= NULL
;
3732 bitmap_obstack_release (NULL
);
3735 /* This function creates new global struct variables.
3736 For each original variable, the set of new variables
3737 is created with the new structure types corresponding
3738 to the structure type of original variable.
3739 Only VAR_DECL variables are treated by this function. */
3742 create_new_global_vars (void)
3744 struct varpool_node
*current_varpool
;
3745 unsigned HOST_WIDE_INT i
;
3746 unsigned HOST_WIDE_INT varpool_size
= 0;
3748 for (i
= 0; i
< 2; i
++)
3751 new_global_vars
= htab_create (varpool_size
,
3752 new_var_hash
, new_var_eq
, NULL
);
3753 FOR_EACH_STATIC_VARIABLE(current_varpool
)
3755 tree var_decl
= current_varpool
->decl
;
3757 if (!var_decl
|| TREE_CODE (var_decl
) != VAR_DECL
)
3762 create_new_var (var_decl
, new_global_vars
);
3766 if (new_global_vars
)
3767 htab_traverse (new_global_vars
, update_varpool_with_new_var
, NULL
);
3770 /* Dump all new types generated by this optimization. */
3773 dump_new_types (void)
3782 fprintf (dump_file
, "\nThe following are the new types generated by"
3783 " this optimization:\n");
3785 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3789 fprintf (dump_file
, "\nFor type ");
3790 dump_struct_type (str
->decl
, 2, 0);
3791 fprintf (dump_file
, "\nthe number of new types is %d\n",
3792 VEC_length (tree
, str
->new_types
));
3794 FOR_EACH_VEC_ELT (tree
, str
->new_types
, j
, type
)
3795 dump_struct_type (type
, 2, 0);
3799 /* This function creates new types to replace old structure types. */
3802 create_new_types (void)
3808 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3809 create_new_type (str
, &str_num
);
3812 /* Free allocation sites hashtable. */
3815 free_alloc_sites (void)
3818 htab_traverse (alloc_sites
, free_falloc_sites
, NULL
);
3819 htab_delete (alloc_sites
);
3823 /* This function collects structures potential
3824 for peeling transformation, and inserts
3825 them into structures hashtable. */
3828 collect_structures (void)
3830 VEC (tree
, heap
) *unsuitable_types
= VEC_alloc (tree
, heap
, 32);
3832 structures
= VEC_alloc (structure
, heap
, 32);
3834 /* If program contains user defined mallocs, we give up. */
3835 if (program_redefines_malloc_p ())
3838 /* Build data structures hashtable of all data structures
3840 build_data_structure (&unsuitable_types
);
3842 /* This function analyzes whether the form of
3843 structure is such that we are capable to transform it.
3844 Nested structures are checked here. */
3845 analyze_struct_form (&unsuitable_types
);
3847 /* This function excludes those structure types
3848 that escape compilation unit. */
3849 exclude_escaping_types (&unsuitable_types
);
3851 /* We do not want to change data layout of the structures with bitfields. */
3852 exclude_types_with_bit_fields (&unsuitable_types
);
3854 remove_unsuitable_types (unsuitable_types
);
3855 VEC_free (tree
, heap
, unsuitable_types
);
3858 /* Collect structure allocation sites. In case of arrays
3859 we have nothing to do. */
3862 collect_allocation_sites (void)
3864 alloc_sites
= htab_create (32, malloc_hash
, malloc_eq
, NULL
);
3865 collect_alloc_sites ();
3868 /* This function collects data accesses for the
3869 structures to be transformed. For each structure
3870 field it updates the count field in field_entry. */
3873 collect_data_accesses (void)
3875 struct cgraph_node
*c_node
;
3877 for (c_node
= cgraph_nodes
; c_node
; c_node
= c_node
->next
)
3879 enum availability avail
= cgraph_function_body_availability (c_node
);
3881 if (avail
== AVAIL_LOCAL
|| avail
== AVAIL_AVAILABLE
)
3883 struct function
*func
= DECL_STRUCT_FUNCTION (c_node
->decl
);
3885 collect_accesses_in_func (func
);
3886 exclude_alloc_and_field_accs (c_node
);
3890 check_cond_exprs ();
3891 /* Print collected accesses. */
3895 /* We do not bother to transform cold structures.
3896 Coldness of the structure is defined relatively
3897 to the highest structure count among the structures
3898 to be transformed. It's triggered by the compiler parameter
3900 --param struct-reorg-cold-struct-ratio=<value>
3902 where <value> ranges from 0 to 100. Structures with count ratios
3903 that are less than this parameter are considered to be cold. */
3906 exclude_cold_structs (void)
3908 gcov_type hottest
= 0;
3912 /* We summarize counts of fields of a structure into the structure count. */
3913 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3914 sum_counts (str
, &hottest
);
3916 /* Remove cold structures from structures vector. */
3918 while (VEC_iterate (structure
, structures
, i
, str
))
3919 if (str
->count
* 100 < (hottest
* STRUCT_REORG_COLD_STRUCT_RATIO
))
3923 fprintf (dump_file
, "\nThe structure ");
3924 print_generic_expr (dump_file
, str
->decl
, 0);
3925 fprintf (dump_file
, " is cold.");
3927 remove_structure (i
);
3933 /* This function decomposes original structure into substructures,
3942 FOR_EACH_VEC_ELT (structure
, structures
, i
, str
)
3943 peel_hot_fields (str
);
3947 /* Do the actual transformation for each structure
3948 from the structures hashtable. */
3953 /* Check that there is a work to do. */
3954 if (!VEC_length (structure
, structures
))
3957 fprintf (dump_file
, "\nNo structures to transform. Exiting...");
3964 fprintf (dump_file
, "\nNumber of structures to transform is %d",
3965 VEC_length (structure
, structures
));
3969 /* Generate new types. */
3970 create_new_types ();
3973 /* Create new global variables. */
3974 create_new_global_vars ();
3975 dump_new_vars (new_global_vars
);
3977 /* Decompose structures for each function separately. */
3980 /* Free auxiliary data collected for global variables. */
3981 free_new_vars_htab (new_global_vars
);
3984 /* Free all auxiliary data used by this optimization. */
3987 free_data_structs (void)
3990 free_alloc_sites ();
3993 /* Perform structure decomposition (peeling). */
3996 reorg_structs (void)
4000 /* Collect structure types. */
4001 collect_structures ();
4003 /* Collect structure allocation sites. */
4004 collect_allocation_sites ();
4006 /* Collect structure accesses. */
4007 collect_data_accesses ();
4009 /* We transform only hot structures. */
4010 exclude_cold_structs ();
4013 /* Decompose structures into substructures, i.e. clusters. */
4017 /* Do the actual transformation for each structure
4018 from the structures hashtable. */
4021 /* Free all auxiliary data used by this optimization. */
4022 free_data_structs ();
4025 /* Struct-reorg optimization entry point function. */
4028 reorg_structs_drive (void)
4030 /* IPA struct-reorg is completely broken - its analysis phase is
4031 non-conservative (which is not the only reason it is broken). */
4037 /* Struct-reorg optimization gate function. */
4040 struct_reorg_gate (void)
4042 return flag_ipa_struct_reorg
4043 && flag_whole_program
4047 struct simple_ipa_opt_pass pass_ipa_struct_reorg
=
4051 "ipa_struct_reorg", /* name */
4052 struct_reorg_gate
, /* gate */
4053 reorg_structs_drive
, /* execute */
4056 0, /* static_pass_number */
4057 TV_INTEGRATION
, /* tv_id */
4058 0, /* properties_required */
4059 0, /* properties_provided */
4060 0, /* properties_destroyed */
4061 TODO_verify_ssa
, /* todo_flags_start */
4062 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */