1/* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
65void
66init_flow (struct function *the_fun)
67{
68 if (!the_fun->cfg)
69 the_fun->cfg = ggc_cleared_alloc<control_flow_graph> ();
70 n_edges_for_fn (the_fun) = 0;
71 the_fun->cfg->count_max = profile_count::uninitialized ();
72 ENTRY_BLOCK_PTR_FOR_FN (the_fun)
73 = alloc_block ();
74 ENTRY_BLOCK_PTR_FOR_FN (the_fun)->index = ENTRY_BLOCK;
75 EXIT_BLOCK_PTR_FOR_FN (the_fun)
76 = alloc_block ();
77 EXIT_BLOCK_PTR_FOR_FN (the_fun)->index = EXIT_BLOCK;
78 ENTRY_BLOCK_PTR_FOR_FN (the_fun)->next_bb
79 = EXIT_BLOCK_PTR_FOR_FN (the_fun);
80 EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
81 = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
82 the_fun->cfg->edge_flags_allocated = EDGE_ALL_FLAGS;
83 the_fun->cfg->bb_flags_allocated = BB_ALL_FLAGS;
84 the_fun->cfg->full_profile = false;
85}
86
87/* Helper function for remove_edge and free_cffg. Frees edge structure
88 without actually removing it from the pred/succ arrays. */
89
90static void
91free_edge (function *fn, edge e)
92{
93 n_edges_for_fn (fn)--;
94 ggc_free (e);
95}
96
97/* Free basic block BB. */
98
99static void
100free_block (basic_block bb)
101{
102 vec_free (v&: bb->succs);
103 bb->succs = NULL;
104 vec_free (v&: bb->preds);
105 bb->preds = NULL;
106 ggc_free (bb);
107}
108
109/* Free the memory associated with the CFG in FN. */
110
111void
112free_cfg (struct function *fn)
113{
114 edge e;
115 edge_iterator ei;
116 basic_block next;
117
118 for (basic_block bb = ENTRY_BLOCK_PTR_FOR_FN (fn); bb; bb = next)
119 {
120 next = bb->next_bb;
121 FOR_EACH_EDGE (e, ei, bb->succs)
122 free_edge (fn, e);
123 free_block (bb);
124 }
125
126 gcc_assert (!n_edges_for_fn (fn));
127 /* Sanity check that dominance tree is freed. */
128 gcc_assert (!fn->cfg->x_dom_computed[0] && !fn->cfg->x_dom_computed[1]);
129
130 vec_free (v&: fn->cfg->x_label_to_block_map);
131 vec_free (basic_block_info_for_fn (fn));
132 ggc_free (fn->cfg);
133 fn->cfg = NULL;
134}
135
136/* Allocate memory for basic_block. */
137
138basic_block
139alloc_block (void)
140{
141 basic_block bb;
142 bb = ggc_cleared_alloc<basic_block_def> ();
143 bb->count = profile_count::uninitialized ();
144 return bb;
145}
146
147/* Link block B to chain after AFTER. */
148void
149link_block (basic_block b, basic_block after)
150{
151 b->next_bb = after->next_bb;
152 b->prev_bb = after;
153 after->next_bb = b;
154 b->next_bb->prev_bb = b;
155}
156
157/* Unlink block B from chain. */
158void
159unlink_block (basic_block b)
160{
161 b->next_bb->prev_bb = b->prev_bb;
162 b->prev_bb->next_bb = b->next_bb;
163 b->prev_bb = NULL;
164 b->next_bb = NULL;
165}
166
167/* Sequentially order blocks and compact the arrays. */
168void
169compact_blocks (void)
170{
171 int i;
172
173 SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
174 SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
175
176 if (df)
177 df_compact_blocks ();
178 else
179 {
180 basic_block bb;
181
182 i = NUM_FIXED_BLOCKS;
183 FOR_EACH_BB_FN (bb, cfun)
184 {
185 SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
186 bb->index = i;
187 i++;
188 }
189 gcc_assert (i == n_basic_blocks_for_fn (cfun));
190
191 for (; i < last_basic_block_for_fn (cfun); i++)
192 SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
193 }
194 last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
195}
196
197/* Remove block B from the basic block array. */
198
199void
200expunge_block (basic_block b)
201{
202 unlink_block (b);
203 SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
204 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}
211
212/* Connect E to E->src. */
213
214static inline void
215connect_src (edge e)
216{
217 vec_safe_push (v&: e->src->succs, obj: e);
218 df_mark_solutions_dirty ();
219}
220
221/* Connect E to E->dest. */
222
223static inline void
224connect_dest (edge e)
225{
226 basic_block dest = e->dest;
227 vec_safe_push (v&: dest->preds, obj: e);
228 e->dest_idx = EDGE_COUNT (dest->preds) - 1;
229 df_mark_solutions_dirty ();
230}
231
232/* Disconnect edge E from E->src. */
233
234static inline void
235disconnect_src (edge e)
236{
237 basic_block src = e->src;
238 edge_iterator ei;
239 edge tmp;
240
241 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (i: ei)); )
242 {
243 if (tmp == e)
244 {
245 src->succs->unordered_remove (ix: ei.index);
246 df_mark_solutions_dirty ();
247 return;
248 }
249 else
250 ei_next (i: &ei);
251 }
252
253 gcc_unreachable ();
254}
255
256/* Disconnect edge E from E->dest. */
257
258static inline void
259disconnect_dest (edge e)
260{
261 basic_block dest = e->dest;
262 unsigned int dest_idx = e->dest_idx;
263
264 dest->preds->unordered_remove (ix: 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 if (dest_idx < EDGE_COUNT (dest->preds))
269 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
270 df_mark_solutions_dirty ();
271}
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
277edge
278unchecked_make_edge (basic_block src, basic_block dst, int flags)
279{
280 edge e;
281 e = ggc_cleared_alloc<edge_def> ();
282 n_edges_for_fn (cfun)++;
283
284 e->probability = profile_probability::uninitialized ();
285 e->src = src;
286 e->dest = dst;
287 e->flags = flags;
288
289 connect_src (e);
290 connect_dest (e);
291
292 execute_on_growing_pred (e);
293 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
299edge
300cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
301{
302 if (edge_cache == NULL
303 || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
304 || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
305 return make_edge (src, dst, flags);
306
307 /* Does the requested edge already exist? */
308 if (! bitmap_bit_p (map: edge_cache, bitno: dst->index))
309 {
310 /* The edge does not exist. Create one and update the
311 cache. */
312 bitmap_set_bit (map: edge_cache, bitno: dst->index);
313 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 if (flags)
319 {
320 edge e = find_edge (src, dst);
321 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
330edge
331make_edge (basic_block src, basic_block dest, int flags)
332{
333 edge e = find_edge (src, dest);
334
335 /* Make sure we don't add duplicate edges. */
336 if (e)
337 {
338 e->flags |= flags;
339 return NULL;
340 }
341
342 return unchecked_make_edge (src, dst: 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
348edge
349make_single_succ_edge (basic_block src, basic_block dest, int flags)
350{
351 edge e = make_edge (src, dest, flags);
352
353 e->probability = profile_probability::always ();
354 return e;
355}
356
357/* This function will remove an edge from the flow graph. */
358
359void
360remove_edge_raw (edge e)
361{
362 remove_predictions_associated_with_edge (e);
363 execute_on_shrinking_pred (e);
364
365 disconnect_src (e);
366 disconnect_dest (e);
367
368 free_edge (cfun, e);
369}
370
371/* Redirect an edge's successor from one block to another. */
372
373void
374redirect_edge_succ (edge e, basic_block new_succ)
375{
376 execute_on_shrinking_pred (e);
377
378 disconnect_dest (e);
379
380 e->dest = new_succ;
381
382 /* Reconnect the edge to the new successor block. */
383 connect_dest (e);
384
385 execute_on_growing_pred (e);
386}
387
388/* Redirect an edge's predecessor from one block to another. */
389
390void
391redirect_edge_pred (edge e, basic_block new_pred)
392{
393 disconnect_src (e);
394
395 e->src = new_pred;
396
397 /* Reconnect the edge to the new predecessor block. */
398 connect_src (e);
399}
400
401/* Clear all basic block flags that do not have to be preserved. */
402void
403clear_bb_flags (void)
404{
405 basic_block bb;
406 int flags_to_preserve = BB_FLAGS_TO_PRESERVE;
407 if (current_loops
408 && loops_state_satisfies_p (cfun, flags: LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
409 flags_to_preserve |= BB_IRREDUCIBLE_LOOP;
410
411 FOR_ALL_BB_FN (bb, cfun)
412 bb->flags &= flags_to_preserve;
413}
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. */
420static void
421check_bb_profile (basic_block bb, FILE * file, int indent)
422{
423 edge e;
424 edge_iterator ei;
425 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
426 char *s_indent = (char *) alloca ((size_t) indent + 1);
427 memset (s: (void *) s_indent, c: ' ', n: (size_t) indent);
428 s_indent[indent] = '\0';
429
430 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
431 return;
432
433 if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
434 {
435 bool found = false;
436 profile_probability sum = profile_probability::never ();
437 int isum = 0;
438
439 FOR_EACH_EDGE (e, ei, bb->succs)
440 {
441 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
442 found = true;
443 sum += e->probability;
444 if (e->probability.initialized_p ())
445 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 if (found)
451 {
452 if (sum.differs_from_p (other: profile_probability::always ()))
453 {
454 fprintf (stream: file,
455 format: ";; %sInvalid sum of outgoing probabilities ",
456 s_indent);
457 sum.dump (f: file);
458 fprintf (stream: file, format: "\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 else if (isum > REG_BR_PROB_BASE + 100)
463 {
464 fprintf (stream: file,
465 format: ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
466 s_indent, isum * 100.0 / REG_BR_PROB_BASE);
467 }
468 }
469 }
470 if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
471 {
472 profile_count sum = profile_count::zero ();
473 FOR_EACH_EDGE (e, ei, bb->preds)
474 sum += e->count ();
475 if (sum.differs_from_p (other: bb->count))
476 {
477 fprintf (stream: file, format: ";; %sInvalid sum of incoming counts ",
478 s_indent);
479 sum.dump (f: file, fun);
480 fprintf (stream: file, format: ", should be ");
481 bb->count.dump (f: file, fun);
482 fprintf (stream: file, format: "\n");
483 }
484 }
485 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 if (!probably_never_executed_bb_p (fun, bb))
490 fprintf (stream: file, format: ";; %sBlock in cold partition with hot count\n",
491 s_indent);
492 FOR_EACH_EDGE (e, ei, bb->preds)
493 {
494 if (!probably_never_executed_edge_p (fun, e))
495 fprintf (stream: file,
496 format: ";; %sBlock in cold partition with incoming hot edge\n",
497 s_indent);
498 }
499 }
500}
501
502void
503dump_edge_info (FILE *file, edge e, dump_flags_t flags, int do_succ)
504{
505 basic_block side = (do_succ ? e->dest : e->src);
506 bool do_details = false;
507
508 if ((flags & TDF_DETAILS) != 0
509 && (flags & TDF_SLIM) == 0)
510 do_details = true;
511
512 if (side->index == ENTRY_BLOCK)
513 fputs (s: " ENTRY", stream: file);
514 else if (side->index == EXIT_BLOCK)
515 fputs (s: " EXIT", stream: file);
516 else
517 fprintf (stream: file, format: " %d", side->index);
518
519 if (e->probability.initialized_p () && do_details)
520 {
521 fprintf (stream: file, format: " [");
522 e->probability.dump (f: file);
523 fprintf (stream: file, format: "] ");
524 }
525
526 if (e->count ().initialized_p () && do_details)
527 {
528 fputs (s: " count:", stream: file);
529 e->count ().dump (f: file, cfun);
530 }
531
532 if (e->flags && do_details)
533 {
534 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 bool comma = false;
542 int i, flags = e->flags;
543
544 gcc_assert (e->flags <= EDGE_ALL_FLAGS);
545 fputs (s: " (", stream: file);
546 for (i = 0; flags; i++)
547 if (flags & (1 << i))
548 {
549 flags &= ~(1 << i);
550
551 if (comma)
552 fputc (c: ',', stream: file);
553 fputs (s: bitnames[i], stream: file);
554 comma = true;
555 }
556
557 fputc (c: ')', stream: file);
558 }
559
560 if (do_details && LOCATION_LOCUS (e->goto_locus) > BUILTINS_LOCATION)
561 fprintf (stream: file, format: " %s:%d:%d", LOCATION_FILE (e->goto_locus),
562 LOCATION_LINE (e->goto_locus), LOCATION_COLUMN (e->goto_locus));
563}
564
565DEBUG_FUNCTION void
566debug (edge_def &ref)
567{
568 fprintf (stderr, format: "<edge (%d -> %d)>\n",
569 ref.src->index, ref.dest->index);
570 dump_edge_info (stderr, e: &ref, flags: TDF_DETAILS, do_succ: false);
571 fprintf (stderr, format: "\n");
572}
573
574DEBUG_FUNCTION void
575debug (edge_def *ptr)
576{
577 if (ptr)
578 debug (ref&: *ptr);
579 else
580 fprintf (stderr, format: "<nil>\n");
581}
582
583static void
584debug_slim (edge e)
585{
586 fprintf (stderr, format: "<edge 0x%p (%d -> %d)>", (void *) e,
587 e->src->index, e->dest->index);
588}
589
590DEFINE_DEBUG_VEC (edge)
591DEFINE_DEBUG_HASH_SET (edge)
592
593/* Simple routines to easily allocate AUX fields of basic blocks. */
594
595static struct obstack block_aux_obstack;
596static void *first_block_aux_obj = 0;
597static struct obstack edge_aux_obstack;
598static 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
603static void
604alloc_aux_for_block (basic_block bb, int size)
605{
606 /* Verify that aux field is clear. */
607 gcc_assert (!bb->aux && first_block_aux_obj);
608 bb->aux = obstack_alloc (&block_aux_obstack, size);
609 memset (s: bb->aux, c: 0, n: size);
610}
611
612/* Initialize the block_aux_obstack and if SIZE is nonzero, call
613 alloc_aux_for_block for each basic block. */
614
615void
616alloc_aux_for_blocks (int size)
617{
618 static int initialized;
619
620 if (!initialized)
621 {
622 gcc_obstack_init (&block_aux_obstack);
623 initialized = 1;
624 }
625 else
626 /* Check whether AUX data are still allocated. */
627 gcc_assert (!first_block_aux_obj);
628
629 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
630 if (size)
631 {
632 basic_block bb;
633
634 FOR_ALL_BB_FN (bb, cfun)
635 alloc_aux_for_block (bb, size);
636 }
637}
638
639/* Clear AUX pointers of all blocks. */
640
641void
642clear_aux_for_blocks (void)
643{
644 basic_block bb;
645
646 FOR_ALL_BB_FN (bb, cfun)
647 bb->aux = NULL;
648}
649
650/* Free data allocated in block_aux_obstack and clear AUX pointers
651 of all blocks. */
652
653void
654free_aux_for_blocks (void)
655{
656 gcc_assert (first_block_aux_obj);
657 obstack_free (&block_aux_obstack, first_block_aux_obj);
658 first_block_aux_obj = NULL;
659
660 clear_aux_for_blocks ();
661}
662
663/* Allocate a memory edge of SIZE as E->aux. The obstack must
664 be first initialized by alloc_aux_for_edges. */
665
666void
667alloc_aux_for_edge (edge e, int size)
668{
669 /* Verify that aux field is clear. */
670 gcc_assert (!e->aux && first_edge_aux_obj);
671 e->aux = obstack_alloc (&edge_aux_obstack, size);
672 memset (s: e->aux, c: 0, n: size);
673}
674
675/* Initialize the edge_aux_obstack and if SIZE is nonzero, call
676 alloc_aux_for_edge for each basic edge. */
677
678void
679alloc_aux_for_edges (int size)
680{
681 static int initialized;
682
683 if (!initialized)
684 {
685 gcc_obstack_init (&edge_aux_obstack);
686 initialized = 1;
687 }
688 else
689 /* Check whether AUX data are still allocated. */
690 gcc_assert (!first_edge_aux_obj);
691
692 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
693 if (size)
694 {
695 basic_block bb;
696
697 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
698 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
699 {
700 edge e;
701 edge_iterator ei;
702
703 FOR_EACH_EDGE (e, ei, bb->succs)
704 alloc_aux_for_edge (e, size);
705 }
706 }
707}
708
709/* Clear AUX pointers of all edges. */
710
711void
712clear_aux_for_edges (void)
713{
714 basic_block bb;
715 edge e;
716
717 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
718 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
719 {
720 edge_iterator ei;
721 FOR_EACH_EDGE (e, ei, bb->succs)
722 e->aux = NULL;
723 }
724}
725
726/* Free data allocated in edge_aux_obstack and clear AUX pointers
727 of all edges. */
728
729void
730free_aux_for_edges (void)
731{
732 gcc_assert (first_edge_aux_obj);
733 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
734 first_edge_aux_obj = NULL;
735
736 clear_aux_for_edges ();
737}
738
739DEBUG_FUNCTION void
740debug_bb (basic_block bb)
741{
742 debug_bb (bb, dump_flags);
743}
744
745DEBUG_FUNCTION basic_block
746debug_bb_n (int n)
747{
748 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
749 debug_bb (bb);
750 return bb;
751}
752
753/* Print BB with specified FLAGS. */
754
755DEBUG_FUNCTION void
756debug_bb (basic_block bb, dump_flags_t flags)
757{
758 dump_bb (stderr, bb, 0, flags);
759}
760
761/* Print basic block numbered N with specified FLAGS. */
762
763DEBUG_FUNCTION basic_block
764debug_bb_n (int n, dump_flags_t flags)
765{
766 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
767 debug_bb (bb, flags);
768 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
778void
779dump_bb_info (FILE *outf, basic_block bb, int indent, dump_flags_t flags,
780 bool do_header, bool do_footer)
781{
782 edge_iterator ei;
783 edge e;
784 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 const unsigned n_bitnames = ARRAY_SIZE (bb_bitnames);
792 bool first;
793 char *s_indent = (char *) alloca ((size_t) indent + 1);
794 memset (s: (void *) s_indent, c: ' ', n: (size_t) indent);
795 s_indent[indent] = '\0';
796
797 gcc_assert (bb->flags <= BB_ALL_FLAGS);
798
799 if (do_header)
800 {
801 unsigned i;
802
803 fputs (s: ";; ", stream: outf);
804 fprintf (stream: outf, format: "%sbasic block %d, loop depth %d",
805 s_indent, bb->index, bb_loop_depth (bb));
806 if (flags & TDF_DETAILS)
807 {
808 struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
809 if (bb->count.initialized_p ())
810 {
811 fputs (s: ", count ", stream: outf);
812 bb->count.dump (f: outf, cfun);
813 }
814 if (maybe_hot_bb_p (fun, bb))
815 fputs (s: ", maybe hot", stream: outf);
816 if (probably_never_executed_bb_p (fun, bb))
817 fputs (s: ", probably never executed", stream: outf);
818 }
819 fputc (c: '\n', stream: outf);
820
821 if (flags & TDF_DETAILS)
822 {
823 check_bb_profile (bb, file: outf, indent);
824 fputs (s: ";; ", stream: outf);
825 fprintf (stream: outf, format: "%s prev block ", s_indent);
826 if (bb->prev_bb)
827 fprintf (stream: outf, format: "%d", bb->prev_bb->index);
828 else
829 fprintf (stream: outf, format: "(nil)");
830 fprintf (stream: outf, format: ", next block ");
831 if (bb->next_bb)
832 fprintf (stream: outf, format: "%d", bb->next_bb->index);
833 else
834 fprintf (stream: outf, format: "(nil)");
835
836 fputs (s: ", flags:", stream: outf);
837 first = true;
838 for (i = 0; i < n_bitnames; i++)
839 if (bb->flags & (1 << i))
840 {
841 if (first)
842 fputs (s: " (", stream: outf);
843 else
844 fputs (s: ", ", stream: outf);
845 first = false;
846 fputs (s: bb_bitnames[i], stream: outf);
847 }
848 if (!first)
849 fputc (c: ')', stream: outf);
850 fputc (c: '\n', stream: outf);
851 }
852
853 fputs (s: ";; ", stream: outf);
854 fprintf (stream: outf, format: "%s pred: ", s_indent);
855 first = true;
856 FOR_EACH_EDGE (e, ei, bb->preds)
857 {
858 if (! first)
859 {
860 fputs (s: ";; ", stream: outf);
861 fprintf (stream: outf, format: "%s ", s_indent);
862 }
863 first = false;
864 dump_edge_info (file: outf, e, flags, do_succ: 0);
865 fputc (c: '\n', stream: outf);
866 }
867 if (first)
868 fputc (c: '\n', stream: outf);
869 }
870
871 if (do_footer)
872 {
873 fputs (s: ";; ", stream: outf);
874 fprintf (stream: outf, format: "%s succ: ", s_indent);
875 first = true;
876 FOR_EACH_EDGE (e, ei, bb->succs)
877 {
878 if (! first)
879 {
880 fputs (s: ";; ", stream: outf);
881 fprintf (stream: outf, format: "%s ", s_indent);
882 }
883 first = false;
884 dump_edge_info (file: outf, e, flags, do_succ: 1);
885 fputc (c: '\n', stream: outf);
886 }
887 if (first)
888 fputc (c: '\n', stream: outf);
889 }
890}
891
892/* Dumps a brief description of cfg to FILE. */
893
894void
895brief_dump_cfg (FILE *file, dump_flags_t flags)
896{
897 basic_block bb;
898
899 FOR_EACH_BB_FN (bb, cfun)
900 {
901 dump_bb_info (outf: file, bb, indent: 0, flags: flags & TDF_DETAILS, do_header: true, do_footer: true);
902 }
903}
904
905/* Set probability of E to NEW_PROB and rescale other edges
906 from E->src so their sum remains the same. */
907
908void
909set_edge_probability_and_rescale_others (edge e, profile_probability new_prob)
910{
911 edge e2;
912 edge_iterator ei;
913 if (e->probability == new_prob)
914 return;
915 /* If we made E unconditional, drop other frequencies to 0. */
916 if (new_prob == profile_probability::always ())
917 {
918 FOR_EACH_EDGE (e2, ei, e->src->succs)
919 if (e2 != e)
920 e2->probability = profile_probability::never ();
921 }
922 else
923 {
924 int n = 0;
925 edge other_e = NULL;
926
927 /* See how many other edges are leaving exit_edge->src. */
928 FOR_EACH_EDGE (e2, ei, e->src->succs)
929 if (e2 != e && !(e2->flags & EDGE_FAKE))
930 {
931 other_e = e2;
932 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 if (n == 1)
938 other_e->probability = new_prob.invert ();
939 /* Nothing to do if there are no other edges. */
940 else if (!n)
941 ;
942 /* Do scaling if possible. */
943 else if (e->probability.invert ().nonzero_p ())
944 {
945 profile_probability num = new_prob.invert (),
946 den = e->probability.invert ();
947 FOR_EACH_EDGE (e2, ei, e->src->succs)
948 if (e2 != e && !(e2->flags & EDGE_FAKE))
949 e2->probability = e2->probability.apply_scale (num, den);
950 }
951 else
952 {
953 if (dump_file && (dump_flags & TDF_DETAILS))
954 fprintf (stream: dump_file,
955 format: ";; probability of edge %i->%i set reduced from 1."
956 " The remaining edges are left inconsistent.\n",
957 e->src->index, e->dest->index);
958 FOR_EACH_EDGE (e2, ei, e->src->succs)
959 if (e2 != e && !(e2->flags & EDGE_FAKE))
960 e2->probability = new_prob.invert ().guessed () / n;
961 }
962 }
963 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. */
973void
974update_bb_profile_for_threading (basic_block bb,
975 profile_count count, edge taken_edge)
976{
977 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 if (!bb->count.initialized_p ()
982 || count == profile_count::zero ())
983 return;
984
985 if (bb->count < count)
986 {
987 if (dump_file)
988 fprintf (stream: dump_file, format: "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 if (bb->count < count.apply_scale (num: 7, den: 8))
993 count = bb->count.apply_scale (num: 1, den: 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 if (!(bb->count <= count))
1000 {
1001 profile_probability prob;
1002 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
1003 Watch for overflows. */
1004 if (bb->count.nonzero_p ())
1005 prob = count.probability_in (overall: bb->count);
1006 else
1007 prob = taken_edge->probability.apply_scale (num: 1, den: 2).guessed ();
1008 if (prob > taken_edge->probability)
1009 {
1010 if (dump_file)
1011 {
1012 fprintf (stream: dump_file, format: "Jump threading proved that the probability "
1013 "of edge %i->%i was originally estimated too small. "
1014 "(it is ",
1015 taken_edge->src->index, taken_edge->dest->index);
1016 taken_edge->probability.dump (f: dump_file);
1017 fprintf (stream: dump_file, format: " should be ");
1018 prob.dump (f: dump_file);
1019 fprintf (stream: dump_file, format: ")\n");
1020 }
1021 prob = taken_edge->probability.apply_scale (num: 6, den: 8).guessed ();
1022 }
1023 set_edge_probability_and_rescale_others (e: taken_edge,
1024 new_prob: (taken_edge->probability - prob)
1025 / prob.invert ());
1026 }
1027 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. */
1033void
1034scale_bbs_frequencies_profile_count (basic_block *bbs, int nbbs,
1035 profile_count num, profile_count den)
1036{
1037 int i;
1038 if (num == profile_count::zero () || den.nonzero_p ())
1039 for (i = 0; i < nbbs; i++)
1040 bbs[i]->count = bbs[i]->count.apply_scale (num, den);
1041}
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. */
1046void
1047scale_bbs_frequencies (basic_block *bbs, int nbbs,
1048 profile_probability p)
1049{
1050 int i;
1051
1052 for (i = 0; i < nbbs; i++)
1053 bbs[i]->count = bbs[i]->count.apply_probability (prob: p);
1054}
1055
1056/* Data structures used to maintain mapping between basic blocks and
1057 copies. */
1058typedef hash_map<int_hash<int, -1, -2>, int> copy_map_t;
1059static copy_map_t *bb_original;
1060static copy_map_t *bb_copy;
1061
1062/* And between loops and copies. */
1063static copy_map_t *loop_copy;
1064
1065/* Initialize the data structures to maintain mapping between blocks
1066 and its copies. */
1067void
1068initialize_original_copy_tables (void)
1069{
1070 bb_original = new copy_map_t (10);
1071 bb_copy = new copy_map_t (10);
1072 loop_copy = new copy_map_t (10);
1073}
1074
1075/* Reset the data structures to maintain mapping between blocks and
1076 its copies. */
1077
1078void
1079reset_original_copy_tables (void)
1080{
1081 bb_original->empty ();
1082 bb_copy->empty ();
1083 loop_copy->empty ();
1084}
1085
1086/* Free the data structures to maintain mapping between blocks and
1087 its copies. */
1088void
1089free_original_copy_tables (void)
1090{
1091 delete bb_copy;
1092 bb_copy = NULL;
1093 delete bb_original;
1094 bb_original = NULL;
1095 delete loop_copy;
1096 loop_copy = NULL;
1097}
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
1102bool
1103original_copy_tables_initialized_p (void)
1104{
1105 return bb_copy != NULL;
1106}
1107
1108/* Removes the value associated with OBJ from table TAB. */
1109
1110static void
1111copy_original_table_clear (copy_map_t *tab, unsigned obj)
1112{
1113 if (!original_copy_tables_initialized_p ())
1114 return;
1115
1116 tab->remove (k: 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
1122static void
1123copy_original_table_set (copy_map_t *tab,
1124 unsigned obj, unsigned val)
1125{
1126 if (!original_copy_tables_initialized_p ())
1127 return;
1128
1129 tab->put (k: obj, v: 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. */
1134void
1135set_bb_original (basic_block bb, basic_block original)
1136{
1137 copy_original_table_set (tab: bb_original, obj: bb->index, val: original->index);
1138}
1139
1140/* Get the original basic block. */
1141basic_block
1142get_bb_original (basic_block bb)
1143{
1144 gcc_assert (original_copy_tables_initialized_p ());
1145
1146 int *entry = bb_original->get (k: bb->index);
1147 if (entry)
1148 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. */
1155void
1156set_bb_copy (basic_block bb, basic_block copy)
1157{
1158 copy_original_table_set (tab: bb_copy, obj: bb->index, val: copy->index);
1159}
1160
1161/* Get the copy of basic block. */
1162basic_block
1163get_bb_copy (basic_block bb)
1164{
1165 gcc_assert (original_copy_tables_initialized_p ());
1166
1167 int *entry = bb_copy->get (k: bb->index);
1168 if (entry)
1169 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
1177void
1178set_loop_copy (class loop *loop, class loop *copy)
1179{
1180 if (!copy)
1181 copy_original_table_clear (tab: loop_copy, obj: loop->num);
1182 else
1183 copy_original_table_set (tab: loop_copy, obj: loop->num, val: copy->num);
1184}
1185
1186/* Get the copy of LOOP. */
1187
1188class loop *
1189get_loop_copy (class loop *loop)
1190{
1191 gcc_assert (original_copy_tables_initialized_p ());
1192
1193 int *entry = loop_copy->get (k: loop->num);
1194 if (entry)
1195 return get_loop (cfun, num: *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
1203void
1204scale_strictly_dominated_blocks (basic_block bb,
1205 profile_count num, profile_count den)
1206{
1207 basic_block son;
1208
1209 if (!den.nonzero_p () && !(num == profile_count::zero ()))
1210 return;
1211 auto_vec <basic_block, 8> worklist;
1212 worklist.safe_push (obj: bb);
1213
1214 while (!worklist.is_empty ())
1215 for (son = first_dom_son (CDI_DOMINATORS, worklist.pop ());
1216 son;
1217 son = next_dom_son (CDI_DOMINATORS, son))
1218 {
1219 son->count = son->count.apply_scale (num, den);
1220 worklist.safe_push (obj: son);
1221 }
1222}
1223

source code of gcc/cfg.cc