1 /* Control flow graph building code for GNU compiler.
2    Copyright (C) 1987-2019 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 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "rtl.h"
26 #include "cfghooks.h"
27 #include "memmodel.h"
28 #include "emit-rtl.h"
29 #include "cfgrtl.h"
30 #include "cfganal.h"
31 #include "cfgbuild.h"
32 #include "except.h"
33 #include "stmt.h"
34 
35 static void make_edges (basic_block, basic_block, int);
36 static void make_label_edge (sbitmap, basic_block, rtx, int);
37 static void find_bb_boundaries (basic_block);
38 static void compute_outgoing_frequencies (basic_block);
39 
40 /* Return true if insn is something that should be contained inside basic
41    block.  */
42 
43 bool
inside_basic_block_p(const rtx_insn * insn)44 inside_basic_block_p (const rtx_insn *insn)
45 {
46   switch (GET_CODE (insn))
47     {
48     case CODE_LABEL:
49       /* Avoid creating of basic block for jumptables.  */
50       return (NEXT_INSN (insn) == 0
51 	      || ! JUMP_TABLE_DATA_P (NEXT_INSN (insn)));
52 
53     case JUMP_INSN:
54     case CALL_INSN:
55     case INSN:
56     case DEBUG_INSN:
57       return true;
58 
59     case JUMP_TABLE_DATA:
60     case BARRIER:
61     case NOTE:
62       return false;
63 
64     default:
65       gcc_unreachable ();
66     }
67 }
68 
69 /* Return true if INSN may cause control flow transfer, so it should be last in
70    the basic block.  */
71 
72 bool
control_flow_insn_p(const rtx_insn * insn)73 control_flow_insn_p (const rtx_insn *insn)
74 {
75   switch (GET_CODE (insn))
76     {
77     case NOTE:
78     case CODE_LABEL:
79     case DEBUG_INSN:
80       return false;
81 
82     case JUMP_INSN:
83       return true;
84 
85     case CALL_INSN:
86       /* Noreturn and sibling call instructions terminate the basic blocks
87 	 (but only if they happen unconditionally).  */
88       if ((SIBLING_CALL_P (insn)
89 	   || find_reg_note (insn, REG_NORETURN, 0))
90 	  && GET_CODE (PATTERN (insn)) != COND_EXEC)
91 	return true;
92 
93       /* Call insn may return to the nonlocal goto handler.  */
94       if (can_nonlocal_goto (insn))
95 	return true;
96       break;
97 
98     case INSN:
99       /* Treat trap instructions like noreturn calls (same provision).  */
100       if (GET_CODE (PATTERN (insn)) == TRAP_IF
101 	  && XEXP (PATTERN (insn), 0) == const1_rtx)
102 	return true;
103       if (!cfun->can_throw_non_call_exceptions)
104 	return false;
105       break;
106 
107     case JUMP_TABLE_DATA:
108     case BARRIER:
109       /* It is nonsense to reach this when looking for the
110 	 end of basic block, but before dead code is eliminated
111 	 this may happen.  */
112       return false;
113 
114     default:
115       gcc_unreachable ();
116     }
117 
118   return can_throw_internal (insn);
119 }
120 
121 
122 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
123    about the edge that is accumulated between calls.  */
124 
125 /* Create an edge from a basic block to a label.  */
126 
127 static void
make_label_edge(sbitmap edge_cache,basic_block src,rtx label,int flags)128 make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags)
129 {
130   gcc_assert (LABEL_P (label));
131 
132   /* If the label was never emitted, this insn is junk, but avoid a
133      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
134      as a result of a syntax error and a diagnostic has already been
135      printed.  */
136 
137   if (INSN_UID (label) == 0)
138     return;
139 
140   cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
141 }
142 
143 /* Create the edges generated by INSN in REGION.  */
144 
145 void
rtl_make_eh_edge(sbitmap edge_cache,basic_block src,rtx insn)146 rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn)
147 {
148   eh_landing_pad lp = get_eh_landing_pad_from_rtx (insn);
149 
150   if (lp)
151     {
152       rtx_insn *label = lp->landing_pad;
153 
154       /* During initial rtl generation, use the post_landing_pad.  */
155       if (label == NULL)
156 	{
157 	  gcc_assert (lp->post_landing_pad);
158 	  label = label_rtx (lp->post_landing_pad);
159 	}
160 
161       make_label_edge (edge_cache, src, label,
162 		       EDGE_ABNORMAL | EDGE_EH
163 		       | (CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0));
164     }
165 }
166 
167 /* States of basic block as seen by find_many_sub_basic_blocks.  */
168 enum state {
169   /* Basic blocks created via split_block belong to this state.
170      make_edges will examine these basic blocks to see if we need to
171      create edges going out of them.  */
172   BLOCK_NEW = 0,
173 
174   /* Basic blocks that do not need examining belong to this state.
175      These blocks will be left intact.  In particular, make_edges will
176      not create edges going out of these basic blocks.  */
177   BLOCK_ORIGINAL,
178 
179   /* Basic blocks that may need splitting (due to a label appearing in
180      the middle, etc) belong to this state.  After splitting them,
181      make_edges will create edges going out of them as needed.  */
182   BLOCK_TO_SPLIT
183 };
184 
185 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
186 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
187 
188 /* Used internally by purge_dead_tablejump_edges, ORed into state.  */
189 #define BLOCK_USED_BY_TABLEJUMP		32
190 #define FULL_STATE(BB) ((size_t) (BB)->aux)
191 
192 /* Identify the edges going out of basic blocks between MIN and MAX,
193    inclusive, that have their states set to BLOCK_NEW or
194    BLOCK_TO_SPLIT.
195 
196    UPDATE_P should be nonzero if we are updating CFG and zero if we
197    are building CFG from scratch.  */
198 
199 static void
make_edges(basic_block min,basic_block max,int update_p)200 make_edges (basic_block min, basic_block max, int update_p)
201 {
202   basic_block bb;
203   sbitmap edge_cache = NULL;
204 
205   /* Heavy use of computed goto in machine-generated code can lead to
206      nearly fully-connected CFGs.  In that case we spend a significant
207      amount of time searching the edge lists for duplicates.  */
208   if (!vec_safe_is_empty (forced_labels)
209       || cfun->cfg->max_jumptable_ents > 100)
210     edge_cache = sbitmap_alloc (last_basic_block_for_fn (cfun));
211 
212   /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
213      is always the entry.  */
214   if (min == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
215     make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), min, EDGE_FALLTHRU);
216 
217   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
218     {
219       rtx_insn *insn;
220       enum rtx_code code;
221       edge e;
222       edge_iterator ei;
223 
224       if (STATE (bb) == BLOCK_ORIGINAL)
225 	continue;
226 
227       /* If we have an edge cache, cache edges going out of BB.  */
228       if (edge_cache)
229 	{
230 	  bitmap_clear (edge_cache);
231 	  if (update_p)
232 	    {
233 	      FOR_EACH_EDGE (e, ei, bb->succs)
234 		if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
235 		  bitmap_set_bit (edge_cache, e->dest->index);
236 	    }
237 	}
238 
239       if (LABEL_P (BB_HEAD (bb))
240 	  && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
241 	cached_make_edge (NULL, ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, 0);
242 
243       /* Examine the last instruction of the block, and discover the
244 	 ways we can leave the block.  */
245 
246       insn = BB_END (bb);
247       code = GET_CODE (insn);
248 
249       /* A branch.  */
250       if (code == JUMP_INSN)
251 	{
252 	  rtx tmp;
253 	  rtx_jump_table_data *table;
254 
255 	  /* Recognize a non-local goto as a branch outside the
256 	     current function.  */
257 	  if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
258 	    ;
259 
260 	  /* Recognize a tablejump and do the right thing.  */
261 	  else if (tablejump_p (insn, NULL, &table))
262 	    {
263 	      rtvec vec = table->get_labels ();
264 	      int j;
265 
266 	      for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
267 		make_label_edge (edge_cache, bb,
268 				 XEXP (RTVEC_ELT (vec, j), 0), 0);
269 
270 	      /* Some targets (eg, ARM) emit a conditional jump that also
271 		 contains the out-of-range target.  Scan for these and
272 		 add an edge if necessary.  */
273 	      if ((tmp = single_set (insn)) != NULL
274 		  && SET_DEST (tmp) == pc_rtx
275 		  && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
276 		  && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
277 		make_label_edge (edge_cache, bb,
278 				 label_ref_label (XEXP (SET_SRC (tmp), 2)), 0);
279 	    }
280 
281 	  /* If this is a computed jump, then mark it as reaching
282 	     everything on the forced_labels list.  */
283 	  else if (computed_jump_p (insn))
284 	    {
285 	      rtx_insn *insn;
286 	      unsigned int i;
287 	      FOR_EACH_VEC_SAFE_ELT (forced_labels, i, insn)
288 		make_label_edge (edge_cache, bb, insn, EDGE_ABNORMAL);
289 	    }
290 
291 	  /* Returns create an exit out.  */
292 	  else if (returnjump_p (insn))
293 	    cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
294 
295 	  /* Recognize asm goto and do the right thing.  */
296 	  else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
297 	    {
298 	      int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
299 	      for (i = 0; i < n; ++i)
300 		make_label_edge (edge_cache, bb,
301 				 XEXP (ASM_OPERANDS_LABEL (tmp, i), 0), 0);
302 	    }
303 
304 	  /* Otherwise, we have a plain conditional or unconditional jump.  */
305 	  else
306 	    {
307 	      gcc_assert (JUMP_LABEL (insn));
308 	      make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
309 	    }
310 	}
311 
312       /* If this is a sibling call insn, then this is in effect a combined call
313 	 and return, and so we need an edge to the exit block.  No need to
314 	 worry about EH edges, since we wouldn't have created the sibling call
315 	 in the first place.  */
316       if (code == CALL_INSN && SIBLING_CALL_P (insn))
317 	cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun),
318 			  EDGE_SIBCALL | EDGE_ABNORMAL);
319 
320       /* If this is a CALL_INSN, then mark it as reaching the active EH
321 	 handler for this CALL_INSN.  If we're handling non-call
322 	 exceptions then any insn can reach any of the active handlers.
323 	 Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
324       else if (code == CALL_INSN || cfun->can_throw_non_call_exceptions)
325 	{
326 	  /* Add any appropriate EH edges.  */
327 	  rtl_make_eh_edge (edge_cache, bb, insn);
328 
329 	  if (code == CALL_INSN)
330 	    {
331 	      if (can_nonlocal_goto (insn))
332 		{
333 		  /* ??? This could be made smarter: in some cases it's
334 		     possible to tell that certain calls will not do a
335 		     nonlocal goto.  For example, if the nested functions
336 		     that do the nonlocal gotos do not have their addresses
337 		     taken, then only calls to those functions or to other
338 		     nested functions that use them could possibly do
339 		     nonlocal gotos.  */
340 		  for (rtx_insn_list *x = nonlocal_goto_handler_labels;
341 		       x;
342 		       x = x->next ())
343 		    make_label_edge (edge_cache, bb, x->insn (),
344 				     EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
345 		}
346 
347 	      if (flag_tm)
348 		{
349 		  rtx note;
350 		  for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
351 		    if (REG_NOTE_KIND (note) == REG_TM)
352 		      make_label_edge (edge_cache, bb, XEXP (note, 0),
353 				       EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
354 		}
355 	    }
356 	}
357 
358       /* Find out if we can drop through to the next block.  */
359       insn = NEXT_INSN (insn);
360       e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
361       if (e && e->flags & EDGE_FALLTHRU)
362 	insn = NULL;
363 
364       while (insn
365 	     && NOTE_P (insn)
366 	     && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
367 	insn = NEXT_INSN (insn);
368 
369       if (!insn)
370 	cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun),
371 			  EDGE_FALLTHRU);
372       else if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
373 	{
374 	  if (insn == BB_HEAD (bb->next_bb))
375 	    cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
376 	}
377     }
378 
379   if (edge_cache)
380     sbitmap_free (edge_cache);
381 }
382 
383 static void
mark_tablejump_edge(rtx label)384 mark_tablejump_edge (rtx label)
385 {
386   basic_block bb;
387 
388   gcc_assert (LABEL_P (label));
389   /* See comment in make_label_edge.  */
390   if (INSN_UID (label) == 0)
391     return;
392   bb = BLOCK_FOR_INSN (label);
393   SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
394 }
395 
396 static void
purge_dead_tablejump_edges(basic_block bb,rtx_jump_table_data * table)397 purge_dead_tablejump_edges (basic_block bb, rtx_jump_table_data *table)
398 {
399   rtx_insn *insn = BB_END (bb);
400   rtx tmp;
401   rtvec vec;
402   int j;
403   edge_iterator ei;
404   edge e;
405 
406   vec = table->get_labels ();
407 
408   for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
409     mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
410 
411   /* Some targets (eg, ARM) emit a conditional jump that also
412      contains the out-of-range target.  Scan for these and
413      add an edge if necessary.  */
414   if ((tmp = single_set (insn)) != NULL
415        && SET_DEST (tmp) == pc_rtx
416        && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
417        && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
418     mark_tablejump_edge (label_ref_label (XEXP (SET_SRC (tmp), 2)));
419 
420   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
421     {
422       if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
423 	SET_STATE (e->dest, FULL_STATE (e->dest)
424 			    & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
425       else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
426 	{
427 	  remove_edge (e);
428 	  continue;
429 	}
430       ei_next (&ei);
431     }
432 }
433 
434 /* Scan basic block BB for possible BB boundaries inside the block
435    and create new basic blocks in the progress.  */
436 
437 static void
find_bb_boundaries(basic_block bb)438 find_bb_boundaries (basic_block bb)
439 {
440   basic_block orig_bb = bb;
441   rtx_insn *insn = BB_HEAD (bb);
442   rtx_insn *end = BB_END (bb), *x;
443   rtx_jump_table_data *table;
444   rtx_insn *flow_transfer_insn = NULL;
445   rtx_insn *debug_insn = NULL;
446   edge fallthru = NULL;
447   bool skip_purge;
448 
449   if (insn == end)
450     return;
451 
452   if (DEBUG_INSN_P (insn) || DEBUG_INSN_P (end))
453     {
454       /* Check whether, without debug insns, the insn==end test above
455 	 would have caused us to return immediately, and behave the
456 	 same way even with debug insns.  If we don't do this, debug
457 	 insns could cause us to purge dead edges at different times,
458 	 which could in turn change the cfg and affect codegen
459 	 decisions in subtle but undesirable ways.  */
460       while (insn != end && DEBUG_INSN_P (insn))
461 	insn = NEXT_INSN (insn);
462       rtx_insn *e = end;
463       while (insn != e && DEBUG_INSN_P (e))
464 	e = PREV_INSN (e);
465       if (insn == e)
466 	{
467 	  /* If there are debug insns after a single insn that is a
468 	     control flow insn in the block, we'd have left right
469 	     away, but we should clean up the debug insns after the
470 	     control flow insn, because they can't remain in the same
471 	     block.  So, do the debug insn cleaning up, but then bail
472 	     out without purging dead edges as we would if the debug
473 	     insns hadn't been there.  */
474 	  if (e != end && !DEBUG_INSN_P (e) && control_flow_insn_p (e))
475 	    {
476 	      skip_purge = true;
477 	      flow_transfer_insn = e;
478 	      goto clean_up_debug_after_control_flow;
479 	    }
480 	  return;
481 	}
482     }
483 
484   if (LABEL_P (insn))
485     insn = NEXT_INSN (insn);
486 
487   /* Scan insn chain and try to find new basic block boundaries.  */
488   while (1)
489     {
490       enum rtx_code code = GET_CODE (insn);
491 
492       if (code == DEBUG_INSN)
493 	{
494 	  if (flow_transfer_insn && !debug_insn)
495 	    debug_insn = insn;
496 	}
497       /* In case we've previously seen an insn that effects a control
498 	 flow transfer, split the block.  */
499       else if ((flow_transfer_insn || code == CODE_LABEL)
500 	       && inside_basic_block_p (insn))
501 	{
502 	  rtx_insn *prev = PREV_INSN (insn);
503 
504 	  /* If the first non-debug inside_basic_block_p insn after a control
505 	     flow transfer is not a label, split the block before the debug
506 	     insn instead of before the non-debug insn, so that the debug
507 	     insns are not lost.  */
508 	  if (debug_insn && code != CODE_LABEL && code != BARRIER)
509 	    prev = PREV_INSN (debug_insn);
510 	  fallthru = split_block (bb, prev);
511 	  if (flow_transfer_insn)
512 	    {
513 	      BB_END (bb) = flow_transfer_insn;
514 
515 	      rtx_insn *next;
516 	      /* Clean up the bb field for the insns between the blocks.  */
517 	      for (x = NEXT_INSN (flow_transfer_insn);
518 		   x != BB_HEAD (fallthru->dest);
519 		   x = next)
520 		{
521 		  next = NEXT_INSN (x);
522 		  /* Debug insns should not be in between basic blocks,
523 		     drop them on the floor.  */
524 		  if (DEBUG_INSN_P (x))
525 		    delete_insn (x);
526 		  else if (!BARRIER_P (x))
527 		    set_block_for_insn (x, NULL);
528 		}
529 	    }
530 
531 	  bb = fallthru->dest;
532 	  remove_edge (fallthru);
533 	  /* BB is unreachable at this point - we need to determine its profile
534 	     once edges are built.  */
535 	  bb->count = profile_count::uninitialized ();
536 	  flow_transfer_insn = NULL;
537 	  debug_insn = NULL;
538 	  if (code == CODE_LABEL && LABEL_ALT_ENTRY_P (insn))
539 	    make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, 0);
540 	}
541       else if (code == BARRIER)
542 	{
543 	  /* __builtin_unreachable () may cause a barrier to be emitted in
544 	     the middle of a BB.  We need to split it in the same manner as
545 	     if the barrier were preceded by a control_flow_insn_p insn.  */
546 	  if (!flow_transfer_insn)
547 	    flow_transfer_insn = prev_nonnote_nondebug_insn_bb (insn);
548 	  debug_insn = NULL;
549 	}
550 
551       if (control_flow_insn_p (insn))
552 	flow_transfer_insn = insn;
553       if (insn == end)
554 	break;
555       insn = NEXT_INSN (insn);
556     }
557 
558   /* In case expander replaced normal insn by sequence terminating by
559      return and barrier, or possibly other sequence not behaving like
560      ordinary jump, we need to take care and move basic block boundary.  */
561   if (flow_transfer_insn && flow_transfer_insn != end)
562     {
563       skip_purge = false;
564 
565     clean_up_debug_after_control_flow:
566       BB_END (bb) = flow_transfer_insn;
567 
568       /* Clean up the bb field for the insns that do not belong to BB.  */
569       rtx_insn *next;
570       for (x = NEXT_INSN (flow_transfer_insn); ; x = next)
571 	{
572 	  next = NEXT_INSN (x);
573 	  /* Debug insns should not be in between basic blocks,
574 	     drop them on the floor.  */
575 	  if (DEBUG_INSN_P (x))
576 	    delete_insn (x);
577 	  else if (!BARRIER_P (x))
578 	    set_block_for_insn (x, NULL);
579 	  if (x == end)
580 	    break;
581 	}
582 
583       if (skip_purge)
584 	return;
585     }
586 
587   /* We've possibly replaced the conditional jump by conditional jump
588      followed by cleanup at fallthru edge, so the outgoing edges may
589      be dead.  */
590   purge_dead_edges (bb);
591 
592   /* purge_dead_edges doesn't handle tablejump's, but if we have split the
593      basic block, we might need to kill some edges.  */
594   if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
595     purge_dead_tablejump_edges (bb, table);
596 }
597 
598 /*  Assume that frequency of basic block B is known.  Compute frequencies
599     and probabilities of outgoing edges.  */
600 
601 static void
compute_outgoing_frequencies(basic_block b)602 compute_outgoing_frequencies (basic_block b)
603 {
604   edge e, f;
605   edge_iterator ei;
606 
607   if (EDGE_COUNT (b->succs) == 2)
608     {
609       rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
610       int probability;
611 
612       if (note)
613 	{
614 	  probability = XINT (note, 0);
615 	  e = BRANCH_EDGE (b);
616 	  e->probability
617 		 = profile_probability::from_reg_br_prob_note (probability);
618 	  f = FALLTHRU_EDGE (b);
619 	  f->probability = e->probability.invert ();
620 	  return;
621 	}
622       else
623         {
624           guess_outgoing_edge_probabilities (b);
625         }
626     }
627   else if (single_succ_p (b))
628     {
629       e = single_succ_edge (b);
630       e->probability = profile_probability::always ();
631       return;
632     }
633   else
634     {
635       /* We rely on BBs with more than two successors to have sane probabilities
636          and do not guess them here. For BBs terminated by switch statements
637          expanded to jump-table jump, we have done the right thing during
638          expansion. For EH edges, we still guess the probabilities here.  */
639       bool complex_edge = false;
640       FOR_EACH_EDGE (e, ei, b->succs)
641         if (e->flags & EDGE_COMPLEX)
642           {
643             complex_edge = true;
644             break;
645           }
646       if (complex_edge)
647         guess_outgoing_edge_probabilities (b);
648     }
649 }
650 
651 /* Assume that some pass has inserted labels or control flow
652    instructions within a basic block.  Split basic blocks as needed
653    and create edges.  */
654 
655 void
find_many_sub_basic_blocks(sbitmap blocks)656 find_many_sub_basic_blocks (sbitmap blocks)
657 {
658   basic_block bb, min, max;
659   bool found = false;
660   auto_vec<unsigned int> n_succs;
661   n_succs.safe_grow_cleared (last_basic_block_for_fn (cfun));
662 
663   FOR_EACH_BB_FN (bb, cfun)
664     SET_STATE (bb,
665 	       bitmap_bit_p (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
666 
667   FOR_EACH_BB_FN (bb, cfun)
668     if (STATE (bb) == BLOCK_TO_SPLIT)
669       {
670 	int n = last_basic_block_for_fn (cfun);
671 	unsigned int ns = EDGE_COUNT (bb->succs);
672 
673         find_bb_boundaries (bb);
674 	if (n == last_basic_block_for_fn (cfun) && ns == EDGE_COUNT (bb->succs))
675 	  n_succs[bb->index] = EDGE_COUNT (bb->succs);
676       }
677 
678   FOR_EACH_BB_FN (bb, cfun)
679     if (STATE (bb) != BLOCK_ORIGINAL)
680       {
681 	found = true;
682         break;
683       }
684 
685   if (!found)
686     return;
687 
688   min = max = bb;
689   for (; bb != EXIT_BLOCK_PTR_FOR_FN (cfun); bb = bb->next_bb)
690     if (STATE (bb) != BLOCK_ORIGINAL)
691       max = bb;
692 
693   /* Now re-scan and wire in all edges.  This expect simple (conditional)
694      jumps at the end of each new basic blocks.  */
695   make_edges (min, max, 1);
696 
697   /* Update branch probabilities.  Expect only (un)conditional jumps
698      to be created with only the forward edges.  */
699   if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
700     FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
701       {
702 	edge e;
703 	edge_iterator ei;
704 
705 	if (STATE (bb) == BLOCK_ORIGINAL)
706 	  continue;
707 	if (STATE (bb) == BLOCK_NEW)
708 	  {
709 	    bool initialized_src = false, uninitialized_src = false;
710 	    bb->count = profile_count::zero ();
711 	    FOR_EACH_EDGE (e, ei, bb->preds)
712 	      {
713 		if (e->count ().initialized_p ())
714 		  {
715 		    bb->count += e->count ();
716 		    initialized_src = true;
717 		  }
718 		else
719 		  uninitialized_src = true;
720 	      }
721 	    /* When some edges are missing with read profile, this is
722 	       most likely because RTL expansion introduced loop.
723 	       When profile is guessed we may have BB that is reachable
724 	       from unlikely path as well as from normal path.
725 
726 	       TODO: We should handle loops created during BB expansion
727 	       correctly here.  For now we assume all those loop to cycle
728 	       precisely once.  */
729 	    if (!initialized_src
730 		|| (uninitialized_src
731 		     && profile_status_for_fn (cfun) < PROFILE_GUESSED))
732 	      bb->count = profile_count::uninitialized ();
733 	  }
734  	/* If nothing changed, there is no need to create new BBs.  */
735 	else if (EDGE_COUNT (bb->succs) == n_succs[bb->index])
736 	  {
737 	    /* In rare occassions RTL expansion might have mistakely assigned
738 	       a probabilities different from what is in CFG.  This happens
739 	       when we try to split branch to two but optimize out the
740 	       second branch during the way. See PR81030.  */
741 	    if (JUMP_P (BB_END (bb)) && any_condjump_p (BB_END (bb))
742 		&& EDGE_COUNT (bb->succs) >= 2)
743 	      update_br_prob_note (bb);
744 	    continue;
745 	  }
746 
747 	compute_outgoing_frequencies (bb);
748       }
749 
750   FOR_EACH_BB_FN (bb, cfun)
751     SET_STATE (bb, 0);
752 }
753