]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Data flow functions for trees. |
d1e082c2 | 2 | Copyright (C) 2001-2013 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "hashtab.h" | |
0c58f841 | 26 | #include "pointer-set.h" |
6de9cd9a | 27 | #include "tree.h" |
6de9cd9a | 28 | #include "tm_p.h" |
6de9cd9a | 29 | #include "basic-block.h" |
6de9cd9a DN |
30 | #include "ggc.h" |
31 | #include "langhooks.h" | |
32 | #include "flags.h" | |
33 | #include "function.h" | |
cf835838 | 34 | #include "tree-pretty-print.h" |
726a989a | 35 | #include "gimple.h" |
7a300452 | 36 | #include "tree-ssa.h" |
6de9cd9a | 37 | #include "tree-inline.h" |
6de9cd9a DN |
38 | #include "tree-pass.h" |
39 | #include "convert.h" | |
40 | #include "params.h" | |
6674a6ce | 41 | #include "cgraph.h" |
6de9cd9a DN |
42 | |
43 | /* Build and maintain data flow information for trees. */ | |
44 | ||
45 | /* Counters used to display DFA and SSA statistics. */ | |
46 | struct dfa_stats_d | |
47 | { | |
6de9cd9a DN |
48 | long num_defs; |
49 | long num_uses; | |
50 | long num_phis; | |
51 | long num_phi_args; | |
726a989a | 52 | size_t max_num_phi_args; |
38635499 | 53 | long num_vdefs; |
6de9cd9a DN |
54 | long num_vuses; |
55 | }; | |
56 | ||
57 | ||
6de9cd9a DN |
58 | /* Local functions. */ |
59 | static void collect_dfa_stats (struct dfa_stats_d *); | |
6de9cd9a DN |
60 | |
61 | ||
6de9cd9a DN |
62 | /*--------------------------------------------------------------------------- |
63 | Dataflow analysis (DFA) routines | |
64 | ---------------------------------------------------------------------------*/ | |
6de9cd9a | 65 | |
908ff6a3 KZ |
66 | /* Renumber all of the gimple stmt uids. */ |
67 | ||
b8698a0f | 68 | void |
908ff6a3 KZ |
69 | renumber_gimple_stmt_uids (void) |
70 | { | |
71 | basic_block bb; | |
72 | ||
73 | set_gimple_stmt_max_uid (cfun, 0); | |
74 | FOR_ALL_BB (bb) | |
75 | { | |
726a989a | 76 | gimple_stmt_iterator bsi; |
8f984534 RB |
77 | for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) |
78 | { | |
79 | gimple stmt = gsi_stmt (bsi); | |
80 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
81 | } | |
726a989a | 82 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) |
908ff6a3 | 83 | { |
726a989a RB |
84 | gimple stmt = gsi_stmt (bsi); |
85 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
908ff6a3 KZ |
86 | } |
87 | } | |
88 | } | |
89 | ||
2c08497a BS |
90 | /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks |
91 | in BLOCKS, of which there are N_BLOCKS. Also renumbers PHIs. */ | |
92 | ||
b8698a0f | 93 | void |
2c08497a BS |
94 | renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks) |
95 | { | |
96 | int i; | |
97 | ||
98 | set_gimple_stmt_max_uid (cfun, 0); | |
99 | for (i = 0; i < n_blocks; i++) | |
100 | { | |
101 | basic_block bb = blocks[i]; | |
102 | gimple_stmt_iterator bsi; | |
103 | for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
104 | { | |
105 | gimple stmt = gsi_stmt (bsi); | |
106 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
107 | } | |
108 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
109 | { | |
110 | gimple stmt = gsi_stmt (bsi); | |
111 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
112 | } | |
113 | } | |
114 | } | |
115 | ||
571325db | 116 | |
6de9cd9a DN |
117 | |
118 | /*--------------------------------------------------------------------------- | |
119 | Debugging functions | |
120 | ---------------------------------------------------------------------------*/ | |
6de9cd9a DN |
121 | |
122 | /* Dump variable VAR and its may-aliases to FILE. */ | |
123 | ||
124 | void | |
125 | dump_variable (FILE *file, tree var) | |
126 | { | |
d8903b30 DN |
127 | if (TREE_CODE (var) == SSA_NAME) |
128 | { | |
129 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
130 | dump_points_to_info_for (file, var); | |
131 | var = SSA_NAME_VAR (var); | |
132 | } | |
6de9cd9a DN |
133 | |
134 | if (var == NULL_TREE) | |
135 | { | |
136 | fprintf (file, "<nil>"); | |
137 | return; | |
138 | } | |
139 | ||
140 | print_generic_expr (file, var, dump_flags); | |
6de9cd9a | 141 | |
ea53115f | 142 | fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var)); |
25a6a873 RG |
143 | if (DECL_PT_UID (var) != DECL_UID (var)) |
144 | fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var)); | |
6de9cd9a | 145 | |
1810f6ed DN |
146 | fprintf (file, ", "); |
147 | print_generic_expr (file, TREE_TYPE (var), dump_flags); | |
148 | ||
c597ef4e DN |
149 | if (TREE_ADDRESSABLE (var)) |
150 | fprintf (file, ", is addressable"); | |
b8698a0f | 151 | |
c597ef4e DN |
152 | if (is_global_var (var)) |
153 | fprintf (file, ", is global"); | |
6de9cd9a | 154 | |
c04f07f4 DN |
155 | if (TREE_THIS_VOLATILE (var)) |
156 | fprintf (file, ", is volatile"); | |
157 | ||
32244553 | 158 | if (cfun && ssa_default_def (cfun, var)) |
6de9cd9a DN |
159 | { |
160 | fprintf (file, ", default def: "); | |
32244553 | 161 | print_generic_expr (file, ssa_default_def (cfun, var), dump_flags); |
6de9cd9a DN |
162 | } |
163 | ||
66350781 DN |
164 | if (DECL_INITIAL (var)) |
165 | { | |
166 | fprintf (file, ", initial: "); | |
167 | print_generic_expr (file, DECL_INITIAL (var), dump_flags); | |
168 | } | |
169 | ||
6de9cd9a DN |
170 | fprintf (file, "\n"); |
171 | } | |
172 | ||
173 | ||
174 | /* Dump variable VAR and its may-aliases to stderr. */ | |
175 | ||
24e47c76 | 176 | DEBUG_FUNCTION void |
6de9cd9a DN |
177 | debug_variable (tree var) |
178 | { | |
179 | dump_variable (stderr, var); | |
180 | } | |
181 | ||
182 | ||
6de9cd9a DN |
183 | /* Dump various DFA statistics to FILE. */ |
184 | ||
185 | void | |
186 | dump_dfa_stats (FILE *file) | |
187 | { | |
188 | struct dfa_stats_d dfa_stats; | |
189 | ||
190 | unsigned long size, total = 0; | |
191 | const char * const fmt_str = "%-30s%-13s%12s\n"; | |
192 | const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n"; | |
193 | const char * const fmt_str_3 = "%-43s%11lu%c\n"; | |
194 | const char *funcname | |
673fda6b | 195 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
196 | |
197 | collect_dfa_stats (&dfa_stats); | |
198 | ||
199 | fprintf (file, "\nDFA Statistics for %s\n\n", funcname); | |
200 | ||
201 | fprintf (file, "---------------------------------------------------------\n"); | |
202 | fprintf (file, fmt_str, "", " Number of ", "Memory"); | |
203 | fprintf (file, fmt_str, "", " instances ", "used "); | |
204 | fprintf (file, "---------------------------------------------------------\n"); | |
205 | ||
6de9cd9a DN |
206 | size = dfa_stats.num_uses * sizeof (tree *); |
207 | total += size; | |
208 | fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses, | |
209 | SCALE (size), LABEL (size)); | |
210 | ||
211 | size = dfa_stats.num_defs * sizeof (tree *); | |
212 | total += size; | |
213 | fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs, | |
214 | SCALE (size), LABEL (size)); | |
215 | ||
216 | size = dfa_stats.num_vuses * sizeof (tree *); | |
217 | total += size; | |
218 | fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses, | |
219 | SCALE (size), LABEL (size)); | |
220 | ||
38635499 | 221 | size = dfa_stats.num_vdefs * sizeof (tree *); |
a32b97a2 | 222 | total += size; |
38635499 | 223 | fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs, |
6de9cd9a DN |
224 | SCALE (size), LABEL (size)); |
225 | ||
726a989a | 226 | size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi); |
6de9cd9a DN |
227 | total += size; |
228 | fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis, | |
229 | SCALE (size), LABEL (size)); | |
230 | ||
231 | size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d); | |
232 | total += size; | |
233 | fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args, | |
234 | SCALE (size), LABEL (size)); | |
235 | ||
236 | fprintf (file, "---------------------------------------------------------\n"); | |
237 | fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total), | |
238 | LABEL (total)); | |
239 | fprintf (file, "---------------------------------------------------------\n"); | |
240 | fprintf (file, "\n"); | |
241 | ||
242 | if (dfa_stats.num_phis) | |
726a989a | 243 | fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n", |
6de9cd9a | 244 | (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis, |
726a989a | 245 | (long) dfa_stats.max_num_phi_args); |
6de9cd9a DN |
246 | |
247 | fprintf (file, "\n"); | |
248 | } | |
249 | ||
250 | ||
251 | /* Dump DFA statistics on stderr. */ | |
252 | ||
24e47c76 | 253 | DEBUG_FUNCTION void |
6de9cd9a DN |
254 | debug_dfa_stats (void) |
255 | { | |
256 | dump_dfa_stats (stderr); | |
257 | } | |
258 | ||
259 | ||
206048bd | 260 | /* Collect DFA statistics and store them in the structure pointed to by |
6de9cd9a DN |
261 | DFA_STATS_P. */ |
262 | ||
263 | static void | |
726a989a | 264 | collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED) |
6de9cd9a | 265 | { |
6de9cd9a | 266 | basic_block bb; |
6de9cd9a | 267 | |
1e128c5f | 268 | gcc_assert (dfa_stats_p); |
6de9cd9a DN |
269 | |
270 | memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d)); | |
271 | ||
726a989a | 272 | /* Walk all the statements in the function counting references. */ |
6de9cd9a DN |
273 | FOR_EACH_BB (bb) |
274 | { | |
726a989a RB |
275 | gimple_stmt_iterator si; |
276 | ||
277 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) | |
6de9cd9a | 278 | { |
726a989a | 279 | gimple phi = gsi_stmt (si); |
6de9cd9a | 280 | dfa_stats_p->num_phis++; |
726a989a RB |
281 | dfa_stats_p->num_phi_args += gimple_phi_num_args (phi); |
282 | if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args) | |
283 | dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi); | |
6de9cd9a | 284 | } |
6de9cd9a | 285 | |
726a989a | 286 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
6de9cd9a | 287 | { |
726a989a RB |
288 | gimple stmt = gsi_stmt (si); |
289 | dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF); | |
290 | dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE); | |
5006671f RG |
291 | dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0; |
292 | dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0; | |
6de9cd9a DN |
293 | } |
294 | } | |
6de9cd9a DN |
295 | } |
296 | ||
297 | ||
298 | /*--------------------------------------------------------------------------- | |
299 | Miscellaneous helpers | |
300 | ---------------------------------------------------------------------------*/ | |
a3648cfc | 301 | |
86051306 JH |
302 | /* Lookup VAR UID in the default_defs hashtable and return the associated |
303 | variable. */ | |
304 | ||
b8698a0f | 305 | tree |
32244553 | 306 | ssa_default_def (struct function *fn, tree var) |
86051306 | 307 | { |
e445a2ff RG |
308 | struct tree_decl_minimal ind; |
309 | struct tree_ssa_name in; | |
32244553 RG |
310 | gcc_assert (TREE_CODE (var) == VAR_DECL |
311 | || TREE_CODE (var) == PARM_DECL | |
312 | || TREE_CODE (var) == RESULT_DECL); | |
e445a2ff RG |
313 | in.var = (tree)&ind; |
314 | ind.uid = DECL_UID (var); | |
315 | return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var)); | |
86051306 JH |
316 | } |
317 | ||
32244553 RG |
318 | /* Insert the pair VAR's UID, DEF into the default_defs hashtable |
319 | of function FN. */ | |
86051306 JH |
320 | |
321 | void | |
32244553 | 322 | set_ssa_default_def (struct function *fn, tree var, tree def) |
b8698a0f | 323 | { |
e445a2ff RG |
324 | struct tree_decl_minimal ind; |
325 | struct tree_ssa_name in; | |
86051306 JH |
326 | void **loc; |
327 | ||
32244553 RG |
328 | gcc_assert (TREE_CODE (var) == VAR_DECL |
329 | || TREE_CODE (var) == PARM_DECL | |
330 | || TREE_CODE (var) == RESULT_DECL); | |
e445a2ff RG |
331 | in.var = (tree)&ind; |
332 | ind.uid = DECL_UID (var); | |
333 | if (!def) | |
86051306 | 334 | { |
32244553 RG |
335 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (fn), &in, |
336 | DECL_UID (var), NO_INSERT); | |
337 | if (*loc) | |
01c59d23 RG |
338 | { |
339 | SSA_NAME_IS_DEFAULT_DEF (*(tree *)loc) = false; | |
340 | htab_clear_slot (DEFAULT_DEFS (fn), loc); | |
341 | } | |
86051306 JH |
342 | return; |
343 | } | |
e445a2ff | 344 | gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var); |
32244553 | 345 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (fn), &in, |
5cd4ec7f | 346 | DECL_UID (var), INSERT); |
38635499 | 347 | |
86051306 | 348 | /* Default definition might be changed by tail call optimization. */ |
e445a2ff RG |
349 | if (*loc) |
350 | SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false; | |
cfaab3a9 DN |
351 | |
352 | /* Mark DEF as the default definition for VAR. */ | |
32244553 | 353 | *(tree *) loc = def; |
01c59d23 | 354 | SSA_NAME_IS_DEFAULT_DEF (def) = true; |
86051306 JH |
355 | } |
356 | ||
32244553 RG |
357 | /* Retrieve or create a default definition for VAR. */ |
358 | ||
359 | tree | |
360 | get_or_create_ssa_default_def (struct function *fn, tree var) | |
361 | { | |
362 | tree ddef = ssa_default_def (fn, var); | |
363 | if (ddef == NULL_TREE) | |
364 | { | |
f3a1fb91 MJ |
365 | ddef = make_ssa_name_fn (fn, var, gimple_build_nop ()); |
366 | set_ssa_default_def (fn, var, ddef); | |
32244553 RG |
367 | } |
368 | return ddef; | |
369 | } | |
370 | ||
6de9cd9a | 371 | |
cfaab3a9 | 372 | /* If EXP is a handled component reference for a structure, return the |
6bec9271 RG |
373 | base variable. The access range is delimited by bit positions *POFFSET and |
374 | *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either | |
375 | *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE | |
376 | and *PMAX_SIZE are equal, the access is non-variable. */ | |
c75ab022 DB |
377 | |
378 | tree | |
6bec9271 RG |
379 | get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, |
380 | HOST_WIDE_INT *psize, | |
381 | HOST_WIDE_INT *pmax_size) | |
c75ab022 | 382 | { |
6bec9271 RG |
383 | HOST_WIDE_INT bitsize = -1; |
384 | HOST_WIDE_INT maxsize = -1; | |
385 | tree size_tree = NULL_TREE; | |
ca8d9092 EB |
386 | double_int bit_offset = double_int_zero; |
387 | HOST_WIDE_INT hbit_offset; | |
00e85045 | 388 | bool seen_variable_array_ref = false; |
90ff582f | 389 | tree base_type; |
6bec9271 | 390 | |
6bec9271 RG |
391 | /* First get the final access size from just the outermost expression. */ |
392 | if (TREE_CODE (exp) == COMPONENT_REF) | |
393 | size_tree = DECL_SIZE (TREE_OPERAND (exp, 1)); | |
394 | else if (TREE_CODE (exp) == BIT_FIELD_REF) | |
395 | size_tree = TREE_OPERAND (exp, 1); | |
55b34b5f | 396 | else if (!VOID_TYPE_P (TREE_TYPE (exp))) |
c75ab022 | 397 | { |
6bec9271 RG |
398 | enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp)); |
399 | if (mode == BLKmode) | |
400 | size_tree = TYPE_SIZE (TREE_TYPE (exp)); | |
401 | else | |
402 | bitsize = GET_MODE_BITSIZE (mode); | |
c75ab022 | 403 | } |
6bec9271 | 404 | if (size_tree != NULL_TREE) |
c75ab022 | 405 | { |
6bec9271 RG |
406 | if (! host_integerp (size_tree, 1)) |
407 | bitsize = -1; | |
408 | else | |
409 | bitsize = TREE_INT_CST_LOW (size_tree); | |
c75ab022 | 410 | } |
6bec9271 RG |
411 | |
412 | /* Initially, maxsize is the same as the accessed element size. | |
413 | In the following it will only grow (or become -1). */ | |
414 | maxsize = bitsize; | |
415 | ||
416 | /* Compute cumulative bit-offset for nested component-refs and array-refs, | |
417 | and find the ultimate containing object. */ | |
418 | while (1) | |
419 | { | |
90ff582f RG |
420 | base_type = TREE_TYPE (exp); |
421 | ||
6bec9271 RG |
422 | switch (TREE_CODE (exp)) |
423 | { | |
424 | case BIT_FIELD_REF: | |
27bcd47c | 425 | bit_offset += tree_to_double_int (TREE_OPERAND (exp, 2)); |
6bec9271 RG |
426 | break; |
427 | ||
428 | case COMPONENT_REF: | |
429 | { | |
430 | tree field = TREE_OPERAND (exp, 1); | |
431 | tree this_offset = component_ref_field_offset (exp); | |
432 | ||
ca8d9092 | 433 | if (this_offset && TREE_CODE (this_offset) == INTEGER_CST) |
6bec9271 | 434 | { |
ca8d9092 | 435 | double_int doffset = tree_to_double_int (this_offset); |
07bfc9ec RB |
436 | doffset = doffset.lshift (BITS_PER_UNIT == 8 |
437 | ? 3 : exact_log2 (BITS_PER_UNIT)); | |
27bcd47c LC |
438 | doffset += tree_to_double_int (DECL_FIELD_BIT_OFFSET (field)); |
439 | bit_offset = bit_offset + doffset; | |
79441eca RG |
440 | |
441 | /* If we had seen a variable array ref already and we just | |
442 | referenced the last field of a struct or a union member | |
443 | then we have to adjust maxsize by the padding at the end | |
444 | of our field. */ | |
ca8d9092 | 445 | if (seen_variable_array_ref && maxsize != -1) |
79441eca RG |
446 | { |
447 | tree stype = TREE_TYPE (TREE_OPERAND (exp, 0)); | |
910ad8de | 448 | tree next = DECL_CHAIN (field); |
79441eca | 449 | while (next && TREE_CODE (next) != FIELD_DECL) |
910ad8de | 450 | next = DECL_CHAIN (next); |
79441eca RG |
451 | if (!next |
452 | || TREE_CODE (stype) != RECORD_TYPE) | |
453 | { | |
454 | tree fsize = DECL_SIZE_UNIT (field); | |
455 | tree ssize = TYPE_SIZE_UNIT (stype); | |
456 | if (host_integerp (fsize, 0) | |
ca8d9092 | 457 | && host_integerp (ssize, 0) |
27bcd47c | 458 | && doffset.fits_shwi ()) |
79441eca RG |
459 | maxsize += ((TREE_INT_CST_LOW (ssize) |
460 | - TREE_INT_CST_LOW (fsize)) | |
ca8d9092 | 461 | * BITS_PER_UNIT |
27bcd47c | 462 | - doffset.to_shwi ()); |
79441eca RG |
463 | else |
464 | maxsize = -1; | |
465 | } | |
466 | } | |
6bec9271 RG |
467 | } |
468 | else | |
469 | { | |
470 | tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
471 | /* We need to adjust maxsize to the whole structure bitsize. | |
fa10beec | 472 | But we can subtract any constant offset seen so far, |
6bec9271 | 473 | because that would get us out of the structure otherwise. */ |
ca8d9092 EB |
474 | if (maxsize != -1 |
475 | && csize | |
476 | && host_integerp (csize, 1) | |
27bcd47c | 477 | && bit_offset.fits_shwi ()) |
ca8d9092 | 478 | maxsize = TREE_INT_CST_LOW (csize) |
27bcd47c | 479 | - bit_offset.to_shwi (); |
6bec9271 RG |
480 | else |
481 | maxsize = -1; | |
482 | } | |
483 | } | |
484 | break; | |
485 | ||
486 | case ARRAY_REF: | |
487 | case ARRAY_RANGE_REF: | |
488 | { | |
489 | tree index = TREE_OPERAND (exp, 1); | |
821bb7f8 | 490 | tree low_bound, unit_size; |
6bec9271 | 491 | |
c21c775a | 492 | /* If the resulting bit-offset is constant, track it. */ |
821bb7f8 | 493 | if (TREE_CODE (index) == INTEGER_CST |
821bb7f8 | 494 | && (low_bound = array_ref_low_bound (exp), |
b48e22b2 | 495 | TREE_CODE (low_bound) == INTEGER_CST) |
821bb7f8 | 496 | && (unit_size = array_ref_element_size (exp), |
ca8d9092 | 497 | TREE_CODE (unit_size) == INTEGER_CST)) |
6bec9271 | 498 | { |
ca8d9092 | 499 | double_int doffset |
27bcd47c LC |
500 | = (TREE_INT_CST (index) - TREE_INT_CST (low_bound)) |
501 | .sext (TYPE_PRECISION (TREE_TYPE (index))); | |
502 | doffset *= tree_to_double_int (unit_size); | |
07bfc9ec RB |
503 | doffset = doffset.lshift (BITS_PER_UNIT == 8 |
504 | ? 3 : exact_log2 (BITS_PER_UNIT)); | |
27bcd47c | 505 | bit_offset = bit_offset + doffset; |
00e85045 RG |
506 | |
507 | /* An array ref with a constant index up in the structure | |
508 | hierarchy will constrain the size of any variable array ref | |
509 | lower in the access hierarchy. */ | |
510 | seen_variable_array_ref = false; | |
6bec9271 RG |
511 | } |
512 | else | |
513 | { | |
514 | tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
515 | /* We need to adjust maxsize to the whole array bitsize. | |
fa10beec | 516 | But we can subtract any constant offset seen so far, |
6bec9271 | 517 | because that would get us outside of the array otherwise. */ |
ca8d9092 EB |
518 | if (maxsize != -1 |
519 | && asize | |
520 | && host_integerp (asize, 1) | |
27bcd47c | 521 | && bit_offset.fits_shwi ()) |
ca8d9092 | 522 | maxsize = TREE_INT_CST_LOW (asize) |
27bcd47c | 523 | - bit_offset.to_shwi (); |
6bec9271 RG |
524 | else |
525 | maxsize = -1; | |
00e85045 RG |
526 | |
527 | /* Remember that we have seen an array ref with a variable | |
528 | index. */ | |
529 | seen_variable_array_ref = true; | |
6bec9271 RG |
530 | } |
531 | } | |
532 | break; | |
533 | ||
534 | case REALPART_EXPR: | |
535 | break; | |
536 | ||
537 | case IMAGPART_EXPR: | |
27bcd47c | 538 | bit_offset += double_int::from_uhwi (bitsize); |
6bec9271 RG |
539 | break; |
540 | ||
541 | case VIEW_CONVERT_EXPR: | |
6bec9271 RG |
542 | break; |
543 | ||
70f34814 RG |
544 | case MEM_REF: |
545 | /* Hand back the decl for MEM[&decl, off]. */ | |
546 | if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR) | |
547 | { | |
548 | if (integer_zerop (TREE_OPERAND (exp, 1))) | |
549 | exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); | |
550 | else | |
551 | { | |
552 | double_int off = mem_ref_offset (exp); | |
07bfc9ec RB |
553 | off = off.lshift (BITS_PER_UNIT == 8 |
554 | ? 3 : exact_log2 (BITS_PER_UNIT)); | |
27bcd47c LC |
555 | off = off + bit_offset; |
556 | if (off.fits_shwi ()) | |
70f34814 | 557 | { |
ca8d9092 | 558 | bit_offset = off; |
70f34814 RG |
559 | exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); |
560 | } | |
561 | } | |
562 | } | |
563 | goto done; | |
564 | ||
4b228e61 RG |
565 | case TARGET_MEM_REF: |
566 | /* Hand back the decl for MEM[&decl, off]. */ | |
4d948885 | 567 | if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR) |
4b228e61 | 568 | { |
4d948885 | 569 | /* Via the variable index or index2 we can reach the |
23a534a1 | 570 | whole object. */ |
4d948885 | 571 | if (TMR_INDEX (exp) || TMR_INDEX2 (exp)) |
4b228e61 | 572 | { |
4d948885 | 573 | exp = TREE_OPERAND (TMR_BASE (exp), 0); |
ca8d9092 | 574 | bit_offset = double_int_zero; |
4b228e61 RG |
575 | maxsize = -1; |
576 | goto done; | |
577 | } | |
578 | if (integer_zerop (TMR_OFFSET (exp))) | |
4d948885 | 579 | exp = TREE_OPERAND (TMR_BASE (exp), 0); |
4b228e61 RG |
580 | else |
581 | { | |
582 | double_int off = mem_ref_offset (exp); | |
07bfc9ec RB |
583 | off = off.lshift (BITS_PER_UNIT == 8 |
584 | ? 3 : exact_log2 (BITS_PER_UNIT)); | |
27bcd47c LC |
585 | off += bit_offset; |
586 | if (off.fits_shwi ()) | |
4b228e61 | 587 | { |
ca8d9092 | 588 | bit_offset = off; |
4d948885 | 589 | exp = TREE_OPERAND (TMR_BASE (exp), 0); |
4b228e61 RG |
590 | } |
591 | } | |
592 | } | |
593 | goto done; | |
594 | ||
6bec9271 RG |
595 | default: |
596 | goto done; | |
597 | } | |
598 | ||
599 | exp = TREE_OPERAND (exp, 0); | |
600 | } | |
601 | done: | |
602 | ||
27bcd47c | 603 | if (!bit_offset.fits_shwi ()) |
ca8d9092 EB |
604 | { |
605 | *poffset = 0; | |
606 | *psize = bitsize; | |
607 | *pmax_size = -1; | |
608 | ||
609 | return exp; | |
610 | } | |
611 | ||
27bcd47c | 612 | hbit_offset = bit_offset.to_shwi (); |
ca8d9092 | 613 | |
00e85045 RG |
614 | /* We need to deal with variable arrays ending structures such as |
615 | struct { int length; int a[1]; } x; x.a[d] | |
616 | struct { struct { int a; int b; } a[1]; } x; x.a[d].a | |
617 | struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] | |
2df373c2 | 618 | struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d] |
00e85045 RG |
619 | where we do not know maxsize for variable index accesses to |
620 | the array. The simplest way to conservatively deal with this | |
621 | is to punt in the case that offset + maxsize reaches the | |
2df373c2 | 622 | base type boundary. This needs to include possible trailing padding |
90ff582f RG |
623 | that is there for alignment purposes. */ |
624 | ||
625 | if (seen_variable_array_ref | |
626 | && maxsize != -1 | |
627 | && (!host_integerp (TYPE_SIZE (base_type), 1) | |
ca8d9092 | 628 | || (hbit_offset + maxsize |
90ff582f RG |
629 | == (signed) TREE_INT_CST_LOW (TYPE_SIZE (base_type))))) |
630 | maxsize = -1; | |
133f9369 | 631 | |
90ff582f | 632 | /* In case of a decl or constant base object we can do better. */ |
0230277c RG |
633 | |
634 | if (DECL_P (exp)) | |
635 | { | |
636 | /* If maxsize is unknown adjust it according to the size of the | |
637 | base decl. */ | |
638 | if (maxsize == -1 | |
639 | && host_integerp (DECL_SIZE (exp), 1)) | |
ca8d9092 | 640 | maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - hbit_offset; |
0230277c | 641 | } |
90ff582f RG |
642 | else if (CONSTANT_CLASS_P (exp)) |
643 | { | |
644 | /* If maxsize is unknown adjust it according to the size of the | |
645 | base type constant. */ | |
646 | if (maxsize == -1 | |
647 | && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)) | |
ca8d9092 | 648 | maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - hbit_offset; |
90ff582f | 649 | } |
00e85045 | 650 | |
6bec9271 RG |
651 | /* ??? Due to negative offsets in ARRAY_REF we can end up with |
652 | negative bit_offset here. We might want to store a zero offset | |
653 | in this case. */ | |
ca8d9092 | 654 | *poffset = hbit_offset; |
6bec9271 RG |
655 | *psize = bitsize; |
656 | *pmax_size = maxsize; | |
657 | ||
658 | return exp; | |
c75ab022 | 659 | } |
e9e0aa2c | 660 | |
70f34814 RG |
661 | /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that |
662 | denotes the starting address of the memory access EXP. | |
663 | Returns NULL_TREE if the offset is not constant or any component | |
664 | is not BITS_PER_UNIT-aligned. */ | |
665 | ||
666 | tree | |
667 | get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset) | |
668 | { | |
cfef45c8 | 669 | return get_addr_base_and_unit_offset_1 (exp, poffset, NULL); |
70f34814 RG |
670 | } |
671 | ||
2e58df6e RG |
672 | /* Returns true if STMT references an SSA_NAME that has |
673 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ | |
674 | ||
675 | bool | |
726a989a | 676 | stmt_references_abnormal_ssa_name (gimple stmt) |
2e58df6e RG |
677 | { |
678 | ssa_op_iter oi; | |
679 | use_operand_p use_p; | |
680 | ||
681 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) | |
682 | { | |
683 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) | |
684 | return true; | |
685 | } | |
686 | ||
687 | return false; | |
688 | } | |
7ee2468b SB |
689 | |
690 | /* Pair of tree and a sorting index, for dump_enumerated_decls. */ | |
691 | struct GTY(()) numbered_tree_d | |
692 | { | |
693 | tree t; | |
694 | int num; | |
695 | }; | |
696 | typedef struct numbered_tree_d numbered_tree; | |
697 | ||
7ee2468b SB |
698 | |
699 | /* Compare two declarations references by their DECL_UID / sequence number. | |
700 | Called via qsort. */ | |
701 | ||
702 | static int | |
703 | compare_decls_by_uid (const void *pa, const void *pb) | |
704 | { | |
705 | const numbered_tree *nt_a = ((const numbered_tree *)pa); | |
706 | const numbered_tree *nt_b = ((const numbered_tree *)pb); | |
707 | ||
708 | if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t)) | |
709 | return DECL_UID (nt_a->t) - DECL_UID (nt_b->t); | |
710 | return nt_a->num - nt_b->num; | |
711 | } | |
712 | ||
713 | /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */ | |
714 | static tree | |
715 | dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data) | |
716 | { | |
717 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; | |
9771b263 | 718 | vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info; |
7ee2468b SB |
719 | numbered_tree nt; |
720 | ||
721 | if (!DECL_P (*tp)) | |
722 | return NULL_TREE; | |
723 | nt.t = *tp; | |
9771b263 DN |
724 | nt.num = list->length (); |
725 | list->safe_push (nt); | |
7ee2468b SB |
726 | *walk_subtrees = 0; |
727 | return NULL_TREE; | |
728 | } | |
729 | ||
730 | /* Find all the declarations used by the current function, sort them by uid, | |
731 | and emit the sorted list. Each declaration is tagged with a sequence | |
732 | number indicating when it was found during statement / tree walking, | |
733 | so that TDF_NOUID comparisons of anonymous declarations are still | |
734 | meaningful. Where a declaration was encountered more than once, we | |
735 | emit only the sequence number of the first encounter. | |
736 | FILE is the dump file where to output the list and FLAGS is as in | |
737 | print_generic_expr. */ | |
738 | void | |
739 | dump_enumerated_decls (FILE *file, int flags) | |
740 | { | |
741 | basic_block bb; | |
742 | struct walk_stmt_info wi; | |
9771b263 DN |
743 | vec<numbered_tree> decl_list; |
744 | decl_list.create (40); | |
7ee2468b SB |
745 | |
746 | memset (&wi, '\0', sizeof (wi)); | |
9771b263 | 747 | wi.info = (void *) &decl_list; |
7ee2468b SB |
748 | FOR_EACH_BB (bb) |
749 | { | |
750 | gimple_stmt_iterator gsi; | |
751 | ||
752 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
753 | if (!is_gimple_debug (gsi_stmt (gsi))) | |
754 | walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi); | |
755 | } | |
9771b263 DN |
756 | decl_list.qsort (compare_decls_by_uid); |
757 | if (decl_list.length ()) | |
7ee2468b SB |
758 | { |
759 | unsigned ix; | |
760 | numbered_tree *ntp; | |
761 | tree last = NULL_TREE; | |
762 | ||
763 | fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n", | |
764 | current_function_name ()); | |
9771b263 | 765 | FOR_EACH_VEC_ELT (decl_list, ix, ntp) |
7ee2468b SB |
766 | { |
767 | if (ntp->t == last) | |
768 | continue; | |
769 | fprintf (file, "%d: ", ntp->num); | |
770 | print_generic_decl (file, ntp->t, flags); | |
771 | fprintf (file, "\n"); | |
772 | last = ntp->t; | |
773 | } | |
774 | } | |
9771b263 | 775 | decl_list.release (); |
7ee2468b | 776 | } |