]>
Commit | Line | Data |
---|---|---|
32154c89 | 1 | /* Struct-reorg optimization. |
6da7fc87 | 2 | Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
32154c89 OG |
3 | Contributed by Olga Golovanevsky <olga@il.ibm.com> |
4 | (Initial version of this code was developed | |
5 | by Caroline Tice and Mostafa Hagog.) | |
6 | ||
7 | This file is part of GCC. | |
8 | ||
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 | |
6da7fc87 | 11 | Software Foundation; either version 3, or (at your option) any later |
32154c89 OG |
12 | version. |
13 | ||
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 | |
17 | for more details. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
6da7fc87 NC |
20 | along with GCC; see the file COPYING3. If not see |
21 | <http://www.gnu.org/licenses/>. */ | |
32154c89 OG |
22 | |
23 | #include "config.h" | |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "tm.h" | |
27 | #include "ggc.h" | |
28 | #include "tree.h" | |
29 | #include "rtl.h" | |
726a989a | 30 | #include "gimple.h" |
32154c89 OG |
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" | |
36 | #include "hashtab.h" | |
32154c89 OG |
37 | #include "toplev.h" |
38 | #include "flags.h" | |
39 | #include "debug.h" | |
40 | #include "target.h" | |
41 | #include "cgraph.h" | |
42 | #include "diagnostic.h" | |
43 | #include "timevar.h" | |
44 | #include "params.h" | |
45 | #include "fibheap.h" | |
46 | #include "intl.h" | |
47 | #include "function.h" | |
48 | #include "basic-block.h" | |
49 | #include "tree-iterator.h" | |
50 | #include "tree-pass.h" | |
51 | #include "ipa-struct-reorg.h" | |
52 | #include "opts.h" | |
53 | #include "ipa-type-escape.h" | |
54 | #include "tree-dump.h" | |
726a989a | 55 | #include "gimple.h" |
32154c89 OG |
56 | |
57 | /* This optimization implements structure peeling. | |
58 | ||
59 | For example, given a structure type: | |
60 | typedef struct | |
61 | { | |
62 | int a; | |
63 | float b; | |
64 | int c; | |
65 | }str_t; | |
66 | ||
67 | it can be peeled into two structure types as follows: | |
68 | ||
69 | typedef struct and typedef struct | |
70 | { { | |
71 | int a; float b; | |
72 | int c; } str_t_1; | |
73 | }str_t_0; | |
74 | ||
75 | or can be fully peeled: | |
76 | ||
77 | typedef struct | |
78 | { | |
79 | int a; | |
80 | }str_t_0; | |
81 | ||
82 | typedef struct | |
83 | { | |
84 | float b; | |
85 | }str_t_1; | |
86 | ||
87 | typedef struct | |
88 | { | |
89 | int c; | |
90 | }str_t_2; | |
91 | ||
92 | When structure type is peeled all instances and their accesses | |
93 | in the program are updated accordingly. For example, if there is | |
94 | array of structures: | |
95 | ||
96 | str_t A[N]; | |
97 | ||
98 | and structure type str_t was peeled into two structures str_t_0 | |
99 | and str_t_1 as it was shown above, then array A will be replaced | |
100 | by two arrays as follows: | |
101 | ||
102 | str_t_0 A_0[N]; | |
103 | str_t_1 A_1[N]; | |
104 | ||
105 | The field access of field a of element i of array A: A[i].a will be | |
106 | replaced by an access to field a of element i of array A_0: A_0[i].a. | |
107 | ||
108 | This optimization also supports dynamically allocated arrays. | |
109 | If array of structures was allocated by malloc function: | |
110 | ||
111 | str_t * p = (str_t *) malloc (sizeof (str_t) * N) | |
112 | ||
113 | the allocation site will be replaced to reflect new structure types: | |
114 | ||
115 | str_t_0 * p_0 = (str_t_0 *) malloc (sizeof (str_t_0) * N) | |
116 | str_t_1 * p_1 = (str_t_1 *) malloc (sizeof (str_t_1) * N) | |
117 | ||
118 | The field access through the pointer p[i].a will be changed by p_0[i].a. | |
119 | ||
120 | The goal of structure peeling is to improve spatial locality. | |
121 | For example, if one of the fields of a structure is accessed frequently | |
122 | in the loop: | |
123 | ||
124 | for (i = 0; i < N; i++) | |
125 | { | |
126 | ... = A[i].a; | |
127 | } | |
128 | ||
129 | the allocation of field a of str_t contiguously in memory will | |
130 | increase the chances of fetching the field from cache. | |
131 | ||
132 | The analysis part of this optimization is based on the frequency of | |
133 | field accesses, which are collected all over the program. | |
134 | Then the fields with the frequencies that satisfy the following condition | |
135 | get peeled out of the structure: | |
136 | ||
137 | freq(f) > C * max_field_freq_in_struct | |
138 | ||
139 | where max_field_freq_in_struct is the maximum field frequency | |
140 | in the structure. C is a constant defining which portion of | |
141 | max_field_freq_in_struct the fields should have in order to be peeled. | |
142 | ||
143 | If profiling information is provided, it is used to calculate the | |
144 | frequency of field accesses. Otherwise, the structure is fully peeled. | |
145 | ||
146 | IPA type-escape analysis is used to determine when it is safe | |
147 | to peel a structure. | |
148 | ||
149 | The optimization is activated by flag -fipa-struct-reorg. */ | |
150 | ||
151 | /* New variables created by this optimization. | |
152 | When doing struct peeling, each variable of | |
153 | the original struct type will be replaced by | |
154 | the set of new variables corresponding to | |
155 | the new structure types. */ | |
156 | struct new_var_data { | |
157 | /* VAR_DECL for original struct type. */ | |
158 | tree orig_var; | |
159 | /* Vector of new variables. */ | |
160 | VEC(tree, heap) *new_vars; | |
161 | }; | |
162 | ||
163 | typedef struct new_var_data *new_var; | |
164 | typedef const struct new_var_data *const_new_var; | |
165 | ||
166 | /* This structure represents allocation site of the structure. */ | |
167 | typedef struct alloc_site | |
168 | { | |
726a989a | 169 | gimple stmt; |
32154c89 OG |
170 | d_str str; |
171 | } alloc_site_t; | |
172 | ||
173 | DEF_VEC_O (alloc_site_t); | |
174 | DEF_VEC_ALLOC_O (alloc_site_t, heap); | |
175 | ||
176 | /* Allocation sites that belong to the same function. */ | |
177 | struct func_alloc_sites | |
178 | { | |
179 | tree func; | |
180 | /* Vector of allocation sites for function. */ | |
181 | VEC (alloc_site_t, heap) *allocs; | |
182 | }; | |
183 | ||
184 | typedef struct func_alloc_sites *fallocs_t; | |
185 | typedef const struct func_alloc_sites *const_fallocs_t; | |
186 | ||
187 | /* All allocation sites in the program. */ | |
1525f2c3 | 188 | htab_t alloc_sites = NULL; |
32154c89 OG |
189 | |
190 | /* New global variables. Generated once for whole program. */ | |
191 | htab_t new_global_vars; | |
192 | ||
193 | /* New local variables. Generated per-function. */ | |
194 | htab_t new_local_vars; | |
195 | ||
196 | /* Vector of structures to be transformed. */ | |
197 | typedef struct data_structure structure; | |
198 | DEF_VEC_O (structure); | |
199 | DEF_VEC_ALLOC_O (structure, heap); | |
200 | VEC (structure, heap) *structures; | |
201 | ||
202 | /* Forward declarations. */ | |
203 | static bool is_equal_types (tree, tree); | |
204 | ||
205 | /* Strip structure TYPE from pointers and arrays. */ | |
206 | ||
207 | static inline tree | |
208 | strip_type (tree type) | |
209 | { | |
210 | gcc_assert (TYPE_P (type)); | |
211 | ||
212 | while (POINTER_TYPE_P (type) | |
213 | || TREE_CODE (type) == ARRAY_TYPE) | |
214 | type = TREE_TYPE (type); | |
215 | ||
216 | return type; | |
217 | } | |
218 | ||
219 | /* This function returns type of VAR. */ | |
220 | ||
221 | static inline tree | |
222 | get_type_of_var (tree var) | |
223 | { | |
224 | if (!var) | |
225 | return NULL; | |
b8698a0f | 226 | |
32154c89 OG |
227 | if (TREE_CODE (var) == PARM_DECL) |
228 | return DECL_ARG_TYPE (var); | |
b8698a0f | 229 | else |
32154c89 OG |
230 | return TREE_TYPE (var); |
231 | } | |
232 | ||
b8698a0f | 233 | /* Set of actions we do for each newly generated STMT. */ |
32154c89 OG |
234 | |
235 | static inline void | |
726a989a | 236 | finalize_stmt (gimple stmt) |
32154c89 OG |
237 | { |
238 | update_stmt (stmt); | |
239 | mark_symbols_for_renaming (stmt); | |
240 | } | |
241 | ||
242 | /* This function finalizes STMT and appends it to the list STMTS. */ | |
243 | ||
244 | static inline void | |
726a989a | 245 | finalize_stmt_and_append (gimple_seq *stmts, gimple stmt) |
32154c89 | 246 | { |
726a989a | 247 | gimple_seq_add_stmt (stmts, stmt); |
32154c89 OG |
248 | finalize_stmt (stmt); |
249 | } | |
250 | ||
b8698a0f L |
251 | /* Given structure type SRT_TYPE and field FIELD, |
252 | this function is looking for a field with the same name | |
32154c89 OG |
253 | and type as FIELD in STR_TYPE. It returns it if found, |
254 | or NULL_TREE otherwise. */ | |
255 | ||
256 | static tree | |
257 | find_field_in_struct_1 (tree str_type, tree field) | |
258 | { | |
259 | tree str_field; | |
260 | ||
a1c65695 JJ |
261 | if (!DECL_NAME (field)) |
262 | return NULL; | |
263 | ||
b8698a0f | 264 | for (str_field = TYPE_FIELDS (str_type); str_field; |
32154c89 OG |
265 | str_field = TREE_CHAIN (str_field)) |
266 | { | |
a1c65695 JJ |
267 | const char *str_field_name; |
268 | const char *field_name; | |
269 | ||
270 | if (!DECL_NAME (str_field)) | |
271 | continue; | |
32154c89 OG |
272 | |
273 | str_field_name = IDENTIFIER_POINTER (DECL_NAME (str_field)); | |
274 | field_name = IDENTIFIER_POINTER (DECL_NAME (field)); | |
a1c65695 | 275 | |
32154c89 OG |
276 | gcc_assert (str_field_name); |
277 | gcc_assert (field_name); | |
278 | ||
279 | if (!strcmp (str_field_name, field_name)) | |
280 | { | |
b8698a0f | 281 | /* Check field types. */ |
32154c89 | 282 | if (is_equal_types (TREE_TYPE (str_field), TREE_TYPE (field))) |
a1c65695 | 283 | return str_field; |
32154c89 OG |
284 | } |
285 | } | |
286 | ||
287 | return NULL_TREE; | |
288 | } | |
289 | ||
b8698a0f | 290 | /* Given a field declaration FIELD_DECL, this function |
32154c89 OG |
291 | returns corresponding field entry in structure STR. */ |
292 | ||
293 | static struct field_entry * | |
294 | find_field_in_struct (d_str str, tree field_decl) | |
295 | { | |
296 | int i; | |
b8698a0f | 297 | |
32154c89 OG |
298 | tree field = find_field_in_struct_1 (str->decl, field_decl); |
299 | ||
300 | for (i = 0; i < str->num_fields; i++) | |
301 | if (str->fields[i].decl == field) | |
302 | return &(str->fields[i]); | |
303 | ||
304 | return NULL; | |
305 | } | |
306 | ||
b8698a0f L |
307 | /* This function checks whether ARG is a result of multiplication |
308 | of some number by STRUCT_SIZE. If yes, the function returns true | |
32154c89 OG |
309 | and this number is filled into NUM. */ |
310 | ||
311 | static bool | |
312 | is_result_of_mult (tree arg, tree *num, tree struct_size) | |
313 | { | |
726a989a | 314 | gimple size_def_stmt = SSA_NAME_DEF_STMT (arg); |
32154c89 | 315 | |
fa10beec | 316 | /* If the allocation statement was of the form |
32154c89 OG |
317 | D.2229_10 = <alloc_func> (D.2228_9); |
318 | then size_def_stmt can be D.2228_9 = num.3_8 * 8; */ | |
319 | ||
726a989a | 320 | if (size_def_stmt && is_gimple_assign (size_def_stmt)) |
32154c89 | 321 | { |
726a989a | 322 | tree lhs = gimple_assign_lhs (size_def_stmt); |
32154c89 OG |
323 | |
324 | /* We expect temporary here. */ | |
b8698a0f | 325 | if (!is_gimple_reg (lhs)) |
32154c89 OG |
326 | return false; |
327 | ||
726a989a | 328 | if (gimple_assign_rhs_code (size_def_stmt) == MULT_EXPR) |
32154c89 | 329 | { |
726a989a RB |
330 | tree arg0 = gimple_assign_rhs1 (size_def_stmt); |
331 | tree arg1 = gimple_assign_rhs2 (size_def_stmt); | |
32154c89 OG |
332 | |
333 | if (operand_equal_p (arg0, struct_size, OEP_ONLY_CONST)) | |
334 | { | |
335 | *num = arg1; | |
336 | return true; | |
337 | } | |
338 | ||
339 | if (operand_equal_p (arg1, struct_size, OEP_ONLY_CONST)) | |
340 | { | |
341 | *num = arg0; | |
342 | return true; | |
343 | } | |
344 | } | |
345 | } | |
346 | ||
347 | *num = NULL_TREE; | |
348 | return false; | |
349 | } | |
350 | ||
351 | ||
352 | /* This function returns true if access ACC corresponds to the pattern | |
b8698a0f L |
353 | generated by compiler when an address of element i of an array |
354 | of structures STR_DECL (pointed by p) is calculated (p[i]). If this | |
32154c89 OG |
355 | pattern is recognized correctly, this function returns true |
356 | and fills missing fields in ACC. Otherwise it returns false. */ | |
357 | ||
358 | static bool | |
359 | decompose_indirect_ref_acc (tree str_decl, struct field_access_site *acc) | |
360 | { | |
361 | tree ref_var; | |
726a989a | 362 | tree struct_size, op0, op1; |
32154c89 | 363 | tree before_cast; |
726a989a | 364 | enum tree_code rhs_code; |
b8698a0f | 365 | |
32154c89 OG |
366 | ref_var = TREE_OPERAND (acc->ref, 0); |
367 | ||
368 | if (TREE_CODE (ref_var) != SSA_NAME) | |
369 | return false; | |
370 | ||
371 | acc->ref_def_stmt = SSA_NAME_DEF_STMT (ref_var); | |
372 | if (!(acc->ref_def_stmt) | |
726a989a | 373 | || (gimple_code (acc->ref_def_stmt) != GIMPLE_ASSIGN)) |
32154c89 OG |
374 | return false; |
375 | ||
726a989a | 376 | rhs_code = gimple_assign_rhs_code (acc->ref_def_stmt); |
32154c89 | 377 | |
726a989a RB |
378 | if (rhs_code != PLUS_EXPR |
379 | && rhs_code != MINUS_EXPR | |
380 | && rhs_code != POINTER_PLUS_EXPR) | |
32154c89 OG |
381 | return false; |
382 | ||
726a989a RB |
383 | op0 = gimple_assign_rhs1 (acc->ref_def_stmt); |
384 | op1 = gimple_assign_rhs2 (acc->ref_def_stmt); | |
32154c89 | 385 | |
b8698a0f L |
386 | if (!is_array_access_through_pointer_and_index (rhs_code, op0, op1, |
387 | &acc->base, &acc->offset, | |
32154c89 OG |
388 | &acc->cast_stmt)) |
389 | return false; | |
390 | ||
391 | if (acc->cast_stmt) | |
392 | before_cast = SINGLE_SSA_TREE_OPERAND (acc->cast_stmt, SSA_OP_USE); | |
393 | else | |
394 | before_cast = acc->offset; | |
395 | ||
396 | if (!before_cast) | |
397 | return false; | |
398 | ||
399 | ||
400 | if (SSA_NAME_IS_DEFAULT_DEF (before_cast)) | |
b8698a0f | 401 | return false; |
32154c89 OG |
402 | |
403 | struct_size = TYPE_SIZE_UNIT (str_decl); | |
404 | ||
405 | if (!is_result_of_mult (before_cast, &acc->num, struct_size)) | |
406 | return false; | |
407 | ||
408 | return true; | |
409 | } | |
410 | ||
411 | ||
b8698a0f | 412 | /* This function checks whether the access ACC of structure type STR |
fa10beec | 413 | is of the form suitable for transformation. If yes, it returns true. |
32154c89 OG |
414 | False otherwise. */ |
415 | ||
416 | static bool | |
417 | decompose_access (tree str_decl, struct field_access_site *acc) | |
418 | { | |
419 | gcc_assert (acc->ref); | |
420 | ||
421 | if (TREE_CODE (acc->ref) == INDIRECT_REF) | |
422 | return decompose_indirect_ref_acc (str_decl, acc); | |
423 | else if (TREE_CODE (acc->ref) == ARRAY_REF) | |
424 | return true; | |
425 | else if (TREE_CODE (acc->ref) == VAR_DECL) | |
426 | return true; | |
427 | ||
428 | return false; | |
429 | } | |
430 | ||
431 | /* This function creates empty field_access_site node. */ | |
432 | ||
433 | static inline struct field_access_site * | |
434 | make_field_acc_node (void) | |
435 | { | |
436 | int size = sizeof (struct field_access_site); | |
437 | ||
438 | return (struct field_access_site *) xcalloc (1, size); | |
439 | } | |
440 | ||
441 | /* This function returns the structure field access, defined by STMT, | |
fa10beec | 442 | if it is already in hashtable of function accesses F_ACCS. */ |
32154c89 OG |
443 | |
444 | static struct field_access_site * | |
726a989a | 445 | is_in_field_accs (gimple stmt, htab_t f_accs) |
32154c89 | 446 | { |
b8698a0f | 447 | return (struct field_access_site *) |
32154c89 OG |
448 | htab_find_with_hash (f_accs, stmt, htab_hash_pointer (stmt)); |
449 | } | |
450 | ||
b8698a0f | 451 | /* This function adds an access ACC to the hashtable |
32154c89 OG |
452 | F_ACCS of field accesses. */ |
453 | ||
454 | static void | |
b8698a0f | 455 | add_field_acc_to_acc_sites (struct field_access_site *acc, |
32154c89 OG |
456 | htab_t f_accs) |
457 | { | |
458 | void **slot; | |
b8698a0f | 459 | |
32154c89 OG |
460 | gcc_assert (!is_in_field_accs (acc->stmt, f_accs)); |
461 | slot = htab_find_slot_with_hash (f_accs, acc->stmt, | |
b8698a0f | 462 | htab_hash_pointer (acc->stmt), |
32154c89 | 463 | INSERT); |
b8698a0f | 464 | *slot = acc; |
32154c89 OG |
465 | } |
466 | ||
b8698a0f L |
467 | /* This function adds the VAR to vector of variables of |
468 | an access site defined by statement STMT. If access entry | |
469 | with statement STMT does not exist in hashtable of | |
470 | accesses ACCS, this function creates it. */ | |
32154c89 OG |
471 | |
472 | static void | |
726a989a | 473 | add_access_to_acc_sites (gimple stmt, tree var, htab_t accs) |
32154c89 OG |
474 | { |
475 | struct access_site *acc; | |
476 | ||
b8698a0f | 477 | acc = (struct access_site *) |
32154c89 OG |
478 | htab_find_with_hash (accs, stmt, htab_hash_pointer (stmt)); |
479 | ||
480 | if (!acc) | |
481 | { | |
482 | void **slot; | |
483 | ||
484 | acc = (struct access_site *) xmalloc (sizeof (struct access_site)); | |
485 | acc->stmt = stmt; | |
486 | acc->vars = VEC_alloc (tree, heap, 10); | |
487 | slot = htab_find_slot_with_hash (accs, stmt, | |
488 | htab_hash_pointer (stmt), INSERT); | |
489 | *slot = acc; | |
490 | ||
b8698a0f | 491 | } |
32154c89 OG |
492 | VEC_safe_push (tree, heap, acc->vars, var); |
493 | } | |
494 | ||
b8698a0f | 495 | /* This function adds NEW_DECL to function |
32154c89 OG |
496 | referenced vars, and marks it for renaming. */ |
497 | ||
498 | static void | |
499 | finalize_var_creation (tree new_decl) | |
500 | { | |
b8698a0f L |
501 | add_referenced_var (new_decl); |
502 | mark_sym_for_renaming (new_decl); | |
32154c89 OG |
503 | } |
504 | ||
505 | /* This function finalizes VAR creation if it is a global VAR_DECL. */ | |
506 | ||
507 | static void | |
508 | finalize_global_creation (tree var) | |
509 | { | |
510 | if (TREE_CODE (var) == VAR_DECL | |
511 | && is_global_var (var)) | |
512 | finalize_var_creation (var); | |
513 | } | |
514 | ||
515 | /* This function inserts NEW_DECL to varpool. */ | |
516 | ||
517 | static inline void | |
518 | insert_global_to_varpool (tree new_decl) | |
519 | { | |
520 | struct varpool_node *new_node; | |
521 | ||
522 | new_node = varpool_node (new_decl); | |
523 | notice_global_symbol (new_decl); | |
524 | varpool_mark_needed_node (new_node); | |
525 | varpool_finalize_decl (new_decl); | |
526 | } | |
527 | ||
b8698a0f L |
528 | /* This function finalizes the creation of new variables, |
529 | defined by *SLOT->new_vars. */ | |
32154c89 OG |
530 | |
531 | static int | |
532 | finalize_new_vars_creation (void **slot, void *data ATTRIBUTE_UNUSED) | |
533 | { | |
534 | new_var n_var = *(new_var *) slot; | |
535 | unsigned i; | |
536 | tree var; | |
537 | ||
538 | for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++) | |
539 | finalize_var_creation (var); | |
540 | return 1; | |
541 | } | |
542 | ||
32154c89 OG |
543 | /* This function looks for the variable of NEW_TYPE type, stored in VAR. |
544 | It returns it, if found, and NULL_TREE otherwise. */ | |
545 | ||
546 | static tree | |
547 | find_var_in_new_vars_vec (new_var var, tree new_type) | |
548 | { | |
549 | tree n_var; | |
550 | unsigned i; | |
551 | ||
552 | for (i = 0; VEC_iterate (tree, var->new_vars, i, n_var); i++) | |
553 | { | |
554 | tree type = strip_type(get_type_of_var (n_var)); | |
555 | gcc_assert (type); | |
b8698a0f | 556 | |
32154c89 OG |
557 | if (type == new_type) |
558 | return n_var; | |
559 | } | |
560 | ||
561 | return NULL_TREE; | |
562 | } | |
563 | ||
564 | /* This function returns new_var node, the orig_var of which is DECL. | |
b8698a0f | 565 | It looks for new_var's in NEW_VARS_HTAB. If not found, |
32154c89 OG |
566 | the function returns NULL. */ |
567 | ||
568 | static new_var | |
569 | is_in_new_vars_htab (tree decl, htab_t new_vars_htab) | |
570 | { | |
571 | return (new_var) htab_find_with_hash (new_vars_htab, decl, | |
572 | htab_hash_pointer (decl)); | |
573 | } | |
574 | ||
fa10beec | 575 | /* Given original variable ORIG_VAR, this function returns |
32154c89 OG |
576 | new variable corresponding to it of NEW_TYPE type. */ |
577 | ||
578 | static tree | |
579 | find_new_var_of_type (tree orig_var, tree new_type) | |
580 | { | |
581 | new_var var; | |
582 | gcc_assert (orig_var && new_type); | |
583 | ||
584 | if (TREE_CODE (orig_var) == SSA_NAME) | |
585 | orig_var = SSA_NAME_VAR (orig_var); | |
586 | ||
587 | var = is_in_new_vars_htab (orig_var, new_global_vars); | |
588 | if (!var) | |
589 | var = is_in_new_vars_htab (orig_var, new_local_vars); | |
590 | gcc_assert (var); | |
591 | return find_var_in_new_vars_vec (var, new_type); | |
592 | } | |
593 | ||
594 | /* This function generates stmt: | |
595 | res = NUM * sizeof(TYPE) and returns it. | |
596 | res is filled into RES. */ | |
597 | ||
726a989a | 598 | static gimple |
32154c89 OG |
599 | gen_size (tree num, tree type, tree *res) |
600 | { | |
601 | tree struct_size = TYPE_SIZE_UNIT (type); | |
602 | HOST_WIDE_INT struct_size_int = TREE_INT_CST_LOW (struct_size); | |
726a989a | 603 | gimple new_stmt; |
32154c89 OG |
604 | |
605 | *res = create_tmp_var (TREE_TYPE (num), NULL); | |
606 | ||
607 | if (*res) | |
608 | add_referenced_var (*res); | |
609 | ||
610 | if (exact_log2 (struct_size_int) == -1) | |
b158b5c6 AD |
611 | { |
612 | tree size = build_int_cst (TREE_TYPE (num), struct_size_int); | |
646bea10 RG |
613 | new_stmt = gimple_build_assign (*res, fold_build2 (MULT_EXPR, |
614 | TREE_TYPE (num), | |
615 | num, size)); | |
b158b5c6 | 616 | } |
32154c89 OG |
617 | else |
618 | { | |
619 | tree C = build_int_cst (TREE_TYPE (num), exact_log2 (struct_size_int)); | |
b8698a0f | 620 | |
646bea10 RG |
621 | new_stmt = gimple_build_assign (*res, fold_build2 (LSHIFT_EXPR, |
622 | TREE_TYPE (num), | |
623 | num, C)); | |
32154c89 OG |
624 | } |
625 | ||
626 | finalize_stmt (new_stmt); | |
627 | return new_stmt; | |
628 | } | |
629 | ||
b8698a0f L |
630 | /* This function generates and returns a statement, that cast variable |
631 | BEFORE_CAST to NEW_TYPE. The cast result variable is stored | |
32154c89 OG |
632 | into RES_P. ORIG_CAST_STMT is the original cast statement. */ |
633 | ||
726a989a RB |
634 | static gimple |
635 | gen_cast_stmt (tree before_cast, tree new_type, gimple orig_cast_stmt, | |
32154c89 OG |
636 | tree *res_p) |
637 | { | |
726a989a RB |
638 | tree lhs, new_lhs; |
639 | gimple new_stmt; | |
640 | ||
641 | lhs = gimple_assign_lhs (orig_cast_stmt); | |
32154c89 OG |
642 | new_lhs = find_new_var_of_type (lhs, new_type); |
643 | gcc_assert (new_lhs); | |
644 | ||
726a989a | 645 | new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_lhs, before_cast, 0); |
32154c89 OG |
646 | finalize_stmt (new_stmt); |
647 | *res_p = new_lhs; | |
648 | return new_stmt; | |
649 | } | |
650 | ||
651 | /* This function builds an edge between BB and E->dest and updates | |
652 | phi nodes of E->dest. It returns newly created edge. */ | |
653 | ||
654 | static edge | |
655 | make_edge_and_fix_phis_of_dest (basic_block bb, edge e) | |
656 | { | |
657 | edge new_e; | |
726a989a RB |
658 | tree arg; |
659 | gimple_stmt_iterator si; | |
b8698a0f | 660 | |
32154c89 OG |
661 | new_e = make_edge (bb, e->dest, e->flags); |
662 | ||
726a989a | 663 | for (si = gsi_start_phis (new_e->dest); !gsi_end_p (si); gsi_next (&si)) |
32154c89 | 664 | { |
726a989a | 665 | gimple phi = gsi_stmt (si); |
32154c89 | 666 | arg = PHI_ARG_DEF_FROM_EDGE (phi, e); |
f5045c96 | 667 | add_phi_arg (phi, arg, new_e, gimple_phi_arg_location_from_edge (phi, e)); |
32154c89 OG |
668 | } |
669 | ||
670 | return new_e; | |
671 | } | |
672 | ||
726a989a | 673 | /* This function inserts NEW_STMT before STMT. */ |
32154c89 OG |
674 | |
675 | static void | |
726a989a | 676 | insert_before_stmt (gimple stmt, gimple new_stmt) |
32154c89 | 677 | { |
726a989a | 678 | gimple_stmt_iterator bsi; |
32154c89 | 679 | |
726a989a | 680 | if (!stmt || !new_stmt) |
32154c89 OG |
681 | return; |
682 | ||
b8698a0f L |
683 | bsi = gsi_for_stmt (stmt); |
684 | gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT); | |
32154c89 OG |
685 | } |
686 | ||
687 | /* Insert NEW_STMTS after STMT. */ | |
688 | ||
689 | static void | |
726a989a | 690 | insert_seq_after_stmt (gimple stmt, gimple_seq new_stmts) |
32154c89 | 691 | { |
726a989a | 692 | gimple_stmt_iterator bsi; |
32154c89 OG |
693 | |
694 | if (!stmt || !new_stmts) | |
695 | return; | |
696 | ||
b8698a0f L |
697 | bsi = gsi_for_stmt (stmt); |
698 | gsi_insert_seq_after (&bsi, new_stmts, GSI_SAME_STMT); | |
726a989a RB |
699 | } |
700 | ||
701 | /* Insert NEW_STMT after STMT. */ | |
702 | ||
703 | static void | |
704 | insert_after_stmt (gimple stmt, gimple new_stmt) | |
705 | { | |
706 | gimple_stmt_iterator bsi; | |
707 | ||
708 | if (!stmt || !new_stmt) | |
709 | return; | |
710 | ||
b8698a0f L |
711 | bsi = gsi_for_stmt (stmt); |
712 | gsi_insert_after (&bsi, new_stmt, GSI_SAME_STMT); | |
32154c89 OG |
713 | } |
714 | ||
715 | /* This function returns vector of allocation sites | |
716 | that appear in function FN_DECL. */ | |
717 | ||
718 | static fallocs_t | |
719 | get_fallocs (tree fn_decl) | |
b8698a0f | 720 | { |
32154c89 OG |
721 | return (fallocs_t) htab_find_with_hash (alloc_sites, fn_decl, |
722 | htab_hash_pointer (fn_decl)); | |
723 | } | |
724 | ||
725 | /* If ALLOC_STMT is D.2225_7 = <alloc_func> (D.2224_6); | |
726 | and it is a part of allocation of a structure, | |
b8698a0f | 727 | then it is usually followed by a cast stmt |
32154c89 OG |
728 | p_8 = (struct str_t *) D.2225_7; |
729 | which is returned by this function. */ | |
730 | ||
726a989a RB |
731 | static gimple |
732 | get_final_alloc_stmt (gimple alloc_stmt) | |
32154c89 | 733 | { |
726a989a | 734 | gimple final_stmt; |
32154c89 OG |
735 | use_operand_p use_p; |
736 | tree alloc_res; | |
737 | ||
738 | if (!alloc_stmt) | |
739 | return NULL; | |
b8698a0f | 740 | |
726a989a | 741 | if (!is_gimple_call (alloc_stmt)) |
32154c89 OG |
742 | return NULL; |
743 | ||
726a989a | 744 | alloc_res = gimple_get_lhs (alloc_stmt); |
32154c89 OG |
745 | |
746 | if (TREE_CODE (alloc_res) != SSA_NAME) | |
747 | return NULL; | |
748 | ||
749 | if (!single_imm_use (alloc_res, &use_p, &final_stmt)) | |
750 | return NULL; | |
751 | else | |
752 | return final_stmt; | |
753 | } | |
754 | ||
b8698a0f | 755 | /* This function returns true if STMT is one of allocation |
32154c89 OG |
756 | sites of function FN_DECL. It returns false otherwise. */ |
757 | ||
758 | static bool | |
726a989a | 759 | is_part_of_malloc (gimple stmt, tree fn_decl) |
32154c89 OG |
760 | { |
761 | fallocs_t fallocs = get_fallocs (fn_decl); | |
b8698a0f | 762 | |
32154c89 OG |
763 | if (fallocs) |
764 | { | |
765 | alloc_site_t *call; | |
766 | unsigned i; | |
767 | ||
726a989a | 768 | for (i = 0; VEC_iterate (alloc_site_t, fallocs->allocs, i, call); i++) |
32154c89 OG |
769 | if (call->stmt == stmt |
770 | || get_final_alloc_stmt (call->stmt) == stmt) | |
771 | return true; | |
772 | } | |
773 | return false; | |
774 | } | |
775 | ||
776 | /* Auxiliary structure for a lookup over field accesses. */ | |
777 | struct find_stmt_data | |
778 | { | |
779 | bool found; | |
726a989a | 780 | gimple stmt; |
32154c89 OG |
781 | }; |
782 | ||
b8698a0f L |
783 | /* This function looks for DATA->stmt among |
784 | the statements involved in the field access, | |
32154c89 OG |
785 | defined by SLOT. It stops when it's found. */ |
786 | ||
787 | static int | |
788 | find_in_field_accs (void **slot, void *data) | |
789 | { | |
726a989a RB |
790 | struct field_access_site *f_acc = *(struct field_access_site **) slot; |
791 | gimple stmt = ((struct find_stmt_data *)data)->stmt; | |
32154c89 OG |
792 | |
793 | if (f_acc->stmt == stmt | |
794 | || f_acc->ref_def_stmt == stmt | |
795 | || f_acc->cast_stmt == stmt) | |
796 | { | |
797 | ((struct find_stmt_data *)data)->found = true; | |
798 | return 0; | |
799 | } | |
800 | else | |
801 | return 1; | |
802 | } | |
803 | ||
804 | /* This function checks whether STMT is part of field | |
805 | accesses of structure STR. It returns true, if found, | |
806 | and false otherwise. */ | |
807 | ||
808 | static bool | |
726a989a | 809 | is_part_of_field_access (gimple stmt, d_str str) |
32154c89 OG |
810 | { |
811 | int i; | |
812 | ||
813 | for (i = 0; i < str->num_fields; i++) | |
814 | { | |
815 | struct find_stmt_data data; | |
816 | data.found = false; | |
817 | data.stmt = stmt; | |
818 | ||
819 | if (str->fields[i].acc_sites) | |
820 | htab_traverse (str->fields[i].acc_sites, find_in_field_accs, &data); | |
821 | ||
822 | if (data.found) | |
823 | return true; | |
824 | } | |
825 | ||
826 | return false; | |
827 | } | |
828 | ||
829 | /* Auxiliary data for exclude_from_accs function. */ | |
830 | ||
831 | struct exclude_data | |
832 | { | |
833 | tree fn_decl; | |
834 | d_str str; | |
835 | }; | |
836 | ||
b8698a0f | 837 | /* This function returns component_ref with the BASE and |
32154c89 OG |
838 | field named FIELD_ID from structure TYPE. */ |
839 | ||
840 | static inline tree | |
841 | build_comp_ref (tree base, tree field_id, tree type) | |
842 | { | |
843 | tree field; | |
844 | bool found = false; | |
b8698a0f | 845 | |
32154c89 OG |
846 | |
847 | /* Find field of structure type with the same name as field_id. */ | |
848 | for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) | |
849 | { | |
850 | if (DECL_NAME (field) == field_id) | |
851 | { | |
852 | found = true; | |
853 | break; | |
854 | } | |
855 | } | |
856 | ||
857 | gcc_assert (found); | |
858 | ||
859 | return build3 (COMPONENT_REF, TREE_TYPE (field), base, field, NULL_TREE); | |
860 | } | |
861 | ||
862 | ||
b8698a0f | 863 | /* This struct represent data used for walk_tree |
32154c89 | 864 | called from function find_pos_in_stmt. |
b8698a0f | 865 | - ref is a tree to be found, |
32154c89 OG |
866 | - and pos is a pointer that points to ref in stmt. */ |
867 | struct ref_pos | |
868 | { | |
869 | tree *pos; | |
870 | tree ref; | |
eed8fcad | 871 | tree container; |
32154c89 OG |
872 | }; |
873 | ||
874 | ||
b8698a0f | 875 | /* This is a callback function for walk_tree, called from |
32154c89 OG |
876 | collect_accesses_in_bb function. DATA is a pointer to ref_pos structure. |
877 | When *TP is equal to DATA->ref, the walk_tree stops, | |
878 | and found position, equal to TP, is assigned to DATA->pos. */ | |
879 | ||
880 | static tree | |
881 | find_pos_in_stmt_1 (tree *tp, int *walk_subtrees, void * data) | |
882 | { | |
726a989a RB |
883 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; |
884 | struct ref_pos *r_pos = (struct ref_pos *) wi->info; | |
32154c89 OG |
885 | tree ref = r_pos->ref; |
886 | tree t = *tp; | |
887 | ||
5f5f0635 | 888 | if (t == ref || (TREE_CODE (t) == SSA_NAME && SSA_NAME_VAR (t) == ref)) |
32154c89 OG |
889 | { |
890 | r_pos->pos = tp; | |
891 | return t; | |
892 | } | |
893 | ||
eed8fcad | 894 | r_pos->container = t; |
b8698a0f | 895 | *walk_subtrees = 1; |
726a989a | 896 | return NULL_TREE; |
32154c89 OG |
897 | } |
898 | ||
899 | ||
900 | /* This function looks for the pointer of REF in STMT, | |
901 | It returns it, if found, and NULL otherwise. */ | |
902 | ||
903 | static tree * | |
eed8fcad | 904 | find_pos_in_stmt (gimple stmt, tree ref, struct ref_pos * r_pos) |
32154c89 | 905 | { |
726a989a | 906 | struct walk_stmt_info wi; |
32154c89 | 907 | |
eed8fcad OG |
908 | r_pos->ref = ref; |
909 | r_pos->pos = NULL; | |
910 | r_pos->container = NULL_TREE; | |
726a989a | 911 | memset (&wi, 0, sizeof (wi)); |
eed8fcad | 912 | wi.info = r_pos; |
726a989a | 913 | walk_gimple_op (stmt, find_pos_in_stmt_1, &wi); |
32154c89 | 914 | |
eed8fcad | 915 | return r_pos->pos; |
32154c89 OG |
916 | } |
917 | ||
b8698a0f | 918 | /* This structure is used to represent array |
32154c89 | 919 | or pointer-to wrappers of structure type. |
b8698a0f L |
920 | For example, if type1 is structure type, |
921 | then for type1 ** we generate two type_wrapper | |
922 | structures with wrap = 0 each one. | |
923 | It's used to unwind the original type up to | |
924 | structure type, replace it with the new structure type | |
32154c89 OG |
925 | and wrap it back in the opposite order. */ |
926 | ||
927 | typedef struct type_wrapper | |
928 | { | |
929 | /* 0 stand for pointer wrapper, and 1 for array wrapper. */ | |
930 | bool wrap; | |
931 | ||
932 | /* Relevant for arrays as domain or index. */ | |
b8698a0f | 933 | tree domain; |
32154c89 OG |
934 | }type_wrapper_t; |
935 | ||
936 | DEF_VEC_O (type_wrapper_t); | |
937 | DEF_VEC_ALLOC_O (type_wrapper_t, heap); | |
938 | ||
b8698a0f | 939 | /* This function replace field access ACC by the new |
32154c89 OG |
940 | field access of structure type NEW_TYPE. */ |
941 | ||
942 | static void | |
943 | replace_field_acc (struct field_access_site *acc, tree new_type) | |
944 | { | |
945 | tree ref_var = acc->ref; | |
946 | tree new_ref; | |
947 | tree lhs, rhs; | |
948 | tree *pos; | |
949 | tree new_acc; | |
950 | tree field_id = DECL_NAME (acc->field_decl); | |
951 | VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10); | |
32154c89 | 952 | type_wrapper_t *wr_p = NULL; |
eed8fcad | 953 | struct ref_pos r_pos; |
b8698a0f | 954 | |
32154c89 OG |
955 | while (TREE_CODE (ref_var) == INDIRECT_REF |
956 | || TREE_CODE (ref_var) == ARRAY_REF) | |
957 | { | |
8d66f742 ST |
958 | type_wrapper_t wr; |
959 | ||
32154c89 OG |
960 | if ( TREE_CODE (ref_var) == INDIRECT_REF) |
961 | { | |
962 | wr.wrap = 0; | |
963 | wr.domain = 0; | |
964 | } | |
8d66f742 | 965 | else |
32154c89 OG |
966 | { |
967 | wr.wrap = 1; | |
968 | wr.domain = TREE_OPERAND (ref_var, 1); | |
969 | } | |
970 | ||
971 | VEC_safe_push (type_wrapper_t, heap, wrapper, &wr); | |
972 | ref_var = TREE_OPERAND (ref_var, 0); | |
973 | } | |
974 | ||
975 | new_ref = find_new_var_of_type (ref_var, new_type); | |
976 | finalize_global_creation (new_ref); | |
977 | ||
978 | while (VEC_length (type_wrapper_t, wrapper) != 0) | |
979 | { | |
980 | tree type = TREE_TYPE (TREE_TYPE (new_ref)); | |
981 | ||
b8698a0f | 982 | wr_p = VEC_last (type_wrapper_t, wrapper); |
32154c89 | 983 | if (wr_p->wrap) /* Array. */ |
b8698a0f | 984 | new_ref = build4 (ARRAY_REF, type, new_ref, |
32154c89 OG |
985 | wr_p->domain, NULL_TREE, NULL_TREE); |
986 | else /* Pointer. */ | |
987 | new_ref = build1 (INDIRECT_REF, type, new_ref); | |
988 | VEC_pop (type_wrapper_t, wrapper); | |
989 | } | |
990 | ||
991 | new_acc = build_comp_ref (new_ref, field_id, new_type); | |
b8698a0f | 992 | VEC_free (type_wrapper_t, heap, wrapper); |
32154c89 | 993 | |
726a989a | 994 | if (is_gimple_assign (acc->stmt)) |
b8698a0f | 995 | { |
726a989a RB |
996 | lhs = gimple_assign_lhs (acc->stmt); |
997 | rhs = gimple_assign_rhs1 (acc->stmt); | |
998 | ||
32154c89 | 999 | if (lhs == acc->comp_ref) |
726a989a | 1000 | gimple_assign_set_lhs (acc->stmt, new_acc); |
32154c89 | 1001 | else if (rhs == acc->comp_ref) |
726a989a | 1002 | gimple_assign_set_rhs1 (acc->stmt, new_acc); |
32154c89 OG |
1003 | else |
1004 | { | |
eed8fcad | 1005 | pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos); |
32154c89 OG |
1006 | gcc_assert (pos); |
1007 | *pos = new_acc; | |
1008 | } | |
1009 | } | |
1010 | else | |
1011 | { | |
eed8fcad | 1012 | pos = find_pos_in_stmt (acc->stmt, acc->comp_ref, &r_pos); |
32154c89 OG |
1013 | gcc_assert (pos); |
1014 | *pos = new_acc; | |
1015 | } | |
b8698a0f | 1016 | |
32154c89 OG |
1017 | finalize_stmt (acc->stmt); |
1018 | } | |
1019 | ||
b8698a0f | 1020 | /* This function replace field access ACC by a new field access |
32154c89 OG |
1021 | of structure type NEW_TYPE. */ |
1022 | ||
1023 | static void | |
1024 | replace_field_access_stmt (struct field_access_site *acc, tree new_type) | |
1025 | { | |
1026 | ||
1027 | if (TREE_CODE (acc->ref) == INDIRECT_REF | |
1028 | ||TREE_CODE (acc->ref) == ARRAY_REF | |
1029 | ||TREE_CODE (acc->ref) == VAR_DECL) | |
1030 | replace_field_acc (acc, new_type); | |
1031 | else | |
1032 | gcc_unreachable (); | |
1033 | } | |
1034 | ||
b8698a0f L |
1035 | /* This function looks for d_str, represented by TYPE, in the structures |
1036 | vector. If found, it returns an index of found structure. Otherwise | |
32154c89 | 1037 | it returns a length of the structures vector. */ |
b8698a0f | 1038 | |
32154c89 OG |
1039 | static unsigned |
1040 | find_structure (tree type) | |
1041 | { | |
1042 | d_str str; | |
1043 | unsigned i; | |
1044 | ||
1045 | type = TYPE_MAIN_VARIANT (type); | |
1046 | ||
1047 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
1048 | if (is_equal_types (str->decl, type)) | |
1049 | return i; | |
1050 | ||
1051 | return VEC_length (structure, structures); | |
1052 | } | |
1053 | ||
1054 | /* In this function we create new statements that have the same | |
b8698a0f L |
1055 | form as ORIG_STMT, but of type NEW_TYPE. The statements |
1056 | treated by this function are simple assignments, | |
1057 | like assignments: p.8_7 = p; or statements with rhs of | |
32154c89 OG |
1058 | tree codes PLUS_EXPR and MINUS_EXPR. */ |
1059 | ||
726a989a RB |
1060 | static gimple |
1061 | create_base_plus_offset (gimple orig_stmt, tree new_type, tree offset) | |
32154c89 | 1062 | { |
726a989a RB |
1063 | tree lhs; |
1064 | tree new_lhs; | |
1065 | gimple new_stmt; | |
1066 | tree new_op0 = NULL_TREE, new_op1 = NULL_TREE; | |
32154c89 | 1067 | |
726a989a | 1068 | lhs = gimple_assign_lhs (orig_stmt); |
32154c89 OG |
1069 | |
1070 | gcc_assert (TREE_CODE (lhs) == VAR_DECL | |
1071 | || TREE_CODE (lhs) == SSA_NAME); | |
b8698a0f | 1072 | |
32154c89 OG |
1073 | new_lhs = find_new_var_of_type (lhs, new_type); |
1074 | gcc_assert (new_lhs); | |
1075 | finalize_var_creation (new_lhs); | |
1076 | ||
726a989a | 1077 | switch (gimple_assign_rhs_code (orig_stmt)) |
32154c89 OG |
1078 | { |
1079 | case PLUS_EXPR: | |
1080 | case MINUS_EXPR: | |
1081 | case POINTER_PLUS_EXPR: | |
1082 | { | |
726a989a RB |
1083 | tree op0 = gimple_assign_rhs1 (orig_stmt); |
1084 | tree op1 = gimple_assign_rhs2 (orig_stmt); | |
32154c89 OG |
1085 | unsigned str0, str1; |
1086 | unsigned length = VEC_length (structure, structures); | |
32154c89 | 1087 | |
b8698a0f L |
1088 | |
1089 | str0 = find_structure (strip_type (get_type_of_var (op0))); | |
32154c89 OG |
1090 | str1 = find_structure (strip_type (get_type_of_var (op1))); |
1091 | gcc_assert ((str0 != length) || (str1 != length)); | |
b8698a0f | 1092 | |
32154c89 OG |
1093 | if (str0 != length) |
1094 | new_op0 = find_new_var_of_type (op0, new_type); | |
1095 | if (str1 != length) | |
1096 | new_op1 = find_new_var_of_type (op1, new_type); | |
1097 | ||
1098 | if (!new_op0) | |
1099 | new_op0 = offset; | |
1100 | if (!new_op1) | |
1101 | new_op1 = offset; | |
32154c89 OG |
1102 | } |
1103 | break; | |
1104 | ||
1105 | default: | |
1106 | gcc_unreachable(); | |
1107 | } | |
b8698a0f | 1108 | |
726a989a RB |
1109 | new_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (orig_stmt), |
1110 | new_lhs, new_op0, new_op1); | |
1111 | finalize_stmt (new_stmt); | |
32154c89 OG |
1112 | |
1113 | return new_stmt; | |
1114 | } | |
1115 | ||
b8698a0f | 1116 | /* Given a field access F_ACC of the FIELD, this function |
32154c89 OG |
1117 | replaces it by the new field access. */ |
1118 | ||
1119 | static void | |
1120 | create_new_field_access (struct field_access_site *f_acc, | |
1121 | struct field_entry field) | |
1122 | { | |
1123 | tree new_type = field.field_mapping; | |
726a989a | 1124 | gimple new_stmt; |
32154c89 | 1125 | tree size_res; |
726a989a RB |
1126 | gimple mult_stmt; |
1127 | gimple cast_stmt; | |
32154c89 | 1128 | tree cast_res = NULL; |
b8698a0f | 1129 | |
32154c89 OG |
1130 | if (f_acc->num) |
1131 | { | |
1132 | mult_stmt = gen_size (f_acc->num, new_type, &size_res); | |
1133 | insert_before_stmt (f_acc->ref_def_stmt, mult_stmt); | |
1134 | } | |
1135 | ||
1136 | if (f_acc->cast_stmt) | |
1137 | { | |
b8698a0f | 1138 | cast_stmt = gen_cast_stmt (size_res, new_type, |
32154c89 OG |
1139 | f_acc->cast_stmt, &cast_res); |
1140 | insert_after_stmt (f_acc->cast_stmt, cast_stmt); | |
1141 | } | |
1142 | ||
1143 | if (f_acc->ref_def_stmt) | |
1144 | { | |
1145 | tree offset; | |
1146 | if (cast_res) | |
1147 | offset = cast_res; | |
1148 | else | |
1149 | offset = size_res; | |
1150 | ||
b8698a0f | 1151 | new_stmt = create_base_plus_offset (f_acc->ref_def_stmt, |
32154c89 OG |
1152 | new_type, offset); |
1153 | insert_after_stmt (f_acc->ref_def_stmt, new_stmt); | |
1154 | } | |
1155 | ||
1156 | /* In stmt D.2163_19 = D.2162_18->b; we replace variable | |
1157 | D.2162_18 by an appropriate variable of new_type type. */ | |
1158 | replace_field_access_stmt (f_acc, new_type); | |
1159 | } | |
1160 | ||
b8698a0f | 1161 | /* This function creates a new condition statement |
32154c89 | 1162 | corresponding to the original COND_STMT, adds new basic block |
b8698a0f | 1163 | and redirects condition edges. NEW_VAR is a new condition |
32154c89 OG |
1164 | variable located in the condition statement at the position POS. */ |
1165 | ||
1166 | static void | |
726a989a | 1167 | create_new_stmts_for_cond_expr_1 (tree new_var, gimple cond_stmt, unsigned pos) |
32154c89 | 1168 | { |
726a989a | 1169 | gimple new_stmt; |
32154c89 OG |
1170 | edge true_e = NULL, false_e = NULL; |
1171 | basic_block new_bb; | |
726a989a | 1172 | gimple_stmt_iterator si; |
32154c89 | 1173 | |
726a989a | 1174 | extract_true_false_edges_from_block (gimple_bb (cond_stmt), |
32154c89 OG |
1175 | &true_e, &false_e); |
1176 | ||
726a989a RB |
1177 | new_stmt = gimple_build_cond (gimple_cond_code (cond_stmt), |
1178 | pos == 0 ? new_var : gimple_cond_lhs (cond_stmt), | |
1179 | pos == 1 ? new_var : gimple_cond_rhs (cond_stmt), | |
1180 | NULL_TREE, | |
1181 | NULL_TREE); | |
32154c89 OG |
1182 | |
1183 | finalize_stmt (new_stmt); | |
1184 | ||
1185 | /* Create new basic block after bb. */ | |
726a989a | 1186 | new_bb = create_empty_bb (gimple_bb (cond_stmt)); |
32154c89 OG |
1187 | |
1188 | /* Add new condition stmt to the new_bb. */ | |
726a989a RB |
1189 | si = gsi_start_bb (new_bb); |
1190 | gsi_insert_after (&si, new_stmt, GSI_NEW_STMT); | |
32154c89 | 1191 | |
32154c89 OG |
1192 | /* Create false and true edges from new_bb. */ |
1193 | make_edge_and_fix_phis_of_dest (new_bb, true_e); | |
1194 | make_edge_and_fix_phis_of_dest (new_bb, false_e); | |
b8698a0f | 1195 | |
32154c89 | 1196 | /* Redirect one of original edges to point to new_bb. */ |
726a989a | 1197 | if (gimple_cond_code (cond_stmt) == NE_EXPR) |
32154c89 OG |
1198 | redirect_edge_succ (true_e, new_bb); |
1199 | else | |
1200 | redirect_edge_succ (false_e, new_bb); | |
1201 | } | |
1202 | ||
b8698a0f L |
1203 | /* This function creates new condition statements corresponding |
1204 | to original condition STMT, one for each new type, and | |
32154c89 OG |
1205 | recursively redirect edges to newly generated basic blocks. */ |
1206 | ||
1207 | static void | |
726a989a | 1208 | create_new_stmts_for_cond_expr (gimple stmt) |
32154c89 | 1209 | { |
32154c89 OG |
1210 | tree arg0, arg1, arg; |
1211 | unsigned str0, str1; | |
1212 | bool s0, s1; | |
1213 | d_str str; | |
1214 | tree type; | |
726a989a | 1215 | unsigned pos; |
32154c89 OG |
1216 | int i; |
1217 | unsigned length = VEC_length (structure, structures); | |
1218 | ||
726a989a RB |
1219 | gcc_assert (gimple_cond_code (stmt) == EQ_EXPR |
1220 | || gimple_cond_code (stmt) == NE_EXPR); | |
32154c89 | 1221 | |
726a989a RB |
1222 | arg0 = gimple_cond_lhs (stmt); |
1223 | arg1 = gimple_cond_rhs (stmt); | |
32154c89 OG |
1224 | |
1225 | str0 = find_structure (strip_type (get_type_of_var (arg0))); | |
1226 | str1 = find_structure (strip_type (get_type_of_var (arg1))); | |
1227 | ||
1228 | s0 = (str0 != length) ? true : false; | |
1229 | s1 = (str1 != length) ? true : false; | |
1230 | ||
bd91d743 OG |
1231 | gcc_assert (s0 || s1); |
1232 | /* For now we allow only comparison with 0 or NULL. */ | |
1233 | gcc_assert (integer_zerop (arg0) || integer_zerop (arg1)); | |
b8698a0f | 1234 | |
bd91d743 | 1235 | str = integer_zerop (arg0) ? |
b8698a0f | 1236 | VEC_index (structure, structures, str1): |
bd91d743 OG |
1237 | VEC_index (structure, structures, str0); |
1238 | arg = integer_zerop (arg0) ? arg1 : arg0; | |
1239 | pos = integer_zerop (arg0) ? 1 : 0; | |
b8698a0f | 1240 | |
32154c89 OG |
1241 | for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++) |
1242 | { | |
1243 | tree new_arg; | |
1244 | ||
1245 | new_arg = find_new_var_of_type (arg, type); | |
1246 | create_new_stmts_for_cond_expr_1 (new_arg, stmt, pos); | |
1247 | } | |
1248 | } | |
1249 | ||
eed8fcad | 1250 | /* This function looks for VAR in STMT, and replace it with NEW_VAR. |
b8698a0f | 1251 | If needed, it wraps NEW_VAR in pointers and indirect references |
eed8fcad OG |
1252 | before insertion. */ |
1253 | ||
1254 | static void | |
1255 | insert_new_var_in_stmt (gimple stmt, tree var, tree new_var) | |
1256 | { | |
1257 | struct ref_pos r_pos; | |
1258 | tree *pos; | |
1259 | ||
1260 | pos = find_pos_in_stmt (stmt, var, &r_pos); | |
1261 | gcc_assert (pos); | |
1262 | ||
1263 | while (r_pos.container && (TREE_CODE(r_pos.container) == INDIRECT_REF | |
1264 | || TREE_CODE(r_pos.container) == ADDR_EXPR)) | |
1265 | { | |
1266 | tree type = TREE_TYPE (TREE_TYPE (new_var)); | |
1267 | ||
b8698a0f | 1268 | if (TREE_CODE(r_pos.container) == INDIRECT_REF) |
eed8fcad OG |
1269 | new_var = build1 (INDIRECT_REF, type, new_var); |
1270 | else | |
1271 | new_var = build_fold_addr_expr (new_var); | |
1272 | pos = find_pos_in_stmt (stmt, r_pos.container, &r_pos); | |
1273 | } | |
b8698a0f | 1274 | |
eed8fcad OG |
1275 | *pos = new_var; |
1276 | } | |
1277 | ||
1278 | ||
32154c89 OG |
1279 | /* Create a new general access to replace original access ACC |
1280 | for structure type NEW_TYPE. */ | |
1281 | ||
726a989a | 1282 | static gimple |
32154c89 OG |
1283 | create_general_new_stmt (struct access_site *acc, tree new_type) |
1284 | { | |
726a989a | 1285 | gimple old_stmt = acc->stmt; |
32154c89 | 1286 | tree var; |
726a989a | 1287 | gimple new_stmt = gimple_copy (old_stmt); |
32154c89 OG |
1288 | unsigned i; |
1289 | ||
5006671f RG |
1290 | /* We are really building a new stmt, clear the virtual operands. */ |
1291 | if (gimple_has_mem_ops (new_stmt)) | |
1292 | { | |
1293 | gimple_set_vuse (new_stmt, NULL_TREE); | |
1294 | gimple_set_vdef (new_stmt, NULL_TREE); | |
1295 | } | |
1296 | ||
32154c89 OG |
1297 | for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++) |
1298 | { | |
32154c89 | 1299 | tree new_var = find_new_var_of_type (var, new_type); |
4e9b2e50 | 1300 | tree lhs, rhs = NULL_TREE; |
32154c89 OG |
1301 | |
1302 | gcc_assert (new_var); | |
1303 | finalize_var_creation (new_var); | |
1304 | ||
726a989a | 1305 | if (is_gimple_assign (new_stmt)) |
32154c89 | 1306 | { |
726a989a | 1307 | lhs = gimple_assign_lhs (new_stmt); |
b8698a0f | 1308 | |
32154c89 OG |
1309 | if (TREE_CODE (lhs) == SSA_NAME) |
1310 | lhs = SSA_NAME_VAR (lhs); | |
726a989a RB |
1311 | if (gimple_assign_rhs_code (new_stmt) == SSA_NAME) |
1312 | rhs = SSA_NAME_VAR (gimple_assign_rhs1 (new_stmt)); | |
32154c89 OG |
1313 | |
1314 | /* It can happen that rhs is a constructor. | |
1315 | Then we have to replace it to be of new_type. */ | |
726a989a | 1316 | if (gimple_assign_rhs_code (new_stmt) == CONSTRUCTOR) |
32154c89 OG |
1317 | { |
1318 | /* Dealing only with empty constructors right now. */ | |
b8698a0f | 1319 | gcc_assert (VEC_empty (constructor_elt, |
32154c89 OG |
1320 | CONSTRUCTOR_ELTS (rhs))); |
1321 | rhs = build_constructor (new_type, 0); | |
726a989a | 1322 | gimple_assign_set_rhs1 (new_stmt, rhs); |
32154c89 | 1323 | } |
b8698a0f | 1324 | |
32154c89 | 1325 | if (lhs == var) |
726a989a | 1326 | gimple_assign_set_lhs (new_stmt, new_var); |
32154c89 | 1327 | else if (rhs == var) |
726a989a | 1328 | gimple_assign_set_rhs1 (new_stmt, new_var); |
32154c89 | 1329 | else |
eed8fcad | 1330 | insert_new_var_in_stmt (new_stmt, var, new_var); |
32154c89 OG |
1331 | } |
1332 | else | |
eed8fcad | 1333 | insert_new_var_in_stmt (new_stmt, var, new_var); |
32154c89 OG |
1334 | } |
1335 | ||
1336 | finalize_stmt (new_stmt); | |
1337 | return new_stmt; | |
1338 | } | |
1339 | ||
1340 | /* For each new type in STR this function creates new general accesses | |
1341 | corresponding to the original access ACC. */ | |
1342 | ||
1343 | static void | |
1344 | create_new_stmts_for_general_acc (struct access_site *acc, d_str str) | |
1345 | { | |
1346 | tree type; | |
726a989a | 1347 | gimple stmt = acc->stmt; |
32154c89 OG |
1348 | unsigned i; |
1349 | ||
1350 | for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++) | |
1351 | { | |
726a989a | 1352 | gimple new_stmt; |
32154c89 OG |
1353 | |
1354 | new_stmt = create_general_new_stmt (acc, type); | |
1355 | insert_after_stmt (stmt, new_stmt); | |
1356 | } | |
1357 | } | |
1358 | ||
b8698a0f | 1359 | /* This function creates a new general access of structure STR |
32154c89 OG |
1360 | to replace the access ACC. */ |
1361 | ||
1362 | static void | |
1363 | create_new_general_access (struct access_site *acc, d_str str) | |
1364 | { | |
726a989a RB |
1365 | gimple stmt = acc->stmt; |
1366 | switch (gimple_code (stmt)) | |
32154c89 | 1367 | { |
726a989a | 1368 | case GIMPLE_COND: |
32154c89 OG |
1369 | create_new_stmts_for_cond_expr (stmt); |
1370 | break; | |
1371 | ||
1372 | default: | |
1373 | create_new_stmts_for_general_acc (acc, str); | |
1374 | } | |
1375 | } | |
1376 | ||
1377 | /* Auxiliary data for creation of accesses. */ | |
1378 | struct create_acc_data | |
1379 | { | |
1380 | basic_block bb; | |
1381 | d_str str; | |
1382 | int field_index; | |
1383 | }; | |
1384 | ||
1385 | /* This function creates a new general access, defined by SLOT. | |
1386 | DATA is a pointer to create_acc_data structure. */ | |
1387 | ||
1388 | static int | |
1389 | create_new_acc (void **slot, void *data) | |
1390 | { | |
1391 | struct access_site *acc = *(struct access_site **) slot; | |
1392 | basic_block bb = ((struct create_acc_data *)data)->bb; | |
1393 | d_str str = ((struct create_acc_data *)data)->str; | |
1394 | ||
726a989a | 1395 | if (gimple_bb (acc->stmt) == bb) |
32154c89 OG |
1396 | create_new_general_access (acc, str); |
1397 | return 1; | |
1398 | } | |
1399 | ||
1400 | /* This function creates a new field access, defined by SLOT. | |
1401 | DATA is a pointer to create_acc_data structure. */ | |
1402 | ||
1403 | static int | |
1404 | create_new_field_acc (void **slot, void *data) | |
1405 | { | |
1406 | struct field_access_site *f_acc = *(struct field_access_site **) slot; | |
1407 | basic_block bb = ((struct create_acc_data *)data)->bb; | |
1408 | d_str str = ((struct create_acc_data *)data)->str; | |
1409 | int i = ((struct create_acc_data *)data)->field_index; | |
1410 | ||
726a989a | 1411 | if (gimple_bb (f_acc->stmt) == bb) |
32154c89 OG |
1412 | create_new_field_access (f_acc, str->fields[i]); |
1413 | return 1; | |
1414 | } | |
1415 | ||
b8698a0f | 1416 | /* This function creates new accesses for the structure |
32154c89 OG |
1417 | type STR in basic block BB. */ |
1418 | ||
1419 | static void | |
1420 | create_new_accs_for_struct (d_str str, basic_block bb) | |
1421 | { | |
1422 | int i; | |
1423 | struct create_acc_data dt; | |
1424 | ||
1425 | dt.str = str; | |
1426 | dt.bb = bb; | |
1427 | dt.field_index = -1; | |
b8698a0f | 1428 | |
32154c89 OG |
1429 | for (i = 0; i < str->num_fields; i++) |
1430 | { | |
1431 | dt.field_index = i; | |
1432 | ||
1433 | if (str->fields[i].acc_sites) | |
b8698a0f | 1434 | htab_traverse (str->fields[i].acc_sites, |
32154c89 | 1435 | create_new_field_acc, &dt); |
b8698a0f | 1436 | } |
32154c89 OG |
1437 | if (str->accs) |
1438 | htab_traverse (str->accs, create_new_acc, &dt); | |
1439 | } | |
1440 | ||
b8698a0f L |
1441 | /* This function inserts new variables from new_var, |
1442 | defined by SLOT, into varpool. */ | |
32154c89 OG |
1443 | |
1444 | static int | |
1445 | update_varpool_with_new_var (void **slot, void *data ATTRIBUTE_UNUSED) | |
1446 | { | |
1447 | new_var n_var = *(new_var *) slot; | |
1448 | tree var; | |
1449 | unsigned i; | |
1450 | ||
1451 | for (i = 0; VEC_iterate (tree, n_var->new_vars, i, var); i++) | |
1452 | insert_global_to_varpool (var); | |
1453 | return 1; | |
1454 | } | |
1455 | ||
b8698a0f | 1456 | /* This function prints a field access site, defined by SLOT. */ |
32154c89 OG |
1457 | |
1458 | static int | |
1459 | dump_field_acc (void **slot, void *data ATTRIBUTE_UNUSED) | |
1460 | { | |
1461 | struct field_access_site *f_acc = | |
1462 | *(struct field_access_site **) slot; | |
1463 | ||
1464 | fprintf(dump_file, "\n"); | |
1465 | if (f_acc->stmt) | |
726a989a | 1466 | print_gimple_stmt (dump_file, f_acc->stmt, 0, 0); |
32154c89 | 1467 | if (f_acc->ref_def_stmt) |
726a989a | 1468 | print_gimple_stmt (dump_file, f_acc->ref_def_stmt, 0, 0); |
32154c89 | 1469 | if (f_acc->cast_stmt) |
726a989a | 1470 | print_gimple_stmt (dump_file, f_acc->cast_stmt, 0, 0); |
32154c89 OG |
1471 | return 1; |
1472 | } | |
1473 | ||
1474 | /* Print field accesses from hashtable F_ACCS. */ | |
1475 | ||
1476 | static void | |
1477 | dump_field_acc_sites (htab_t f_accs) | |
1478 | { | |
1479 | if (!dump_file) | |
1480 | return; | |
1481 | ||
1482 | if (f_accs) | |
1483 | htab_traverse (f_accs, dump_field_acc, NULL); | |
1484 | } | |
1485 | ||
1486 | /* Hash value for fallocs_t. */ | |
1487 | ||
1488 | static hashval_t | |
1489 | malloc_hash (const void *x) | |
1490 | { | |
1491 | return htab_hash_pointer (((const_fallocs_t)x)->func); | |
1492 | } | |
1493 | ||
b8698a0f | 1494 | /* This function returns nonzero if function of func_alloc_sites' X |
32154c89 OG |
1495 | is equal to Y. */ |
1496 | ||
1497 | static int | |
1498 | malloc_eq (const void *x, const void *y) | |
1499 | { | |
1500 | return ((const_fallocs_t)x)->func == (const_tree)y; | |
1501 | } | |
1502 | ||
1503 | /* This function is a callback for traversal over a structure accesses. | |
1504 | It frees an access represented by SLOT. */ | |
1505 | ||
1506 | static int | |
1507 | free_accs (void **slot, void *data ATTRIBUTE_UNUSED) | |
1508 | { | |
1509 | struct access_site * acc = *(struct access_site **) slot; | |
1510 | ||
1511 | VEC_free (tree, heap, acc->vars); | |
1512 | free (acc); | |
1513 | return 1; | |
1514 | } | |
1515 | ||
b8698a0f | 1516 | /* This is a callback function for traversal over field accesses. |
32154c89 OG |
1517 | It frees a field access represented by SLOT. */ |
1518 | ||
1519 | static int | |
1520 | free_field_accs (void **slot, void *data ATTRIBUTE_UNUSED) | |
1521 | { | |
1522 | struct field_access_site *f_acc = *(struct field_access_site **) slot; | |
1523 | ||
1524 | free (f_acc); | |
1525 | return 1; | |
1526 | } | |
1527 | ||
b8698a0f | 1528 | /* This function inserts TYPE into vector of UNSUITABLE_TYPES, |
32154c89 OG |
1529 | if it is not there yet. */ |
1530 | ||
1531 | static void | |
1532 | add_unsuitable_type (VEC (tree, heap) **unsuitable_types, tree type) | |
1533 | { | |
1534 | unsigned i; | |
1535 | tree t; | |
1536 | ||
1537 | if (!type) | |
1538 | return; | |
1539 | ||
1540 | type = TYPE_MAIN_VARIANT (type); | |
1541 | ||
1542 | for (i = 0; VEC_iterate (tree, *unsuitable_types, i, t); i++) | |
1543 | if (is_equal_types (t, type)) | |
1544 | break; | |
b8698a0f | 1545 | |
32154c89 OG |
1546 | if (i == VEC_length (tree, *unsuitable_types)) |
1547 | VEC_safe_push (tree, heap, *unsuitable_types, type); | |
1548 | } | |
1549 | ||
1550 | /* Given a type TYPE, this function returns the name of the type. */ | |
1551 | ||
1552 | static const char * | |
1553 | get_type_name (tree type) | |
1554 | { | |
1555 | if (! TYPE_NAME (type)) | |
1556 | return NULL; | |
1557 | ||
1558 | if (TREE_CODE (TYPE_NAME (type)) == IDENTIFIER_NODE) | |
1559 | return IDENTIFIER_POINTER (TYPE_NAME (type)); | |
1560 | else if (TREE_CODE (TYPE_NAME (type)) == TYPE_DECL | |
1561 | && DECL_NAME (TYPE_NAME (type))) | |
1562 | return IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type))); | |
1563 | else | |
1564 | return NULL; | |
1565 | } | |
1566 | ||
1567 | /* This function is a temporary hack to overcome the types problem. | |
1568 | When several compilation units are compiled together | |
b8698a0f | 1569 | with -combine, the TYPE_MAIN_VARIANT of the same type |
32154c89 OG |
1570 | can appear differently in different compilation units. |
1571 | Therefore this function first compares type names. | |
b8698a0f | 1572 | If there are no names, structure bodies are recursively |
32154c89 OG |
1573 | compared. */ |
1574 | ||
1575 | static bool | |
1576 | is_equal_types (tree type1, tree type2) | |
1577 | { | |
1578 | const char * name1,* name2; | |
1579 | ||
1580 | if ((!type1 && type2) | |
1581 | ||(!type2 && type1)) | |
1582 | return false; | |
1583 | ||
1584 | if (!type1 && !type2) | |
1585 | return true; | |
1586 | ||
1587 | if (TREE_CODE (type1) != TREE_CODE (type2)) | |
1588 | return false; | |
1589 | ||
1590 | if (type1 == type2) | |
1591 | return true; | |
1592 | ||
1593 | if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2)) | |
1594 | return true; | |
1595 | ||
1596 | name1 = get_type_name (type1); | |
1597 | name2 = get_type_name (type2); | |
b8698a0f | 1598 | |
32154c89 OG |
1599 | if (name1 && name2 && !strcmp (name1, name2)) |
1600 | return true; | |
1601 | ||
1602 | if (name1 && name2 && strcmp (name1, name2)) | |
1603 | return false; | |
b8698a0f | 1604 | |
32154c89 OG |
1605 | switch (TREE_CODE (type1)) |
1606 | { | |
1607 | case POINTER_TYPE: | |
1608 | case REFERENCE_TYPE: | |
1609 | { | |
1610 | return is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2)); | |
1611 | } | |
1612 | break; | |
1613 | ||
1614 | case RECORD_TYPE: | |
1615 | case UNION_TYPE: | |
1616 | case QUAL_UNION_TYPE: | |
1617 | case ENUMERAL_TYPE: | |
1618 | { | |
1619 | tree field1; | |
fa10beec | 1620 | /* Compare fields of structure. */ |
b8698a0f | 1621 | for (field1 = TYPE_FIELDS (type1); field1; |
32154c89 OG |
1622 | field1 = TREE_CHAIN (field1)) |
1623 | { | |
1624 | tree field2 = find_field_in_struct_1 (type2, field1); | |
1625 | if (!field2) | |
1626 | return false; | |
1627 | } | |
1628 | return true; | |
1629 | } | |
1630 | break; | |
1631 | ||
1632 | case INTEGER_TYPE: | |
1633 | { | |
1634 | if (TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2) | |
1635 | && TYPE_PRECISION (type1) == TYPE_PRECISION (type2)) | |
1636 | return true; | |
1637 | } | |
1638 | break; | |
1639 | ||
1640 | case ARRAY_TYPE: | |
1641 | { | |
1642 | tree d1, d2; | |
1643 | tree max1, min1, max2, min2; | |
1644 | ||
1645 | if (!is_equal_types (TREE_TYPE (type1), TREE_TYPE (type2))) | |
1646 | return false; | |
1647 | ||
1648 | d1 = TYPE_DOMAIN (type1); | |
1649 | d2 = TYPE_DOMAIN (type2); | |
1650 | ||
1651 | if (!d1 || !d2) | |
1652 | return false; | |
1653 | ||
1654 | max1 = TYPE_MAX_VALUE (d1); | |
1655 | max2 = TYPE_MAX_VALUE (d2); | |
1656 | min1 = TYPE_MIN_VALUE (d1); | |
1657 | min2 = TYPE_MIN_VALUE (d2); | |
1658 | ||
1659 | if (max1 && max2 && min1 && min2 | |
1660 | && TREE_CODE (max1) == TREE_CODE (max2) | |
1661 | && TREE_CODE (max1) == INTEGER_CST | |
1662 | && TREE_CODE (min1) == TREE_CODE (min2) | |
1663 | && TREE_CODE (min1) == INTEGER_CST | |
1664 | && tree_int_cst_equal (max1, max2) | |
1665 | && tree_int_cst_equal (min1, min2)) | |
1666 | return true; | |
1667 | } | |
1668 | break; | |
1669 | ||
1670 | default: | |
1671 | gcc_unreachable(); | |
1672 | } | |
1673 | ||
1674 | return false; | |
1675 | } | |
1676 | ||
1677 | /* This function free non-field accesses from hashtable ACCS. */ | |
1678 | ||
1679 | static void | |
1680 | free_accesses (htab_t accs) | |
1681 | { | |
1682 | if (accs) | |
b8698a0f | 1683 | htab_traverse (accs, free_accs, NULL); |
32154c89 OG |
1684 | htab_delete (accs); |
1685 | } | |
1686 | ||
1687 | /* This function free field accesses hashtable F_ACCS. */ | |
1688 | ||
1689 | static void | |
1690 | free_field_accesses (htab_t f_accs) | |
1691 | { | |
1692 | if (f_accs) | |
b8698a0f | 1693 | htab_traverse (f_accs, free_field_accs, NULL); |
32154c89 OG |
1694 | htab_delete (f_accs); |
1695 | } | |
1696 | ||
1697 | /* Update call graph with new edge generated by new MALLOC_STMT. | |
1698 | The edge origin is CONTEXT function. */ | |
1699 | ||
1700 | static void | |
726a989a | 1701 | update_cgraph_with_malloc_call (gimple malloc_stmt, tree context) |
32154c89 | 1702 | { |
32154c89 OG |
1703 | struct cgraph_node *src, *dest; |
1704 | tree malloc_fn_decl; | |
1705 | ||
1706 | if (!malloc_stmt) | |
1707 | return; | |
1708 | ||
726a989a | 1709 | malloc_fn_decl = gimple_call_fndecl (malloc_stmt); |
b8698a0f | 1710 | |
32154c89 OG |
1711 | src = cgraph_node (context); |
1712 | dest = cgraph_node (malloc_fn_decl); | |
b8698a0f | 1713 | cgraph_create_edge (src, dest, malloc_stmt, |
d1725344 JH |
1714 | gimple_bb (malloc_stmt)->count, |
1715 | compute_call_stmt_bb_frequency | |
1716 | (context, gimple_bb (malloc_stmt)), | |
1717 | gimple_bb (malloc_stmt)->loop_depth); | |
32154c89 OG |
1718 | } |
1719 | ||
b8698a0f | 1720 | /* This function generates set of statements required |
32154c89 OG |
1721 | to allocate number NUM of structures of type NEW_TYPE. |
1722 | The statements are stored in NEW_STMTS. The statement that contain | |
1723 | call to malloc is returned. MALLOC_STMT is an original call to malloc. */ | |
1724 | ||
726a989a RB |
1725 | static gimple |
1726 | create_new_malloc (gimple malloc_stmt, tree new_type, gimple_seq *new_stmts, | |
1727 | tree num) | |
32154c89 OG |
1728 | { |
1729 | tree new_malloc_size; | |
726a989a RB |
1730 | tree malloc_fn_decl; |
1731 | gimple new_stmt; | |
1732 | tree malloc_res; | |
1733 | gimple call_stmt, final_stmt; | |
32154c89 OG |
1734 | tree cast_res; |
1735 | ||
1736 | gcc_assert (num && malloc_stmt && new_type); | |
726a989a | 1737 | *new_stmts = gimple_seq_alloc (); |
32154c89 | 1738 | |
b8698a0f | 1739 | /* Generate argument to malloc as multiplication of num |
32154c89 OG |
1740 | and size of new_type. */ |
1741 | new_stmt = gen_size (num, new_type, &new_malloc_size); | |
726a989a | 1742 | gimple_seq_add_stmt (new_stmts, new_stmt); |
32154c89 OG |
1743 | |
1744 | /* Generate new call for malloc. */ | |
1b7af7b0 | 1745 | malloc_res = create_tmp_var (ptr_type_node, NULL); |
726a989a | 1746 | add_referenced_var (malloc_res); |
32154c89 | 1747 | |
726a989a | 1748 | malloc_fn_decl = gimple_call_fndecl (malloc_stmt); |
b8698a0f | 1749 | call_stmt = gimple_build_call (malloc_fn_decl, 1, new_malloc_size); |
726a989a | 1750 | gimple_call_set_lhs (call_stmt, malloc_res); |
32154c89 OG |
1751 | finalize_stmt_and_append (new_stmts, call_stmt); |
1752 | ||
1753 | /* Create new cast statement. */ | |
1754 | final_stmt = get_final_alloc_stmt (malloc_stmt); | |
1755 | gcc_assert (final_stmt); | |
1756 | new_stmt = gen_cast_stmt (malloc_res, new_type, final_stmt, &cast_res); | |
726a989a | 1757 | gimple_seq_add_stmt (new_stmts, new_stmt); |
b8698a0f L |
1758 | |
1759 | return call_stmt; | |
32154c89 OG |
1760 | } |
1761 | ||
b8698a0f L |
1762 | /* This function returns a tree representing |
1763 | the number of instances of structure STR_DECL allocated | |
fa10beec | 1764 | by allocation STMT. If new statements are generated, |
32154c89 OG |
1765 | they are filled into NEW_STMTS_P. */ |
1766 | ||
b8698a0f | 1767 | static tree |
726a989a RB |
1768 | gen_num_of_structs_in_malloc (gimple stmt, tree str_decl, |
1769 | gimple_seq *new_stmts_p) | |
32154c89 | 1770 | { |
32154c89 | 1771 | tree arg; |
32154c89 OG |
1772 | tree struct_size; |
1773 | HOST_WIDE_INT struct_size_int; | |
1774 | ||
1775 | if (!stmt) | |
1776 | return NULL_TREE; | |
1777 | ||
1778 | /* Get malloc argument. */ | |
726a989a | 1779 | if (!is_gimple_call (stmt)) |
32154c89 OG |
1780 | return NULL_TREE; |
1781 | ||
726a989a | 1782 | arg = gimple_call_arg (stmt, 0); |
32154c89 OG |
1783 | |
1784 | if (TREE_CODE (arg) != SSA_NAME | |
1785 | && !TREE_CONSTANT (arg)) | |
1786 | return NULL_TREE; | |
b8698a0f | 1787 | |
32154c89 OG |
1788 | struct_size = TYPE_SIZE_UNIT (str_decl); |
1789 | struct_size_int = TREE_INT_CST_LOW (struct_size); | |
b8698a0f | 1790 | |
32154c89 OG |
1791 | gcc_assert (struct_size); |
1792 | ||
1793 | if (TREE_CODE (arg) == SSA_NAME) | |
1794 | { | |
726a989a RB |
1795 | tree num; |
1796 | gimple div_stmt; | |
32154c89 OG |
1797 | |
1798 | if (is_result_of_mult (arg, &num, struct_size)) | |
b8698a0f | 1799 | return num; |
32154c89 OG |
1800 | |
1801 | num = create_tmp_var (integer_type_node, NULL); | |
1802 | ||
1803 | if (num) | |
1804 | add_referenced_var (num); | |
1805 | ||
1806 | if (exact_log2 (struct_size_int) == -1) | |
726a989a RB |
1807 | div_stmt = gimple_build_assign_with_ops (TRUNC_DIV_EXPR, num, arg, |
1808 | struct_size); | |
32154c89 OG |
1809 | else |
1810 | { | |
1811 | tree C = build_int_cst (integer_type_node, | |
b8698a0f | 1812 | exact_log2 (struct_size_int)); |
32154c89 | 1813 | |
b8698a0f | 1814 | div_stmt = gimple_build_assign_with_ops (RSHIFT_EXPR, num, arg, C); |
32154c89 | 1815 | } |
726a989a | 1816 | gimple_seq_add_stmt (new_stmts_p, div_stmt); |
32154c89 OG |
1817 | finalize_stmt (div_stmt); |
1818 | return num; | |
1819 | } | |
1820 | ||
1821 | if (CONSTANT_CLASS_P (arg) | |
b8698a0f | 1822 | && multiple_of_p (TREE_TYPE (struct_size), arg, struct_size)) |
32154c89 OG |
1823 | return int_const_binop (TRUNC_DIV_EXPR, arg, struct_size, 0); |
1824 | ||
b8698a0f | 1825 | return NULL_TREE; |
32154c89 OG |
1826 | } |
1827 | ||
1828 | /* This function is a callback for traversal on new_var's hashtable. | |
b8698a0f L |
1829 | SLOT is a pointer to new_var. This function prints to dump_file |
1830 | an original variable and all new variables from the new_var | |
1831 | pointed by *SLOT. */ | |
32154c89 OG |
1832 | |
1833 | static int | |
1834 | dump_new_var (void **slot, void *data ATTRIBUTE_UNUSED) | |
1835 | { | |
1836 | new_var n_var = *(new_var *) slot; | |
1837 | tree var_type; | |
1838 | tree var; | |
1839 | unsigned i; | |
1840 | ||
1841 | var_type = get_type_of_var (n_var->orig_var); | |
1842 | ||
1843 | fprintf (dump_file, "\nOrig var: "); | |
1844 | print_generic_expr (dump_file, n_var->orig_var, 0); | |
1845 | fprintf (dump_file, " of type "); | |
1846 | print_generic_expr (dump_file, var_type, 0); | |
1847 | fprintf (dump_file, "\n"); | |
1848 | ||
1849 | for (i = 0; | |
1850 | VEC_iterate (tree, n_var->new_vars, i, var); i++) | |
b8698a0f | 1851 | { |
32154c89 | 1852 | var_type = get_type_of_var (var); |
b8698a0f | 1853 | |
32154c89 OG |
1854 | fprintf (dump_file, " "); |
1855 | print_generic_expr (dump_file, var, 0); | |
1856 | fprintf (dump_file, " of type "); | |
1857 | print_generic_expr (dump_file, var_type, 0); | |
1858 | fprintf (dump_file, "\n"); | |
1859 | } | |
1860 | return 1; | |
1861 | } | |
1862 | ||
1863 | /* This function copies attributes form ORIG_DECL to NEW_DECL. */ | |
1864 | ||
b8698a0f | 1865 | static inline void |
32154c89 OG |
1866 | copy_decl_attributes (tree new_decl, tree orig_decl) |
1867 | { | |
1868 | ||
1869 | DECL_ARTIFICIAL (new_decl) = 1; | |
1870 | DECL_EXTERNAL (new_decl) = DECL_EXTERNAL (orig_decl); | |
1871 | TREE_STATIC (new_decl) = TREE_STATIC (orig_decl); | |
1872 | TREE_PUBLIC (new_decl) = TREE_PUBLIC (orig_decl); | |
1873 | TREE_USED (new_decl) = TREE_USED (orig_decl); | |
1874 | DECL_CONTEXT (new_decl) = DECL_CONTEXT (orig_decl); | |
1875 | TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (orig_decl); | |
1876 | TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (orig_decl); | |
b8698a0f | 1877 | |
32154c89 OG |
1878 | if (TREE_CODE (orig_decl) == VAR_DECL) |
1879 | { | |
1880 | TREE_READONLY (new_decl) = TREE_READONLY (orig_decl); | |
1881 | DECL_TLS_MODEL (new_decl) = DECL_TLS_MODEL (orig_decl); | |
1882 | } | |
1883 | } | |
1884 | ||
b8698a0f L |
1885 | /* This function wraps NEW_STR_TYPE in pointers or arrays wrapper |
1886 | the same way as a structure type is wrapped in DECL. | |
32154c89 OG |
1887 | It returns the generated type. */ |
1888 | ||
1889 | static inline tree | |
1890 | gen_struct_type (tree decl, tree new_str_type) | |
1891 | { | |
1892 | tree type_orig = get_type_of_var (decl); | |
1893 | tree new_type = new_str_type; | |
1894 | VEC (type_wrapper_t, heap) *wrapper = VEC_alloc (type_wrapper_t, heap, 10); | |
1895 | type_wrapper_t wr; | |
1896 | type_wrapper_t *wr_p; | |
b8698a0f | 1897 | |
32154c89 OG |
1898 | while (POINTER_TYPE_P (type_orig) |
1899 | || TREE_CODE (type_orig) == ARRAY_TYPE) | |
b8698a0f | 1900 | { |
32154c89 OG |
1901 | if (POINTER_TYPE_P (type_orig)) |
1902 | { | |
1903 | wr.wrap = 0; | |
1904 | wr.domain = NULL_TREE; | |
1905 | } | |
5be1c58c | 1906 | else |
32154c89 | 1907 | { |
5be1c58c | 1908 | gcc_assert (TREE_CODE (type_orig) == ARRAY_TYPE); |
32154c89 OG |
1909 | wr.wrap = 1; |
1910 | wr.domain = TYPE_DOMAIN (type_orig); | |
1911 | } | |
1912 | VEC_safe_push (type_wrapper_t, heap, wrapper, &wr); | |
1913 | type_orig = TREE_TYPE (type_orig); | |
1914 | } | |
1915 | ||
1916 | while (VEC_length (type_wrapper_t, wrapper) != 0) | |
1917 | { | |
b8698a0f | 1918 | wr_p = VEC_last (type_wrapper_t, wrapper); |
32154c89 OG |
1919 | |
1920 | if (wr_p->wrap) /* Array. */ | |
1921 | new_type = build_array_type (new_type, wr_p->domain); | |
1922 | else /* Pointer. */ | |
1923 | new_type = build_pointer_type (new_type); | |
b8698a0f | 1924 | |
32154c89 OG |
1925 | VEC_pop (type_wrapper_t, wrapper); |
1926 | } | |
1927 | ||
b8698a0f | 1928 | VEC_free (type_wrapper_t, heap, wrapper); |
32154c89 OG |
1929 | return new_type; |
1930 | } | |
1931 | ||
1932 | /* This function generates and returns new variable name based on | |
1933 | ORIG_DECL name, combined with index I. | |
1934 | The form of the new name is <orig_name>.<I> . */ | |
1935 | ||
1936 | static tree | |
1937 | gen_var_name (tree orig_decl, unsigned HOST_WIDE_INT i) | |
1938 | { | |
1939 | const char *old_name; | |
1940 | char *prefix; | |
1941 | char *new_name; | |
1942 | ||
1943 | if (!DECL_NAME (orig_decl) | |
1944 | || !IDENTIFIER_POINTER (DECL_NAME (orig_decl))) | |
1945 | return NULL; | |
1946 | ||
b8698a0f | 1947 | /* If the original variable has a name, create an |
32154c89 OG |
1948 | appropriate new name for the new variable. */ |
1949 | ||
1950 | old_name = IDENTIFIER_POINTER (DECL_NAME (orig_decl)); | |
d3bfe4de | 1951 | prefix = XALLOCAVEC (char, strlen (old_name) + 1); |
32154c89 OG |
1952 | strcpy (prefix, old_name); |
1953 | ASM_FORMAT_PRIVATE_NAME (new_name, prefix, i); | |
1954 | return get_identifier (new_name); | |
1955 | } | |
1956 | ||
1957 | /* This function adds NEW_NODE to hashtable of new_var's NEW_VARS_HTAB. */ | |
1958 | ||
1959 | static void | |
1960 | add_to_new_vars_htab (new_var new_node, htab_t new_vars_htab) | |
1961 | { | |
1962 | void **slot; | |
1963 | ||
1964 | slot = htab_find_slot_with_hash (new_vars_htab, new_node->orig_var, | |
b8698a0f | 1965 | htab_hash_pointer (new_node->orig_var), |
32154c89 OG |
1966 | INSERT); |
1967 | *slot = new_node; | |
1968 | } | |
1969 | ||
b8698a0f | 1970 | /* This function creates and returns new_var_data node |
32154c89 OG |
1971 | with empty new_vars and orig_var equal to VAR. */ |
1972 | ||
1973 | static new_var | |
1974 | create_new_var_node (tree var, d_str str) | |
1975 | { | |
1976 | new_var node; | |
1977 | ||
1978 | node = (new_var) xmalloc (sizeof (struct new_var_data)); | |
1979 | node->orig_var = var; | |
1980 | node->new_vars = VEC_alloc (tree, heap, VEC_length (tree, str->new_types)); | |
1981 | return node; | |
1982 | } | |
1983 | ||
1984 | /* Check whether the type of VAR is potential candidate for peeling. | |
1985 | Returns true if yes, false otherwise. If yes, TYPE_P will contain | |
1986 | candidate type. If VAR is initialized, the type of VAR will be added | |
1987 | to UNSUITABLE_TYPES. */ | |
1988 | ||
1989 | static bool | |
1990 | is_candidate (tree var, tree *type_p, VEC (tree, heap) **unsuitable_types) | |
1991 | { | |
1992 | tree type; | |
1993 | bool initialized = false; | |
1994 | ||
1995 | *type_p = NULL; | |
1996 | ||
1997 | if (!var) | |
1998 | return false; | |
1999 | ||
2000 | /* There is no support of initialized vars. */ | |
2001 | if (TREE_CODE (var) == VAR_DECL | |
2002 | && DECL_INITIAL (var) != NULL_TREE) | |
2003 | initialized = true; | |
b8698a0f | 2004 | |
32154c89 OG |
2005 | type = get_type_of_var (var); |
2006 | ||
2007 | if (type) | |
2008 | { | |
2009 | type = TYPE_MAIN_VARIANT (strip_type (type)); | |
2010 | if (TREE_CODE (type) != RECORD_TYPE) | |
b8698a0f | 2011 | return false; |
32154c89 OG |
2012 | else |
2013 | { | |
2014 | if (initialized && unsuitable_types && *unsuitable_types) | |
d9d90953 OG |
2015 | { |
2016 | if (dump_file) | |
2017 | { | |
2018 | fprintf (dump_file, "The type "); | |
2019 | print_generic_expr (dump_file, type, 0); | |
b8698a0f | 2020 | fprintf (dump_file, " is initialized...Excluded."); |
d9d90953 OG |
2021 | } |
2022 | add_unsuitable_type (unsuitable_types, type); | |
2023 | } | |
32154c89 OG |
2024 | *type_p = type; |
2025 | return true; | |
2026 | } | |
2027 | } | |
2028 | else | |
2029 | return false; | |
2030 | } | |
2031 | ||
2032 | /* Hash value for field_access_site. */ | |
2033 | ||
2034 | static hashval_t | |
2035 | field_acc_hash (const void *x) | |
2036 | { | |
2037 | return htab_hash_pointer (((const struct field_access_site *)x)->stmt); | |
2038 | } | |
2039 | ||
b8698a0f | 2040 | /* This function returns nonzero if stmt of field_access_site X |
32154c89 OG |
2041 | is equal to Y. */ |
2042 | ||
2043 | static int | |
2044 | field_acc_eq (const void *x, const void *y) | |
2045 | { | |
726a989a | 2046 | return ((const struct field_access_site *)x)->stmt == (const_gimple)y; |
32154c89 OG |
2047 | } |
2048 | ||
b8698a0f | 2049 | /* This function prints an access site, defined by SLOT. */ |
32154c89 OG |
2050 | |
2051 | static int | |
2052 | dump_acc (void **slot, void *data ATTRIBUTE_UNUSED) | |
2053 | { | |
2054 | struct access_site *acc = *(struct access_site **) slot; | |
2055 | tree var; | |
2056 | unsigned i; | |
2057 | ||
2058 | fprintf(dump_file, "\n"); | |
2059 | if (acc->stmt) | |
726a989a | 2060 | print_gimple_stmt (dump_file, acc->stmt, 0, 0); |
32154c89 OG |
2061 | fprintf(dump_file, " : "); |
2062 | ||
2063 | for (i = 0; VEC_iterate (tree, acc->vars, i, var); i++) | |
2064 | { | |
2065 | print_generic_expr (dump_file, var, 0); | |
b8698a0f | 2066 | fprintf(dump_file, ", "); |
32154c89 OG |
2067 | } |
2068 | return 1; | |
2069 | } | |
2070 | ||
fa10beec | 2071 | /* This function frees memory allocated for structure clusters, |
32154c89 OG |
2072 | starting from CLUSTER. */ |
2073 | ||
2074 | static void | |
2075 | free_struct_cluster (struct field_cluster* cluster) | |
2076 | { | |
2077 | if (cluster) | |
2078 | { | |
2079 | if (cluster->fields_in_cluster) | |
b8698a0f | 2080 | sbitmap_free (cluster->fields_in_cluster); |
32154c89 OG |
2081 | if (cluster->sibling) |
2082 | free_struct_cluster (cluster->sibling); | |
2083 | free (cluster); | |
2084 | } | |
2085 | } | |
2086 | ||
2087 | /* Free all allocated memory under the structure node pointed by D_NODE. */ | |
2088 | ||
2089 | static void | |
2090 | free_data_struct (d_str d_node) | |
2091 | { | |
2092 | int i; | |
2093 | ||
2094 | if (!d_node) | |
2095 | return; | |
b8698a0f | 2096 | |
32154c89 OG |
2097 | if (dump_file) |
2098 | { | |
2099 | fprintf (dump_file, "\nRemoving data structure \""); | |
b8698a0f | 2100 | print_generic_expr (dump_file, d_node->decl, 0); |
32154c89 OG |
2101 | fprintf (dump_file, "\" from data_struct_list."); |
2102 | } | |
2103 | ||
2104 | /* Free all space under d_node. */ | |
2105 | if (d_node->fields) | |
2106 | { | |
2107 | for (i = 0; i < d_node->num_fields; i++) | |
2108 | free_field_accesses (d_node->fields[i].acc_sites); | |
2109 | free (d_node->fields); | |
2110 | } | |
2111 | ||
2112 | if (d_node->accs) | |
2113 | free_accesses (d_node->accs); | |
2114 | ||
2115 | if (d_node->struct_clustering) | |
2116 | free_struct_cluster (d_node->struct_clustering); | |
2117 | ||
2118 | if (d_node->new_types) | |
2119 | VEC_free (tree, heap, d_node->new_types); | |
2120 | } | |
2121 | ||
2122 | /* This function creates new general and field accesses in BB. */ | |
2123 | ||
2124 | static void | |
2125 | create_new_accesses_in_bb (basic_block bb) | |
2126 | { | |
2127 | d_str str; | |
2128 | unsigned i; | |
2129 | ||
2130 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
2131 | create_new_accs_for_struct (str, bb); | |
2132 | } | |
2133 | ||
2134 | /* This function adds allocation sites for peeled structures. | |
2135 | M_DATA is vector of allocation sites of function CONTEXT. */ | |
2136 | ||
2137 | static void | |
2138 | create_new_alloc_sites (fallocs_t m_data, tree context) | |
2139 | { | |
2140 | alloc_site_t *call; | |
2141 | unsigned j; | |
b8698a0f | 2142 | |
726a989a | 2143 | for (j = 0; VEC_iterate (alloc_site_t, m_data->allocs, j, call); j++) |
32154c89 | 2144 | { |
726a989a | 2145 | gimple stmt = call->stmt; |
32154c89 OG |
2146 | d_str str = call->str; |
2147 | tree num; | |
726a989a RB |
2148 | gimple_seq new_stmts = NULL; |
2149 | gimple last_stmt = get_final_alloc_stmt (stmt); | |
32154c89 OG |
2150 | unsigned i; |
2151 | tree type; | |
2152 | ||
2153 | num = gen_num_of_structs_in_malloc (stmt, str->decl, &new_stmts); | |
2154 | if (new_stmts) | |
2155 | { | |
a291ed6d | 2156 | gimple last_stmt_tmp = gimple_seq_last_stmt (new_stmts); |
726a989a | 2157 | insert_seq_after_stmt (last_stmt, new_stmts); |
a291ed6d | 2158 | last_stmt = last_stmt_tmp; |
32154c89 | 2159 | } |
b8698a0f L |
2160 | |
2161 | /* Generate an allocation sites for each new structure type. */ | |
2162 | for (i = 0; VEC_iterate (tree, str->new_types, i, type); i++) | |
32154c89 | 2163 | { |
726a989a RB |
2164 | gimple new_malloc_stmt = NULL; |
2165 | gimple last_stmt_tmp = NULL; | |
32154c89 | 2166 | |
726a989a | 2167 | new_stmts = NULL; |
32154c89 | 2168 | new_malloc_stmt = create_new_malloc (stmt, type, &new_stmts, num); |
726a989a RB |
2169 | last_stmt_tmp = gimple_seq_last_stmt (new_stmts); |
2170 | insert_seq_after_stmt (last_stmt, new_stmts); | |
32154c89 OG |
2171 | update_cgraph_with_malloc_call (new_malloc_stmt, context); |
2172 | last_stmt = last_stmt_tmp; | |
2173 | } | |
2174 | } | |
2175 | } | |
2176 | ||
b8698a0f | 2177 | /* This function prints new variables from hashtable |
32154c89 OG |
2178 | NEW_VARS_HTAB to dump_file. */ |
2179 | ||
2180 | static void | |
2181 | dump_new_vars (htab_t new_vars_htab) | |
2182 | { | |
2183 | if (!dump_file) | |
2184 | return; | |
2185 | ||
2186 | if (new_vars_htab) | |
2187 | htab_traverse (new_vars_htab, dump_new_var, NULL); | |
2188 | } | |
2189 | ||
2190 | /* Given an original variable ORIG_DECL of structure type STR, | |
b8698a0f | 2191 | this function generates new variables of the types defined |
32154c89 OG |
2192 | by STR->new_type. Generated types are saved in new_var node NODE. |
2193 | ORIG_DECL should has VAR_DECL tree_code. */ | |
2194 | ||
2195 | static void | |
2196 | create_new_var_1 (tree orig_decl, d_str str, new_var node) | |
2197 | { | |
2198 | unsigned i; | |
2199 | tree type; | |
2200 | ||
b8698a0f | 2201 | for (i = 0; |
32154c89 OG |
2202 | VEC_iterate (tree, str->new_types, i, type); i++) |
2203 | { | |
2204 | tree new_decl = NULL; | |
2205 | tree new_name; | |
2206 | ||
2207 | new_name = gen_var_name (orig_decl, i); | |
b8698a0f | 2208 | type = gen_struct_type (orig_decl, type); |
32154c89 OG |
2209 | |
2210 | if (is_global_var (orig_decl)) | |
c2255bc4 | 2211 | new_decl = build_decl (DECL_SOURCE_LOCATION (orig_decl), |
b8698a0f | 2212 | VAR_DECL, new_name, type); |
32154c89 OG |
2213 | else |
2214 | { | |
2215 | const char *name = new_name ? IDENTIFIER_POINTER (new_name) : NULL; | |
b8698a0f | 2216 | new_decl = create_tmp_var (type, name); |
32154c89 | 2217 | } |
b8698a0f | 2218 | |
32154c89 OG |
2219 | copy_decl_attributes (new_decl, orig_decl); |
2220 | VEC_safe_push (tree, heap, node->new_vars, new_decl); | |
2221 | } | |
2222 | } | |
2223 | ||
b8698a0f L |
2224 | /* This function creates new variables to |
2225 | substitute the original variable VAR_DECL and adds | |
32154c89 OG |
2226 | them to the new_var's hashtable NEW_VARS_HTAB. */ |
2227 | ||
2228 | static void | |
2229 | create_new_var (tree var_decl, htab_t new_vars_htab) | |
2230 | { | |
2231 | new_var node; | |
2232 | d_str str; | |
2233 | tree type; | |
2234 | unsigned i; | |
2235 | ||
2236 | if (!var_decl || is_in_new_vars_htab (var_decl, new_vars_htab)) | |
2237 | return; | |
2238 | ||
2239 | if (!is_candidate (var_decl, &type, NULL)) | |
2240 | return; | |
b8698a0f | 2241 | |
32154c89 OG |
2242 | i = find_structure (type); |
2243 | if (i == VEC_length (structure, structures)) | |
2244 | return; | |
2245 | ||
2246 | str = VEC_index (structure, structures, i); | |
2247 | node = create_new_var_node (var_decl, str); | |
2248 | create_new_var_1 (var_decl, str, node); | |
2249 | add_to_new_vars_htab (node, new_vars_htab); | |
2250 | } | |
2251 | ||
2252 | /* Hash value for new_var. */ | |
2253 | ||
2254 | static hashval_t | |
2255 | new_var_hash (const void *x) | |
2256 | { | |
2257 | return htab_hash_pointer (((const_new_var)x)->orig_var); | |
2258 | } | |
2259 | ||
2260 | /* This function returns nonzero if orig_var of new_var X is equal to Y. */ | |
2261 | ||
2262 | static int | |
2263 | new_var_eq (const void *x, const void *y) | |
2264 | { | |
2265 | return ((const_new_var)x)->orig_var == (const_tree)y; | |
2266 | } | |
2267 | ||
b8698a0f L |
2268 | /* This function check whether a structure type represented by STR |
2269 | escapes due to ipa-type-escape analysis. If yes, this type is added | |
2270 | to UNSUITABLE_TYPES vector. */ | |
32154c89 OG |
2271 | |
2272 | static void | |
2273 | check_type_escape (d_str str, VEC (tree, heap) **unsuitable_types) | |
2274 | { | |
2275 | tree type = str->decl; | |
2276 | ||
2277 | if (!ipa_type_escape_type_contained_p (type)) | |
2278 | { | |
2279 | if (dump_file) | |
2280 | { | |
2281 | fprintf (dump_file, "\nEscaping type is "); | |
2282 | print_generic_expr (dump_file, type, 0); | |
2283 | } | |
2284 | add_unsuitable_type (unsuitable_types, type); | |
2285 | } | |
2286 | } | |
2287 | ||
2288 | /* Hash value for access_site. */ | |
2289 | ||
2290 | static hashval_t | |
2291 | acc_hash (const void *x) | |
2292 | { | |
2293 | return htab_hash_pointer (((const struct access_site *)x)->stmt); | |
2294 | } | |
2295 | ||
2296 | /* Return nonzero if stmt of access_site X is equal to Y. */ | |
2297 | ||
2298 | static int | |
2299 | acc_eq (const void *x, const void *y) | |
2300 | { | |
726a989a | 2301 | return ((const struct access_site *)x)->stmt == (const_gimple)y; |
32154c89 OG |
2302 | } |
2303 | ||
b8698a0f L |
2304 | /* Given a structure declaration STRUCT_DECL, and number of fields |
2305 | in the structure NUM_FIELDS, this function creates and returns | |
32154c89 OG |
2306 | corresponding field_entry's. */ |
2307 | ||
2308 | static struct field_entry * | |
2309 | get_fields (tree struct_decl, int num_fields) | |
2310 | { | |
2311 | struct field_entry *list; | |
2312 | tree t = TYPE_FIELDS (struct_decl); | |
2313 | int idx = 0; | |
2314 | ||
b8698a0f | 2315 | list = |
32154c89 OG |
2316 | (struct field_entry *) xmalloc (num_fields * sizeof (struct field_entry)); |
2317 | ||
2318 | for (idx = 0 ; t; t = TREE_CHAIN (t), idx++) | |
2319 | if (TREE_CODE (t) == FIELD_DECL) | |
2320 | { | |
2321 | list[idx].index = idx; | |
2322 | list[idx].decl = t; | |
b8698a0f | 2323 | list[idx].acc_sites = |
32154c89 OG |
2324 | htab_create (32, field_acc_hash, field_acc_eq, NULL); |
2325 | list[idx].count = 0; | |
2326 | list[idx].field_mapping = NULL_TREE; | |
2327 | } | |
2328 | ||
2329 | return list; | |
2330 | } | |
2331 | ||
2332 | /* Print non-field accesses from hashtable ACCS of structure. */ | |
2333 | ||
2334 | static void | |
2335 | dump_access_sites (htab_t accs) | |
2336 | { | |
2337 | if (!dump_file) | |
2338 | return; | |
2339 | ||
2340 | if (accs) | |
2341 | htab_traverse (accs, dump_acc, NULL); | |
2342 | } | |
2343 | ||
b8698a0f | 2344 | /* This function is a callback for alloc_sites hashtable |
1525f2c3 GO |
2345 | traversal. SLOT is a pointer to fallocs_t. This function |
2346 | removes all allocations of the structure defined by DATA. */ | |
2347 | ||
2348 | static int | |
2349 | remove_str_allocs_in_func (void **slot, void *data) | |
2350 | { | |
2351 | fallocs_t fallocs = *(fallocs_t *) slot; | |
2352 | unsigned i = 0; | |
2353 | alloc_site_t *call; | |
2354 | ||
2355 | while (VEC_iterate (alloc_site_t, fallocs->allocs, i, call)) | |
2356 | { | |
2357 | if (call->str == (d_str) data) | |
2358 | VEC_ordered_remove (alloc_site_t, fallocs->allocs, i); | |
2359 | else | |
2360 | i++; | |
2361 | } | |
2362 | ||
2363 | return 1; | |
2364 | } | |
2365 | ||
2366 | /* This function remove all entries corresponding to the STR structure | |
2367 | from alloc_sites hashtable. */ | |
2368 | ||
2369 | static void | |
2370 | remove_str_allocs (d_str str) | |
2371 | { | |
2372 | if (!str) | |
2373 | return; | |
2374 | ||
2375 | if (alloc_sites) | |
2376 | htab_traverse (alloc_sites, remove_str_allocs_in_func, str); | |
2377 | } | |
2378 | ||
32154c89 OG |
2379 | /* This function removes the structure with index I from structures vector. */ |
2380 | ||
b8698a0f | 2381 | static void |
32154c89 | 2382 | remove_structure (unsigned i) |
b8698a0f | 2383 | { |
32154c89 OG |
2384 | d_str str; |
2385 | ||
2386 | if (i >= VEC_length (structure, structures)) | |
2387 | return; | |
2388 | ||
1525f2c3 | 2389 | str = VEC_index (structure, structures, i); |
b8698a0f | 2390 | |
1525f2c3 GO |
2391 | /* Before removing the structure str, we have to remove its |
2392 | allocations from alloc_sites hashtable. */ | |
2393 | remove_str_allocs (str); | |
32154c89 OG |
2394 | free_data_struct (str); |
2395 | VEC_ordered_remove (structure, structures, i); | |
2396 | } | |
2397 | ||
2398 | /* Currently we support only EQ_EXPR or NE_EXPR conditions. | |
fa10beec | 2399 | COND_STMT is a condition statement to check. */ |
32154c89 OG |
2400 | |
2401 | static bool | |
726a989a | 2402 | is_safe_cond_expr (gimple cond_stmt) |
32154c89 | 2403 | { |
32154c89 OG |
2404 | tree arg0, arg1; |
2405 | unsigned str0, str1; | |
2406 | bool s0, s1; | |
2407 | unsigned length = VEC_length (structure, structures); | |
2408 | ||
726a989a RB |
2409 | if (gimple_cond_code (cond_stmt) != EQ_EXPR |
2410 | && gimple_cond_code (cond_stmt) != NE_EXPR) | |
32154c89 | 2411 | return false; |
b8698a0f | 2412 | |
726a989a RB |
2413 | arg0 = gimple_cond_lhs (cond_stmt); |
2414 | arg1 = gimple_cond_rhs (cond_stmt); | |
32154c89 OG |
2415 | |
2416 | str0 = find_structure (strip_type (get_type_of_var (arg0))); | |
2417 | str1 = find_structure (strip_type (get_type_of_var (arg1))); | |
2418 | ||
2419 | s0 = (str0 != length) ? true : false; | |
2420 | s1 = (str1 != length) ? true : false; | |
b8698a0f | 2421 | |
bd91d743 OG |
2422 | if (!s0 && !s1) |
2423 | return false; | |
32154c89 | 2424 | |
bd91d743 OG |
2425 | /* For now we allow only comparison with 0 or NULL. */ |
2426 | if (!integer_zerop (arg0) && !integer_zerop (arg1)) | |
32154c89 OG |
2427 | return false; |
2428 | ||
2429 | return true; | |
2430 | } | |
2431 | ||
b8698a0f | 2432 | /* This function excludes statements, that are |
32154c89 | 2433 | part of allocation sites or field accesses, from the |
b8698a0f L |
2434 | hashtable of general accesses. SLOT represents general |
2435 | access that will be checked. DATA is a pointer to | |
32154c89 OG |
2436 | exclude_data structure. */ |
2437 | ||
2438 | static int | |
2439 | exclude_from_accs (void **slot, void *data) | |
2440 | { | |
2441 | struct access_site *acc = *(struct access_site **) slot; | |
2442 | tree fn_decl = ((struct exclude_data *)data)->fn_decl; | |
2443 | d_str str = ((struct exclude_data *)data)->str; | |
2444 | ||
2445 | if (is_part_of_malloc (acc->stmt, fn_decl) | |
2446 | || is_part_of_field_access (acc->stmt, str)) | |
2447 | { | |
2448 | VEC_free (tree, heap, acc->vars); | |
2449 | free (acc); | |
2450 | htab_clear_slot (str->accs, slot); | |
2451 | } | |
2452 | return 1; | |
2453 | } | |
2454 | ||
b8698a0f | 2455 | /* Callback function for walk_tree called from collect_accesses_in_bb |
32154c89 OG |
2456 | function. DATA is the statement which is analyzed. */ |
2457 | ||
2458 | static tree | |
2459 | get_stmt_accesses (tree *tp, int *walk_subtrees, void *data) | |
2460 | { | |
726a989a RB |
2461 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; |
2462 | gimple stmt = (gimple) wi->info; | |
32154c89 OG |
2463 | tree t = *tp; |
2464 | ||
2465 | if (!t) | |
2466 | return NULL; | |
2467 | ||
2468 | switch (TREE_CODE (t)) | |
2469 | { | |
32154c89 OG |
2470 | case BIT_FIELD_REF: |
2471 | { | |
2472 | tree var = TREE_OPERAND(t, 0); | |
2473 | tree type = TYPE_MAIN_VARIANT (strip_type (get_type_of_var (var))); | |
2474 | unsigned i = find_structure (type); | |
2475 | ||
2476 | if (i != VEC_length (structure, structures)) | |
d9d90953 OG |
2477 | { |
2478 | if (dump_file) | |
2479 | { | |
2480 | fprintf (dump_file, "\nThe type "); | |
2481 | print_generic_expr (dump_file, type, 0); | |
2482 | fprintf (dump_file, " has bitfield."); | |
b8698a0f | 2483 | } |
d9d90953 OG |
2484 | remove_structure (i); |
2485 | } | |
32154c89 OG |
2486 | } |
2487 | break; | |
2488 | ||
2489 | case COMPONENT_REF: | |
2490 | { | |
2491 | tree ref = TREE_OPERAND (t, 0); | |
2492 | tree field_decl = TREE_OPERAND (t, 1); | |
2493 | ||
2494 | ||
2495 | if ((TREE_CODE (ref) == INDIRECT_REF | |
2496 | || TREE_CODE (ref) == ARRAY_REF | |
2497 | || TREE_CODE (ref) == VAR_DECL) | |
2498 | && TREE_CODE (field_decl) == FIELD_DECL) | |
2499 | { | |
2500 | tree type = TYPE_MAIN_VARIANT (TREE_TYPE (ref)); | |
2501 | unsigned i = find_structure (type); | |
2502 | ||
2503 | if (i != VEC_length (structure, structures)) | |
2504 | { | |
2505 | d_str str = VEC_index (structure, structures, i); | |
b8698a0f | 2506 | struct field_entry * field = |
32154c89 OG |
2507 | find_field_in_struct (str, field_decl); |
2508 | ||
2509 | if (field) | |
2510 | { | |
2511 | struct field_access_site *acc = make_field_acc_node (); | |
2512 | ||
2513 | gcc_assert (acc); | |
2514 | ||
2515 | acc->stmt = stmt; | |
2516 | acc->comp_ref = t; | |
2517 | acc->ref = ref; | |
2518 | acc->field_decl = field_decl; | |
2519 | ||
b8698a0f | 2520 | /* Check whether the access is of the form |
32154c89 OG |
2521 | we can deal with. */ |
2522 | if (!decompose_access (str->decl, acc)) | |
2523 | { | |
d9d90953 OG |
2524 | if (dump_file) |
2525 | { | |
2526 | fprintf (dump_file, "\nThe type "); | |
2527 | print_generic_expr (dump_file, type, 0); | |
b8698a0f | 2528 | fprintf (dump_file, |
d9d90953 | 2529 | " has complicate access in statement "); |
726a989a | 2530 | print_gimple_stmt (dump_file, stmt, 0, 0); |
d9d90953 | 2531 | } |
b8698a0f | 2532 | |
32154c89 OG |
2533 | remove_structure (i); |
2534 | free (acc); | |
2535 | } | |
2536 | else | |
2537 | { | |
2538 | /* Increase count of field. */ | |
726a989a | 2539 | basic_block bb = gimple_bb (stmt); |
32154c89 OG |
2540 | field->count += bb->count; |
2541 | ||
2542 | /* Add stmt to the acc_sites of field. */ | |
2543 | add_field_acc_to_acc_sites (acc, field->acc_sites); | |
2544 | } | |
2545 | *walk_subtrees = 0; | |
2546 | } | |
b8698a0f | 2547 | } |
32154c89 OG |
2548 | } |
2549 | } | |
2550 | break; | |
2551 | ||
32154c89 OG |
2552 | case COND_EXPR: |
2553 | { | |
2554 | tree cond = COND_EXPR_COND (t); | |
2555 | int i; | |
2556 | for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (cond)); i++) | |
2557 | { | |
2558 | tree t = TREE_OPERAND (cond, i); | |
2559 | ||
2560 | *walk_subtrees = 1; | |
2561 | walk_tree (&t, get_stmt_accesses, data, NULL); | |
2562 | } | |
b8698a0f | 2563 | *walk_subtrees = 0; |
32154c89 OG |
2564 | } |
2565 | break; | |
2566 | ||
2567 | case VAR_DECL: | |
2568 | case SSA_NAME: | |
2569 | { | |
2570 | unsigned i; | |
2571 | ||
2572 | if (TREE_CODE (t) == SSA_NAME) | |
2573 | t = SSA_NAME_VAR (t); | |
2574 | ||
2575 | i = find_structure (strip_type (get_type_of_var (t))); | |
2576 | if (i != VEC_length (structure, structures)) | |
2577 | { | |
2578 | d_str str; | |
2579 | ||
2580 | str = VEC_index (structure, structures, i); | |
2581 | add_access_to_acc_sites (stmt, t, str->accs); | |
2582 | } | |
2583 | *walk_subtrees = 0; | |
2584 | } | |
2585 | break; | |
2586 | ||
32154c89 OG |
2587 | default: |
2588 | return NULL; | |
2589 | } | |
2590 | ||
2591 | return NULL; | |
2592 | } | |
2593 | ||
2594 | /* Free structures hashtable. */ | |
2595 | ||
2596 | static void | |
2597 | free_structures (void) | |
2598 | { | |
2599 | d_str str; | |
2600 | unsigned i; | |
2601 | ||
2602 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
2603 | free_data_struct (str); | |
2604 | ||
2605 | VEC_free (structure, heap, structures); | |
2606 | structures = NULL; | |
2607 | } | |
2608 | ||
2609 | /* This function is a callback for traversal over new_var's hashtable. | |
b8698a0f | 2610 | SLOT is a pointer to new_var. This function frees memory allocated |
32154c89 OG |
2611 | for new_var and pointed by *SLOT. */ |
2612 | ||
2613 | static int | |
2614 | free_new_var (void **slot, void *data ATTRIBUTE_UNUSED) | |
2615 | { | |
2616 | new_var n_var = *(new_var *) slot; | |
2617 | ||
2618 | /* Free vector of new_vars. */ | |
2619 | VEC_free (tree, heap, n_var->new_vars); | |
2620 | free (n_var); | |
2621 | return 1; | |
2622 | } | |
2623 | ||
2624 | /* Free new_vars hashtable NEW_VARS_HTAB. */ | |
2625 | ||
2626 | static void | |
2627 | free_new_vars_htab (htab_t new_vars_htab) | |
2628 | { | |
2629 | if (new_vars_htab) | |
b8698a0f | 2630 | htab_traverse (new_vars_htab, free_new_var, NULL); |
32154c89 OG |
2631 | htab_delete (new_vars_htab); |
2632 | new_vars_htab = NULL; | |
2633 | } | |
2634 | ||
2635 | /* This function creates new general and field accesses that appear in cfun. */ | |
2636 | ||
2637 | static void | |
2638 | create_new_accesses_for_func (void) | |
2639 | { | |
2640 | basic_block bb; | |
2641 | ||
2642 | FOR_EACH_BB_FN (bb, cfun) | |
2643 | create_new_accesses_in_bb (bb); | |
2644 | } | |
2645 | ||
2646 | /* Create new allocation sites for the function represented by NODE. */ | |
2647 | ||
2648 | static void | |
2649 | create_new_alloc_sites_for_func (struct cgraph_node *node) | |
2650 | { | |
2651 | fallocs_t fallocs = get_fallocs (node->decl); | |
2652 | ||
2653 | if (fallocs) | |
2654 | create_new_alloc_sites (fallocs, node->decl); | |
2655 | } | |
2656 | ||
2657 | /* For each local variable of structure type from the vector of structures | |
2658 | this function generates new variable(s) to replace it. */ | |
2659 | ||
2660 | static void | |
2661 | create_new_local_vars (void) | |
2662 | { | |
2663 | tree var; | |
2664 | referenced_var_iterator rvi; | |
b8698a0f L |
2665 | |
2666 | new_local_vars = htab_create (num_referenced_vars, | |
32154c89 OG |
2667 | new_var_hash, new_var_eq, NULL); |
2668 | ||
2669 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
2670 | { | |
2671 | if (!is_global_var (var)) | |
2672 | create_new_var (var, new_local_vars); | |
2673 | } | |
2674 | ||
2675 | if (new_local_vars) | |
b8698a0f | 2676 | htab_traverse (new_local_vars, finalize_new_vars_creation, NULL); |
32154c89 OG |
2677 | dump_new_vars (new_local_vars); |
2678 | } | |
2679 | ||
2680 | /* This function prints the SHIFT number of spaces to the DUMP_FILE. */ | |
2681 | ||
2682 | static inline void | |
2683 | print_shift (unsigned HOST_WIDE_INT shift) | |
2684 | { | |
2685 | unsigned HOST_WIDE_INT sh = shift; | |
2686 | ||
2687 | while (sh--) | |
b8698a0f | 2688 | fprintf (dump_file, " "); |
32154c89 OG |
2689 | } |
2690 | ||
2691 | /* This function updates field_mapping of FIELDS in CLUSTER with NEW_TYPE. */ | |
2692 | ||
2693 | static inline void | |
2694 | update_fields_mapping (struct field_cluster *cluster, tree new_type, | |
2695 | struct field_entry * fields, int num_fields) | |
2696 | { | |
2697 | int i; | |
2698 | ||
2699 | for (i = 0; i < num_fields; i++) | |
2700 | if (TEST_BIT (cluster->fields_in_cluster, i)) | |
b8698a0f | 2701 | fields[i].field_mapping = new_type; |
32154c89 OG |
2702 | } |
2703 | ||
b8698a0f L |
2704 | /* This functions builds structure with FIELDS, |
2705 | NAME and attributes similar to ORIG_STRUCT. | |
32154c89 OG |
2706 | It returns the newly created structure. */ |
2707 | ||
2708 | static tree | |
2709 | build_basic_struct (tree fields, tree name, tree orig_struct) | |
2710 | { | |
2711 | tree attributes = NULL_TREE; | |
2712 | tree ref = 0; | |
2713 | tree x; | |
2714 | ||
2715 | if (TYPE_ATTRIBUTES (orig_struct)) | |
2716 | attributes = unshare_expr (TYPE_ATTRIBUTES (orig_struct)); | |
2717 | ref = make_node (RECORD_TYPE); | |
2718 | TYPE_SIZE (ref) = 0; | |
b8698a0f | 2719 | decl_attributes (&ref, attributes, (int) ATTR_FLAG_TYPE_IN_PLACE); |
32154c89 OG |
2720 | TYPE_PACKED (ref) = TYPE_PACKED (orig_struct); |
2721 | for (x = fields; x; x = TREE_CHAIN (x)) | |
2722 | { | |
2723 | DECL_CONTEXT (x) = ref; | |
2724 | DECL_PACKED (x) |= TYPE_PACKED (ref); | |
2725 | } | |
2726 | TYPE_FIELDS (ref) = fields; | |
2727 | layout_type (ref); | |
2728 | TYPE_NAME (ref) = name; | |
2729 | ||
2730 | return ref; | |
2731 | } | |
2732 | ||
b8698a0f L |
2733 | /* This function copies FIELDS from CLUSTER into TREE_CHAIN as part |
2734 | of preparation for new structure building. NUM_FIELDS is a total | |
2735 | number of fields in the structure. The function returns newly | |
32154c89 OG |
2736 | generated fields. */ |
2737 | ||
2738 | static tree | |
b8698a0f | 2739 | create_fields (struct field_cluster * cluster, |
32154c89 OG |
2740 | struct field_entry * fields, int num_fields) |
2741 | { | |
2742 | int i; | |
2743 | tree new_types = NULL_TREE; | |
2744 | tree last = NULL_TREE; | |
2745 | ||
2746 | for (i = 0; i < num_fields; i++) | |
2747 | if (TEST_BIT (cluster->fields_in_cluster, i)) | |
2748 | { | |
2749 | tree new_decl = unshare_expr (fields[i].decl); | |
2750 | ||
2751 | if (!new_types) | |
2752 | new_types = new_decl; | |
2753 | else | |
2754 | TREE_CHAIN (last) = new_decl; | |
2755 | last = new_decl; | |
2756 | } | |
2757 | ||
2758 | TREE_CHAIN (last) = NULL_TREE; | |
2759 | return new_types; | |
2760 | ||
2761 | } | |
2762 | ||
b8698a0f | 2763 | /* This function creates a cluster name. The name is based on |
32154c89 | 2764 | the original structure name, if it is present. It has a form: |
b8698a0f | 2765 | |
32154c89 OG |
2766 | <original_struct_name>_sub.<CLUST_NUM> |
2767 | ||
2768 | The original structure name is taken from the type of DECL. | |
2769 | If an original structure name is not present, it's generated to be: | |
2770 | ||
2771 | struct.<STR_NUM> | |
2772 | ||
2773 | The function returns identifier of the new cluster name. */ | |
2774 | ||
2775 | static inline tree | |
2776 | gen_cluster_name (tree decl, int clust_num, int str_num) | |
2777 | { | |
2778 | const char * orig_name = get_type_name (decl); | |
2779 | char * tmp_name = NULL; | |
2780 | char * prefix; | |
2781 | char * new_name; | |
2782 | size_t len; | |
b8698a0f | 2783 | |
32154c89 OG |
2784 | if (!orig_name) |
2785 | ASM_FORMAT_PRIVATE_NAME(tmp_name, "struct", str_num); | |
2786 | ||
2787 | len = strlen (tmp_name ? tmp_name : orig_name) + strlen ("_sub"); | |
d3bfe4de | 2788 | prefix = XALLOCAVEC (char, len + 1); |
b8698a0f | 2789 | memcpy (prefix, tmp_name ? tmp_name : orig_name, |
32154c89 | 2790 | strlen (tmp_name ? tmp_name : orig_name)); |
b8698a0f L |
2791 | strcpy (prefix + strlen (tmp_name ? tmp_name : orig_name), "_sub"); |
2792 | ||
32154c89 OG |
2793 | ASM_FORMAT_PRIVATE_NAME (new_name, prefix, clust_num); |
2794 | return get_identifier (new_name); | |
2795 | } | |
2796 | ||
2797 | /* This function checks whether the structure STR has bitfields. | |
2798 | If yes, this structure type is added to UNSUITABLE_TYPES vector. */ | |
2799 | ||
2800 | static void | |
2801 | check_bitfields (d_str str, VEC (tree, heap) **unsuitable_types) | |
2802 | { | |
2803 | tree type = str->decl; | |
2804 | int i; | |
2805 | ||
2806 | for (i = 0; i < str->num_fields; i++) | |
2807 | if (DECL_BIT_FIELD (str->fields[i].decl)) | |
2808 | { | |
2809 | add_unsuitable_type (unsuitable_types, type); | |
2810 | if (dump_file) | |
2811 | { | |
2812 | fprintf (dump_file, "\nType "); | |
2813 | print_generic_expr (dump_file, type, 0); | |
2814 | fprintf (dump_file, "\nescapes due to bitfield "); | |
2815 | print_generic_expr (dump_file, str->fields[i].decl, 0); | |
2816 | } | |
2817 | break; | |
2818 | } | |
2819 | } | |
2820 | ||
b8698a0f | 2821 | /* This function adds to UNSUITABLE_TYPES those types that escape |
fa10beec | 2822 | due to results of ipa-type-escape analysis. See ipa-type-escape.[c,h]. */ |
32154c89 OG |
2823 | |
2824 | static void | |
2825 | exclude_escaping_types_1 (VEC (tree, heap) **unsuitable_types) | |
2826 | { | |
2827 | d_str str; | |
2828 | unsigned i; | |
2829 | ||
2830 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
2831 | check_type_escape (str, unsuitable_types); | |
2832 | } | |
2833 | ||
2834 | /* If a structure type is a return type of any function, | |
2835 | we cannot transform it. Such type is added to UNSUITABLE_TYPES vector. */ | |
2836 | ||
2837 | static void | |
2838 | exclude_returned_types (VEC (tree, heap) **unsuitable_types) | |
2839 | { | |
2840 | struct cgraph_node *c_node; | |
2841 | ||
2842 | for (c_node = cgraph_nodes; c_node; c_node = c_node->next) | |
2843 | { | |
2844 | tree ret_t = TREE_TYPE (TREE_TYPE (c_node->decl)); | |
2845 | ||
2846 | if (ret_t) | |
2847 | { | |
2848 | ret_t = strip_type (ret_t); | |
2849 | if (TREE_CODE (ret_t) == RECORD_TYPE) | |
2850 | { | |
2851 | add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (ret_t)); | |
2852 | if (dump_file) | |
2853 | { | |
2854 | fprintf (dump_file, "\nThe type \""); | |
2855 | print_generic_expr (dump_file, ret_t, 0); | |
2856 | fprintf (dump_file, | |
2857 | "\" is return type of function...Excluded."); | |
2858 | } | |
2859 | } | |
2860 | } | |
2861 | } | |
2862 | } | |
2863 | ||
b8698a0f L |
2864 | /* This function looks for parameters of local functions |
2865 | which are of structure types, or derived from them (arrays | |
32154c89 OG |
2866 | of structures, pointers to structures, or their combinations). |
2867 | We are not handling peeling of such structures right now. | |
2868 | The found structures types are added to UNSUITABLE_TYPES vector. */ | |
2869 | ||
2870 | static void | |
2871 | exclude_types_passed_to_local_func (VEC (tree, heap) **unsuitable_types) | |
2872 | { | |
2873 | struct cgraph_node *c_node; | |
2874 | ||
2875 | for (c_node = cgraph_nodes; c_node; c_node = c_node->next) | |
2876 | if (cgraph_function_body_availability (c_node) == AVAIL_LOCAL) | |
2877 | { | |
2878 | tree fn = c_node->decl; | |
2879 | tree arg; | |
b8698a0f | 2880 | |
32154c89 OG |
2881 | for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) |
2882 | { | |
2883 | tree type = TREE_TYPE (arg); | |
2884 | ||
2885 | type = strip_type (type); | |
2886 | if (TREE_CODE (type) == RECORD_TYPE) | |
2887 | { | |
b8698a0f | 2888 | add_unsuitable_type (unsuitable_types, |
32154c89 OG |
2889 | TYPE_MAIN_VARIANT (type)); |
2890 | if (dump_file) | |
2891 | { | |
2892 | fprintf (dump_file, "\nPointer to type \""); | |
2893 | print_generic_expr (dump_file, type, 0); | |
b8698a0f L |
2894 | fprintf (dump_file, |
2895 | "\" is passed to local function...Excluded."); | |
32154c89 OG |
2896 | } |
2897 | } | |
2898 | } | |
2899 | } | |
2900 | } | |
2901 | ||
b8698a0f | 2902 | /* This function analyzes structure form of structures |
32154c89 OG |
2903 | potential for transformation. If we are not capable to transform |
2904 | structure of some form, we remove it from the structures hashtable. | |
b8698a0f L |
2905 | Right now we cannot handle nested structs, when nesting is |
2906 | through any level of pointers or arrays. | |
32154c89 OG |
2907 | |
2908 | TBD: release these constrains in future. | |
2909 | ||
b8698a0f L |
2910 | Note, that in this function we suppose that all structures |
2911 | in the program are members of the structures hashtable right now, | |
32154c89 OG |
2912 | without excluding escaping types. */ |
2913 | ||
2914 | static void | |
2915 | check_struct_form (d_str str, VEC (tree, heap) **unsuitable_types) | |
2916 | { | |
2917 | int i; | |
2918 | ||
2919 | for (i = 0; i < str->num_fields; i++) | |
2920 | { | |
2921 | tree f_type = strip_type(TREE_TYPE (str->fields[i].decl)); | |
b8698a0f | 2922 | |
32154c89 OG |
2923 | if (TREE_CODE (f_type) == RECORD_TYPE) |
2924 | { | |
2925 | add_unsuitable_type (unsuitable_types, TYPE_MAIN_VARIANT (f_type)); | |
2926 | add_unsuitable_type (unsuitable_types, str->decl); | |
2927 | if (dump_file) | |
2928 | { | |
2929 | fprintf (dump_file, "\nType "); | |
2930 | print_generic_expr (dump_file, f_type, 0); | |
2931 | fprintf (dump_file, " is a field in the structure "); | |
2932 | print_generic_expr (dump_file, str->decl, 0); | |
2933 | fprintf (dump_file, ". Escaping..."); | |
2934 | } | |
2935 | } | |
2936 | } | |
2937 | } | |
2938 | ||
2939 | /* This function adds a structure TYPE to the vector of structures, | |
2940 | if it's not already there. */ | |
2941 | ||
2942 | static void | |
2943 | add_structure (tree type) | |
2944 | { | |
2945 | struct data_structure node; | |
2946 | unsigned i; | |
2947 | int num_fields; | |
2948 | ||
2949 | type = TYPE_MAIN_VARIANT (type); | |
2950 | ||
2951 | i = find_structure (type); | |
2952 | ||
2953 | if (i != VEC_length (structure, structures)) | |
2954 | return; | |
2955 | ||
2956 | num_fields = fields_length (type); | |
2957 | node.decl = type; | |
2958 | node.num_fields = num_fields; | |
2959 | node.fields = get_fields (type, num_fields); | |
2960 | node.struct_clustering = NULL; | |
2961 | node.accs = htab_create (32, acc_hash, acc_eq, NULL); | |
2962 | node.new_types = VEC_alloc (tree, heap, num_fields); | |
2963 | node.count = 0; | |
2964 | ||
2965 | VEC_safe_push (structure, heap, structures, &node); | |
2966 | ||
2967 | if (dump_file) | |
2968 | { | |
2969 | fprintf (dump_file, "\nAdding data structure \""); | |
b8698a0f | 2970 | print_generic_expr (dump_file, type, 0); |
32154c89 OG |
2971 | fprintf (dump_file, "\" to data_struct_list."); |
2972 | } | |
2973 | } | |
2974 | ||
2975 | /* This function adds an allocation site to alloc_sites hashtable. | |
b8698a0f | 2976 | The allocation site appears in STMT of function FN_DECL and |
32154c89 OG |
2977 | allocates the structure represented by STR. */ |
2978 | ||
2979 | static void | |
726a989a | 2980 | add_alloc_site (tree fn_decl, gimple stmt, d_str str) |
32154c89 OG |
2981 | { |
2982 | fallocs_t fallocs = NULL; | |
2983 | alloc_site_t m_call; | |
2984 | ||
2985 | m_call.stmt = stmt; | |
2986 | m_call.str = str; | |
2987 | ||
b8698a0f | 2988 | fallocs = |
32154c89 OG |
2989 | (fallocs_t) htab_find_with_hash (alloc_sites, |
2990 | fn_decl, htab_hash_pointer (fn_decl)); | |
2991 | ||
2992 | if (!fallocs) | |
2993 | { | |
2994 | void **slot; | |
2995 | ||
b8698a0f | 2996 | fallocs = (fallocs_t) |
32154c89 OG |
2997 | xmalloc (sizeof (struct func_alloc_sites)); |
2998 | fallocs->func = fn_decl; | |
2999 | fallocs->allocs = VEC_alloc (alloc_site_t, heap, 1); | |
3000 | slot = htab_find_slot_with_hash (alloc_sites, fn_decl, | |
3001 | htab_hash_pointer (fn_decl), INSERT); | |
3002 | *slot = fallocs; | |
3003 | } | |
b8698a0f | 3004 | VEC_safe_push (alloc_site_t, heap, |
32154c89 | 3005 | fallocs->allocs, &m_call); |
b8698a0f | 3006 | |
32154c89 OG |
3007 | if (dump_file) |
3008 | { | |
3009 | fprintf (dump_file, "\nAdding stmt "); | |
726a989a | 3010 | print_gimple_stmt (dump_file, stmt, 0, 0); |
32154c89 OG |
3011 | fprintf (dump_file, " to list of mallocs."); |
3012 | } | |
3013 | } | |
3014 | ||
3015 | /* This function returns true if the result of STMT, that contains a call | |
3016 | to an allocation function, is cast to one of the structure types. | |
3017 | STMT should be of the form: T.2 = <alloc_func> (T.1); | |
b8698a0f | 3018 | If true, I_P contains an index of an allocated structure. |
32154c89 OG |
3019 | Otherwise I_P contains the length of the vector of structures. */ |
3020 | ||
3021 | static bool | |
726a989a | 3022 | is_alloc_of_struct (gimple stmt, unsigned *i_p) |
32154c89 OG |
3023 | { |
3024 | tree lhs; | |
3025 | tree type; | |
726a989a | 3026 | gimple final_stmt; |
32154c89 OG |
3027 | |
3028 | final_stmt = get_final_alloc_stmt (stmt); | |
3029 | ||
3030 | if (!final_stmt) | |
3031 | return false; | |
3032 | ||
3033 | /* final_stmt should be of the form: | |
3034 | T.3 = (struct_type *) T.2; */ | |
3035 | ||
726a989a | 3036 | if (gimple_code (final_stmt) != GIMPLE_ASSIGN) |
32154c89 OG |
3037 | return false; |
3038 | ||
726a989a | 3039 | lhs = gimple_assign_lhs (final_stmt); |
32154c89 OG |
3040 | |
3041 | type = get_type_of_var (lhs); | |
b8698a0f | 3042 | |
32154c89 OG |
3043 | if (!type) |
3044 | return false; | |
3045 | ||
3046 | if (!POINTER_TYPE_P (type) | |
3047 | || TREE_CODE (strip_type (type)) != RECORD_TYPE) | |
3048 | return false; | |
3049 | ||
3050 | *i_p = find_structure (strip_type (type)); | |
3051 | ||
3052 | if (*i_p == VEC_length (structure, structures)) | |
3053 | return false; | |
3054 | ||
3055 | return true; | |
3056 | } | |
3057 | ||
b8698a0f L |
3058 | /* This function prints non-field and field accesses |
3059 | of the structure STR. */ | |
32154c89 OG |
3060 | |
3061 | static void | |
3062 | dump_accs (d_str str) | |
3063 | { | |
3064 | int i; | |
3065 | ||
3066 | fprintf (dump_file, "\nAccess sites of struct "); | |
3067 | print_generic_expr (dump_file, str->decl, 0); | |
3068 | ||
3069 | for (i = 0; i < str->num_fields; i++) | |
3070 | { | |
3071 | fprintf (dump_file, "\nAccess site of field "); | |
3072 | print_generic_expr (dump_file, str->fields[i].decl, 0); | |
b8698a0f | 3073 | dump_field_acc_sites (str->fields[i].acc_sites); |
32154c89 OG |
3074 | fprintf (dump_file, ":\n"); |
3075 | } | |
3076 | fprintf (dump_file, "\nGeneral access sites\n"); | |
b8698a0f | 3077 | dump_access_sites (str->accs); |
32154c89 OG |
3078 | } |
3079 | ||
3080 | /* This function checks whether an access statement, pointed by SLOT, | |
986d97ed RS |
3081 | is a condition we are capable to transform. It returns false if not, |
3082 | setting bool *DATA to false. */ | |
b8698a0f | 3083 | |
32154c89 OG |
3084 | static int |
3085 | safe_cond_expr_check (void **slot, void *data) | |
3086 | { | |
3087 | struct access_site *acc = *(struct access_site **) slot; | |
3088 | ||
726a989a | 3089 | if (gimple_code (acc->stmt) == GIMPLE_COND |
986d97ed | 3090 | && !is_safe_cond_expr (acc->stmt)) |
32154c89 | 3091 | { |
986d97ed | 3092 | if (dump_file) |
d9d90953 | 3093 | { |
986d97ed | 3094 | fprintf (dump_file, "\nUnsafe conditional statement "); |
726a989a | 3095 | print_gimple_stmt (dump_file, acc->stmt, 0, 0); |
d9d90953 | 3096 | } |
986d97ed RS |
3097 | *(bool *) data = false; |
3098 | return 0; | |
32154c89 OG |
3099 | } |
3100 | return 1; | |
3101 | } | |
3102 | ||
3103 | /* This function excludes statements that are part of allocation sites and | |
3104 | field accesses from the hashtable of general accesses of the structure | |
3105 | type STR. Only accesses that belong to the function represented by | |
3106 | NODE are treated. */ | |
3107 | ||
3108 | static void | |
3109 | exclude_alloc_and_field_accs_1 (d_str str, struct cgraph_node *node) | |
3110 | { | |
3111 | struct exclude_data dt; | |
3112 | dt.str = str; | |
3113 | dt.fn_decl = node->decl; | |
3114 | ||
3115 | if (dt.str->accs) | |
b8698a0f | 3116 | htab_traverse (dt.str->accs, exclude_from_accs, &dt); |
32154c89 OG |
3117 | } |
3118 | ||
fa10beec | 3119 | /* Collect accesses to the structure types that appear in basic block BB. */ |
32154c89 OG |
3120 | |
3121 | static void | |
3122 | collect_accesses_in_bb (basic_block bb) | |
3123 | { | |
726a989a RB |
3124 | gimple_stmt_iterator bsi; |
3125 | struct walk_stmt_info wi; | |
3126 | ||
3127 | memset (&wi, 0, sizeof (wi)); | |
32154c89 | 3128 | |
726a989a | 3129 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) |
32154c89 | 3130 | { |
726a989a | 3131 | gimple stmt = gsi_stmt (bsi); |
32154c89 OG |
3132 | |
3133 | /* In asm stmt we cannot always track the arguments, | |
3134 | so we just give up. */ | |
726a989a | 3135 | if (gimple_code (stmt) == GIMPLE_ASM) |
32154c89 OG |
3136 | { |
3137 | free_structures (); | |
3138 | break; | |
3139 | } | |
3140 | ||
726a989a RB |
3141 | wi.info = (void *) stmt; |
3142 | walk_gimple_op (stmt, get_stmt_accesses, &wi); | |
32154c89 OG |
3143 | } |
3144 | } | |
3145 | ||
fa10beec RW |
3146 | /* This function generates cluster substructure that contains FIELDS. |
3147 | The cluster added to the set of clusters of the structure STR. */ | |
32154c89 OG |
3148 | |
3149 | static void | |
3150 | gen_cluster (sbitmap fields, d_str str) | |
3151 | { | |
3152 | struct field_cluster *crr_cluster = NULL; | |
3153 | ||
b8698a0f | 3154 | crr_cluster = |
32154c89 OG |
3155 | (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster)); |
3156 | crr_cluster->sibling = str->struct_clustering; | |
3157 | str->struct_clustering = crr_cluster; | |
3158 | crr_cluster->fields_in_cluster = fields; | |
3159 | } | |
3160 | ||
3161 | /* This function peels a field with the index I from the structure DS. */ | |
3162 | ||
3163 | static void | |
3164 | peel_field (int i, d_str ds) | |
3165 | { | |
3166 | struct field_cluster *crr_cluster = NULL; | |
3167 | ||
b8698a0f | 3168 | crr_cluster = |
32154c89 OG |
3169 | (struct field_cluster *) xcalloc (1, sizeof (struct field_cluster)); |
3170 | crr_cluster->sibling = ds->struct_clustering; | |
3171 | ds->struct_clustering = crr_cluster; | |
3172 | crr_cluster->fields_in_cluster = | |
3173 | sbitmap_alloc ((unsigned int) ds->num_fields); | |
3174 | sbitmap_zero (crr_cluster->fields_in_cluster); | |
b8698a0f | 3175 | SET_BIT (crr_cluster->fields_in_cluster, i); |
32154c89 OG |
3176 | } |
3177 | ||
b8698a0f | 3178 | /* This function calculates maximum field count in |
32154c89 OG |
3179 | the structure STR. */ |
3180 | ||
3181 | static gcov_type | |
3182 | get_max_field_count (d_str str) | |
3183 | { | |
3184 | gcov_type max = 0; | |
3185 | int i; | |
3186 | ||
3187 | for (i = 0; i < str->num_fields; i++) | |
3188 | if (str->fields[i].count > max) | |
b8698a0f | 3189 | max = str->fields[i].count; |
32154c89 OG |
3190 | |
3191 | return max; | |
3192 | } | |
3193 | ||
b8698a0f L |
3194 | /* Do struct-reorg transformation for individual function |
3195 | represented by NODE. All structure types relevant | |
32154c89 OG |
3196 | for this function are transformed. */ |
3197 | ||
3198 | static void | |
3199 | do_reorg_for_func (struct cgraph_node *node) | |
3200 | { | |
b8698a0f | 3201 | create_new_local_vars (); |
32154c89 OG |
3202 | create_new_alloc_sites_for_func (node); |
3203 | create_new_accesses_for_func (); | |
3204 | update_ssa (TODO_update_ssa); | |
3205 | cleanup_tree_cfg (); | |
3206 | ||
3207 | /* Free auxiliary data representing local variables. */ | |
b8698a0f | 3208 | free_new_vars_htab (new_local_vars); |
32154c89 OG |
3209 | } |
3210 | ||
3211 | /* Print structure TYPE, its name, if it exists, and body. | |
b8698a0f L |
3212 | INDENT defines the level of indentation (similar |
3213 | to the option -i of indent command). SHIFT parameter | |
3214 | defines a number of spaces by which a structure will | |
32154c89 OG |
3215 | be shifted right. */ |
3216 | ||
3217 | static void | |
3218 | dump_struct_type (tree type, unsigned HOST_WIDE_INT indent, | |
3219 | unsigned HOST_WIDE_INT shift) | |
3220 | { | |
3221 | const char *struct_name; | |
3222 | tree field; | |
3223 | ||
3224 | if (!type || !dump_file) | |
3225 | return; | |
3226 | ||
3227 | if (TREE_CODE (type) != RECORD_TYPE) | |
3228 | { | |
3229 | print_generic_expr (dump_file, type, 0); | |
3230 | return; | |
3231 | } | |
b8698a0f | 3232 | |
32154c89 | 3233 | print_shift (shift); |
b8698a0f | 3234 | struct_name = get_type_name (type); |
32154c89 | 3235 | fprintf (dump_file, "struct "); |
b8698a0f | 3236 | if (struct_name) |
32154c89 OG |
3237 | fprintf (dump_file, "%s\n",struct_name); |
3238 | print_shift (shift); | |
3239 | fprintf (dump_file, "{\n"); | |
b8698a0f L |
3240 | |
3241 | for (field = TYPE_FIELDS (type); field; | |
32154c89 OG |
3242 | field = TREE_CHAIN (field)) |
3243 | { | |
3244 | unsigned HOST_WIDE_INT s = indent; | |
3245 | tree f_type = TREE_TYPE (field); | |
b8698a0f | 3246 | |
32154c89 OG |
3247 | print_shift (shift); |
3248 | while (s--) | |
3249 | fprintf (dump_file, " "); | |
3250 | dump_struct_type (f_type, indent, shift + indent); | |
3251 | fprintf(dump_file, " "); | |
3252 | print_generic_expr (dump_file, field, 0); | |
3253 | fprintf(dump_file, ";\n"); | |
3254 | } | |
3255 | print_shift (shift); | |
3256 | fprintf (dump_file, "}\n"); | |
3257 | } | |
3258 | ||
b8698a0f L |
3259 | /* This function creates new structure types to replace original type, |
3260 | indicated by STR->decl. The names of the new structure types are | |
3261 | derived from the original structure type. If the original structure | |
32154c89 OG |
3262 | type has no name, we assume that its name is 'struct.<STR_NUM>'. */ |
3263 | ||
3264 | static void | |
3265 | create_new_type (d_str str, int *str_num) | |
3266 | { | |
3267 | int cluster_num = 0; | |
3268 | ||
3269 | struct field_cluster *cluster = str->struct_clustering; | |
3270 | while (cluster) | |
b8698a0f L |
3271 | { |
3272 | tree name = gen_cluster_name (str->decl, cluster_num, | |
32154c89 OG |
3273 | *str_num); |
3274 | tree fields; | |
3275 | tree new_type; | |
3276 | cluster_num++; | |
b8698a0f L |
3277 | |
3278 | fields = create_fields (cluster, str->fields, | |
32154c89 OG |
3279 | str->num_fields); |
3280 | new_type = build_basic_struct (fields, name, str->decl); | |
b8698a0f L |
3281 | |
3282 | update_fields_mapping (cluster, new_type, | |
32154c89 OG |
3283 | str->fields, str->num_fields); |
3284 | ||
3285 | VEC_safe_push (tree, heap, str->new_types, new_type); | |
b8698a0f | 3286 | cluster = cluster->sibling; |
32154c89 OG |
3287 | } |
3288 | (*str_num)++; | |
3289 | } | |
3290 | ||
b8698a0f L |
3291 | /* This function is a callback for alloc_sites hashtable |
3292 | traversal. SLOT is a pointer to fallocs_t. | |
32154c89 OG |
3293 | This function frees memory pointed by *SLOT. */ |
3294 | ||
3295 | static int | |
3296 | free_falloc_sites (void **slot, void *data ATTRIBUTE_UNUSED) | |
3297 | { | |
3298 | fallocs_t fallocs = *(fallocs_t *) slot; | |
3299 | ||
3300 | VEC_free (alloc_site_t, heap, fallocs->allocs); | |
3301 | free (fallocs); | |
3302 | return 1; | |
3303 | } | |
3304 | ||
3305 | /* Remove structures collected in UNSUITABLE_TYPES | |
3306 | from structures vector. */ | |
3307 | ||
3308 | static void | |
3309 | remove_unsuitable_types (VEC (tree, heap) *unsuitable_types) | |
3310 | { | |
3311 | d_str str; | |
3312 | tree type; | |
3313 | unsigned i, j; | |
3314 | ||
3315 | for (j = 0; VEC_iterate (tree, unsuitable_types, j, type); j++) | |
3316 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3317 | if (is_equal_types (str->decl, type)) | |
3318 | { | |
3319 | remove_structure (i); | |
3320 | break; | |
3321 | } | |
3322 | } | |
3323 | ||
3324 | /* Exclude structure types with bitfields. | |
b8698a0f L |
3325 | We would not want to interfere with other optimizations |
3326 | that can be done in this case. The structure types with | |
32154c89 OG |
3327 | bitfields are added to UNSUITABLE_TYPES vector. */ |
3328 | ||
3329 | static void | |
3330 | exclude_types_with_bit_fields (VEC (tree, heap) **unsuitable_types) | |
3331 | { | |
3332 | d_str str; | |
3333 | unsigned i; | |
3334 | ||
3335 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3336 | check_bitfields (str, unsuitable_types); | |
3337 | } | |
3338 | ||
3339 | /* This function checks three types of escape. A structure type escapes: | |
3340 | ||
3341 | 1. if it's a type of parameter of a local function. | |
3342 | 2. if it's a type of function return value. | |
b8698a0f | 3343 | 3. if it escapes as a result of ipa-type-escape analysis. |
32154c89 OG |
3344 | |
3345 | The escaping structure types are added to UNSUITABLE_TYPES vector. */ | |
3346 | ||
3347 | static void | |
3348 | exclude_escaping_types (VEC (tree, heap) **unsuitable_types) | |
3349 | { | |
3350 | exclude_types_passed_to_local_func (unsuitable_types); | |
3351 | exclude_returned_types (unsuitable_types); | |
3352 | exclude_escaping_types_1 (unsuitable_types); | |
3353 | } | |
3354 | ||
b8698a0f L |
3355 | /* This function analyzes whether the form of |
3356 | structure is such that we are capable to transform it. | |
32154c89 OG |
3357 | Nested structures are checked here. Unsuitable structure |
3358 | types are added to UNSUITABLE_TYPE vector. */ | |
3359 | ||
3360 | static void | |
3361 | analyze_struct_form (VEC (tree, heap) **unsuitable_types) | |
3362 | { | |
3363 | d_str str; | |
3364 | unsigned i; | |
3365 | ||
3366 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3367 | check_struct_form (str, unsuitable_types); | |
3368 | } | |
3369 | ||
b8698a0f L |
3370 | /* This function looks for structure types instantiated in the program. |
3371 | The candidate types are added to the structures vector. | |
32154c89 OG |
3372 | Unsuitable types are collected into UNSUITABLE_TYPES vector. */ |
3373 | ||
3374 | static void | |
3375 | build_data_structure (VEC (tree, heap) **unsuitable_types) | |
3376 | { | |
3377 | tree var, type; | |
3378 | tree var_list; | |
3379 | struct varpool_node *current_varpool; | |
3380 | struct cgraph_node *c_node; | |
3381 | ||
b8698a0f | 3382 | /* Check global variables. */ |
32154c89 OG |
3383 | FOR_EACH_STATIC_VARIABLE (current_varpool) |
3384 | { | |
3385 | var = current_varpool->decl; | |
3386 | if (is_candidate (var, &type, unsuitable_types)) | |
3387 | add_structure (type); | |
3388 | } | |
3389 | ||
b8698a0f | 3390 | /* Now add structures that are types of function parameters and |
32154c89 OG |
3391 | local variables. */ |
3392 | for (c_node = cgraph_nodes; c_node; c_node = c_node->next) | |
3393 | { | |
b8698a0f | 3394 | enum availability avail = |
32154c89 OG |
3395 | cgraph_function_body_availability (c_node); |
3396 | ||
3397 | /* We need AVAIL_AVAILABLE for main function. */ | |
3398 | if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE) | |
3399 | { | |
3400 | struct function *fn = DECL_STRUCT_FUNCTION (c_node->decl); | |
3401 | ||
b8698a0f | 3402 | for (var = DECL_ARGUMENTS (c_node->decl); var; |
32154c89 OG |
3403 | var = TREE_CHAIN (var)) |
3404 | if (is_candidate (var, &type, unsuitable_types)) | |
3405 | add_structure (type); | |
3406 | ||
68052d59 JJ |
3407 | if (fn == NULL) |
3408 | { | |
3409 | /* Skip cones that haven't been materialized yet. */ | |
3410 | gcc_assert (c_node->clone_of | |
3411 | && c_node->clone_of->decl != c_node->decl); | |
3412 | continue; | |
3413 | } | |
3414 | ||
32154c89 | 3415 | /* Check function local variables. */ |
b8698a0f | 3416 | for (var_list = fn->local_decls; var_list; |
32154c89 OG |
3417 | var_list = TREE_CHAIN (var_list)) |
3418 | { | |
3419 | var = TREE_VALUE (var_list); | |
3420 | ||
3421 | if (is_candidate (var, &type, unsuitable_types)) | |
3422 | add_structure (type); | |
3423 | } | |
3424 | } | |
3425 | } | |
3426 | } | |
3427 | ||
b8698a0f | 3428 | /* This function returns true if the program contains |
32154c89 OG |
3429 | a call to user defined allocation function, or other |
3430 | functions that can interfere with struct-reorg optimizations. */ | |
3431 | ||
3432 | static bool | |
3433 | program_redefines_malloc_p (void) | |
3434 | { | |
3435 | struct cgraph_node *c_node; | |
3436 | struct cgraph_node *c_node2; | |
3437 | struct cgraph_edge *c_edge; | |
3438 | tree fndecl; | |
3439 | tree fndecl2; | |
b8698a0f | 3440 | |
32154c89 OG |
3441 | for (c_node = cgraph_nodes; c_node; c_node = c_node->next) |
3442 | { | |
3443 | fndecl = c_node->decl; | |
3444 | ||
3445 | for (c_edge = c_node->callees; c_edge; c_edge = c_edge->next_callee) | |
3446 | { | |
32154c89 OG |
3447 | c_node2 = c_edge->callee; |
3448 | fndecl2 = c_node2->decl; | |
726a989a | 3449 | if (is_gimple_call (c_edge->call_stmt)) |
32154c89 OG |
3450 | { |
3451 | const char * fname = get_name (fndecl2); | |
3452 | ||
726a989a RB |
3453 | if ((gimple_call_flags (c_edge->call_stmt) & ECF_MALLOC) |
3454 | && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_MALLOC) | |
3455 | && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_CALLOC) | |
3456 | && (DECL_FUNCTION_CODE (fndecl2) != BUILT_IN_ALLOCA)) | |
32154c89 OG |
3457 | return true; |
3458 | ||
3459 | /* Check that there is no __builtin_object_size, | |
3460 | __builtin_offsetof, or realloc's in the program. */ | |
3461 | if (DECL_FUNCTION_CODE (fndecl2) == BUILT_IN_OBJECT_SIZE | |
3462 | || !strcmp (fname, "__builtin_offsetof") | |
3463 | || !strcmp (fname, "realloc")) | |
b8698a0f | 3464 | return true; |
32154c89 OG |
3465 | } |
3466 | } | |
3467 | } | |
b8698a0f | 3468 | |
32154c89 OG |
3469 | return false; |
3470 | } | |
3471 | ||
b8698a0f | 3472 | /* In this function we assume that an allocation statement |
32154c89 OG |
3473 | |
3474 | var = (type_cast) malloc (size); | |
b8698a0f | 3475 | |
32154c89 OG |
3476 | is converted into the following set of statements: |
3477 | ||
3478 | T.1 = size; | |
3479 | T.2 = malloc (T.1); | |
3480 | T.3 = (type_cast) T.2; | |
3481 | var = T.3; | |
3482 | ||
b8698a0f L |
3483 | In this function we collect into alloc_sites the allocation |
3484 | sites of variables of structure types that are present | |
32154c89 OG |
3485 | in structures vector. */ |
3486 | ||
3487 | static void | |
3488 | collect_alloc_sites (void) | |
3489 | { | |
3490 | struct cgraph_node *node; | |
3491 | struct cgraph_edge *cs; | |
3492 | ||
3493 | for (node = cgraph_nodes; node; node = node->next) | |
3494 | if (node->analyzed && node->decl) | |
3495 | { | |
3496 | for (cs = node->callees; cs; cs = cs->next_callee) | |
3497 | { | |
726a989a | 3498 | gimple stmt = cs->call_stmt; |
32154c89 OG |
3499 | |
3500 | if (stmt) | |
3501 | { | |
32154c89 OG |
3502 | tree decl; |
3503 | ||
726a989a | 3504 | if (is_gimple_call (stmt) |
b8698a0f | 3505 | && (decl = gimple_call_fndecl (stmt)) |
726a989a | 3506 | && gimple_call_lhs (stmt)) |
32154c89 OG |
3507 | { |
3508 | unsigned i; | |
3509 | ||
3510 | if (is_alloc_of_struct (stmt, &i)) | |
3511 | { | |
3512 | /* We support only malloc now. */ | |
3513 | if (DECL_FUNCTION_CODE (decl) == BUILT_IN_MALLOC) | |
3514 | { | |
3515 | d_str str; | |
b8698a0f | 3516 | |
32154c89 OG |
3517 | str = VEC_index (structure, structures, i); |
3518 | add_alloc_site (node->decl, stmt, str); | |
3519 | } | |
3520 | else | |
d9d90953 OG |
3521 | { |
3522 | if (dump_file) | |
3523 | { | |
b8698a0f | 3524 | fprintf (dump_file, |
d9d90953 | 3525 | "\nUnsupported allocation function "); |
726a989a | 3526 | print_gimple_stmt (dump_file, stmt, 0, 0); |
d9d90953 | 3527 | } |
b8698a0f | 3528 | remove_structure (i); |
d9d90953 | 3529 | } |
32154c89 OG |
3530 | } |
3531 | } | |
b8698a0f | 3532 | } |
32154c89 OG |
3533 | } |
3534 | } | |
3535 | } | |
3536 | ||
3537 | /* Print collected accesses. */ | |
3538 | ||
3539 | static void | |
3540 | dump_accesses (void) | |
3541 | { | |
3542 | d_str str; | |
3543 | unsigned i; | |
3544 | ||
3545 | if (!dump_file) | |
3546 | return; | |
3547 | ||
3548 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3549 | dump_accs (str); | |
3550 | } | |
3551 | ||
b8698a0f L |
3552 | /* This function checks whether the accesses of structures in condition |
3553 | expressions are of the kind we are capable to transform. | |
32154c89 OG |
3554 | If not, such structures are removed from the vector of structures. */ |
3555 | ||
3556 | static void | |
3557 | check_cond_exprs (void) | |
3558 | { | |
3559 | d_str str; | |
3560 | unsigned i; | |
3561 | ||
986d97ed RS |
3562 | i = 0; |
3563 | while (VEC_iterate (structure, structures, i, str)) | |
3564 | { | |
3565 | bool safe_p = true; | |
3566 | ||
3567 | if (str->accs) | |
3568 | htab_traverse (str->accs, safe_cond_expr_check, &safe_p); | |
3569 | if (!safe_p) | |
3570 | remove_structure (i); | |
3571 | else | |
3572 | i++; | |
3573 | } | |
32154c89 OG |
3574 | } |
3575 | ||
b8698a0f L |
3576 | /* We exclude from non-field accesses of the structure |
3577 | all statements that will be treated as part of the structure | |
32154c89 OG |
3578 | allocation sites or field accesses. */ |
3579 | ||
3580 | static void | |
3581 | exclude_alloc_and_field_accs (struct cgraph_node *node) | |
3582 | { | |
3583 | d_str str; | |
3584 | unsigned i; | |
3585 | ||
3586 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3587 | exclude_alloc_and_field_accs_1 (str, node); | |
3588 | } | |
3589 | ||
b8698a0f | 3590 | /* This function collects accesses of the fields of the structures |
32154c89 OG |
3591 | that appear at function FN. */ |
3592 | ||
3593 | static void | |
3594 | collect_accesses_in_func (struct function *fn) | |
3595 | { | |
3596 | basic_block bb; | |
3597 | ||
3598 | if (! fn) | |
3599 | return; | |
3600 | ||
3601 | /* Collect accesses for each basic blocks separately. */ | |
3602 | FOR_EACH_BB_FN (bb, fn) | |
3603 | collect_accesses_in_bb (bb); | |
3604 | } | |
3605 | ||
3606 | /* This function summarizes counts of the fields into the structure count. */ | |
3607 | ||
3608 | static void | |
ea429753 | 3609 | sum_counts (d_str str, gcov_type *hottest) |
32154c89 OG |
3610 | { |
3611 | int i; | |
b8698a0f | 3612 | |
32154c89 OG |
3613 | str->count = 0; |
3614 | for (i = 0; i < str->num_fields; i++) | |
3615 | { | |
3616 | if (dump_file) | |
3617 | { | |
3618 | fprintf (dump_file, "\nCounter of field \""); | |
3619 | print_generic_expr (dump_file, str->fields[i].decl, 0); | |
b8698a0f | 3620 | fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, |
32154c89 OG |
3621 | str->fields[i].count); |
3622 | } | |
3623 | str->count += str->fields[i].count; | |
3624 | } | |
3625 | ||
3626 | if (dump_file) | |
3627 | { | |
3628 | fprintf (dump_file, "\nCounter of struct \""); | |
3629 | print_generic_expr (dump_file, str->decl, 0); | |
8d66f742 | 3630 | fprintf (dump_file, "\" is " HOST_WIDEST_INT_PRINT_DEC, str->count); |
32154c89 OG |
3631 | } |
3632 | ||
ea429753 BF |
3633 | if (str->count > *hottest) |
3634 | *hottest = str->count; | |
32154c89 OG |
3635 | } |
3636 | ||
3637 | /* This function peels the field into separate structure if it's | |
b8698a0f | 3638 | sufficiently hot, i.e. if its count provides at least 90% of |
32154c89 OG |
3639 | the maximum field count in the structure. */ |
3640 | ||
3641 | static void | |
3642 | peel_hot_fields (d_str str) | |
3643 | { | |
3644 | gcov_type max_field_count; | |
3645 | sbitmap fields_left = sbitmap_alloc (str->num_fields); | |
3646 | int i; | |
3647 | ||
3648 | sbitmap_ones (fields_left); | |
b8698a0f | 3649 | max_field_count = |
32154c89 OG |
3650 | (gcov_type) (get_max_field_count (str)/100)*90; |
3651 | ||
3652 | str->struct_clustering = NULL; | |
3653 | ||
3654 | for (i = 0; i < str->num_fields; i++) | |
3655 | { | |
3656 | if (str->count >= max_field_count) | |
3657 | { | |
b8698a0f | 3658 | RESET_BIT (fields_left, i); |
32154c89 OG |
3659 | peel_field (i, str); |
3660 | } | |
3661 | } | |
3662 | ||
3663 | i = sbitmap_first_set_bit (fields_left); | |
3664 | if (i != -1) | |
3665 | gen_cluster (fields_left, str); | |
3666 | else | |
3667 | sbitmap_free (fields_left); | |
b8698a0f | 3668 | } |
32154c89 | 3669 | |
b8698a0f L |
3670 | /* This function is a helper for do_reorg. It goes over |
3671 | functions in call graph and performs actual transformation | |
32154c89 OG |
3672 | on them. */ |
3673 | ||
3674 | static void | |
3675 | do_reorg_1 (void) | |
3676 | { | |
3677 | struct cgraph_node *node; | |
3678 | ||
3679 | /* Initialize the default bitmap obstack. */ | |
3680 | bitmap_obstack_initialize (NULL); | |
3681 | ||
3682 | for (node = cgraph_nodes; node; node = node->next) | |
9187e02d | 3683 | if (node->analyzed && node->decl) |
32154c89 OG |
3684 | { |
3685 | push_cfun (DECL_STRUCT_FUNCTION (node->decl)); | |
3686 | current_function_decl = node->decl; | |
3687 | if (dump_file) | |
c3df55f9 | 3688 | fprintf (dump_file, "\nFunction to do reorg is %s: \n", |
32154c89 OG |
3689 | (const char *) IDENTIFIER_POINTER (DECL_NAME (node->decl))); |
3690 | do_reorg_for_func (node); | |
3691 | free_dominance_info (CDI_DOMINATORS); | |
3692 | free_dominance_info (CDI_POST_DOMINATORS); | |
3693 | current_function_decl = NULL; | |
3694 | pop_cfun (); | |
3695 | } | |
3696 | ||
5576d6f2 | 3697 | set_cfun (NULL); |
a68ab351 | 3698 | bitmap_obstack_release (NULL); |
32154c89 OG |
3699 | } |
3700 | ||
3701 | /* This function creates new global struct variables. | |
b8698a0f L |
3702 | For each original variable, the set of new variables |
3703 | is created with the new structure types corresponding | |
3704 | to the structure type of original variable. | |
32154c89 OG |
3705 | Only VAR_DECL variables are treated by this function. */ |
3706 | ||
b8698a0f | 3707 | static void |
32154c89 OG |
3708 | create_new_global_vars (void) |
3709 | { | |
3710 | struct varpool_node *current_varpool; | |
3711 | unsigned HOST_WIDE_INT i; | |
3712 | unsigned HOST_WIDE_INT varpool_size = 0; | |
3713 | ||
3714 | for (i = 0; i < 2; i++) | |
3715 | { | |
3716 | if (i) | |
b8698a0f | 3717 | new_global_vars = htab_create (varpool_size, |
32154c89 OG |
3718 | new_var_hash, new_var_eq, NULL); |
3719 | FOR_EACH_STATIC_VARIABLE(current_varpool) | |
3720 | { | |
3721 | tree var_decl = current_varpool->decl; | |
3722 | ||
3723 | if (!var_decl || TREE_CODE (var_decl) != VAR_DECL) | |
3724 | continue; | |
3725 | if (!i) | |
3726 | varpool_size++; | |
3727 | else | |
3728 | create_new_var (var_decl, new_global_vars); | |
3729 | } | |
3730 | } | |
3731 | ||
3732 | if (new_global_vars) | |
3733 | htab_traverse (new_global_vars, update_varpool_with_new_var, NULL); | |
3734 | } | |
3735 | ||
3736 | /* Dump all new types generated by this optimization. */ | |
3737 | ||
3738 | static void | |
3739 | dump_new_types (void) | |
3740 | { | |
3741 | d_str str; | |
3742 | tree type; | |
3743 | unsigned i, j; | |
3744 | ||
3745 | if (!dump_file) | |
3746 | return; | |
3747 | ||
3748 | fprintf (dump_file, "\nThe following are the new types generated by" | |
3749 | " this optimization:\n"); | |
3750 | ||
3751 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
d9d90953 OG |
3752 | { |
3753 | if (dump_file) | |
3754 | { | |
3755 | fprintf (dump_file, "\nFor type "); | |
3756 | dump_struct_type (str->decl, 2, 0); | |
3757 | fprintf (dump_file, "\nthe number of new types is %d\n", | |
3758 | VEC_length (tree, str->new_types)); | |
b8698a0f | 3759 | } |
d9d90953 | 3760 | for (j = 0; VEC_iterate (tree, str->new_types, j, type); j++) |
b8698a0f | 3761 | dump_struct_type (type, 2, 0); |
d9d90953 | 3762 | } |
32154c89 OG |
3763 | } |
3764 | ||
3765 | /* This function creates new types to replace old structure types. */ | |
3766 | ||
3767 | static void | |
3768 | create_new_types (void) | |
3769 | { | |
3770 | d_str str; | |
3771 | unsigned i; | |
3772 | int str_num = 0; | |
3773 | ||
3774 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3775 | create_new_type (str, &str_num); | |
3776 | } | |
3777 | ||
3778 | /* Free allocation sites hashtable. */ | |
3779 | ||
3780 | static void | |
3781 | free_alloc_sites (void) | |
3782 | { | |
3783 | if (alloc_sites) | |
b8698a0f | 3784 | htab_traverse (alloc_sites, free_falloc_sites, NULL); |
32154c89 OG |
3785 | htab_delete (alloc_sites); |
3786 | alloc_sites = NULL; | |
3787 | } | |
3788 | ||
b8698a0f L |
3789 | /* This function collects structures potential |
3790 | for peeling transformation, and inserts | |
32154c89 OG |
3791 | them into structures hashtable. */ |
3792 | ||
b8698a0f | 3793 | static void |
32154c89 OG |
3794 | collect_structures (void) |
3795 | { | |
3796 | VEC (tree, heap) *unsuitable_types = VEC_alloc (tree, heap, 32); | |
3797 | ||
3798 | structures = VEC_alloc (structure, heap, 32); | |
b8698a0f | 3799 | |
32154c89 OG |
3800 | /* If program contains user defined mallocs, we give up. */ |
3801 | if (program_redefines_malloc_p ()) | |
b8698a0f | 3802 | return; |
32154c89 | 3803 | |
b8698a0f | 3804 | /* Build data structures hashtable of all data structures |
32154c89 OG |
3805 | in the program. */ |
3806 | build_data_structure (&unsuitable_types); | |
3807 | ||
b8698a0f L |
3808 | /* This function analyzes whether the form of |
3809 | structure is such that we are capable to transform it. | |
32154c89 OG |
3810 | Nested structures are checked here. */ |
3811 | analyze_struct_form (&unsuitable_types); | |
3812 | ||
b8698a0f | 3813 | /* This function excludes those structure types |
32154c89 OG |
3814 | that escape compilation unit. */ |
3815 | exclude_escaping_types (&unsuitable_types); | |
3816 | ||
3817 | /* We do not want to change data layout of the structures with bitfields. */ | |
3818 | exclude_types_with_bit_fields (&unsuitable_types); | |
3819 | ||
3820 | remove_unsuitable_types (unsuitable_types); | |
3821 | VEC_free (tree, heap, unsuitable_types); | |
32154c89 OG |
3822 | } |
3823 | ||
3824 | /* Collect structure allocation sites. In case of arrays | |
3825 | we have nothing to do. */ | |
3826 | ||
3827 | static void | |
3828 | collect_allocation_sites (void) | |
3829 | { | |
3830 | alloc_sites = htab_create (32, malloc_hash, malloc_eq, NULL); | |
3831 | collect_alloc_sites (); | |
3832 | } | |
3833 | ||
b8698a0f L |
3834 | /* This function collects data accesses for the |
3835 | structures to be transformed. For each structure | |
32154c89 OG |
3836 | field it updates the count field in field_entry. */ |
3837 | ||
b8698a0f | 3838 | static void |
32154c89 OG |
3839 | collect_data_accesses (void) |
3840 | { | |
3841 | struct cgraph_node *c_node; | |
3842 | ||
3843 | for (c_node = cgraph_nodes; c_node; c_node = c_node->next) | |
3844 | { | |
3845 | enum availability avail = cgraph_function_body_availability (c_node); | |
3846 | ||
3847 | if (avail == AVAIL_LOCAL || avail == AVAIL_AVAILABLE) | |
3848 | { | |
3849 | struct function *func = DECL_STRUCT_FUNCTION (c_node->decl); | |
3850 | ||
9187e02d | 3851 | collect_accesses_in_func (func); |
32154c89 OG |
3852 | exclude_alloc_and_field_accs (c_node); |
3853 | } | |
3854 | } | |
3855 | ||
3856 | check_cond_exprs (); | |
3857 | /* Print collected accesses. */ | |
3858 | dump_accesses (); | |
3859 | } | |
3860 | ||
3861 | /* We do not bother to transform cold structures. | |
b8698a0f L |
3862 | Coldness of the structure is defined relatively |
3863 | to the highest structure count among the structures | |
32154c89 OG |
3864 | to be transformed. It's triggered by the compiler parameter |
3865 | ||
3866 | --param struct-reorg-cold-struct-ratio=<value> | |
3867 | ||
3868 | where <value> ranges from 0 to 100. Structures with count ratios | |
3869 | that are less than this parameter are considered to be cold. */ | |
3870 | ||
3871 | static void | |
3872 | exclude_cold_structs (void) | |
3873 | { | |
ea429753 | 3874 | gcov_type hottest = 0; |
32154c89 OG |
3875 | unsigned i; |
3876 | d_str str; | |
3877 | ||
3878 | /* We summarize counts of fields of a structure into the structure count. */ | |
3879 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
ea429753 | 3880 | sum_counts (str, &hottest); |
32154c89 OG |
3881 | |
3882 | /* Remove cold structures from structures vector. */ | |
986d97ed RS |
3883 | i = 0; |
3884 | while (VEC_iterate (structure, structures, i, str)) | |
ea429753 | 3885 | if (str->count * 100 < (hottest * STRUCT_REORG_COLD_STRUCT_RATIO)) |
d9d90953 OG |
3886 | { |
3887 | if (dump_file) | |
3888 | { | |
3889 | fprintf (dump_file, "\nThe structure "); | |
3890 | print_generic_expr (dump_file, str->decl, 0); | |
3891 | fprintf (dump_file, " is cold."); | |
3892 | } | |
3893 | remove_structure (i); | |
3894 | } | |
986d97ed RS |
3895 | else |
3896 | i++; | |
32154c89 OG |
3897 | } |
3898 | ||
b8698a0f | 3899 | /* This function decomposes original structure into substructures, |
32154c89 OG |
3900 | i.e.clusters. */ |
3901 | ||
3902 | static void | |
3903 | peel_structs (void) | |
3904 | { | |
3905 | d_str str; | |
3906 | unsigned i; | |
3907 | ||
3908 | for (i = 0; VEC_iterate (structure, structures, i, str); i++) | |
3909 | peel_hot_fields (str); | |
3910 | } | |
3911 | ||
3912 | /* Stage 3. */ | |
3913 | /* Do the actual transformation for each structure | |
3914 | from the structures hashtable. */ | |
3915 | ||
3916 | static void | |
3917 | do_reorg (void) | |
3918 | { | |
3919 | /* Check that there is a work to do. */ | |
3920 | if (!VEC_length (structure, structures)) | |
d9d90953 OG |
3921 | { |
3922 | if (dump_file) | |
3923 | fprintf (dump_file, "\nNo structures to transform. Exiting..."); | |
3924 | return; | |
3925 | } | |
3926 | else | |
3927 | { | |
3928 | if (dump_file) | |
3929 | { | |
3930 | fprintf (dump_file, "\nNumber of structures to transform is %d", | |
3931 | VEC_length (structure, structures)); | |
3932 | } | |
3933 | } | |
32154c89 OG |
3934 | |
3935 | /* Generate new types. */ | |
3936 | create_new_types (); | |
3937 | dump_new_types (); | |
3938 | ||
3939 | /* Create new global variables. */ | |
3940 | create_new_global_vars (); | |
b8698a0f | 3941 | dump_new_vars (new_global_vars); |
32154c89 OG |
3942 | |
3943 | /* Decompose structures for each function separately. */ | |
3944 | do_reorg_1 (); | |
3945 | ||
3946 | /* Free auxiliary data collected for global variables. */ | |
b8698a0f | 3947 | free_new_vars_htab (new_global_vars); |
32154c89 OG |
3948 | } |
3949 | ||
3950 | /* Free all auxiliary data used by this optimization. */ | |
3951 | ||
3952 | static void | |
3953 | free_data_structs (void) | |
3954 | { | |
3955 | free_structures (); | |
b8698a0f | 3956 | free_alloc_sites (); |
32154c89 OG |
3957 | } |
3958 | ||
3959 | /* Perform structure decomposition (peeling). */ | |
3960 | ||
3961 | static void | |
3962 | reorg_structs (void) | |
3963 | { | |
3964 | ||
b8698a0f | 3965 | /* Stage1. */ |
32154c89 OG |
3966 | /* Collect structure types. */ |
3967 | collect_structures (); | |
3968 | ||
3969 | /* Collect structure allocation sites. */ | |
b8698a0f | 3970 | collect_allocation_sites (); |
32154c89 OG |
3971 | |
3972 | /* Collect structure accesses. */ | |
b8698a0f | 3973 | collect_data_accesses (); |
32154c89 OG |
3974 | |
3975 | /* We transform only hot structures. */ | |
3976 | exclude_cold_structs (); | |
3977 | ||
3978 | /* Stage2. */ | |
3979 | /* Decompose structures into substructures, i.e. clusters. */ | |
3980 | peel_structs (); | |
3981 | ||
b8698a0f | 3982 | /* Stage3. */ |
32154c89 OG |
3983 | /* Do the actual transformation for each structure |
3984 | from the structures hashtable. */ | |
3985 | do_reorg (); | |
3986 | ||
3987 | /* Free all auxiliary data used by this optimization. */ | |
b8698a0f | 3988 | free_data_structs (); |
32154c89 OG |
3989 | } |
3990 | ||
3991 | /* Struct-reorg optimization entry point function. */ | |
3992 | ||
3993 | static unsigned int | |
3994 | reorg_structs_drive (void) | |
3995 | { | |
3996 | reorg_structs (); | |
3997 | return 0; | |
3998 | } | |
3999 | ||
4000 | /* Struct-reorg optimization gate function. */ | |
4001 | ||
4002 | static bool | |
4003 | struct_reorg_gate (void) | |
4004 | { | |
726a989a | 4005 | return flag_ipa_struct_reorg |
b8698a0f | 4006 | && flag_whole_program |
726a989a | 4007 | && (optimize > 0); |
32154c89 OG |
4008 | } |
4009 | ||
b8698a0f | 4010 | struct simple_ipa_opt_pass pass_ipa_struct_reorg = |
32154c89 | 4011 | { |
8ddbbcae JH |
4012 | { |
4013 | SIMPLE_IPA_PASS, | |
32154c89 OG |
4014 | "ipa_struct_reorg", /* name */ |
4015 | struct_reorg_gate, /* gate */ | |
4016 | reorg_structs_drive, /* execute */ | |
4017 | NULL, /* sub */ | |
4018 | NULL, /* next */ | |
4019 | 0, /* static_pass_number */ | |
4020 | TV_INTEGRATION, /* tv_id */ | |
4021 | 0, /* properties_required */ | |
4022 | 0, /* properties_provided */ | |
4023 | 0, /* properties_destroyed */ | |
4024 | TODO_verify_ssa, /* todo_flags_start */ | |
8ddbbcae JH |
4025 | TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ |
4026 | } | |
32154c89 | 4027 | }; |