xref: /netbsd-src/external/gpl3/gcc/dist/gcc/cfg.cc (revision b1e838363e3c6fc78a55519254d99869742dd33c)
1 /* Control flow graph manipulation code for GNU compiler.
2    Copyright (C) 1987-2022 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
init_flow(struct function * the_fun)66 init_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 }
85 
86 /* Helper function for remove_edge and free_cffg.  Frees edge structure
87    without actually removing it from the pred/succ arrays.  */
88 
89 static void
free_edge(function * fn,edge e)90 free_edge (function *fn, edge e)
91 {
92   n_edges_for_fn (fn)--;
93   ggc_free (e);
94 }
95 
96 /* Free basic block BB.  */
97 
98 static void
free_block(basic_block bb)99 free_block (basic_block bb)
100 {
101    vec_free (bb->succs);
102    bb->succs = NULL;
103    vec_free (bb->preds);
104    bb->preds = NULL;
105    ggc_free (bb);
106 }
107 
108 /* Free the memory associated with the CFG in FN.  */
109 
110 void
free_cfg(struct function * fn)111 free_cfg (struct function *fn)
112 {
113   edge e;
114   edge_iterator ei;
115   basic_block next;
116 
117   for (basic_block bb = ENTRY_BLOCK_PTR_FOR_FN (fn); bb; bb = next)
118     {
119       next = bb->next_bb;
120       FOR_EACH_EDGE (e, ei, bb->succs)
121 	free_edge (fn, e);
122       free_block (bb);
123     }
124 
125   gcc_assert (!n_edges_for_fn (fn));
126   /* Sanity check that dominance tree is freed.  */
127   gcc_assert (!fn->cfg->x_dom_computed[0] && !fn->cfg->x_dom_computed[1]);
128 
129   vec_free (fn->cfg->x_label_to_block_map);
130   vec_free (basic_block_info_for_fn (fn));
131   ggc_free (fn->cfg);
132   fn->cfg = NULL;
133 }
134 
135 /* Allocate memory for basic_block.  */
136 
137 basic_block
alloc_block(void)138 alloc_block (void)
139 {
140   basic_block bb;
141   bb = ggc_cleared_alloc<basic_block_def> ();
142   bb->count = profile_count::uninitialized ();
143   return bb;
144 }
145 
146 /* Link block B to chain after AFTER.  */
147 void
link_block(basic_block b,basic_block after)148 link_block (basic_block b, basic_block after)
149 {
150   b->next_bb = after->next_bb;
151   b->prev_bb = after;
152   after->next_bb = b;
153   b->next_bb->prev_bb = b;
154 }
155 
156 /* Unlink block B from chain.  */
157 void
unlink_block(basic_block b)158 unlink_block (basic_block b)
159 {
160   b->next_bb->prev_bb = b->prev_bb;
161   b->prev_bb->next_bb = b->next_bb;
162   b->prev_bb = NULL;
163   b->next_bb = NULL;
164 }
165 
166 /* Sequentially order blocks and compact the arrays.  */
167 void
compact_blocks(void)168 compact_blocks (void)
169 {
170   int i;
171 
172   SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
173   SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
174 
175   if (df)
176     df_compact_blocks ();
177   else
178     {
179       basic_block bb;
180 
181       i = NUM_FIXED_BLOCKS;
182       FOR_EACH_BB_FN (bb, cfun)
183 	{
184 	  SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
185 	  bb->index = i;
186 	  i++;
187 	}
188       gcc_assert (i == n_basic_blocks_for_fn (cfun));
189 
190       for (; i < last_basic_block_for_fn (cfun); i++)
191 	SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
192     }
193   last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
194 }
195 
196 /* Remove block B from the basic block array.  */
197 
198 void
expunge_block(basic_block b)199 expunge_block (basic_block b)
200 {
201   unlink_block (b);
202   SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
203   n_basic_blocks_for_fn (cfun)--;
204   /* We should be able to ggc_free here, but we are not.
205      The dead SSA_NAMES are left pointing to dead statements that are pointing
206      to dead basic blocks making garbage collector to die.
207      We should be able to release all dead SSA_NAMES and at the same time we
208      should clear out BB pointer of dead statements consistently.  */
209 }
210 
211 /* Connect E to E->src.  */
212 
213 static inline void
connect_src(edge e)214 connect_src (edge e)
215 {
216   vec_safe_push (e->src->succs, e);
217   df_mark_solutions_dirty ();
218 }
219 
220 /* Connect E to E->dest.  */
221 
222 static inline void
connect_dest(edge e)223 connect_dest (edge e)
224 {
225   basic_block dest = e->dest;
226   vec_safe_push (dest->preds, e);
227   e->dest_idx = EDGE_COUNT (dest->preds) - 1;
228   df_mark_solutions_dirty ();
229 }
230 
231 /* Disconnect edge E from E->src.  */
232 
233 static inline void
disconnect_src(edge e)234 disconnect_src (edge e)
235 {
236   basic_block src = e->src;
237   edge_iterator ei;
238   edge tmp;
239 
240   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
241     {
242       if (tmp == e)
243 	{
244 	  src->succs->unordered_remove (ei.index);
245 	  df_mark_solutions_dirty ();
246 	  return;
247 	}
248       else
249 	ei_next (&ei);
250     }
251 
252   gcc_unreachable ();
253 }
254 
255 /* Disconnect edge E from E->dest.  */
256 
257 static inline void
disconnect_dest(edge e)258 disconnect_dest (edge e)
259 {
260   basic_block dest = e->dest;
261   unsigned int dest_idx = e->dest_idx;
262 
263   dest->preds->unordered_remove (dest_idx);
264 
265   /* If we removed an edge in the middle of the edge vector, we need
266      to update dest_idx of the edge that moved into the "hole".  */
267   if (dest_idx < EDGE_COUNT (dest->preds))
268     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
269   df_mark_solutions_dirty ();
270 }
271 
272 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
273    created edge.  Use this only if you are sure that this edge can't
274    possibly already exist.  */
275 
276 edge
unchecked_make_edge(basic_block src,basic_block dst,int flags)277 unchecked_make_edge (basic_block src, basic_block dst, int flags)
278 {
279   edge e;
280   e = ggc_cleared_alloc<edge_def> ();
281   n_edges_for_fn (cfun)++;
282 
283   e->probability = profile_probability::uninitialized ();
284   e->src = src;
285   e->dest = dst;
286   e->flags = flags;
287 
288   connect_src (e);
289   connect_dest (e);
290 
291   execute_on_growing_pred (e);
292   return e;
293 }
294 
295 /* Create an edge connecting SRC and DST with FLAGS optionally using
296    edge cache CACHE.  Return the new edge, NULL if already exist.  */
297 
298 edge
cached_make_edge(sbitmap edge_cache,basic_block src,basic_block dst,int flags)299 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
300 {
301   if (edge_cache == NULL
302       || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
303       || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
304     return make_edge (src, dst, flags);
305 
306   /* Does the requested edge already exist?  */
307   if (! bitmap_bit_p (edge_cache, dst->index))
308     {
309       /* The edge does not exist.  Create one and update the
310 	 cache.  */
311       bitmap_set_bit (edge_cache, dst->index);
312       return unchecked_make_edge (src, dst, flags);
313     }
314 
315   /* At this point, we know that the requested edge exists.  Adjust
316      flags if necessary.  */
317   if (flags)
318     {
319       edge e = find_edge (src, dst);
320       e->flags |= flags;
321     }
322 
323   return NULL;
324 }
325 
326 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
327    created edge or NULL if already exist.  */
328 
329 edge
make_edge(basic_block src,basic_block dest,int flags)330 make_edge (basic_block src, basic_block dest, int flags)
331 {
332   edge e = find_edge (src, dest);
333 
334   /* Make sure we don't add duplicate edges.  */
335   if (e)
336     {
337       e->flags |= flags;
338       return NULL;
339     }
340 
341   return unchecked_make_edge (src, dest, flags);
342 }
343 
344 /* Create an edge connecting SRC to DEST and set probability by knowing
345    that it is the single edge leaving SRC.  */
346 
347 edge
make_single_succ_edge(basic_block src,basic_block dest,int flags)348 make_single_succ_edge (basic_block src, basic_block dest, int flags)
349 {
350   edge e = make_edge (src, dest, flags);
351 
352   e->probability = profile_probability::always ();
353   return e;
354 }
355 
356 /* This function will remove an edge from the flow graph.  */
357 
358 void
remove_edge_raw(edge e)359 remove_edge_raw (edge e)
360 {
361   remove_predictions_associated_with_edge (e);
362   execute_on_shrinking_pred (e);
363 
364   disconnect_src (e);
365   disconnect_dest (e);
366 
367   free_edge (cfun, e);
368 }
369 
370 /* Redirect an edge's successor from one block to another.  */
371 
372 void
redirect_edge_succ(edge e,basic_block new_succ)373 redirect_edge_succ (edge e, basic_block new_succ)
374 {
375   execute_on_shrinking_pred (e);
376 
377   disconnect_dest (e);
378 
379   e->dest = new_succ;
380 
381   /* Reconnect the edge to the new successor block.  */
382   connect_dest (e);
383 
384   execute_on_growing_pred (e);
385 }
386 
387 /* Redirect an edge's predecessor from one block to another.  */
388 
389 void
redirect_edge_pred(edge e,basic_block new_pred)390 redirect_edge_pred (edge e, basic_block new_pred)
391 {
392   disconnect_src (e);
393 
394   e->src = new_pred;
395 
396   /* Reconnect the edge to the new predecessor block.  */
397   connect_src (e);
398 }
399 
400 /* Clear all basic block flags that do not have to be preserved.  */
401 void
clear_bb_flags(void)402 clear_bb_flags (void)
403 {
404   basic_block bb;
405   int flags_to_preserve = BB_FLAGS_TO_PRESERVE;
406   if (current_loops
407       && loops_state_satisfies_p (cfun, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
408     flags_to_preserve |= BB_IRREDUCIBLE_LOOP;
409 
410   FOR_ALL_BB_FN (bb, cfun)
411     bb->flags &= flags_to_preserve;
412 }
413 
414 /* Check the consistency of profile information.  We can't do that
415    in verify_flow_info, as the counts may get invalid for incompletely
416    solved graphs, later eliminating of conditionals or roundoff errors.
417    It is still practical to have them reported for debugging of simple
418    testcases.  */
419 static void
check_bb_profile(basic_block bb,FILE * file,int indent)420 check_bb_profile (basic_block bb, FILE * file, int indent)
421 {
422   edge e;
423   edge_iterator ei;
424   struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
425   char *s_indent = (char *) alloca ((size_t) indent + 1);
426   memset ((void *) s_indent, ' ', (size_t) indent);
427   s_indent[indent] = '\0';
428 
429   if (profile_status_for_fn (fun) == PROFILE_ABSENT)
430     return;
431 
432   if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
433     {
434       bool found = false;
435       profile_probability sum = profile_probability::never ();
436       int isum = 0;
437 
438       FOR_EACH_EDGE (e, ei, bb->succs)
439 	{
440 	  if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
441 	    found = true;
442 	  sum += e->probability;
443 	  if (e->probability.initialized_p ())
444 	    isum += e->probability.to_reg_br_prob_base ();
445 	}
446       /* Only report mismatches for non-EH control flow. If there are only EH
447 	 edges it means that the BB ends by noreturn call.  Here the control
448 	 flow may just terminate.  */
449       if (found)
450 	{
451 	  if (sum.differs_from_p (profile_probability::always ()))
452 	    {
453 	      fprintf (file,
454 		       ";; %sInvalid sum of outgoing probabilities ",
455 		       s_indent);
456 	      sum.dump (file);
457 	      fprintf (file, "\n");
458 	    }
459 	  /* Probabilities caps to 100% and thus the previous test will never
460 	     fire if the sum of probabilities is too large.  */
461 	  else if (isum > REG_BR_PROB_BASE + 100)
462 	    {
463 	      fprintf (file,
464 		       ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
465 		       s_indent, isum * 100.0 / REG_BR_PROB_BASE);
466 	    }
467 	}
468     }
469   if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
470     {
471       profile_count sum = profile_count::zero ();
472       FOR_EACH_EDGE (e, ei, bb->preds)
473 	sum += e->count ();
474       if (sum.differs_from_p (bb->count))
475 	{
476 	  fprintf (file, ";; %sInvalid sum of incoming counts ",
477 		   s_indent);
478 	  sum.dump (file);
479 	  fprintf (file, ", should be ");
480 	  bb->count.dump (file);
481 	  fprintf (file, "\n");
482 	}
483     }
484   if (BB_PARTITION (bb) == BB_COLD_PARTITION)
485     {
486       /* Warn about inconsistencies in the partitioning that are
487          currently caused by profile insanities created via optimization.  */
488       if (!probably_never_executed_bb_p (fun, bb))
489 	fprintf (file, ";; %sBlock in cold partition with hot count\n",
490 		 s_indent);
491       FOR_EACH_EDGE (e, ei, bb->preds)
492         {
493           if (!probably_never_executed_edge_p (fun, e))
494             fprintf (file,
495 		     ";; %sBlock in cold partition with incoming hot edge\n",
496 		     s_indent);
497         }
498     }
499 }
500 
501 void
dump_edge_info(FILE * file,edge e,dump_flags_t flags,int do_succ)502 dump_edge_info (FILE *file, edge e, dump_flags_t flags, int do_succ)
503 {
504   basic_block side = (do_succ ? e->dest : e->src);
505   bool do_details = false;
506 
507   if ((flags & TDF_DETAILS) != 0
508       && (flags & TDF_SLIM) == 0)
509     do_details = true;
510 
511   if (side->index == ENTRY_BLOCK)
512     fputs (" ENTRY", file);
513   else if (side->index == EXIT_BLOCK)
514     fputs (" EXIT", file);
515   else
516     fprintf (file, " %d", side->index);
517 
518   if (e->probability.initialized_p () && do_details)
519     {
520       fprintf (file, " [");
521       e->probability.dump (file);
522       fprintf (file, "] ");
523     }
524 
525   if (e->count ().initialized_p () && do_details)
526     {
527       fputs (" count:", file);
528       e->count ().dump (file);
529     }
530 
531   if (e->flags && do_details)
532     {
533       static const char * const bitnames[] =
534 	{
535 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
536 #include "cfg-flags.def"
537 	  NULL
538 #undef DEF_EDGE_FLAG
539 	};
540       bool comma = false;
541       int i, flags = e->flags;
542 
543       gcc_assert (e->flags <= EDGE_ALL_FLAGS);
544       fputs (" (", file);
545       for (i = 0; flags; i++)
546 	if (flags & (1 << i))
547 	  {
548 	    flags &= ~(1 << i);
549 
550 	    if (comma)
551 	      fputc (',', file);
552 	    fputs (bitnames[i], file);
553 	    comma = true;
554 	  }
555 
556       fputc (')', file);
557     }
558 
559   if (do_details && LOCATION_LOCUS (e->goto_locus) > BUILTINS_LOCATION)
560     fprintf (file, " %s:%d:%d", LOCATION_FILE (e->goto_locus),
561 	     LOCATION_LINE (e->goto_locus), LOCATION_COLUMN (e->goto_locus));
562 }
563 
564 DEBUG_FUNCTION void
debug(edge_def & ref)565 debug (edge_def &ref)
566 {
567   fprintf (stderr, "<edge (%d -> %d)>\n",
568 	   ref.src->index, ref.dest->index);
569   dump_edge_info (stderr, &ref, TDF_DETAILS, false);
570   fprintf (stderr, "\n");
571 }
572 
573 DEBUG_FUNCTION void
debug(edge_def * ptr)574 debug (edge_def *ptr)
575 {
576   if (ptr)
577     debug (*ptr);
578   else
579     fprintf (stderr, "<nil>\n");
580 }
581 
582 static void
debug_slim(edge e)583 debug_slim (edge e)
584 {
585   fprintf (stderr, "<edge 0x%p (%d -> %d)>", (void *) e,
586 	   e->src->index, e->dest->index);
587 }
588 
589 DEFINE_DEBUG_VEC (edge)
590 DEFINE_DEBUG_HASH_SET (edge)
591 
592 /* Simple routines to easily allocate AUX fields of basic blocks.  */
593 
594 static struct obstack block_aux_obstack;
595 static void *first_block_aux_obj = 0;
596 static struct obstack edge_aux_obstack;
597 static void *first_edge_aux_obj = 0;
598 
599 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
600    be first initialized by alloc_aux_for_blocks.  */
601 
602 static void
alloc_aux_for_block(basic_block bb,int size)603 alloc_aux_for_block (basic_block bb, int size)
604 {
605   /* Verify that aux field is clear.  */
606   gcc_assert (!bb->aux && first_block_aux_obj);
607   bb->aux = obstack_alloc (&block_aux_obstack, size);
608   memset (bb->aux, 0, size);
609 }
610 
611 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
612    alloc_aux_for_block for each basic block.  */
613 
614 void
alloc_aux_for_blocks(int size)615 alloc_aux_for_blocks (int size)
616 {
617   static int initialized;
618 
619   if (!initialized)
620     {
621       gcc_obstack_init (&block_aux_obstack);
622       initialized = 1;
623     }
624   else
625     /* Check whether AUX data are still allocated.  */
626     gcc_assert (!first_block_aux_obj);
627 
628   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
629   if (size)
630     {
631       basic_block bb;
632 
633       FOR_ALL_BB_FN (bb, cfun)
634 	alloc_aux_for_block (bb, size);
635     }
636 }
637 
638 /* Clear AUX pointers of all blocks.  */
639 
640 void
clear_aux_for_blocks(void)641 clear_aux_for_blocks (void)
642 {
643   basic_block bb;
644 
645   FOR_ALL_BB_FN (bb, cfun)
646     bb->aux = NULL;
647 }
648 
649 /* Free data allocated in block_aux_obstack and clear AUX pointers
650    of all blocks.  */
651 
652 void
free_aux_for_blocks(void)653 free_aux_for_blocks (void)
654 {
655   gcc_assert (first_block_aux_obj);
656   obstack_free (&block_aux_obstack, first_block_aux_obj);
657   first_block_aux_obj = NULL;
658 
659   clear_aux_for_blocks ();
660 }
661 
662 /* Allocate a memory edge of SIZE as E->aux.  The obstack must
663    be first initialized by alloc_aux_for_edges.  */
664 
665 void
alloc_aux_for_edge(edge e,int size)666 alloc_aux_for_edge (edge e, int size)
667 {
668   /* Verify that aux field is clear.  */
669   gcc_assert (!e->aux && first_edge_aux_obj);
670   e->aux = obstack_alloc (&edge_aux_obstack, size);
671   memset (e->aux, 0, size);
672 }
673 
674 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
675    alloc_aux_for_edge for each basic edge.  */
676 
677 void
alloc_aux_for_edges(int size)678 alloc_aux_for_edges (int size)
679 {
680   static int initialized;
681 
682   if (!initialized)
683     {
684       gcc_obstack_init (&edge_aux_obstack);
685       initialized = 1;
686     }
687   else
688     /* Check whether AUX data are still allocated.  */
689     gcc_assert (!first_edge_aux_obj);
690 
691   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
692   if (size)
693     {
694       basic_block bb;
695 
696       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
697 		      EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
698 	{
699 	  edge e;
700 	  edge_iterator ei;
701 
702 	  FOR_EACH_EDGE (e, ei, bb->succs)
703 	    alloc_aux_for_edge (e, size);
704 	}
705     }
706 }
707 
708 /* Clear AUX pointers of all edges.  */
709 
710 void
clear_aux_for_edges(void)711 clear_aux_for_edges (void)
712 {
713   basic_block bb;
714   edge e;
715 
716   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
717 		  EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
718     {
719       edge_iterator ei;
720       FOR_EACH_EDGE (e, ei, bb->succs)
721 	e->aux = NULL;
722     }
723 }
724 
725 /* Free data allocated in edge_aux_obstack and clear AUX pointers
726    of all edges.  */
727 
728 void
free_aux_for_edges(void)729 free_aux_for_edges (void)
730 {
731   gcc_assert (first_edge_aux_obj);
732   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
733   first_edge_aux_obj = NULL;
734 
735   clear_aux_for_edges ();
736 }
737 
738 DEBUG_FUNCTION void
debug_bb(basic_block bb)739 debug_bb (basic_block bb)
740 {
741   debug_bb (bb, dump_flags);
742 }
743 
744 DEBUG_FUNCTION basic_block
debug_bb_n(int n)745 debug_bb_n (int n)
746 {
747   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
748   debug_bb (bb);
749   return bb;
750 }
751 
752 /* Print BB with specified FLAGS.  */
753 
754 DEBUG_FUNCTION void
debug_bb(basic_block bb,dump_flags_t flags)755 debug_bb (basic_block bb, dump_flags_t flags)
756 {
757   dump_bb (stderr, bb, 0, flags);
758 }
759 
760 /* Print basic block numbered N with specified FLAGS.  */
761 
762 DEBUG_FUNCTION basic_block
debug_bb_n(int n,dump_flags_t flags)763 debug_bb_n (int n, dump_flags_t flags)
764 {
765   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
766   debug_bb (bb, flags);
767   return bb;
768 }
769 
770 /* Dumps cfg related information about basic block BB to OUTF.
771    If HEADER is true, dump things that appear before the instructions
772    contained in BB.  If FOOTER is true, dump things that appear after.
773    Flags are the TDF_* masks as documented in dumpfile.h.
774    NB: With TDF_DETAILS, it is assumed that cfun is available, so
775    that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.  */
776 
777 void
dump_bb_info(FILE * outf,basic_block bb,int indent,dump_flags_t flags,bool do_header,bool do_footer)778 dump_bb_info (FILE *outf, basic_block bb, int indent, dump_flags_t flags,
779 	      bool do_header, bool do_footer)
780 {
781   edge_iterator ei;
782   edge e;
783   static const char * const bb_bitnames[] =
784     {
785 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
786 #include "cfg-flags.def"
787       NULL
788 #undef DEF_BASIC_BLOCK_FLAG
789     };
790   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
791   bool first;
792   char *s_indent = (char *) alloca ((size_t) indent + 1);
793   memset ((void *) s_indent, ' ', (size_t) indent);
794   s_indent[indent] = '\0';
795 
796   gcc_assert (bb->flags <= BB_ALL_FLAGS);
797 
798   if (do_header)
799     {
800       unsigned i;
801 
802       fputs (";; ", outf);
803       fprintf (outf, "%sbasic block %d, loop depth %d",
804 	       s_indent, bb->index, bb_loop_depth (bb));
805       if (flags & TDF_DETAILS)
806 	{
807 	  struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
808 	  if (bb->count.initialized_p ())
809 	    {
810 	      fputs (", count ", outf);
811 	      bb->count.dump (outf);
812 	    }
813 	  if (maybe_hot_bb_p (fun, bb))
814 	    fputs (", maybe hot", outf);
815 	  if (probably_never_executed_bb_p (fun, bb))
816 	    fputs (", probably never executed", outf);
817 	}
818       fputc ('\n', outf);
819 
820       if (flags & TDF_DETAILS)
821 	{
822 	  check_bb_profile (bb, outf, indent);
823 	  fputs (";; ", outf);
824 	  fprintf (outf, "%s prev block ", s_indent);
825 	  if (bb->prev_bb)
826 	    fprintf (outf, "%d", bb->prev_bb->index);
827 	  else
828 	    fprintf (outf, "(nil)");
829 	  fprintf (outf, ", next block ");
830 	  if (bb->next_bb)
831 	    fprintf (outf, "%d", bb->next_bb->index);
832 	  else
833 	    fprintf (outf, "(nil)");
834 
835 	  fputs (", flags:", outf);
836 	  first = true;
837 	  for (i = 0; i < n_bitnames; i++)
838 	    if (bb->flags & (1 << i))
839 	      {
840 		if (first)
841 		  fputs (" (", outf);
842 		else
843 		  fputs (", ", outf);
844 		first = false;
845 		fputs (bb_bitnames[i], outf);
846 	      }
847 	  if (!first)
848 	    fputc (')', outf);
849 	  fputc ('\n', outf);
850 	}
851 
852       fputs (";; ", outf);
853       fprintf (outf, "%s pred:      ", s_indent);
854       first = true;
855       FOR_EACH_EDGE (e, ei, bb->preds)
856 	{
857 	  if (! first)
858 	    {
859 	      fputs (";; ", outf);
860 	      fprintf (outf, "%s            ", s_indent);
861 	    }
862 	  first = false;
863 	  dump_edge_info (outf, e, flags, 0);
864 	  fputc ('\n', outf);
865 	}
866       if (first)
867 	fputc ('\n', outf);
868     }
869 
870   if (do_footer)
871     {
872       fputs (";; ", outf);
873       fprintf (outf, "%s succ:      ", s_indent);
874       first = true;
875       FOR_EACH_EDGE (e, ei, bb->succs)
876         {
877 	  if (! first)
878 	    {
879 	      fputs (";; ", outf);
880 	      fprintf (outf, "%s            ", s_indent);
881 	    }
882 	  first = false;
883 	  dump_edge_info (outf, e, flags, 1);
884 	  fputc ('\n', outf);
885 	}
886       if (first)
887 	fputc ('\n', outf);
888     }
889 }
890 
891 /* Dumps a brief description of cfg to FILE.  */
892 
893 void
brief_dump_cfg(FILE * file,dump_flags_t flags)894 brief_dump_cfg (FILE *file, dump_flags_t flags)
895 {
896   basic_block bb;
897 
898   FOR_EACH_BB_FN (bb, cfun)
899     {
900       dump_bb_info (file, bb, 0, flags & TDF_DETAILS, true, true);
901     }
902 }
903 
904 /* An edge originally destinating BB of COUNT has been proved to
905    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
906    redirected to destination of TAKEN_EDGE.
907 
908    This function may leave the profile inconsistent in the case TAKEN_EDGE
909    frequency or count is believed to be lower than COUNT
910    respectively.  */
911 void
update_bb_profile_for_threading(basic_block bb,profile_count count,edge taken_edge)912 update_bb_profile_for_threading (basic_block bb,
913 				 profile_count count, edge taken_edge)
914 {
915   edge c;
916   profile_probability prob;
917   edge_iterator ei;
918 
919   if (bb->count < count)
920     {
921       if (dump_file)
922 	fprintf (dump_file, "bb %i count became negative after threading",
923 		 bb->index);
924     }
925   bb->count -= count;
926 
927   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
928      Watch for overflows.  */
929   if (bb->count.nonzero_p ())
930     prob = count.probability_in (bb->count);
931   else
932     prob = profile_probability::never ();
933   if (prob > taken_edge->probability)
934     {
935       if (dump_file)
936 	{
937 	  fprintf (dump_file, "Jump threading proved probability of edge "
938 		   "%i->%i too small (it is ",
939 		   taken_edge->src->index, taken_edge->dest->index);
940 	  taken_edge->probability.dump (dump_file);
941 	  fprintf (dump_file, " should be ");
942 	  prob.dump (dump_file);
943 	  fprintf (dump_file, ")\n");
944 	}
945       prob = taken_edge->probability.apply_scale (6, 8);
946     }
947 
948   /* Now rescale the probabilities.  */
949   taken_edge->probability -= prob;
950   prob = prob.invert ();
951   if (prob == profile_probability::never ())
952     {
953       if (dump_file)
954 	fprintf (dump_file, "Edge probabilities of bb %i has been reset, "
955 		 "count of block should end up being 0, it is non-zero\n",
956 		 bb->index);
957       EDGE_SUCC (bb, 0)->probability = profile_probability::guessed_always ();
958       ei = ei_start (bb->succs);
959       ei_next (&ei);
960       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
961 	c->probability = profile_probability::guessed_never ();
962     }
963   else if (!(prob == profile_probability::always ()))
964     {
965       FOR_EACH_EDGE (c, ei, bb->succs)
966 	c->probability /= prob;
967     }
968 
969   gcc_assert (bb == taken_edge->src);
970 }
971 
972 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
973    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
974    function but considerably slower.  */
975 void
scale_bbs_frequencies_profile_count(basic_block * bbs,int nbbs,profile_count num,profile_count den)976 scale_bbs_frequencies_profile_count (basic_block *bbs, int nbbs,
977 				     profile_count num, profile_count den)
978 {
979   int i;
980   if (num == profile_count::zero () || den.nonzero_p ())
981     for (i = 0; i < nbbs; i++)
982       bbs[i]->count = bbs[i]->count.apply_scale (num, den);
983 }
984 
985 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
986    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
987    function but considerably slower.  */
988 void
scale_bbs_frequencies(basic_block * bbs,int nbbs,profile_probability p)989 scale_bbs_frequencies (basic_block *bbs, int nbbs,
990 		       profile_probability p)
991 {
992   int i;
993 
994   for (i = 0; i < nbbs; i++)
995     bbs[i]->count = bbs[i]->count.apply_probability (p);
996 }
997 
998 /* Data structures used to maintain mapping between basic blocks and
999    copies.  */
1000 typedef hash_map<int_hash<int, -1, -2>, int> copy_map_t;
1001 static copy_map_t *bb_original;
1002 static copy_map_t *bb_copy;
1003 
1004 /* And between loops and copies.  */
1005 static copy_map_t *loop_copy;
1006 
1007 /* Initialize the data structures to maintain mapping between blocks
1008    and its copies.  */
1009 void
initialize_original_copy_tables(void)1010 initialize_original_copy_tables (void)
1011 {
1012   bb_original = new copy_map_t (10);
1013   bb_copy = new copy_map_t (10);
1014   loop_copy = new copy_map_t (10);
1015 }
1016 
1017 /* Reset the data structures to maintain mapping between blocks and
1018    its copies.  */
1019 
1020 void
reset_original_copy_tables(void)1021 reset_original_copy_tables (void)
1022 {
1023   bb_original->empty ();
1024   bb_copy->empty ();
1025   loop_copy->empty ();
1026 }
1027 
1028 /* Free the data structures to maintain mapping between blocks and
1029    its copies.  */
1030 void
free_original_copy_tables(void)1031 free_original_copy_tables (void)
1032 {
1033   delete bb_copy;
1034   bb_copy = NULL;
1035   delete bb_original;
1036   bb_original = NULL;
1037   delete loop_copy;
1038   loop_copy = NULL;
1039 }
1040 
1041 /* Return true iff we have had a call to initialize_original_copy_tables
1042    without a corresponding call to free_original_copy_tables.  */
1043 
1044 bool
original_copy_tables_initialized_p(void)1045 original_copy_tables_initialized_p (void)
1046 {
1047   return bb_copy != NULL;
1048 }
1049 
1050 /* Removes the value associated with OBJ from table TAB.  */
1051 
1052 static void
copy_original_table_clear(copy_map_t * tab,unsigned obj)1053 copy_original_table_clear (copy_map_t *tab, unsigned obj)
1054 {
1055   if (!original_copy_tables_initialized_p ())
1056     return;
1057 
1058   tab->remove (obj);
1059 }
1060 
1061 /* Sets the value associated with OBJ in table TAB to VAL.
1062    Do nothing when data structures are not initialized.  */
1063 
1064 static void
copy_original_table_set(copy_map_t * tab,unsigned obj,unsigned val)1065 copy_original_table_set (copy_map_t *tab,
1066 			 unsigned obj, unsigned val)
1067 {
1068   if (!original_copy_tables_initialized_p ())
1069     return;
1070 
1071   tab->put (obj, val);
1072 }
1073 
1074 /* Set original for basic block.  Do nothing when data structures are not
1075    initialized so passes not needing this don't need to care.  */
1076 void
set_bb_original(basic_block bb,basic_block original)1077 set_bb_original (basic_block bb, basic_block original)
1078 {
1079   copy_original_table_set (bb_original, bb->index, original->index);
1080 }
1081 
1082 /* Get the original basic block.  */
1083 basic_block
get_bb_original(basic_block bb)1084 get_bb_original (basic_block bb)
1085 {
1086   gcc_assert (original_copy_tables_initialized_p ());
1087 
1088   int *entry = bb_original->get (bb->index);
1089   if (entry)
1090     return BASIC_BLOCK_FOR_FN (cfun, *entry);
1091   else
1092     return NULL;
1093 }
1094 
1095 /* Set copy for basic block.  Do nothing when data structures are not
1096    initialized so passes not needing this don't need to care.  */
1097 void
set_bb_copy(basic_block bb,basic_block copy)1098 set_bb_copy (basic_block bb, basic_block copy)
1099 {
1100   copy_original_table_set (bb_copy, bb->index, copy->index);
1101 }
1102 
1103 /* Get the copy of basic block.  */
1104 basic_block
get_bb_copy(basic_block bb)1105 get_bb_copy (basic_block bb)
1106 {
1107   gcc_assert (original_copy_tables_initialized_p ());
1108 
1109   int *entry = bb_copy->get (bb->index);
1110   if (entry)
1111     return BASIC_BLOCK_FOR_FN (cfun, *entry);
1112   else
1113     return NULL;
1114 }
1115 
1116 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1117    initialized so passes not needing this don't need to care.  */
1118 
1119 void
set_loop_copy(class loop * loop,class loop * copy)1120 set_loop_copy (class loop *loop, class loop *copy)
1121 {
1122   if (!copy)
1123     copy_original_table_clear (loop_copy, loop->num);
1124   else
1125     copy_original_table_set (loop_copy, loop->num, copy->num);
1126 }
1127 
1128 /* Get the copy of LOOP.  */
1129 
1130 class loop *
get_loop_copy(class loop * loop)1131 get_loop_copy (class loop *loop)
1132 {
1133   gcc_assert (original_copy_tables_initialized_p ());
1134 
1135   int *entry = loop_copy->get (loop->num);
1136   if (entry)
1137     return get_loop (cfun, *entry);
1138   else
1139     return NULL;
1140 }
1141