1 /* Struct-reorg optimization.
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Olga Golovanevsky <olga@il.ibm.com>
4 (Initial version of this code was developed
5 by Caroline Tice and Mostafa Hagog.)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
32 #include "tree-inline.h"
33 #include "tree-flow.h"
34 #include "tree-flow-inline.h"
35 #include "langhooks.h"
36 #include "pointer-set.h"
44 #include "diagnostic.h"
50 #include "basic-block.h"
51 #include "tree-iterator.h"
52 #include "tree-pass.h"
53 #include "ipa-struct-reorg.h"
55 #include "ipa-type-escape.h"
56 #include "tree-dump.h"
60 /* This optimization implements structure peeling.
62 For example, given a structure type:
70 it can be peeled into two structure types as follows:
72 typedef struct and typedef struct
78 or can be fully peeled:
95 When structure type is peeled all instances and their accesses
96 in the program are updated accordingly. For example, if there is
101 and structure type str_t was peeled into two structures str_t_0
102 and str_t_1 as it was shown above, then array A will be replaced
103 by two arrays as follows:
108 The field access of field a of element i of array A: A[i].a will be
109 replaced by an access to field a of element i of array A_0: A_0[i].a.
111 This optimization also supports dynamically allocated arrays.
112 If array of structures was allocated by malloc function:
114 str_t * p = (str_t *) malloc (sizeof (str_t) * N)
116 the allocation site will be replaced to reflect new structure types:
118 str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N)
119 str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N)
121 The field access through the pointer p[i].a will be changed by p_0[i].a.
123 The goal of structure peeling is to improve spatial locality.
124 For example, if one of the fields of a structure is accessed frequently
127 for (i = 0; i < N; i++)
132 the allocation of field a of str_t contiguously in memory will
133 increase the chances of fetching the field from cache.
135 The analysis part of this optimization is based on the frequency of
136 field accesses, which are collected all over the program.
137 Then the fields with the frequencies that satisfy the following condition
138 get peeled out of the structure:
140 freq(f) > C * max_field_freq_in_struct
142 where max_field_freq_in_struct is the maximum field frequency
143 in the structure. C is a constant defining which portion of
144 max_field_freq_in_struct the fields should have in order to be peeled.
146 If profiling information is provided, it is used to calculate the
147 frequency of field accesses. Otherwise, the structure is fully peeled.
149 IPA type-escape analysis is used to determine when it is safe
152 The optimization is activated by flag -fipa-struct-reorg. */
154 /* New variables created by this optimization.
155 When doing struct peeling, each variable of
156 the original struct type will be replaced by
157 the set of new variables corresponding to
158 the new structure types. */
159 struct new_var_data {
160 /* VAR_DECL for original struct type. */
162 /* Vector of new variables. */
163 VEC(tree, heap) *new_vars;
166 typedef struct new_var_data *new_var;
167 typedef const struct new_var_data *const_new_var;
169 /* This structure represents allocation site of the structure. */
170 typedef struct alloc_site
176 DEF_VEC_O (alloc_site_t);
177 DEF_VEC_ALLOC_O (alloc_site_t, heap);
179 /* Allocation sites that belong to the same function. */
180 struct func_alloc_sites
183 /* Vector of allocation sites for function. */
184 VEC (alloc_site_t, heap) *allocs;
187 typedef struct func_alloc_sites *fallocs_t;
188 typedef const struct func_alloc_sites *const_fallocs_t;
190 /* All allocation sites in the program. */
191 htab_t alloc_sites = NULL;
193 /* New global variables. Generated once for whole program. */
194 htab_t new_global_vars;
196 /* New local variables. Generated per-function. */
197 htab_t new_local_vars;
199 /* Vector of structures to be transformed. */
200 typedef struct data_structure structure;
201 DEF_VEC_O (structure);
202 DEF_VEC_ALLOC_O (structure, heap);
203 VEC (structure, heap) *structures;
205 /* Forward declarations. */
206 static bool is_equal_types (tree, tree);
208 /* Strip structure TYPE from pointers and arrays. */
211 strip_type (tree type)
213 gcc_assert (TYPE_P (type));
215 while (POINTER_TYPE_P (type)
216 || TREE_CODE (type) == ARRAY_TYPE)
217 type = TREE_TYPE (type);
222 /* This function returns type of VAR. */
225 get_type_of_var (tree var)
230 if (TREE_CODE (var) == PARM_DECL)
231 return DECL_ARG_TYPE (var);
233 return TREE_TYPE (var);
236 /* Set of actions we do for each newly generated STMT. */
239 finalize_stmt (gimple stmt)
242 mark_symbols_for_renaming (stmt);
245 /* This function finalizes STMT and appends it to the list STMTS. */
248 finalize_stmt_and_append (gimple_seq *stmts, gimple stmt)
250 gimple_seq_add_stmt (stmts, stmt);
251 finalize_stmt (stmt);
254 /* Given structure type SRT_TYPE and field FIELD,
255 this function is looking for a field with the same name
256 and type as FIELD in STR_TYPE. It returns it if found,
257 or NULL_TREE otherwise. */
260 find_field_in_struct_1 (tree str_type, tree field)
264 for (str_field = TYPE_FIELDS (str_type); str_field;
265 str_field = TREE_CHAIN (str_field))
267 const char * str_field_name;
268 const char * field_name;
270 str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field));
271 field_name = IDENTIFIER_POINTER (DECL_NAME (field));
273 gcc_assert (str_field_name);
274 gcc_assert (field_name);
276 if (!strcmp (str_field_name, field_name))
278 /* Check field types. */
279 if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field)))
287 /* Given a field declaration FIELD_DECL, this function
288 returns corresponding field entry in structure STR. */
290 static struct field_entry *
291 find_field_in_struct (d_str str, tree field_decl)
295 tree field = find_field_in_struct_1 (str->decl, field_decl);
297 for (i = 0; i < str->num_fields; i++)
298 if (str->fields[i].decl == field)
299 return &(str->fields[i]);
304 /* This function checks whether ARG is a result of multiplication
305 of some number by STRUCT_SIZE. If yes, the function returns true
306 and this number is filled into NUM. */
309 is_result_of_mult (tree arg, tree *num, tree struct_size)
311 gimple size_def_stmt = SSA_NAME_DEF_STMT (arg);
313 /* If the allocation statement was of the form
314 D.2229_10 = <alloc_func> (D.2228_9);
315 then size_def_stmt can be D.2228_9 = num.3_8 * 8; */
317 if (size_def_stmt && is_gimple_assign (size_def_stmt))
319 tree lhs = gimple_assign_lhs (size_def_stmt);
321 /* We expect temporary here. */
322 if (!is_gimple_reg (lhs))
325 if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR)
327 tree arg0 = gimple_assign_rhs1 (size_def_stmt);
328 tree arg1 = gimple_assign_rhs2 (size_def_stmt);
330 if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST))
336 if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST))
349 /* This function returns true if access ACC corresponds to the pattern
350 generated by compiler when an address of element i of an array
351 of structures STR_DECL (pointed by p) is calculated (p[i]). If this
352 pattern is recognized correctly, this function returns true
353 and fills missing fields in ACC. Otherwise it returns false. */
356 decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc)
359 tree struct_size, op0, op1;
361 enum tree_code rhs_code;
363 ref_var = TREE_OPERAND (acc->ref, 0);
365 if (TREE_CODE (ref_var) != SSA_NAME)
368 acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var);
369 if (!(acc->ref_def_stmt)
370 || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN))
373 rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt);
375 if (rhs_code != PLUS_EXPR
376 && rhs_code != MINUS_EXPR
377 && rhs_code != POINTER_PLUS_EXPR)
380 op0 = gimple_assign_rhs1 (acc->ref_def_stmt);
381 op1 = gimple_assign_rhs2 (acc->ref_def_stmt);
383 if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1,
384 &acc->base, &acc->offset,
389 before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE);
391 before_cast = acc->offset;
397 if (SSA_NAME_IS_DEFAULT_DEF (before_cast))
400 struct_size = TYPE_SIZE_UNIT (str_decl);
402 if (!is_result_of_mult (before_cast, &acc->num, struct_size))
409 /* This function checks whether the access ACC of structure type STR
410 is of the form suitable for transformation. If yes, it returns true.
414 decompose_access (tree str_decl, struct field_access_site *acc)
416 gcc_assert (acc->ref);
418 if (TREE_CODE (acc->ref) == INDIRECT_REF)
419 return decompose_indirect_ref_acc (str_decl, acc);
420 else if (TREE_CODE (acc->ref) == ARRAY_REF)
422 else if (TREE_CODE (acc->ref) == VAR_DECL)
428 /* This function creates empty field_access_site node. */
430 static inline struct field_access_site *
431 make_field_acc_node (void)
433 int size = sizeof (struct field_access_site);
435 return (struct field_access_site *) xcalloc (1, size);
438 /* This function returns the structure field access, defined by STMT,
439 if it is already in hashtable of function accesses F_ACCS. */
441 static struct field_access_site *
442 is_in_field_accs (gimple stmt, htab_t f_accs)
444 return (struct field_access_site *)
445 htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt));
448 /* This function adds an access ACC to the hashtable
449 F_ACCS of field accesses. */
452 add_field_acc_to_acc_sites (struct field_access_site *acc,
457 gcc_assert (!is_in_field_accs (acc->stmt, f_accs));
458 slot = htab_find_slot_with_hash (f_accs, acc->stmt,
459 htab_hash_pointer (acc->stmt),
464 /* This function adds the VAR to vector of variables of
465 an access site defined by statement STMT. If access entry
466 with statement STMT does not exist in hashtable of
467 accesses ACCS, this function creates it. */
470 add_access_to_acc_sites (gimple stmt, tree var, htab_t accs)
472 struct access_site *acc;
474 acc = (struct access_site *)
475 htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt));
481 acc = (struct access_site *) xmalloc (sizeof (struct access_site));
483 acc->vars = VEC_alloc (tree, heap, 10);
484 slot = htab_find_slot_with_hash (accs, stmt,
485 htab_hash_pointer (stmt), INSERT);
489 VEC_safe_push (tree, heap, acc->vars, var);
492 /* This function adds NEW_DECL to function
493 referenced vars, and marks it for renaming. */
496 finalize_var_creation (tree new_decl)
498 add_referenced_var (new_decl);
499 if (is_global_var (new_decl))
500 mark_call_clobbered (new_decl, ESCAPE_UNKNOWN);
501 mark_sym_for_renaming (new_decl);
504 /* This function finalizes VAR creation if it is a global VAR_DECL. */
507 finalize_global_creation (tree var)
509 if (TREE_CODE (var) == VAR_DECL
510 && is_global_var (var))
511 finalize_var_creation (var);
514 /* This function inserts NEW_DECL to varpool. */
517 insert_global_to_varpool (tree new_decl)
519 struct varpool_node *new_node;
521 new_node = varpool_node (new_decl);
522 notice_global_symbol (new_decl);
523 varpool_mark_needed_node (new_node);
524 varpool_finalize_decl (new_decl);
527 /* This function finalizes the creation of new variables,
528 defined by *SLOT->new_vars. */
531 finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED)
533 new_var n_var = *(new_var *) slot;
537 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
538 finalize_var_creation (var);
542 /* This function looks for the variable of NEW_TYPE type, stored in VAR.
543 It returns it, if found, and NULL_TREE otherwise. */
546 find_var_in_new_vars_vec (new_var var, tree new_type)
551 for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++)
553 tree type = strip_type(get_type_of_var (n_var));
556 if (type == new_type)
563 /* This function returns new_var node, the orig_var of which is DECL.
564 It looks for new_var's in NEW_VARS_HTAB. If not found,
565 the function returns NULL. */
568 is_in_new_vars_htab (tree decl, htab_t new_vars_htab)
570 return (new_var) htab_find_with_hash (new_vars_htab, decl,
571 htab_hash_pointer (decl));
574 /* Given original variable ORIG_VAR, this function returns
575 new variable corresponding to it of NEW_TYPE type. */
578 find_new_var_of_type (tree orig_var, tree new_type)
581 gcc_assert (orig_var && new_type);
583 if (TREE_CODE (orig_var) == SSA_NAME)
584 orig_var = SSA_NAME_VAR (orig_var);
586 var = is_in_new_vars_htab (orig_var, new_global_vars);
588 var = is_in_new_vars_htab (orig_var, new_local_vars);
590 return find_var_in_new_vars_vec (var, new_type);
593 /* This function generates stmt:
594 res = NUM * sizeof(TYPE) and returns it.
595 res is filled into RES. */
598 gen_size (tree num, tree type, tree *res)
600 tree struct_size = TYPE_SIZE_UNIT (type);
601 HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size);
604 *res = create_tmp_var (TREE_TYPE (num), NULL);
607 add_referenced_var (*res);
609 if (exact_log2 (struct_size_int) == -1)
611 tree size = build_int_cst (TREE_TYPE (num), struct_size_int);
612 new_stmt = gimple_build_assign_with_ops (MULT_EXPR, *res, num, size);
616 tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int));
618 new_stmt = gimple_build_assign_with_ops (LSHIFT_EXPR, *res, num, C);
621 finalize_stmt (new_stmt);
625 /* This function generates and returns a statement, that cast variable
626 BEFORE_CAST to NEW_TYPE. The cast result variable is stored
627 into RES_P. ORIG_CAST_STMT is the original cast statement. */
630 gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt,
636 lhs = gimple_assign_lhs (orig_cast_stmt);
637 new_lhs = find_new_var_of_type (lhs, new_type);
638 gcc_assert (new_lhs);
640 new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0);
641 finalize_stmt (new_stmt);
646 /* This function builds an edge between BB and E->dest and updates
647 phi nodes of E->dest. It returns newly created edge. */
650 make_edge_and_fix_phis_of_dest (basic_block bb, edge e)
654 gimple_stmt_iterator si;
656 new_e = make_edge (bb, e->dest, e->flags);
658 for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si))
660 gimple phi = gsi_stmt (si);
661 arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
662 add_phi_arg (phi, arg, new_e);
668 /* This function inserts NEW_STMT before STMT. */
671 insert_before_stmt (gimple stmt, gimple new_stmt)
673 gimple_stmt_iterator bsi;
675 if (!stmt || !new_stmt)
678 bsi = gsi_for_stmt (stmt);
679 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
682 /* Insert NEW_STMTS after STMT. */
685 insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts)
687 gimple_stmt_iterator bsi;
689 if (!stmt || !new_stmts)
692 bsi = gsi_for_stmt (stmt);
693 gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT);
696 /* Insert NEW_STMT after STMT. */
699 insert_after_stmt (gimple stmt, gimple new_stmt)
701 gimple_stmt_iterator bsi;
703 if (!stmt || !new_stmt)
706 bsi = gsi_for_stmt (stmt);
707 gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT);
710 /* This function returns vector of allocation sites
711 that appear in function FN_DECL. */
714 get_fallocs (tree fn_decl)
716 return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl,
717 htab_hash_pointer (fn_decl));
720 /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6);
721 and it is a part of allocation of a structure,
722 then it is usually followed by a cast stmt
723 p_8 = (struct str_t *) D.2225_7;
724 which is returned by this function. */
727 get_final_alloc_stmt (gimple alloc_stmt)
736 if (!is_gimple_call (alloc_stmt))
739 alloc_res = gimple_get_lhs (alloc_stmt);
741 if (TREE_CODE (alloc_res) != SSA_NAME)
744 if (!single_imm_use (alloc_res, &use_p, &final_stmt))
750 /* This function returns true if STMT is one of allocation
751 sites of function FN_DECL. It returns false otherwise. */
754 is_part_of_malloc (gimple stmt, tree fn_decl)
756 fallocs_t fallocs = get_fallocs (fn_decl);
763 for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++)
764 if (call->stmt == stmt
765 || get_final_alloc_stmt (call->stmt) == stmt)
771 /* Auxiliary structure for a lookup over field accesses. */
772 struct find_stmt_data
778 /* This function looks for DATA->stmt among
779 the statements involved in the field access,
780 defined by SLOT. It stops when it's found. */
783 find_in_field_accs (void **slot, void *data)
785 struct field_access_site *f_acc = *(struct field_access_site **) slot;
786 gimple stmt = ((struct find_stmt_data *)data)->stmt;
788 if (f_acc->stmt == stmt
789 || f_acc->ref_def_stmt == stmt
790 || f_acc->cast_stmt == stmt)
792 ((struct find_stmt_data *)data)->found = true;
799 /* This function checks whether STMT is part of field
800 accesses of structure STR. It returns true, if found,
801 and false otherwise. */
804 is_part_of_field_access (gimple stmt, d_str str)
808 for (i = 0; i < str->num_fields; i++)
810 struct find_stmt_data data;
814 if (str->fields[i].acc_sites)
815 htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data);
824 /* Auxiliary data for exclude_from_accs function. */
832 /* This function returns component_ref with the BASE and
833 field named FIELD_ID from structure TYPE. */
836 build_comp_ref (tree base, tree field_id, tree type)
842 /* Find field of structure type with the same name as field_id. */
843 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
845 if (DECL_NAME (field) == field_id)
854 return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE);
858 /* This struct represent data used for walk_tree
859 called from function find_pos_in_stmt.
860 - ref is a tree to be found,
861 - and pos is a pointer that points to ref in stmt. */
869 /* This is a callback function for walk_tree, called from
870 collect_accesses_in_bb function. DATA is a pointer to ref_pos structure.
871 When *TP is equal to DATA->ref, the walk_tree stops,
872 and found position, equal to TP, is assigned to DATA->pos. */
875 find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data)
877 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
878 struct ref_pos *r_pos = (struct ref_pos *) wi->info;
879 tree ref = r_pos->ref;
882 if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref))
893 /* This function looks for the pointer of REF in STMT,
894 It returns it, if found, and NULL otherwise. */
897 find_pos_in_stmt (gimple stmt, tree ref)
899 struct ref_pos r_pos;
900 struct walk_stmt_info wi;
904 memset (&wi, 0, sizeof (wi));
906 walk_gimple_op (stmt, find_pos_in_stmt_1, &wi);
911 /* This structure is used to represent array
912 or pointer-to wrappers of structure type.
913 For example, if type1 is structure type,
914 then for type1 ** we generate two type_wrapper
915 structures with wrap = 0 each one.
916 It's used to unwind the original type up to
917 structure type, replace it with the new structure type
918 and wrap it back in the opposite order. */
920 typedef struct type_wrapper
922 /* 0 stand for pointer wrapper, and 1 for array wrapper. */
925 /* Relevant for arrays as domain or index. */
929 DEF_VEC_O (type_wrapper_t);
930 DEF_VEC_ALLOC_O (type_wrapper_t, heap);
932 /* This function replace field access ACC by the new
933 field access of structure type NEW_TYPE. */
936 replace_field_acc (struct field_access_site *acc, tree new_type)
938 tree ref_var = acc->ref;
943 tree field_id = DECL_NAME (acc->field_decl);
944 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
945 type_wrapper_t *wr_p = NULL;
947 while (TREE_CODE (ref_var) == INDIRECT_REF
948 || TREE_CODE (ref_var) == ARRAY_REF)
952 if ( TREE_CODE (ref_var) == INDIRECT_REF)
960 wr.domain = TREE_OPERAND (ref_var, 1);
963 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
964 ref_var = TREE_OPERAND (ref_var, 0);
967 new_ref = find_new_var_of_type (ref_var, new_type);
968 finalize_global_creation (new_ref);
970 while (VEC_length (type_wrapper_t, wrapper) != 0)
972 tree type = TREE_TYPE (TREE_TYPE (new_ref));
974 wr_p = VEC_last (type_wrapper_t, wrapper);
975 if (wr_p->wrap) /* Array. */
976 new_ref = build4 (ARRAY_REF, type, new_ref,
977 wr_p->domain, NULL_TREE, NULL_TREE);
979 new_ref = build1 (INDIRECT_REF, type, new_ref);
980 VEC_pop (type_wrapper_t, wrapper);
983 new_acc = build_comp_ref (new_ref, field_id, new_type);
984 VEC_free (type_wrapper_t, heap, wrapper);
986 if (is_gimple_assign (acc->stmt))
988 lhs = gimple_assign_lhs (acc->stmt);
989 rhs = gimple_assign_rhs1 (acc->stmt);
991 if (lhs == acc->comp_ref)
992 gimple_assign_set_lhs (acc->stmt, new_acc);
993 else if (rhs == acc->comp_ref)
994 gimple_assign_set_rhs1 (acc->stmt, new_acc);
997 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1004 pos = find_pos_in_stmt (acc->stmt, acc->comp_ref);
1009 finalize_stmt (acc->stmt);
1012 /* This function replace field access ACC by a new field access
1013 of structure type NEW_TYPE. */
1016 replace_field_access_stmt (struct field_access_site *acc, tree new_type)
1019 if (TREE_CODE (acc->ref) == INDIRECT_REF
1020 ||TREE_CODE (acc->ref) == ARRAY_REF
1021 ||TREE_CODE (acc->ref) == VAR_DECL)
1022 replace_field_acc (acc, new_type);
1027 /* This function looks for d_str, represented by TYPE, in the structures
1028 vector. If found, it returns an index of found structure. Otherwise
1029 it returns a length of the structures vector. */
1032 find_structure (tree type)
1037 type = TYPE_MAIN_VARIANT (type);
1039 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
1040 if (is_equal_types (str->decl, type))
1043 return VEC_length (structure, structures);
1046 /* In this function we create new statements that have the same
1047 form as ORIG_STMT, but of type NEW_TYPE. The statements
1048 treated by this function are simple assignments,
1049 like assignments: p.8_7 = p; or statements with rhs of
1050 tree codes PLUS_EXPR and MINUS_EXPR. */
1053 create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset)
1058 tree new_op0 = NULL_TREE, new_op1 = NULL_TREE;
1060 lhs = gimple_assign_lhs (orig_stmt);
1062 gcc_assert (TREE_CODE (lhs) == VAR_DECL
1063 || TREE_CODE (lhs) == SSA_NAME);
1065 new_lhs = find_new_var_of_type (lhs, new_type);
1066 gcc_assert (new_lhs);
1067 finalize_var_creation (new_lhs);
1069 switch (gimple_assign_rhs_code (orig_stmt))
1073 case POINTER_PLUS_EXPR:
1075 tree op0 = gimple_assign_rhs1 (orig_stmt);
1076 tree op1 = gimple_assign_rhs2 (orig_stmt);
1077 unsigned str0, str1;
1078 unsigned length = VEC_length (structure, structures);
1081 str0 = find_structure (strip_type (get_type_of_var (op0)));
1082 str1 = find_structure (strip_type (get_type_of_var (op1)));
1083 gcc_assert ((str0 != length) || (str1 != length));
1086 new_op0 = find_new_var_of_type (op0, new_type);
1088 new_op1 = find_new_var_of_type (op1, new_type);
1101 new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt),
1102 new_lhs, new_op0, new_op1);
1103 finalize_stmt (new_stmt);
1108 /* Given a field access F_ACC of the FIELD, this function
1109 replaces it by the new field access. */
1112 create_new_field_access (struct field_access_site *f_acc,
1113 struct field_entry field)
1115 tree new_type = field.field_mapping;
1120 tree cast_res = NULL;
1124 mult_stmt = gen_size (f_acc->num, new_type, &size_res);
1125 insert_before_stmt (f_acc->ref_def_stmt, mult_stmt);
1128 if (f_acc->cast_stmt)
1130 cast_stmt = gen_cast_stmt (size_res, new_type,
1131 f_acc->cast_stmt, &cast_res);
1132 insert_after_stmt (f_acc->cast_stmt, cast_stmt);
1135 if (f_acc->ref_def_stmt)
1143 new_stmt = create_base_plus_offset (f_acc->ref_def_stmt,
1145 insert_after_stmt (f_acc->ref_def_stmt, new_stmt);
1148 /* In stmt D.2163_19 = D.2162_18->b; we replace variable
1149 D.2162_18 by an appropriate variable of new_type type. */
1150 replace_field_access_stmt (f_acc, new_type);
1153 /* This function creates a new condition statement
1154 corresponding to the original COND_STMT, adds new basic block
1155 and redirects condition edges. NEW_VAR is a new condition
1156 variable located in the condition statement at the position POS. */
1159 create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos)
1162 edge true_e = NULL, false_e = NULL;
1164 gimple_stmt_iterator si;
1166 extract_true_false_edges_from_block (gimple_bb (cond_stmt),
1169 new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1170 pos == 0 ? new_var : gimple_cond_lhs (cond_stmt),
1171 pos == 1 ? new_var : gimple_cond_rhs (cond_stmt),
1175 finalize_stmt (new_stmt);
1177 /* Create new basic block after bb. */
1178 new_bb = create_empty_bb (gimple_bb (cond_stmt));
1180 /* Add new condition stmt to the new_bb. */
1181 si = gsi_start_bb (new_bb);
1182 gsi_insert_after (&si, new_stmt, GSI_NEW_STMT);
1184 /* Create false and true edges from new_bb. */
1185 make_edge_and_fix_phis_of_dest (new_bb, true_e);
1186 make_edge_and_fix_phis_of_dest (new_bb, false_e);
1188 /* Redirect one of original edges to point to new_bb. */
1189 if (gimple_cond_code (cond_stmt) == NE_EXPR)
1190 redirect_edge_succ (true_e, new_bb);
1192 redirect_edge_succ (false_e, new_bb);
1195 /* This function creates new condition statements corresponding
1196 to original condition STMT, one for each new type, and
1197 recursively redirect edges to newly generated basic blocks. */
1200 create_new_stmts_for_cond_expr (gimple stmt)
1202 tree arg0, arg1, arg;
1203 unsigned str0, str1;
1209 unsigned length = VEC_length (structure, structures);
1211 gcc_assert (gimple_cond_code (stmt) == EQ_EXPR
1212 || gimple_cond_code (stmt) == NE_EXPR);
1214 arg0 = gimple_cond_lhs (stmt);
1215 arg1 = gimple_cond_rhs (stmt);
1217 str0 = find_structure (strip_type (get_type_of_var (arg0)));
1218 str1 = find_structure (strip_type (get_type_of_var (arg1)));
1220 s0 = (str0 != length) ? true : false;
1221 s1 = (str1 != length) ? true : false;
1223 gcc_assert (s0 || s1);
1224 /* For now we allow only comparison with 0 or NULL. */
1225 gcc_assert (integer_zerop (arg0) || integer_zerop (arg1));
1227 str = integer_zerop (arg0) ?
1228 VEC_index (structure, structures, str1):
1229 VEC_index (structure, structures, str0);
1230 arg = integer_zerop (arg0) ? arg1 : arg0;
1231 pos = integer_zerop (arg0) ? 1 : 0;
1233 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1237 new_arg = find_new_var_of_type (arg, type);
1238 create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos);
1242 /* Create a new general access to replace original access ACC
1243 for structure type NEW_TYPE. */
1246 create_general_new_stmt (struct access_site *acc, tree new_type)
1248 gimple old_stmt = acc->stmt;
1250 gimple new_stmt = gimple_copy (old_stmt);
1253 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
1256 tree new_var = find_new_var_of_type (var, new_type);
1259 gcc_assert (new_var);
1260 finalize_var_creation (new_var);
1262 if (is_gimple_assign (new_stmt))
1264 lhs = gimple_assign_lhs (new_stmt);
1266 if (TREE_CODE (lhs) == SSA_NAME)
1267 lhs = SSA_NAME_VAR (lhs);
1268 if (gimple_assign_rhs_code (new_stmt) == SSA_NAME)
1269 rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt));
1271 /* It can happen that rhs is a constructor.
1272 Then we have to replace it to be of new_type. */
1273 if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR)
1275 /* Dealing only with empty constructors right now. */
1276 gcc_assert (VEC_empty (constructor_elt,
1277 CONSTRUCTOR_ELTS (rhs)));
1278 rhs = build_constructor (new_type, 0);
1279 gimple_assign_set_rhs1 (new_stmt, rhs);
1283 gimple_assign_set_lhs (new_stmt, new_var);
1284 else if (rhs == var)
1285 gimple_assign_set_rhs1 (new_stmt, new_var);
1288 pos = find_pos_in_stmt (new_stmt, var);
1295 pos = find_pos_in_stmt (new_stmt, var);
1301 finalize_stmt (new_stmt);
1305 /* For each new type in STR this function creates new general accesses
1306 corresponding to the original access ACC. */
1309 create_new_stmts_for_general_acc (struct access_site *acc, d_str str)
1312 gimple stmt = acc->stmt;
1315 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
1319 new_stmt = create_general_new_stmt (acc, type);
1320 insert_after_stmt (stmt, new_stmt);
1324 /* This function creates a new general access of structure STR
1325 to replace the access ACC. */
1328 create_new_general_access (struct access_site *acc, d_str str)
1330 gimple stmt = acc->stmt;
1331 switch (gimple_code (stmt))
1334 create_new_stmts_for_cond_expr (stmt);
1338 create_new_stmts_for_general_acc (acc, str);
1342 /* Auxiliary data for creation of accesses. */
1343 struct create_acc_data
1350 /* This function creates a new general access, defined by SLOT.
1351 DATA is a pointer to create_acc_data structure. */
1354 create_new_acc (void **slot, void *data)
1356 struct access_site *acc = *(struct access_site **) slot;
1357 basic_block bb = ((struct create_acc_data *)data)->bb;
1358 d_str str = ((struct create_acc_data *)data)->str;
1360 if (gimple_bb (acc->stmt) == bb)
1361 create_new_general_access (acc, str);
1365 /* This function creates a new field access, defined by SLOT.
1366 DATA is a pointer to create_acc_data structure. */
1369 create_new_field_acc (void **slot, void *data)
1371 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1372 basic_block bb = ((struct create_acc_data *)data)->bb;
1373 d_str str = ((struct create_acc_data *)data)->str;
1374 int i = ((struct create_acc_data *)data)->field_index;
1376 if (gimple_bb (f_acc->stmt) == bb)
1377 create_new_field_access (f_acc, str->fields[i]);
1381 /* This function creates new accesses for the structure
1382 type STR in basic block BB. */
1385 create_new_accs_for_struct (d_str str, basic_block bb)
1388 struct create_acc_data dt;
1392 dt.field_index = -1;
1394 for (i = 0; i < str->num_fields; i++)
1398 if (str->fields[i].acc_sites)
1399 htab_traverse (str->fields[i].acc_sites,
1400 create_new_field_acc, &dt);
1403 htab_traverse (str->accs, create_new_acc, &dt);
1406 /* This function inserts new variables from new_var,
1407 defined by SLOT, into varpool. */
1410 update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1412 new_var n_var = *(new_var *) slot;
1416 for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++)
1417 insert_global_to_varpool (var);
1421 /* This function prints a field access site, defined by SLOT. */
1424 dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED)
1426 struct field_access_site *f_acc =
1427 *(struct field_access_site **) slot;
1429 fprintf(dump_file, "\n");
1431 print_gimple_stmt (dump_file, f_acc->stmt, 0, 0);
1432 if (f_acc->ref_def_stmt)
1433 print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0);
1434 if (f_acc->cast_stmt)
1435 print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0);
1439 /* Print field accesses from hashtable F_ACCS. */
1442 dump_field_acc_sites (htab_t f_accs)
1448 htab_traverse (f_accs, dump_field_acc, NULL);
1451 /* Hash value for fallocs_t. */
1454 malloc_hash (const void *x)
1456 return htab_hash_pointer (((const_fallocs_t)x)->func);
1459 /* This function returns nonzero if function of func_alloc_sites' X
1463 malloc_eq (const void *x, const void *y)
1465 return ((const_fallocs_t)x)->func == (const_tree)y;
1468 /* This function is a callback for traversal over a structure accesses.
1469 It frees an access represented by SLOT. */
1472 free_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1474 struct access_site * acc = *(struct access_site **) slot;
1476 VEC_free (tree, heap, acc->vars);
1481 /* This is a callback function for traversal over field accesses.
1482 It frees a field access represented by SLOT. */
1485 free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED)
1487 struct field_access_site *f_acc = *(struct field_access_site **) slot;
1493 /* This function inserts TYPE into vector of UNSUITABLE_TYPES,
1494 if it is not there yet. */
1497 add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type)
1505 type = TYPE_MAIN_VARIANT (type);
1507 for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++)
1508 if (is_equal_types (t, type))
1511 if (i == VEC_length (tree, *unsuitable_types))
1512 VEC_safe_push (tree, heap, *unsuitable_types, type);
1515 /* Given a type TYPE, this function returns the name of the type. */
1518 get_type_name (tree type)
1520 if (! TYPE_NAME (type))
1523 if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE)
1524 return IDENTIFIER_POINTER (TYPE_NAME (type));
1525 else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
1526 && DECL_NAME (TYPE_NAME (type)))
1527 return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type)));
1532 /* This function is a temporary hack to overcome the types problem.
1533 When several compilation units are compiled together
1534 with -combine, the TYPE_MAIN_VARIANT of the same type
1535 can appear differently in different compilation units.
1536 Therefore this function first compares type names.
1537 If there are no names, structure bodies are recursively
1541 is_equal_types (tree type1, tree type2)
1543 const char * name1,* name2;
1545 if ((!type1 && type2)
1546 ||(!type2 && type1))
1549 if (!type1 && !type2)
1552 if (TREE_CODE (type1) != TREE_CODE (type2))
1558 if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2))
1561 name1 = get_type_name (type1);
1562 name2 = get_type_name (type2);
1564 if (name1 && name2 && !strcmp (name1, name2))
1567 if (name1 && name2 && strcmp (name1, name2))
1570 switch (TREE_CODE (type1))
1573 case REFERENCE_TYPE:
1575 return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2));
1581 case QUAL_UNION_TYPE:
1585 /* Compare fields of structure. */
1586 for (field1 = TYPE_FIELDS (type1); field1;
1587 field1 = TREE_CHAIN (field1))
1589 tree field2 = find_field_in_struct_1 (type2, field1);
1599 if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
1600 && TYPE_PRECISION (type1) == TYPE_PRECISION (type2))
1608 tree max1, min1, max2, min2;
1610 if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)))
1613 d1 = TYPE_DOMAIN (type1);
1614 d2 = TYPE_DOMAIN (type2);
1619 max1 = TYPE_MAX_VALUE (d1);
1620 max2 = TYPE_MAX_VALUE (d2);
1621 min1 = TYPE_MIN_VALUE (d1);
1622 min2 = TYPE_MIN_VALUE (d2);
1624 if (max1 && max2 && min1 && min2
1625 && TREE_CODE (max1) == TREE_CODE (max2)
1626 && TREE_CODE (max1) == INTEGER_CST
1627 && TREE_CODE (min1) == TREE_CODE (min2)
1628 && TREE_CODE (min1) == INTEGER_CST
1629 && tree_int_cst_equal (max1, max2)
1630 && tree_int_cst_equal (min1, min2))
1642 /* This function free non-field accesses from hashtable ACCS. */
1645 free_accesses (htab_t accs)
1648 htab_traverse (accs, free_accs, NULL);
1652 /* This function free field accesses hashtable F_ACCS. */
1655 free_field_accesses (htab_t f_accs)
1658 htab_traverse (f_accs, free_field_accs, NULL);
1659 htab_delete (f_accs);
1662 /* Update call graph with new edge generated by new MALLOC_STMT.
1663 The edge origin is CONTEXT function. */
1666 update_cgraph_with_malloc_call (gimple malloc_stmt, tree context)
1668 struct cgraph_node *src, *dest;
1669 tree malloc_fn_decl;
1674 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1676 src = cgraph_node (context);
1677 dest = cgraph_node (malloc_fn_decl);
1678 cgraph_create_edge (src, dest, malloc_stmt,
1679 0, 0, gimple_bb (malloc_stmt)->loop_depth);
1682 /* This function generates set of statements required
1683 to allocate number NUM of structures of type NEW_TYPE.
1684 The statements are stored in NEW_STMTS. The statement that contain
1685 call to malloc is returned. MALLOC_STMT is an original call to malloc. */
1688 create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts,
1691 tree new_malloc_size;
1692 tree malloc_fn_decl;
1695 gimple call_stmt, final_stmt;
1698 gcc_assert (num && malloc_stmt && new_type);
1699 *new_stmts = gimple_seq_alloc ();
1701 /* Generate argument to malloc as multiplication of num
1702 and size of new_type. */
1703 new_stmt = gen_size (num, new_type, &new_malloc_size);
1704 gimple_seq_add_stmt (new_stmts, new_stmt);
1706 /* Generate new call for malloc. */
1707 malloc_res = create_tmp_var (ptr_type_node, NULL);
1708 add_referenced_var (malloc_res);
1710 malloc_fn_decl = gimple_call_fndecl (malloc_stmt);
1711 call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size);
1712 gimple_call_set_lhs (call_stmt, malloc_res);
1713 finalize_stmt_and_append (new_stmts, call_stmt);
1715 /* Create new cast statement. */
1716 final_stmt = get_final_alloc_stmt (malloc_stmt);
1717 gcc_assert (final_stmt);
1718 new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res);
1719 gimple_seq_add_stmt (new_stmts, new_stmt);
1724 /* This function returns a tree representing
1725 the number of instances of structure STR_DECL allocated
1726 by allocation STMT. If new statements are generated,
1727 they are filled into NEW_STMTS_P. */
1730 gen_num_of_structs_in_malloc (gimple stmt, tree str_decl,
1731 gimple_seq *new_stmts_p)
1735 HOST_WIDE_INT struct_size_int;
1740 /* Get malloc argument. */
1741 if (!is_gimple_call (stmt))
1744 arg = gimple_call_arg (stmt, 0);
1746 if (TREE_CODE (arg) != SSA_NAME
1747 && !TREE_CONSTANT (arg))
1750 struct_size = TYPE_SIZE_UNIT (str_decl);
1751 struct_size_int = TREE_INT_CST_LOW (struct_size);
1753 gcc_assert (struct_size);
1755 if (TREE_CODE (arg) == SSA_NAME)
1760 if (is_result_of_mult (arg, &num, struct_size))
1763 num = create_tmp_var (integer_type_node, NULL);
1766 add_referenced_var (num);
1768 if (exact_log2 (struct_size_int) == -1)
1769 div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg,
1773 tree C = build_int_cst (integer_type_node,
1774 exact_log2 (struct_size_int));
1776 div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C);
1778 gimple_seq_add_stmt (new_stmts_p, div_stmt);
1779 finalize_stmt (div_stmt);
1783 if (CONSTANT_CLASS_P (arg)
1784 && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size))
1785 return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0);
1790 /* This function is a callback for traversal on new_var's hashtable.
1791 SLOT is a pointer to new_var. This function prints to dump_file
1792 an original variable and all new variables from the new_var
1793 pointed by *SLOT. */
1796 dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
1798 new_var n_var = *(new_var *) slot;
1803 var_type = get_type_of_var (n_var->orig_var);
1805 fprintf (dump_file, "\nOrig var: ");
1806 print_generic_expr (dump_file, n_var->orig_var, 0);
1807 fprintf (dump_file, " of type ");
1808 print_generic_expr (dump_file, var_type, 0);
1809 fprintf (dump_file, "\n");
1812 VEC_iterate (tree, n_var->new_vars, i, var); i++)
1814 var_type = get_type_of_var (var);
1816 fprintf (dump_file, " ");
1817 print_generic_expr (dump_file, var, 0);
1818 fprintf (dump_file, " of type ");
1819 print_generic_expr (dump_file, var_type, 0);
1820 fprintf (dump_file, "\n");
1825 /* This function copies attributes form ORIG_DECL to NEW_DECL. */
1828 copy_decl_attributes (tree new_decl, tree orig_decl)
1831 DECL_ARTIFICIAL (new_decl) = 1;
1832 DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl);
1833 TREE_STATIC (new_decl) = TREE_STATIC (orig_decl);
1834 TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl);
1835 TREE_USED (new_decl) = TREE_USED (orig_decl);
1836 DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl);
1837 TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl);
1838 TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl);
1840 if (TREE_CODE (orig_decl) == VAR_DECL)
1842 TREE_READONLY (new_decl) = TREE_READONLY (orig_decl);
1843 DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl);
1847 /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper
1848 the same way as a structure type is wrapped in DECL.
1849 It returns the generated type. */
1852 gen_struct_type (tree decl, tree new_str_type)
1854 tree type_orig = get_type_of_var (decl);
1855 tree new_type = new_str_type;
1856 VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10);
1858 type_wrapper_t *wr_p;
1860 while (POINTER_TYPE_P (type_orig)
1861 || TREE_CODE (type_orig) == ARRAY_TYPE)
1863 if (POINTER_TYPE_P (type_orig))
1866 wr.domain = NULL_TREE;
1870 gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE);
1872 wr.domain = TYPE_DOMAIN (type_orig);
1874 VEC_safe_push (type_wrapper_t, heap, wrapper, &wr);
1875 type_orig = TREE_TYPE (type_orig);
1878 while (VEC_length (type_wrapper_t, wrapper) != 0)
1880 wr_p = VEC_last (type_wrapper_t, wrapper);
1882 if (wr_p->wrap) /* Array. */
1883 new_type = build_array_type (new_type, wr_p->domain);
1885 new_type = build_pointer_type (new_type);
1887 VEC_pop (type_wrapper_t, wrapper);
1890 VEC_free (type_wrapper_t, heap, wrapper);
1894 /* This function generates and returns new variable name based on
1895 ORIG_DECL name, combined with index I.
1896 The form of the new name is <orig_name>.<I> . */
1899 gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i)
1901 const char *old_name;
1905 if (!DECL_NAME (orig_decl)
1906 || !IDENTIFIER_POINTER (DECL_NAME (orig_decl)))
1909 /* If the original variable has a name, create an
1910 appropriate new name for the new variable. */
1912 old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl));
1913 prefix = XALLOCAVEC (char, strlen (old_name) + 1);
1914 strcpy (prefix, old_name);
1915 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i);
1916 return get_identifier (new_name);
1919 /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */
1922 add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab)
1926 slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var,
1927 htab_hash_pointer (new_node->orig_var),
1932 /* This function creates and returns new_var_data node
1933 with empty new_vars and orig_var equal to VAR. */
1936 create_new_var_node (tree var, d_str str)
1940 node = (new_var) xmalloc (sizeof (struct new_var_data));
1941 node->orig_var = var;
1942 node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types));
1946 /* Check whether the type of VAR is potential candidate for peeling.
1947 Returns true if yes, false otherwise. If yes, TYPE_P will contain
1948 candidate type. If VAR is initialized, the type of VAR will be added
1949 to UNSUITABLE_TYPES. */
1952 is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types)
1955 bool initialized = false;
1962 /* There is no support of initialized vars. */
1963 if (TREE_CODE (var) == VAR_DECL
1964 && DECL_INITIAL (var) != NULL_TREE)
1967 type = get_type_of_var (var);
1971 type = TYPE_MAIN_VARIANT (strip_type (type));
1972 if (TREE_CODE (type) != RECORD_TYPE)
1976 if (initialized && unsuitable_types && *unsuitable_types)
1980 fprintf (dump_file, "The type ");
1981 print_generic_expr (dump_file, type, 0);
1982 fprintf (dump_file, " is initialized...Excluded.");
1984 add_unsuitable_type (unsuitable_types, type);
1994 /* Hash value for field_access_site. */
1997 field_acc_hash (const void *x)
1999 return htab_hash_pointer (((const struct field_access_site *)x)->stmt);
2002 /* This function returns nonzero if stmt of field_access_site X
2006 field_acc_eq (const void *x, const void *y)
2008 return ((const struct field_access_site *)x)->stmt == (const_gimple)y;
2011 /* This function prints an access site, defined by SLOT. */
2014 dump_acc (void **slot, void *data ATTRIBUTE_UNUSED)
2016 struct access_site *acc = *(struct access_site **) slot;
2020 fprintf(dump_file, "\n");
2022 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
2023 fprintf(dump_file, " : ");
2025 for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++)
2027 print_generic_expr (dump_file, var, 0);
2028 fprintf(dump_file, ", ");
2033 /* This function frees memory allocated for structure clusters,
2034 starting from CLUSTER. */
2037 free_struct_cluster (struct field_cluster* cluster)
2041 if (cluster->fields_in_cluster)
2042 sbitmap_free (cluster->fields_in_cluster);
2043 if (cluster->sibling)
2044 free_struct_cluster (cluster->sibling);
2049 /* Free all allocated memory under the structure node pointed by D_NODE. */
2052 free_data_struct (d_str d_node)
2061 fprintf (dump_file, "\nRemoving data structure \"");
2062 print_generic_expr (dump_file, d_node->decl, 0);
2063 fprintf (dump_file, "\" from data_struct_list.");
2066 /* Free all space under d_node. */
2069 for (i = 0; i < d_node->num_fields; i++)
2070 free_field_accesses (d_node->fields[i].acc_sites);
2071 free (d_node->fields);
2075 free_accesses (d_node->accs);
2077 if (d_node->struct_clustering)
2078 free_struct_cluster (d_node->struct_clustering);
2080 if (d_node->new_types)
2081 VEC_free (tree, heap, d_node->new_types);
2084 /* This function creates new general and field accesses in BB. */
2087 create_new_accesses_in_bb (basic_block bb)
2092 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2093 create_new_accs_for_struct (str, bb);
2096 /* This function adds allocation sites for peeled structures.
2097 M_DATA is vector of allocation sites of function CONTEXT. */
2100 create_new_alloc_sites (fallocs_t m_data, tree context)
2105 for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++)
2107 gimple stmt = call->stmt;
2108 d_str str = call->str;
2110 gimple_seq new_stmts = NULL;
2111 gimple last_stmt = get_final_alloc_stmt (stmt);
2115 num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts);
2118 gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2119 insert_seq_after_stmt (last_stmt, new_stmts);
2120 last_stmt = last_stmt_tmp;
2123 /* Generate an allocation sites for each new structure type. */
2124 for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++)
2126 gimple new_malloc_stmt = NULL;
2127 gimple last_stmt_tmp = NULL;
2130 new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num);
2131 last_stmt_tmp = gimple_seq_last_stmt (new_stmts);
2132 insert_seq_after_stmt (last_stmt, new_stmts);
2133 update_cgraph_with_malloc_call (new_malloc_stmt, context);
2134 last_stmt = last_stmt_tmp;
2139 /* This function prints new variables from hashtable
2140 NEW_VARS_HTAB to dump_file. */
2143 dump_new_vars (htab_t new_vars_htab)
2149 htab_traverse (new_vars_htab, dump_new_var, NULL);
2152 /* Given an original variable ORIG_DECL of structure type STR,
2153 this function generates new variables of the types defined
2154 by STR->new_type. Generated types are saved in new_var node NODE.
2155 ORIG_DECL should has VAR_DECL tree_code. */
2158 create_new_var_1 (tree orig_decl, d_str str, new_var node)
2164 VEC_iterate (tree, str->new_types, i, type); i++)
2166 tree new_decl = NULL;
2169 new_name = gen_var_name (orig_decl, i);
2170 type = gen_struct_type (orig_decl, type);
2172 if (is_global_var (orig_decl))
2173 new_decl = build_decl (VAR_DECL, new_name, type);
2176 const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL;
2177 new_decl = create_tmp_var (type, name);
2180 copy_decl_attributes (new_decl, orig_decl);
2181 VEC_safe_push (tree, heap, node->new_vars, new_decl);
2185 /* This function creates new variables to
2186 substitute the original variable VAR_DECL and adds
2187 them to the new_var's hashtable NEW_VARS_HTAB. */
2190 create_new_var (tree var_decl, htab_t new_vars_htab)
2197 if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab))
2200 if (!is_candidate (var_decl, &type, NULL))
2203 i = find_structure (type);
2204 if (i == VEC_length (structure, structures))
2207 str = VEC_index (structure, structures, i);
2208 node = create_new_var_node (var_decl, str);
2209 create_new_var_1 (var_decl, str, node);
2210 add_to_new_vars_htab (node, new_vars_htab);
2213 /* Hash value for new_var. */
2216 new_var_hash (const void *x)
2218 return htab_hash_pointer (((const_new_var)x)->orig_var);
2221 /* This function returns nonzero if orig_var of new_var X is equal to Y. */
2224 new_var_eq (const void *x, const void *y)
2226 return ((const_new_var)x)->orig_var == (const_tree)y;
2229 /* This function check whether a structure type represented by STR
2230 escapes due to ipa-type-escape analysis. If yes, this type is added
2231 to UNSUITABLE_TYPES vector. */
2234 check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types)
2236 tree type = str->decl;
2238 if (!ipa_type_escape_type_contained_p (type))
2242 fprintf (dump_file, "\nEscaping type is ");
2243 print_generic_expr (dump_file, type, 0);
2245 add_unsuitable_type (unsuitable_types, type);
2249 /* Hash value for access_site. */
2252 acc_hash (const void *x)
2254 return htab_hash_pointer (((const struct access_site *)x)->stmt);
2257 /* Return nonzero if stmt of access_site X is equal to Y. */
2260 acc_eq (const void *x, const void *y)
2262 return ((const struct access_site *)x)->stmt == (const_gimple)y;
2265 /* Given a structure declaration STRUCT_DECL, and number of fields
2266 in the structure NUM_FIELDS, this function creates and returns
2267 corresponding field_entry's. */
2269 static struct field_entry *
2270 get_fields (tree struct_decl, int num_fields)
2272 struct field_entry *list;
2273 tree t = TYPE_FIELDS (struct_decl);
2277 (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry));
2279 for (idx = 0 ; t; t = TREE_CHAIN (t), idx++)
2280 if (TREE_CODE (t) == FIELD_DECL)
2282 list[idx].index = idx;
2284 list[idx].acc_sites =
2285 htab_create (32, field_acc_hash, field_acc_eq, NULL);
2286 list[idx].count = 0;
2287 list[idx].field_mapping = NULL_TREE;
2293 /* Print non-field accesses from hashtable ACCS of structure. */
2296 dump_access_sites (htab_t accs)
2302 htab_traverse (accs, dump_acc, NULL);
2305 /* This function is a callback for alloc_sites hashtable
2306 traversal. SLOT is a pointer to fallocs_t. This function
2307 removes all allocations of the structure defined by DATA. */
2310 remove_str_allocs_in_func (void **slot, void *data)
2312 fallocs_t fallocs = *(fallocs_t *) slot;
2316 while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call))
2318 if (call->str == (d_str) data)
2319 VEC_ordered_remove (alloc_site_t, fallocs->allocs, i);
2327 /* This function remove all entries corresponding to the STR structure
2328 from alloc_sites hashtable. */
2331 remove_str_allocs (d_str str)
2337 htab_traverse (alloc_sites, remove_str_allocs_in_func, str);
2340 /* This function removes the structure with index I from structures vector. */
2343 remove_structure (unsigned i)
2347 if (i >= VEC_length (structure, structures))
2350 str = VEC_index (structure, structures, i);
2352 /* Before removing the structure str, we have to remove its
2353 allocations from alloc_sites hashtable. */
2354 remove_str_allocs (str);
2355 free_data_struct (str);
2356 VEC_ordered_remove (structure, structures, i);
2359 /* Currently we support only EQ_EXPR or NE_EXPR conditions.
2360 COND_STMT is a condition statement to check. */
2363 is_safe_cond_expr (gimple cond_stmt)
2366 unsigned str0, str1;
2368 unsigned length = VEC_length (structure, structures);
2370 if (gimple_cond_code (cond_stmt) != EQ_EXPR
2371 && gimple_cond_code (cond_stmt) != NE_EXPR)
2374 arg0 = gimple_cond_lhs (cond_stmt);
2375 arg1 = gimple_cond_rhs (cond_stmt);
2377 str0 = find_structure (strip_type (get_type_of_var (arg0)));
2378 str1 = find_structure (strip_type (get_type_of_var (arg1)));
2380 s0 = (str0 != length) ? true : false;
2381 s1 = (str1 != length) ? true : false;
2386 /* For now we allow only comparison with 0 or NULL. */
2387 if (!integer_zerop (arg0) && !integer_zerop (arg1))
2393 /* This function excludes statements, that are
2394 part of allocation sites or field accesses, from the
2395 hashtable of general accesses. SLOT represents general
2396 access that will be checked. DATA is a pointer to
2397 exclude_data structure. */
2400 exclude_from_accs (void **slot, void *data)
2402 struct access_site *acc = *(struct access_site **) slot;
2403 tree fn_decl = ((struct exclude_data *)data)->fn_decl;
2404 d_str str = ((struct exclude_data *)data)->str;
2406 if (is_part_of_malloc (acc->stmt, fn_decl)
2407 || is_part_of_field_access (acc->stmt, str))
2409 VEC_free (tree, heap, acc->vars);
2411 htab_clear_slot (str->accs, slot);
2416 /* Callback function for walk_tree called from collect_accesses_in_bb
2417 function. DATA is the statement which is analyzed. */
2420 get_stmt_accesses (tree *tp, int *walk_subtrees, void *data)
2422 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
2423 gimple stmt = (gimple) wi->info;
2429 switch (TREE_CODE (t))
2433 tree var = TREE_OPERAND(t, 0);
2434 tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var)));
2435 unsigned i = find_structure (type);
2437 if (i != VEC_length (structure, structures))
2441 fprintf (dump_file, "\nThe type ");
2442 print_generic_expr (dump_file, type, 0);
2443 fprintf (dump_file, " has bitfield.");
2445 remove_structure (i);
2452 tree ref = TREE_OPERAND (t, 0);
2453 tree field_decl = TREE_OPERAND (t, 1);
2456 if ((TREE_CODE (ref) == INDIRECT_REF
2457 || TREE_CODE (ref) == ARRAY_REF
2458 || TREE_CODE (ref) == VAR_DECL)
2459 && TREE_CODE (field_decl) == FIELD_DECL)
2461 tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref));
2462 unsigned i = find_structure (type);
2464 if (i != VEC_length (structure, structures))
2466 d_str str = VEC_index (structure, structures, i);
2467 struct field_entry * field =
2468 find_field_in_struct (str, field_decl);
2472 struct field_access_site *acc = make_field_acc_node ();
2479 acc->field_decl = field_decl;
2481 /* Check whether the access is of the form
2482 we can deal with. */
2483 if (!decompose_access (str->decl, acc))
2487 fprintf (dump_file, "\nThe type ");
2488 print_generic_expr (dump_file, type, 0);
2490 " has complicate access in statement ");
2491 print_gimple_stmt (dump_file, stmt, 0, 0);
2494 remove_structure (i);
2499 /* Increase count of field. */
2500 basic_block bb = gimple_bb (stmt);
2501 field->count += bb->count;
2503 /* Add stmt to the acc_sites of field. */
2504 add_field_acc_to_acc_sites (acc, field->acc_sites);
2515 tree cond = COND_EXPR_COND (t);
2517 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++)
2519 tree t = TREE_OPERAND (cond, i);
2522 walk_tree (&t, get_stmt_accesses, data, NULL);
2533 if (TREE_CODE (t) == SSA_NAME)
2534 t = SSA_NAME_VAR (t);
2536 i = find_structure (strip_type (get_type_of_var (t)));
2537 if (i != VEC_length (structure, structures))
2541 str = VEC_index (structure, structures, i);
2542 add_access_to_acc_sites (stmt, t, str->accs);
2555 /* Free structures hashtable. */
2558 free_structures (void)
2563 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2564 free_data_struct (str);
2566 VEC_free (structure, heap, structures);
2570 /* This function is a callback for traversal over new_var's hashtable.
2571 SLOT is a pointer to new_var. This function frees memory allocated
2572 for new_var and pointed by *SLOT. */
2575 free_new_var (void **slot, void *data ATTRIBUTE_UNUSED)
2577 new_var n_var = *(new_var *) slot;
2579 /* Free vector of new_vars. */
2580 VEC_free (tree, heap, n_var->new_vars);
2585 /* Free new_vars hashtable NEW_VARS_HTAB. */
2588 free_new_vars_htab (htab_t new_vars_htab)
2591 htab_traverse (new_vars_htab, free_new_var, NULL);
2592 htab_delete (new_vars_htab);
2593 new_vars_htab = NULL;
2596 /* This function creates new general and field accesses that appear in cfun. */
2599 create_new_accesses_for_func (void)
2603 FOR_EACH_BB_FN (bb, cfun)
2604 create_new_accesses_in_bb (bb);
2607 /* Create new allocation sites for the function represented by NODE. */
2610 create_new_alloc_sites_for_func (struct cgraph_node *node)
2612 fallocs_t fallocs = get_fallocs (node->decl);
2615 create_new_alloc_sites (fallocs, node->decl);
2618 /* For each local variable of structure type from the vector of structures
2619 this function generates new variable(s) to replace it. */
2622 create_new_local_vars (void)
2625 referenced_var_iterator rvi;
2627 new_local_vars = htab_create (num_referenced_vars,
2628 new_var_hash, new_var_eq, NULL);
2630 FOR_EACH_REFERENCED_VAR (var, rvi)
2632 if (!is_global_var (var))
2633 create_new_var (var, new_local_vars);
2637 htab_traverse (new_local_vars, finalize_new_vars_creation, NULL);
2638 dump_new_vars (new_local_vars);
2641 /* This function prints the SHIFT number of spaces to the DUMP_FILE. */
2644 print_shift (unsigned HOST_WIDE_INT shift)
2646 unsigned HOST_WIDE_INT sh = shift;
2649 fprintf (dump_file, " ");
2652 /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */
2655 update_fields_mapping (struct field_cluster *cluster, tree new_type,
2656 struct field_entry * fields, int num_fields)
2660 for (i = 0; i < num_fields; i++)
2661 if (TEST_BIT (cluster->fields_in_cluster, i))
2662 fields[i].field_mapping = new_type;
2665 /* This functions builds structure with FIELDS,
2666 NAME and attributes similar to ORIG_STRUCT.
2667 It returns the newly created structure. */
2670 build_basic_struct (tree fields, tree name, tree orig_struct)
2672 tree attributes = NULL_TREE;
2676 if (TYPE_ATTRIBUTES (orig_struct))
2677 attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct));
2678 ref = make_node (RECORD_TYPE);
2679 TYPE_SIZE (ref) = 0;
2680 decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE);
2681 TYPE_PACKED (ref) = TYPE_PACKED (orig_struct);
2682 for (x = fields; x; x = TREE_CHAIN (x))
2684 DECL_CONTEXT (x) = ref;
2685 DECL_PACKED (x) |= TYPE_PACKED (ref);
2687 TYPE_FIELDS (ref) = fields;
2689 TYPE_NAME (ref) = name;
2694 /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part
2695 of preparation for new structure building. NUM_FIELDS is a total
2696 number of fields in the structure. The function returns newly
2697 generated fields. */
2700 create_fields (struct field_cluster * cluster,
2701 struct field_entry * fields, int num_fields)
2704 tree new_types = NULL_TREE;
2705 tree last = NULL_TREE;
2707 for (i = 0; i < num_fields; i++)
2708 if (TEST_BIT (cluster->fields_in_cluster, i))
2710 tree new_decl = unshare_expr (fields[i].decl);
2713 new_types = new_decl;
2715 TREE_CHAIN (last) = new_decl;
2719 TREE_CHAIN (last) = NULL_TREE;
2724 /* This function creates a cluster name. The name is based on
2725 the original structure name, if it is present. It has a form:
2727 <original_struct_name>_sub.<CLUST_NUM>
2729 The original structure name is taken from the type of DECL.
2730 If an original structure name is not present, it's generated to be:
2734 The function returns identifier of the new cluster name. */
2737 gen_cluster_name (tree decl, int clust_num, int str_num)
2739 const char * orig_name = get_type_name (decl);
2740 char * tmp_name = NULL;
2746 ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num);
2748 len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub");
2749 prefix = XALLOCAVEC (char, len + 1);
2750 memcpy (prefix, tmp_name ? tmp_name : orig_name,
2751 strlen (tmp_name ? tmp_name : orig_name));
2752 strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub");
2754 ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num);
2755 return get_identifier (new_name);
2758 /* This function checks whether the structure STR has bitfields.
2759 If yes, this structure type is added to UNSUITABLE_TYPES vector. */
2762 check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types)
2764 tree type = str->decl;
2767 for (i = 0; i < str->num_fields; i++)
2768 if (DECL_BIT_FIELD (str->fields[i].decl))
2770 add_unsuitable_type (unsuitable_types, type);
2773 fprintf (dump_file, "\nType ");
2774 print_generic_expr (dump_file, type, 0);
2775 fprintf (dump_file, "\nescapes due to bitfield ");
2776 print_generic_expr (dump_file, str->fields[i].decl, 0);
2782 /* This function adds to UNSUITABLE_TYPES those types that escape
2783 due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */
2786 exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types)
2791 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
2792 check_type_escape (str, unsuitable_types);
2795 /* If a structure type is a return type of any function,
2796 we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */
2799 exclude_returned_types (VEC (tree, heap) **unsuitable_types)
2801 struct cgraph_node *c_node;
2803 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2805 tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl));
2809 ret_t = strip_type (ret_t);
2810 if (TREE_CODE (ret_t) == RECORD_TYPE)
2812 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t));
2815 fprintf (dump_file, "\nThe type \"");
2816 print_generic_expr (dump_file, ret_t, 0);
2818 "\" is return type of function...Excluded.");
2825 /* This function looks for parameters of local functions
2826 which are of structure types, or derived from them (arrays
2827 of structures, pointers to structures, or their combinations).
2828 We are not handling peeling of such structures right now.
2829 The found structures types are added to UNSUITABLE_TYPES vector. */
2832 exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types)
2834 struct cgraph_node *c_node;
2836 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
2837 if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL)
2839 tree fn = c_node->decl;
2842 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg))
2844 tree type = TREE_TYPE (arg);
2846 type = strip_type (type);
2847 if (TREE_CODE (type) == RECORD_TYPE)
2849 add_unsuitable_type (unsuitable_types,
2850 TYPE_MAIN_VARIANT (type));
2853 fprintf (dump_file, "\nPointer to type \"");
2854 print_generic_expr (dump_file, type, 0);
2856 "\" is passed to local function...Excluded.");
2863 /* This function analyzes structure form of structures
2864 potential for transformation. If we are not capable to transform
2865 structure of some form, we remove it from the structures hashtable.
2866 Right now we cannot handle nested structs, when nesting is
2867 through any level of pointers or arrays.
2869 TBD: release these constrains in future.
2871 Note, that in this function we suppose that all structures
2872 in the program are members of the structures hashtable right now,
2873 without excluding escaping types. */
2876 check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types)
2880 for (i = 0; i < str->num_fields; i++)
2882 tree f_type = strip_type(TREE_TYPE (str->fields[i].decl));
2884 if (TREE_CODE (f_type) == RECORD_TYPE)
2886 add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type));
2887 add_unsuitable_type (unsuitable_types, str->decl);
2890 fprintf (dump_file, "\nType ");
2891 print_generic_expr (dump_file, f_type, 0);
2892 fprintf (dump_file, " is a field in the structure ");
2893 print_generic_expr (dump_file, str->decl, 0);
2894 fprintf (dump_file, ". Escaping...");
2900 /* This function adds a structure TYPE to the vector of structures,
2901 if it's not already there. */
2904 add_structure (tree type)
2906 struct data_structure node;
2910 type = TYPE_MAIN_VARIANT (type);
2912 i = find_structure (type);
2914 if (i != VEC_length (structure, structures))
2917 num_fields = fields_length (type);
2919 node.num_fields = num_fields;
2920 node.fields = get_fields (type, num_fields);
2921 node.struct_clustering = NULL;
2922 node.accs = htab_create (32, acc_hash, acc_eq, NULL);
2923 node.new_types = VEC_alloc (tree, heap, num_fields);
2926 VEC_safe_push (structure, heap, structures, &node);
2930 fprintf (dump_file, "\nAdding data structure \"");
2931 print_generic_expr (dump_file, type, 0);
2932 fprintf (dump_file, "\" to data_struct_list.");
2936 /* This function adds an allocation site to alloc_sites hashtable.
2937 The allocation site appears in STMT of function FN_DECL and
2938 allocates the structure represented by STR. */
2941 add_alloc_site (tree fn_decl, gimple stmt, d_str str)
2943 fallocs_t fallocs = NULL;
2944 alloc_site_t m_call;
2950 (fallocs_t) htab_find_with_hash (alloc_sites,
2951 fn_decl, htab_hash_pointer (fn_decl));
2957 fallocs = (fallocs_t)
2958 xmalloc (sizeof (struct func_alloc_sites));
2959 fallocs->func = fn_decl;
2960 fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1);
2961 slot = htab_find_slot_with_hash (alloc_sites, fn_decl,
2962 htab_hash_pointer (fn_decl), INSERT);
2965 VEC_safe_push (alloc_site_t, heap,
2966 fallocs->allocs, &m_call);
2970 fprintf (dump_file, "\nAdding stmt ");
2971 print_gimple_stmt (dump_file, stmt, 0, 0);
2972 fprintf (dump_file, " to list of mallocs.");
2976 /* This function returns true if the result of STMT, that contains a call
2977 to an allocation function, is cast to one of the structure types.
2978 STMT should be of the form: T.2 = <alloc_func> (T.1);
2979 If true, I_P contains an index of an allocated structure.
2980 Otherwise I_P contains the length of the vector of structures. */
2983 is_alloc_of_struct (gimple stmt, unsigned *i_p)
2989 final_stmt = get_final_alloc_stmt (stmt);
2994 /* final_stmt should be of the form:
2995 T.3 = (struct_type *) T.2; */
2997 if (gimple_code (final_stmt) != GIMPLE_ASSIGN)
3000 lhs = gimple_assign_lhs (final_stmt);
3002 type = get_type_of_var (lhs);
3007 if (!POINTER_TYPE_P (type)
3008 || TREE_CODE (strip_type (type)) != RECORD_TYPE)
3011 *i_p = find_structure (strip_type (type));
3013 if (*i_p == VEC_length (structure, structures))
3019 /* This function prints non-field and field accesses
3020 of the structure STR. */
3023 dump_accs (d_str str)
3027 fprintf (dump_file, "\nAccess sites of struct ");
3028 print_generic_expr (dump_file, str->decl, 0);
3030 for (i = 0; i < str->num_fields; i++)
3032 fprintf (dump_file, "\nAccess site of field ");
3033 print_generic_expr (dump_file, str->fields[i].decl, 0);
3034 dump_field_acc_sites (str->fields[i].acc_sites);
3035 fprintf (dump_file, ":\n");
3037 fprintf (dump_file, "\nGeneral access sites\n");
3038 dump_access_sites (str->accs);
3041 /* This function checks whether an access statement, pointed by SLOT,
3042 is a condition we are capable to transform. It returns false if not,
3043 setting bool *DATA to false. */
3046 safe_cond_expr_check (void **slot, void *data)
3048 struct access_site *acc = *(struct access_site **) slot;
3050 if (gimple_code (acc->stmt) == GIMPLE_COND
3051 && !is_safe_cond_expr (acc->stmt))
3055 fprintf (dump_file, "\nUnsafe conditional statement ");
3056 print_gimple_stmt (dump_file, acc->stmt, 0, 0);
3058 *(bool *) data = false;
3064 /* This function excludes statements that are part of allocation sites and
3065 field accesses from the hashtable of general accesses of the structure
3066 type STR. Only accesses that belong to the function represented by
3067 NODE are treated. */
3070 exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node)
3072 struct exclude_data dt;
3074 dt.fn_decl = node->decl;
3077 htab_traverse (dt.str->accs, exclude_from_accs, &dt);
3080 /* Collect accesses to the structure types that appear in basic block BB. */
3083 collect_accesses_in_bb (basic_block bb)
3085 gimple_stmt_iterator bsi;
3086 struct walk_stmt_info wi;
3088 memset (&wi, 0, sizeof (wi));
3090 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3092 gimple stmt = gsi_stmt (bsi);
3094 /* In asm stmt we cannot always track the arguments,
3095 so we just give up. */
3096 if (gimple_code (stmt) == GIMPLE_ASM)
3102 wi.info = (void *) stmt;
3103 walk_gimple_op (stmt, get_stmt_accesses, &wi);
3107 /* This function generates cluster substructure that contains FIELDS.
3108 The cluster added to the set of clusters of the structure STR. */
3111 gen_cluster (sbitmap fields, d_str str)
3113 struct field_cluster *crr_cluster = NULL;
3116 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3117 crr_cluster->sibling = str->struct_clustering;
3118 str->struct_clustering = crr_cluster;
3119 crr_cluster->fields_in_cluster = fields;
3122 /* This function peels a field with the index I from the structure DS. */
3125 peel_field (int i, d_str ds)
3127 struct field_cluster *crr_cluster = NULL;
3130 (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster));
3131 crr_cluster->sibling = ds->struct_clustering;
3132 ds->struct_clustering = crr_cluster;
3133 crr_cluster->fields_in_cluster =
3134 sbitmap_alloc ((unsigned int) ds->num_fields);
3135 sbitmap_zero (crr_cluster->fields_in_cluster);
3136 SET_BIT (crr_cluster->fields_in_cluster, i);
3139 /* This function calculates maximum field count in
3140 the structure STR. */
3143 get_max_field_count (d_str str)
3148 for (i = 0; i < str->num_fields; i++)
3149 if (str->fields[i].count > max)
3150 max = str->fields[i].count;
3155 /* Do struct-reorg transformation for individual function
3156 represented by NODE. All structure types relevant
3157 for this function are transformed. */
3160 do_reorg_for_func (struct cgraph_node *node)
3162 create_new_local_vars ();
3163 create_new_alloc_sites_for_func (node);
3164 create_new_accesses_for_func ();
3165 update_ssa (TODO_update_ssa);
3166 cleanup_tree_cfg ();
3168 /* Free auxiliary data representing local variables. */
3169 free_new_vars_htab (new_local_vars);
3172 /* Print structure TYPE, its name, if it exists, and body.
3173 INDENT defines the level of indentation (similar
3174 to the option -i of indent command). SHIFT parameter
3175 defines a number of spaces by which a structure will
3176 be shifted right. */
3179 dump_struct_type (tree type, unsigned HOST_WIDE_INT indent,
3180 unsigned HOST_WIDE_INT shift)
3182 const char *struct_name;
3185 if (!type || !dump_file)
3188 if (TREE_CODE (type) != RECORD_TYPE)
3190 print_generic_expr (dump_file, type, 0);
3194 print_shift (shift);
3195 struct_name = get_type_name (type);
3196 fprintf (dump_file, "struct ");
3198 fprintf (dump_file, "%s\n",struct_name);
3199 print_shift (shift);
3200 fprintf (dump_file, "{\n");
3202 for (field = TYPE_FIELDS (type); field;
3203 field = TREE_CHAIN (field))
3205 unsigned HOST_WIDE_INT s = indent;
3206 tree f_type = TREE_TYPE (field);
3208 print_shift (shift);
3210 fprintf (dump_file, " ");
3211 dump_struct_type (f_type, indent, shift + indent);
3212 fprintf(dump_file, " ");
3213 print_generic_expr (dump_file, field, 0);
3214 fprintf(dump_file, ";\n");
3216 print_shift (shift);
3217 fprintf (dump_file, "}\n");
3220 /* This function creates new structure types to replace original type,
3221 indicated by STR->decl. The names of the new structure types are
3222 derived from the original structure type. If the original structure
3223 type has no name, we assume that its name is 'struct.<STR_NUM>'. */
3226 create_new_type (d_str str, int *str_num)
3228 int cluster_num = 0;
3230 struct field_cluster *cluster = str->struct_clustering;
3233 tree name = gen_cluster_name (str->decl, cluster_num,
3239 fields = create_fields (cluster, str->fields,
3241 new_type = build_basic_struct (fields, name, str->decl);
3243 update_fields_mapping (cluster, new_type,
3244 str->fields, str->num_fields);
3246 VEC_safe_push (tree, heap, str->new_types, new_type);
3247 cluster = cluster->sibling;
3252 /* This function is a callback for alloc_sites hashtable
3253 traversal. SLOT is a pointer to fallocs_t.
3254 This function frees memory pointed by *SLOT. */
3257 free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED)
3259 fallocs_t fallocs = *(fallocs_t *) slot;
3261 VEC_free (alloc_site_t, heap, fallocs->allocs);
3266 /* Remove structures collected in UNSUITABLE_TYPES
3267 from structures vector. */
3270 remove_unsuitable_types (VEC (tree, heap) *unsuitable_types)
3276 for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++)
3277 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3278 if (is_equal_types (str->decl, type))
3280 remove_structure (i);
3285 /* Exclude structure types with bitfields.
3286 We would not want to interfere with other optimizations
3287 that can be done in this case. The structure types with
3288 bitfields are added to UNSUITABLE_TYPES vector. */
3291 exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types)
3296 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3297 check_bitfields (str, unsuitable_types);
3300 /* This function checks three types of escape. A structure type escapes:
3302 1. if it's a type of parameter of a local function.
3303 2. if it's a type of function return value.
3304 3. if it escapes as a result of ipa-type-escape analysis.
3306 The escaping structure types are added to UNSUITABLE_TYPES vector. */
3309 exclude_escaping_types (VEC (tree, heap) **unsuitable_types)
3311 exclude_types_passed_to_local_func (unsuitable_types);
3312 exclude_returned_types (unsuitable_types);
3313 exclude_escaping_types_1 (unsuitable_types);
3316 /* This function analyzes whether the form of
3317 structure is such that we are capable to transform it.
3318 Nested structures are checked here. Unsuitable structure
3319 types are added to UNSUITABLE_TYPE vector. */
3322 analyze_struct_form (VEC (tree, heap) **unsuitable_types)
3327 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3328 check_struct_form (str, unsuitable_types);
3331 /* This function looks for structure types instantiated in the program.
3332 The candidate types are added to the structures vector.
3333 Unsuitable types are collected into UNSUITABLE_TYPES vector. */
3336 build_data_structure (VEC (tree, heap) **unsuitable_types)
3340 struct varpool_node *current_varpool;
3341 struct cgraph_node *c_node;
3343 /* Check global variables. */
3344 FOR_EACH_STATIC_VARIABLE (current_varpool)
3346 var = current_varpool->decl;
3347 if (is_candidate (var, &type, unsuitable_types))
3348 add_structure (type);
3351 /* Now add structures that are types of function parameters and
3353 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3355 enum availability avail =
3356 cgraph_function_body_availability (c_node);
3358 /* We need AVAIL_AVAILABLE for main function. */
3359 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3361 struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl);
3363 for (var = DECL_ARGUMENTS (c_node->decl); var;
3364 var = TREE_CHAIN (var))
3365 if (is_candidate (var, &type, unsuitable_types))
3366 add_structure (type);
3368 /* Check function local variables. */
3369 for (var_list = fn->local_decls; var_list;
3370 var_list = TREE_CHAIN (var_list))
3372 var = TREE_VALUE (var_list);
3374 if (is_candidate (var, &type, unsuitable_types))
3375 add_structure (type);
3381 /* This function returns true if the program contains
3382 a call to user defined allocation function, or other
3383 functions that can interfere with struct-reorg optimizations. */
3386 program_redefines_malloc_p (void)
3388 struct cgraph_node *c_node;
3389 struct cgraph_node *c_node2;
3390 struct cgraph_edge *c_edge;
3394 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3396 fndecl = c_node->decl;
3398 for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee)
3400 c_node2 = c_edge->callee;
3401 fndecl2 = c_node2->decl;
3402 if (is_gimple_call (c_edge->call_stmt))
3404 const char * fname = get_name (fndecl2);
3406 if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC)
3407 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC)
3408 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC)
3409 && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA))
3412 /* Check that there is no __builtin_object_size,
3413 __builtin_offsetof, or realloc's in the program. */
3414 if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE
3415 || !strcmp (fname, "__builtin_offsetof")
3416 || !strcmp (fname, "realloc"))
3425 /* In this function we assume that an allocation statement
3427 var = (type_cast) malloc (size);
3429 is converted into the following set of statements:
3433 T.3 = (type_cast) T.2;
3436 In this function we collect into alloc_sites the allocation
3437 sites of variables of structure types that are present
3438 in structures vector. */
3441 collect_alloc_sites (void)
3443 struct cgraph_node *node;
3444 struct cgraph_edge *cs;
3446 for (node = cgraph_nodes; node; node = node->next)
3447 if (node->analyzed && node->decl)
3449 for (cs = node->callees; cs; cs = cs->next_callee)
3451 gimple stmt = cs->call_stmt;
3457 if (is_gimple_call (stmt)
3458 && (decl = gimple_call_fndecl (stmt))
3459 && gimple_call_lhs (stmt))
3463 if (is_alloc_of_struct (stmt, &i))
3465 /* We support only malloc now. */
3466 if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC)
3470 str = VEC_index (structure, structures, i);
3471 add_alloc_site (node->decl, stmt, str);
3478 "\nUnsupported allocation function ");
3479 print_gimple_stmt (dump_file, stmt, 0, 0);
3481 remove_structure (i);
3490 /* Print collected accesses. */
3493 dump_accesses (void)
3501 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3505 /* This function checks whether the accesses of structures in condition
3506 expressions are of the kind we are capable to transform.
3507 If not, such structures are removed from the vector of structures. */
3510 check_cond_exprs (void)
3516 while (VEC_iterate (structure, structures, i, str))
3521 htab_traverse (str->accs, safe_cond_expr_check, &safe_p);
3523 remove_structure (i);
3529 /* We exclude from non-field accesses of the structure
3530 all statements that will be treated as part of the structure
3531 allocation sites or field accesses. */
3534 exclude_alloc_and_field_accs (struct cgraph_node *node)
3539 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3540 exclude_alloc_and_field_accs_1 (str, node);
3543 /* This function collects accesses of the fields of the structures
3544 that appear at function FN. */
3547 collect_accesses_in_func (struct function *fn)
3554 /* Collect accesses for each basic blocks separately. */
3555 FOR_EACH_BB_FN (bb, fn)
3556 collect_accesses_in_bb (bb);
3559 /* This function summarizes counts of the fields into the structure count. */
3562 sum_counts (d_str str, gcov_type *hottest)
3567 for (i = 0; i < str->num_fields; i++)
3571 fprintf (dump_file, "\nCounter of field \"");
3572 print_generic_expr (dump_file, str->fields[i].decl, 0);
3573 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC,
3574 str->fields[i].count);
3576 str->count += str->fields[i].count;
3581 fprintf (dump_file, "\nCounter of struct \"");
3582 print_generic_expr (dump_file, str->decl, 0);
3583 fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count);
3586 if (str->count > *hottest)
3587 *hottest = str->count;
3590 /* This function peels the field into separate structure if it's
3591 sufficiently hot, i.e. if its count provides at least 90% of
3592 the maximum field count in the structure. */
3595 peel_hot_fields (d_str str)
3597 gcov_type max_field_count;
3598 sbitmap fields_left = sbitmap_alloc (str->num_fields);
3601 sbitmap_ones (fields_left);
3603 (gcov_type) (get_max_field_count (str)/100)*90;
3605 str->struct_clustering = NULL;
3607 for (i = 0; i < str->num_fields; i++)
3609 if (str->count >= max_field_count)
3611 RESET_BIT (fields_left, i);
3612 peel_field (i, str);
3616 i = sbitmap_first_set_bit (fields_left);
3618 gen_cluster (fields_left, str);
3620 sbitmap_free (fields_left);
3623 /* This function is a helper for do_reorg. It goes over
3624 functions in call graph and performs actual transformation
3630 struct cgraph_node *node;
3632 /* Initialize the default bitmap obstack. */
3633 bitmap_obstack_initialize (NULL);
3635 for (node = cgraph_nodes; node; node = node->next)
3636 if (node->analyzed && node->decl && !node->next_clone)
3638 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3639 current_function_decl = node->decl;
3641 fprintf (dump_file, "\nFunction to do reorg is %s: \n",
3642 (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl)));
3643 do_reorg_for_func (node);
3644 free_dominance_info (CDI_DOMINATORS);
3645 free_dominance_info (CDI_POST_DOMINATORS);
3646 current_function_decl = NULL;
3651 bitmap_obstack_release (NULL);
3654 /* This function creates new global struct variables.
3655 For each original variable, the set of new variables
3656 is created with the new structure types corresponding
3657 to the structure type of original variable.
3658 Only VAR_DECL variables are treated by this function. */
3661 create_new_global_vars (void)
3663 struct varpool_node *current_varpool;
3664 unsigned HOST_WIDE_INT i;
3665 unsigned HOST_WIDE_INT varpool_size = 0;
3667 for (i = 0; i < 2; i++)
3670 new_global_vars = htab_create (varpool_size,
3671 new_var_hash, new_var_eq, NULL);
3672 FOR_EACH_STATIC_VARIABLE(current_varpool)
3674 tree var_decl = current_varpool->decl;
3676 if (!var_decl || TREE_CODE (var_decl) != VAR_DECL)
3681 create_new_var (var_decl, new_global_vars);
3685 if (new_global_vars)
3686 htab_traverse (new_global_vars, update_varpool_with_new_var, NULL);
3689 /* Dump all new types generated by this optimization. */
3692 dump_new_types (void)
3701 fprintf (dump_file, "\nThe following are the new types generated by"
3702 " this optimization:\n");
3704 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3708 fprintf (dump_file, "\nFor type ");
3709 dump_struct_type (str->decl, 2, 0);
3710 fprintf (dump_file, "\nthe number of new types is %d\n",
3711 VEC_length (tree, str->new_types));
3713 for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++)
3714 dump_struct_type (type, 2, 0);
3718 /* This function creates new types to replace old structure types. */
3721 create_new_types (void)
3727 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3728 create_new_type (str, &str_num);
3731 /* Free allocation sites hashtable. */
3734 free_alloc_sites (void)
3737 htab_traverse (alloc_sites, free_falloc_sites, NULL);
3738 htab_delete (alloc_sites);
3742 /* This function collects structures potential
3743 for peeling transformation, and inserts
3744 them into structures hashtable. */
3747 collect_structures (void)
3749 VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32);
3751 structures = VEC_alloc (structure, heap, 32);
3753 /* If program contains user defined mallocs, we give up. */
3754 if (program_redefines_malloc_p ())
3757 /* Build data structures hashtable of all data structures
3759 build_data_structure (&unsuitable_types);
3761 /* This function analyzes whether the form of
3762 structure is such that we are capable to transform it.
3763 Nested structures are checked here. */
3764 analyze_struct_form (&unsuitable_types);
3766 /* This function excludes those structure types
3767 that escape compilation unit. */
3768 exclude_escaping_types (&unsuitable_types);
3770 /* We do not want to change data layout of the structures with bitfields. */
3771 exclude_types_with_bit_fields (&unsuitable_types);
3773 remove_unsuitable_types (unsuitable_types);
3774 VEC_free (tree, heap, unsuitable_types);
3777 /* Collect structure allocation sites. In case of arrays
3778 we have nothing to do. */
3781 collect_allocation_sites (void)
3783 alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL);
3784 collect_alloc_sites ();
3787 /* This function collects data accesses for the
3788 structures to be transformed. For each structure
3789 field it updates the count field in field_entry. */
3792 collect_data_accesses (void)
3794 struct cgraph_node *c_node;
3796 for (c_node = cgraph_nodes; c_node; c_node = c_node->next)
3798 enum availability avail = cgraph_function_body_availability (c_node);
3800 if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE)
3802 struct function *func = DECL_STRUCT_FUNCTION (c_node->decl);
3804 if (!c_node->next_clone)
3805 collect_accesses_in_func (func);
3806 exclude_alloc_and_field_accs (c_node);
3810 check_cond_exprs ();
3811 /* Print collected accesses. */
3815 /* We do not bother to transform cold structures.
3816 Coldness of the structure is defined relatively
3817 to the highest structure count among the structures
3818 to be transformed. It's triggered by the compiler parameter
3820 --param struct-reorg-cold-struct-ratio=<value>
3822 where <value> ranges from 0 to 100. Structures with count ratios
3823 that are less than this parameter are considered to be cold. */
3826 exclude_cold_structs (void)
3828 gcov_type hottest = 0;
3832 /* We summarize counts of fields of a structure into the structure count. */
3833 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3834 sum_counts (str, &hottest);
3836 /* Remove cold structures from structures vector. */
3838 while (VEC_iterate (structure, structures, i, str))
3839 if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO))
3843 fprintf (dump_file, "\nThe structure ");
3844 print_generic_expr (dump_file, str->decl, 0);
3845 fprintf (dump_file, " is cold.");
3847 remove_structure (i);
3853 /* This function decomposes original structure into substructures,
3862 for (i = 0; VEC_iterate (structure, structures, i, str); i++)
3863 peel_hot_fields (str);
3867 /* Do the actual transformation for each structure
3868 from the structures hashtable. */
3873 /* Check that there is a work to do. */
3874 if (!VEC_length (structure, structures))
3877 fprintf (dump_file, "\nNo structures to transform. Exiting...");
3884 fprintf (dump_file, "\nNumber of structures to transform is %d",
3885 VEC_length (structure, structures));
3889 /* Generate new types. */
3890 create_new_types ();
3893 /* Create new global variables. */
3894 create_new_global_vars ();
3895 dump_new_vars (new_global_vars);
3897 /* Decompose structures for each function separately. */
3900 /* Free auxiliary data collected for global variables. */
3901 free_new_vars_htab (new_global_vars);
3904 /* Free all auxiliary data used by this optimization. */
3907 free_data_structs (void)
3910 free_alloc_sites ();
3913 /* Perform structure decomposition (peeling). */
3916 reorg_structs (void)
3920 /* Collect structure types. */
3921 collect_structures ();
3923 /* Collect structure allocation sites. */
3924 collect_allocation_sites ();
3926 /* Collect structure accesses. */
3927 collect_data_accesses ();
3929 /* We transform only hot structures. */
3930 exclude_cold_structs ();
3933 /* Decompose structures into substructures, i.e. clusters. */
3937 /* Do the actual transformation for each structure
3938 from the structures hashtable. */
3941 /* Free all auxiliary data used by this optimization. */
3942 free_data_structs ();
3945 /* Struct-reorg optimization entry point function. */
3948 reorg_structs_drive (void)
3954 /* Struct-reorg optimization gate function. */
3957 struct_reorg_gate (void)
3959 return flag_ipa_struct_reorg
3960 && flag_whole_program
3964 struct simple_ipa_opt_pass pass_ipa_struct_reorg =
3968 "ipa_struct_reorg", /* name */
3969 struct_reorg_gate, /* gate */
3970 reorg_structs_drive, /* execute */
3973 0, /* static_pass_number */
3974 TV_INTEGRATION, /* tv_id */
3975 0, /* properties_required */
3976 0, /* properties_provided */
3977 0, /* properties_destroyed */
3978 TODO_verify_ssa, /* todo_flags_start */
3979 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */