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