Line data Source code
1 : /* Control flow graph manipulation code for GNU compiler.
2 : Copyright (C) 1987-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : /* This file contains low level functions to manipulate the CFG and
21 : analyze it. All other modules should not transform the data structure
22 : directly and use abstraction instead. The file is supposed to be
23 : ordered bottom-up and should not contain any code dependent on a
24 : particular intermediate language (RTL or trees).
25 :
26 : Available functionality:
27 : - Initialization/deallocation
28 : init_flow, free_cfg
29 : - Low level basic block manipulation
30 : alloc_block, expunge_block
31 : - Edge manipulation
32 : make_edge, make_single_succ_edge, cached_make_edge, remove_edge
33 : - Low level edge redirection (without updating instruction chain)
34 : redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
35 : - Dumping and debugging
36 : dump_flow_info, debug_flow_info, dump_edge_info
37 : - Allocation of AUX fields for basic blocks
38 : alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
39 : - clear_bb_flags
40 : - Consistency checking
41 : verify_flow_info
42 : - Dumping and debugging
43 : print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
44 :
45 : TODO: Document these "Available functionality" functions in the files
46 : that implement them.
47 : */
48 :
49 : #include "config.h"
50 : #include "system.h"
51 : #include "coretypes.h"
52 : #include "backend.h"
53 : #include "hard-reg-set.h"
54 : #include "tree.h"
55 : #include "cfghooks.h"
56 : #include "df.h"
57 : #include "cfganal.h"
58 : #include "cfgloop.h" /* FIXME: For struct loop. */
59 : #include "dumpfile.h"
60 :
61 :
62 :
63 : /* Called once at initialization time. */
64 :
65 : void
66 3248405 : init_flow (struct function *the_fun)
67 : {
68 3248405 : if (!the_fun->cfg)
69 3248405 : the_fun->cfg = ggc_cleared_alloc<control_flow_graph> ();
70 3248405 : n_edges_for_fn (the_fun) = 0;
71 3248405 : the_fun->cfg->count_max = profile_count::uninitialized ();
72 3248405 : ENTRY_BLOCK_PTR_FOR_FN (the_fun)
73 3248405 : = alloc_block ();
74 3248405 : ENTRY_BLOCK_PTR_FOR_FN (the_fun)->index = ENTRY_BLOCK;
75 3248405 : EXIT_BLOCK_PTR_FOR_FN (the_fun)
76 3248405 : = alloc_block ();
77 3248405 : EXIT_BLOCK_PTR_FOR_FN (the_fun)->index = EXIT_BLOCK;
78 3248405 : ENTRY_BLOCK_PTR_FOR_FN (the_fun)->next_bb
79 3248405 : = EXIT_BLOCK_PTR_FOR_FN (the_fun);
80 3248405 : EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
81 3248405 : = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
82 3248405 : the_fun->cfg->edge_flags_allocated = EDGE_ALL_FLAGS;
83 3248405 : the_fun->cfg->bb_flags_allocated = BB_ALL_FLAGS;
84 3248405 : the_fun->cfg->full_profile = false;
85 3248405 : }
86 :
87 : /* Helper function for remove_edge and free_cffg. Frees edge structure
88 : without actually removing it from the pred/succ arrays. */
89 :
90 : static void
91 92541090 : free_edge (function *fn, edge e)
92 : {
93 92541090 : n_edges_for_fn (fn)--;
94 0 : ggc_free (e);
95 0 : }
96 :
97 : /* Free basic block BB. */
98 :
99 : static void
100 8768214 : free_block (basic_block bb)
101 : {
102 8768214 : vec_free (bb->succs);
103 8768214 : bb->succs = NULL;
104 8768214 : vec_free (bb->preds);
105 8768214 : bb->preds = NULL;
106 8768214 : ggc_free (bb);
107 8768214 : }
108 :
109 : /* Free the memory associated with the CFG in FN. */
110 :
111 : void
112 1671245 : free_cfg (struct function *fn)
113 : {
114 1671245 : edge e;
115 1671245 : edge_iterator ei;
116 1671245 : basic_block next;
117 :
118 10439459 : for (basic_block bb = ENTRY_BLOCK_PTR_FOR_FN (fn); bb; bb = next)
119 : {
120 8768214 : next = bb->next_bb;
121 17192472 : FOR_EACH_EDGE (e, ei, bb->succs)
122 8424258 : free_edge (fn, e);
123 8768214 : free_block (bb);
124 : }
125 :
126 1671245 : gcc_assert (!n_edges_for_fn (fn));
127 : /* Sanity check that dominance tree is freed. */
128 1671245 : gcc_assert (!fn->cfg->x_dom_computed[0] && !fn->cfg->x_dom_computed[1]);
129 :
130 1671245 : vec_free (fn->cfg->x_label_to_block_map);
131 1671245 : vec_free (basic_block_info_for_fn (fn));
132 1671245 : ggc_free (fn->cfg);
133 1671245 : fn->cfg = NULL;
134 1671245 : }
135 :
136 : /* Allocate memory for basic_block. */
137 :
138 : basic_block
139 90800682 : alloc_block (void)
140 : {
141 90800682 : basic_block bb;
142 90800682 : bb = ggc_cleared_alloc<basic_block_def> ();
143 90800682 : bb->count = profile_count::uninitialized ();
144 90800682 : return bb;
145 : }
146 :
147 : /* Link block B to chain after AFTER. */
148 : void
149 89295039 : link_block (basic_block b, basic_block after)
150 : {
151 89295039 : b->next_bb = after->next_bb;
152 89295039 : b->prev_bb = after;
153 89295039 : after->next_bb = b;
154 89295039 : b->next_bb->prev_bb = b;
155 89295039 : }
156 :
157 : /* Unlink block B from chain. */
158 : void
159 69848866 : unlink_block (basic_block b)
160 : {
161 69848866 : b->next_bb->prev_bb = b->prev_bb;
162 69848866 : b->prev_bb->next_bb = b->next_bb;
163 69848866 : b->prev_bb = NULL;
164 69848866 : b->next_bb = NULL;
165 69848866 : }
166 :
167 : /* Sequentially order blocks and compact the arrays. */
168 : void
169 50456012 : compact_blocks (void)
170 : {
171 50456012 : int i;
172 :
173 50456012 : SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
174 50456012 : SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
175 :
176 50456012 : if (df)
177 17912457 : df_compact_blocks ();
178 : else
179 : {
180 32543555 : basic_block bb;
181 :
182 32543555 : i = NUM_FIXED_BLOCKS;
183 392583790 : FOR_EACH_BB_FN (bb, cfun)
184 : {
185 360040235 : SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
186 360040235 : bb->index = i;
187 360040235 : i++;
188 : }
189 32543555 : gcc_assert (i == n_basic_blocks_for_fn (cfun));
190 :
191 98483740 : for (; i < last_basic_block_for_fn (cfun); i++)
192 65940185 : SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
193 : }
194 50456012 : last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
195 50456012 : }
196 :
197 : /* Remove block B from the basic block array. */
198 :
199 : void
200 64276930 : expunge_block (basic_block b)
201 : {
202 64276930 : unlink_block (b);
203 64276930 : SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
204 64276930 : n_basic_blocks_for_fn (cfun)--;
205 : /* We should be able to ggc_free here, but we are not.
206 : The dead SSA_NAMES are left pointing to dead statements that are pointing
207 : to dead basic blocks making garbage collector to die.
208 : We should be able to release all dead SSA_NAMES and at the same time we
209 : should clear out BB pointer of dead statements consistently. */
210 64276930 : }
211 :
212 : /* Connect E to E->src. */
213 :
214 : static inline void
215 117232445 : connect_src (edge e)
216 : {
217 117232445 : vec_safe_push (e->src->succs, e);
218 117232445 : df_mark_solutions_dirty ();
219 117232445 : }
220 :
221 : /* Connect E to E->dest. */
222 :
223 : static inline void
224 202150859 : connect_dest (edge e)
225 : {
226 202150859 : basic_block dest = e->dest;
227 202150859 : vec_safe_push (dest->preds, e);
228 202150859 : e->dest_idx = EDGE_COUNT (dest->preds) - 1;
229 202150859 : df_mark_solutions_dirty ();
230 202150859 : }
231 :
232 : /* Disconnect edge E from E->src. */
233 :
234 : static inline void
235 86034835 : disconnect_src (edge e)
236 : {
237 86034835 : basic_block src = e->src;
238 86034835 : edge_iterator ei;
239 86034835 : edge tmp;
240 :
241 90575882 : for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
242 : {
243 90575882 : if (tmp == e)
244 : {
245 86034835 : src->succs->unordered_remove (ei.index);
246 86034835 : df_mark_solutions_dirty ();
247 86034835 : return;
248 : }
249 : else
250 4541047 : ei_next (&ei);
251 : }
252 :
253 0 : gcc_unreachable ();
254 : }
255 :
256 : /* Disconnect edge E from E->dest. */
257 :
258 : static inline void
259 170953249 : disconnect_dest (edge e)
260 : {
261 170953249 : basic_block dest = e->dest;
262 170953249 : unsigned int dest_idx = e->dest_idx;
263 :
264 170953249 : dest->preds->unordered_remove (dest_idx);
265 :
266 : /* If we removed an edge in the middle of the edge vector, we need
267 : to update dest_idx of the edge that moved into the "hole". */
268 170953249 : if (dest_idx < EDGE_COUNT (dest->preds))
269 84518767 : EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
270 170953249 : df_mark_solutions_dirty ();
271 170953249 : }
272 :
273 : /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
274 : created edge. Use this only if you are sure that this edge can't
275 : possibly already exist. */
276 :
277 : edge
278 115314442 : unchecked_make_edge (basic_block src, basic_block dst, int flags)
279 : {
280 115314442 : edge e;
281 115314442 : e = ggc_cleared_alloc<edge_def> ();
282 115314442 : n_edges_for_fn (cfun)++;
283 :
284 115314442 : e->probability = profile_probability::uninitialized ();
285 115314442 : e->src = src;
286 115314442 : e->dest = dst;
287 115314442 : e->flags = flags;
288 :
289 115314442 : connect_src (e);
290 115314442 : connect_dest (e);
291 :
292 115314442 : execute_on_growing_pred (e);
293 115314442 : return e;
294 : }
295 :
296 : /* Create an edge connecting SRC and DST with FLAGS optionally using
297 : edge cache CACHE. Return the new edge, NULL if already exist. */
298 :
299 : edge
300 36914791 : cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
301 : {
302 36914791 : if (edge_cache == NULL
303 348341 : || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
304 348341 : || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
305 36589438 : return make_edge (src, dst, flags);
306 :
307 : /* Does the requested edge already exist? */
308 325353 : if (! bitmap_bit_p (edge_cache, dst->index))
309 : {
310 : /* The edge does not exist. Create one and update the
311 : cache. */
312 41891 : bitmap_set_bit (edge_cache, dst->index);
313 41891 : return unchecked_make_edge (src, dst, flags);
314 : }
315 :
316 : /* At this point, we know that the requested edge exists. Adjust
317 : flags if necessary. */
318 283462 : if (flags)
319 : {
320 136424 : edge e = find_edge (src, dst);
321 136424 : e->flags |= flags;
322 : }
323 :
324 : return NULL;
325 : }
326 :
327 : /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
328 : created edge or NULL if already exist. */
329 :
330 : edge
331 144303380 : make_edge (basic_block src, basic_block dest, int flags)
332 : {
333 144303380 : edge e = find_edge (src, dest);
334 :
335 : /* Make sure we don't add duplicate edges. */
336 144303380 : if (e)
337 : {
338 37189246 : e->flags |= flags;
339 37189246 : return NULL;
340 : }
341 :
342 107114134 : return unchecked_make_edge (src, dest, flags);
343 : }
344 :
345 : /* Create an edge connecting SRC to DEST and set probability by knowing
346 : that it is the single edge leaving SRC. */
347 :
348 : edge
349 43438518 : make_single_succ_edge (basic_block src, basic_block dest, int flags)
350 : {
351 43438518 : edge e = make_edge (src, dest, flags);
352 :
353 43438518 : e->probability = profile_probability::always ();
354 43438518 : return e;
355 : }
356 :
357 : /* This function will remove an edge from the flow graph. */
358 :
359 : void
360 84116832 : remove_edge_raw (edge e)
361 : {
362 84116832 : remove_predictions_associated_with_edge (e);
363 84116832 : execute_on_shrinking_pred (e);
364 :
365 84116832 : disconnect_src (e);
366 84116832 : disconnect_dest (e);
367 :
368 84116832 : free_edge (cfun, e);
369 84116832 : }
370 :
371 : /* Redirect an edge's successor from one block to another. */
372 :
373 : void
374 86836417 : redirect_edge_succ (edge e, basic_block new_succ)
375 : {
376 86836417 : execute_on_shrinking_pred (e);
377 :
378 86836417 : disconnect_dest (e);
379 :
380 86836417 : e->dest = new_succ;
381 :
382 : /* Reconnect the edge to the new successor block. */
383 86836417 : connect_dest (e);
384 :
385 86836417 : execute_on_growing_pred (e);
386 86836417 : }
387 :
388 : /* Redirect an edge's predecessor from one block to another. */
389 :
390 : void
391 1918003 : redirect_edge_pred (edge e, basic_block new_pred)
392 : {
393 1918003 : disconnect_src (e);
394 :
395 1918003 : e->src = new_pred;
396 :
397 : /* Reconnect the edge to the new predecessor block. */
398 1918003 : connect_src (e);
399 1918003 : }
400 :
401 : /* Clear all basic block flags that do not have to be preserved. */
402 : void
403 5463779 : clear_bb_flags (void)
404 : {
405 5463779 : basic_block bb;
406 5463779 : int flags_to_preserve = BB_FLAGS_TO_PRESERVE;
407 5463779 : if (current_loops
408 5463779 : && loops_state_satisfies_p (cfun, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
409 : flags_to_preserve |= BB_IRREDUCIBLE_LOOP;
410 :
411 78689249 : FOR_ALL_BB_FN (bb, cfun)
412 73225470 : bb->flags &= flags_to_preserve;
413 5463779 : }
414 :
415 : /* Check the consistency of profile information. We can't do that
416 : in verify_flow_info, as the counts may get invalid for incompletely
417 : solved graphs, later eliminating of conditionals or roundoff errors.
418 : It is still practical to have them reported for debugging of simple
419 : testcases. */
420 : static void
421 14101 : check_bb_profile (basic_block bb, FILE * file, int indent)
422 : {
423 14101 : edge e;
424 14101 : edge_iterator ei;
425 14101 : struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
426 14101 : char *s_indent = (char *) alloca ((size_t) indent + 1);
427 14101 : memset ((void *) s_indent, ' ', (size_t) indent);
428 14101 : s_indent[indent] = '\0';
429 :
430 14101 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
431 2024 : return;
432 :
433 12077 : if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
434 : {
435 12077 : bool found = false;
436 12077 : profile_probability sum = profile_probability::never ();
437 12077 : int isum = 0;
438 :
439 27951 : FOR_EACH_EDGE (e, ei, bb->succs)
440 : {
441 15874 : if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
442 15870 : found = true;
443 15874 : sum += e->probability;
444 15874 : if (e->probability.initialized_p ())
445 15874 : isum += e->probability.to_reg_br_prob_base ();
446 : }
447 : /* Only report mismatches for non-EH control flow. If there are only EH
448 : edges it means that the BB ends by noreturn call. Here the control
449 : flow may just terminate. */
450 12077 : if (found)
451 : {
452 10825 : if (sum.differs_from_p (profile_probability::always ()))
453 : {
454 0 : fprintf (file,
455 : ";; %sInvalid sum of outgoing probabilities ",
456 : s_indent);
457 0 : sum.dump (file);
458 0 : fprintf (file, "\n");
459 : }
460 : /* Probabilities caps to 100% and thus the previous test will never
461 : fire if the sum of probabilities is too large. */
462 10825 : else if (isum > REG_BR_PROB_BASE + 100)
463 : {
464 170 : fprintf (file,
465 : ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
466 170 : s_indent, isum * 100.0 / REG_BR_PROB_BASE);
467 : }
468 : }
469 : }
470 12077 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
471 : {
472 12077 : profile_count sum = profile_count::zero ();
473 28328 : FOR_EACH_EDGE (e, ei, bb->preds)
474 16251 : sum += e->count ();
475 12077 : if (sum.differs_from_p (bb->count))
476 : {
477 362 : fprintf (file, ";; %sInvalid sum of incoming counts ",
478 : s_indent);
479 362 : sum.dump (file, fun);
480 362 : fprintf (file, ", should be ");
481 362 : bb->count.dump (file, fun);
482 362 : fprintf (file, "\n");
483 : }
484 : }
485 12077 : if (BB_PARTITION (bb) == BB_COLD_PARTITION)
486 : {
487 : /* Warn about inconsistencies in the partitioning that are
488 : currently caused by profile insanities created via optimization. */
489 1 : if (!probably_never_executed_bb_p (fun, bb))
490 0 : fprintf (file, ";; %sBlock in cold partition with hot count\n",
491 : s_indent);
492 2 : FOR_EACH_EDGE (e, ei, bb->preds)
493 : {
494 1 : if (!probably_never_executed_edge_p (fun, e))
495 0 : fprintf (file,
496 : ";; %sBlock in cold partition with incoming hot edge\n",
497 : s_indent);
498 : }
499 : }
500 : }
501 :
502 : void
503 79809 : dump_edge_info (FILE *file, edge e, dump_flags_t flags, int do_succ)
504 : {
505 79809 : basic_block side = (do_succ ? e->dest : e->src);
506 79809 : bool do_details = false;
507 :
508 79809 : if ((flags & TDF_DETAILS) != 0
509 79809 : && (flags & TDF_SLIM) == 0)
510 : do_details = true;
511 :
512 79809 : if (side->index == ENTRY_BLOCK)
513 4474 : fputs (" ENTRY", file);
514 75335 : else if (side->index == EXIT_BLOCK)
515 4100 : fputs (" EXIT", file);
516 : else
517 71235 : fprintf (file, " %d", side->index);
518 :
519 79809 : if (e->probability.initialized_p () && do_details)
520 : {
521 37778 : fprintf (file, " [");
522 37778 : e->probability.dump (file);
523 37778 : fprintf (file, "] ");
524 : }
525 :
526 79809 : if (e->count ().initialized_p () && do_details)
527 : {
528 35361 : fputs (" count:", file);
529 35361 : e->count ().dump (file, cfun);
530 : }
531 :
532 79809 : if (e->flags && do_details)
533 : {
534 38195 : static const char * const bitnames[] =
535 : {
536 : #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
537 : #include "cfg-flags.def"
538 : NULL
539 : #undef DEF_EDGE_FLAG
540 : };
541 38195 : bool comma = false;
542 38195 : int i, flags = e->flags;
543 :
544 38195 : gcc_assert (e->flags <= EDGE_ALL_FLAGS);
545 38195 : fputs (" (", file);
546 421047 : for (i = 0; flags; i++)
547 344657 : if (flags & (1 << i))
548 : {
549 66525 : flags &= ~(1 << i);
550 :
551 66525 : if (comma)
552 28330 : fputc (',', file);
553 66525 : fputs (bitnames[i], file);
554 66525 : comma = true;
555 : }
556 :
557 38195 : fputc (')', file);
558 : }
559 :
560 41879 : if (do_details && LOCATION_LOCUS (e->goto_locus) > BUILTINS_LOCATION)
561 3029 : fprintf (file, " %s:%d:%d", LOCATION_FILE (e->goto_locus),
562 6058 : LOCATION_LINE (e->goto_locus), LOCATION_COLUMN (e->goto_locus));
563 79809 : }
564 :
565 : DEBUG_FUNCTION void
566 0 : debug (edge_def &ref)
567 : {
568 0 : fprintf (stderr, "<edge (%d -> %d)>\n",
569 0 : ref.src->index, ref.dest->index);
570 0 : dump_edge_info (stderr, &ref, TDF_DETAILS, false);
571 0 : fprintf (stderr, "\n");
572 0 : }
573 :
574 : DEBUG_FUNCTION void
575 0 : debug (edge_def *ptr)
576 : {
577 0 : if (ptr)
578 0 : debug (*ptr);
579 : else
580 0 : fprintf (stderr, "<nil>\n");
581 0 : }
582 :
583 : static void
584 0 : debug_slim (edge e)
585 : {
586 0 : fprintf (stderr, "<edge 0x%p (%d -> %d)>", (void *) e,
587 0 : e->src->index, e->dest->index);
588 0 : }
589 :
590 0 : DEFINE_DEBUG_VEC (edge)
591 0 : DEFINE_DEBUG_HASH_SET (edge)
592 :
593 : /* Simple routines to easily allocate AUX fields of basic blocks. */
594 :
595 : static struct obstack block_aux_obstack;
596 : static void *first_block_aux_obj = 0;
597 : static struct obstack edge_aux_obstack;
598 : static void *first_edge_aux_obj = 0;
599 :
600 : /* Allocate a memory block of SIZE as BB->aux. The obstack must
601 : be first initialized by alloc_aux_for_blocks. */
602 :
603 : static void
604 59274370 : alloc_aux_for_block (basic_block bb, int size)
605 : {
606 : /* Verify that aux field is clear. */
607 59274370 : gcc_assert (!bb->aux && first_block_aux_obj);
608 59274370 : bb->aux = obstack_alloc (&block_aux_obstack, size);
609 59274370 : memset (bb->aux, 0, size);
610 59274370 : }
611 :
612 : /* Initialize the block_aux_obstack and if SIZE is nonzero, call
613 : alloc_aux_for_block for each basic block. */
614 :
615 : void
616 4973687 : alloc_aux_for_blocks (int size)
617 : {
618 4973687 : static int initialized;
619 :
620 4973687 : if (!initialized)
621 : {
622 153522 : gcc_obstack_init (&block_aux_obstack);
623 153522 : initialized = 1;
624 : }
625 : else
626 : /* Check whether AUX data are still allocated. */
627 4820165 : gcc_assert (!first_block_aux_obj);
628 :
629 4973687 : first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
630 4973687 : if (size)
631 : {
632 4973687 : basic_block bb;
633 :
634 64248057 : FOR_ALL_BB_FN (bb, cfun)
635 59274370 : alloc_aux_for_block (bb, size);
636 : }
637 4973687 : }
638 :
639 : /* Clear AUX pointers of all blocks. */
640 :
641 : void
642 12688783 : clear_aux_for_blocks (void)
643 : {
644 12688783 : basic_block bb;
645 :
646 194469386 : FOR_ALL_BB_FN (bb, cfun)
647 181780603 : bb->aux = NULL;
648 12688783 : }
649 :
650 : /* Free data allocated in block_aux_obstack and clear AUX pointers
651 : of all blocks. */
652 :
653 : void
654 4973687 : free_aux_for_blocks (void)
655 : {
656 4973687 : gcc_assert (first_block_aux_obj);
657 4973687 : obstack_free (&block_aux_obstack, first_block_aux_obj);
658 4973687 : first_block_aux_obj = NULL;
659 :
660 4973687 : clear_aux_for_blocks ();
661 4973687 : }
662 :
663 : /* Allocate a memory edge of SIZE as E->aux. The obstack must
664 : be first initialized by alloc_aux_for_edges. */
665 :
666 : void
667 22660420 : alloc_aux_for_edge (edge e, int size)
668 : {
669 : /* Verify that aux field is clear. */
670 22660420 : gcc_assert (!e->aux && first_edge_aux_obj);
671 22660420 : e->aux = obstack_alloc (&edge_aux_obstack, size);
672 22660420 : memset (e->aux, 0, size);
673 22660420 : }
674 :
675 : /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
676 : alloc_aux_for_edge for each basic edge. */
677 :
678 : void
679 2475564 : alloc_aux_for_edges (int size)
680 : {
681 2475564 : static int initialized;
682 :
683 2475564 : if (!initialized)
684 : {
685 143085 : gcc_obstack_init (&edge_aux_obstack);
686 143085 : initialized = 1;
687 : }
688 : else
689 : /* Check whether AUX data are still allocated. */
690 2332479 : gcc_assert (!first_edge_aux_obj);
691 :
692 2475564 : first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
693 2475564 : if (size)
694 : {
695 2475564 : basic_block bb;
696 :
697 19105200 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
698 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
699 : {
700 16629636 : edge e;
701 16629636 : edge_iterator ei;
702 :
703 39290056 : FOR_EACH_EDGE (e, ei, bb->succs)
704 22660420 : alloc_aux_for_edge (e, size);
705 : }
706 : }
707 2475564 : }
708 :
709 : /* Clear AUX pointers of all edges. */
710 :
711 : void
712 5393080 : clear_aux_for_edges (void)
713 : {
714 5393080 : basic_block bb;
715 5393080 : edge e;
716 :
717 85317104 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
718 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
719 : {
720 79924024 : edge_iterator ei;
721 195513130 : FOR_EACH_EDGE (e, ei, bb->succs)
722 115589106 : e->aux = NULL;
723 : }
724 5393080 : }
725 :
726 : /* Free data allocated in edge_aux_obstack and clear AUX pointers
727 : of all edges. */
728 :
729 : void
730 2475564 : free_aux_for_edges (void)
731 : {
732 2475564 : gcc_assert (first_edge_aux_obj);
733 2475564 : obstack_free (&edge_aux_obstack, first_edge_aux_obj);
734 2475564 : first_edge_aux_obj = NULL;
735 :
736 2475564 : clear_aux_for_edges ();
737 2475564 : }
738 :
739 : DEBUG_FUNCTION void
740 0 : debug_bb (basic_block bb)
741 : {
742 0 : debug_bb (bb, dump_flags);
743 0 : }
744 :
745 : DEBUG_FUNCTION basic_block
746 0 : debug_bb_n (int n)
747 : {
748 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
749 0 : debug_bb (bb);
750 0 : return bb;
751 : }
752 :
753 : /* Print BB with specified FLAGS. */
754 :
755 : DEBUG_FUNCTION void
756 0 : debug_bb (basic_block bb, dump_flags_t flags)
757 : {
758 0 : dump_bb (stderr, bb, 0, flags);
759 0 : }
760 :
761 : /* Print basic block numbered N with specified FLAGS. */
762 :
763 : DEBUG_FUNCTION basic_block
764 0 : debug_bb_n (int n, dump_flags_t flags)
765 : {
766 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
767 0 : debug_bb (bb, flags);
768 0 : return bb;
769 : }
770 :
771 : /* Dumps cfg related information about basic block BB to OUTF.
772 : If HEADER is true, dump things that appear before the instructions
773 : contained in BB. If FOOTER is true, dump things that appear after.
774 : Flags are the TDF_* masks as documented in dumpfile.h.
775 : NB: With TDF_DETAILS, it is assumed that cfun is available, so
776 : that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
777 :
778 : void
779 95752 : dump_bb_info (FILE *outf, basic_block bb, int indent, dump_flags_t flags,
780 : bool do_header, bool do_footer)
781 : {
782 95752 : edge_iterator ei;
783 95752 : edge e;
784 95752 : static const char * const bb_bitnames[] =
785 : {
786 : #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
787 : #include "cfg-flags.def"
788 : NULL
789 : #undef DEF_BASIC_BLOCK_FLAG
790 : };
791 95752 : const unsigned n_bitnames = ARRAY_SIZE (bb_bitnames);
792 95752 : bool first;
793 95752 : char *s_indent = (char *) alloca ((size_t) indent + 1);
794 95752 : memset ((void *) s_indent, ' ', (size_t) indent);
795 95752 : s_indent[indent] = '\0';
796 :
797 95752 : gcc_assert (bb->flags <= BB_ALL_FLAGS);
798 :
799 95752 : if (do_header)
800 : {
801 47958 : unsigned i;
802 :
803 47958 : fputs (";; ", outf);
804 47958 : fprintf (outf, "%sbasic block %d, loop depth %d",
805 : s_indent, bb->index, bb_loop_depth (bb));
806 47958 : if (flags & TDF_DETAILS)
807 : {
808 14101 : struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
809 14101 : if (bb->count.initialized_p ())
810 : {
811 13143 : fputs (", count ", outf);
812 13143 : bb->count.dump (outf, cfun);
813 : }
814 14101 : if (maybe_hot_bb_p (fun, bb))
815 12228 : fputs (", maybe hot", outf);
816 14101 : if (probably_never_executed_bb_p (fun, bb))
817 1316 : fputs (", probably never executed", outf);
818 : }
819 47958 : fputc ('\n', outf);
820 :
821 47958 : if (flags & TDF_DETAILS)
822 : {
823 14101 : check_bb_profile (bb, outf, indent);
824 14101 : fputs (";; ", outf);
825 14101 : fprintf (outf, "%s prev block ", s_indent);
826 14101 : if (bb->prev_bb)
827 14078 : fprintf (outf, "%d", bb->prev_bb->index);
828 : else
829 23 : fprintf (outf, "(nil)");
830 14101 : fprintf (outf, ", next block ");
831 14101 : if (bb->next_bb)
832 14078 : fprintf (outf, "%d", bb->next_bb->index);
833 : else
834 23 : fprintf (outf, "(nil)");
835 :
836 14101 : fputs (", flags:", outf);
837 14101 : first = true;
838 253818 : for (i = 0; i < n_bitnames; i++)
839 225616 : if (bb->flags & (1 << i))
840 : {
841 36464 : if (first)
842 14101 : fputs (" (", outf);
843 : else
844 22363 : fputs (", ", outf);
845 36464 : first = false;
846 36464 : fputs (bb_bitnames[i], outf);
847 : }
848 14101 : if (!first)
849 14101 : fputc (')', outf);
850 14101 : fputc ('\n', outf);
851 : }
852 :
853 47958 : fputs (";; ", outf);
854 47958 : fprintf (outf, "%s pred: ", s_indent);
855 47958 : first = true;
856 75647 : FOR_EACH_EDGE (e, ei, bb->preds)
857 : {
858 27689 : if (! first)
859 : {
860 6307 : fputs (";; ", outf);
861 6307 : fprintf (outf, "%s ", s_indent);
862 : }
863 27689 : first = false;
864 27689 : dump_edge_info (outf, e, flags, 0);
865 27689 : fputc ('\n', outf);
866 : }
867 47958 : if (first)
868 26576 : fputc ('\n', outf);
869 : }
870 :
871 95752 : if (do_footer)
872 : {
873 47958 : fputs (";; ", outf);
874 47958 : fprintf (outf, "%s succ: ", s_indent);
875 47958 : first = true;
876 95312 : FOR_EACH_EDGE (e, ei, bb->succs)
877 : {
878 47354 : if (! first)
879 : {
880 8696 : fputs (";; ", outf);
881 8696 : fprintf (outf, "%s ", s_indent);
882 : }
883 47354 : first = false;
884 47354 : dump_edge_info (outf, e, flags, 1);
885 47354 : fputc ('\n', outf);
886 : }
887 47958 : if (first)
888 9300 : fputc ('\n', outf);
889 : }
890 95752 : }
891 :
892 : /* Dumps a brief description of cfg to FILE. */
893 :
894 : void
895 22 : brief_dump_cfg (FILE *file, dump_flags_t flags)
896 : {
897 22 : basic_block bb;
898 :
899 186 : FOR_EACH_BB_FN (bb, cfun)
900 : {
901 164 : dump_bb_info (file, bb, 0, flags & TDF_DETAILS, true, true);
902 : }
903 22 : }
904 :
905 : /* Set probability of E to NEW_PROB and rescale other edges
906 : from E->src so their sum remains the same. */
907 :
908 : void
909 1689247 : set_edge_probability_and_rescale_others (edge e, profile_probability new_prob)
910 : {
911 1689247 : edge e2;
912 1689247 : edge_iterator ei;
913 1689247 : if (e->probability == new_prob)
914 56249 : return;
915 : /* If we made E unconditional, drop other frequencies to 0. */
916 1632998 : if (new_prob == profile_probability::always ())
917 : {
918 3 : FOR_EACH_EDGE (e2, ei, e->src->succs)
919 2 : if (e2 != e)
920 1 : e2->probability = profile_probability::never ();
921 : }
922 : else
923 : {
924 1632997 : int n = 0;
925 1632997 : edge other_e = NULL;
926 :
927 : /* See how many other edges are leaving exit_edge->src. */
928 4908449 : FOR_EACH_EDGE (e2, ei, e->src->succs)
929 3275452 : if (e2 != e && !(e2->flags & EDGE_FAKE))
930 : {
931 1642455 : other_e = e2;
932 1642455 : n++;
933 : }
934 : /* If there is only one other edge with non-zero probability we do not
935 : need to scale which drops quality of profile from precise
936 : to adjusted. */
937 1632997 : if (n == 1)
938 1630833 : other_e->probability = new_prob.invert ();
939 : /* Nothing to do if there are no other edges. */
940 2164 : else if (!n)
941 : ;
942 : /* Do scaling if possible. */
943 2164 : else if (e->probability.invert ().nonzero_p ())
944 : {
945 2164 : profile_probability num = new_prob.invert (),
946 2164 : den = e->probability.invert ();
947 15950 : FOR_EACH_EDGE (e2, ei, e->src->succs)
948 13786 : if (e2 != e && !(e2->flags & EDGE_FAKE))
949 11622 : e2->probability = e2->probability.apply_scale (num, den);
950 : }
951 : else
952 : {
953 0 : if (dump_file && (dump_flags & TDF_DETAILS))
954 0 : fprintf (dump_file,
955 : ";; probability of edge %i->%i set reduced from 1."
956 : " The remaining edges are left inconsistent.\n",
957 0 : e->src->index, e->dest->index);
958 0 : FOR_EACH_EDGE (e2, ei, e->src->succs)
959 0 : if (e2 != e && !(e2->flags & EDGE_FAKE))
960 0 : e2->probability = new_prob.invert ().guessed () / n;
961 : }
962 : }
963 1632998 : e->probability = new_prob;
964 : }
965 :
966 : /* An edge originally destinating BB of COUNT has been proved to
967 : leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
968 : redirected to destination of TAKEN_EDGE.
969 :
970 : This function may leave the profile inconsistent in the case TAKEN_EDGE
971 : frequency or count is believed to be lower than COUNT
972 : respectively. */
973 : void
974 1132407 : update_bb_profile_for_threading (basic_block bb,
975 : profile_count count, edge taken_edge)
976 : {
977 1132407 : gcc_assert (bb == taken_edge->src);
978 :
979 : /* If there is no profile or the threaded path is never executed
980 : we don't need to upate. */
981 1132407 : if (!bb->count.initialized_p ()
982 2264814 : || count == profile_count::zero ())
983 45 : return;
984 :
985 1132362 : if (bb->count < count)
986 : {
987 848 : if (dump_file)
988 0 : fprintf (dump_file, "bb %i count became negative after threading",
989 : bb->index);
990 : /* If probabilities looks very off, scale down and reduce to guesses
991 : to avoid dropping the other path close to zero. */
992 848 : if (bb->count < count.apply_scale (7, 8))
993 402 : count = bb->count.apply_scale (1, 2).guessed ();
994 : }
995 :
996 : /* If bb->count will become zero, the probabilities on the original path
997 : are not really known, but it is probably better to keep original ones
998 : then try to invent something new. */
999 1132362 : if (!(bb->count <= count))
1000 : {
1001 957749 : profile_probability prob;
1002 : /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
1003 : Watch for overflows. */
1004 957749 : if (bb->count.nonzero_p ())
1005 957749 : prob = count.probability_in (bb->count);
1006 : else
1007 0 : prob = taken_edge->probability.apply_scale (1, 2).guessed ();
1008 957749 : if (prob > taken_edge->probability)
1009 : {
1010 192924 : if (dump_file)
1011 : {
1012 18 : fprintf (dump_file, "Jump threading proved that the probability "
1013 : "of edge %i->%i was originally estimated too small. "
1014 : "(it is ",
1015 18 : taken_edge->src->index, taken_edge->dest->index);
1016 18 : taken_edge->probability.dump (dump_file);
1017 18 : fprintf (dump_file, " should be ");
1018 18 : prob.dump (dump_file);
1019 18 : fprintf (dump_file, ")\n");
1020 : }
1021 192924 : prob = taken_edge->probability.apply_scale (6, 8).guessed ();
1022 : }
1023 1915498 : set_edge_probability_and_rescale_others (taken_edge,
1024 1915498 : (taken_edge->probability - prob)
1025 1915498 : / prob.invert ());
1026 : }
1027 1132362 : bb->count -= count;
1028 : }
1029 :
1030 : /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1031 : by NUM/DEN, in profile_count arithmetic. More accurate than previous
1032 : function but considerably slower. */
1033 : void
1034 2316634 : scale_bbs_frequencies_profile_count (basic_block *bbs, int nbbs,
1035 : profile_count num, profile_count den)
1036 : {
1037 2316634 : int i;
1038 4773457 : if (num == profile_count::zero () || den.nonzero_p ())
1039 4630316 : for (i = 0; i < nbbs; i++)
1040 2315160 : bbs[i]->count = bbs[i]->count.apply_scale (num, den);
1041 2316634 : }
1042 :
1043 : /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1044 : by NUM/DEN, in profile_count arithmetic. More accurate than previous
1045 : function but considerably slower. */
1046 : void
1047 1043263 : scale_bbs_frequencies (basic_block *bbs, int nbbs,
1048 : profile_probability p)
1049 : {
1050 1043263 : int i;
1051 :
1052 3846143 : for (i = 0; i < nbbs; i++)
1053 2802880 : bbs[i]->count = bbs[i]->count.apply_probability (p);
1054 1043263 : }
1055 :
1056 : /* Data structures used to maintain mapping between basic blocks and
1057 : copies. */
1058 : typedef hash_map<int_hash<int, -1, -2>, int> copy_map_t;
1059 : static copy_map_t *bb_original;
1060 : static copy_map_t *bb_copy;
1061 :
1062 : /* And between loops and copies. */
1063 : static copy_map_t *loop_copy;
1064 :
1065 : /* Initialize the data structures to maintain mapping between blocks
1066 : and its copies. */
1067 : void
1068 6516625 : initialize_original_copy_tables (void)
1069 : {
1070 6516625 : bb_original = new copy_map_t (10);
1071 6516625 : bb_copy = new copy_map_t (10);
1072 6516625 : loop_copy = new copy_map_t (10);
1073 6516625 : }
1074 :
1075 : /* Reset the data structures to maintain mapping between blocks and
1076 : its copies. */
1077 :
1078 : void
1079 438 : reset_original_copy_tables (void)
1080 : {
1081 438 : bb_original->empty ();
1082 438 : bb_copy->empty ();
1083 438 : loop_copy->empty ();
1084 438 : }
1085 :
1086 : /* Free the data structures to maintain mapping between blocks and
1087 : its copies. */
1088 : void
1089 6516625 : free_original_copy_tables (void)
1090 : {
1091 13033250 : delete bb_copy;
1092 6516625 : bb_copy = NULL;
1093 13033250 : delete bb_original;
1094 6516625 : bb_original = NULL;
1095 13033250 : delete loop_copy;
1096 6516625 : loop_copy = NULL;
1097 6516625 : }
1098 :
1099 : /* Return true iff we have had a call to initialize_original_copy_tables
1100 : without a corresponding call to free_original_copy_tables. */
1101 :
1102 : bool
1103 32643310 : original_copy_tables_initialized_p (void)
1104 : {
1105 32643310 : return bb_copy != NULL;
1106 : }
1107 :
1108 : /* Removes the value associated with OBJ from table TAB. */
1109 :
1110 : static void
1111 278032 : copy_original_table_clear (copy_map_t *tab, unsigned obj)
1112 : {
1113 278032 : if (!original_copy_tables_initialized_p ())
1114 : return;
1115 :
1116 278032 : tab->remove (obj);
1117 : }
1118 :
1119 : /* Sets the value associated with OBJ in table TAB to VAL.
1120 : Do nothing when data structures are not initialized. */
1121 :
1122 : static void
1123 11716925 : copy_original_table_set (copy_map_t *tab,
1124 : unsigned obj, unsigned val)
1125 : {
1126 11716925 : if (!original_copy_tables_initialized_p ())
1127 : return;
1128 :
1129 11634555 : tab->put (obj, val);
1130 : }
1131 :
1132 : /* Set original for basic block. Do nothing when data structures are not
1133 : initialized so passes not needing this don't need to care. */
1134 : void
1135 4633967 : set_bb_original (basic_block bb, basic_block original)
1136 : {
1137 4633967 : copy_original_table_set (bb_original, bb->index, original->index);
1138 4633967 : }
1139 :
1140 : /* Get the original basic block. */
1141 : basic_block
1142 4152733 : get_bb_original (basic_block bb)
1143 : {
1144 4152733 : gcc_assert (original_copy_tables_initialized_p ());
1145 :
1146 4152733 : int *entry = bb_original->get (bb->index);
1147 4152733 : if (entry)
1148 3817384 : return BASIC_BLOCK_FOR_FN (cfun, *entry);
1149 : else
1150 : return NULL;
1151 : }
1152 :
1153 : /* Set copy for basic block. Do nothing when data structures are not
1154 : initialized so passes not needing this don't need to care. */
1155 : void
1156 4633967 : set_bb_copy (basic_block bb, basic_block copy)
1157 : {
1158 4633967 : copy_original_table_set (bb_copy, bb->index, copy->index);
1159 4633967 : }
1160 :
1161 : /* Get the copy of basic block. */
1162 : basic_block
1163 9002631 : get_bb_copy (basic_block bb)
1164 : {
1165 9002631 : gcc_assert (original_copy_tables_initialized_p ());
1166 :
1167 9002631 : int *entry = bb_copy->get (bb->index);
1168 9002631 : if (entry)
1169 8982836 : return BASIC_BLOCK_FOR_FN (cfun, *entry);
1170 : else
1171 : return NULL;
1172 : }
1173 :
1174 : /* Set copy for LOOP to COPY. Do nothing when data structures are not
1175 : initialized so passes not needing this don't need to care. */
1176 :
1177 : void
1178 2727023 : set_loop_copy (class loop *loop, class loop *copy)
1179 : {
1180 2727023 : if (!copy)
1181 278032 : copy_original_table_clear (loop_copy, loop->num);
1182 : else
1183 2448991 : copy_original_table_set (loop_copy, loop->num, copy->num);
1184 2727023 : }
1185 :
1186 : /* Get the copy of LOOP. */
1187 :
1188 : class loop *
1189 4344093 : get_loop_copy (class loop *loop)
1190 : {
1191 4344093 : gcc_assert (original_copy_tables_initialized_p ());
1192 :
1193 4344093 : int *entry = loop_copy->get (loop->num);
1194 4344093 : if (entry)
1195 3955325 : return get_loop (cfun, *entry);
1196 : else
1197 : return NULL;
1198 : }
1199 :
1200 : /* Scales the frequencies of all basic blocks that are strictly
1201 : dominated by BB by NUM/DEN. */
1202 :
1203 : void
1204 26 : scale_strictly_dominated_blocks (basic_block bb,
1205 : profile_count num, profile_count den)
1206 : {
1207 26 : basic_block son;
1208 :
1209 26 : if (!den.nonzero_p () && !(num == profile_count::zero ()))
1210 0 : return;
1211 26 : auto_vec <basic_block, 8> worklist;
1212 26 : worklist.safe_push (bb);
1213 :
1214 180 : while (!worklist.is_empty ())
1215 102 : for (son = first_dom_son (CDI_DOMINATORS, worklist.pop ());
1216 178 : son;
1217 76 : son = next_dom_son (CDI_DOMINATORS, son))
1218 : {
1219 76 : son->count = son->count.apply_scale (num, den);
1220 76 : worklist.safe_push (son);
1221 : }
1222 26 : }
|
