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