compiler: explicitly convert between type aliases
[official-gcc.git] / gcc / cfgrtl.c
blob65e25dc1293349f2ecdc3f309635a4d7d9879381
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
32 fixup_abnormal_edges
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
40 #include "config.h"
41 #include "system.h"
42 #include "coretypes.h"
43 #include "backend.h"
44 #include "target.h"
45 #include "rtl.h"
46 #include "tree.h"
47 #include "cfghooks.h"
48 #include "df.h"
49 #include "insn-config.h"
50 #include "memmodel.h"
51 #include "emit-rtl.h"
52 #include "cfgrtl.h"
53 #include "cfganal.h"
54 #include "cfgbuild.h"
55 #include "cfgcleanup.h"
56 #include "bb-reorder.h"
57 #include "rtl-error.h"
58 #include "insn-attr.h"
59 #include "dojump.h"
60 #include "expr.h"
61 #include "cfgloop.h"
62 #include "tree-pass.h"
63 #include "print-rtl.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx_insn *cfg_layout_function_footer;
68 static GTY(()) rtx_insn *cfg_layout_function_header;
70 static rtx_insn *skip_insns_after_block (basic_block);
71 static void record_effective_endpoints (void);
72 static void fixup_reorder_chain (void);
74 void verify_insn_chain (void);
75 static void fixup_fallthru_exit_predecessor (void);
76 static int can_delete_note_p (const rtx_note *);
77 static int can_delete_label_p (const rtx_code_label *);
78 static basic_block rtl_split_edge (edge);
79 static bool rtl_move_block_after (basic_block, basic_block);
80 static int rtl_verify_flow_info (void);
81 static basic_block cfg_layout_split_block (basic_block, void *);
82 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
83 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
84 static void cfg_layout_delete_block (basic_block);
85 static void rtl_delete_block (basic_block);
86 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
87 static edge rtl_redirect_edge_and_branch (edge, basic_block);
88 static basic_block rtl_split_block (basic_block, void *);
89 static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
90 static int rtl_verify_flow_info_1 (void);
91 static void rtl_make_forwarder_block (edge);
93 /* Return true if NOTE is not one of the ones that must be kept paired,
94 so that we may simply delete it. */
96 static int
97 can_delete_note_p (const rtx_note *note)
99 switch (NOTE_KIND (note))
101 case NOTE_INSN_DELETED:
102 case NOTE_INSN_BASIC_BLOCK:
103 case NOTE_INSN_EPILOGUE_BEG:
104 return true;
106 default:
107 return false;
111 /* True if a given label can be deleted. */
113 static int
114 can_delete_label_p (const rtx_code_label *label)
116 return (!LABEL_PRESERVE_P (label)
117 /* User declared labels must be preserved. */
118 && LABEL_NAME (label) == 0
119 && !vec_safe_contains<rtx_insn *> (forced_labels,
120 const_cast<rtx_code_label *> (label)));
123 /* Delete INSN by patching it out. */
125 void
126 delete_insn (rtx_insn *insn)
128 rtx note;
129 bool really_delete = true;
131 if (LABEL_P (insn))
133 /* Some labels can't be directly removed from the INSN chain, as they
134 might be references via variables, constant pool etc.
135 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
136 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
138 const char *name = LABEL_NAME (insn);
139 basic_block bb = BLOCK_FOR_INSN (insn);
140 rtx_insn *bb_note = NEXT_INSN (insn);
142 really_delete = false;
143 PUT_CODE (insn, NOTE);
144 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
145 NOTE_DELETED_LABEL_NAME (insn) = name;
147 /* If the note following the label starts a basic block, and the
148 label is a member of the same basic block, interchange the two. */
149 if (bb_note != NULL_RTX
150 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
151 && bb != NULL
152 && bb == BLOCK_FOR_INSN (bb_note))
154 reorder_insns_nobb (insn, insn, bb_note);
155 BB_HEAD (bb) = bb_note;
156 if (BB_END (bb) == bb_note)
157 BB_END (bb) = insn;
161 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
164 if (really_delete)
166 /* If this insn has already been deleted, something is very wrong. */
167 gcc_assert (!insn->deleted ());
168 if (INSN_P (insn))
169 df_insn_delete (insn);
170 remove_insn (insn);
171 insn->set_deleted ();
174 /* If deleting a jump, decrement the use count of the label. Deleting
175 the label itself should happen in the normal course of block merging. */
176 if (JUMP_P (insn))
178 if (JUMP_LABEL (insn)
179 && LABEL_P (JUMP_LABEL (insn)))
180 LABEL_NUSES (JUMP_LABEL (insn))--;
182 /* If there are more targets, remove them too. */
183 while ((note
184 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
185 && LABEL_P (XEXP (note, 0)))
187 LABEL_NUSES (XEXP (note, 0))--;
188 remove_note (insn, note);
192 /* Also if deleting any insn that references a label as an operand. */
193 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
194 && LABEL_P (XEXP (note, 0)))
196 LABEL_NUSES (XEXP (note, 0))--;
197 remove_note (insn, note);
200 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
202 rtvec vec = table->get_labels ();
203 int len = GET_NUM_ELEM (vec);
204 int i;
206 for (i = 0; i < len; i++)
208 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
210 /* When deleting code in bulk (e.g. removing many unreachable
211 blocks) we can delete a label that's a target of the vector
212 before deleting the vector itself. */
213 if (!NOTE_P (label))
214 LABEL_NUSES (label)--;
219 /* Like delete_insn but also purge dead edges from BB.
220 Return true if any edges are eliminated. */
222 bool
223 delete_insn_and_edges (rtx_insn *insn)
225 bool purge = false;
227 if (INSN_P (insn)
228 && BLOCK_FOR_INSN (insn)
229 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
230 purge = true;
231 delete_insn (insn);
232 if (purge)
233 return purge_dead_edges (BLOCK_FOR_INSN (insn));
234 return false;
237 /* Unlink a chain of insns between START and FINISH, leaving notes
238 that must be paired. If CLEAR_BB is true, we set bb field for
239 insns that cannot be removed to NULL. */
241 void
242 delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
244 /* Unchain the insns one by one. It would be quicker to delete all of these
245 with a single unchaining, rather than one at a time, but we need to keep
246 the NOTE's. */
247 rtx_insn *current = finish;
248 while (1)
250 rtx_insn *prev = PREV_INSN (current);
251 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
253 else
254 delete_insn (current);
256 if (clear_bb && !current->deleted ())
257 set_block_for_insn (current, NULL);
259 if (current == start)
260 break;
261 current = prev;
265 /* Create a new basic block consisting of the instructions between HEAD and END
266 inclusive. This function is designed to allow fast BB construction - reuses
267 the note and basic block struct in BB_NOTE, if any and do not grow
268 BASIC_BLOCK chain and should be used directly only by CFG construction code.
269 END can be NULL in to create new empty basic block before HEAD. Both END
270 and HEAD can be NULL to create basic block at the end of INSN chain.
271 AFTER is the basic block we should be put after. */
273 basic_block
274 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
275 basic_block after)
277 basic_block bb;
279 if (bb_note
280 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
281 && bb->aux == NULL)
283 /* If we found an existing note, thread it back onto the chain. */
285 rtx_insn *after;
287 if (LABEL_P (head))
288 after = head;
289 else
291 after = PREV_INSN (head);
292 head = bb_note;
295 if (after != bb_note && NEXT_INSN (after) != bb_note)
296 reorder_insns_nobb (bb_note, bb_note, after);
298 else
300 /* Otherwise we must create a note and a basic block structure. */
302 bb = alloc_block ();
304 init_rtl_bb_info (bb);
305 if (!head && !end)
306 head = end = bb_note
307 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
308 else if (LABEL_P (head) && end)
310 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
311 if (head == end)
312 end = bb_note;
314 else
316 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
317 head = bb_note;
318 if (!end)
319 end = head;
322 NOTE_BASIC_BLOCK (bb_note) = bb;
325 /* Always include the bb note in the block. */
326 if (NEXT_INSN (end) == bb_note)
327 end = bb_note;
329 BB_HEAD (bb) = head;
330 BB_END (bb) = end;
331 bb->index = last_basic_block_for_fn (cfun)++;
332 bb->flags = BB_NEW | BB_RTL;
333 link_block (bb, after);
334 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
335 df_bb_refs_record (bb->index, false);
336 update_bb_for_insn (bb);
337 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
339 /* Tag the block so that we know it has been used when considering
340 other basic block notes. */
341 bb->aux = bb;
343 return bb;
346 /* Create new basic block consisting of instructions in between HEAD and END
347 and place it to the BB chain after block AFTER. END can be NULL to
348 create a new empty basic block before HEAD. Both END and HEAD can be
349 NULL to create basic block at the end of INSN chain. */
351 static basic_block
352 rtl_create_basic_block (void *headp, void *endp, basic_block after)
354 rtx_insn *head = (rtx_insn *) headp;
355 rtx_insn *end = (rtx_insn *) endp;
356 basic_block bb;
358 /* Grow the basic block array if needed. */
359 if ((size_t) last_basic_block_for_fn (cfun)
360 >= basic_block_info_for_fn (cfun)->length ())
362 size_t new_size =
363 (last_basic_block_for_fn (cfun)
364 + (last_basic_block_for_fn (cfun) + 3) / 4);
365 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
368 n_basic_blocks_for_fn (cfun)++;
370 bb = create_basic_block_structure (head, end, NULL, after);
371 bb->aux = NULL;
372 return bb;
375 static basic_block
376 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
378 basic_block newbb = rtl_create_basic_block (head, end, after);
380 return newbb;
383 /* Delete the insns in a (non-live) block. We physically delete every
384 non-deleted-note insn, and update the flow graph appropriately.
386 Return nonzero if we deleted an exception handler. */
388 /* ??? Preserving all such notes strikes me as wrong. It would be nice
389 to post-process the stream to remove empty blocks, loops, ranges, etc. */
391 static void
392 rtl_delete_block (basic_block b)
394 rtx_insn *insn, *end;
396 /* If the head of this block is a CODE_LABEL, then it might be the
397 label for an exception handler which can't be reached. We need
398 to remove the label from the exception_handler_label list. */
399 insn = BB_HEAD (b);
401 end = get_last_bb_insn (b);
403 /* Selectively delete the entire chain. */
404 BB_HEAD (b) = NULL;
405 delete_insn_chain (insn, end, true);
408 if (dump_file)
409 fprintf (dump_file, "deleting block %d\n", b->index);
410 df_bb_delete (b->index);
413 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
415 void
416 compute_bb_for_insn (void)
418 basic_block bb;
420 FOR_EACH_BB_FN (bb, cfun)
422 rtx_insn *end = BB_END (bb);
423 rtx_insn *insn;
425 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
427 BLOCK_FOR_INSN (insn) = bb;
428 if (insn == end)
429 break;
434 /* Release the basic_block_for_insn array. */
436 unsigned int
437 free_bb_for_insn (void)
439 rtx_insn *insn;
440 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
441 if (!BARRIER_P (insn))
442 BLOCK_FOR_INSN (insn) = NULL;
443 return 0;
446 namespace {
448 const pass_data pass_data_free_cfg =
450 RTL_PASS, /* type */
451 "*free_cfg", /* name */
452 OPTGROUP_NONE, /* optinfo_flags */
453 TV_NONE, /* tv_id */
454 0, /* properties_required */
455 0, /* properties_provided */
456 PROP_cfg, /* properties_destroyed */
457 0, /* todo_flags_start */
458 0, /* todo_flags_finish */
461 class pass_free_cfg : public rtl_opt_pass
463 public:
464 pass_free_cfg (gcc::context *ctxt)
465 : rtl_opt_pass (pass_data_free_cfg, ctxt)
468 /* opt_pass methods: */
469 virtual unsigned int execute (function *);
471 }; // class pass_free_cfg
473 unsigned int
474 pass_free_cfg::execute (function *)
476 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
477 valid at that point so it would be too late to call df_analyze. */
478 if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch)
480 df_note_add_problem ();
481 df_analyze ();
484 if (crtl->has_bb_partition)
485 insert_section_boundary_note ();
487 free_bb_for_insn ();
488 return 0;
491 } // anon namespace
493 rtl_opt_pass *
494 make_pass_free_cfg (gcc::context *ctxt)
496 return new pass_free_cfg (ctxt);
499 /* Return RTX to emit after when we want to emit code on the entry of function. */
500 rtx_insn *
501 entry_of_function (void)
503 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
504 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
507 /* Emit INSN at the entry point of the function, ensuring that it is only
508 executed once per function. */
509 void
510 emit_insn_at_entry (rtx insn)
512 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
513 edge e = ei_safe_edge (ei);
514 gcc_assert (e->flags & EDGE_FALLTHRU);
516 insert_insn_on_edge (insn, e);
517 commit_edge_insertions ();
520 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
521 (or BARRIER if found) and notify df of the bb change.
522 The insn chain range is inclusive
523 (i.e. both BEGIN and END will be updated. */
525 static void
526 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
528 rtx_insn *insn;
530 end = NEXT_INSN (end);
531 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
532 if (!BARRIER_P (insn))
533 df_insn_change_bb (insn, bb);
536 /* Update BLOCK_FOR_INSN of insns in BB to BB,
537 and notify df of the change. */
539 void
540 update_bb_for_insn (basic_block bb)
542 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
546 /* Like active_insn_p, except keep the return value clobber around
547 even after reload. */
549 static bool
550 flow_active_insn_p (const rtx_insn *insn)
552 if (active_insn_p (insn))
553 return true;
555 /* A clobber of the function return value exists for buggy
556 programs that fail to return a value. Its effect is to
557 keep the return value from being live across the entire
558 function. If we allow it to be skipped, we introduce the
559 possibility for register lifetime confusion. */
560 if (GET_CODE (PATTERN (insn)) == CLOBBER
561 && REG_P (XEXP (PATTERN (insn), 0))
562 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
563 return true;
565 return false;
568 /* Return true if the block has no effect and only forwards control flow to
569 its single destination. */
571 bool
572 contains_no_active_insn_p (const_basic_block bb)
574 rtx_insn *insn;
576 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
577 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
578 || !single_succ_p (bb)
579 || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0)
580 return false;
582 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
583 if (INSN_P (insn) && flow_active_insn_p (insn))
584 return false;
586 return (!INSN_P (insn)
587 || (JUMP_P (insn) && simplejump_p (insn))
588 || !flow_active_insn_p (insn));
591 /* Likewise, but protect loop latches, headers and preheaders. */
592 /* FIXME: Make this a cfg hook. */
594 bool
595 forwarder_block_p (const_basic_block bb)
597 if (!contains_no_active_insn_p (bb))
598 return false;
600 /* Protect loop latches, headers and preheaders. */
601 if (current_loops)
603 basic_block dest;
604 if (bb->loop_father->header == bb)
605 return false;
606 dest = EDGE_SUCC (bb, 0)->dest;
607 if (dest->loop_father->header == dest)
608 return false;
611 return true;
614 /* Return nonzero if we can reach target from src by falling through. */
615 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
617 bool
618 can_fallthru (basic_block src, basic_block target)
620 rtx_insn *insn = BB_END (src);
621 rtx_insn *insn2;
622 edge e;
623 edge_iterator ei;
625 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
626 return true;
627 if (src->next_bb != target)
628 return false;
630 /* ??? Later we may add code to move jump tables offline. */
631 if (tablejump_p (insn, NULL, NULL))
632 return false;
634 FOR_EACH_EDGE (e, ei, src->succs)
635 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
636 && e->flags & EDGE_FALLTHRU)
637 return false;
639 insn2 = BB_HEAD (target);
640 if (!active_insn_p (insn2))
641 insn2 = next_active_insn (insn2);
643 return next_active_insn (insn) == insn2;
646 /* Return nonzero if we could reach target from src by falling through,
647 if the target was made adjacent. If we already have a fall-through
648 edge to the exit block, we can't do that. */
649 static bool
650 could_fall_through (basic_block src, basic_block target)
652 edge e;
653 edge_iterator ei;
655 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
656 return true;
657 FOR_EACH_EDGE (e, ei, src->succs)
658 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
659 && e->flags & EDGE_FALLTHRU)
660 return 0;
661 return true;
664 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
665 rtx_note *
666 bb_note (basic_block bb)
668 rtx_insn *note;
670 note = BB_HEAD (bb);
671 if (LABEL_P (note))
672 note = NEXT_INSN (note);
674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
675 return as_a <rtx_note *> (note);
678 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
679 note associated with the BLOCK. */
681 static rtx_insn *
682 first_insn_after_basic_block_note (basic_block block)
684 rtx_insn *insn;
686 /* Get the first instruction in the block. */
687 insn = BB_HEAD (block);
689 if (insn == NULL_RTX)
690 return NULL;
691 if (LABEL_P (insn))
692 insn = NEXT_INSN (insn);
693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
695 return NEXT_INSN (insn);
698 /* Creates a new basic block just after basic block BB by splitting
699 everything after specified instruction INSNP. */
701 static basic_block
702 rtl_split_block (basic_block bb, void *insnp)
704 basic_block new_bb;
705 rtx_insn *insn = (rtx_insn *) insnp;
706 edge e;
707 edge_iterator ei;
709 if (!insn)
711 insn = first_insn_after_basic_block_note (bb);
713 if (insn)
715 rtx_insn *next = insn;
717 insn = PREV_INSN (insn);
719 /* If the block contains only debug insns, insn would have
720 been NULL in a non-debug compilation, and then we'd end
721 up emitting a DELETED note. For -fcompare-debug
722 stability, emit the note too. */
723 if (insn != BB_END (bb)
724 && DEBUG_INSN_P (next)
725 && DEBUG_INSN_P (BB_END (bb)))
727 while (next != BB_END (bb) && DEBUG_INSN_P (next))
728 next = NEXT_INSN (next);
730 if (next == BB_END (bb))
731 emit_note_after (NOTE_INSN_DELETED, next);
734 else
735 insn = get_last_insn ();
738 /* We probably should check type of the insn so that we do not create
739 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
740 bother. */
741 if (insn == BB_END (bb))
742 emit_note_after (NOTE_INSN_DELETED, insn);
744 /* Create the new basic block. */
745 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
746 BB_COPY_PARTITION (new_bb, bb);
747 BB_END (bb) = insn;
749 /* Redirect the outgoing edges. */
750 new_bb->succs = bb->succs;
751 bb->succs = NULL;
752 FOR_EACH_EDGE (e, ei, new_bb->succs)
753 e->src = new_bb;
755 /* The new block starts off being dirty. */
756 df_set_bb_dirty (bb);
757 return new_bb;
760 /* Return true if the single edge between blocks A and B is the only place
761 in RTL which holds some unique locus. */
763 static bool
764 unique_locus_on_edge_between_p (basic_block a, basic_block b)
766 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
767 rtx_insn *insn, *end;
769 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
770 return false;
772 /* First scan block A backward. */
773 insn = BB_END (a);
774 end = PREV_INSN (BB_HEAD (a));
775 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
776 insn = PREV_INSN (insn);
778 if (insn != end && INSN_LOCATION (insn) == goto_locus)
779 return false;
781 /* Then scan block B forward. */
782 insn = BB_HEAD (b);
783 if (insn)
785 end = NEXT_INSN (BB_END (b));
786 while (insn != end && !NONDEBUG_INSN_P (insn))
787 insn = NEXT_INSN (insn);
789 if (insn != end && INSN_HAS_LOCATION (insn)
790 && INSN_LOCATION (insn) == goto_locus)
791 return false;
794 return true;
797 /* If the single edge between blocks A and B is the only place in RTL which
798 holds some unique locus, emit a nop with that locus between the blocks. */
800 static void
801 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
803 if (!unique_locus_on_edge_between_p (a, b))
804 return;
806 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
807 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
810 /* Blocks A and B are to be merged into a single block A. The insns
811 are already contiguous. */
813 static void
814 rtl_merge_blocks (basic_block a, basic_block b)
816 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
817 rtx_insn *del_first = NULL, *del_last = NULL;
818 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
819 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
820 int b_empty = 0;
822 if (dump_file)
823 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
824 a->index);
826 while (DEBUG_INSN_P (b_end))
827 b_end = PREV_INSN (b_debug_start = b_end);
829 /* If there was a CODE_LABEL beginning B, delete it. */
830 if (LABEL_P (b_head))
832 /* Detect basic blocks with nothing but a label. This can happen
833 in particular at the end of a function. */
834 if (b_head == b_end)
835 b_empty = 1;
837 del_first = del_last = b_head;
838 b_head = NEXT_INSN (b_head);
841 /* Delete the basic block note and handle blocks containing just that
842 note. */
843 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
845 if (b_head == b_end)
846 b_empty = 1;
847 if (! del_last)
848 del_first = b_head;
850 del_last = b_head;
851 b_head = NEXT_INSN (b_head);
854 /* If there was a jump out of A, delete it. */
855 if (JUMP_P (a_end))
857 rtx_insn *prev;
859 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
860 if (!NOTE_P (prev)
861 || NOTE_INSN_BASIC_BLOCK_P (prev)
862 || prev == BB_HEAD (a))
863 break;
865 del_first = a_end;
867 /* If this was a conditional jump, we need to also delete
868 the insn that set cc0. */
869 if (HAVE_cc0 && only_sets_cc0_p (prev))
871 rtx_insn *tmp = prev;
873 prev = prev_nonnote_insn (prev);
874 if (!prev)
875 prev = BB_HEAD (a);
876 del_first = tmp;
879 a_end = PREV_INSN (del_first);
881 else if (BARRIER_P (NEXT_INSN (a_end)))
882 del_first = NEXT_INSN (a_end);
884 /* Delete everything marked above as well as crap that might be
885 hanging out between the two blocks. */
886 BB_END (a) = a_end;
887 BB_HEAD (b) = b_empty ? NULL : b_head;
888 delete_insn_chain (del_first, del_last, true);
890 /* When not optimizing and the edge is the only place in RTL which holds
891 some unique locus, emit a nop with that locus in between. */
892 if (!optimize)
894 emit_nop_for_unique_locus_between (a, b);
895 a_end = BB_END (a);
898 /* Reassociate the insns of B with A. */
899 if (!b_empty)
901 update_bb_for_insn_chain (a_end, b_debug_end, a);
903 BB_END (a) = b_debug_end;
904 BB_HEAD (b) = NULL;
906 else if (b_end != b_debug_end)
908 /* Move any deleted labels and other notes between the end of A
909 and the debug insns that make up B after the debug insns,
910 bringing the debug insns into A while keeping the notes after
911 the end of A. */
912 if (NEXT_INSN (a_end) != b_debug_start)
913 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
914 b_debug_end);
915 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
916 BB_END (a) = b_debug_end;
919 df_bb_delete (b->index);
921 /* If B was a forwarder block, propagate the locus on the edge. */
922 if (forwarder_p
923 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
924 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
926 if (dump_file)
927 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
931 /* Return true when block A and B can be merged. */
933 static bool
934 rtl_can_merge_blocks (basic_block a, basic_block b)
936 /* If we are partitioning hot/cold basic blocks, we don't want to
937 mess up unconditional or indirect jumps that cross between hot
938 and cold sections.
940 Basic block partitioning may result in some jumps that appear to
941 be optimizable (or blocks that appear to be mergeable), but which really
942 must be left untouched (they are required to make it safely across
943 partition boundaries). See the comments at the top of
944 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
946 if (BB_PARTITION (a) != BB_PARTITION (b))
947 return false;
949 /* Protect the loop latches. */
950 if (current_loops && b->loop_father->latch == b)
951 return false;
953 /* There must be exactly one edge in between the blocks. */
954 return (single_succ_p (a)
955 && single_succ (a) == b
956 && single_pred_p (b)
957 && a != b
958 /* Must be simple edge. */
959 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
960 && a->next_bb == b
961 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
962 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
963 /* If the jump insn has side effects,
964 we can't kill the edge. */
965 && (!JUMP_P (BB_END (a))
966 || (reload_completed
967 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
970 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
971 exist. */
973 rtx_code_label *
974 block_label (basic_block block)
976 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
977 return NULL;
979 if (!LABEL_P (BB_HEAD (block)))
981 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
984 return as_a <rtx_code_label *> (BB_HEAD (block));
987 /* Attempt to perform edge redirection by replacing possibly complex jump
988 instruction by unconditional jump or removing jump completely. This can
989 apply only if all edges now point to the same block. The parameters and
990 return values are equivalent to redirect_edge_and_branch. */
992 edge
993 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
995 basic_block src = e->src;
996 rtx_insn *insn = BB_END (src), *kill_from;
997 rtx set;
998 int fallthru = 0;
1000 /* If we are partitioning hot/cold basic blocks, we don't want to
1001 mess up unconditional or indirect jumps that cross between hot
1002 and cold sections.
1004 Basic block partitioning may result in some jumps that appear to
1005 be optimizable (or blocks that appear to be mergeable), but which really
1006 must be left untouched (they are required to make it safely across
1007 partition boundaries). See the comments at the top of
1008 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1010 if (BB_PARTITION (src) != BB_PARTITION (target))
1011 return NULL;
1013 /* We can replace or remove a complex jump only when we have exactly
1014 two edges. Also, if we have exactly one outgoing edge, we can
1015 redirect that. */
1016 if (EDGE_COUNT (src->succs) >= 3
1017 /* Verify that all targets will be TARGET. Specifically, the
1018 edge that is not E must also go to TARGET. */
1019 || (EDGE_COUNT (src->succs) == 2
1020 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1021 return NULL;
1023 if (!onlyjump_p (insn))
1024 return NULL;
1025 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1026 return NULL;
1028 /* Avoid removing branch with side effects. */
1029 set = single_set (insn);
1030 if (!set || side_effects_p (set))
1031 return NULL;
1033 /* In case we zap a conditional jump, we'll need to kill
1034 the cc0 setter too. */
1035 kill_from = insn;
1036 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, PATTERN (insn))
1037 && only_sets_cc0_p (PREV_INSN (insn)))
1038 kill_from = PREV_INSN (insn);
1040 /* See if we can create the fallthru edge. */
1041 if (in_cfglayout || can_fallthru (src, target))
1043 if (dump_file)
1044 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1045 fallthru = 1;
1047 /* Selectively unlink whole insn chain. */
1048 if (in_cfglayout)
1050 rtx_insn *insn = BB_FOOTER (src);
1052 delete_insn_chain (kill_from, BB_END (src), false);
1054 /* Remove barriers but keep jumptables. */
1055 while (insn)
1057 if (BARRIER_P (insn))
1059 if (PREV_INSN (insn))
1060 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1061 else
1062 BB_FOOTER (src) = NEXT_INSN (insn);
1063 if (NEXT_INSN (insn))
1064 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1066 if (LABEL_P (insn))
1067 break;
1068 insn = NEXT_INSN (insn);
1071 else
1072 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1073 false);
1076 /* If this already is simplejump, redirect it. */
1077 else if (simplejump_p (insn))
1079 if (e->dest == target)
1080 return NULL;
1081 if (dump_file)
1082 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1083 INSN_UID (insn), e->dest->index, target->index);
1084 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1085 block_label (target), 0))
1087 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1088 return NULL;
1092 /* Cannot do anything for target exit block. */
1093 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1094 return NULL;
1096 /* Or replace possibly complicated jump insn by simple jump insn. */
1097 else
1099 rtx_code_label *target_label = block_label (target);
1100 rtx_insn *barrier;
1101 rtx_insn *label;
1102 rtx_jump_table_data *table;
1104 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1105 JUMP_LABEL (BB_END (src)) = target_label;
1106 LABEL_NUSES (target_label)++;
1107 if (dump_file)
1108 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1109 INSN_UID (insn), INSN_UID (BB_END (src)));
1112 delete_insn_chain (kill_from, insn, false);
1114 /* Recognize a tablejump that we are converting to a
1115 simple jump and remove its associated CODE_LABEL
1116 and ADDR_VEC or ADDR_DIFF_VEC. */
1117 if (tablejump_p (insn, &label, &table))
1118 delete_insn_chain (label, table, false);
1120 barrier = next_nonnote_insn (BB_END (src));
1121 if (!barrier || !BARRIER_P (barrier))
1122 emit_barrier_after (BB_END (src));
1123 else
1125 if (barrier != NEXT_INSN (BB_END (src)))
1127 /* Move the jump before barrier so that the notes
1128 which originally were or were created before jump table are
1129 inside the basic block. */
1130 rtx_insn *new_insn = BB_END (src);
1132 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1133 PREV_INSN (barrier), src);
1135 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1136 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1138 SET_NEXT_INSN (new_insn) = barrier;
1139 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1141 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1142 SET_PREV_INSN (barrier) = new_insn;
1147 /* Keep only one edge out and set proper flags. */
1148 if (!single_succ_p (src))
1149 remove_edge (e);
1150 gcc_assert (single_succ_p (src));
1152 e = single_succ_edge (src);
1153 if (fallthru)
1154 e->flags = EDGE_FALLTHRU;
1155 else
1156 e->flags = 0;
1158 e->probability = profile_probability::always ();
1160 if (e->dest != target)
1161 redirect_edge_succ (e, target);
1162 return e;
1165 /* Subroutine of redirect_branch_edge that tries to patch the jump
1166 instruction INSN so that it reaches block NEW. Do this
1167 only when it originally reached block OLD. Return true if this
1168 worked or the original target wasn't OLD, return false if redirection
1169 doesn't work. */
1171 static bool
1172 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1174 rtx_jump_table_data *table;
1175 rtx tmp;
1176 /* Recognize a tablejump and adjust all matching cases. */
1177 if (tablejump_p (insn, NULL, &table))
1179 rtvec vec;
1180 int j;
1181 rtx_code_label *new_label = block_label (new_bb);
1183 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1184 return false;
1185 vec = table->get_labels ();
1187 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1188 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1190 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1191 --LABEL_NUSES (old_label);
1192 ++LABEL_NUSES (new_label);
1195 /* Handle casesi dispatch insns. */
1196 if ((tmp = single_set (insn)) != NULL
1197 && SET_DEST (tmp) == pc_rtx
1198 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1199 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1200 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1202 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1203 new_label);
1204 --LABEL_NUSES (old_label);
1205 ++LABEL_NUSES (new_label);
1208 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1210 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1211 rtx note;
1213 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1214 return false;
1215 rtx_code_label *new_label = block_label (new_bb);
1217 for (i = 0; i < n; ++i)
1219 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1220 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1221 if (XEXP (old_ref, 0) == old_label)
1223 ASM_OPERANDS_LABEL (tmp, i)
1224 = gen_rtx_LABEL_REF (Pmode, new_label);
1225 --LABEL_NUSES (old_label);
1226 ++LABEL_NUSES (new_label);
1230 if (JUMP_LABEL (insn) == old_label)
1232 JUMP_LABEL (insn) = new_label;
1233 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1234 if (note)
1235 remove_note (insn, note);
1237 else
1239 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1240 if (note)
1241 remove_note (insn, note);
1242 if (JUMP_LABEL (insn) != new_label
1243 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1244 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1246 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1247 != NULL_RTX)
1248 XEXP (note, 0) = new_label;
1250 else
1252 /* ?? We may play the games with moving the named labels from
1253 one basic block to the other in case only one computed_jump is
1254 available. */
1255 if (computed_jump_p (insn)
1256 /* A return instruction can't be redirected. */
1257 || returnjump_p (insn))
1258 return false;
1260 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1262 /* If the insn doesn't go where we think, we're confused. */
1263 gcc_assert (JUMP_LABEL (insn) == old_label);
1265 /* If the substitution doesn't succeed, die. This can happen
1266 if the back end emitted unrecognizable instructions or if
1267 target is exit block on some arches. */
1268 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1269 block_label (new_bb), 0))
1271 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1272 return false;
1276 return true;
1280 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1281 NULL on failure */
1282 static edge
1283 redirect_branch_edge (edge e, basic_block target)
1285 rtx_insn *old_label = BB_HEAD (e->dest);
1286 basic_block src = e->src;
1287 rtx_insn *insn = BB_END (src);
1289 /* We can only redirect non-fallthru edges of jump insn. */
1290 if (e->flags & EDGE_FALLTHRU)
1291 return NULL;
1292 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1293 return NULL;
1295 if (!currently_expanding_to_rtl)
1297 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1298 return NULL;
1300 else
1301 /* When expanding this BB might actually contain multiple
1302 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1303 Redirect all of those that match our label. */
1304 FOR_BB_INSNS (src, insn)
1305 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1306 old_label, target))
1307 return NULL;
1309 if (dump_file)
1310 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1311 e->src->index, e->dest->index, target->index);
1313 if (e->dest != target)
1314 e = redirect_edge_succ_nodup (e, target);
1316 return e;
1319 /* Called when edge E has been redirected to a new destination,
1320 in order to update the region crossing flag on the edge and
1321 jump. */
1323 static void
1324 fixup_partition_crossing (edge e)
1326 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1327 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1328 return;
1329 /* If we redirected an existing edge, it may already be marked
1330 crossing, even though the new src is missing a reg crossing note.
1331 But make sure reg crossing note doesn't already exist before
1332 inserting. */
1333 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1335 e->flags |= EDGE_CROSSING;
1336 if (JUMP_P (BB_END (e->src))
1337 && !CROSSING_JUMP_P (BB_END (e->src)))
1338 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1340 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1342 e->flags &= ~EDGE_CROSSING;
1343 /* Remove the section crossing note from jump at end of
1344 src if it exists, and if no other successors are
1345 still crossing. */
1346 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1348 bool has_crossing_succ = false;
1349 edge e2;
1350 edge_iterator ei;
1351 FOR_EACH_EDGE (e2, ei, e->src->succs)
1353 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1354 if (has_crossing_succ)
1355 break;
1357 if (!has_crossing_succ)
1358 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1363 /* Called when block BB has been reassigned to the cold partition,
1364 because it is now dominated by another cold block,
1365 to ensure that the region crossing attributes are updated. */
1367 static void
1368 fixup_new_cold_bb (basic_block bb)
1370 edge e;
1371 edge_iterator ei;
1373 /* This is called when a hot bb is found to now be dominated
1374 by a cold bb and therefore needs to become cold. Therefore,
1375 its preds will no longer be region crossing. Any non-dominating
1376 preds that were previously hot would also have become cold
1377 in the caller for the same region. Any preds that were previously
1378 region-crossing will be adjusted in fixup_partition_crossing. */
1379 FOR_EACH_EDGE (e, ei, bb->preds)
1381 fixup_partition_crossing (e);
1384 /* Possibly need to make bb's successor edges region crossing,
1385 or remove stale region crossing. */
1386 FOR_EACH_EDGE (e, ei, bb->succs)
1388 /* We can't have fall-through edges across partition boundaries.
1389 Note that force_nonfallthru will do any necessary partition
1390 boundary fixup by calling fixup_partition_crossing itself. */
1391 if ((e->flags & EDGE_FALLTHRU)
1392 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1393 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1394 force_nonfallthru (e);
1395 else
1396 fixup_partition_crossing (e);
1400 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1401 expense of adding new instructions or reordering basic blocks.
1403 Function can be also called with edge destination equivalent to the TARGET.
1404 Then it should try the simplifications and do nothing if none is possible.
1406 Return edge representing the branch if transformation succeeded. Return NULL
1407 on failure.
1408 We still return NULL in case E already destinated TARGET and we didn't
1409 managed to simplify instruction stream. */
1411 static edge
1412 rtl_redirect_edge_and_branch (edge e, basic_block target)
1414 edge ret;
1415 basic_block src = e->src;
1416 basic_block dest = e->dest;
1418 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1419 return NULL;
1421 if (dest == target)
1422 return e;
1424 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1426 df_set_bb_dirty (src);
1427 fixup_partition_crossing (ret);
1428 return ret;
1431 ret = redirect_branch_edge (e, target);
1432 if (!ret)
1433 return NULL;
1435 df_set_bb_dirty (src);
1436 fixup_partition_crossing (ret);
1437 return ret;
1440 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1442 void
1443 emit_barrier_after_bb (basic_block bb)
1445 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1446 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1447 || current_ir_type () == IR_RTL_CFGLAYOUT);
1448 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1450 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1452 if (BB_FOOTER (bb))
1454 rtx_insn *footer_tail = BB_FOOTER (bb);
1456 while (NEXT_INSN (footer_tail))
1457 footer_tail = NEXT_INSN (footer_tail);
1458 if (!BARRIER_P (footer_tail))
1460 SET_NEXT_INSN (footer_tail) = insn;
1461 SET_PREV_INSN (insn) = footer_tail;
1464 else
1465 BB_FOOTER (bb) = insn;
1469 /* Like force_nonfallthru below, but additionally performs redirection
1470 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1471 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1472 simple_return_rtx, indicating which kind of returnjump to create.
1473 It should be NULL otherwise. */
1475 basic_block
1476 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1478 basic_block jump_block, new_bb = NULL, src = e->src;
1479 rtx note;
1480 edge new_edge;
1481 int abnormal_edge_flags = 0;
1482 bool asm_goto_edge = false;
1483 int loc;
1485 /* In the case the last instruction is conditional jump to the next
1486 instruction, first redirect the jump itself and then continue
1487 by creating a basic block afterwards to redirect fallthru edge. */
1488 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1489 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1490 && any_condjump_p (BB_END (e->src))
1491 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1493 rtx note;
1494 edge b = unchecked_make_edge (e->src, target, 0);
1495 bool redirected;
1497 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1498 block_label (target), 0);
1499 gcc_assert (redirected);
1501 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1502 if (note)
1504 int prob = XINT (note, 0);
1506 b->probability = profile_probability::from_reg_br_prob_note (prob);
1507 e->probability -= e->probability;
1511 if (e->flags & EDGE_ABNORMAL)
1513 /* Irritating special case - fallthru edge to the same block as abnormal
1514 edge.
1515 We can't redirect abnormal edge, but we still can split the fallthru
1516 one and create separate abnormal edge to original destination.
1517 This allows bb-reorder to make such edge non-fallthru. */
1518 gcc_assert (e->dest == target);
1519 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1520 e->flags &= EDGE_FALLTHRU;
1522 else
1524 gcc_assert (e->flags & EDGE_FALLTHRU);
1525 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1527 /* We can't redirect the entry block. Create an empty block
1528 at the start of the function which we use to add the new
1529 jump. */
1530 edge tmp;
1531 edge_iterator ei;
1532 bool found = false;
1534 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1535 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1537 /* Change the existing edge's source to be the new block, and add
1538 a new edge from the entry block to the new block. */
1539 e->src = bb;
1540 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1541 (tmp = ei_safe_edge (ei)); )
1543 if (tmp == e)
1545 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1546 found = true;
1547 break;
1549 else
1550 ei_next (&ei);
1553 gcc_assert (found);
1555 vec_safe_push (bb->succs, e);
1556 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1557 EDGE_FALLTHRU);
1561 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1562 don't point to the target or fallthru label. */
1563 if (JUMP_P (BB_END (e->src))
1564 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1565 && (e->flags & EDGE_FALLTHRU)
1566 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1568 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1569 bool adjust_jump_target = false;
1571 for (i = 0; i < n; ++i)
1573 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1575 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1576 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1577 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1578 adjust_jump_target = true;
1580 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1581 asm_goto_edge = true;
1583 if (adjust_jump_target)
1585 rtx_insn *insn = BB_END (e->src);
1586 rtx note;
1587 rtx_insn *old_label = BB_HEAD (e->dest);
1588 rtx_insn *new_label = BB_HEAD (target);
1590 if (JUMP_LABEL (insn) == old_label)
1592 JUMP_LABEL (insn) = new_label;
1593 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1594 if (note)
1595 remove_note (insn, note);
1597 else
1599 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1600 if (note)
1601 remove_note (insn, note);
1602 if (JUMP_LABEL (insn) != new_label
1603 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1604 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1606 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1607 != NULL_RTX)
1608 XEXP (note, 0) = new_label;
1612 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1614 rtx_insn *new_head;
1615 profile_count count = e->count ();
1616 profile_probability probability = e->probability;
1617 /* Create the new structures. */
1619 /* If the old block ended with a tablejump, skip its table
1620 by searching forward from there. Otherwise start searching
1621 forward from the last instruction of the old block. */
1622 rtx_jump_table_data *table;
1623 if (tablejump_p (BB_END (e->src), NULL, &table))
1624 new_head = table;
1625 else
1626 new_head = BB_END (e->src);
1627 new_head = NEXT_INSN (new_head);
1629 jump_block = create_basic_block (new_head, NULL, e->src);
1630 jump_block->count = count;
1631 jump_block->frequency = EDGE_FREQUENCY (e);
1633 /* Make sure new block ends up in correct hot/cold section. */
1635 BB_COPY_PARTITION (jump_block, e->src);
1637 /* Wire edge in. */
1638 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1639 new_edge->probability = probability;
1641 /* Redirect old edge. */
1642 redirect_edge_pred (e, jump_block);
1643 e->probability = profile_probability::always ();
1645 /* If e->src was previously region crossing, it no longer is
1646 and the reg crossing note should be removed. */
1647 fixup_partition_crossing (new_edge);
1649 /* If asm goto has any label refs to target's label,
1650 add also edge from asm goto bb to target. */
1651 if (asm_goto_edge)
1653 new_edge->probability = new_edge->probability.apply_scale (1, 2);
1654 jump_block->count = jump_block->count.apply_scale (1, 2);
1655 jump_block->frequency /= 2;
1656 edge new_edge2 = make_edge (new_edge->src, target,
1657 e->flags & ~EDGE_FALLTHRU);
1658 new_edge2->probability = probability - new_edge->probability;
1661 new_bb = jump_block;
1663 else
1664 jump_block = e->src;
1666 loc = e->goto_locus;
1667 e->flags &= ~EDGE_FALLTHRU;
1668 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1670 if (jump_label == ret_rtx)
1671 emit_jump_insn_after_setloc (targetm.gen_return (),
1672 BB_END (jump_block), loc);
1673 else
1675 gcc_assert (jump_label == simple_return_rtx);
1676 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1677 BB_END (jump_block), loc);
1679 set_return_jump_label (BB_END (jump_block));
1681 else
1683 rtx_code_label *label = block_label (target);
1684 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1685 BB_END (jump_block), loc);
1686 JUMP_LABEL (BB_END (jump_block)) = label;
1687 LABEL_NUSES (label)++;
1690 /* We might be in cfg layout mode, and if so, the following routine will
1691 insert the barrier correctly. */
1692 emit_barrier_after_bb (jump_block);
1693 redirect_edge_succ_nodup (e, target);
1695 if (abnormal_edge_flags)
1696 make_edge (src, target, abnormal_edge_flags);
1698 df_mark_solutions_dirty ();
1699 fixup_partition_crossing (e);
1700 return new_bb;
1703 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1704 (and possibly create new basic block) to make edge non-fallthru.
1705 Return newly created BB or NULL if none. */
1707 static basic_block
1708 rtl_force_nonfallthru (edge e)
1710 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1713 /* Redirect edge even at the expense of creating new jump insn or
1714 basic block. Return new basic block if created, NULL otherwise.
1715 Conversion must be possible. */
1717 static basic_block
1718 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1720 if (redirect_edge_and_branch (e, target)
1721 || e->dest == target)
1722 return NULL;
1724 /* In case the edge redirection failed, try to force it to be non-fallthru
1725 and redirect newly created simplejump. */
1726 df_set_bb_dirty (e->src);
1727 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1730 /* The given edge should potentially be a fallthru edge. If that is in
1731 fact true, delete the jump and barriers that are in the way. */
1733 static void
1734 rtl_tidy_fallthru_edge (edge e)
1736 rtx_insn *q;
1737 basic_block b = e->src, c = b->next_bb;
1739 /* ??? In a late-running flow pass, other folks may have deleted basic
1740 blocks by nopping out blocks, leaving multiple BARRIERs between here
1741 and the target label. They ought to be chastised and fixed.
1743 We can also wind up with a sequence of undeletable labels between
1744 one block and the next.
1746 So search through a sequence of barriers, labels, and notes for
1747 the head of block C and assert that we really do fall through. */
1749 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1750 if (INSN_P (q))
1751 return;
1753 /* Remove what will soon cease being the jump insn from the source block.
1754 If block B consisted only of this single jump, turn it into a deleted
1755 note. */
1756 q = BB_END (b);
1757 if (JUMP_P (q)
1758 && onlyjump_p (q)
1759 && (any_uncondjump_p (q)
1760 || single_succ_p (b)))
1762 rtx_insn *label;
1763 rtx_jump_table_data *table;
1765 if (tablejump_p (q, &label, &table))
1767 /* The label is likely mentioned in some instruction before
1768 the tablejump and might not be DCEd, so turn it into
1769 a note instead and move before the tablejump that is going to
1770 be deleted. */
1771 const char *name = LABEL_NAME (label);
1772 PUT_CODE (label, NOTE);
1773 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1774 NOTE_DELETED_LABEL_NAME (label) = name;
1775 reorder_insns (label, label, PREV_INSN (q));
1776 delete_insn (table);
1779 /* If this was a conditional jump, we need to also delete
1780 the insn that set cc0. */
1781 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1782 q = PREV_INSN (q);
1784 q = PREV_INSN (q);
1786 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1787 together with the barrier) should never have a fallthru edge. */
1788 else if (JUMP_P (q) && any_uncondjump_p (q))
1789 return;
1791 /* Selectively unlink the sequence. */
1792 if (q != PREV_INSN (BB_HEAD (c)))
1793 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1795 e->flags |= EDGE_FALLTHRU;
1798 /* Should move basic block BB after basic block AFTER. NIY. */
1800 static bool
1801 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1802 basic_block after ATTRIBUTE_UNUSED)
1804 return false;
1807 /* Locate the last bb in the same partition as START_BB. */
1809 static basic_block
1810 last_bb_in_partition (basic_block start_bb)
1812 basic_block bb;
1813 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1815 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1816 return bb;
1818 /* Return bb before the exit block. */
1819 return bb->prev_bb;
1822 /* Split a (typically critical) edge. Return the new block.
1823 The edge must not be abnormal.
1825 ??? The code generally expects to be called on critical edges.
1826 The case of a block ending in an unconditional jump to a
1827 block with multiple predecessors is not handled optimally. */
1829 static basic_block
1830 rtl_split_edge (edge edge_in)
1832 basic_block bb, new_bb;
1833 rtx_insn *before;
1835 /* Abnormal edges cannot be split. */
1836 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1838 /* We are going to place the new block in front of edge destination.
1839 Avoid existence of fallthru predecessors. */
1840 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1842 edge e = find_fallthru_edge (edge_in->dest->preds);
1844 if (e)
1845 force_nonfallthru (e);
1848 /* Create the basic block note. */
1849 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1850 before = BB_HEAD (edge_in->dest);
1851 else
1852 before = NULL;
1854 /* If this is a fall through edge to the exit block, the blocks might be
1855 not adjacent, and the right place is after the source. */
1856 if ((edge_in->flags & EDGE_FALLTHRU)
1857 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1859 before = NEXT_INSN (BB_END (edge_in->src));
1860 bb = create_basic_block (before, NULL, edge_in->src);
1861 BB_COPY_PARTITION (bb, edge_in->src);
1863 else
1865 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1867 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1868 BB_COPY_PARTITION (bb, edge_in->dest);
1870 else
1872 basic_block after = edge_in->dest->prev_bb;
1873 /* If this is post-bb reordering, and the edge crosses a partition
1874 boundary, the new block needs to be inserted in the bb chain
1875 at the end of the src partition (since we put the new bb into
1876 that partition, see below). Otherwise we may end up creating
1877 an extra partition crossing in the chain, which is illegal.
1878 It can't go after the src, because src may have a fall-through
1879 to a different block. */
1880 if (crtl->bb_reorder_complete
1881 && (edge_in->flags & EDGE_CROSSING))
1883 after = last_bb_in_partition (edge_in->src);
1884 before = get_last_bb_insn (after);
1885 /* The instruction following the last bb in partition should
1886 be a barrier, since it cannot end in a fall-through. */
1887 gcc_checking_assert (BARRIER_P (before));
1888 before = NEXT_INSN (before);
1890 bb = create_basic_block (before, NULL, after);
1891 /* Put the split bb into the src partition, to avoid creating
1892 a situation where a cold bb dominates a hot bb, in the case
1893 where src is cold and dest is hot. The src will dominate
1894 the new bb (whereas it might not have dominated dest). */
1895 BB_COPY_PARTITION (bb, edge_in->src);
1899 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1901 /* Can't allow a region crossing edge to be fallthrough. */
1902 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1903 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1905 new_bb = force_nonfallthru (single_succ_edge (bb));
1906 gcc_assert (!new_bb);
1909 /* For non-fallthru edges, we must adjust the predecessor's
1910 jump instruction to target our new block. */
1911 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1913 edge redirected = redirect_edge_and_branch (edge_in, bb);
1914 gcc_assert (redirected);
1916 else
1918 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1920 /* For asm goto even splitting of fallthru edge might
1921 need insn patching, as other labels might point to the
1922 old label. */
1923 rtx_insn *last = BB_END (edge_in->src);
1924 if (last
1925 && JUMP_P (last)
1926 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1927 && (extract_asm_operands (PATTERN (last))
1928 || JUMP_LABEL (last) == before)
1929 && patch_jump_insn (last, before, bb))
1930 df_set_bb_dirty (edge_in->src);
1932 redirect_edge_succ (edge_in, bb);
1935 return bb;
1938 /* Queue instructions for insertion on an edge between two basic blocks.
1939 The new instructions and basic blocks (if any) will not appear in the
1940 CFG until commit_edge_insertions is called. */
1942 void
1943 insert_insn_on_edge (rtx pattern, edge e)
1945 /* We cannot insert instructions on an abnormal critical edge.
1946 It will be easier to find the culprit if we die now. */
1947 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1949 if (e->insns.r == NULL_RTX)
1950 start_sequence ();
1951 else
1952 push_to_sequence (e->insns.r);
1954 emit_insn (pattern);
1956 e->insns.r = get_insns ();
1957 end_sequence ();
1960 /* Update the CFG for the instructions queued on edge E. */
1962 void
1963 commit_one_edge_insertion (edge e)
1965 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1966 basic_block bb;
1968 /* Pull the insns off the edge now since the edge might go away. */
1969 insns = e->insns.r;
1970 e->insns.r = NULL;
1972 /* Figure out where to put these insns. If the destination has
1973 one predecessor, insert there. Except for the exit block. */
1974 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1976 bb = e->dest;
1978 /* Get the location correct wrt a code label, and "nice" wrt
1979 a basic block note, and before everything else. */
1980 tmp = BB_HEAD (bb);
1981 if (LABEL_P (tmp))
1982 tmp = NEXT_INSN (tmp);
1983 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1984 tmp = NEXT_INSN (tmp);
1985 if (tmp == BB_HEAD (bb))
1986 before = tmp;
1987 else if (tmp)
1988 after = PREV_INSN (tmp);
1989 else
1990 after = get_last_insn ();
1993 /* If the source has one successor and the edge is not abnormal,
1994 insert there. Except for the entry block.
1995 Don't do this if the predecessor ends in a jump other than
1996 unconditional simple jump. E.g. for asm goto that points all
1997 its labels at the fallthru basic block, we can't insert instructions
1998 before the asm goto, as the asm goto can have various of side effects,
1999 and can't emit instructions after the asm goto, as it must end
2000 the basic block. */
2001 else if ((e->flags & EDGE_ABNORMAL) == 0
2002 && single_succ_p (e->src)
2003 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2004 && (!JUMP_P (BB_END (e->src))
2005 || simplejump_p (BB_END (e->src))))
2007 bb = e->src;
2009 /* It is possible to have a non-simple jump here. Consider a target
2010 where some forms of unconditional jumps clobber a register. This
2011 happens on the fr30 for example.
2013 We know this block has a single successor, so we can just emit
2014 the queued insns before the jump. */
2015 if (JUMP_P (BB_END (bb)))
2016 before = BB_END (bb);
2017 else
2019 /* We'd better be fallthru, or we've lost track of what's what. */
2020 gcc_assert (e->flags & EDGE_FALLTHRU);
2022 after = BB_END (bb);
2026 /* Otherwise we must split the edge. */
2027 else
2029 bb = split_edge (e);
2031 /* If E crossed a partition boundary, we needed to make bb end in
2032 a region-crossing jump, even though it was originally fallthru. */
2033 if (JUMP_P (BB_END (bb)))
2034 before = BB_END (bb);
2035 else
2036 after = BB_END (bb);
2039 /* Now that we've found the spot, do the insertion. */
2040 if (before)
2042 emit_insn_before_noloc (insns, before, bb);
2043 last = prev_nonnote_insn (before);
2045 else
2046 last = emit_insn_after_noloc (insns, after, bb);
2048 if (returnjump_p (last))
2050 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2051 This is not currently a problem because this only happens
2052 for the (single) epilogue, which already has a fallthru edge
2053 to EXIT. */
2055 e = single_succ_edge (bb);
2056 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2057 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2059 e->flags &= ~EDGE_FALLTHRU;
2060 emit_barrier_after (last);
2062 if (before)
2063 delete_insn (before);
2065 else
2066 gcc_assert (!JUMP_P (last));
2069 /* Update the CFG for all queued instructions. */
2071 void
2072 commit_edge_insertions (void)
2074 basic_block bb;
2076 /* Optimization passes that invoke this routine can cause hot blocks
2077 previously reached by both hot and cold blocks to become dominated only
2078 by cold blocks. This will cause the verification below to fail,
2079 and lead to now cold code in the hot section. In some cases this
2080 may only be visible after newly unreachable blocks are deleted,
2081 which will be done by fixup_partitions. */
2082 fixup_partitions ();
2084 checking_verify_flow_info ();
2086 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2087 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2089 edge e;
2090 edge_iterator ei;
2092 FOR_EACH_EDGE (e, ei, bb->succs)
2093 if (e->insns.r)
2094 commit_one_edge_insertion (e);
2099 /* Print out RTL-specific basic block information (live information
2100 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2101 documented in dumpfile.h. */
2103 static void
2104 rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2106 char *s_indent;
2108 s_indent = (char *) alloca ((size_t) indent + 1);
2109 memset (s_indent, ' ', (size_t) indent);
2110 s_indent[indent] = '\0';
2112 if (df && (flags & TDF_DETAILS))
2114 df_dump_top (bb, outf);
2115 putc ('\n', outf);
2118 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2120 rtx_insn *last = BB_END (bb);
2121 if (last)
2122 last = NEXT_INSN (last);
2123 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2125 if (flags & TDF_DETAILS)
2126 df_dump_insn_top (insn, outf);
2127 if (! (flags & TDF_SLIM))
2128 print_rtl_single (outf, insn);
2129 else
2130 dump_insn_slim (outf, insn);
2131 if (flags & TDF_DETAILS)
2132 df_dump_insn_bottom (insn, outf);
2136 if (df && (flags & TDF_DETAILS))
2138 df_dump_bottom (bb, outf);
2139 putc ('\n', outf);
2144 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2145 for the start of each basic block. FLAGS are the TDF_* masks documented
2146 in dumpfile.h. */
2148 void
2149 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2151 const rtx_insn *tmp_rtx;
2152 if (rtx_first == 0)
2153 fprintf (outf, "(nil)\n");
2154 else
2156 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2157 int max_uid = get_max_uid ();
2158 basic_block *start = XCNEWVEC (basic_block, max_uid);
2159 basic_block *end = XCNEWVEC (basic_block, max_uid);
2160 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2161 basic_block bb;
2163 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2164 insns, but the CFG is not maintained so the basic block info
2165 is not reliable. Therefore it's omitted from the dumps. */
2166 if (! (cfun->curr_properties & PROP_cfg))
2167 flags &= ~TDF_BLOCKS;
2169 if (df)
2170 df_dump_start (outf);
2172 if (flags & TDF_BLOCKS)
2174 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2176 rtx_insn *x;
2178 start[INSN_UID (BB_HEAD (bb))] = bb;
2179 end[INSN_UID (BB_END (bb))] = bb;
2180 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2182 enum bb_state state = IN_MULTIPLE_BB;
2184 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2185 state = IN_ONE_BB;
2186 in_bb_p[INSN_UID (x)] = state;
2188 if (x == BB_END (bb))
2189 break;
2194 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2196 if (flags & TDF_BLOCKS)
2198 bb = start[INSN_UID (tmp_rtx)];
2199 if (bb != NULL)
2201 dump_bb_info (outf, bb, 0, dump_flags, true, false);
2202 if (df && (flags & TDF_DETAILS))
2203 df_dump_top (bb, outf);
2206 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2207 && !NOTE_P (tmp_rtx)
2208 && !BARRIER_P (tmp_rtx))
2209 fprintf (outf, ";; Insn is not within a basic block\n");
2210 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2211 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2214 if (flags & TDF_DETAILS)
2215 df_dump_insn_top (tmp_rtx, outf);
2216 if (! (flags & TDF_SLIM))
2217 print_rtl_single (outf, tmp_rtx);
2218 else
2219 dump_insn_slim (outf, tmp_rtx);
2220 if (flags & TDF_DETAILS)
2221 df_dump_insn_bottom (tmp_rtx, outf);
2223 if (flags & TDF_BLOCKS)
2225 bb = end[INSN_UID (tmp_rtx)];
2226 if (bb != NULL)
2228 dump_bb_info (outf, bb, 0, dump_flags, false, true);
2229 if (df && (flags & TDF_DETAILS))
2230 df_dump_bottom (bb, outf);
2231 putc ('\n', outf);
2236 free (start);
2237 free (end);
2238 free (in_bb_p);
2242 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2244 void
2245 update_br_prob_note (basic_block bb)
2247 rtx note;
2248 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2249 return;
2250 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2251 if (!note
2252 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2253 return;
2254 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2257 /* Get the last insn associated with block BB (that includes barriers and
2258 tablejumps after BB). */
2259 rtx_insn *
2260 get_last_bb_insn (basic_block bb)
2262 rtx_jump_table_data *table;
2263 rtx_insn *tmp;
2264 rtx_insn *end = BB_END (bb);
2266 /* Include any jump table following the basic block. */
2267 if (tablejump_p (end, NULL, &table))
2268 end = table;
2270 /* Include any barriers that may follow the basic block. */
2271 tmp = next_nonnote_insn_bb (end);
2272 while (tmp && BARRIER_P (tmp))
2274 end = tmp;
2275 tmp = next_nonnote_insn_bb (end);
2278 return end;
2281 /* Add all BBs reachable from entry via hot paths into the SET. */
2283 void
2284 find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2286 auto_vec<basic_block, 64> worklist;
2288 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2289 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2291 while (worklist.length () > 0)
2293 basic_block bb = worklist.pop ();
2294 edge_iterator ei;
2295 edge e;
2297 FOR_EACH_EDGE (e, ei, bb->succs)
2298 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2299 && !set->add (e->dest))
2300 worklist.safe_push (e->dest);
2304 /* Sanity check partition hotness to ensure that basic blocks in
2305   the cold partition don't dominate basic blocks in the hot partition.
2306 If FLAG_ONLY is true, report violations as errors. Otherwise
2307 re-mark the dominated blocks as cold, since this is run after
2308 cfg optimizations that may make hot blocks previously reached
2309 by both hot and cold blocks now only reachable along cold paths. */
2311 static vec<basic_block>
2312 find_partition_fixes (bool flag_only)
2314 basic_block bb;
2315 vec<basic_block> bbs_in_cold_partition = vNULL;
2316 vec<basic_block> bbs_to_fix = vNULL;
2317 hash_set<basic_block> set;
2319 /* Callers check this. */
2320 gcc_checking_assert (crtl->has_bb_partition);
2322 find_bbs_reachable_by_hot_paths (&set);
2324 FOR_EACH_BB_FN (bb, cfun)
2325 if (!set.contains (bb)
2326 && BB_PARTITION (bb) != BB_COLD_PARTITION)
2328 if (flag_only)
2329 error ("non-cold basic block %d reachable only "
2330 "by paths crossing the cold partition", bb->index);
2331 else
2332 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2333 bbs_to_fix.safe_push (bb);
2334 bbs_in_cold_partition.safe_push (bb);
2337 return bbs_to_fix;
2340 /* Perform cleanup on the hot/cold bb partitioning after optimization
2341 passes that modify the cfg. */
2343 void
2344 fixup_partitions (void)
2346 basic_block bb;
2348 if (!crtl->has_bb_partition)
2349 return;
2351 /* Delete any blocks that became unreachable and weren't
2352 already cleaned up, for example during edge forwarding
2353 and convert_jumps_to_returns. This will expose more
2354 opportunities for fixing the partition boundaries here.
2355 Also, the calculation of the dominance graph during verification
2356 will assert if there are unreachable nodes. */
2357 delete_unreachable_blocks ();
2359 /* If there are partitions, do a sanity check on them: A basic block in
2360   a cold partition cannot dominate a basic block in a hot partition.
2361 Fixup any that now violate this requirement, as a result of edge
2362 forwarding and unreachable block deletion.  */
2363 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2365 /* Do the partition fixup after all necessary blocks have been converted to
2366 cold, so that we only update the region crossings the minimum number of
2367 places, which can require forcing edges to be non fallthru. */
2368 while (! bbs_to_fix.is_empty ())
2370 bb = bbs_to_fix.pop ();
2371 fixup_new_cold_bb (bb);
2375 /* Verify, in the basic block chain, that there is at most one switch
2376 between hot/cold partitions. This condition will not be true until
2377 after reorder_basic_blocks is called. */
2379 static int
2380 verify_hot_cold_block_grouping (void)
2382 basic_block bb;
2383 int err = 0;
2384 bool switched_sections = false;
2385 int current_partition = BB_UNPARTITIONED;
2387 /* Even after bb reordering is complete, we go into cfglayout mode
2388 again (in compgoto). Ensure we don't call this before going back
2389 into linearized RTL when any layout fixes would have been committed. */
2390 if (!crtl->bb_reorder_complete
2391 || current_ir_type () != IR_RTL_CFGRTL)
2392 return err;
2394 FOR_EACH_BB_FN (bb, cfun)
2396 if (current_partition != BB_UNPARTITIONED
2397 && BB_PARTITION (bb) != current_partition)
2399 if (switched_sections)
2401 error ("multiple hot/cold transitions found (bb %i)",
2402 bb->index);
2403 err = 1;
2405 else
2406 switched_sections = true;
2408 if (!crtl->has_bb_partition)
2409 error ("partition found but function partition flag not set");
2411 current_partition = BB_PARTITION (bb);
2414 return err;
2418 /* Perform several checks on the edges out of each block, such as
2419 the consistency of the branch probabilities, the correctness
2420 of hot/cold partition crossing edges, and the number of expected
2421 successor edges. Also verify that the dominance relationship
2422 between hot/cold blocks is sane. */
2424 static int
2425 rtl_verify_edges (void)
2427 int err = 0;
2428 basic_block bb;
2430 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2432 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2433 int n_eh = 0, n_abnormal = 0;
2434 edge e, fallthru = NULL;
2435 edge_iterator ei;
2436 rtx note;
2437 bool has_crossing_edge = false;
2439 if (JUMP_P (BB_END (bb))
2440 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2441 && EDGE_COUNT (bb->succs) >= 2
2442 && any_condjump_p (BB_END (bb)))
2444 if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2446 if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2448 error ("verify_flow_info: "
2449 "REG_BR_PROB is set but cfg probability is not");
2450 err = 1;
2453 else if (XINT (note, 0)
2454 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2455 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2457 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2458 XINT (note, 0),
2459 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2460 err = 1;
2464 FOR_EACH_EDGE (e, ei, bb->succs)
2466 bool is_crossing;
2468 if (e->flags & EDGE_FALLTHRU)
2469 n_fallthru++, fallthru = e;
2471 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2472 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2473 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2474 has_crossing_edge |= is_crossing;
2475 if (e->flags & EDGE_CROSSING)
2477 if (!is_crossing)
2479 error ("EDGE_CROSSING incorrectly set across same section");
2480 err = 1;
2482 if (e->flags & EDGE_FALLTHRU)
2484 error ("fallthru edge crosses section boundary in bb %i",
2485 e->src->index);
2486 err = 1;
2488 if (e->flags & EDGE_EH)
2490 error ("EH edge crosses section boundary in bb %i",
2491 e->src->index);
2492 err = 1;
2494 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2496 error ("No region crossing jump at section boundary in bb %i",
2497 bb->index);
2498 err = 1;
2501 else if (is_crossing)
2503 error ("EDGE_CROSSING missing across section boundary");
2504 err = 1;
2507 if ((e->flags & ~(EDGE_DFS_BACK
2508 | EDGE_CAN_FALLTHRU
2509 | EDGE_IRREDUCIBLE_LOOP
2510 | EDGE_LOOP_EXIT
2511 | EDGE_CROSSING
2512 | EDGE_PRESERVE)) == 0)
2513 n_branch++;
2515 if (e->flags & EDGE_ABNORMAL_CALL)
2516 n_abnormal_call++;
2518 if (e->flags & EDGE_SIBCALL)
2519 n_sibcall++;
2521 if (e->flags & EDGE_EH)
2522 n_eh++;
2524 if (e->flags & EDGE_ABNORMAL)
2525 n_abnormal++;
2528 if (!has_crossing_edge
2529 && JUMP_P (BB_END (bb))
2530 && CROSSING_JUMP_P (BB_END (bb)))
2532 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2533 error ("Region crossing jump across same section in bb %i",
2534 bb->index);
2535 err = 1;
2538 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2540 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2541 err = 1;
2543 if (n_eh > 1)
2545 error ("too many exception handling edges in bb %i", bb->index);
2546 err = 1;
2548 if (n_branch
2549 && (!JUMP_P (BB_END (bb))
2550 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2551 || any_condjump_p (BB_END (bb))))))
2553 error ("too many outgoing branch edges from bb %i", bb->index);
2554 err = 1;
2556 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2558 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2559 err = 1;
2561 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2563 error ("wrong number of branch edges after unconditional jump"
2564 " in bb %i", bb->index);
2565 err = 1;
2567 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2568 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2570 error ("wrong amount of branch edges after conditional jump"
2571 " in bb %i", bb->index);
2572 err = 1;
2574 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2576 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2577 err = 1;
2579 if (n_sibcall && !CALL_P (BB_END (bb)))
2581 error ("sibcall edges for non-call insn in bb %i", bb->index);
2582 err = 1;
2584 if (n_abnormal > n_eh
2585 && !(CALL_P (BB_END (bb))
2586 && n_abnormal == n_abnormal_call + n_sibcall)
2587 && (!JUMP_P (BB_END (bb))
2588 || any_condjump_p (BB_END (bb))
2589 || any_uncondjump_p (BB_END (bb))))
2591 error ("abnormal edges for no purpose in bb %i", bb->index);
2592 err = 1;
2596 /* If there are partitions, do a sanity check on them: A basic block in
2597   a cold partition cannot dominate a basic block in a hot partition.  */
2598 if (crtl->has_bb_partition && !err)
2600 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2601 err = !bbs_to_fix.is_empty ();
2604 /* Clean up. */
2605 return err;
2608 /* Checks on the instructions within blocks. Currently checks that each
2609 block starts with a basic block note, and that basic block notes and
2610 control flow jumps are not found in the middle of the block. */
2612 static int
2613 rtl_verify_bb_insns (void)
2615 rtx_insn *x;
2616 int err = 0;
2617 basic_block bb;
2619 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2621 /* Now check the header of basic
2622 block. It ought to contain optional CODE_LABEL followed
2623 by NOTE_BASIC_BLOCK. */
2624 x = BB_HEAD (bb);
2625 if (LABEL_P (x))
2627 if (BB_END (bb) == x)
2629 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2630 bb->index);
2631 err = 1;
2634 x = NEXT_INSN (x);
2637 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2639 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2640 bb->index);
2641 err = 1;
2644 if (BB_END (bb) == x)
2645 /* Do checks for empty blocks here. */
2647 else
2648 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2650 if (NOTE_INSN_BASIC_BLOCK_P (x))
2652 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2653 INSN_UID (x), bb->index);
2654 err = 1;
2657 if (x == BB_END (bb))
2658 break;
2660 if (control_flow_insn_p (x))
2662 error ("in basic block %d:", bb->index);
2663 fatal_insn ("flow control insn inside a basic block", x);
2668 /* Clean up. */
2669 return err;
2672 /* Verify that block pointers for instructions in basic blocks, headers and
2673 footers are set appropriately. */
2675 static int
2676 rtl_verify_bb_pointers (void)
2678 int err = 0;
2679 basic_block bb;
2681 /* Check the general integrity of the basic blocks. */
2682 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2684 rtx_insn *insn;
2686 if (!(bb->flags & BB_RTL))
2688 error ("BB_RTL flag not set for block %d", bb->index);
2689 err = 1;
2692 FOR_BB_INSNS (bb, insn)
2693 if (BLOCK_FOR_INSN (insn) != bb)
2695 error ("insn %d basic block pointer is %d, should be %d",
2696 INSN_UID (insn),
2697 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2698 bb->index);
2699 err = 1;
2702 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2703 if (!BARRIER_P (insn)
2704 && BLOCK_FOR_INSN (insn) != NULL)
2706 error ("insn %d in header of bb %d has non-NULL basic block",
2707 INSN_UID (insn), bb->index);
2708 err = 1;
2710 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2711 if (!BARRIER_P (insn)
2712 && BLOCK_FOR_INSN (insn) != NULL)
2714 error ("insn %d in footer of bb %d has non-NULL basic block",
2715 INSN_UID (insn), bb->index);
2716 err = 1;
2720 /* Clean up. */
2721 return err;
2724 /* Verify the CFG and RTL consistency common for both underlying RTL and
2725 cfglayout RTL.
2727 Currently it does following checks:
2729 - overlapping of basic blocks
2730 - insns with wrong BLOCK_FOR_INSN pointers
2731 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2732 - tails of basic blocks (ensure that boundary is necessary)
2733 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2734 and NOTE_INSN_BASIC_BLOCK
2735 - verify that no fall_thru edge crosses hot/cold partition boundaries
2736 - verify that there are no pending RTL branch predictions
2737 - verify that hot blocks are not dominated by cold blocks
2739 In future it can be extended check a lot of other stuff as well
2740 (reachability of basic blocks, life information, etc. etc.). */
2742 static int
2743 rtl_verify_flow_info_1 (void)
2745 int err = 0;
2747 err |= rtl_verify_bb_pointers ();
2749 err |= rtl_verify_bb_insns ();
2751 err |= rtl_verify_edges ();
2753 return err;
2756 /* Walk the instruction chain and verify that bb head/end pointers
2757 are correct, and that instructions are in exactly one bb and have
2758 correct block pointers. */
2760 static int
2761 rtl_verify_bb_insn_chain (void)
2763 basic_block bb;
2764 int err = 0;
2765 rtx_insn *x;
2766 rtx_insn *last_head = get_last_insn ();
2767 basic_block *bb_info;
2768 const int max_uid = get_max_uid ();
2770 bb_info = XCNEWVEC (basic_block, max_uid);
2772 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2774 rtx_insn *head = BB_HEAD (bb);
2775 rtx_insn *end = BB_END (bb);
2777 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2779 /* Verify the end of the basic block is in the INSN chain. */
2780 if (x == end)
2781 break;
2783 /* And that the code outside of basic blocks has NULL bb field. */
2784 if (!BARRIER_P (x)
2785 && BLOCK_FOR_INSN (x) != NULL)
2787 error ("insn %d outside of basic blocks has non-NULL bb field",
2788 INSN_UID (x));
2789 err = 1;
2793 if (!x)
2795 error ("end insn %d for block %d not found in the insn stream",
2796 INSN_UID (end), bb->index);
2797 err = 1;
2800 /* Work backwards from the end to the head of the basic block
2801 to verify the head is in the RTL chain. */
2802 for (; x != NULL_RTX; x = PREV_INSN (x))
2804 /* While walking over the insn chain, verify insns appear
2805 in only one basic block. */
2806 if (bb_info[INSN_UID (x)] != NULL)
2808 error ("insn %d is in multiple basic blocks (%d and %d)",
2809 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2810 err = 1;
2813 bb_info[INSN_UID (x)] = bb;
2815 if (x == head)
2816 break;
2818 if (!x)
2820 error ("head insn %d for block %d not found in the insn stream",
2821 INSN_UID (head), bb->index);
2822 err = 1;
2825 last_head = PREV_INSN (x);
2828 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2830 /* Check that the code before the first basic block has NULL
2831 bb field. */
2832 if (!BARRIER_P (x)
2833 && BLOCK_FOR_INSN (x) != NULL)
2835 error ("insn %d outside of basic blocks has non-NULL bb field",
2836 INSN_UID (x));
2837 err = 1;
2840 free (bb_info);
2842 return err;
2845 /* Verify that fallthru edges point to adjacent blocks in layout order and
2846 that barriers exist after non-fallthru blocks. */
2848 static int
2849 rtl_verify_fallthru (void)
2851 basic_block bb;
2852 int err = 0;
2854 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2856 edge e;
2858 e = find_fallthru_edge (bb->succs);
2859 if (!e)
2861 rtx_insn *insn;
2863 /* Ensure existence of barrier in BB with no fallthru edges. */
2864 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2866 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2868 error ("missing barrier after block %i", bb->index);
2869 err = 1;
2870 break;
2872 if (BARRIER_P (insn))
2873 break;
2876 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2877 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2879 rtx_insn *insn;
2881 if (e->src->next_bb != e->dest)
2883 error
2884 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2885 e->src->index, e->dest->index);
2886 err = 1;
2888 else
2889 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2890 insn = NEXT_INSN (insn))
2891 if (BARRIER_P (insn) || INSN_P (insn))
2893 error ("verify_flow_info: Incorrect fallthru %i->%i",
2894 e->src->index, e->dest->index);
2895 fatal_insn ("wrong insn in the fallthru edge", insn);
2896 err = 1;
2901 return err;
2904 /* Verify that blocks are laid out in consecutive order. While walking the
2905 instructions, verify that all expected instructions are inside the basic
2906 blocks, and that all returns are followed by barriers. */
2908 static int
2909 rtl_verify_bb_layout (void)
2911 basic_block bb;
2912 int err = 0;
2913 rtx_insn *x;
2914 int num_bb_notes;
2915 rtx_insn * const rtx_first = get_insns ();
2916 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2918 num_bb_notes = 0;
2919 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2921 for (x = rtx_first; x; x = NEXT_INSN (x))
2923 if (NOTE_INSN_BASIC_BLOCK_P (x))
2925 bb = NOTE_BASIC_BLOCK (x);
2927 num_bb_notes++;
2928 if (bb != last_bb_seen->next_bb)
2929 internal_error ("basic blocks not laid down consecutively");
2931 curr_bb = last_bb_seen = bb;
2934 if (!curr_bb)
2936 switch (GET_CODE (x))
2938 case BARRIER:
2939 case NOTE:
2940 break;
2942 case CODE_LABEL:
2943 /* An ADDR_VEC is placed outside any basic block. */
2944 if (NEXT_INSN (x)
2945 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2946 x = NEXT_INSN (x);
2948 /* But in any case, non-deletable labels can appear anywhere. */
2949 break;
2951 default:
2952 fatal_insn ("insn outside basic block", x);
2956 if (JUMP_P (x)
2957 && returnjump_p (x) && ! condjump_p (x)
2958 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2959 fatal_insn ("return not followed by barrier", x);
2961 if (curr_bb && x == BB_END (curr_bb))
2962 curr_bb = NULL;
2965 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2966 internal_error
2967 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2968 num_bb_notes, n_basic_blocks_for_fn (cfun));
2970 return err;
2973 /* Verify the CFG and RTL consistency common for both underlying RTL and
2974 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2976 Currently it does following checks:
2977 - all checks of rtl_verify_flow_info_1
2978 - test head/end pointers
2979 - check that blocks are laid out in consecutive order
2980 - check that all insns are in the basic blocks
2981 (except the switch handling code, barriers and notes)
2982 - check that all returns are followed by barriers
2983 - check that all fallthru edge points to the adjacent blocks
2984 - verify that there is a single hot/cold partition boundary after bbro */
2986 static int
2987 rtl_verify_flow_info (void)
2989 int err = 0;
2991 err |= rtl_verify_flow_info_1 ();
2993 err |= rtl_verify_bb_insn_chain ();
2995 err |= rtl_verify_fallthru ();
2997 err |= rtl_verify_bb_layout ();
2999 err |= verify_hot_cold_block_grouping ();
3001 return err;
3004 /* Assume that the preceding pass has possibly eliminated jump instructions
3005 or converted the unconditional jumps. Eliminate the edges from CFG.
3006 Return true if any edges are eliminated. */
3008 bool
3009 purge_dead_edges (basic_block bb)
3011 edge e;
3012 rtx_insn *insn = BB_END (bb);
3013 rtx note;
3014 bool purged = false;
3015 bool found;
3016 edge_iterator ei;
3018 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3020 insn = PREV_INSN (insn);
3021 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3023 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3024 if (NONJUMP_INSN_P (insn)
3025 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3027 rtx eqnote;
3029 if (! may_trap_p (PATTERN (insn))
3030 || ((eqnote = find_reg_equal_equiv_note (insn))
3031 && ! may_trap_p (XEXP (eqnote, 0))))
3032 remove_note (insn, note);
3035 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3036 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3038 bool remove = false;
3040 /* There are three types of edges we need to handle correctly here: EH
3041 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3042 latter can appear when nonlocal gotos are used. */
3043 if (e->flags & EDGE_ABNORMAL_CALL)
3045 if (!CALL_P (insn))
3046 remove = true;
3047 else if (can_nonlocal_goto (insn))
3049 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3051 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3053 else
3054 remove = true;
3056 else if (e->flags & EDGE_EH)
3057 remove = !can_throw_internal (insn);
3059 if (remove)
3061 remove_edge (e);
3062 df_set_bb_dirty (bb);
3063 purged = true;
3065 else
3066 ei_next (&ei);
3069 if (JUMP_P (insn))
3071 rtx note;
3072 edge b,f;
3073 edge_iterator ei;
3075 /* We do care only about conditional jumps and simplejumps. */
3076 if (!any_condjump_p (insn)
3077 && !returnjump_p (insn)
3078 && !simplejump_p (insn))
3079 return purged;
3081 /* Branch probability/prediction notes are defined only for
3082 condjumps. We've possibly turned condjump into simplejump. */
3083 if (simplejump_p (insn))
3085 note = find_reg_note (insn, REG_BR_PROB, NULL);
3086 if (note)
3087 remove_note (insn, note);
3088 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3089 remove_note (insn, note);
3092 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3094 /* Avoid abnormal flags to leak from computed jumps turned
3095 into simplejumps. */
3097 e->flags &= ~EDGE_ABNORMAL;
3099 /* See if this edge is one we should keep. */
3100 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3101 /* A conditional jump can fall through into the next
3102 block, so we should keep the edge. */
3104 ei_next (&ei);
3105 continue;
3107 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3108 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3109 /* If the destination block is the target of the jump,
3110 keep the edge. */
3112 ei_next (&ei);
3113 continue;
3115 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3116 && returnjump_p (insn))
3117 /* If the destination block is the exit block, and this
3118 instruction is a return, then keep the edge. */
3120 ei_next (&ei);
3121 continue;
3123 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3124 /* Keep the edges that correspond to exceptions thrown by
3125 this instruction and rematerialize the EDGE_ABNORMAL
3126 flag we just cleared above. */
3128 e->flags |= EDGE_ABNORMAL;
3129 ei_next (&ei);
3130 continue;
3133 /* We do not need this edge. */
3134 df_set_bb_dirty (bb);
3135 purged = true;
3136 remove_edge (e);
3139 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3140 return purged;
3142 if (dump_file)
3143 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3145 if (!optimize)
3146 return purged;
3148 /* Redistribute probabilities. */
3149 if (single_succ_p (bb))
3151 single_succ_edge (bb)->probability = profile_probability::always ();
3153 else
3155 note = find_reg_note (insn, REG_BR_PROB, NULL);
3156 if (!note)
3157 return purged;
3159 b = BRANCH_EDGE (bb);
3160 f = FALLTHRU_EDGE (bb);
3161 b->probability = profile_probability::from_reg_br_prob_note
3162 (XINT (note, 0));
3163 f->probability = b->probability.invert ();
3166 return purged;
3168 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3170 /* First, there should not be any EH or ABCALL edges resulting
3171 from non-local gotos and the like. If there were, we shouldn't
3172 have created the sibcall in the first place. Second, there
3173 should of course never have been a fallthru edge. */
3174 gcc_assert (single_succ_p (bb));
3175 gcc_assert (single_succ_edge (bb)->flags
3176 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3178 return 0;
3181 /* If we don't see a jump insn, we don't know exactly why the block would
3182 have been broken at this point. Look for a simple, non-fallthru edge,
3183 as these are only created by conditional branches. If we find such an
3184 edge we know that there used to be a jump here and can then safely
3185 remove all non-fallthru edges. */
3186 found = false;
3187 FOR_EACH_EDGE (e, ei, bb->succs)
3188 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3190 found = true;
3191 break;
3194 if (!found)
3195 return purged;
3197 /* Remove all but the fake and fallthru edges. The fake edge may be
3198 the only successor for this block in the case of noreturn
3199 calls. */
3200 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3202 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3204 df_set_bb_dirty (bb);
3205 remove_edge (e);
3206 purged = true;
3208 else
3209 ei_next (&ei);
3212 gcc_assert (single_succ_p (bb));
3214 single_succ_edge (bb)->probability = profile_probability::always ();
3216 if (dump_file)
3217 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3218 bb->index);
3219 return purged;
3222 /* Search all basic blocks for potentially dead edges and purge them. Return
3223 true if some edge has been eliminated. */
3225 bool
3226 purge_all_dead_edges (void)
3228 int purged = false;
3229 basic_block bb;
3231 FOR_EACH_BB_FN (bb, cfun)
3233 bool purged_here = purge_dead_edges (bb);
3235 purged |= purged_here;
3238 return purged;
3241 /* This is used by a few passes that emit some instructions after abnormal
3242 calls, moving the basic block's end, while they in fact do want to emit
3243 them on the fallthru edge. Look for abnormal call edges, find backward
3244 the call in the block and insert the instructions on the edge instead.
3246 Similarly, handle instructions throwing exceptions internally.
3248 Return true when instructions have been found and inserted on edges. */
3250 bool
3251 fixup_abnormal_edges (void)
3253 bool inserted = false;
3254 basic_block bb;
3256 FOR_EACH_BB_FN (bb, cfun)
3258 edge e;
3259 edge_iterator ei;
3261 /* Look for cases we are interested in - calls or instructions causing
3262 exceptions. */
3263 FOR_EACH_EDGE (e, ei, bb->succs)
3264 if ((e->flags & EDGE_ABNORMAL_CALL)
3265 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3266 == (EDGE_ABNORMAL | EDGE_EH)))
3267 break;
3269 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3271 rtx_insn *insn;
3273 /* Get past the new insns generated. Allow notes, as the insns
3274 may be already deleted. */
3275 insn = BB_END (bb);
3276 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3277 && !can_throw_internal (insn)
3278 && insn != BB_HEAD (bb))
3279 insn = PREV_INSN (insn);
3281 if (CALL_P (insn) || can_throw_internal (insn))
3283 rtx_insn *stop, *next;
3285 e = find_fallthru_edge (bb->succs);
3287 stop = NEXT_INSN (BB_END (bb));
3288 BB_END (bb) = insn;
3290 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3292 next = NEXT_INSN (insn);
3293 if (INSN_P (insn))
3295 delete_insn (insn);
3297 /* Sometimes there's still the return value USE.
3298 If it's placed after a trapping call (i.e. that
3299 call is the last insn anyway), we have no fallthru
3300 edge. Simply delete this use and don't try to insert
3301 on the non-existent edge. */
3302 if (GET_CODE (PATTERN (insn)) != USE)
3304 /* We're not deleting it, we're moving it. */
3305 insn->set_undeleted ();
3306 SET_PREV_INSN (insn) = NULL_RTX;
3307 SET_NEXT_INSN (insn) = NULL_RTX;
3309 insert_insn_on_edge (insn, e);
3310 inserted = true;
3313 else if (!BARRIER_P (insn))
3314 set_block_for_insn (insn, NULL);
3318 /* It may be that we don't find any trapping insn. In this
3319 case we discovered quite late that the insn that had been
3320 marked as can_throw_internal in fact couldn't trap at all.
3321 So we should in fact delete the EH edges out of the block. */
3322 else
3323 purge_dead_edges (bb);
3327 return inserted;
3330 /* Cut the insns from FIRST to LAST out of the insns stream. */
3332 rtx_insn *
3333 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3335 rtx_insn *prevfirst = PREV_INSN (first);
3336 rtx_insn *nextlast = NEXT_INSN (last);
3338 SET_PREV_INSN (first) = NULL;
3339 SET_NEXT_INSN (last) = NULL;
3340 if (prevfirst)
3341 SET_NEXT_INSN (prevfirst) = nextlast;
3342 if (nextlast)
3343 SET_PREV_INSN (nextlast) = prevfirst;
3344 else
3345 set_last_insn (prevfirst);
3346 if (!prevfirst)
3347 set_first_insn (nextlast);
3348 return first;
3351 /* Skip over inter-block insns occurring after BB which are typically
3352 associated with BB (e.g., barriers). If there are any such insns,
3353 we return the last one. Otherwise, we return the end of BB. */
3355 static rtx_insn *
3356 skip_insns_after_block (basic_block bb)
3358 rtx_insn *insn, *last_insn, *next_head, *prev;
3360 next_head = NULL;
3361 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3362 next_head = BB_HEAD (bb->next_bb);
3364 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3366 if (insn == next_head)
3367 break;
3369 switch (GET_CODE (insn))
3371 case BARRIER:
3372 last_insn = insn;
3373 continue;
3375 case NOTE:
3376 switch (NOTE_KIND (insn))
3378 case NOTE_INSN_BLOCK_END:
3379 gcc_unreachable ();
3380 continue;
3381 default:
3382 continue;
3383 break;
3385 break;
3387 case CODE_LABEL:
3388 if (NEXT_INSN (insn)
3389 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3391 insn = NEXT_INSN (insn);
3392 last_insn = insn;
3393 continue;
3395 break;
3397 default:
3398 break;
3401 break;
3404 /* It is possible to hit contradictory sequence. For instance:
3406 jump_insn
3407 NOTE_INSN_BLOCK_BEG
3408 barrier
3410 Where barrier belongs to jump_insn, but the note does not. This can be
3411 created by removing the basic block originally following
3412 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3414 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3416 prev = PREV_INSN (insn);
3417 if (NOTE_P (insn))
3418 switch (NOTE_KIND (insn))
3420 case NOTE_INSN_BLOCK_END:
3421 gcc_unreachable ();
3422 break;
3423 case NOTE_INSN_DELETED:
3424 case NOTE_INSN_DELETED_LABEL:
3425 case NOTE_INSN_DELETED_DEBUG_LABEL:
3426 continue;
3427 default:
3428 reorder_insns (insn, insn, last_insn);
3432 return last_insn;
3435 /* Locate or create a label for a given basic block. */
3437 static rtx_insn *
3438 label_for_bb (basic_block bb)
3440 rtx_insn *label = BB_HEAD (bb);
3442 if (!LABEL_P (label))
3444 if (dump_file)
3445 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3447 label = block_label (bb);
3450 return label;
3453 /* Locate the effective beginning and end of the insn chain for each
3454 block, as defined by skip_insns_after_block above. */
3456 static void
3457 record_effective_endpoints (void)
3459 rtx_insn *next_insn;
3460 basic_block bb;
3461 rtx_insn *insn;
3463 for (insn = get_insns ();
3464 insn
3465 && NOTE_P (insn)
3466 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3467 insn = NEXT_INSN (insn))
3468 continue;
3469 /* No basic blocks at all? */
3470 gcc_assert (insn);
3472 if (PREV_INSN (insn))
3473 cfg_layout_function_header =
3474 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3475 else
3476 cfg_layout_function_header = NULL;
3478 next_insn = get_insns ();
3479 FOR_EACH_BB_FN (bb, cfun)
3481 rtx_insn *end;
3483 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3484 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3485 PREV_INSN (BB_HEAD (bb)));
3486 end = skip_insns_after_block (bb);
3487 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3488 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3489 next_insn = NEXT_INSN (BB_END (bb));
3492 cfg_layout_function_footer = next_insn;
3493 if (cfg_layout_function_footer)
3494 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3497 namespace {
3499 const pass_data pass_data_into_cfg_layout_mode =
3501 RTL_PASS, /* type */
3502 "into_cfglayout", /* name */
3503 OPTGROUP_NONE, /* optinfo_flags */
3504 TV_CFG, /* tv_id */
3505 0, /* properties_required */
3506 PROP_cfglayout, /* properties_provided */
3507 0, /* properties_destroyed */
3508 0, /* todo_flags_start */
3509 0, /* todo_flags_finish */
3512 class pass_into_cfg_layout_mode : public rtl_opt_pass
3514 public:
3515 pass_into_cfg_layout_mode (gcc::context *ctxt)
3516 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3519 /* opt_pass methods: */
3520 virtual unsigned int execute (function *)
3522 cfg_layout_initialize (0);
3523 return 0;
3526 }; // class pass_into_cfg_layout_mode
3528 } // anon namespace
3530 rtl_opt_pass *
3531 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3533 return new pass_into_cfg_layout_mode (ctxt);
3536 namespace {
3538 const pass_data pass_data_outof_cfg_layout_mode =
3540 RTL_PASS, /* type */
3541 "outof_cfglayout", /* name */
3542 OPTGROUP_NONE, /* optinfo_flags */
3543 TV_CFG, /* tv_id */
3544 0, /* properties_required */
3545 0, /* properties_provided */
3546 PROP_cfglayout, /* properties_destroyed */
3547 0, /* todo_flags_start */
3548 0, /* todo_flags_finish */
3551 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3553 public:
3554 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3555 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3558 /* opt_pass methods: */
3559 virtual unsigned int execute (function *);
3561 }; // class pass_outof_cfg_layout_mode
3563 unsigned int
3564 pass_outof_cfg_layout_mode::execute (function *fun)
3566 basic_block bb;
3568 FOR_EACH_BB_FN (bb, fun)
3569 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3570 bb->aux = bb->next_bb;
3572 cfg_layout_finalize ();
3574 return 0;
3577 } // anon namespace
3579 rtl_opt_pass *
3580 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3582 return new pass_outof_cfg_layout_mode (ctxt);
3586 /* Link the basic blocks in the correct order, compacting the basic
3587 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3588 function also clears the basic block header and footer fields.
3590 This function is usually called after a pass (e.g. tracer) finishes
3591 some transformations while in cfglayout mode. The required sequence
3592 of the basic blocks is in a linked list along the bb->aux field.
3593 This functions re-links the basic block prev_bb and next_bb pointers
3594 accordingly, and it compacts and renumbers the blocks.
3596 FIXME: This currently works only for RTL, but the only RTL-specific
3597 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3598 to GIMPLE a long time ago, but it doesn't relink the basic block
3599 chain. It could do that (to give better initial RTL) if this function
3600 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3602 void
3603 relink_block_chain (bool stay_in_cfglayout_mode)
3605 basic_block bb, prev_bb;
3606 int index;
3608 /* Maybe dump the re-ordered sequence. */
3609 if (dump_file)
3611 fprintf (dump_file, "Reordered sequence:\n");
3612 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3613 NUM_FIXED_BLOCKS;
3615 bb = (basic_block) bb->aux, index++)
3617 fprintf (dump_file, " %i ", index);
3618 if (get_bb_original (bb))
3619 fprintf (dump_file, "duplicate of %i ",
3620 get_bb_original (bb)->index);
3621 else if (forwarder_block_p (bb)
3622 && !LABEL_P (BB_HEAD (bb)))
3623 fprintf (dump_file, "compensation ");
3624 else
3625 fprintf (dump_file, "bb %i ", bb->index);
3626 fprintf (dump_file, " [%i]\n", bb->frequency);
3630 /* Now reorder the blocks. */
3631 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3632 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3633 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3635 bb->prev_bb = prev_bb;
3636 prev_bb->next_bb = bb;
3638 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3639 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3641 /* Then, clean up the aux fields. */
3642 FOR_ALL_BB_FN (bb, cfun)
3644 bb->aux = NULL;
3645 if (!stay_in_cfglayout_mode)
3646 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3649 /* Maybe reset the original copy tables, they are not valid anymore
3650 when we renumber the basic blocks in compact_blocks. If we are
3651 are going out of cfglayout mode, don't re-allocate the tables. */
3652 if (original_copy_tables_initialized_p ())
3653 free_original_copy_tables ();
3654 if (stay_in_cfglayout_mode)
3655 initialize_original_copy_tables ();
3657 /* Finally, put basic_block_info in the new order. */
3658 compact_blocks ();
3662 /* Given a reorder chain, rearrange the code to match. */
3664 static void
3665 fixup_reorder_chain (void)
3667 basic_block bb;
3668 rtx_insn *insn = NULL;
3670 if (cfg_layout_function_header)
3672 set_first_insn (cfg_layout_function_header);
3673 insn = cfg_layout_function_header;
3674 while (NEXT_INSN (insn))
3675 insn = NEXT_INSN (insn);
3678 /* First do the bulk reordering -- rechain the blocks without regard to
3679 the needed changes to jumps and labels. */
3681 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3682 bb->aux)
3684 if (BB_HEADER (bb))
3686 if (insn)
3687 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3688 else
3689 set_first_insn (BB_HEADER (bb));
3690 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3691 insn = BB_HEADER (bb);
3692 while (NEXT_INSN (insn))
3693 insn = NEXT_INSN (insn);
3695 if (insn)
3696 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3697 else
3698 set_first_insn (BB_HEAD (bb));
3699 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3700 insn = BB_END (bb);
3701 if (BB_FOOTER (bb))
3703 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3704 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3705 while (NEXT_INSN (insn))
3706 insn = NEXT_INSN (insn);
3710 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3711 if (cfg_layout_function_footer)
3712 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3714 while (NEXT_INSN (insn))
3715 insn = NEXT_INSN (insn);
3717 set_last_insn (insn);
3718 if (flag_checking)
3719 verify_insn_chain ();
3721 /* Now add jumps and labels as needed to match the blocks new
3722 outgoing edges. */
3724 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3725 bb->aux)
3727 edge e_fall, e_taken, e;
3728 rtx_insn *bb_end_insn;
3729 rtx ret_label = NULL_RTX;
3730 basic_block nb;
3731 edge_iterator ei;
3733 if (EDGE_COUNT (bb->succs) == 0)
3734 continue;
3736 /* Find the old fallthru edge, and another non-EH edge for
3737 a taken jump. */
3738 e_taken = e_fall = NULL;
3740 FOR_EACH_EDGE (e, ei, bb->succs)
3741 if (e->flags & EDGE_FALLTHRU)
3742 e_fall = e;
3743 else if (! (e->flags & EDGE_EH))
3744 e_taken = e;
3746 bb_end_insn = BB_END (bb);
3747 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3749 ret_label = JUMP_LABEL (bb_end_jump);
3750 if (any_condjump_p (bb_end_jump))
3752 /* This might happen if the conditional jump has side
3753 effects and could therefore not be optimized away.
3754 Make the basic block to end with a barrier in order
3755 to prevent rtl_verify_flow_info from complaining. */
3756 if (!e_fall)
3758 gcc_assert (!onlyjump_p (bb_end_jump)
3759 || returnjump_p (bb_end_jump)
3760 || (e_taken->flags & EDGE_CROSSING));
3761 emit_barrier_after (bb_end_jump);
3762 continue;
3765 /* If the old fallthru is still next, nothing to do. */
3766 if (bb->aux == e_fall->dest
3767 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3768 continue;
3770 /* The degenerated case of conditional jump jumping to the next
3771 instruction can happen for jumps with side effects. We need
3772 to construct a forwarder block and this will be done just
3773 fine by force_nonfallthru below. */
3774 if (!e_taken)
3777 /* There is another special case: if *neither* block is next,
3778 such as happens at the very end of a function, then we'll
3779 need to add a new unconditional jump. Choose the taken
3780 edge based on known or assumed probability. */
3781 else if (bb->aux != e_taken->dest)
3783 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3785 if (note
3786 && profile_probability::from_reg_br_prob_note
3787 (XINT (note, 0)) < profile_probability::even ()
3788 && invert_jump (bb_end_jump,
3789 (e_fall->dest
3790 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3791 ? NULL_RTX
3792 : label_for_bb (e_fall->dest)), 0))
3794 e_fall->flags &= ~EDGE_FALLTHRU;
3795 gcc_checking_assert (could_fall_through
3796 (e_taken->src, e_taken->dest));
3797 e_taken->flags |= EDGE_FALLTHRU;
3798 update_br_prob_note (bb);
3799 e = e_fall, e_fall = e_taken, e_taken = e;
3803 /* If the "jumping" edge is a crossing edge, and the fall
3804 through edge is non-crossing, leave things as they are. */
3805 else if ((e_taken->flags & EDGE_CROSSING)
3806 && !(e_fall->flags & EDGE_CROSSING))
3807 continue;
3809 /* Otherwise we can try to invert the jump. This will
3810 basically never fail, however, keep up the pretense. */
3811 else if (invert_jump (bb_end_jump,
3812 (e_fall->dest
3813 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3814 ? NULL_RTX
3815 : label_for_bb (e_fall->dest)), 0))
3817 e_fall->flags &= ~EDGE_FALLTHRU;
3818 gcc_checking_assert (could_fall_through
3819 (e_taken->src, e_taken->dest));
3820 e_taken->flags |= EDGE_FALLTHRU;
3821 update_br_prob_note (bb);
3822 if (LABEL_NUSES (ret_label) == 0
3823 && single_pred_p (e_taken->dest))
3824 delete_insn (as_a<rtx_insn *> (ret_label));
3825 continue;
3828 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3830 /* If the old fallthru is still next or if
3831 asm goto doesn't have a fallthru (e.g. when followed by
3832 __builtin_unreachable ()), nothing to do. */
3833 if (! e_fall
3834 || bb->aux == e_fall->dest
3835 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3836 continue;
3838 /* Otherwise we'll have to use the fallthru fixup below. */
3840 else
3842 /* Otherwise we have some return, switch or computed
3843 jump. In the 99% case, there should not have been a
3844 fallthru edge. */
3845 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3846 continue;
3849 else
3851 /* No fallthru implies a noreturn function with EH edges, or
3852 something similarly bizarre. In any case, we don't need to
3853 do anything. */
3854 if (! e_fall)
3855 continue;
3857 /* If the fallthru block is still next, nothing to do. */
3858 if (bb->aux == e_fall->dest)
3859 continue;
3861 /* A fallthru to exit block. */
3862 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3863 continue;
3866 /* We got here if we need to add a new jump insn.
3867 Note force_nonfallthru can delete E_FALL and thus we have to
3868 save E_FALL->src prior to the call to force_nonfallthru. */
3869 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3870 if (nb)
3872 nb->aux = bb->aux;
3873 bb->aux = nb;
3874 /* Don't process this new block. */
3875 bb = nb;
3879 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3881 /* Annoying special case - jump around dead jumptables left in the code. */
3882 FOR_EACH_BB_FN (bb, cfun)
3884 edge e = find_fallthru_edge (bb->succs);
3886 if (e && !can_fallthru (e->src, e->dest))
3887 force_nonfallthru (e);
3890 /* Ensure goto_locus from edges has some instructions with that locus
3891 in RTL. */
3892 if (!optimize)
3893 FOR_EACH_BB_FN (bb, cfun)
3895 edge e;
3896 edge_iterator ei;
3898 FOR_EACH_EDGE (e, ei, bb->succs)
3899 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3900 && !(e->flags & EDGE_ABNORMAL))
3902 edge e2;
3903 edge_iterator ei2;
3904 basic_block dest, nb;
3905 rtx_insn *end;
3907 insn = BB_END (e->src);
3908 end = PREV_INSN (BB_HEAD (e->src));
3909 while (insn != end
3910 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3911 insn = PREV_INSN (insn);
3912 if (insn != end
3913 && INSN_LOCATION (insn) == e->goto_locus)
3914 continue;
3915 if (simplejump_p (BB_END (e->src))
3916 && !INSN_HAS_LOCATION (BB_END (e->src)))
3918 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3919 continue;
3921 dest = e->dest;
3922 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3924 /* Non-fallthru edges to the exit block cannot be split. */
3925 if (!(e->flags & EDGE_FALLTHRU))
3926 continue;
3928 else
3930 insn = BB_HEAD (dest);
3931 end = NEXT_INSN (BB_END (dest));
3932 while (insn != end && !NONDEBUG_INSN_P (insn))
3933 insn = NEXT_INSN (insn);
3934 if (insn != end && INSN_HAS_LOCATION (insn)
3935 && INSN_LOCATION (insn) == e->goto_locus)
3936 continue;
3938 nb = split_edge (e);
3939 if (!INSN_P (BB_END (nb)))
3940 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3941 nb);
3942 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3944 /* If there are other incoming edges to the destination block
3945 with the same goto locus, redirect them to the new block as
3946 well, this can prevent other such blocks from being created
3947 in subsequent iterations of the loop. */
3948 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3949 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3950 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3951 && e->goto_locus == e2->goto_locus)
3952 redirect_edge_and_branch (e2, nb);
3953 else
3954 ei_next (&ei2);
3959 /* Perform sanity checks on the insn chain.
3960 1. Check that next/prev pointers are consistent in both the forward and
3961 reverse direction.
3962 2. Count insns in chain, going both directions, and check if equal.
3963 3. Check that get_last_insn () returns the actual end of chain. */
3965 DEBUG_FUNCTION void
3966 verify_insn_chain (void)
3968 rtx_insn *x, *prevx, *nextx;
3969 int insn_cnt1, insn_cnt2;
3971 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3972 x != 0;
3973 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3974 gcc_assert (PREV_INSN (x) == prevx);
3976 gcc_assert (prevx == get_last_insn ());
3978 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3979 x != 0;
3980 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3981 gcc_assert (NEXT_INSN (x) == nextx);
3983 gcc_assert (insn_cnt1 == insn_cnt2);
3986 /* If we have assembler epilogues, the block falling through to exit must
3987 be the last one in the reordered chain when we reach final. Ensure
3988 that this condition is met. */
3989 static void
3990 fixup_fallthru_exit_predecessor (void)
3992 edge e;
3993 basic_block bb = NULL;
3995 /* This transformation is not valid before reload, because we might
3996 separate a call from the instruction that copies the return
3997 value. */
3998 gcc_assert (reload_completed);
4000 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4001 if (e)
4002 bb = e->src;
4004 if (bb && bb->aux)
4006 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4008 /* If the very first block is the one with the fall-through exit
4009 edge, we have to split that block. */
4010 if (c == bb)
4012 bb = split_block_after_labels (bb)->dest;
4013 bb->aux = c->aux;
4014 c->aux = bb;
4015 BB_FOOTER (bb) = BB_FOOTER (c);
4016 BB_FOOTER (c) = NULL;
4019 while (c->aux != bb)
4020 c = (basic_block) c->aux;
4022 c->aux = bb->aux;
4023 while (c->aux)
4024 c = (basic_block) c->aux;
4026 c->aux = bb;
4027 bb->aux = NULL;
4031 /* In case there are more than one fallthru predecessors of exit, force that
4032 there is only one. */
4034 static void
4035 force_one_exit_fallthru (void)
4037 edge e, predecessor = NULL;
4038 bool more = false;
4039 edge_iterator ei;
4040 basic_block forwarder, bb;
4042 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4043 if (e->flags & EDGE_FALLTHRU)
4045 if (predecessor == NULL)
4046 predecessor = e;
4047 else
4049 more = true;
4050 break;
4054 if (!more)
4055 return;
4057 /* Exit has several fallthru predecessors. Create a forwarder block for
4058 them. */
4059 forwarder = split_edge (predecessor);
4060 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4061 (e = ei_safe_edge (ei)); )
4063 if (e->src == forwarder
4064 || !(e->flags & EDGE_FALLTHRU))
4065 ei_next (&ei);
4066 else
4067 redirect_edge_and_branch_force (e, forwarder);
4070 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4071 exit block. */
4072 FOR_EACH_BB_FN (bb, cfun)
4074 if (bb->aux == NULL && bb != forwarder)
4076 bb->aux = forwarder;
4077 break;
4082 /* Return true in case it is possible to duplicate the basic block BB. */
4084 static bool
4085 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4087 /* Do not attempt to duplicate tablejumps, as we need to unshare
4088 the dispatch table. This is difficult to do, as the instructions
4089 computing jump destination may be hoisted outside the basic block. */
4090 if (tablejump_p (BB_END (bb), NULL, NULL))
4091 return false;
4093 /* Do not duplicate blocks containing insns that can't be copied. */
4094 if (targetm.cannot_copy_insn_p)
4096 rtx_insn *insn = BB_HEAD (bb);
4097 while (1)
4099 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4100 return false;
4101 if (insn == BB_END (bb))
4102 break;
4103 insn = NEXT_INSN (insn);
4107 return true;
4110 rtx_insn *
4111 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4113 rtx_insn *insn, *next, *copy;
4114 rtx_note *last;
4116 /* Avoid updating of boundaries of previous basic block. The
4117 note will get removed from insn stream in fixup. */
4118 last = emit_note (NOTE_INSN_DELETED);
4120 /* Create copy at the end of INSN chain. The chain will
4121 be reordered later. */
4122 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4124 switch (GET_CODE (insn))
4126 case DEBUG_INSN:
4127 /* Don't duplicate label debug insns. */
4128 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4129 break;
4130 /* FALLTHRU */
4131 case INSN:
4132 case CALL_INSN:
4133 case JUMP_INSN:
4134 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4135 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4136 && ANY_RETURN_P (JUMP_LABEL (insn)))
4137 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4138 maybe_copy_prologue_epilogue_insn (insn, copy);
4139 break;
4141 case JUMP_TABLE_DATA:
4142 /* Avoid copying of dispatch tables. We never duplicate
4143 tablejumps, so this can hit only in case the table got
4144 moved far from original jump.
4145 Avoid copying following barrier as well if any
4146 (and debug insns in between). */
4147 for (next = NEXT_INSN (insn);
4148 next != NEXT_INSN (to);
4149 next = NEXT_INSN (next))
4150 if (!DEBUG_INSN_P (next))
4151 break;
4152 if (next != NEXT_INSN (to) && BARRIER_P (next))
4153 insn = next;
4154 break;
4156 case CODE_LABEL:
4157 break;
4159 case BARRIER:
4160 emit_barrier ();
4161 break;
4163 case NOTE:
4164 switch (NOTE_KIND (insn))
4166 /* In case prologue is empty and function contain label
4167 in first BB, we may want to copy the block. */
4168 case NOTE_INSN_PROLOGUE_END:
4170 case NOTE_INSN_DELETED:
4171 case NOTE_INSN_DELETED_LABEL:
4172 case NOTE_INSN_DELETED_DEBUG_LABEL:
4173 /* No problem to strip these. */
4174 case NOTE_INSN_FUNCTION_BEG:
4175 /* There is always just single entry to function. */
4176 case NOTE_INSN_BASIC_BLOCK:
4177 /* We should only switch text sections once. */
4178 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4179 break;
4181 case NOTE_INSN_EPILOGUE_BEG:
4182 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4183 emit_note_copy (as_a <rtx_note *> (insn));
4184 break;
4186 default:
4187 /* All other notes should have already been eliminated. */
4188 gcc_unreachable ();
4190 break;
4191 default:
4192 gcc_unreachable ();
4195 insn = NEXT_INSN (last);
4196 delete_insn (last);
4197 return insn;
4200 /* Create a duplicate of the basic block BB. */
4202 static basic_block
4203 cfg_layout_duplicate_bb (basic_block bb)
4205 rtx_insn *insn;
4206 basic_block new_bb;
4208 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4209 new_bb = create_basic_block (insn,
4210 insn ? get_last_insn () : NULL,
4211 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4213 BB_COPY_PARTITION (new_bb, bb);
4214 if (BB_HEADER (bb))
4216 insn = BB_HEADER (bb);
4217 while (NEXT_INSN (insn))
4218 insn = NEXT_INSN (insn);
4219 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4220 if (insn)
4221 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4224 if (BB_FOOTER (bb))
4226 insn = BB_FOOTER (bb);
4227 while (NEXT_INSN (insn))
4228 insn = NEXT_INSN (insn);
4229 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4230 if (insn)
4231 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4234 return new_bb;
4238 /* Main entry point to this module - initialize the datastructures for
4239 CFG layout changes. It keeps LOOPS up-to-date if not null.
4241 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4243 void
4244 cfg_layout_initialize (int flags)
4246 rtx_insn_list *x;
4247 basic_block bb;
4249 /* Once bb partitioning is complete, cfg layout mode should not be
4250 re-entered. Entering cfg layout mode may require fixups. As an
4251 example, if edge forwarding performed when optimizing the cfg
4252 layout required moving a block from the hot to the cold
4253 section. This would create an illegal partitioning unless some
4254 manual fixup was performed. */
4255 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4257 initialize_original_copy_tables ();
4259 cfg_layout_rtl_register_cfg_hooks ();
4261 record_effective_endpoints ();
4263 /* Make sure that the targets of non local gotos are marked. */
4264 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4266 bb = BLOCK_FOR_INSN (x->insn ());
4267 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4270 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4273 /* Splits superblocks. */
4274 void
4275 break_superblocks (void)
4277 bool need = false;
4278 basic_block bb;
4280 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4281 bitmap_clear (superblocks);
4283 FOR_EACH_BB_FN (bb, cfun)
4284 if (bb->flags & BB_SUPERBLOCK)
4286 bb->flags &= ~BB_SUPERBLOCK;
4287 bitmap_set_bit (superblocks, bb->index);
4288 need = true;
4291 if (need)
4293 rebuild_jump_labels (get_insns ());
4294 find_many_sub_basic_blocks (superblocks);
4298 /* Finalize the changes: reorder insn list according to the sequence specified
4299 by aux pointers, enter compensation code, rebuild scope forest. */
4301 void
4302 cfg_layout_finalize (void)
4304 checking_verify_flow_info ();
4305 free_dominance_info (CDI_DOMINATORS);
4306 force_one_exit_fallthru ();
4307 rtl_register_cfg_hooks ();
4308 if (reload_completed && !targetm.have_epilogue ())
4309 fixup_fallthru_exit_predecessor ();
4310 fixup_reorder_chain ();
4312 rebuild_jump_labels (get_insns ());
4313 delete_dead_jumptables ();
4315 if (flag_checking)
4316 verify_insn_chain ();
4317 checking_verify_flow_info ();
4321 /* Same as split_block but update cfg_layout structures. */
4323 static basic_block
4324 cfg_layout_split_block (basic_block bb, void *insnp)
4326 rtx insn = (rtx) insnp;
4327 basic_block new_bb = rtl_split_block (bb, insn);
4329 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4330 BB_FOOTER (bb) = NULL;
4332 return new_bb;
4335 /* Redirect Edge to DEST. */
4336 static edge
4337 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4339 basic_block src = e->src;
4340 edge ret;
4342 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4343 return NULL;
4345 if (e->dest == dest)
4346 return e;
4348 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4349 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4351 df_set_bb_dirty (src);
4352 return ret;
4355 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4356 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4358 if (dump_file)
4359 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4360 e->src->index, dest->index);
4362 df_set_bb_dirty (e->src);
4363 redirect_edge_succ (e, dest);
4364 return e;
4367 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4368 in the case the basic block appears to be in sequence. Avoid this
4369 transformation. */
4371 if (e->flags & EDGE_FALLTHRU)
4373 /* Redirect any branch edges unified with the fallthru one. */
4374 if (JUMP_P (BB_END (src))
4375 && label_is_jump_target_p (BB_HEAD (e->dest),
4376 BB_END (src)))
4378 edge redirected;
4380 if (dump_file)
4381 fprintf (dump_file, "Fallthru edge unified with branch "
4382 "%i->%i redirected to %i\n",
4383 e->src->index, e->dest->index, dest->index);
4384 e->flags &= ~EDGE_FALLTHRU;
4385 redirected = redirect_branch_edge (e, dest);
4386 gcc_assert (redirected);
4387 redirected->flags |= EDGE_FALLTHRU;
4388 df_set_bb_dirty (redirected->src);
4389 return redirected;
4391 /* In case we are redirecting fallthru edge to the branch edge
4392 of conditional jump, remove it. */
4393 if (EDGE_COUNT (src->succs) == 2)
4395 /* Find the edge that is different from E. */
4396 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4398 if (s->dest == dest
4399 && any_condjump_p (BB_END (src))
4400 && onlyjump_p (BB_END (src)))
4401 delete_insn (BB_END (src));
4403 if (dump_file)
4404 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4405 e->src->index, e->dest->index, dest->index);
4406 ret = redirect_edge_succ_nodup (e, dest);
4408 else
4409 ret = redirect_branch_edge (e, dest);
4411 /* We don't want simplejumps in the insn stream during cfglayout. */
4412 gcc_assert (!simplejump_p (BB_END (src)));
4414 df_set_bb_dirty (src);
4415 return ret;
4418 /* Simple wrapper as we always can redirect fallthru edges. */
4419 static basic_block
4420 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4422 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4424 gcc_assert (redirected);
4425 return NULL;
4428 /* Same as delete_basic_block but update cfg_layout structures. */
4430 static void
4431 cfg_layout_delete_block (basic_block bb)
4433 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4434 rtx_insn **to;
4436 if (BB_HEADER (bb))
4438 next = BB_HEAD (bb);
4439 if (prev)
4440 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4441 else
4442 set_first_insn (BB_HEADER (bb));
4443 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4444 insn = BB_HEADER (bb);
4445 while (NEXT_INSN (insn))
4446 insn = NEXT_INSN (insn);
4447 SET_NEXT_INSN (insn) = next;
4448 SET_PREV_INSN (next) = insn;
4450 next = NEXT_INSN (BB_END (bb));
4451 if (BB_FOOTER (bb))
4453 insn = BB_FOOTER (bb);
4454 while (insn)
4456 if (BARRIER_P (insn))
4458 if (PREV_INSN (insn))
4459 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4460 else
4461 BB_FOOTER (bb) = NEXT_INSN (insn);
4462 if (NEXT_INSN (insn))
4463 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4465 if (LABEL_P (insn))
4466 break;
4467 insn = NEXT_INSN (insn);
4469 if (BB_FOOTER (bb))
4471 insn = BB_END (bb);
4472 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4473 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4474 while (NEXT_INSN (insn))
4475 insn = NEXT_INSN (insn);
4476 SET_NEXT_INSN (insn) = next;
4477 if (next)
4478 SET_PREV_INSN (next) = insn;
4479 else
4480 set_last_insn (insn);
4483 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4484 to = &BB_HEADER (bb->next_bb);
4485 else
4486 to = &cfg_layout_function_footer;
4488 rtl_delete_block (bb);
4490 if (prev)
4491 prev = NEXT_INSN (prev);
4492 else
4493 prev = get_insns ();
4494 if (next)
4495 next = PREV_INSN (next);
4496 else
4497 next = get_last_insn ();
4499 if (next && NEXT_INSN (next) != prev)
4501 remaints = unlink_insn_chain (prev, next);
4502 insn = remaints;
4503 while (NEXT_INSN (insn))
4504 insn = NEXT_INSN (insn);
4505 SET_NEXT_INSN (insn) = *to;
4506 if (*to)
4507 SET_PREV_INSN (*to) = insn;
4508 *to = remaints;
4512 /* Return true when blocks A and B can be safely merged. */
4514 static bool
4515 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4517 /* If we are partitioning hot/cold basic blocks, we don't want to
4518 mess up unconditional or indirect jumps that cross between hot
4519 and cold sections.
4521 Basic block partitioning may result in some jumps that appear to
4522 be optimizable (or blocks that appear to be mergeable), but which really
4523 must be left untouched (they are required to make it safely across
4524 partition boundaries). See the comments at the top of
4525 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4527 if (BB_PARTITION (a) != BB_PARTITION (b))
4528 return false;
4530 /* Protect the loop latches. */
4531 if (current_loops && b->loop_father->latch == b)
4532 return false;
4534 /* If we would end up moving B's instructions, make sure it doesn't fall
4535 through into the exit block, since we cannot recover from a fallthrough
4536 edge into the exit block occurring in the middle of a function. */
4537 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4539 edge e = find_fallthru_edge (b->succs);
4540 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4541 return false;
4544 /* There must be exactly one edge in between the blocks. */
4545 return (single_succ_p (a)
4546 && single_succ (a) == b
4547 && single_pred_p (b) == 1
4548 && a != b
4549 /* Must be simple edge. */
4550 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4551 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4552 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4553 /* If the jump insn has side effects, we can't kill the edge.
4554 When not optimizing, try_redirect_by_replacing_jump will
4555 not allow us to redirect an edge by replacing a table jump. */
4556 && (!JUMP_P (BB_END (a))
4557 || ((!optimize || reload_completed)
4558 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4561 /* Merge block A and B. The blocks must be mergeable. */
4563 static void
4564 cfg_layout_merge_blocks (basic_block a, basic_block b)
4566 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4567 rtx_insn *insn;
4569 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4571 if (dump_file)
4572 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4573 a->index);
4575 /* If there was a CODE_LABEL beginning B, delete it. */
4576 if (LABEL_P (BB_HEAD (b)))
4578 delete_insn (BB_HEAD (b));
4581 /* We should have fallthru edge in a, or we can do dummy redirection to get
4582 it cleaned up. */
4583 if (JUMP_P (BB_END (a)))
4584 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4585 gcc_assert (!JUMP_P (BB_END (a)));
4587 /* When not optimizing and the edge is the only place in RTL which holds
4588 some unique locus, emit a nop with that locus in between. */
4589 if (!optimize)
4590 emit_nop_for_unique_locus_between (a, b);
4592 /* Move things from b->footer after a->footer. */
4593 if (BB_FOOTER (b))
4595 if (!BB_FOOTER (a))
4596 BB_FOOTER (a) = BB_FOOTER (b);
4597 else
4599 rtx_insn *last = BB_FOOTER (a);
4601 while (NEXT_INSN (last))
4602 last = NEXT_INSN (last);
4603 SET_NEXT_INSN (last) = BB_FOOTER (b);
4604 SET_PREV_INSN (BB_FOOTER (b)) = last;
4606 BB_FOOTER (b) = NULL;
4609 /* Move things from b->header before a->footer.
4610 Note that this may include dead tablejump data, but we don't clean
4611 those up until we go out of cfglayout mode. */
4612 if (BB_HEADER (b))
4614 if (! BB_FOOTER (a))
4615 BB_FOOTER (a) = BB_HEADER (b);
4616 else
4618 rtx_insn *last = BB_HEADER (b);
4620 while (NEXT_INSN (last))
4621 last = NEXT_INSN (last);
4622 SET_NEXT_INSN (last) = BB_FOOTER (a);
4623 SET_PREV_INSN (BB_FOOTER (a)) = last;
4624 BB_FOOTER (a) = BB_HEADER (b);
4626 BB_HEADER (b) = NULL;
4629 /* In the case basic blocks are not adjacent, move them around. */
4630 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4632 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4634 emit_insn_after_noloc (insn, BB_END (a), a);
4636 /* Otherwise just re-associate the instructions. */
4637 else
4639 insn = BB_HEAD (b);
4640 BB_END (a) = BB_END (b);
4643 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4644 We need to explicitly call. */
4645 update_bb_for_insn_chain (insn, BB_END (b), a);
4647 /* Skip possible DELETED_LABEL insn. */
4648 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4649 insn = NEXT_INSN (insn);
4650 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4651 BB_HEAD (b) = BB_END (b) = NULL;
4652 delete_insn (insn);
4654 df_bb_delete (b->index);
4656 /* If B was a forwarder block, propagate the locus on the edge. */
4657 if (forwarder_p
4658 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4659 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4661 if (dump_file)
4662 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4665 /* Split edge E. */
4667 static basic_block
4668 cfg_layout_split_edge (edge e)
4670 basic_block new_bb =
4671 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4672 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4673 NULL_RTX, e->src);
4675 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4676 BB_COPY_PARTITION (new_bb, e->src);
4677 else
4678 BB_COPY_PARTITION (new_bb, e->dest);
4679 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4680 redirect_edge_and_branch_force (e, new_bb);
4682 return new_bb;
4685 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4687 static void
4688 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4692 /* Return true if BB contains only labels or non-executable
4693 instructions. */
4695 static bool
4696 rtl_block_empty_p (basic_block bb)
4698 rtx_insn *insn;
4700 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4701 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4702 return true;
4704 FOR_BB_INSNS (bb, insn)
4705 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4706 return false;
4708 return true;
4711 /* Split a basic block if it ends with a conditional branch and if
4712 the other part of the block is not empty. */
4714 static basic_block
4715 rtl_split_block_before_cond_jump (basic_block bb)
4717 rtx_insn *insn;
4718 rtx_insn *split_point = NULL;
4719 rtx_insn *last = NULL;
4720 bool found_code = false;
4722 FOR_BB_INSNS (bb, insn)
4724 if (any_condjump_p (insn))
4725 split_point = last;
4726 else if (NONDEBUG_INSN_P (insn))
4727 found_code = true;
4728 last = insn;
4731 /* Did not find everything. */
4732 if (found_code && split_point)
4733 return split_block (bb, split_point)->dest;
4734 else
4735 return NULL;
4738 /* Return 1 if BB ends with a call, possibly followed by some
4739 instructions that must stay with the call, 0 otherwise. */
4741 static bool
4742 rtl_block_ends_with_call_p (basic_block bb)
4744 rtx_insn *insn = BB_END (bb);
4746 while (!CALL_P (insn)
4747 && insn != BB_HEAD (bb)
4748 && (keep_with_call_p (insn)
4749 || NOTE_P (insn)
4750 || DEBUG_INSN_P (insn)))
4751 insn = PREV_INSN (insn);
4752 return (CALL_P (insn));
4755 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4757 static bool
4758 rtl_block_ends_with_condjump_p (const_basic_block bb)
4760 return any_condjump_p (BB_END (bb));
4763 /* Return true if we need to add fake edge to exit.
4764 Helper function for rtl_flow_call_edges_add. */
4766 static bool
4767 need_fake_edge_p (const rtx_insn *insn)
4769 if (!INSN_P (insn))
4770 return false;
4772 if ((CALL_P (insn)
4773 && !SIBLING_CALL_P (insn)
4774 && !find_reg_note (insn, REG_NORETURN, NULL)
4775 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4776 return true;
4778 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4779 && MEM_VOLATILE_P (PATTERN (insn)))
4780 || (GET_CODE (PATTERN (insn)) == PARALLEL
4781 && asm_noperands (insn) != -1
4782 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4783 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4786 /* Add fake edges to the function exit for any non constant and non noreturn
4787 calls, volatile inline assembly in the bitmap of blocks specified by
4788 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4789 that were split.
4791 The goal is to expose cases in which entering a basic block does not imply
4792 that all subsequent instructions must be executed. */
4794 static int
4795 rtl_flow_call_edges_add (sbitmap blocks)
4797 int i;
4798 int blocks_split = 0;
4799 int last_bb = last_basic_block_for_fn (cfun);
4800 bool check_last_block = false;
4802 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4803 return 0;
4805 if (! blocks)
4806 check_last_block = true;
4807 else
4808 check_last_block = bitmap_bit_p (blocks,
4809 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4811 /* In the last basic block, before epilogue generation, there will be
4812 a fallthru edge to EXIT. Special care is required if the last insn
4813 of the last basic block is a call because make_edge folds duplicate
4814 edges, which would result in the fallthru edge also being marked
4815 fake, which would result in the fallthru edge being removed by
4816 remove_fake_edges, which would result in an invalid CFG.
4818 Moreover, we can't elide the outgoing fake edge, since the block
4819 profiler needs to take this into account in order to solve the minimal
4820 spanning tree in the case that the call doesn't return.
4822 Handle this by adding a dummy instruction in a new last basic block. */
4823 if (check_last_block)
4825 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4826 rtx_insn *insn = BB_END (bb);
4828 /* Back up past insns that must be kept in the same block as a call. */
4829 while (insn != BB_HEAD (bb)
4830 && keep_with_call_p (insn))
4831 insn = PREV_INSN (insn);
4833 if (need_fake_edge_p (insn))
4835 edge e;
4837 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4838 if (e)
4840 insert_insn_on_edge (gen_use (const0_rtx), e);
4841 commit_edge_insertions ();
4846 /* Now add fake edges to the function exit for any non constant
4847 calls since there is no way that we can determine if they will
4848 return or not... */
4850 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4852 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4853 rtx_insn *insn;
4854 rtx_insn *prev_insn;
4856 if (!bb)
4857 continue;
4859 if (blocks && !bitmap_bit_p (blocks, i))
4860 continue;
4862 for (insn = BB_END (bb); ; insn = prev_insn)
4864 prev_insn = PREV_INSN (insn);
4865 if (need_fake_edge_p (insn))
4867 edge e;
4868 rtx_insn *split_at_insn = insn;
4870 /* Don't split the block between a call and an insn that should
4871 remain in the same block as the call. */
4872 if (CALL_P (insn))
4873 while (split_at_insn != BB_END (bb)
4874 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4875 split_at_insn = NEXT_INSN (split_at_insn);
4877 /* The handling above of the final block before the epilogue
4878 should be enough to verify that there is no edge to the exit
4879 block in CFG already. Calling make_edge in such case would
4880 cause us to mark that edge as fake and remove it later. */
4882 if (flag_checking && split_at_insn == BB_END (bb))
4884 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4885 gcc_assert (e == NULL);
4888 /* Note that the following may create a new basic block
4889 and renumber the existing basic blocks. */
4890 if (split_at_insn != BB_END (bb))
4892 e = split_block (bb, split_at_insn);
4893 if (e)
4894 blocks_split++;
4897 edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4898 ne->probability = profile_probability::guessed_never ();
4901 if (insn == BB_HEAD (bb))
4902 break;
4906 if (blocks_split)
4907 verify_flow_info ();
4909 return blocks_split;
4912 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4913 the conditional branch target, SECOND_HEAD should be the fall-thru
4914 there is no need to handle this here the loop versioning code handles
4915 this. the reason for SECON_HEAD is that it is needed for condition
4916 in trees, and this should be of the same type since it is a hook. */
4917 static void
4918 rtl_lv_add_condition_to_bb (basic_block first_head ,
4919 basic_block second_head ATTRIBUTE_UNUSED,
4920 basic_block cond_bb, void *comp_rtx)
4922 rtx_code_label *label;
4923 rtx_insn *seq, *jump;
4924 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4925 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4926 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4927 machine_mode mode;
4930 label = block_label (first_head);
4931 mode = GET_MODE (op0);
4932 if (mode == VOIDmode)
4933 mode = GET_MODE (op1);
4935 start_sequence ();
4936 op0 = force_operand (op0, NULL_RTX);
4937 op1 = force_operand (op1, NULL_RTX);
4938 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
4939 profile_probability::uninitialized ());
4940 jump = get_last_insn ();
4941 JUMP_LABEL (jump) = label;
4942 LABEL_NUSES (label)++;
4943 seq = get_insns ();
4944 end_sequence ();
4946 /* Add the new cond, in the new head. */
4947 emit_insn_after (seq, BB_END (cond_bb));
4951 /* Given a block B with unconditional branch at its end, get the
4952 store the return the branch edge and the fall-thru edge in
4953 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4954 static void
4955 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4956 edge *fallthru_edge)
4958 edge e = EDGE_SUCC (b, 0);
4960 if (e->flags & EDGE_FALLTHRU)
4962 *fallthru_edge = e;
4963 *branch_edge = EDGE_SUCC (b, 1);
4965 else
4967 *branch_edge = e;
4968 *fallthru_edge = EDGE_SUCC (b, 1);
4972 void
4973 init_rtl_bb_info (basic_block bb)
4975 gcc_assert (!bb->il.x.rtl);
4976 bb->il.x.head_ = NULL;
4977 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
4980 /* Returns true if it is possible to remove edge E by redirecting
4981 it to the destination of the other edge from E->src. */
4983 static bool
4984 rtl_can_remove_branch_p (const_edge e)
4986 const_basic_block src = e->src;
4987 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
4988 const rtx_insn *insn = BB_END (src);
4989 rtx set;
4991 /* The conditions are taken from try_redirect_by_replacing_jump. */
4992 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
4993 return false;
4995 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4996 return false;
4998 if (BB_PARTITION (src) != BB_PARTITION (target))
4999 return false;
5001 if (!onlyjump_p (insn)
5002 || tablejump_p (insn, NULL, NULL))
5003 return false;
5005 set = single_set (insn);
5006 if (!set || side_effects_p (set))
5007 return false;
5009 return true;
5012 static basic_block
5013 rtl_duplicate_bb (basic_block bb)
5015 bb = cfg_layout_duplicate_bb (bb);
5016 bb->aux = NULL;
5017 return bb;
5020 /* Do book-keeping of basic block BB for the profile consistency checker.
5021 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5022 then do post-pass accounting. Store the counting in RECORD. */
5023 static void
5024 rtl_account_profile_record (basic_block bb, int after_pass,
5025 struct profile_record *record)
5027 rtx_insn *insn;
5028 FOR_BB_INSNS (bb, insn)
5029 if (INSN_P (insn))
5031 record->size[after_pass] += insn_cost (insn, false);
5032 if (bb->count.initialized_p ())
5033 record->time[after_pass]
5034 += insn_cost (insn, true) * bb->count.to_gcov_type ();
5035 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5036 record->time[after_pass]
5037 += insn_cost (insn, true) * bb->frequency;
5041 /* Implementation of CFG manipulation for linearized RTL. */
5042 struct cfg_hooks rtl_cfg_hooks = {
5043 "rtl",
5044 rtl_verify_flow_info,
5045 rtl_dump_bb,
5046 rtl_dump_bb_for_graph,
5047 rtl_create_basic_block,
5048 rtl_redirect_edge_and_branch,
5049 rtl_redirect_edge_and_branch_force,
5050 rtl_can_remove_branch_p,
5051 rtl_delete_block,
5052 rtl_split_block,
5053 rtl_move_block_after,
5054 rtl_can_merge_blocks, /* can_merge_blocks_p */
5055 rtl_merge_blocks,
5056 rtl_predict_edge,
5057 rtl_predicted_by_p,
5058 cfg_layout_can_duplicate_bb_p,
5059 rtl_duplicate_bb,
5060 rtl_split_edge,
5061 rtl_make_forwarder_block,
5062 rtl_tidy_fallthru_edge,
5063 rtl_force_nonfallthru,
5064 rtl_block_ends_with_call_p,
5065 rtl_block_ends_with_condjump_p,
5066 rtl_flow_call_edges_add,
5067 NULL, /* execute_on_growing_pred */
5068 NULL, /* execute_on_shrinking_pred */
5069 NULL, /* duplicate loop for trees */
5070 NULL, /* lv_add_condition_to_bb */
5071 NULL, /* lv_adjust_loop_header_phi*/
5072 NULL, /* extract_cond_bb_edges */
5073 NULL, /* flush_pending_stmts */
5074 rtl_block_empty_p, /* block_empty_p */
5075 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5076 rtl_account_profile_record,
5079 /* Implementation of CFG manipulation for cfg layout RTL, where
5080 basic block connected via fallthru edges does not have to be adjacent.
5081 This representation will hopefully become the default one in future
5082 version of the compiler. */
5084 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5085 "cfglayout mode",
5086 rtl_verify_flow_info_1,
5087 rtl_dump_bb,
5088 rtl_dump_bb_for_graph,
5089 cfg_layout_create_basic_block,
5090 cfg_layout_redirect_edge_and_branch,
5091 cfg_layout_redirect_edge_and_branch_force,
5092 rtl_can_remove_branch_p,
5093 cfg_layout_delete_block,
5094 cfg_layout_split_block,
5095 rtl_move_block_after,
5096 cfg_layout_can_merge_blocks_p,
5097 cfg_layout_merge_blocks,
5098 rtl_predict_edge,
5099 rtl_predicted_by_p,
5100 cfg_layout_can_duplicate_bb_p,
5101 cfg_layout_duplicate_bb,
5102 cfg_layout_split_edge,
5103 rtl_make_forwarder_block,
5104 NULL, /* tidy_fallthru_edge */
5105 rtl_force_nonfallthru,
5106 rtl_block_ends_with_call_p,
5107 rtl_block_ends_with_condjump_p,
5108 rtl_flow_call_edges_add,
5109 NULL, /* execute_on_growing_pred */
5110 NULL, /* execute_on_shrinking_pred */
5111 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5112 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5113 NULL, /* lv_adjust_loop_header_phi*/
5114 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5115 NULL, /* flush_pending_stmts */
5116 rtl_block_empty_p, /* block_empty_p */
5117 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5118 rtl_account_profile_record,
5121 #include "gt-cfgrtl.h"