Branch data Line data Source code
1 : : /* Liveness for SSA trees.
2 : : Copyright (C) 2003-2025 Free Software Foundation, Inc.
3 : : Contributed by Andrew MacLeod <amacleod@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 "timevar.h"
29 : : #include "ssa.h"
30 : : #include "cgraph.h"
31 : : #include "gimple-pretty-print.h"
32 : : #include "diagnostic-core.h"
33 : : #include "gimple-iterator.h"
34 : : #include "tree-dfa.h"
35 : : #include "dumpfile.h"
36 : : #include "tree-ssa-live.h"
37 : : #include "debug.h"
38 : : #include "tree-ssa.h"
39 : : #include "ipa-utils.h"
40 : : #include "cfgloop.h"
41 : : #include "stringpool.h"
42 : : #include "attribs.h"
43 : : #include "optinfo.h"
44 : : #include "gimple-walk.h"
45 : : #include "cfganal.h"
46 : : #include "tree-cfg.h"
47 : :
48 : : static void verify_live_on_entry (tree_live_info_p);
49 : :
50 : :
51 : : /* VARMAP maintains a mapping from SSA version number to real variables.
52 : :
53 : : All SSA_NAMES are divided into partitions. Initially each ssa_name is the
54 : : only member of it's own partition. Coalescing will attempt to group any
55 : : ssa_names which occur in a copy or in a PHI node into the same partition.
56 : :
57 : : At the end of out-of-ssa, each partition becomes a "real" variable and is
58 : : rewritten as a compiler variable.
59 : :
60 : : The var_map data structure is used to manage these partitions. It allows
61 : : partitions to be combined, and determines which partition belongs to what
62 : : ssa_name or variable, and vice versa. */
63 : :
64 : :
65 : : /* Remove the base table in MAP. */
66 : :
67 : : static void
68 : 4365915 : var_map_base_fini (var_map map)
69 : : {
70 : : /* Free the basevar info if it is present. */
71 : 4365915 : if (map->partition_to_base_index != NULL)
72 : : {
73 : 1455305 : free (map->partition_to_base_index);
74 : 1455305 : map->partition_to_base_index = NULL;
75 : 1455305 : map->num_basevars = 0;
76 : : }
77 : 4365915 : }
78 : : /* Create a variable partition map of SIZE for region, initialize and return
79 : : it. Region is a loop if LOOP is non-NULL, otherwise is the current
80 : : function. If BITINT is non-NULL, only SSA_NAMEs from that bitmap
81 : : will be coalesced. */
82 : :
83 : : var_map
84 : 1455305 : init_var_map (int size, class loop *loop, bitmap bitint)
85 : : {
86 : 1455305 : var_map map;
87 : :
88 : 1455305 : map = (var_map) xmalloc (sizeof (struct _var_map));
89 : 1455305 : map->var_partition = partition_new (size);
90 : :
91 : 1455305 : map->partition_to_view = NULL;
92 : 1455305 : map->view_to_partition = NULL;
93 : 1455305 : map->num_partitions = size;
94 : 1455305 : map->partition_size = size;
95 : 1455305 : map->num_basevars = 0;
96 : 1455305 : map->partition_to_base_index = NULL;
97 : 1455305 : map->vec_bbs = vNULL;
98 : 1455305 : if (loop)
99 : : {
100 : 0 : map->bmp_bbs = BITMAP_ALLOC (NULL);
101 : 0 : map->outofssa_p = false;
102 : 0 : basic_block *bbs = get_loop_body_in_dom_order (loop);
103 : 0 : for (unsigned i = 0; i < loop->num_nodes; ++i)
104 : : {
105 : 0 : bitmap_set_bit (map->bmp_bbs, bbs[i]->index);
106 : 0 : map->vec_bbs.safe_push (bbs[i]);
107 : : }
108 : 0 : free (bbs);
109 : : }
110 : : else
111 : : {
112 : 1455305 : map->bmp_bbs = NULL;
113 : 1455305 : map->outofssa_p = bitint == NULL;
114 : 1455305 : map->bitint = bitint;
115 : 1455305 : basic_block bb;
116 : 2910610 : map->vec_bbs.reserve_exact (n_basic_blocks_for_fn (cfun)
117 : 1455305 : - NUM_FIXED_BLOCKS);
118 : 13968964 : FOR_EACH_BB_FN (bb, cfun)
119 : 12513659 : map->vec_bbs.quick_push (bb);
120 : : }
121 : 1455305 : return map;
122 : : }
123 : :
124 : :
125 : : /* Free memory associated with MAP. */
126 : :
127 : : void
128 : 1455305 : delete_var_map (var_map map)
129 : : {
130 : 1455305 : var_map_base_fini (map);
131 : 1455305 : partition_delete (map->var_partition);
132 : 1455305 : free (map->partition_to_view);
133 : 1455305 : free (map->view_to_partition);
134 : 1455305 : if (map->bmp_bbs)
135 : 0 : BITMAP_FREE (map->bmp_bbs);
136 : 1455305 : map->vec_bbs.release ();
137 : 1455305 : free (map);
138 : 1455305 : }
139 : :
140 : :
141 : : /* This function will combine the partitions in MAP for VAR1 and VAR2. It
142 : : Returns the partition which represents the new partition. If the two
143 : : partitions cannot be combined, NO_PARTITION is returned. */
144 : :
145 : : int
146 : 5382345 : var_union (var_map map, tree var1, tree var2)
147 : : {
148 : 5382345 : int p1, p2, p3;
149 : :
150 : 5382345 : gcc_assert (TREE_CODE (var1) == SSA_NAME);
151 : 5382345 : gcc_assert (TREE_CODE (var2) == SSA_NAME);
152 : :
153 : : /* This is independent of partition_to_view. If partition_to_view is
154 : : on, then whichever one of these partitions is absorbed will never have a
155 : : dereference into the partition_to_view array any more. */
156 : :
157 : 5382345 : p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
158 : 5382345 : p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
159 : :
160 : 5382345 : gcc_assert (p1 != NO_PARTITION);
161 : 5382345 : gcc_assert (p2 != NO_PARTITION);
162 : :
163 : 5382345 : if (p1 == p2)
164 : : p3 = p1;
165 : : else
166 : 5382345 : p3 = partition_union (map->var_partition, p1, p2);
167 : :
168 : 5382345 : if (map->partition_to_view)
169 : 5382345 : p3 = map->partition_to_view[p3];
170 : :
171 : 5382345 : return p3;
172 : : }
173 : :
174 : :
175 : : /* Compress the partition numbers in MAP such that they fall in the range
176 : : 0..(num_partitions-1) instead of wherever they turned out during
177 : : the partitioning exercise. This removes any references to unused
178 : : partitions, thereby allowing bitmaps and other vectors to be much
179 : : denser.
180 : :
181 : : This is implemented such that compaction doesn't affect partitioning.
182 : : Ie., once partitions are created and possibly merged, running one
183 : : or more different kind of compaction will not affect the partitions
184 : : themselves. Their index might change, but all the same variables will
185 : : still be members of the same partition group. This allows work on reduced
186 : : sets, and no loss of information when a larger set is later desired.
187 : :
188 : : In particular, coalescing can work on partitions which have 2 or more
189 : : definitions, and then 'recompact' later to include all the single
190 : : definitions for assignment to program variables. */
191 : :
192 : :
193 : : /* Set MAP back to the initial state of having no partition view. Return a
194 : : bitmap which has a bit set for each partition number which is in use in the
195 : : varmap. */
196 : :
197 : : static bitmap
198 : 2910610 : partition_view_init (var_map map)
199 : : {
200 : 2910610 : bitmap used;
201 : 2910610 : int tmp;
202 : 2910610 : unsigned int x;
203 : :
204 : 2910610 : used = BITMAP_ALLOC (NULL);
205 : :
206 : : /* Already in a view? Abandon the old one. */
207 : 2910610 : if (map->partition_to_view)
208 : : {
209 : 1455305 : free (map->partition_to_view);
210 : 1455305 : map->partition_to_view = NULL;
211 : : }
212 : 2910610 : if (map->view_to_partition)
213 : : {
214 : 1455305 : free (map->view_to_partition);
215 : 1455305 : map->view_to_partition = NULL;
216 : : }
217 : :
218 : : /* Find out which partitions are actually referenced. */
219 : 146537710 : for (x = 0; x < map->partition_size; x++)
220 : : {
221 : 143627100 : tmp = partition_find (map->var_partition, x);
222 : 337336124 : if (ssa_name (tmp) != NULL_TREE && !virtual_operand_p (ssa_name (tmp))
223 : 206251208 : && (!has_zero_uses (ssa_name (tmp))
224 : 4136677 : || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))
225 : 3503359 : || (SSA_NAME_VAR (ssa_name (tmp))
226 : 3503359 : && !VAR_P (SSA_NAME_VAR (ssa_name (tmp))))))
227 : 62071838 : bitmap_set_bit (used, tmp);
228 : : }
229 : :
230 : 2910610 : map->num_partitions = map->partition_size;
231 : 2910610 : return used;
232 : : }
233 : :
234 : :
235 : : /* This routine will finalize the view data for MAP based on the partitions
236 : : set in SELECTED. This is either the same bitmap returned from
237 : : partition_view_init, or a trimmed down version if some of those partitions
238 : : were not desired in this view. SELECTED is freed before returning. */
239 : :
240 : : static void
241 : 2910610 : partition_view_fini (var_map map, bitmap selected)
242 : : {
243 : 2910610 : bitmap_iterator bi;
244 : 2910610 : unsigned count, i, x, limit;
245 : :
246 : 2910610 : gcc_assert (selected);
247 : :
248 : 2910610 : count = bitmap_count_bits (selected);
249 : 2910610 : limit = map->partition_size;
250 : :
251 : : /* If its a one-to-one ratio, we don't need any view compaction. */
252 : 2910610 : if (count < limit)
253 : : {
254 : 2910610 : map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
255 : 2910610 : memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
256 : 2910610 : map->view_to_partition = (int *)xmalloc (count * sizeof (int));
257 : :
258 : 2910610 : i = 0;
259 : : /* Give each selected partition an index. */
260 : 39776115 : EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
261 : : {
262 : 36865505 : map->partition_to_view[x] = i;
263 : 36865505 : map->view_to_partition[i] = x;
264 : 36865505 : i++;
265 : : }
266 : 2910610 : gcc_assert (i == count);
267 : 2910610 : map->num_partitions = i;
268 : : }
269 : :
270 : 2910610 : BITMAP_FREE (selected);
271 : 2910610 : }
272 : :
273 : :
274 : : /* Create a partition view which includes all the used partitions in MAP. */
275 : :
276 : : void
277 : 1455305 : partition_view_normal (var_map map)
278 : : {
279 : 1455305 : bitmap used;
280 : :
281 : 1455305 : used = partition_view_init (map);
282 : 1455305 : partition_view_fini (map, used);
283 : :
284 : 1455305 : var_map_base_fini (map);
285 : 1455305 : }
286 : :
287 : :
288 : : /* Create a partition view in MAP which includes just partitions which occur in
289 : : the bitmap ONLY. If WANT_BASES is true, create the base variable map
290 : : as well. */
291 : :
292 : : void
293 : 1455305 : partition_view_bitmap (var_map map, bitmap only)
294 : : {
295 : 1455305 : bitmap used;
296 : 1455305 : bitmap new_partitions = BITMAP_ALLOC (NULL);
297 : 1455305 : unsigned x, p;
298 : 1455305 : bitmap_iterator bi;
299 : :
300 : 1455305 : used = partition_view_init (map);
301 : 12667236 : EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
302 : : {
303 : 11211931 : p = partition_find (map->var_partition, x);
304 : 11211931 : gcc_assert (bitmap_bit_p (used, p));
305 : 11211931 : bitmap_set_bit (new_partitions, p);
306 : : }
307 : 1455305 : partition_view_fini (map, new_partitions);
308 : :
309 : 1455305 : var_map_base_fini (map);
310 : 1455305 : }
311 : :
312 : :
313 : : static bitmap usedvars;
314 : :
315 : : /* Mark VAR as used, so that it'll be preserved during rtl expansion.
316 : : Returns true if VAR wasn't marked before. */
317 : :
318 : : static inline bool
319 : 180181390 : set_is_used (tree var)
320 : : {
321 : 180181390 : return bitmap_set_bit (usedvars, DECL_UID (var));
322 : : }
323 : :
324 : : /* Return true if VAR is marked as used. */
325 : :
326 : : static inline bool
327 : 194839918 : is_used_p (tree var)
328 : : {
329 : 194839918 : return bitmap_bit_p (usedvars, DECL_UID (var));
330 : : }
331 : :
332 : : static inline void mark_all_vars_used (tree *);
333 : :
334 : : /* Helper function for mark_all_vars_used, called via walk_tree. */
335 : :
336 : : static tree
337 : 1063969675 : mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
338 : : {
339 : 1063969675 : tree t = *tp;
340 : 1063969675 : enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
341 : 1063969675 : tree b;
342 : :
343 : 1063969675 : if (TREE_CODE (t) == SSA_NAME)
344 : : {
345 : 399758910 : *walk_subtrees = 0;
346 : 399758910 : t = SSA_NAME_VAR (t);
347 : : if (!t)
348 : : return NULL;
349 : : }
350 : :
351 : 796185848 : if (IS_EXPR_CODE_CLASS (c)
352 : 796185848 : && (b = TREE_BLOCK (t)) != NULL)
353 : 77481381 : TREE_USED (b) = true;
354 : :
355 : : /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those
356 : : fields do not contain vars. */
357 : 796185848 : if (TREE_CODE (t) == TARGET_MEM_REF)
358 : : {
359 : 1704895 : mark_all_vars_used (&TMR_BASE (t));
360 : 1704895 : mark_all_vars_used (&TMR_INDEX (t));
361 : 1704895 : mark_all_vars_used (&TMR_INDEX2 (t));
362 : 1704895 : *walk_subtrees = 0;
363 : 1704895 : return NULL;
364 : : }
365 : :
366 : : /* Only need to mark VAR_DECLS; parameters and return results are not
367 : : eliminated as unused. */
368 : 794480953 : if (VAR_P (t))
369 : : {
370 : : /* When a global var becomes used for the first time also walk its
371 : : initializer (non global ones don't have any). */
372 : 221723997 : if (set_is_used (t) && is_global_var (t)
373 : 187231390 : && DECL_CONTEXT (t) == current_function_decl)
374 : 1045837 : mark_all_vars_used (&DECL_INITIAL (t));
375 : : }
376 : : /* remove_unused_scope_block_p requires information about labels
377 : : which are not DECL_IGNORED_P to tell if they might be used in the IL. */
378 : 614299563 : else if (TREE_CODE (t) == LABEL_DECL)
379 : : /* Although the TREE_USED values that the frontend uses would be
380 : : acceptable (albeit slightly over-conservative) for our purposes,
381 : : init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we
382 : : must re-compute it here. */
383 : 6609619 : TREE_USED (t) = 1;
384 : :
385 : 794480953 : if (IS_TYPE_OR_DECL_P (t))
386 : 357335115 : *walk_subtrees = 0;
387 : :
388 : : return NULL;
389 : : }
390 : :
391 : : /* Mark the scope block SCOPE and its subblocks unused when they can be
392 : : possibly eliminated if dead. */
393 : :
394 : : static void
395 : 121052867 : mark_scope_block_unused (tree scope)
396 : : {
397 : 121052867 : tree t;
398 : 121052867 : TREE_USED (scope) = false;
399 : 121052867 : if (!(*debug_hooks->ignore_block) (scope))
400 : 428556 : TREE_USED (scope) = true;
401 : 230468995 : for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
402 : 109416128 : mark_scope_block_unused (t);
403 : 121052867 : }
404 : :
405 : : /* Look if the block is dead (by possibly eliminating its dead subblocks)
406 : : and return true if so.
407 : : Block is declared dead if:
408 : : 1) No statements are associated with it.
409 : : 2) Declares no live variables
410 : : 3) All subblocks are dead
411 : : or there is precisely one subblocks and the block
412 : : has same abstract origin as outer block and declares
413 : : no variables, so it is pure wrapper.
414 : : When we are not outputting full debug info, we also eliminate dead variables
415 : : out of scope blocks to let them to be recycled by GGC and to save copying work
416 : : done by the inliner. */
417 : :
418 : : static bool
419 : 121052867 : remove_unused_scope_block_p (tree scope, bool in_ctor_dtor_block)
420 : : {
421 : 121052867 : tree *t, *next;
422 : 121052867 : bool unused = !TREE_USED (scope);
423 : 121052867 : int nsubblocks = 0;
424 : :
425 : : /* For ipa-polymorphic-call.cc purposes, preserve blocks:
426 : : 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
427 : 121052867 : if (inlined_polymorphic_ctor_dtor_block_p (scope, true))
428 : : {
429 : : in_ctor_dtor_block = true;
430 : : unused = false;
431 : : }
432 : : /* 2) inside such blocks, the outermost block with block_ultimate_origin
433 : : being a FUNCTION_DECL. */
434 : 101666316 : else if (in_ctor_dtor_block)
435 : : {
436 : 16989020 : tree fn = block_ultimate_origin (scope);
437 : 16989020 : if (fn && TREE_CODE (fn) == FUNCTION_DECL)
438 : : {
439 : 121052867 : in_ctor_dtor_block = false;
440 : 121052867 : unused = false;
441 : : }
442 : : }
443 : :
444 : 240570341 : for (t = &BLOCK_VARS (scope); *t; t = next)
445 : : {
446 : 119517474 : next = &DECL_CHAIN (*t);
447 : :
448 : : /* Debug info of nested function refers to the block of the
449 : : function. We might stil call it even if all statements
450 : : of function it was nested into was elliminated.
451 : :
452 : : TODO: We can actually look into cgraph to see if function
453 : : will be output to file. */
454 : 119517474 : if (TREE_CODE (*t) == FUNCTION_DECL)
455 : : unused = false;
456 : :
457 : : /* If a decl has a value expr, we need to instantiate it
458 : : regardless of debug info generation, to avoid codegen
459 : : differences in memory overlap tests. update_equiv_regs() may
460 : : indirectly call validate_equiv_mem() to test whether a
461 : : SET_DEST overlaps with others, and if the value expr changes
462 : : by virtual register instantiation, we may get end up with
463 : : different results. */
464 : 119183132 : else if (VAR_P (*t) && DECL_HAS_VALUE_EXPR_P (*t))
465 : : unused = false;
466 : :
467 : : /* Remove everything we don't generate debug info for. */
468 : 117625436 : else if (DECL_IGNORED_P (*t))
469 : : {
470 : 4153221 : *t = DECL_CHAIN (*t);
471 : 4153221 : next = t;
472 : : }
473 : :
474 : : /* When we are outputting debug info, we usually want to output
475 : : info about optimized-out variables in the scope blocks.
476 : : Exception are the scope blocks not containing any instructions
477 : : at all so user can't get into the scopes at first place. */
478 : 113472215 : else if (is_used_p (*t))
479 : : unused = false;
480 : 99491930 : else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t))
481 : : /* For labels that are still used in the IL, the decision to
482 : : preserve them must not depend DEBUG_INFO_LEVEL, otherwise we
483 : : risk having different ordering in debug vs. non-debug builds
484 : : during inlining or versioning.
485 : : A label appearing here (we have already checked DECL_IGNORED_P)
486 : : should not be used in the IL unless it has been explicitly used
487 : : before, so we use TREE_USED as an approximation. */
488 : : /* In principle, we should do the same here as for the debug case
489 : : below, however, when debugging, there might be additional nested
490 : : levels that keep an upper level with a label live, so we have to
491 : : force this block to be considered used, too. */
492 : : unused = false;
493 : :
494 : : /* When we are not doing full debug info, we however can keep around
495 : : only the used variables for cfgexpand's memory packing saving quite
496 : : a lot of memory.
497 : :
498 : : For sake of -g3, we keep around those vars but we don't count this as
499 : : use of block, so innermost block with no used vars and no instructions
500 : : can be considered dead. We only want to keep around blocks user can
501 : : breakpoint into and ask about value of optimized out variables.
502 : :
503 : : Similarly we need to keep around types at least until all
504 : : variables of all nested blocks are gone. We track no
505 : : information on whether given type is used or not, so we have
506 : : to keep them even when not emitting debug information,
507 : : otherwise we may end up remapping variables and their (local)
508 : : types in different orders depending on whether debug
509 : : information is being generated. */
510 : :
511 : 98918907 : else if (TREE_CODE (*t) == TYPE_DECL
512 : 94040106 : || debug_info_level == DINFO_LEVEL_NORMAL
513 : 2319691 : || debug_info_level == DINFO_LEVEL_VERBOSE)
514 : : ;
515 : : else
516 : : {
517 : 2310390 : *t = DECL_CHAIN (*t);
518 : 2310390 : next = t;
519 : : }
520 : : }
521 : :
522 : 230468995 : for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
523 : 109416128 : if (remove_unused_scope_block_p (*t, in_ctor_dtor_block))
524 : : {
525 : 8626437 : if (BLOCK_SUBBLOCKS (*t))
526 : : {
527 : 2803371 : tree next = BLOCK_CHAIN (*t);
528 : 2803371 : tree supercontext = BLOCK_SUPERCONTEXT (*t);
529 : :
530 : 2803371 : *t = BLOCK_SUBBLOCKS (*t);
531 : 3463993 : while (BLOCK_CHAIN (*t))
532 : : {
533 : 660622 : BLOCK_SUPERCONTEXT (*t) = supercontext;
534 : 660622 : t = &BLOCK_CHAIN (*t);
535 : : }
536 : 2803371 : BLOCK_CHAIN (*t) = next;
537 : 2803371 : BLOCK_SUPERCONTEXT (*t) = supercontext;
538 : 2803371 : t = &BLOCK_CHAIN (*t);
539 : 2803371 : nsubblocks ++;
540 : : }
541 : : else
542 : 5823066 : *t = BLOCK_CHAIN (*t);
543 : : }
544 : : else
545 : : {
546 : 100789691 : t = &BLOCK_CHAIN (*t);
547 : 100789691 : nsubblocks ++;
548 : : }
549 : :
550 : :
551 : 121052867 : if (!unused)
552 : : ;
553 : : /* Outer scope is always used. */
554 : 26237272 : else if (!BLOCK_SUPERCONTEXT (scope)
555 : 26237272 : || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
556 : : unused = false;
557 : : /* Innermost blocks with no live variables nor statements can be always
558 : : eliminated. */
559 : 25127053 : else if (!nsubblocks)
560 : : ;
561 : : /* When not generating debug info we can eliminate info on unused
562 : : variables. */
563 : 19303987 : else if (!flag_auto_profile
564 : 19303987 : && debug_info_level == DINFO_LEVEL_NONE
565 : 20900254 : && !optinfo_wants_inlining_info_p ())
566 : : {
567 : : /* Even for -g0 don't prune outer scopes from inlined functions,
568 : : otherwise late diagnostics from such functions will not be
569 : : emitted or suppressed properly. */
570 : 1596199 : if (inlined_function_outer_scope_p (scope))
571 : : {
572 : 1345119 : gcc_assert (TREE_CODE (BLOCK_ORIGIN (scope)) == FUNCTION_DECL);
573 : : unused = false;
574 : : }
575 : : }
576 : 17707788 : else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
577 : : unused = false;
578 : : /* See if this block is important for representation of inlined
579 : : function. Inlined functions are always represented by block
580 : : with block_ultimate_origin being set to FUNCTION_DECL and
581 : : DECL_SOURCE_LOCATION set, unless they expand to nothing... */
582 : 2692808 : else if (inlined_function_outer_scope_p (scope))
583 : : unused = false;
584 : : else
585 : : /* Verfify that only blocks with source location set
586 : : are entry points to the inlined functions. */
587 : 2552291 : gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope))
588 : : == UNKNOWN_LOCATION);
589 : :
590 : 121052867 : TREE_USED (scope) = !unused;
591 : 121052867 : return unused;
592 : : }
593 : :
594 : : /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
595 : : eliminated during the tree->rtl conversion process. */
596 : :
597 : : static inline void
598 : 792690089 : mark_all_vars_used (tree *expr_p)
599 : : {
600 : 792690089 : walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
601 : 792690089 : }
602 : :
603 : : /* Helper function for clear_unused_block_pointer, called via walk_tree. */
604 : :
605 : : static tree
606 : 490477829 : clear_unused_block_pointer_1 (tree *tp, int *, void *)
607 : : {
608 : 86100614 : if (EXPR_P (*tp) && TREE_BLOCK (*tp)
609 : 548185655 : && !TREE_USED (TREE_BLOCK (*tp)))
610 : 1316151 : TREE_SET_BLOCK (*tp, NULL);
611 : 490477829 : return NULL_TREE;
612 : : }
613 : :
614 : : /* Clear references to unused BLOCKs from DECL_VALUE_EXPRs of variables
615 : : in BLOCK. */
616 : :
617 : : static void
618 : 112426430 : clear_unused_block_pointer_in_block (tree block)
619 : : {
620 : 221920475 : for (tree t = BLOCK_VARS (block); t; t = DECL_CHAIN (t))
621 : 109494045 : if (VAR_P (t) && DECL_HAS_VALUE_EXPR_P (t))
622 : : {
623 : 1557696 : tree val = DECL_VALUE_EXPR (t);
624 : 1557696 : walk_tree (&val, clear_unused_block_pointer_1, NULL, NULL);
625 : : }
626 : 213216121 : for (tree t = BLOCK_SUBBLOCKS (block); t; t = BLOCK_CHAIN (t))
627 : 100789691 : clear_unused_block_pointer_in_block (t);
628 : 112426430 : }
629 : :
630 : : /* Set all block pointer in debug or clobber stmt to NULL if the block
631 : : is unused, so that they will not be streamed out. */
632 : :
633 : : static void
634 : 11636739 : clear_unused_block_pointer (void)
635 : : {
636 : 11636739 : basic_block bb;
637 : 11636739 : gimple_stmt_iterator gsi;
638 : :
639 : 92106557 : FOR_EACH_BB_FN (bb, cfun)
640 : 717693325 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
641 : : {
642 : 558393219 : unsigned i;
643 : 558393219 : tree b;
644 : 558393219 : gimple *stmt;
645 : :
646 : 556755602 : next:
647 : 558393219 : stmt = gsi_stmt (gsi);
648 : 558393219 : if (!is_gimple_debug (stmt) && !gimple_clobber_p (stmt))
649 : 262632708 : continue;
650 : 295760511 : b = gimple_block (stmt);
651 : 295760511 : if (b && !TREE_USED (b))
652 : : {
653 : : /* Elide debug marker stmts that have an associated BLOCK from an
654 : : inline instance removed with also the outermost scope BLOCK of
655 : : said inline instance removed. If the outermost scope BLOCK of
656 : : said inline instance is preserved use that in place of the
657 : : removed BLOCK. That keeps the marker associated to the correct
658 : : inline instance (or no inline instance in case it was not from
659 : : an inline instance). */
660 : 6899442 : if (gimple_debug_nonbind_marker_p (stmt)
661 : 8690580 : && BLOCK_ABSTRACT_ORIGIN (b))
662 : : {
663 : 2174277 : while (TREE_CODE (b) == BLOCK
664 : 2174277 : && !inlined_function_outer_scope_p (b))
665 : 397862 : b = BLOCK_SUPERCONTEXT (b);
666 : 1776415 : if (TREE_CODE (b) == BLOCK)
667 : : {
668 : 1775642 : if (TREE_USED (b))
669 : : {
670 : 136112 : gimple_set_block (stmt, b);
671 : 136112 : continue;
672 : : }
673 : 1639530 : gsi_remove (&gsi, true);
674 : 1639530 : if (gsi_end_p (gsi))
675 : : break;
676 : 1637617 : goto next;
677 : : }
678 : : }
679 : 5123800 : gimple_set_block (stmt, NULL);
680 : : }
681 : 743906123 : for (i = 0; i < gimple_num_ops (stmt); i++)
682 : 449921254 : walk_tree (gimple_op_ptr (stmt, i), clear_unused_block_pointer_1,
683 : : NULL, NULL);
684 : : }
685 : :
686 : : /* Walk all variables mentioned in the functions BLOCK tree and clear
687 : : DECL_VALUE_EXPR from unused blocks where present. */
688 : 11636739 : clear_unused_block_pointer_in_block (DECL_INITIAL (current_function_decl));
689 : 11636739 : }
690 : :
691 : : /* Dump scope blocks starting at SCOPE to FILE. INDENT is the
692 : : indentation level and FLAGS is as in print_generic_expr. */
693 : :
694 : : static void
695 : 4420 : dump_scope_block (FILE *file, int indent, tree scope, dump_flags_t flags)
696 : : {
697 : 4420 : tree var, t;
698 : 4420 : unsigned int i;
699 : :
700 : 4420 : fprintf (file, "\n%*s{ Scope block #%i%s",indent, "" , BLOCK_NUMBER (scope),
701 : 4420 : TREE_USED (scope) ? "" : " (unused)");
702 : 4420 : if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope)) != UNKNOWN_LOCATION)
703 : : {
704 : 941 : expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
705 : 941 : fprintf (file, " %s:%i:%i", s.file, s.line, s.column);
706 : 941 : if (has_discriminator (BLOCK_SOURCE_LOCATION (scope)))
707 : 58 : fprintf (file, " discrim %i",
708 : 29 : get_discriminator_from_loc (BLOCK_SOURCE_LOCATION (scope)));
709 : : }
710 : 4420 : if (BLOCK_ABSTRACT_ORIGIN (scope))
711 : : {
712 : 2051 : tree origin = block_ultimate_origin (scope);
713 : 2051 : if (origin)
714 : : {
715 : 2051 : fprintf (file, " Originating from :");
716 : 2051 : if (DECL_P (origin))
717 : 941 : print_generic_decl (file, origin, flags);
718 : : else
719 : 1110 : fprintf (file, "#%i", BLOCK_NUMBER (origin));
720 : : }
721 : : }
722 : 4420 : if (BLOCK_FRAGMENT_ORIGIN (scope))
723 : 0 : fprintf (file, " Fragment of : #%i",
724 : 0 : BLOCK_NUMBER (BLOCK_FRAGMENT_ORIGIN (scope)));
725 : 4420 : else if (BLOCK_FRAGMENT_CHAIN (scope))
726 : : {
727 : 0 : fprintf (file, " Fragment chain :");
728 : 0 : for (t = BLOCK_FRAGMENT_CHAIN (scope); t ;
729 : 0 : t = BLOCK_FRAGMENT_CHAIN (t))
730 : 0 : fprintf (file, " #%i", BLOCK_NUMBER (t));
731 : : }
732 : 4420 : fprintf (file, " \n");
733 : 8270 : for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var))
734 : : {
735 : 3850 : fprintf (file, "%*s", indent, "");
736 : 3850 : print_generic_decl (file, var, flags);
737 : 3850 : fprintf (file, "\n");
738 : : }
739 : 4420 : for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
740 : : {
741 : 0 : fprintf (file, "%*s",indent, "");
742 : 0 : print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
743 : : flags);
744 : 0 : fprintf (file, " (nonlocalized)\n");
745 : : }
746 : 6853 : for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
747 : 2433 : dump_scope_block (file, indent + 2, t, flags);
748 : 4420 : fprintf (file, "\n%*s}\n",indent, "");
749 : 4420 : }
750 : :
751 : : /* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS
752 : : is as in print_generic_expr. */
753 : :
754 : : DEBUG_FUNCTION void
755 : 0 : debug_scope_block (tree scope, dump_flags_t flags)
756 : : {
757 : 0 : dump_scope_block (stderr, 0, scope, flags);
758 : 0 : }
759 : :
760 : :
761 : : /* Dump the tree of lexical scopes of current_function_decl to FILE.
762 : : FLAGS is as in print_generic_expr. */
763 : :
764 : : void
765 : 1987 : dump_scope_blocks (FILE *file, dump_flags_t flags)
766 : : {
767 : 1987 : dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
768 : 1987 : }
769 : :
770 : :
771 : : /* Dump the tree of lexical scopes of current_function_decl to stderr.
772 : : FLAGS is as in print_generic_expr. */
773 : :
774 : : DEBUG_FUNCTION void
775 : 0 : debug_scope_blocks (dump_flags_t flags)
776 : : {
777 : 0 : dump_scope_blocks (stderr, flags);
778 : 0 : }
779 : :
780 : : /* Remove local variables that are not referenced in the IL. */
781 : :
782 : : void
783 : 12940901 : remove_unused_locals (void)
784 : : {
785 : 12940901 : basic_block bb;
786 : 12940901 : tree var;
787 : 12940901 : unsigned srcidx, dstidx, num;
788 : 12940901 : bool have_local_clobbers = false;
789 : :
790 : : /* Removing declarations from lexical blocks when not optimizing is
791 : : not only a waste of time, it actually causes differences in stack
792 : : layout. */
793 : 12940901 : if (!optimize)
794 : 1304162 : return;
795 : :
796 : 11636739 : timevar_push (TV_REMOVE_UNUSED);
797 : :
798 : 11636739 : mark_scope_block_unused (DECL_INITIAL (current_function_decl));
799 : :
800 : 11636739 : usedvars = BITMAP_ALLOC (NULL);
801 : 11636739 : auto_bitmap useddebug;
802 : :
803 : : /* Walk the CFG marking all referenced symbols. */
804 : 92106557 : FOR_EACH_BB_FN (bb, cfun)
805 : : {
806 : 80469818 : gimple_stmt_iterator gsi;
807 : 80469818 : size_t i;
808 : 80469818 : edge_iterator ei;
809 : 80469818 : edge e;
810 : :
811 : : /* Walk the statements. */
812 : 724911099 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
813 : : {
814 : 563971463 : gimple *stmt = gsi_stmt (gsi);
815 : 563971463 : tree b = gimple_block (stmt);
816 : :
817 : : /* If we wanted to mark the block referenced by the inline
818 : : entry point marker as used, this would be a good spot to
819 : : do it. If the block is not otherwise used, the stmt will
820 : : be cleaned up in clean_unused_block_pointer. */
821 : 563971463 : if (is_gimple_debug (stmt))
822 : : {
823 : 285465196 : if (gimple_debug_bind_p (stmt))
824 : : {
825 : 214135586 : tree var = gimple_debug_bind_get_var (stmt);
826 : 214135586 : if (VAR_P (var))
827 : : {
828 : 201233841 : if (!gimple_debug_bind_get_value (stmt))
829 : : /* Run the 2nd phase. */
830 : : have_local_clobbers = true;
831 : : else
832 : 107256800 : bitmap_set_bit (useddebug, DECL_UID (var));
833 : : }
834 : : }
835 : 285465196 : continue;
836 : 285465196 : }
837 : :
838 : 278506267 : if (gimple_clobber_p (stmt))
839 : : {
840 : 15873548 : have_local_clobbers = true;
841 : 15873548 : continue;
842 : : }
843 : :
844 : 262632719 : if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
845 : : {
846 : 1167 : have_local_clobbers = true;
847 : 1167 : continue;
848 : : }
849 : :
850 : 262631552 : if (b)
851 : 238250227 : TREE_USED (b) = true;
852 : :
853 : 999623262 : for (i = 0; i < gimple_num_ops (stmt); i++)
854 : 736991710 : mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i));
855 : : }
856 : :
857 : 80469818 : for (gphi_iterator gpi = gsi_start_phis (bb);
858 : 108236918 : !gsi_end_p (gpi);
859 : 27767100 : gsi_next (&gpi))
860 : : {
861 : 27767100 : use_operand_p arg_p;
862 : 27767100 : ssa_op_iter i;
863 : 27767100 : tree def;
864 : 27767100 : gphi *phi = gpi.phi ();
865 : :
866 : 55534200 : if (virtual_operand_p (gimple_phi_result (phi)))
867 : 12862322 : continue;
868 : :
869 : 14904778 : def = gimple_phi_result (phi);
870 : 14904778 : mark_all_vars_used (&def);
871 : :
872 : 49537857 : FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
873 : : {
874 : 34633079 : tree arg = USE_FROM_PTR (arg_p);
875 : 34633079 : int index = PHI_ARG_INDEX_FROM_USE (arg_p);
876 : 34633079 : tree block =
877 : 34633079 : LOCATION_BLOCK (gimple_phi_arg_location (phi, index));
878 : 20011838 : if (block != NULL)
879 : 20008030 : TREE_USED (block) = true;
880 : 34633079 : mark_all_vars_used (&arg);
881 : : }
882 : : }
883 : :
884 : 192617647 : FOR_EACH_EDGE (e, ei, bb->succs)
885 : 112147829 : if (LOCATION_BLOCK (e->goto_locus) != NULL)
886 : 24747503 : TREE_USED (LOCATION_BLOCK (e->goto_locus)) = true;
887 : : }
888 : :
889 : : /* We do a two-pass approach about the out-of-scope clobbers. We want
890 : : to remove them if they are the only references to a local variable,
891 : : but we want to retain them when there's any other. So the first pass
892 : : ignores them, and the second pass (if there were any) tries to remove
893 : : them. We do the same for .DEFERRED_INIT. */
894 : 11636739 : if (have_local_clobbers)
895 : 62797045 : FOR_EACH_BB_FN (bb, cfun)
896 : : {
897 : 57552399 : gimple_stmt_iterator gsi;
898 : :
899 : 597307392 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
900 : : {
901 : 482202594 : gimple *stmt = gsi_stmt (gsi);
902 : 482202594 : tree b = gimple_block (stmt);
903 : :
904 : 482202594 : if (gimple_clobber_p (stmt))
905 : : {
906 : 15873548 : tree lhs = gimple_assign_lhs (stmt);
907 : 15873548 : tree base = get_base_address (lhs);
908 : : /* Remove clobbers referencing unused vars, or clobbers
909 : : with MEM_REF lhs referencing uninitialized pointers. */
910 : 13552092 : if ((VAR_P (base) && !is_used_p (base))
911 : 28456177 : || (TREE_CODE (lhs) == MEM_REF
912 : 4171015 : && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME
913 : 2278633 : && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs, 0))
914 : 1509452 : && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))
915 : : != PARM_DECL)))
916 : : {
917 : 1002833 : unlink_stmt_vdef (stmt);
918 : 1002833 : gsi_remove (&gsi, true);
919 : 1002833 : release_defs (stmt);
920 : 1002833 : continue;
921 : : }
922 : 14870715 : if (b)
923 : 9998489 : TREE_USED (b) = true;
924 : : }
925 : 466329046 : else if (gimple_call_internal_p (stmt, IFN_DEFERRED_INIT))
926 : : {
927 : 1167 : tree lhs = gimple_call_lhs (stmt);
928 : 1167 : tree base = get_base_address (lhs);
929 : 1167 : if (DECL_P (base) && !is_used_p (base))
930 : : {
931 : 11 : unlink_stmt_vdef (stmt);
932 : 11 : gsi_remove (&gsi, true);
933 : 11 : release_defs (stmt);
934 : 11 : continue;
935 : : }
936 : 1156 : if (b)
937 : 1156 : TREE_USED (b) = true;
938 : : }
939 : 466327879 : else if (gimple_debug_bind_p (stmt))
940 : : {
941 : 211095252 : tree var = gimple_debug_bind_get_var (stmt);
942 : 215670652 : if (VAR_P (var)
943 : 198448454 : && !bitmap_bit_p (useddebug, DECL_UID (var))
944 : 216252398 : && !is_used_p (var))
945 : : {
946 : 4575400 : if (dump_file && (dump_flags & TDF_DETAILS))
947 : 0 : fprintf (dump_file, "Dead debug bind reset to %u\n",
948 : 0 : DECL_UID (var));
949 : 4575400 : gsi_remove (&gsi, true);
950 : 4575400 : continue;
951 : : }
952 : : }
953 : 476624350 : gsi_next (&gsi);
954 : : }
955 : : }
956 : :
957 : 11636739 : if (cfun->has_simduid_loops)
958 : : {
959 : 124592 : for (auto loop : loops_list (cfun, 0))
960 : 46490 : if (loop->simduid && !is_used_p (loop->simduid))
961 : 26314 : loop->simduid = NULL_TREE;
962 : : }
963 : :
964 : 11636739 : cfun->has_local_explicit_reg_vars = false;
965 : :
966 : : /* Remove unmarked local and global vars from local_decls. */
967 : 11636739 : num = vec_safe_length (cfun->local_decls);
968 : 74283678 : for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
969 : : {
970 : 62646939 : var = (*cfun->local_decls)[srcidx];
971 : 62646939 : if (VAR_P (var))
972 : : {
973 : 62646939 : if (!is_used_p (var))
974 : : {
975 : 27050577 : tree def;
976 : 27050577 : if (cfun->nonlocal_goto_save_area
977 : 27050577 : && TREE_OPERAND (cfun->nonlocal_goto_save_area, 0) == var)
978 : 10 : cfun->nonlocal_goto_save_area = NULL;
979 : : /* Release any default def associated with var. */
980 : 27050577 : if ((def = ssa_default_def (cfun, var)) != NULL_TREE)
981 : : {
982 : 1094213 : set_ssa_default_def (cfun, var, NULL_TREE);
983 : 1094213 : release_ssa_name (def);
984 : : }
985 : 27050577 : continue;
986 : 27050577 : }
987 : : }
988 : 35596362 : if (VAR_P (var) && DECL_HARD_REGISTER (var) && !is_global_var (var))
989 : 6608 : cfun->has_local_explicit_reg_vars = true;
990 : :
991 : 35596362 : if (srcidx != dstidx)
992 : 14770254 : (*cfun->local_decls)[dstidx] = var;
993 : 35596362 : dstidx++;
994 : : }
995 : 11636739 : if (dstidx != num)
996 : : {
997 : 4204746 : statistics_counter_event (cfun, "unused VAR_DECLs removed", num - dstidx);
998 : 4204746 : cfun->local_decls->truncate (dstidx);
999 : : }
1000 : :
1001 : 11636739 : remove_unused_scope_block_p (DECL_INITIAL (current_function_decl),
1002 : 11636739 : polymorphic_ctor_dtor_p (current_function_decl,
1003 : : true) != NULL_TREE);
1004 : 11636739 : clear_unused_block_pointer ();
1005 : :
1006 : 11636739 : BITMAP_FREE (usedvars);
1007 : :
1008 : 11636739 : if (dump_file && (dump_flags & TDF_DETAILS))
1009 : : {
1010 : 1985 : fprintf (dump_file, "Scope blocks after cleanups:\n");
1011 : 1985 : dump_scope_blocks (dump_file, dump_flags);
1012 : : }
1013 : :
1014 : 11636739 : timevar_pop (TV_REMOVE_UNUSED);
1015 : 11636739 : }
1016 : :
1017 : : /* Allocate and return a new live range information object base on MAP. */
1018 : :
1019 : : static tree_live_info_p
1020 : 1273037 : new_tree_live_info (var_map map)
1021 : : {
1022 : 1273037 : tree_live_info_p live;
1023 : 1273037 : basic_block bb;
1024 : :
1025 : 1273037 : live = XNEW (struct tree_live_info_d);
1026 : 1273037 : live->map = map;
1027 : 1273037 : live->num_blocks = last_basic_block_for_fn (cfun);
1028 : :
1029 : 1273037 : bitmap_obstack_initialize (&live->livein_obstack);
1030 : 1273037 : bitmap_obstack_initialize (&live->liveout_obstack);
1031 : :
1032 : 1273037 : live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1033 : 1273037 : live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1034 : 12978129 : for (unsigned i = 0; map->vec_bbs.iterate (i, &bb); ++i)
1035 : : {
1036 : 11705092 : bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
1037 : 11705092 : bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
1038 : : }
1039 : :
1040 : 1273037 : live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun));
1041 : 1273037 : live->stack_top = live->work_stack;
1042 : :
1043 : 1273037 : return live;
1044 : : }
1045 : :
1046 : :
1047 : : /* Free storage for live range info object LIVE. */
1048 : :
1049 : : void
1050 : 1273037 : delete_tree_live_info (tree_live_info_p live)
1051 : : {
1052 : 1273037 : if (live->livein)
1053 : : {
1054 : 0 : bitmap_obstack_release (&live->livein_obstack);
1055 : 0 : free (live->livein);
1056 : : }
1057 : 1273037 : if (live->liveout)
1058 : : {
1059 : 1273037 : bitmap_obstack_release (&live->liveout_obstack);
1060 : 1273037 : free (live->liveout);
1061 : : }
1062 : 1273037 : free (live->work_stack);
1063 : 1273037 : free (live);
1064 : 1273037 : }
1065 : :
1066 : :
1067 : : /* Visit basic block BB and propagate any required live on entry bits from
1068 : : LIVE into the predecessors. VISITED is the bitmap of visited blocks.
1069 : : TMP is a temporary work bitmap which is passed in to avoid reallocating
1070 : : it each time. */
1071 : :
1072 : : static void
1073 : 13550269 : loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited)
1074 : : {
1075 : 13550269 : edge e;
1076 : 13550269 : bool change;
1077 : 13550269 : edge_iterator ei;
1078 : 13550269 : basic_block pred_bb;
1079 : 13550269 : bitmap loe;
1080 : :
1081 : 13550269 : gcc_checking_assert (!bitmap_bit_p (visited, bb->index));
1082 : 13550269 : bitmap_set_bit (visited, bb->index);
1083 : :
1084 : 13550269 : loe = live_on_entry (live, bb);
1085 : :
1086 : 33338345 : FOR_EACH_EDGE (e, ei, bb->preds)
1087 : : {
1088 : 19788076 : pred_bb = e->src;
1089 : 19788076 : if (!region_contains_p (live->map, pred_bb))
1090 : 1290018 : continue;
1091 : : /* Variables live-on-entry from BB that aren't defined in the
1092 : : predecessor block. This should be the live on entry vars to pred.
1093 : : Note that liveout is the DEFs in a block while live on entry is
1094 : : being calculated.
1095 : : Add these bits to live-on-entry for the pred. if there are any
1096 : : changes, and pred_bb has been visited already, add it to the
1097 : : revisit stack. */
1098 : 18498058 : change = bitmap_ior_and_compl_into (live_on_entry (live, pred_bb),
1099 : 18498058 : loe, &live->liveout[pred_bb->index]);
1100 : 18498058 : if (change
1101 : 18498058 : && bitmap_bit_p (visited, pred_bb->index))
1102 : : {
1103 : 1845177 : bitmap_clear_bit (visited, pred_bb->index);
1104 : 1845177 : *(live->stack_top)++ = pred_bb->index;
1105 : : }
1106 : : }
1107 : 13550269 : }
1108 : :
1109 : :
1110 : : /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
1111 : : of all the variables. */
1112 : :
1113 : : static void
1114 : 1273037 : live_worklist (tree_live_info_p live)
1115 : : {
1116 : 1273037 : unsigned b;
1117 : 1273037 : basic_block bb;
1118 : 1273037 : auto_sbitmap visited (last_basic_block_for_fn (cfun) + 1);
1119 : :
1120 : 1273037 : bitmap_clear (visited);
1121 : :
1122 : : /* Visit region's blocks in reverse order and propagate live on entry values
1123 : : into the predecessors blocks. */
1124 : 14251166 : for (unsigned i = live->map->vec_bbs.length () - 1;
1125 : 12978129 : live->map->vec_bbs.iterate (i, &bb); --i)
1126 : 11705092 : loe_visit_block (live, bb, visited);
1127 : :
1128 : : /* Process any blocks which require further iteration. */
1129 : 3118214 : while (live->stack_top != live->work_stack)
1130 : : {
1131 : 1845177 : b = *--(live->stack_top);
1132 : 1845177 : loe_visit_block (live, BASIC_BLOCK_FOR_FN (cfun, b), visited);
1133 : : }
1134 : 1273037 : }
1135 : :
1136 : :
1137 : : /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
1138 : : links. Set the live on entry fields in LIVE. Def's are marked temporarily
1139 : : in the liveout vector. */
1140 : :
1141 : : static void
1142 : 11211931 : set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
1143 : : {
1144 : 11211931 : int p;
1145 : 11211931 : gimple *stmt;
1146 : 11211931 : use_operand_p use;
1147 : 11211931 : basic_block def_bb = NULL;
1148 : 11211931 : imm_use_iterator imm_iter;
1149 : :
1150 : 11211931 : p = var_to_partition (live->map, ssa_name);
1151 : 11211931 : if (p == NO_PARTITION)
1152 : 711371 : return;
1153 : :
1154 : 11211931 : stmt = SSA_NAME_DEF_STMT (ssa_name);
1155 : 11211931 : if (stmt)
1156 : : {
1157 : 11211931 : def_bb = gimple_bb (stmt);
1158 : : /* Mark defs in liveout bitmap temporarily. */
1159 : 11211931 : if (def_bb && region_contains_p (live->map, def_bb))
1160 : 7584091 : bitmap_set_bit (&live->liveout[def_bb->index], p);
1161 : : }
1162 : : else
1163 : 0 : def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1164 : :
1165 : : /* An undefined local variable does not need to be very alive. */
1166 : 11211931 : if (ssa_undefined_value_p (ssa_name, false))
1167 : : return;
1168 : :
1169 : : /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
1170 : : add it to the list of live on entry blocks. */
1171 : 34709003 : FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
1172 : : {
1173 : 24208443 : gimple *use_stmt = USE_STMT (use);
1174 : 24208443 : basic_block add_block = NULL;
1175 : :
1176 : 24208443 : if (gimple_code (use_stmt) == GIMPLE_PHI)
1177 : : {
1178 : : /* Uses in PHI's are considered to be live at exit of the SRC block
1179 : : as this is where a copy would be inserted. Check to see if it is
1180 : : defined in that block, or whether its live on entry. */
1181 : 5980663 : int index = PHI_ARG_INDEX_FROM_USE (use);
1182 : 5980663 : edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index);
1183 : 5980663 : if (e->src != def_bb && region_contains_p (live->map, e->src))
1184 : 1971040 : add_block = e->src;
1185 : : }
1186 : 18227780 : else if (is_gimple_debug (use_stmt))
1187 : 4711408 : continue;
1188 : : else
1189 : : {
1190 : : /* If its not defined in this block, its live on entry. */
1191 : 13516372 : basic_block use_bb = gimple_bb (use_stmt);
1192 : 13516372 : if (use_bb != def_bb && region_contains_p (live->map, use_bb))
1193 : : add_block = use_bb;
1194 : : }
1195 : :
1196 : : /* If there was a live on entry use, set the bit. */
1197 : 10740413 : if (add_block)
1198 : 10740413 : bitmap_set_bit (&live->livein[add_block->index], p);
1199 : : }
1200 : : }
1201 : :
1202 : :
1203 : : /* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
1204 : :
1205 : : static void
1206 : 1273037 : calculate_live_on_exit (tree_live_info_p liveinfo)
1207 : : {
1208 : 1273037 : basic_block bb;
1209 : 1273037 : edge e;
1210 : 1273037 : edge_iterator ei;
1211 : :
1212 : : /* live on entry calculations used liveout vectors for defs, clear them. */
1213 : 12978129 : for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
1214 : 11705092 : bitmap_clear (&liveinfo->liveout[bb->index]);
1215 : :
1216 : : /* Set all the live-on-exit bits for uses in PHIs. */
1217 : 12978129 : FOR_EACH_BB_FN (bb, cfun)
1218 : : {
1219 : 11705092 : gphi_iterator gsi;
1220 : 11705092 : size_t i;
1221 : :
1222 : : /* Mark the PHI arguments which are live on exit to the pred block. */
1223 : 14678097 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1224 : : {
1225 : 2973005 : gphi *phi = gsi.phi ();
1226 : 5946010 : if (virtual_operand_p (gimple_phi_result (phi)))
1227 : 5656 : continue;
1228 : 10373593 : for (i = 0; i < gimple_phi_num_args (phi); i++)
1229 : : {
1230 : 7406244 : tree t = PHI_ARG_DEF (phi, i);
1231 : 7406244 : int p;
1232 : :
1233 : 7406244 : if (TREE_CODE (t) != SSA_NAME)
1234 : 1396462 : continue;
1235 : :
1236 : 6009782 : p = var_to_partition (liveinfo->map, t);
1237 : 6009782 : if (p == NO_PARTITION)
1238 : 1387 : continue;
1239 : 6008395 : e = gimple_phi_arg_edge (phi, i);
1240 : 6008395 : if (region_contains_p (liveinfo->map, e->src))
1241 : 6008161 : bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
1242 : : }
1243 : : }
1244 : :
1245 : 11705092 : if (!region_contains_p (liveinfo->map, bb))
1246 : 0 : continue;
1247 : :
1248 : : /* Add each successors live on entry to this bock live on exit. */
1249 : 28740526 : FOR_EACH_EDGE (e, ei, bb->succs)
1250 : 17035434 : if (region_contains_p (liveinfo->map, e->dest))
1251 : 15785303 : bitmap_ior_into (&liveinfo->liveout[bb->index],
1252 : 15785303 : live_on_entry (liveinfo, e->dest));
1253 : : }
1254 : 1273037 : }
1255 : :
1256 : :
1257 : : /* Given partition map MAP, calculate all the live on entry bitmaps for
1258 : : each partition. Return a new live info object. */
1259 : :
1260 : : tree_live_info_p
1261 : 1273037 : calculate_live_ranges (var_map map, bool want_livein)
1262 : : {
1263 : 1273037 : tree var;
1264 : 1273037 : unsigned i;
1265 : 1273037 : tree_live_info_p live;
1266 : :
1267 : 1273037 : live = new_tree_live_info (map);
1268 : 13758005 : for (i = 0; i < num_var_partitions (map); i++)
1269 : : {
1270 : 11211931 : var = partition_to_var (map, i);
1271 : 11211931 : if (var != NULL_TREE)
1272 : 11211931 : set_var_live_on_entry (var, live);
1273 : : }
1274 : :
1275 : 1273037 : live_worklist (live);
1276 : :
1277 : 1273037 : if (flag_checking)
1278 : 1273020 : verify_live_on_entry (live);
1279 : :
1280 : 1273037 : calculate_live_on_exit (live);
1281 : :
1282 : 1273037 : if (!want_livein)
1283 : : {
1284 : 1273037 : bitmap_obstack_release (&live->livein_obstack);
1285 : 1273037 : free (live->livein);
1286 : 1273037 : live->livein = NULL;
1287 : : }
1288 : :
1289 : 1273037 : return live;
1290 : : }
1291 : :
1292 : : /* Data structure for compute_live_vars* functions. */
1293 : :
1294 : : struct compute_live_vars_data {
1295 : : /* Vector of bitmaps for live vars indices at the end of basic blocks,
1296 : : indexed by bb->index. ACTIVE[ENTRY_BLOCK] must be empty bitmap,
1297 : : ACTIVE[EXIT_BLOCK] is used for STOP_AFTER. */
1298 : : vec<bitmap_head> active;
1299 : : /* Work bitmap of currently live variables. */
1300 : : bitmap work;
1301 : : /* Set of interesting variables. Variables with uids not in this
1302 : : hash_map are not tracked. */
1303 : : live_vars_map *vars;
1304 : : };
1305 : :
1306 : : /* Callback for walk_stmt_load_store_addr_ops. If OP is a VAR_DECL with
1307 : : uid set in DATA->vars, enter its corresponding index into bitmap
1308 : : DATA->work. */
1309 : :
1310 : : static bool
1311 : 28077411 : compute_live_vars_visit (gimple *, tree op, tree, void *pdata)
1312 : : {
1313 : 28077411 : compute_live_vars_data *data = (compute_live_vars_data *) pdata;
1314 : 28077411 : op = get_base_address (op);
1315 : 28077411 : if (op && VAR_P (op))
1316 : 18665822 : if (unsigned int *v = data->vars->get (DECL_UID (op)))
1317 : 14515858 : bitmap_set_bit (data->work, *v);
1318 : 28077411 : return false;
1319 : : }
1320 : :
1321 : : /* Helper routine for compute_live_vars, calculating the sets of live
1322 : : variables at the end of BB, leaving the result in DATA->work.
1323 : : If STOP_AFTER is non-NULL, stop processing after that stmt. */
1324 : :
1325 : : static void
1326 : 13857587 : compute_live_vars_1 (basic_block bb, compute_live_vars_data *data,
1327 : : gimple *stop_after)
1328 : : {
1329 : 13857587 : edge e;
1330 : 13857587 : edge_iterator ei;
1331 : 13857587 : gimple_stmt_iterator gsi;
1332 : 13857587 : walk_stmt_load_store_addr_fn visit = compute_live_vars_visit;
1333 : :
1334 : 13857587 : bitmap_clear (data->work);
1335 : 33380592 : FOR_EACH_EDGE (e, ei, bb->preds)
1336 : 19523005 : bitmap_ior_into (data->work, &data->active[e->src->index]);
1337 : :
1338 : 19769848 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1339 : 5912261 : walk_stmt_load_store_addr_ops (gsi_stmt (gsi), data, NULL, NULL, visit);
1340 : 171751812 : for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1341 : : {
1342 : 158145466 : gimple *stmt = gsi_stmt (gsi);
1343 : :
1344 : 158145466 : if (gimple_clobber_p (stmt))
1345 : : {
1346 : 5067895 : tree lhs = gimple_assign_lhs (stmt);
1347 : 5067895 : if (VAR_P (lhs))
1348 : 3670087 : if (unsigned int *v = data->vars->get (DECL_UID (lhs)))
1349 : 3038273 : bitmap_clear_bit (data->work, *v);
1350 : : }
1351 : 153077571 : else if (!is_gimple_debug (stmt))
1352 : 42261838 : walk_stmt_load_store_addr_ops (stmt, data, visit, visit, visit);
1353 : 158145466 : if (stmt == stop_after)
1354 : : break;
1355 : : }
1356 : 13857587 : }
1357 : :
1358 : : /* For function FN and live_vars_map (hash map from DECL_UIDs to a dense set of
1359 : : indexes of automatic variables VARS, compute which of those variables are
1360 : : (might be) live at the end of each basic block. */
1361 : :
1362 : : vec<bitmap_head>
1363 : 337595 : compute_live_vars (struct function *fn, live_vars_map *vars)
1364 : : {
1365 : 337595 : vec<bitmap_head> active;
1366 : :
1367 : : /* We approximate the live range of a stack variable by taking the first
1368 : : mention of its name as starting point(s), and by the end-of-scope
1369 : : death clobber added by gimplify as ending point(s) of the range.
1370 : : This overapproximates in the case we for instance moved an address-taken
1371 : : operation upward, without also moving a dereference to it upwards.
1372 : : But it's conservatively correct as a variable never can hold values
1373 : : before its name is mentioned at least once.
1374 : :
1375 : : We then do a mostly classical bitmap liveness algorithm. */
1376 : :
1377 : 337595 : active.create (last_basic_block_for_fn (fn));
1378 : 337595 : active.quick_grow_cleared (last_basic_block_for_fn (fn));
1379 : 7736070 : for (int i = 0; i < last_basic_block_for_fn (fn); i++)
1380 : 7398475 : bitmap_initialize (&active[i], &bitmap_default_obstack);
1381 : :
1382 : 337595 : bitmap work = BITMAP_ALLOC (NULL);
1383 : :
1384 : 337595 : int *rpo = XNEWVEC (int, last_basic_block_for_fn (fn));
1385 : 337595 : int n_bbs = pre_and_rev_post_order_compute_fn (fn, NULL, rpo, false);
1386 : :
1387 : 337595 : bool changed = true;
1388 : 337595 : compute_live_vars_data data = { active, work, vars };
1389 : 943398 : while (changed)
1390 : : {
1391 : : int i;
1392 : : changed = false;
1393 : 14212149 : for (i = 0; i < n_bbs; i++)
1394 : : {
1395 : 13606346 : basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
1396 : 13606346 : compute_live_vars_1 (bb, &data, NULL);
1397 : 13606346 : if (bitmap_ior_into (&active[bb->index], work))
1398 : 5132913 : changed = true;
1399 : : }
1400 : : }
1401 : :
1402 : 337595 : free (rpo);
1403 : 337595 : BITMAP_FREE (work);
1404 : :
1405 : 337595 : return active;
1406 : : }
1407 : :
1408 : : /* For ACTIVE computed by compute_live_vars, compute a bitmap of variables
1409 : : live after the STOP_AFTER statement and return that bitmap. */
1410 : :
1411 : : bitmap
1412 : 251241 : live_vars_at_stmt (vec<bitmap_head> &active, live_vars_map *vars,
1413 : : gimple *stop_after)
1414 : : {
1415 : 251241 : bitmap work = BITMAP_ALLOC (NULL);
1416 : 251241 : compute_live_vars_data data = { active, work, vars };
1417 : 251241 : basic_block bb = gimple_bb (stop_after);
1418 : 251241 : compute_live_vars_1 (bb, &data, stop_after);
1419 : 251241 : return work;
1420 : : }
1421 : :
1422 : : /* Destroy what compute_live_vars has returned when it is no longer needed. */
1423 : :
1424 : : void
1425 : 337595 : destroy_live_vars (vec<bitmap_head> &active)
1426 : : {
1427 : 337595 : unsigned len = active.length ();
1428 : 7736070 : for (unsigned i = 0; i < len; i++)
1429 : 7398475 : bitmap_clear (&active[i]);
1430 : :
1431 : 337595 : active.release ();
1432 : 337595 : }
1433 : :
1434 : : /* Output partition map MAP to file F. */
1435 : :
1436 : : void
1437 : 350 : dump_var_map (FILE *f, var_map map)
1438 : : {
1439 : 350 : int t;
1440 : 350 : unsigned x, y;
1441 : 350 : int p;
1442 : :
1443 : 350 : fprintf (f, "\nPartition map \n\n");
1444 : :
1445 : 1789 : for (x = 0; x < map->num_partitions; x++)
1446 : : {
1447 : 1089 : if (map->view_to_partition != NULL)
1448 : 465 : p = map->view_to_partition[x];
1449 : : else
1450 : 624 : p = x;
1451 : :
1452 : 1089 : if (ssa_name (p) == NULL_TREE
1453 : 2016 : || virtual_operand_p (ssa_name (p)))
1454 : 367 : continue;
1455 : :
1456 : : t = 0;
1457 : 9754 : for (y = 1; y < num_ssa_names; y++)
1458 : : {
1459 : 9032 : p = partition_find (map->var_partition, y);
1460 : 9032 : if (map->partition_to_view)
1461 : 5711 : p = map->partition_to_view[p];
1462 : 9032 : if (p == (int)x)
1463 : : {
1464 : 754 : if (t++ == 0)
1465 : : {
1466 : 722 : fprintf (f, "Partition %d (", x);
1467 : 722 : print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1468 : 722 : fprintf (f, " - ");
1469 : : }
1470 : 754 : fprintf (f, "%d ", y);
1471 : : }
1472 : : }
1473 : 722 : if (t != 0)
1474 : 722 : fprintf (f, ")\n");
1475 : : }
1476 : 350 : fprintf (f, "\n");
1477 : 350 : }
1478 : :
1479 : :
1480 : : /* Generic dump for the above. */
1481 : :
1482 : : DEBUG_FUNCTION void
1483 : 0 : debug (_var_map &ref)
1484 : : {
1485 : 0 : dump_var_map (stderr, &ref);
1486 : 0 : }
1487 : :
1488 : : DEBUG_FUNCTION void
1489 : 0 : debug (_var_map *ptr)
1490 : : {
1491 : 0 : if (ptr)
1492 : 0 : debug (*ptr);
1493 : : else
1494 : 0 : fprintf (stderr, "<nil>\n");
1495 : 0 : }
1496 : :
1497 : :
1498 : : /* Output live range info LIVE to file F, controlled by FLAG. */
1499 : :
1500 : : void
1501 : 64 : dump_live_info (FILE *f, tree_live_info_p live, int flag)
1502 : : {
1503 : 64 : basic_block bb;
1504 : 64 : unsigned i;
1505 : 64 : var_map map = live->map;
1506 : 64 : bitmap_iterator bi;
1507 : :
1508 : 64 : if ((flag & LIVEDUMP_ENTRY) && live->livein)
1509 : : {
1510 : 0 : FOR_EACH_BB_FN (bb, cfun)
1511 : : {
1512 : 0 : fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1513 : 0 : EXECUTE_IF_SET_IN_BITMAP (&live->livein[bb->index], 0, i, bi)
1514 : : {
1515 : 0 : print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1516 : 0 : fprintf (f, " ");
1517 : : }
1518 : 0 : fprintf (f, "\n");
1519 : : }
1520 : : }
1521 : :
1522 : 64 : if ((flag & LIVEDUMP_EXIT) && live->liveout)
1523 : : {
1524 : 0 : FOR_EACH_BB_FN (bb, cfun)
1525 : : {
1526 : 0 : fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1527 : 0 : EXECUTE_IF_SET_IN_BITMAP (&live->liveout[bb->index], 0, i, bi)
1528 : : {
1529 : 0 : print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1530 : 0 : fprintf (f, " ");
1531 : : }
1532 : 0 : fprintf (f, "\n");
1533 : : }
1534 : : }
1535 : 64 : }
1536 : :
1537 : :
1538 : : /* Generic dump for the above. */
1539 : :
1540 : : DEBUG_FUNCTION void
1541 : 0 : debug (tree_live_info_d &ref)
1542 : : {
1543 : 0 : dump_live_info (stderr, &ref, 0);
1544 : 0 : }
1545 : :
1546 : : DEBUG_FUNCTION void
1547 : 0 : debug (tree_live_info_d *ptr)
1548 : : {
1549 : 0 : if (ptr)
1550 : 0 : debug (*ptr);
1551 : : else
1552 : 0 : fprintf (stderr, "<nil>\n");
1553 : 0 : }
1554 : :
1555 : :
1556 : : /* Verify that the info in LIVE matches the current cfg. */
1557 : :
1558 : : static void
1559 : 1273020 : verify_live_on_entry (tree_live_info_p live)
1560 : : {
1561 : 1273020 : unsigned i;
1562 : 1273020 : tree var;
1563 : 1273020 : gimple *stmt;
1564 : 1273020 : basic_block bb;
1565 : 1273020 : edge e;
1566 : 1273020 : int num;
1567 : 1273020 : edge_iterator ei;
1568 : 1273020 : var_map map = live->map;
1569 : :
1570 : : /* Check for live on entry partitions and report those with a DEF in
1571 : : the program. This will typically mean an optimization has done
1572 : : something wrong. */
1573 : 1273020 : bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1574 : 1273020 : num = 0;
1575 : 2546040 : FOR_EACH_EDGE (e, ei, bb->succs)
1576 : : {
1577 : 1273020 : int entry_block = e->dest->index;
1578 : 1273020 : if (!region_contains_p (live->map, e->dest))
1579 : 0 : continue;
1580 : 12484895 : for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1581 : : {
1582 : 11211875 : basic_block tmp;
1583 : 11211875 : tree d = NULL_TREE;
1584 : 11211875 : bitmap loe;
1585 : 11211875 : var = partition_to_var (map, i);
1586 : 11211875 : stmt = SSA_NAME_DEF_STMT (var);
1587 : 11211875 : tmp = gimple_bb (stmt);
1588 : 11211875 : if (SSA_NAME_VAR (var))
1589 : 7930226 : d = ssa_default_def (cfun, SSA_NAME_VAR (var));
1590 : :
1591 : 11211875 : loe = live_on_entry (live, e->dest);
1592 : 11211875 : if (loe && bitmap_bit_p (loe, i))
1593 : : {
1594 : 1951420 : if (!gimple_nop_p (stmt))
1595 : : {
1596 : 0 : num++;
1597 : 0 : print_generic_expr (stderr, var, TDF_SLIM);
1598 : 0 : fprintf (stderr, " is defined ");
1599 : 0 : if (tmp)
1600 : 0 : fprintf (stderr, " in BB%d, ", tmp->index);
1601 : 0 : fprintf (stderr, "by:\n");
1602 : 0 : print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1603 : 0 : fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1604 : : entry_block);
1605 : 0 : fprintf (stderr, " So it appears to have multiple defs.\n");
1606 : : }
1607 : : else
1608 : : {
1609 : 1951420 : if (d != var)
1610 : : {
1611 : 0 : num++;
1612 : 0 : print_generic_expr (stderr, var, TDF_SLIM);
1613 : 0 : fprintf (stderr, " is live-on-entry to BB%d ",
1614 : : entry_block);
1615 : 0 : if (d)
1616 : : {
1617 : 0 : fprintf (stderr, " but is not the default def of ");
1618 : 0 : print_generic_expr (stderr, d, TDF_SLIM);
1619 : 0 : fprintf (stderr, "\n");
1620 : : }
1621 : : else
1622 : 0 : fprintf (stderr, " and there is no default def.\n");
1623 : : }
1624 : : }
1625 : : }
1626 : : else
1627 : 9260455 : if (d == var)
1628 : : {
1629 : : /* An undefined local variable does not need to be very
1630 : : alive. */
1631 : 1676393 : if (ssa_undefined_value_p (var, false))
1632 : 1676393 : continue;
1633 : :
1634 : : /* The only way this var shouldn't be marked live on entry is
1635 : : if it occurs in a PHI argument of the block. */
1636 : 965068 : size_t z;
1637 : 965068 : bool ok = false;
1638 : 965068 : gphi_iterator gsi;
1639 : 965068 : for (gsi = gsi_start_phis (e->dest);
1640 : 965283 : !gsi_end_p (gsi) && !ok;
1641 : 215 : gsi_next (&gsi))
1642 : : {
1643 : 215 : gphi *phi = gsi.phi ();
1644 : 430 : if (virtual_operand_p (gimple_phi_result (phi)))
1645 : 0 : continue;
1646 : 348 : for (z = 0; z < gimple_phi_num_args (phi); z++)
1647 : 283 : if (var == gimple_phi_arg_def (phi, z))
1648 : : {
1649 : : ok = true;
1650 : : break;
1651 : : }
1652 : : }
1653 : 965068 : if (ok)
1654 : 150 : continue;
1655 : : /* Expand adds unused default defs for PARM_DECLs and
1656 : : RESULT_DECLs. They're ok. */
1657 : 964918 : if (has_zero_uses (var)
1658 : 964918 : && SSA_NAME_VAR (var)
1659 : 1929836 : && !VAR_P (SSA_NAME_VAR (var)))
1660 : 964918 : continue;
1661 : 0 : num++;
1662 : 0 : print_generic_expr (stderr, var, TDF_SLIM);
1663 : 0 : fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1664 : : entry_block);
1665 : 0 : fprintf (stderr, "but it is a default def so it should be.\n");
1666 : : }
1667 : : }
1668 : : }
1669 : 1273020 : gcc_assert (num <= 0);
1670 : 1273020 : }
1671 : :
1672 : :
1673 : : /* Virtual operand liveness analysis data init. */
1674 : :
1675 : : void
1676 : 203754 : virtual_operand_live::init ()
1677 : : {
1678 : 203754 : liveout = XCNEWVEC (tree, last_basic_block_for_fn (cfun) + 1);
1679 : 203754 : liveout[ENTRY_BLOCK] = ssa_default_def (cfun, gimple_vop (cfun));
1680 : 203754 : }
1681 : :
1682 : : /* Compute live-in of BB from cached live-out. */
1683 : :
1684 : : tree
1685 : 1870459 : virtual_operand_live::get_live_in (basic_block bb)
1686 : : {
1687 : : /* A virtual PHI is a convenient cache for live-in. */
1688 : 1870459 : gphi *phi = get_virtual_phi (bb);
1689 : 1870459 : if (phi)
1690 : 577385 : return gimple_phi_result (phi);
1691 : :
1692 : 1293074 : if (!liveout)
1693 : 203754 : init ();
1694 : :
1695 : : /* Since we don't have a virtual PHI and we don't know whether there's
1696 : : a downstream virtual use (and thus PHIs are inserted where necessary)
1697 : : we now have to check each incoming edge live-out. */
1698 : 1293074 : edge_iterator ei;
1699 : 1293074 : edge e;
1700 : 1293074 : tree livein = NULL_TREE;
1701 : 1293074 : bool first = true;
1702 : 2805109 : FOR_EACH_EDGE (e, ei, bb->preds)
1703 : 1512039 : if (e->flags & EDGE_DFS_BACK)
1704 : : /* We can ignore backedges since if there's a def there it would
1705 : : have forced a PHI in the source because it also acts as use
1706 : : downstream. */
1707 : 68920 : continue;
1708 : 1443119 : else if (first)
1709 : : {
1710 : 1293074 : livein = get_live_out (e->src);
1711 : 1293074 : first = false;
1712 : : }
1713 : 150045 : else if (get_live_out (e->src) != livein)
1714 : : /* When there's no virtual use downstream this indicates a point
1715 : : where we'd insert a PHI merging the different live virtual
1716 : : operands. */
1717 : : return NULL_TREE;
1718 : :
1719 : : return livein;
1720 : : }
1721 : :
1722 : : /* Compute live-out of BB. */
1723 : :
1724 : : tree
1725 : 1443119 : virtual_operand_live::get_live_out (basic_block bb)
1726 : : {
1727 : 1443119 : if (!liveout)
1728 : 0 : init ();
1729 : :
1730 : 1443119 : if (liveout[bb->index])
1731 : : return liveout[bb->index];
1732 : :
1733 : 830866 : tree lo = NULL_TREE;
1734 : 4084097 : for (auto gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1735 : : {
1736 : 2992476 : gimple *stmt = gsi_stmt (gsi);
1737 : 3938741 : if (gimple_vdef (stmt))
1738 : : {
1739 : : lo = gimple_vdef (stmt);
1740 : : break;
1741 : : }
1742 : 3603408 : if (gimple_vuse (stmt))
1743 : : {
1744 : : lo = gimple_vuse (stmt);
1745 : : break;
1746 : : }
1747 : : }
1748 : 830866 : if (!lo)
1749 : 260755 : lo = get_live_in (bb);
1750 : 830866 : liveout[bb->index] = lo;
1751 : 830866 : return lo;
1752 : : }
|
