Branch data Line data Source code
1 : : /* Data flow functions for trees.
2 : : Copyright (C) 2001-2024 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 : 65596458 : renumber_gimple_stmt_uids_in_block (struct function *fun, basic_block bb)
67 : : {
68 : 65596458 : gimple_stmt_iterator bsi;
69 : 89435418 : for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
70 : : {
71 : 23838960 : gimple *stmt = gsi_stmt (bsi);
72 : 23838960 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
73 : : }
74 : 496204308 : for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
75 : : {
76 : 365011392 : gimple *stmt = gsi_stmt (bsi);
77 : 365011392 : gimple_set_uid (stmt, inc_gimple_stmt_max_uid (fun));
78 : : }
79 : 65596458 : }
80 : :
81 : : /* Renumber all of the gimple stmt uids. */
82 : :
83 : : void
84 : 5967993 : renumber_gimple_stmt_uids (struct function *fun)
85 : : {
86 : 5967993 : basic_block bb;
87 : :
88 : 5967993 : set_gimple_stmt_max_uid (fun, 0);
89 : 67709391 : FOR_ALL_BB_FN (bb, fun)
90 : 61741398 : renumber_gimple_stmt_uids_in_block (fun, bb);
91 : 5967993 : }
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 : 545711 : renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
98 : : {
99 : 545711 : int i;
100 : :
101 : 545711 : set_gimple_stmt_max_uid (cfun, 0);
102 : 4105745 : for (i = 0; i < n_blocks; i++)
103 : 3560034 : renumber_gimple_stmt_uids_in_block (cfun, blocks[i]);
104 : 545711 : }
105 : :
106 : :
107 : :
108 : : /*---------------------------------------------------------------------------
109 : : Debugging functions
110 : : ---------------------------------------------------------------------------*/
111 : :
112 : : /* Dump variable VAR and its may-aliases to FILE. */
113 : :
114 : : void
115 : 365 : dump_variable (FILE *file, tree var)
116 : : {
117 : 365 : 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 : 365 : print_generic_expr (file, var, dump_flags);
131 : :
132 : 365 : fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
133 : 365 : if (DECL_PT_UID (var) != DECL_UID (var))
134 : 0 : fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
135 : :
136 : 365 : fprintf (file, ", ");
137 : 365 : print_generic_expr (file, TREE_TYPE (var), dump_flags);
138 : :
139 : 365 : if (TREE_ADDRESSABLE (var))
140 : 365 : fprintf (file, ", is addressable");
141 : :
142 : 365 : if (is_global_var (var))
143 : 77 : fprintf (file, ", is global");
144 : :
145 : 365 : if (TREE_THIS_VOLATILE (var))
146 : 0 : fprintf (file, ", is volatile");
147 : :
148 : 365 : 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 : 365 : if (DECL_INITIAL (var))
155 : : {
156 : 77 : fprintf (file, ", initial: ");
157 : 77 : print_generic_expr (file, DECL_INITIAL (var), dump_flags);
158 : : }
159 : :
160 : 365 : 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 : 552 : dump_dfa_stats (FILE *file)
177 : : {
178 : 552 : struct dfa_stats_d dfa_stats;
179 : :
180 : 552 : unsigned long size, total = 0;
181 : 552 : const char * const fmt_str = "%-30s%-13s%12s\n";
182 : 552 : const char * const fmt_str_1 = "%-30s%13lu" PRsa (11) "\n";
183 : 552 : const char * const fmt_str_3 = "%-43s" PRsa (11) "\n";
184 : 552 : const char *funcname
185 : 552 : = lang_hooks.decl_printable_name (current_function_decl, 2);
186 : :
187 : 552 : collect_dfa_stats (&dfa_stats);
188 : :
189 : 552 : fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
190 : :
191 : 552 : fprintf (file, "---------------------------------------------------------\n");
192 : 552 : fprintf (file, fmt_str, "", " Number of ", "Memory");
193 : 552 : fprintf (file, fmt_str, "", " instances ", "used ");
194 : 552 : fprintf (file, "---------------------------------------------------------\n");
195 : :
196 : 552 : size = dfa_stats.num_uses * sizeof (tree *);
197 : 552 : total += size;
198 : 552 : fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
199 : 0 : SIZE_AMOUNT (size));
200 : :
201 : 552 : size = dfa_stats.num_defs * sizeof (tree *);
202 : 552 : total += size;
203 : 552 : fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
204 : 0 : SIZE_AMOUNT (size));
205 : :
206 : 552 : size = dfa_stats.num_vuses * sizeof (tree *);
207 : 552 : total += size;
208 : 552 : fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
209 : 0 : SIZE_AMOUNT (size));
210 : :
211 : 552 : size = dfa_stats.num_vdefs * sizeof (tree *);
212 : 552 : total += size;
213 : 552 : fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
214 : 0 : SIZE_AMOUNT (size));
215 : :
216 : 552 : size = dfa_stats.num_phis * sizeof (struct gphi);
217 : 552 : total += size;
218 : 552 : fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
219 : 0 : SIZE_AMOUNT (size));
220 : :
221 : 552 : size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
222 : 552 : total += size;
223 : 552 : fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
224 : 0 : SIZE_AMOUNT (size));
225 : :
226 : 552 : fprintf (file, "---------------------------------------------------------\n");
227 : 566 : fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data",
228 : 28 : SIZE_AMOUNT (total));
229 : 552 : fprintf (file, "---------------------------------------------------------\n");
230 : 552 : fprintf (file, "\n");
231 : :
232 : 552 : if (dfa_stats.num_phis)
233 : 545 : fprintf (file, "Average number of arguments per PHI node: %.1f (max: "
234 : : HOST_SIZE_T_PRINT_DEC ")\n",
235 : 545 : (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
236 : 545 : (fmt_size_t) dfa_stats.max_num_phi_args);
237 : :
238 : 552 : fprintf (file, "\n");
239 : 552 : }
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 : 552 : collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
256 : : {
257 : 552 : basic_block bb;
258 : :
259 : 552 : gcc_assert (dfa_stats_p);
260 : :
261 : 552 : memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
262 : :
263 : : /* Walk all the statements in the function counting references. */
264 : 8982 : FOR_EACH_BB_FN (bb, cfun)
265 : : {
266 : 14034 : for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
267 : 5604 : gsi_next (&si))
268 : : {
269 : 5604 : gphi *phi = si.phi ();
270 : 5604 : dfa_stats_p->num_phis++;
271 : 5604 : dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
272 : 5604 : if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
273 : 766 : dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
274 : : }
275 : :
276 : 32263 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
277 : 15403 : gsi_next (&si))
278 : : {
279 : 15403 : gimple *stmt = gsi_stmt (si);
280 : 15403 : dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
281 : 15403 : dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
282 : 28795 : dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
283 : 28795 : dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
284 : : }
285 : : }
286 : 552 : }
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 : 505115427 : ssa_default_def (struct function *fn, tree var)
298 : : {
299 : 505115427 : struct tree_decl_minimal ind;
300 : 505115427 : struct tree_ssa_name in;
301 : 505115427 : 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 : 505115427 : if (!fn->gimple_df)
307 : : return NULL_TREE;
308 : :
309 : 505115427 : in.var = (tree)&ind;
310 : 505115427 : ind.uid = DECL_UID (var);
311 : 505115427 : 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 : 11300591 : set_ssa_default_def (struct function *fn, tree var, tree def)
319 : : {
320 : 11300591 : struct tree_decl_minimal ind;
321 : 11300591 : struct tree_ssa_name in;
322 : :
323 : 11300591 : gcc_assert (VAR_P (var)
324 : : || TREE_CODE (var) == PARM_DECL
325 : : || TREE_CODE (var) == RESULT_DECL);
326 : 11300591 : in.var = (tree)&ind;
327 : 11300591 : ind.uid = DECL_UID (var);
328 : 11300591 : if (!def)
329 : : {
330 : 1168472 : tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
331 : 1168472 : DECL_UID (var),
332 : : NO_INSERT);
333 : 1168472 : if (loc)
334 : : {
335 : 1168466 : SSA_NAME_IS_DEFAULT_DEF (*(tree *)loc) = false;
336 : 1168466 : DEFAULT_DEFS (fn)->clear_slot (loc);
337 : : }
338 : 1168472 : return;
339 : : }
340 : 10132119 : gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
341 : 10132119 : tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
342 : 10132119 : DECL_UID (var), INSERT);
343 : :
344 : : /* Default definition might be changed by tail call optimization. */
345 : 10132119 : if (*loc)
346 : 990 : SSA_NAME_IS_DEFAULT_DEF (*loc) = false;
347 : :
348 : : /* Mark DEF as the default definition for VAR. */
349 : 10132119 : *loc = def;
350 : 10132119 : SSA_NAME_IS_DEFAULT_DEF (def) = true;
351 : : }
352 : :
353 : : /* Retrieve or create a default definition for VAR. */
354 : :
355 : : tree
356 : 24224501 : get_or_create_ssa_default_def (struct function *fn, tree var)
357 : : {
358 : 24224501 : tree ddef = ssa_default_def (fn, var);
359 : 24224501 : if (ddef == NULL_TREE)
360 : : {
361 : 9632974 : ddef = make_ssa_name_fn (fn, var, gimple_build_nop ());
362 : 9632974 : set_ssa_default_def (fn, var, ddef);
363 : : }
364 : 24224501 : 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 : 2701858348 : get_ref_base_and_extent (tree exp, poly_int64 *poffset,
377 : : poly_int64 *psize,
378 : : poly_int64 *pmax_size,
379 : : bool *preverse)
380 : : {
381 : 2701858348 : poly_offset_int bitsize = -1;
382 : 2701858348 : poly_offset_int maxsize;
383 : 2701858348 : tree size_tree = NULL_TREE;
384 : 2701858348 : poly_offset_int bit_offset = 0;
385 : 2701858348 : 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 : 2701858348 : if (TREE_CODE (exp) == COMPONENT_REF)
390 : 1463082500 : size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
391 : 1238775848 : else if (TREE_CODE (exp) == BIT_FIELD_REF)
392 : 6841191 : size_tree = TREE_OPERAND (exp, 1);
393 : 1231934657 : 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 : 1231934483 : else if (!VOID_TYPE_P (TREE_TYPE (exp)))
399 : : {
400 : 1195805821 : machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
401 : 1195805821 : if (mode == BLKmode)
402 : 355227841 : size_tree = TYPE_SIZE (TREE_TYPE (exp));
403 : : else
404 : 1681155960 : bitsize = GET_MODE_BITSIZE (mode);
405 : : }
406 : 840577980 : if (size_tree != NULL_TREE
407 : 1825151706 : && poly_int_tree_p (size_tree))
408 : 1824355549 : bitsize = wi::to_poly_offset (size_tree);
409 : :
410 : 2701858348 : *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 : 2701858348 : maxsize = bitsize;
415 : :
416 : : /* Compute cumulative bit-offset for nested component-refs and array-refs,
417 : : and find the ultimate containing object. */
418 : 8581581848 : while (1)
419 : : {
420 : 5641720098 : switch (TREE_CODE (exp))
421 : : {
422 : 6841191 : case BIT_FIELD_REF:
423 : 6841191 : bit_offset += wi::to_poly_offset (TREE_OPERAND (exp, 2));
424 : 6841191 : break;
425 : :
426 : 2205842488 : case COMPONENT_REF:
427 : 2205842488 : {
428 : 2205842488 : tree field = TREE_OPERAND (exp, 1);
429 : 2205842488 : tree this_offset = component_ref_field_offset (exp);
430 : :
431 : 2205842488 : if (this_offset && poly_int_tree_p (this_offset))
432 : : {
433 : 2205839521 : poly_offset_int woffset = (wi::to_poly_offset (this_offset)
434 : 2205839521 : << LOG2_BITS_PER_UNIT);
435 : 2205839521 : woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
436 : 2205839521 : 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 : 2205839521 : if (seen_variable_array_ref)
443 : : {
444 : 17849290 : tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
445 : 17849290 : tree next = DECL_CHAIN (field);
446 : 29319493 : while (next && TREE_CODE (next) != FIELD_DECL)
447 : 11470203 : next = DECL_CHAIN (next);
448 : 17849290 : if (!next
449 : 3007488 : || TREE_CODE (stype) != RECORD_TYPE)
450 : : {
451 : 15448940 : tree fsize = DECL_SIZE (field);
452 : 15448940 : tree ssize = TYPE_SIZE (stype);
453 : 15448940 : if (fsize == NULL
454 : 9752568 : || !poly_int_tree_p (fsize)
455 : 9751143 : || ssize == NULL
456 : 25200083 : || !poly_int_tree_p (ssize))
457 : 5697797 : maxsize = -1;
458 : 9751143 : else if (known_size_p (maxsize))
459 : : {
460 : 9751001 : poly_offset_int tem
461 : 9751001 : = (wi::to_poly_offset (ssize)
462 : 9751001 : - wi::to_poly_offset (fsize));
463 : 19502002 : tem -= woffset;
464 : 9751001 : 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 : 2967 : 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 : 2967 : if (known_size_p (maxsize)
481 : 1979 : && csize
482 : 4946 : && poly_int_tree_p (csize))
483 : 0 : maxsize = wi::to_poly_offset (csize) - bit_offset;
484 : : else
485 : 2967 : maxsize = -1;
486 : : }
487 : : }
488 : : break;
489 : :
490 : 710874212 : case ARRAY_REF:
491 : 710874212 : case ARRAY_RANGE_REF:
492 : 710874212 : {
493 : 710874212 : tree index = TREE_OPERAND (exp, 1);
494 : 710874212 : tree low_bound, unit_size;
495 : :
496 : : /* If the resulting bit-offset is constant, track it. */
497 : 1335990718 : if (poly_int_tree_p (index)
498 : 625116506 : && (low_bound = array_ref_low_bound (exp),
499 : 625116506 : poly_int_tree_p (low_bound))
500 : 1335990718 : && (unit_size = array_ref_element_size (exp),
501 : 625116506 : TREE_CODE (unit_size) == INTEGER_CST))
502 : : {
503 : 625027880 : poly_offset_int woffset
504 : 625027880 : = wi::sext (wi::to_poly_offset (index)
505 : 1250055760 : - wi::to_poly_offset (low_bound),
506 : 625027880 : TYPE_PRECISION (sizetype));
507 : 625027880 : woffset *= wi::to_offset (unit_size);
508 : 625027880 : woffset <<= LOG2_BITS_PER_UNIT;
509 : 625027880 : 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 : 625027880 : seen_variable_array_ref = false;
515 : : }
516 : : else
517 : : {
518 : 85846332 : 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 : 85846332 : if (known_size_p (maxsize)
523 : 85601458 : && asize
524 : 153652210 : && poly_int_tree_p (asize))
525 : 66003156 : maxsize = wi::to_poly_offset (asize) - bit_offset;
526 : : else
527 : 19843176 : maxsize = -1;
528 : :
529 : : /* Remember that we have seen an array ref with a variable
530 : : index. */
531 : 85846332 : seen_variable_array_ref = true;
532 : :
533 : 85846332 : value_range vr;
534 : 85846332 : range_query *query;
535 : 85846332 : query = get_range_query (cfun);
536 : :
537 : 85846332 : if (TREE_CODE (index) == SSA_NAME
538 : 85341963 : && (low_bound = array_ref_low_bound (exp),
539 : 85341963 : poly_int_tree_p (low_bound))
540 : 85341963 : && (unit_size = array_ref_element_size (exp),
541 : 85341963 : TREE_CODE (unit_size) == INTEGER_CST)
542 : 85142254 : && query->range_of_expr (vr, index)
543 : 85142254 : && !vr.varying_p ()
544 : 132975854 : && !vr.undefined_p ())
545 : : {
546 : 47124832 : wide_int min = vr.lower_bound ();
547 : 47124832 : wide_int max = vr.upper_bound ();
548 : 47124832 : poly_offset_int lbound = wi::to_poly_offset (low_bound);
549 : : /* Try to constrain maxsize with range information. */
550 : 47124832 : offset_int omax
551 : 47124832 : = offset_int::from (max, TYPE_SIGN (TREE_TYPE (index)));
552 : 47124832 : if (wi::get_precision (max) <= ADDR_MAX_BITSIZE
553 : 94105093 : && known_lt (lbound, omax))
554 : : {
555 : 46960862 : poly_offset_int rmaxsize;
556 : 93921724 : rmaxsize = (omax - lbound + 1)
557 : 93921724 : * wi::to_offset (unit_size) << LOG2_BITS_PER_UNIT;
558 : 46960862 : if (!known_size_p (maxsize)
559 : 82653694 : || known_lt (rmaxsize, maxsize))
560 : : {
561 : : /* If we know an upper bound below the declared
562 : : one this is no longer variable. */
563 : 17923129 : if (known_size_p (maxsize))
564 : : seen_variable_array_ref = false;
565 : 17923129 : maxsize = rmaxsize;
566 : : }
567 : : }
568 : : /* Try to adjust bit_offset with range information. */
569 : 47124832 : offset_int omin
570 : 47124832 : = offset_int::from (min, TYPE_SIGN (TREE_TYPE (index)));
571 : 47124832 : if (wi::get_precision (min) <= ADDR_MAX_BITSIZE
572 : 94105093 : && known_le (lbound, omin))
573 : : {
574 : 41583986 : poly_offset_int woffset
575 : 41583986 : = wi::sext (omin - lbound,
576 : 41583986 : TYPE_PRECISION (sizetype));
577 : 41583986 : woffset *= wi::to_offset (unit_size);
578 : 41583986 : woffset <<= LOG2_BITS_PER_UNIT;
579 : 41583986 : bit_offset += woffset;
580 : 41583986 : if (known_size_p (maxsize))
581 : 41583986 : maxsize -= woffset;
582 : : }
583 : 47124832 : }
584 : 85846332 : }
585 : : }
586 : : break;
587 : :
588 : : case REALPART_EXPR:
589 : : break;
590 : :
591 : : case IMAGPART_EXPR:
592 : 2939861750 : bit_offset += bitsize;
593 : : break;
594 : :
595 : : case VIEW_CONVERT_EXPR:
596 : : break;
597 : :
598 : 44734214 : case TARGET_MEM_REF:
599 : : /* Via the variable index or index2 we can reach the
600 : : whole object. Still hand back the decl here. */
601 : 44734214 : if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
602 : 44734214 : && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
603 : : {
604 : 7735914 : exp = TREE_OPERAND (TMR_BASE (exp), 0);
605 : 7735914 : bit_offset = 0;
606 : 7735914 : maxsize = -1;
607 : 7735914 : goto done;
608 : : }
609 : : /* Fallthru. */
610 : 889274422 : case MEM_REF:
611 : : /* We need to deal with variable arrays ending structures such as
612 : : struct { int length; int a[1]; } x; x.a[d]
613 : : struct { struct { int a; int b; } a[1]; } x; x.a[d].a
614 : : struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
615 : : struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
616 : : where we do not know maxsize for variable index accesses to
617 : : the array. The simplest way to conservatively deal with this
618 : : is to punt in the case that offset + maxsize reaches the
619 : : base type boundary. This needs to include possible trailing
620 : : padding that is there for alignment purposes. */
621 : 889274422 : if (seen_variable_array_ref
622 : 27295838 : && known_size_p (maxsize)
623 : 905305454 : && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
624 : 9176231 : || !poly_int_tree_p (TYPE_SIZE (TREE_TYPE (exp)))
625 : 8128575 : || (maybe_eq
626 : 8128575 : (bit_offset + maxsize,
627 : 881371965 : wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (exp)))))))
628 : 16031032 : maxsize = -1;
629 : :
630 : : /* Hand back the decl for MEM[&decl, off]. */
631 : 889274422 : if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
632 : : {
633 : 306959449 : if (integer_zerop (TREE_OPERAND (exp, 1)))
634 : 144005547 : exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
635 : : else
636 : : {
637 : 162953902 : poly_offset_int off = mem_ref_offset (exp);
638 : 162953902 : off <<= LOG2_BITS_PER_UNIT;
639 : 162953902 : off += bit_offset;
640 : 162953902 : poly_int64 off_hwi;
641 : 162953902 : if (off.to_shwi (&off_hwi))
642 : : {
643 : 162952243 : bit_offset = off_hwi;
644 : 162952243 : exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
645 : : }
646 : : }
647 : : }
648 : 889274422 : goto done;
649 : :
650 : 1804848012 : default:
651 : 1804848012 : goto done;
652 : : }
653 : :
654 : 2939861750 : exp = TREE_OPERAND (exp, 0);
655 : 2939861750 : }
656 : :
657 : 2701858348 : done:
658 : 2701858348 : if (!bitsize.to_shwi (psize) || maybe_lt (*psize, 0))
659 : : {
660 : 36924842 : *poffset = 0;
661 : 36924842 : *psize = -1;
662 : 36924842 : *pmax_size = -1;
663 : :
664 : 36924842 : return exp;
665 : : }
666 : :
667 : : /* ??? Due to negative offsets in ARRAY_REF we can end up with
668 : : negative bit_offset here. We might want to store a zero offset
669 : : in this case. */
670 : 2664933506 : if (!bit_offset.to_shwi (poffset))
671 : : {
672 : 8099 : *poffset = 0;
673 : 8099 : *pmax_size = -1;
674 : :
675 : 8099 : return exp;
676 : : }
677 : :
678 : : /* In case of a decl or constant base object we can do better. */
679 : :
680 : 2664925407 : if (DECL_P (exp))
681 : : {
682 : 2058166596 : if (VAR_P (exp)
683 : 2058166596 : && ((flag_unconstrained_commons && DECL_COMMON (exp))
684 : 2005584112 : || (DECL_EXTERNAL (exp) && seen_variable_array_ref)))
685 : : {
686 : 500482 : tree sz_tree = TYPE_SIZE (TREE_TYPE (exp));
687 : : /* If size is unknown, or we have read to the end, assume there
688 : : may be more to the structure than we are told. */
689 : 500482 : if (TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE
690 : 500482 : || (seen_variable_array_ref
691 : 35404 : && (sz_tree == NULL_TREE
692 : 35404 : || !poly_int_tree_p (sz_tree)
693 : 35404 : || maybe_eq (bit_offset + maxsize,
694 : 36086 : wi::to_poly_offset (sz_tree)))))
695 : 499800 : maxsize = -1;
696 : : }
697 : : /* If maxsize is unknown adjust it according to the size of the
698 : : base decl. */
699 : 2057666114 : else if (!known_size_p (maxsize)
700 : 14517104 : && DECL_SIZE (exp)
701 : 2072178820 : && poly_int_tree_p (DECL_SIZE (exp)))
702 : 14512662 : maxsize = wi::to_poly_offset (DECL_SIZE (exp)) - bit_offset;
703 : : }
704 : 606758811 : else if (CONSTANT_CLASS_P (exp))
705 : : {
706 : : /* If maxsize is unknown adjust it according to the size of the
707 : : base type constant. */
708 : 6643487 : if (!known_size_p (maxsize)
709 : 27911 : && TYPE_SIZE (TREE_TYPE (exp))
710 : 6671398 : && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (exp))))
711 : 27911 : maxsize = (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (exp)))
712 : 27911 : - bit_offset);
713 : : }
714 : :
715 : 2664925407 : if (!maxsize.to_shwi (pmax_size)
716 : 2664925407 : || maybe_lt (*pmax_size, 0)
717 : 5308876987 : || !endpoint_representable_p (*poffset, *pmax_size))
718 : 20973883 : *pmax_size = -1;
719 : :
720 : : /* Punt if *POFFSET + *PSIZE overflows in HOST_WIDE_INT, the callers don't
721 : : check for such overflows individually and assume it works. */
722 : 5329850814 : if (!endpoint_representable_p (*poffset, *psize))
723 : : {
724 : 56 : *poffset = 0;
725 : 56 : *psize = -1;
726 : 56 : *pmax_size = -1;
727 : :
728 : 56 : return exp;
729 : : }
730 : :
731 : : return exp;
732 : : }
733 : :
734 : : /* Like get_ref_base_and_extent, but for cases in which we only care
735 : : about constant-width accesses at constant offsets. Return null
736 : : if the access is anything else. */
737 : :
738 : : tree
739 : 42760781 : get_ref_base_and_extent_hwi (tree exp, HOST_WIDE_INT *poffset,
740 : : HOST_WIDE_INT *psize, bool *preverse)
741 : : {
742 : 42760781 : poly_int64 offset, size, max_size;
743 : 42760781 : HOST_WIDE_INT const_offset, const_size;
744 : 42760781 : bool reverse;
745 : 42760781 : tree decl = get_ref_base_and_extent (exp, &offset, &size, &max_size,
746 : : &reverse);
747 : 42760781 : if (!offset.is_constant (&const_offset)
748 : 42760781 : || !size.is_constant (&const_size)
749 : 42760781 : || const_offset < 0
750 : 42760002 : || !known_size_p (max_size)
751 : 42329098 : || maybe_ne (max_size, const_size))
752 : : return NULL_TREE;
753 : :
754 : 41521319 : *poffset = const_offset;
755 : 41521319 : *psize = const_size;
756 : 41521319 : *preverse = reverse;
757 : 41521319 : return decl;
758 : : }
759 : :
760 : : /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
761 : : denotes the starting address of the memory access EXP.
762 : : Returns NULL_TREE if the offset is not constant or any component
763 : : is not BITS_PER_UNIT-aligned.
764 : : VALUEIZE if non-NULL is used to valueize SSA names. It should return
765 : : its argument or a constant if the argument is known to be constant. */
766 : :
767 : : tree
768 : 169173412 : get_addr_base_and_unit_offset_1 (tree exp, poly_int64 *poffset,
769 : : tree (*valueize) (tree))
770 : : {
771 : 169173412 : poly_int64 byte_offset = 0;
772 : :
773 : : /* Compute cumulative byte-offset for nested component-refs and array-refs,
774 : : and find the ultimate containing object. */
775 : 246497864 : while (1)
776 : : {
777 : 207835638 : switch (TREE_CODE (exp))
778 : : {
779 : 23128 : case BIT_FIELD_REF:
780 : 23128 : {
781 : 23128 : poly_int64 this_byte_offset;
782 : 23128 : poly_uint64 this_bit_offset;
783 : 23128 : if (!poly_int_tree_p (TREE_OPERAND (exp, 2), &this_bit_offset)
784 : 46256 : || !multiple_p (this_bit_offset, BITS_PER_UNIT,
785 : : &this_byte_offset))
786 : 0 : return NULL_TREE;
787 : 23128 : byte_offset += this_byte_offset;
788 : : }
789 : 23128 : break;
790 : :
791 : 35006372 : case COMPONENT_REF:
792 : 35006372 : {
793 : 35006372 : tree field = TREE_OPERAND (exp, 1);
794 : 35006372 : tree this_offset = component_ref_field_offset (exp);
795 : 35006372 : poly_int64 hthis_offset;
796 : :
797 : 35006372 : if (!this_offset
798 : 35006372 : || !poly_int_tree_p (this_offset, &hthis_offset)
799 : 70009842 : || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
800 : : % BITS_PER_UNIT))
801 : 3586 : return NULL_TREE;
802 : :
803 : 35002786 : hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
804 : 35002786 : / BITS_PER_UNIT);
805 : 35002786 : byte_offset += hthis_offset;
806 : : }
807 : 35002786 : break;
808 : :
809 : 6138301 : case ARRAY_REF:
810 : 6138301 : case ARRAY_RANGE_REF:
811 : 6138301 : {
812 : 6138301 : tree index = TREE_OPERAND (exp, 1);
813 : 6138301 : tree low_bound, unit_size;
814 : :
815 : 6138301 : if (valueize
816 : 1576294 : && TREE_CODE (index) == SSA_NAME)
817 : 975860 : index = (*valueize) (index);
818 : 6138301 : if (!poly_int_tree_p (index))
819 : 2787566 : return NULL_TREE;
820 : 3361444 : low_bound = array_ref_low_bound (exp);
821 : 3361444 : if (valueize
822 : 836485 : && TREE_CODE (low_bound) == SSA_NAME)
823 : 3527 : low_bound = (*valueize) (low_bound);
824 : 3361444 : if (!poly_int_tree_p (low_bound))
825 : : return NULL_TREE;
826 : 3361444 : unit_size = array_ref_element_size (exp);
827 : 3361444 : if (TREE_CODE (unit_size) != INTEGER_CST)
828 : : return NULL_TREE;
829 : :
830 : : /* If the resulting bit-offset is constant, track it. */
831 : 3350735 : poly_offset_int woffset
832 : 3350735 : = wi::sext (wi::to_poly_offset (index)
833 : 6701470 : - wi::to_poly_offset (low_bound),
834 : 3350735 : TYPE_PRECISION (sizetype));
835 : 3350735 : woffset *= wi::to_offset (unit_size);
836 : 3350735 : byte_offset += woffset.force_shwi ();
837 : : }
838 : 3350735 : break;
839 : :
840 : : case REALPART_EXPR:
841 : : break;
842 : :
843 : 21803 : case IMAGPART_EXPR:
844 : 21803 : byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
845 : 21803 : break;
846 : :
847 : : case VIEW_CONVERT_EXPR:
848 : : break;
849 : :
850 : 19834108 : case MEM_REF:
851 : 19834108 : {
852 : 19834108 : tree base = TREE_OPERAND (exp, 0);
853 : 19834108 : if (valueize
854 : 6973536 : && TREE_CODE (base) == SSA_NAME)
855 : 6623166 : base = (*valueize) (base);
856 : :
857 : : /* Hand back the decl for MEM[&decl, off]. */
858 : 19834108 : if (TREE_CODE (base) == ADDR_EXPR)
859 : : {
860 : 7829358 : if (!integer_zerop (TREE_OPERAND (exp, 1)))
861 : : {
862 : 5794501 : poly_offset_int off = mem_ref_offset (exp);
863 : 5794501 : byte_offset += off.force_shwi ();
864 : : }
865 : 7829358 : exp = TREE_OPERAND (base, 0);
866 : : }
867 : 19834108 : goto done;
868 : : }
869 : :
870 : 548275 : case TARGET_MEM_REF:
871 : 548275 : {
872 : 548275 : tree base = TREE_OPERAND (exp, 0);
873 : 548275 : if (valueize
874 : 1915 : && TREE_CODE (base) == SSA_NAME)
875 : 1200 : base = (*valueize) (base);
876 : :
877 : : /* Hand back the decl for MEM[&decl, off]. */
878 : 548275 : if (TREE_CODE (base) == ADDR_EXPR)
879 : : {
880 : 6200 : if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
881 : : return NULL_TREE;
882 : 0 : if (!integer_zerop (TMR_OFFSET (exp)))
883 : : {
884 : 0 : poly_offset_int off = mem_ref_offset (exp);
885 : 0 : byte_offset += off.force_shwi ();
886 : : }
887 : 0 : exp = TREE_OPERAND (base, 0);
888 : : }
889 : 542075 : goto done;
890 : : }
891 : :
892 : 145999877 : default:
893 : 145999877 : goto done;
894 : : }
895 : :
896 : 38662226 : exp = TREE_OPERAND (exp, 0);
897 : 38662226 : }
898 : 166376060 : done:
899 : :
900 : 166376060 : *poffset = byte_offset;
901 : 166376060 : return exp;
902 : : }
903 : :
904 : : /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
905 : : denotes the starting address of the memory access EXP.
906 : : Returns NULL_TREE if the offset is not constant or any component
907 : : is not BITS_PER_UNIT-aligned. */
908 : :
909 : : tree
910 : 47213422 : get_addr_base_and_unit_offset (tree exp, poly_int64 *poffset)
911 : : {
912 : 47213422 : return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
913 : : }
914 : :
915 : : /* Returns true if STMT references an SSA_NAME that has
916 : : SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
917 : :
918 : : bool
919 : 12973927 : stmt_references_abnormal_ssa_name (gimple *stmt)
920 : : {
921 : 12973927 : ssa_op_iter oi;
922 : 12973927 : use_operand_p use_p;
923 : :
924 : 29215933 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
925 : : {
926 : 16242550 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
927 : : return true;
928 : : }
929 : :
930 : : return false;
931 : : }
932 : :
933 : : /* If STMT takes any abnormal PHI values as input, replace them with
934 : : local copies. */
935 : :
936 : : void
937 : 1800 : replace_abnormal_ssa_names (gimple *stmt)
938 : : {
939 : 1800 : ssa_op_iter oi;
940 : 1800 : use_operand_p use_p;
941 : :
942 : 3587 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
943 : : {
944 : 1787 : tree op = USE_FROM_PTR (use_p);
945 : 1787 : if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
946 : : {
947 : 20 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
948 : 20 : tree new_name = make_ssa_name (TREE_TYPE (op));
949 : 20 : gassign *assign = gimple_build_assign (new_name, op);
950 : 20 : gsi_insert_before (&gsi, assign, GSI_SAME_STMT);
951 : 20 : SET_USE (use_p, new_name);
952 : : }
953 : : }
954 : 1800 : }
955 : :
956 : : /* Pair of tree and a sorting index, for dump_enumerated_decls. */
957 : : struct GTY(()) numbered_tree
958 : : {
959 : : tree t;
960 : : int num;
961 : : };
962 : :
963 : :
964 : : /* Compare two declarations references by their DECL_UID / sequence number.
965 : : Called via qsort. */
966 : :
967 : : static int
968 : 381123 : compare_decls_by_uid (const void *pa, const void *pb)
969 : : {
970 : 381123 : const numbered_tree *nt_a = ((const numbered_tree *)pa);
971 : 381123 : const numbered_tree *nt_b = ((const numbered_tree *)pb);
972 : :
973 : 381123 : if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
974 : 310383 : return DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
975 : 70740 : return nt_a->num - nt_b->num;
976 : : }
977 : :
978 : : /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */
979 : : static tree
980 : 114014 : dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
981 : : {
982 : 114014 : struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
983 : 114014 : vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
984 : 114014 : numbered_tree nt;
985 : :
986 : 114014 : if (!DECL_P (*tp))
987 : : return NULL_TREE;
988 : 21082 : nt.t = *tp;
989 : 21082 : nt.num = list->length ();
990 : 21082 : list->safe_push (nt);
991 : 21082 : *walk_subtrees = 0;
992 : 21082 : return NULL_TREE;
993 : : }
994 : :
995 : : /* Find all the declarations used by the current function, sort them by uid,
996 : : and emit the sorted list. Each declaration is tagged with a sequence
997 : : number indicating when it was found during statement / tree walking,
998 : : so that TDF_NOUID comparisons of anonymous declarations are still
999 : : meaningful. Where a declaration was encountered more than once, we
1000 : : emit only the sequence number of the first encounter.
1001 : : FILE is the dump file where to output the list and FLAGS is as in
1002 : : print_generic_expr. */
1003 : : void
1004 : 4030 : dump_enumerated_decls (FILE *file, dump_flags_t flags)
1005 : : {
1006 : 4030 : if (!cfun->cfg)
1007 : 4 : return;
1008 : :
1009 : 4026 : basic_block bb;
1010 : 4026 : struct walk_stmt_info wi;
1011 : 4026 : auto_vec<numbered_tree, 40> decl_list;
1012 : :
1013 : 4026 : memset (&wi, '\0', sizeof (wi));
1014 : 4026 : wi.info = (void *) &decl_list;
1015 : 14868 : FOR_EACH_BB_FN (bb, cfun)
1016 : : {
1017 : 10842 : gimple_stmt_iterator gsi;
1018 : :
1019 : 74565 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1020 : 52881 : if (!is_gimple_debug (gsi_stmt (gsi)))
1021 : 35052 : walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
1022 : : }
1023 : 4026 : decl_list.qsort (compare_decls_by_uid);
1024 : 4026 : if (decl_list.length ())
1025 : : {
1026 : 3592 : unsigned ix;
1027 : 3592 : numbered_tree *ntp;
1028 : 3592 : tree last = NULL_TREE;
1029 : :
1030 : 3592 : fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
1031 : : current_function_name ());
1032 : 32292 : FOR_EACH_VEC_ELT (decl_list, ix, ntp)
1033 : : {
1034 : 21082 : if (ntp->t == last)
1035 : 7911 : continue;
1036 : 13171 : fprintf (file, "%d: ", ntp->num);
1037 : 13171 : print_generic_decl (file, ntp->t, flags);
1038 : 13171 : fprintf (file, "\n");
1039 : 13171 : last = ntp->t;
1040 : : }
1041 : : }
1042 : 4026 : }
|
