Line data Source code
1 : /* Data flow functions for trees.
2 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
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
9 : the Free Software Foundation; either version 3, or (at your option)
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
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "rtl.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "tree-pass.h"
29 : #include "ssa.h"
30 : #include "tree-pretty-print.h"
31 : #include "fold-const.h"
32 : #include "stor-layout.h"
33 : #include "langhooks.h"
34 : #include "gimple-iterator.h"
35 : #include "gimple-walk.h"
36 : #include "tree-dfa.h"
37 : #include "gimple-range.h"
38 :
39 : /* Build and maintain data flow information for trees. */
40 :
41 : /* Counters used to display DFA and SSA statistics. */
42 : struct dfa_stats_d
43 : {
44 : long num_defs;
45 : long num_uses;
46 : long num_phis;
47 : long num_phi_args;
48 : size_t max_num_phi_args;
49 : long num_vdefs;
50 : long num_vuses;
51 : };
52 :
53 :
54 : /* Local functions. */
55 : static void collect_dfa_stats (struct dfa_stats_d *);
56 :
57 :
58 : /*---------------------------------------------------------------------------
59 : Dataflow analysis (DFA) routines
60 : ---------------------------------------------------------------------------*/
61 :
62 : /* Renumber the gimple stmt uids in one block. The caller is responsible
63 : of calling set_gimple_stmt_max_uid (fun, 0) at some point. */
64 :
65 : void
66 76745474 : renumber_gimple_stmt_uids_in_block (struct function *fun, basic_block bb)
67 : {
68 76745474 : gimple_stmt_iterator bsi;
69 103792823 : for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
70 : {
71 27047349 : gimple *stmt = gsi_stmt (bsi);
72 27047349 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
73 : }
74 657539620 : for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
75 : {
76 504048672 : gimple *stmt = gsi_stmt (bsi);
77 504048672 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
78 : }
79 76745474 : }
80 :
81 : /* Renumber all of the gimple stmt uids. */
82 :
83 : void
84 6770889 : renumber_gimple_stmt_uids (struct function *fun)
85 : {
86 6770889 : basic_block bb;
87 :
88 6770889 : set_gimple_stmt_max_uid (fun, 0);
89 78998174 : FOR_ALL_BB_FN (bb, fun)
90 72227285 : renumber_gimple_stmt_uids_in_block (fun, bb);
91 6770889 : }
92 :
93 : /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
94 : in BLOCKS, of which there are N_BLOCKS. Also renumbers PHIs. */
95 :
96 : void
97 643581 : renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
98 : {
99 643581 : int i;
100 :
101 643581 : set_gimple_stmt_max_uid (cfun, 0);
102 4779144 : for (i = 0; i < n_blocks; i++)
103 4135563 : renumber_gimple_stmt_uids_in_block (cfun, blocks[i]);
104 643581 : }
105 :
106 :
107 :
108 : /*---------------------------------------------------------------------------
109 : Debugging functions
110 : ---------------------------------------------------------------------------*/
111 :
112 : /* Dump variable VAR and its may-aliases to FILE. */
113 :
114 : void
115 351 : dump_variable (FILE *file, tree var)
116 : {
117 351 : if (TREE_CODE (var) == SSA_NAME)
118 : {
119 0 : if (POINTER_TYPE_P (TREE_TYPE (var)))
120 0 : dump_points_to_info_for (file, var);
121 0 : var = SSA_NAME_VAR (var);
122 : }
123 :
124 : if (var == NULL_TREE)
125 : {
126 0 : fprintf (file, "<nil>");
127 0 : return;
128 : }
129 :
130 351 : print_generic_expr (file, var, dump_flags);
131 :
132 351 : fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
133 351 : if (DECL_PT_UID (var) != DECL_UID (var))
134 0 : fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
135 :
136 351 : fprintf (file, ", ");
137 351 : print_generic_expr (file, TREE_TYPE (var), dump_flags);
138 :
139 351 : if (TREE_ADDRESSABLE (var))
140 351 : fprintf (file, ", is addressable");
141 :
142 351 : if (is_global_var (var))
143 63 : fprintf (file, ", is global");
144 :
145 351 : if (TREE_THIS_VOLATILE (var))
146 0 : fprintf (file, ", is volatile");
147 :
148 351 : if (cfun && ssa_default_def (cfun, var))
149 : {
150 0 : fprintf (file, ", default def: ");
151 0 : print_generic_expr (file, ssa_default_def (cfun, var), dump_flags);
152 : }
153 :
154 351 : if (DECL_INITIAL (var))
155 : {
156 63 : fprintf (file, ", initial: ");
157 63 : print_generic_expr (file, DECL_INITIAL (var), dump_flags);
158 : }
159 :
160 351 : fprintf (file, "\n");
161 : }
162 :
163 :
164 : /* Dump variable VAR and its may-aliases to stderr. */
165 :
166 : DEBUG_FUNCTION void
167 0 : debug_variable (tree var)
168 : {
169 0 : dump_variable (stderr, var);
170 0 : }
171 :
172 :
173 : /* Dump various DFA statistics to FILE. */
174 :
175 : void
176 492 : dump_dfa_stats (FILE *file)
177 : {
178 492 : struct dfa_stats_d dfa_stats;
179 :
180 492 : unsigned long size, total = 0;
181 492 : const char * const fmt_str = "%-30s%-13s%12s\n";
182 492 : const char * const fmt_str_1 = "%-30s%13lu" PRsa (11) "\n";
183 492 : const char * const fmt_str_3 = "%-43s" PRsa (11) "\n";
184 492 : const char *funcname
185 492 : = lang_hooks.decl_printable_name (current_function_decl, 2);
186 :
187 492 : collect_dfa_stats (&dfa_stats);
188 :
189 492 : fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
190 :
191 492 : fprintf (file, "---------------------------------------------------------\n");
192 492 : fprintf (file, fmt_str, "", " Number of ", "Memory");
193 492 : fprintf (file, fmt_str, "", " instances ", "used ");
194 492 : fprintf (file, "---------------------------------------------------------\n");
195 :
196 492 : size = dfa_stats.num_uses * sizeof (tree *);
197 492 : total += size;
198 492 : fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
199 0 : SIZE_AMOUNT (size));
200 :
201 492 : size = dfa_stats.num_defs * sizeof (tree *);
202 492 : total += size;
203 492 : fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
204 0 : SIZE_AMOUNT (size));
205 :
206 492 : size = dfa_stats.num_vuses * sizeof (tree *);
207 492 : total += size;
208 492 : fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
209 0 : SIZE_AMOUNT (size));
210 :
211 492 : size = dfa_stats.num_vdefs * sizeof (tree *);
212 492 : total += size;
213 492 : fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
214 0 : SIZE_AMOUNT (size));
215 :
216 492 : size = dfa_stats.num_phis * sizeof (struct gphi);
217 492 : total += size;
218 494 : fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
219 4 : SIZE_AMOUNT (size));
220 :
221 492 : size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
222 492 : total += size;
223 494 : fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
224 4 : SIZE_AMOUNT (size));
225 :
226 492 : fprintf (file, "---------------------------------------------------------\n");
227 508 : fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data",
228 32 : SIZE_AMOUNT (total));
229 492 : fprintf (file, "---------------------------------------------------------\n");
230 492 : fprintf (file, "\n");
231 :
232 492 : if (dfa_stats.num_phis)
233 485 : fprintf (file, "Average number of arguments per PHI node: %.1f (max: "
234 : HOST_SIZE_T_PRINT_DEC ")\n",
235 485 : (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
236 485 : (fmt_size_t) dfa_stats.max_num_phi_args);
237 :
238 492 : fprintf (file, "\n");
239 492 : }
240 :
241 :
242 : /* Dump DFA statistics on stderr. */
243 :
244 : DEBUG_FUNCTION void
245 0 : debug_dfa_stats (void)
246 : {
247 0 : dump_dfa_stats (stderr);
248 0 : }
249 :
250 :
251 : /* Collect DFA statistics and store them in the structure pointed to by
252 : DFA_STATS_P. */
253 :
254 : static void
255 492 : collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
256 : {
257 492 : basic_block bb;
258 :
259 492 : gcc_assert (dfa_stats_p);
260 :
261 492 : memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
262 :
263 : /* Walk all the statements in the function counting references. */
264 8601 : FOR_EACH_BB_FN (bb, cfun)
265 : {
266 13424 : for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
267 5315 : gsi_next (&si))
268 : {
269 5315 : gphi *phi = si.phi ();
270 5315 : dfa_stats_p->num_phis++;
271 5315 : dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
272 5315 : if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
273 675 : dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
274 : }
275 :
276 30739 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
277 14521 : gsi_next (&si))
278 : {
279 14521 : gimple *stmt = gsi_stmt (si);
280 14521 : dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
281 14521 : dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
282 27038 : dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
283 27038 : dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
284 : }
285 : }
286 492 : }
287 :
288 :
289 : /*---------------------------------------------------------------------------
290 : Miscellaneous helpers
291 : ---------------------------------------------------------------------------*/
292 :
293 : /* Lookup VAR UID in the default_defs hashtable and return the associated
294 : variable. */
295 :
296 : tree
297 585497848 : ssa_default_def (struct function *fn, tree var)
298 : {
299 585497848 : struct tree_decl_minimal ind;
300 585497848 : struct tree_ssa_name in;
301 585497848 : gcc_assert (VAR_P (var)
302 : || TREE_CODE (var) == PARM_DECL
303 : || TREE_CODE (var) == RESULT_DECL);
304 :
305 : /* Always NULL_TREE for rtl function dumps. */
306 585497848 : if (!fn->gimple_df)
307 : return NULL_TREE;
308 :
309 585497848 : in.var = (tree)&ind;
310 585497848 : ind.uid = DECL_UID (var);
311 585497848 : return DEFAULT_DEFS (fn)->find_with_hash ((tree)&in, DECL_UID (var));
312 : }
313 :
314 : /* Insert the pair VAR's UID, DEF into the default_defs hashtable
315 : of function FN. */
316 :
317 : void
318 12849684 : set_ssa_default_def (struct function *fn, tree var, tree def)
319 : {
320 12849684 : struct tree_decl_minimal ind;
321 12849684 : struct tree_ssa_name in;
322 :
323 12849684 : gcc_assert (VAR_P (var)
324 : || TREE_CODE (var) == PARM_DECL
325 : || TREE_CODE (var) == RESULT_DECL);
326 12849684 : in.var = (tree)&ind;
327 12849684 : ind.uid = DECL_UID (var);
328 12849684 : if (!def)
329 : {
330 3589494 : tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
331 1196498 : DECL_UID (var),
332 : NO_INSERT);
333 1196498 : if (loc)
334 : {
335 1196460 : SSA_NAME_IS_DEFAULT_DEF (*(tree *)loc) = false;
336 1196460 : DEFAULT_DEFS (fn)->clear_slot (loc);
337 : }
338 1196498 : return;
339 : }
340 11653186 : gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
341 34959558 : tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
342 11653186 : DECL_UID (var), INSERT);
343 :
344 : /* Default definition might be changed by tail call optimization. */
345 11653186 : if (*loc)
346 1659 : SSA_NAME_IS_DEFAULT_DEF (*loc) = false;
347 :
348 : /* Mark DEF as the default definition for VAR. */
349 11653186 : *loc = def;
350 11653186 : SSA_NAME_IS_DEFAULT_DEF (def) = true;
351 : }
352 :
353 : /* Retrieve or create a default definition for VAR. */
354 :
355 : tree
356 27978599 : get_or_create_ssa_default_def (struct function *fn, tree var)
357 : {
358 27978599 : tree ddef = ssa_default_def (fn, var);
359 27978599 : if (ddef == NULL_TREE)
360 : {
361 11111398 : ddef = make_ssa_name_fn (fn, var, gimple_build_nop ());
362 11111398 : set_ssa_default_def (fn, var, ddef);
363 : }
364 27978599 : return ddef;
365 : }
366 :
367 :
368 : /* If EXP is a handled component reference for a structure, return the
369 : base variable. The access range is delimited by bit positions *POFFSET and
370 : *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
371 : *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
372 : and *PMAX_SIZE are equal, the access is non-variable. If *PREVERSE is
373 : true, the storage order of the reference is reversed. */
374 :
375 : tree
376 3245689063 : get_ref_base_and_extent (tree exp, poly_int64 *poffset,
377 : poly_int64 *psize,
378 : poly_int64 *pmax_size,
379 : bool *preverse)
380 : {
381 3245689063 : poly_offset_int bitsize = -1;
382 3245689063 : poly_offset_int maxsize;
383 3245689063 : tree size_tree = NULL_TREE;
384 3245689063 : poly_offset_int bit_offset = 0;
385 3245689063 : bool seen_variable_array_ref = false;
386 :
387 : /* First get the final access size and the storage order from just the
388 : outermost expression. */
389 3245689063 : if (TREE_CODE (exp) == COMPONENT_REF)
390 1583342196 : size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
391 1662346867 : else if (TREE_CODE (exp) == BIT_FIELD_REF)
392 8607991 : size_tree = TREE_OPERAND (exp, 1);
393 1653738876 : else if (TREE_CODE (exp) == WITH_SIZE_EXPR)
394 : {
395 174 : size_tree = TREE_OPERAND (exp, 1);
396 174 : exp = TREE_OPERAND (exp, 0);
397 : }
398 1653738702 : else if (!VOID_TYPE_P (TREE_TYPE (exp)))
399 : {
400 1611675546 : machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
401 1611675546 : if (mode == BLKmode)
402 386444459 : size_tree = TYPE_SIZE (TREE_TYPE (exp));
403 : else
404 2450462174 : bitsize = GET_MODE_BITSIZE (mode);
405 : }
406 1225231087 : if (size_tree != NULL_TREE
407 1978394820 : && poly_int_tree_p (size_tree))
408 1978012046 : bitsize = wi::to_poly_offset (size_tree);
409 :
410 3245689063 : *preverse = reverse_storage_order_for_component_p (exp);
411 :
412 : /* Initially, maxsize is the same as the accessed element size.
413 : In the following it will only grow (or become -1). */
414 3245689063 : maxsize = bitsize;
415 :
416 : /* Compute cumulative bit-offset for nested component-refs and array-refs,
417 : and find the ultimate containing object. */
418 9498067187 : while (1)
419 : {
420 6371878125 : switch (TREE_CODE (exp))
421 : {
422 8607991 : case BIT_FIELD_REF:
423 8607991 : bit_offset += wi::to_poly_offset (TREE_OPERAND (exp, 2));
424 8607991 : break;
425 :
426 2352184572 : case COMPONENT_REF:
427 2352184572 : {
428 2352184572 : tree field = TREE_OPERAND (exp, 1);
429 2352184572 : tree this_offset = component_ref_field_offset (exp);
430 :
431 2352184572 : if (this_offset && poly_int_tree_p (this_offset))
432 : {
433 2352181522 : poly_offset_int woffset = (wi::to_poly_offset (this_offset)
434 2352181522 : << LOG2_BITS_PER_UNIT);
435 2352181522 : woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
436 2352181522 : bit_offset += woffset;
437 :
438 : /* If we had seen a variable array ref already and we just
439 : referenced the last field of a struct or a union member
440 : then we have to adjust maxsize by the padding at the end
441 : of our field. */
442 2352181522 : if (seen_variable_array_ref)
443 : {
444 21253370 : tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
445 21253370 : tree next = DECL_CHAIN (field);
446 63719011 : while (next && TREE_CODE (next) != FIELD_DECL)
447 42465641 : next = DECL_CHAIN (next);
448 21253370 : if (!next
449 3159757 : || TREE_CODE (stype) != RECORD_TYPE)
450 : {
451 18830216 : tree fsize = DECL_SIZE (field);
452 18830216 : tree ssize = TYPE_SIZE (stype);
453 18830216 : if (fsize == NULL
454 11801703 : || !poly_int_tree_p (fsize)
455 11799538 : || ssize == NULL
456 30629754 : || !poly_int_tree_p (ssize))
457 7030678 : maxsize = -1;
458 11799538 : else if (known_size_p (maxsize))
459 : {
460 11799388 : poly_offset_int tem
461 11799388 : = (wi::to_poly_offset (ssize)
462 11799388 : - wi::to_poly_offset (fsize));
463 23598776 : tem -= woffset;
464 11799388 : maxsize += tem;
465 : }
466 : }
467 : /* An component ref with an adjacent field up in the
468 : structure hierarchy constrains the size of any variable
469 : array ref lower in the access hierarchy. */
470 : else
471 : seen_variable_array_ref = false;
472 : }
473 : }
474 : else
475 : {
476 3050 : tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
477 : /* We need to adjust maxsize to the whole structure bitsize.
478 : But we can subtract any constant offset seen so far,
479 : because that would get us out of the structure otherwise. */
480 3050 : if (known_size_p (maxsize)
481 2041 : && csize
482 5091 : && poly_int_tree_p (csize))
483 0 : maxsize = wi::to_poly_offset (csize) - bit_offset;
484 : else
485 3050 : maxsize = -1;
486 : }
487 : }
488 : break;
489 :
490 748731755 : case ARRAY_REF:
491 748731755 : case ARRAY_RANGE_REF:
492 748731755 : {
493 748731755 : tree index = TREE_OPERAND (exp, 1);
494 748731755 : tree low_bound, unit_size;
495 :
496 : /* If the resulting bit-offset is constant, track it. */
497 748731755 : if (poly_int_tree_p (index)
498 645442101 : && (low_bound = array_ref_low_bound (exp),
499 645442101 : poly_int_tree_p (low_bound))
500 1394168804 : && (unit_size = array_ref_element_size (exp),
501 645437049 : TREE_CODE (unit_size) == INTEGER_CST))
502 : {
503 645365045 : poly_offset_int woffset
504 645365045 : = wi::sext (wi::to_poly_offset (index)
505 1290730090 : - wi::to_poly_offset (low_bound),
506 645365045 : TYPE_PRECISION (sizetype));
507 645365045 : woffset *= wi::to_offset (unit_size);
508 645365045 : woffset <<= LOG2_BITS_PER_UNIT;
509 645365045 : bit_offset += woffset;
510 :
511 : /* An array ref with a constant index up in the structure
512 : hierarchy will constrain the size of any variable array ref
513 : lower in the access hierarchy. */
514 645365045 : seen_variable_array_ref = false;
515 : }
516 : else
517 : {
518 103366710 : tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
519 : /* We need to adjust maxsize to the whole array bitsize.
520 : But we can subtract any constant offset seen so far,
521 : because that would get us outside of the array otherwise. */
522 103366710 : if (known_size_p (maxsize)
523 103164749 : && asize
524 185453017 : && poly_int_tree_p (asize))
525 79295942 : maxsize = wi::to_poly_offset (asize) - bit_offset;
526 : else
527 24070768 : maxsize = -1;
528 :
529 : /* Remember that we have seen an array ref with a variable
530 : index. */
531 103366710 : seen_variable_array_ref = true;
532 :
533 : /* Try to constrain the access range by using the range of the
534 : index expression when we know it. Extra care must be taken
535 : when the low bound of the array is not zero, because it may
536 : be very large and the index expression may be unsigned and
537 : wrap around; in this case, the correct range is that of the
538 : difference between the index expression and the low bound,
539 : see get_inner_reference for the model computation. */
540 103366710 : range_query *query = get_range_query (cfun);
541 103366710 : range_op_handler minus_op (MINUS_EXPR);
542 103366710 : int_range_max vr_idx, vr_lb, vr;
543 :
544 103366710 : if (TREE_CODE (index) == SSA_NAME
545 102860632 : && (low_bound = array_ref_low_bound (exp),
546 102860632 : TREE_CODE (low_bound) == INTEGER_CST)
547 102860320 : && (unit_size = array_ref_element_size (exp),
548 102860320 : TREE_CODE (unit_size) == INTEGER_CST)
549 102688660 : && query->range_of_expr (vr, index)
550 102688660 : && (integer_zerop (low_bound)
551 472757 : || ((vr_idx = vr,
552 472757 : query->range_of_expr (vr_lb, low_bound))
553 42516500 : && minus_op.fold_range (vr, TREE_TYPE (index),
554 : vr_idx, vr_lb)))
555 102688660 : && !vr.varying_p ()
556 164694874 : && !vr.undefined_p ())
557 : {
558 61322967 : wide_int min = vr.lower_bound ();
559 61322967 : wide_int max = vr.upper_bound ();
560 : /* Try to constrain maxsize with range information. */
561 61322967 : offset_int omax
562 61322967 : = offset_int::from (max, TYPE_SIGN (TREE_TYPE (index)));
563 61322967 : if (wi::get_precision (max) <= ADDR_MAX_BITSIZE
564 61322967 : && omax >= 0)
565 : {
566 61213246 : offset_int rmaxsize
567 61213246 : = (omax + 1)
568 122426492 : * wi::to_offset (unit_size) << LOG2_BITS_PER_UNIT;
569 61213246 : if (!known_size_p (maxsize)
570 108951308 : || known_lt (rmaxsize, maxsize))
571 : {
572 : /* If we know an upper bound below the declared
573 : one this is no longer variable. */
574 24680162 : if (known_size_p (maxsize))
575 : seen_variable_array_ref = false;
576 24680162 : maxsize = rmaxsize;
577 : }
578 : }
579 : /* Try to adjust bit_offset with range information. */
580 61322967 : offset_int omin
581 61322967 : = offset_int::from (min, TYPE_SIGN (TREE_TYPE (index)));
582 61322967 : if (wi::get_precision (min) <= ADDR_MAX_BITSIZE
583 61322967 : && omin > 0)
584 : {
585 16427743 : offset_int woffset
586 16427743 : = wi::sext (omin, TYPE_PRECISION (sizetype));
587 16427743 : woffset *= wi::to_offset (unit_size);
588 16427743 : woffset <<= LOG2_BITS_PER_UNIT;
589 16427743 : bit_offset += woffset;
590 16427743 : if (known_size_p (maxsize))
591 16427743 : maxsize -= woffset;
592 : }
593 61322967 : }
594 103366710 : }
595 : }
596 : break;
597 :
598 : case REALPART_EXPR:
599 : break;
600 :
601 : case IMAGPART_EXPR:
602 3126189062 : bit_offset += bitsize;
603 : break;
604 :
605 : case VIEW_CONVERT_EXPR:
606 : break;
607 :
608 55987096 : case TARGET_MEM_REF:
609 : /* Via the variable index or index2 we can reach the
610 : whole object. Still hand back the decl here. */
611 55987096 : if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
612 55987096 : && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
613 : {
614 6942864 : exp = TREE_OPERAND (TMR_BASE (exp), 0);
615 6942864 : bit_offset = 0;
616 6942864 : maxsize = -1;
617 6942864 : goto done;
618 : }
619 : /* Fallthru. */
620 1248730321 : case MEM_REF:
621 : /* We need to deal with variable arrays ending structures such as
622 : struct { int length; int a[1]; } x; x.a[d]
623 : struct { struct { int a; int b; } a[1]; } x; x.a[d].a
624 : struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
625 : struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
626 : where we do not know maxsize for variable index accesses to
627 : the array. The simplest way to conservatively deal with this
628 : is to punt in the case that offset + maxsize reaches the
629 : base type boundary. This needs to include possible trailing
630 : padding that is there for alignment purposes. */
631 1248730321 : if (seen_variable_array_ref
632 33025889 : && known_size_p (maxsize)
633 1267219552 : && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
634 11319898 : || !poly_int_tree_p (TYPE_SIZE (TREE_TYPE (exp)))
635 9604805 : || (maybe_eq
636 9604805 : (bit_offset + maxsize,
637 1258335126 : wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (exp)))))))
638 18489229 : maxsize = -1;
639 :
640 : /* Hand back the decl for MEM[&decl, off]. */
641 1248730321 : if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
642 : {
643 546014738 : if (integer_zerop (TREE_OPERAND (exp, 1)))
644 212195506 : exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
645 : else
646 : {
647 333819232 : poly_offset_int off = mem_ref_offset (exp);
648 333819232 : off <<= LOG2_BITS_PER_UNIT;
649 333819232 : off += bit_offset;
650 333819232 : poly_int64 off_hwi;
651 333819232 : if (off.to_shwi (&off_hwi))
652 : {
653 333817627 : bit_offset = off_hwi;
654 333817627 : exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
655 : }
656 : }
657 : }
658 1248730321 : goto done;
659 :
660 1990015878 : default:
661 1990015878 : goto done;
662 : }
663 :
664 3126189062 : exp = TREE_OPERAND (exp, 0);
665 3126189062 : }
666 :
667 3245689063 : done:
668 3245689063 : if (!bitsize.to_shwi (psize) || maybe_lt (*psize, 0))
669 : {
670 42445959 : *poffset = 0;
671 42445959 : *psize = -1;
672 42445959 : *pmax_size = -1;
673 :
674 42445959 : return exp;
675 : }
676 :
677 : /* ??? Due to negative offsets in ARRAY_REF we can end up with
678 : negative bit_offset here. We might want to store a zero offset
679 : in this case. */
680 3203243104 : if (!bit_offset.to_shwi (poffset))
681 : {
682 7279 : *poffset = 0;
683 7279 : *pmax_size = -1;
684 :
685 7279 : return exp;
686 : }
687 :
688 : /* In case of a decl or constant base object we can do better. */
689 :
690 3203235825 : if (DECL_P (exp))
691 : {
692 2470679699 : if (VAR_P (exp)
693 2470679699 : && ((flag_unconstrained_commons && DECL_COMMON (exp))
694 2408578980 : || (DECL_EXTERNAL (exp) && seen_variable_array_ref)))
695 : {
696 529444 : tree sz_tree = TYPE_SIZE (TREE_TYPE (exp));
697 : /* If size is unknown, or we have read to the end, assume there
698 : may be more to the structure than we are told. */
699 529444 : if (TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE
700 529444 : || (seen_variable_array_ref
701 35594 : && (sz_tree == NULL_TREE
702 35594 : || !poly_int_tree_p (sz_tree)
703 35594 : || maybe_eq (bit_offset + maxsize,
704 565038 : wi::to_poly_offset (sz_tree)))))
705 528746 : maxsize = -1;
706 : }
707 : /* If maxsize is unknown adjust it according to the size of the
708 : base decl. */
709 2470150255 : else if (!known_size_p (maxsize)
710 15029311 : && DECL_SIZE (exp)
711 2485175028 : && poly_int_tree_p (DECL_SIZE (exp)))
712 15024711 : maxsize = wi::to_poly_offset (DECL_SIZE (exp)) - bit_offset;
713 : }
714 732556126 : else if (CONSTANT_CLASS_P (exp))
715 : {
716 : /* If maxsize is unknown adjust it according to the size of the
717 : base type constant. */
718 7746988 : if (!known_size_p (maxsize)
719 35228 : && TYPE_SIZE (TREE_TYPE (exp))
720 7782216 : && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (exp))))
721 35228 : maxsize = (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (exp)))
722 35228 : - bit_offset);
723 : }
724 :
725 3203235825 : if (!maxsize.to_shwi (pmax_size)
726 3203235825 : || maybe_lt (*pmax_size, 0)
727 6381051256 : || !endpoint_representable_p (*poffset, *pmax_size))
728 25420431 : *pmax_size = -1;
729 :
730 : /* Punt if *POFFSET + *PSIZE overflows in HOST_WIDE_INT, the callers don't
731 : check for such overflows individually and assume it works. */
732 6406471650 : if (!endpoint_representable_p (*poffset, *psize))
733 : {
734 37 : *poffset = 0;
735 37 : *psize = -1;
736 37 : *pmax_size = -1;
737 :
738 37 : return exp;
739 : }
740 :
741 : return exp;
742 : }
743 :
744 : /* Like get_ref_base_and_extent, but for cases in which we only care
745 : about constant-width accesses at constant offsets. Return null
746 : if the access is anything else. */
747 :
748 : tree
749 50406657 : get_ref_base_and_extent_hwi (tree exp, HOST_WIDE_INT *poffset,
750 : HOST_WIDE_INT *psize, bool *preverse)
751 : {
752 50406657 : poly_int64 offset, size, max_size;
753 50406657 : HOST_WIDE_INT const_offset, const_size;
754 50406657 : bool reverse;
755 50406657 : tree decl = get_ref_base_and_extent (exp, &offset, &size, &max_size,
756 : &reverse);
757 50406657 : if (!offset.is_constant (&const_offset)
758 50406657 : || !size.is_constant (&const_size)
759 50406657 : || const_offset < 0
760 50405887 : || !known_size_p (max_size)
761 49874453 : || maybe_ne (max_size, const_size))
762 : return NULL_TREE;
763 :
764 48935947 : *poffset = const_offset;
765 48935947 : *psize = const_size;
766 48935947 : *preverse = reverse;
767 48935947 : return decl;
768 : }
769 :
770 : /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
771 : denotes the starting address of the memory access EXP.
772 : Returns NULL_TREE if the offset is not constant or any component
773 : is not BITS_PER_UNIT-aligned.
774 : VALUEIZE if non-NULL is used to valueize SSA names. It should return
775 : its argument or a constant if the argument is known to be constant. */
776 :
777 : tree
778 224434539 : get_addr_base_and_unit_offset_1 (tree exp, poly_int64 *poffset,
779 : tree (*valueize) (tree))
780 : {
781 224434539 : poly_int64 byte_offset = 0;
782 :
783 : /* Compute cumulative byte-offset for nested component-refs and array-refs,
784 : and find the ultimate containing object. */
785 342304957 : while (1)
786 : {
787 283369748 : switch (TREE_CODE (exp))
788 : {
789 21044 : case BIT_FIELD_REF:
790 21044 : {
791 21044 : poly_int64 this_byte_offset;
792 21044 : poly_uint64 this_bit_offset;
793 21044 : if (!poly_int_tree_p (TREE_OPERAND (exp, 2), &this_bit_offset)
794 42088 : || !multiple_p (this_bit_offset, BITS_PER_UNIT,
795 : &this_byte_offset))
796 0 : return NULL_TREE;
797 21044 : byte_offset += this_byte_offset;
798 : }
799 21044 : break;
800 :
801 54318363 : case COMPONENT_REF:
802 54318363 : {
803 54318363 : tree field = TREE_OPERAND (exp, 1);
804 54318363 : tree this_offset = component_ref_field_offset (exp);
805 54318363 : poly_int64 hthis_offset;
806 :
807 54318363 : if (!this_offset
808 54318363 : || !poly_int_tree_p (this_offset, &hthis_offset)
809 108633929 : || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
810 : % BITS_PER_UNIT))
811 3792 : return NULL_TREE;
812 :
813 54314571 : hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
814 54314571 : / BITS_PER_UNIT);
815 54314571 : byte_offset += hthis_offset;
816 : }
817 54314571 : break;
818 :
819 8179375 : case ARRAY_REF:
820 8179375 : case ARRAY_RANGE_REF:
821 8179375 : {
822 8179375 : tree index = TREE_OPERAND (exp, 1);
823 8179375 : tree low_bound, unit_size;
824 :
825 8179375 : if (valueize
826 1648253 : && TREE_CODE (index) == SSA_NAME)
827 1064692 : index = (*valueize) (index);
828 8179375 : if (!poly_int_tree_p (index))
829 3975868 : return NULL_TREE;
830 4219169 : low_bound = array_ref_low_bound (exp);
831 4219169 : if (valueize
832 853613 : && TREE_CODE (low_bound) == SSA_NAME)
833 4061 : low_bound = (*valueize) (low_bound);
834 4219169 : if (!poly_int_tree_p (low_bound))
835 : return NULL_TREE;
836 4219169 : unit_size = array_ref_element_size (exp);
837 4219169 : if (TREE_CODE (unit_size) != INTEGER_CST)
838 : return NULL_TREE;
839 :
840 : /* If the resulting bit-offset is constant, track it. */
841 4203507 : poly_offset_int woffset
842 4203507 : = wi::sext (wi::to_poly_offset (index)
843 8407014 : - wi::to_poly_offset (low_bound),
844 4203507 : TYPE_PRECISION (sizetype));
845 4203507 : woffset *= wi::to_offset (unit_size);
846 4203507 : byte_offset += woffset.force_shwi ();
847 : }
848 4203507 : break;
849 :
850 : case REALPART_EXPR:
851 : break;
852 :
853 25706 : case IMAGPART_EXPR:
854 25706 : byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
855 25706 : break;
856 :
857 : case VIEW_CONVERT_EXPR:
858 : break;
859 :
860 35098807 : case MEM_REF:
861 35098807 : {
862 35098807 : tree base = TREE_OPERAND (exp, 0);
863 35098807 : if (valueize
864 6937134 : && TREE_CODE (base) == SSA_NAME)
865 6477570 : base = (*valueize) (base);
866 :
867 : /* Hand back the decl for MEM[&decl, off]. */
868 35098807 : if (TREE_CODE (base) == ADDR_EXPR)
869 : {
870 20237481 : if (!integer_zerop (TREE_OPERAND (exp, 1)))
871 : {
872 16849736 : poly_offset_int off = mem_ref_offset (exp);
873 16849736 : byte_offset += off.force_shwi ();
874 : }
875 20237481 : exp = TREE_OPERAND (base, 0);
876 : }
877 35098807 : goto done;
878 : }
879 :
880 737450 : case TARGET_MEM_REF:
881 737450 : {
882 737450 : tree base = TREE_OPERAND (exp, 0);
883 737450 : if (valueize
884 2242 : && TREE_CODE (base) == SSA_NAME)
885 1611 : base = (*valueize) (base);
886 :
887 : /* Hand back the decl for MEM[&decl, off]. */
888 737450 : if (TREE_CODE (base) == ADDR_EXPR)
889 : {
890 11953 : if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
891 : return NULL_TREE;
892 33 : if (!integer_zerop (TMR_OFFSET (exp)))
893 : {
894 17 : poly_offset_int off = mem_ref_offset (exp);
895 17 : byte_offset += off.force_shwi ();
896 : }
897 33 : exp = TREE_OPERAND (base, 0);
898 : }
899 725530 : goto done;
900 : }
901 :
902 184618622 : default:
903 184618622 : goto done;
904 : }
905 :
906 58935209 : exp = TREE_OPERAND (exp, 0);
907 58935209 : }
908 220442959 : done:
909 :
910 220442959 : *poffset = byte_offset;
911 220442959 : return exp;
912 : }
913 :
914 : /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
915 : denotes the starting address of the memory access EXP.
916 : Returns NULL_TREE if the offset is not constant or any component
917 : is not BITS_PER_UNIT-aligned. */
918 :
919 : tree
920 86921394 : get_addr_base_and_unit_offset (tree exp, poly_int64 *poffset)
921 : {
922 86921394 : return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
923 : }
924 :
925 : /* Returns true if STMT references an SSA_NAME that has
926 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
927 :
928 : bool
929 18180605 : stmt_references_abnormal_ssa_name (gimple *stmt)
930 : {
931 18180605 : ssa_op_iter oi;
932 18180605 : use_operand_p use_p;
933 :
934 40571410 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
935 : {
936 22391540 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
937 : return true;
938 : }
939 :
940 : return false;
941 : }
942 :
943 : /* If STMT takes any abnormal PHI values as input, replace them with
944 : local copies. */
945 :
946 : void
947 1896 : replace_abnormal_ssa_names (gimple *stmt)
948 : {
949 1896 : ssa_op_iter oi;
950 1896 : use_operand_p use_p;
951 :
952 3784 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
953 : {
954 1888 : tree op = USE_FROM_PTR (use_p);
955 1888 : if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
956 : {
957 20 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
958 20 : tree new_name = make_ssa_name (TREE_TYPE (op));
959 20 : gassign *assign = gimple_build_assign (new_name, op);
960 20 : gsi_insert_before (&gsi, assign, GSI_SAME_STMT);
961 20 : SET_USE (use_p, new_name);
962 : }
963 : }
964 1896 : }
965 :
966 : /* Pair of tree and a sorting index, for dump_enumerated_decls. */
967 : struct GTY(()) numbered_tree
968 : {
969 : tree t;
970 : int num;
971 : };
972 :
973 :
974 : /* Compare two declarations references by their DECL_UID / sequence number.
975 : Called via qsort. */
976 :
977 : static int
978 367675 : compare_decls_by_uid (const void *pa, const void *pb)
979 : {
980 367675 : const numbered_tree *nt_a = ((const numbered_tree *)pa);
981 367675 : const numbered_tree *nt_b = ((const numbered_tree *)pb);
982 :
983 367675 : if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
984 299635 : return DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
985 68040 : return nt_a->num - nt_b->num;
986 : }
987 :
988 : /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */
989 : static tree
990 114580 : dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
991 : {
992 114580 : struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
993 114580 : vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
994 114580 : numbered_tree nt;
995 :
996 114580 : if (!DECL_P (*tp))
997 : return NULL_TREE;
998 20783 : nt.t = *tp;
999 20783 : nt.num = list->length ();
1000 20783 : list->safe_push (nt);
1001 20783 : *walk_subtrees = 0;
1002 20783 : return NULL_TREE;
1003 : }
1004 :
1005 : /* Find all the declarations used by the current function, sort them by uid,
1006 : and emit the sorted list. Each declaration is tagged with a sequence
1007 : number indicating when it was found during statement / tree walking,
1008 : so that TDF_NOUID comparisons of anonymous declarations are still
1009 : meaningful. Where a declaration was encountered more than once, we
1010 : emit only the sequence number of the first encounter.
1011 : FILE is the dump file where to output the list and FLAGS is as in
1012 : print_generic_expr. */
1013 : void
1014 3967 : dump_enumerated_decls (FILE *file, dump_flags_t flags)
1015 : {
1016 3967 : if (!cfun->cfg)
1017 4 : return;
1018 :
1019 3963 : basic_block bb;
1020 3963 : struct walk_stmt_info wi;
1021 3963 : auto_vec<numbered_tree, 40> decl_list;
1022 :
1023 3963 : memset (&wi, '\0', sizeof (wi));
1024 3963 : wi.info = (void *) &decl_list;
1025 15253 : FOR_EACH_BB_FN (bb, cfun)
1026 : {
1027 11290 : gimple_stmt_iterator gsi;
1028 :
1029 79324 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1030 56744 : if (!is_gimple_debug (gsi_stmt (gsi)))
1031 36203 : walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
1032 : }
1033 3963 : decl_list.qsort (compare_decls_by_uid);
1034 3963 : if (decl_list.length ())
1035 : {
1036 3577 : unsigned ix;
1037 3577 : numbered_tree *ntp;
1038 3577 : tree last = NULL_TREE;
1039 :
1040 3577 : fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
1041 : current_function_name ());
1042 31900 : FOR_EACH_VEC_ELT (decl_list, ix, ntp)
1043 : {
1044 20783 : if (ntp->t == last)
1045 7699 : continue;
1046 13084 : fprintf (file, "%d: ", ntp->num);
1047 13084 : print_generic_decl (file, ntp->t, flags);
1048 13084 : fprintf (file, "\n");
1049 13084 : last = ntp->t;
1050 : }
1051 : }
1052 3963 : }
|
