Patch for RTL expand bug affecting aarch64 vector code.
[official-gcc.git] / gcc / cfgrtl.c
blobcafa38d35b05263270ef52927ca63a6cdbfde603
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, int);
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 = REG_BR_PROB_BASE;
1159 e->count = src->count;
1161 if (e->dest != target)
1162 redirect_edge_succ (e, target);
1163 return e;
1166 /* Subroutine of redirect_branch_edge that tries to patch the jump
1167 instruction INSN so that it reaches block NEW. Do this
1168 only when it originally reached block OLD. Return true if this
1169 worked or the original target wasn't OLD, return false if redirection
1170 doesn't work. */
1172 static bool
1173 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1175 rtx_jump_table_data *table;
1176 rtx tmp;
1177 /* Recognize a tablejump and adjust all matching cases. */
1178 if (tablejump_p (insn, NULL, &table))
1180 rtvec vec;
1181 int j;
1182 rtx_code_label *new_label = block_label (new_bb);
1184 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1185 return false;
1186 vec = table->get_labels ();
1188 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1189 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1191 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1192 --LABEL_NUSES (old_label);
1193 ++LABEL_NUSES (new_label);
1196 /* Handle casesi dispatch insns. */
1197 if ((tmp = single_set (insn)) != NULL
1198 && SET_DEST (tmp) == pc_rtx
1199 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1200 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1201 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1203 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1204 new_label);
1205 --LABEL_NUSES (old_label);
1206 ++LABEL_NUSES (new_label);
1209 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1211 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1212 rtx note;
1214 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1215 return false;
1216 rtx_code_label *new_label = block_label (new_bb);
1218 for (i = 0; i < n; ++i)
1220 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1221 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1222 if (XEXP (old_ref, 0) == old_label)
1224 ASM_OPERANDS_LABEL (tmp, i)
1225 = gen_rtx_LABEL_REF (Pmode, new_label);
1226 --LABEL_NUSES (old_label);
1227 ++LABEL_NUSES (new_label);
1231 if (JUMP_LABEL (insn) == old_label)
1233 JUMP_LABEL (insn) = new_label;
1234 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1235 if (note)
1236 remove_note (insn, note);
1238 else
1240 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1241 if (note)
1242 remove_note (insn, note);
1243 if (JUMP_LABEL (insn) != new_label
1244 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1245 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1247 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1248 != NULL_RTX)
1249 XEXP (note, 0) = new_label;
1251 else
1253 /* ?? We may play the games with moving the named labels from
1254 one basic block to the other in case only one computed_jump is
1255 available. */
1256 if (computed_jump_p (insn)
1257 /* A return instruction can't be redirected. */
1258 || returnjump_p (insn))
1259 return false;
1261 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1263 /* If the insn doesn't go where we think, we're confused. */
1264 gcc_assert (JUMP_LABEL (insn) == old_label);
1266 /* If the substitution doesn't succeed, die. This can happen
1267 if the back end emitted unrecognizable instructions or if
1268 target is exit block on some arches. */
1269 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1270 block_label (new_bb), 0))
1272 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1273 return false;
1277 return true;
1281 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1282 NULL on failure */
1283 static edge
1284 redirect_branch_edge (edge e, basic_block target)
1286 rtx_insn *old_label = BB_HEAD (e->dest);
1287 basic_block src = e->src;
1288 rtx_insn *insn = BB_END (src);
1290 /* We can only redirect non-fallthru edges of jump insn. */
1291 if (e->flags & EDGE_FALLTHRU)
1292 return NULL;
1293 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1294 return NULL;
1296 if (!currently_expanding_to_rtl)
1298 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1299 return NULL;
1301 else
1302 /* When expanding this BB might actually contain multiple
1303 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1304 Redirect all of those that match our label. */
1305 FOR_BB_INSNS (src, insn)
1306 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1307 old_label, target))
1308 return NULL;
1310 if (dump_file)
1311 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1312 e->src->index, e->dest->index, target->index);
1314 if (e->dest != target)
1315 e = redirect_edge_succ_nodup (e, target);
1317 return e;
1320 /* Called when edge E has been redirected to a new destination,
1321 in order to update the region crossing flag on the edge and
1322 jump. */
1324 static void
1325 fixup_partition_crossing (edge e)
1327 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1328 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1329 return;
1330 /* If we redirected an existing edge, it may already be marked
1331 crossing, even though the new src is missing a reg crossing note.
1332 But make sure reg crossing note doesn't already exist before
1333 inserting. */
1334 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1336 e->flags |= EDGE_CROSSING;
1337 if (JUMP_P (BB_END (e->src))
1338 && !CROSSING_JUMP_P (BB_END (e->src)))
1339 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1341 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1343 e->flags &= ~EDGE_CROSSING;
1344 /* Remove the section crossing note from jump at end of
1345 src if it exists, and if no other successors are
1346 still crossing. */
1347 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1349 bool has_crossing_succ = false;
1350 edge e2;
1351 edge_iterator ei;
1352 FOR_EACH_EDGE (e2, ei, e->src->succs)
1354 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1355 if (has_crossing_succ)
1356 break;
1358 if (!has_crossing_succ)
1359 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1364 /* Called when block BB has been reassigned to the cold partition,
1365 because it is now dominated by another cold block,
1366 to ensure that the region crossing attributes are updated. */
1368 static void
1369 fixup_new_cold_bb (basic_block bb)
1371 edge e;
1372 edge_iterator ei;
1374 /* This is called when a hot bb is found to now be dominated
1375 by a cold bb and therefore needs to become cold. Therefore,
1376 its preds will no longer be region crossing. Any non-dominating
1377 preds that were previously hot would also have become cold
1378 in the caller for the same region. Any preds that were previously
1379 region-crossing will be adjusted in fixup_partition_crossing. */
1380 FOR_EACH_EDGE (e, ei, bb->preds)
1382 fixup_partition_crossing (e);
1385 /* Possibly need to make bb's successor edges region crossing,
1386 or remove stale region crossing. */
1387 FOR_EACH_EDGE (e, ei, bb->succs)
1389 /* We can't have fall-through edges across partition boundaries.
1390 Note that force_nonfallthru will do any necessary partition
1391 boundary fixup by calling fixup_partition_crossing itself. */
1392 if ((e->flags & EDGE_FALLTHRU)
1393 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1394 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1395 force_nonfallthru (e);
1396 else
1397 fixup_partition_crossing (e);
1401 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1402 expense of adding new instructions or reordering basic blocks.
1404 Function can be also called with edge destination equivalent to the TARGET.
1405 Then it should try the simplifications and do nothing if none is possible.
1407 Return edge representing the branch if transformation succeeded. Return NULL
1408 on failure.
1409 We still return NULL in case E already destinated TARGET and we didn't
1410 managed to simplify instruction stream. */
1412 static edge
1413 rtl_redirect_edge_and_branch (edge e, basic_block target)
1415 edge ret;
1416 basic_block src = e->src;
1417 basic_block dest = e->dest;
1419 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1420 return NULL;
1422 if (dest == target)
1423 return e;
1425 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1427 df_set_bb_dirty (src);
1428 fixup_partition_crossing (ret);
1429 return ret;
1432 ret = redirect_branch_edge (e, target);
1433 if (!ret)
1434 return NULL;
1436 df_set_bb_dirty (src);
1437 fixup_partition_crossing (ret);
1438 return ret;
1441 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1443 void
1444 emit_barrier_after_bb (basic_block bb)
1446 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1447 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1448 || current_ir_type () == IR_RTL_CFGLAYOUT);
1449 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1451 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1453 if (BB_FOOTER (bb))
1455 rtx_insn *footer_tail = BB_FOOTER (bb);
1457 while (NEXT_INSN (footer_tail))
1458 footer_tail = NEXT_INSN (footer_tail);
1459 if (!BARRIER_P (footer_tail))
1461 SET_NEXT_INSN (footer_tail) = insn;
1462 SET_PREV_INSN (insn) = footer_tail;
1465 else
1466 BB_FOOTER (bb) = insn;
1470 /* Like force_nonfallthru below, but additionally performs redirection
1471 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1472 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1473 simple_return_rtx, indicating which kind of returnjump to create.
1474 It should be NULL otherwise. */
1476 basic_block
1477 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1479 basic_block jump_block, new_bb = NULL, src = e->src;
1480 rtx note;
1481 edge new_edge;
1482 int abnormal_edge_flags = 0;
1483 bool asm_goto_edge = false;
1484 int loc;
1486 /* In the case the last instruction is conditional jump to the next
1487 instruction, first redirect the jump itself and then continue
1488 by creating a basic block afterwards to redirect fallthru edge. */
1489 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1490 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1491 && any_condjump_p (BB_END (e->src))
1492 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1494 rtx note;
1495 edge b = unchecked_make_edge (e->src, target, 0);
1496 bool redirected;
1498 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1499 block_label (target), 0);
1500 gcc_assert (redirected);
1502 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1503 if (note)
1505 int prob = XINT (note, 0);
1507 b->probability = prob;
1508 /* Update this to use GCOV_COMPUTE_SCALE. */
1509 b->count = e->count * prob / REG_BR_PROB_BASE;
1510 e->probability -= e->probability;
1511 e->count -= b->count;
1512 if (e->probability < 0)
1513 e->probability = 0;
1514 if (e->count < 0)
1515 e->count = 0;
1519 if (e->flags & EDGE_ABNORMAL)
1521 /* Irritating special case - fallthru edge to the same block as abnormal
1522 edge.
1523 We can't redirect abnormal edge, but we still can split the fallthru
1524 one and create separate abnormal edge to original destination.
1525 This allows bb-reorder to make such edge non-fallthru. */
1526 gcc_assert (e->dest == target);
1527 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1528 e->flags &= EDGE_FALLTHRU;
1530 else
1532 gcc_assert (e->flags & EDGE_FALLTHRU);
1533 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1535 /* We can't redirect the entry block. Create an empty block
1536 at the start of the function which we use to add the new
1537 jump. */
1538 edge tmp;
1539 edge_iterator ei;
1540 bool found = false;
1542 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1543 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1545 /* Change the existing edge's source to be the new block, and add
1546 a new edge from the entry block to the new block. */
1547 e->src = bb;
1548 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1549 (tmp = ei_safe_edge (ei)); )
1551 if (tmp == e)
1553 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1554 found = true;
1555 break;
1557 else
1558 ei_next (&ei);
1561 gcc_assert (found);
1563 vec_safe_push (bb->succs, e);
1564 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1565 EDGE_FALLTHRU);
1569 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1570 don't point to the target or fallthru label. */
1571 if (JUMP_P (BB_END (e->src))
1572 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1573 && (e->flags & EDGE_FALLTHRU)
1574 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1576 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1577 bool adjust_jump_target = false;
1579 for (i = 0; i < n; ++i)
1581 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1583 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1584 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1585 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1586 adjust_jump_target = true;
1588 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1589 asm_goto_edge = true;
1591 if (adjust_jump_target)
1593 rtx_insn *insn = BB_END (e->src);
1594 rtx note;
1595 rtx_insn *old_label = BB_HEAD (e->dest);
1596 rtx_insn *new_label = BB_HEAD (target);
1598 if (JUMP_LABEL (insn) == old_label)
1600 JUMP_LABEL (insn) = new_label;
1601 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1602 if (note)
1603 remove_note (insn, note);
1605 else
1607 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1608 if (note)
1609 remove_note (insn, note);
1610 if (JUMP_LABEL (insn) != new_label
1611 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1612 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1614 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1615 != NULL_RTX)
1616 XEXP (note, 0) = new_label;
1620 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1622 rtx_insn *new_head;
1623 gcov_type count = e->count;
1624 int probability = e->probability;
1625 /* Create the new structures. */
1627 /* If the old block ended with a tablejump, skip its table
1628 by searching forward from there. Otherwise start searching
1629 forward from the last instruction of the old block. */
1630 rtx_jump_table_data *table;
1631 if (tablejump_p (BB_END (e->src), NULL, &table))
1632 new_head = table;
1633 else
1634 new_head = BB_END (e->src);
1635 new_head = NEXT_INSN (new_head);
1637 jump_block = create_basic_block (new_head, NULL, e->src);
1638 jump_block->count = count;
1639 jump_block->frequency = EDGE_FREQUENCY (e);
1641 /* Make sure new block ends up in correct hot/cold section. */
1643 BB_COPY_PARTITION (jump_block, e->src);
1645 /* Wire edge in. */
1646 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1647 new_edge->probability = probability;
1648 new_edge->count = count;
1650 /* Redirect old edge. */
1651 redirect_edge_pred (e, jump_block);
1652 e->probability = REG_BR_PROB_BASE;
1654 /* If e->src was previously region crossing, it no longer is
1655 and the reg crossing note should be removed. */
1656 fixup_partition_crossing (new_edge);
1658 /* If asm goto has any label refs to target's label,
1659 add also edge from asm goto bb to target. */
1660 if (asm_goto_edge)
1662 new_edge->probability /= 2;
1663 new_edge->count /= 2;
1664 jump_block->count /= 2;
1665 jump_block->frequency /= 2;
1666 new_edge = make_edge (new_edge->src, target,
1667 e->flags & ~EDGE_FALLTHRU);
1668 new_edge->probability = probability - probability / 2;
1669 new_edge->count = count - count / 2;
1672 new_bb = jump_block;
1674 else
1675 jump_block = e->src;
1677 loc = e->goto_locus;
1678 e->flags &= ~EDGE_FALLTHRU;
1679 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1681 if (jump_label == ret_rtx)
1682 emit_jump_insn_after_setloc (targetm.gen_return (),
1683 BB_END (jump_block), loc);
1684 else
1686 gcc_assert (jump_label == simple_return_rtx);
1687 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1688 BB_END (jump_block), loc);
1690 set_return_jump_label (BB_END (jump_block));
1692 else
1694 rtx_code_label *label = block_label (target);
1695 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1696 BB_END (jump_block), loc);
1697 JUMP_LABEL (BB_END (jump_block)) = label;
1698 LABEL_NUSES (label)++;
1701 /* We might be in cfg layout mode, and if so, the following routine will
1702 insert the barrier correctly. */
1703 emit_barrier_after_bb (jump_block);
1704 redirect_edge_succ_nodup (e, target);
1706 if (abnormal_edge_flags)
1707 make_edge (src, target, abnormal_edge_flags);
1709 df_mark_solutions_dirty ();
1710 fixup_partition_crossing (e);
1711 return new_bb;
1714 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1715 (and possibly create new basic block) to make edge non-fallthru.
1716 Return newly created BB or NULL if none. */
1718 static basic_block
1719 rtl_force_nonfallthru (edge e)
1721 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1724 /* Redirect edge even at the expense of creating new jump insn or
1725 basic block. Return new basic block if created, NULL otherwise.
1726 Conversion must be possible. */
1728 static basic_block
1729 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1731 if (redirect_edge_and_branch (e, target)
1732 || e->dest == target)
1733 return NULL;
1735 /* In case the edge redirection failed, try to force it to be non-fallthru
1736 and redirect newly created simplejump. */
1737 df_set_bb_dirty (e->src);
1738 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1741 /* The given edge should potentially be a fallthru edge. If that is in
1742 fact true, delete the jump and barriers that are in the way. */
1744 static void
1745 rtl_tidy_fallthru_edge (edge e)
1747 rtx_insn *q;
1748 basic_block b = e->src, c = b->next_bb;
1750 /* ??? In a late-running flow pass, other folks may have deleted basic
1751 blocks by nopping out blocks, leaving multiple BARRIERs between here
1752 and the target label. They ought to be chastised and fixed.
1754 We can also wind up with a sequence of undeletable labels between
1755 one block and the next.
1757 So search through a sequence of barriers, labels, and notes for
1758 the head of block C and assert that we really do fall through. */
1760 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1761 if (INSN_P (q))
1762 return;
1764 /* Remove what will soon cease being the jump insn from the source block.
1765 If block B consisted only of this single jump, turn it into a deleted
1766 note. */
1767 q = BB_END (b);
1768 if (JUMP_P (q)
1769 && onlyjump_p (q)
1770 && (any_uncondjump_p (q)
1771 || single_succ_p (b)))
1773 rtx_insn *label;
1774 rtx_jump_table_data *table;
1776 if (tablejump_p (q, &label, &table))
1778 /* The label is likely mentioned in some instruction before
1779 the tablejump and might not be DCEd, so turn it into
1780 a note instead and move before the tablejump that is going to
1781 be deleted. */
1782 const char *name = LABEL_NAME (label);
1783 PUT_CODE (label, NOTE);
1784 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1785 NOTE_DELETED_LABEL_NAME (label) = name;
1786 reorder_insns (label, label, PREV_INSN (q));
1787 delete_insn (table);
1790 /* If this was a conditional jump, we need to also delete
1791 the insn that set cc0. */
1792 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1793 q = PREV_INSN (q);
1795 q = PREV_INSN (q);
1797 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1798 together with the barrier) should never have a fallthru edge. */
1799 else if (JUMP_P (q) && any_uncondjump_p (q))
1800 return;
1802 /* Selectively unlink the sequence. */
1803 if (q != PREV_INSN (BB_HEAD (c)))
1804 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1806 e->flags |= EDGE_FALLTHRU;
1809 /* Should move basic block BB after basic block AFTER. NIY. */
1811 static bool
1812 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1813 basic_block after ATTRIBUTE_UNUSED)
1815 return false;
1818 /* Locate the last bb in the same partition as START_BB. */
1820 static basic_block
1821 last_bb_in_partition (basic_block start_bb)
1823 basic_block bb;
1824 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1826 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1827 return bb;
1829 /* Return bb before the exit block. */
1830 return bb->prev_bb;
1833 /* Split a (typically critical) edge. Return the new block.
1834 The edge must not be abnormal.
1836 ??? The code generally expects to be called on critical edges.
1837 The case of a block ending in an unconditional jump to a
1838 block with multiple predecessors is not handled optimally. */
1840 static basic_block
1841 rtl_split_edge (edge edge_in)
1843 basic_block bb, new_bb;
1844 rtx_insn *before;
1846 /* Abnormal edges cannot be split. */
1847 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1849 /* We are going to place the new block in front of edge destination.
1850 Avoid existence of fallthru predecessors. */
1851 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1853 edge e = find_fallthru_edge (edge_in->dest->preds);
1855 if (e)
1856 force_nonfallthru (e);
1859 /* Create the basic block note. */
1860 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1861 before = BB_HEAD (edge_in->dest);
1862 else
1863 before = NULL;
1865 /* If this is a fall through edge to the exit block, the blocks might be
1866 not adjacent, and the right place is after the source. */
1867 if ((edge_in->flags & EDGE_FALLTHRU)
1868 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1870 before = NEXT_INSN (BB_END (edge_in->src));
1871 bb = create_basic_block (before, NULL, edge_in->src);
1872 BB_COPY_PARTITION (bb, edge_in->src);
1874 else
1876 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1878 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1879 BB_COPY_PARTITION (bb, edge_in->dest);
1881 else
1883 basic_block after = edge_in->dest->prev_bb;
1884 /* If this is post-bb reordering, and the edge crosses a partition
1885 boundary, the new block needs to be inserted in the bb chain
1886 at the end of the src partition (since we put the new bb into
1887 that partition, see below). Otherwise we may end up creating
1888 an extra partition crossing in the chain, which is illegal.
1889 It can't go after the src, because src may have a fall-through
1890 to a different block. */
1891 if (crtl->bb_reorder_complete
1892 && (edge_in->flags & EDGE_CROSSING))
1894 after = last_bb_in_partition (edge_in->src);
1895 before = get_last_bb_insn (after);
1896 /* The instruction following the last bb in partition should
1897 be a barrier, since it cannot end in a fall-through. */
1898 gcc_checking_assert (BARRIER_P (before));
1899 before = NEXT_INSN (before);
1901 bb = create_basic_block (before, NULL, after);
1902 /* Put the split bb into the src partition, to avoid creating
1903 a situation where a cold bb dominates a hot bb, in the case
1904 where src is cold and dest is hot. The src will dominate
1905 the new bb (whereas it might not have dominated dest). */
1906 BB_COPY_PARTITION (bb, edge_in->src);
1910 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1912 /* Can't allow a region crossing edge to be fallthrough. */
1913 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1914 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1916 new_bb = force_nonfallthru (single_succ_edge (bb));
1917 gcc_assert (!new_bb);
1920 /* For non-fallthru edges, we must adjust the predecessor's
1921 jump instruction to target our new block. */
1922 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1924 edge redirected = redirect_edge_and_branch (edge_in, bb);
1925 gcc_assert (redirected);
1927 else
1929 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1931 /* For asm goto even splitting of fallthru edge might
1932 need insn patching, as other labels might point to the
1933 old label. */
1934 rtx_insn *last = BB_END (edge_in->src);
1935 if (last
1936 && JUMP_P (last)
1937 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1938 && (extract_asm_operands (PATTERN (last))
1939 || JUMP_LABEL (last) == before)
1940 && patch_jump_insn (last, before, bb))
1941 df_set_bb_dirty (edge_in->src);
1943 redirect_edge_succ (edge_in, bb);
1946 return bb;
1949 /* Queue instructions for insertion on an edge between two basic blocks.
1950 The new instructions and basic blocks (if any) will not appear in the
1951 CFG until commit_edge_insertions is called. */
1953 void
1954 insert_insn_on_edge (rtx pattern, edge e)
1956 /* We cannot insert instructions on an abnormal critical edge.
1957 It will be easier to find the culprit if we die now. */
1958 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1960 if (e->insns.r == NULL_RTX)
1961 start_sequence ();
1962 else
1963 push_to_sequence (e->insns.r);
1965 emit_insn (pattern);
1967 e->insns.r = get_insns ();
1968 end_sequence ();
1971 /* Update the CFG for the instructions queued on edge E. */
1973 void
1974 commit_one_edge_insertion (edge e)
1976 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1977 basic_block bb;
1979 /* Pull the insns off the edge now since the edge might go away. */
1980 insns = e->insns.r;
1981 e->insns.r = NULL;
1983 /* Figure out where to put these insns. If the destination has
1984 one predecessor, insert there. Except for the exit block. */
1985 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1987 bb = e->dest;
1989 /* Get the location correct wrt a code label, and "nice" wrt
1990 a basic block note, and before everything else. */
1991 tmp = BB_HEAD (bb);
1992 if (LABEL_P (tmp))
1993 tmp = NEXT_INSN (tmp);
1994 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1995 tmp = NEXT_INSN (tmp);
1996 if (tmp == BB_HEAD (bb))
1997 before = tmp;
1998 else if (tmp)
1999 after = PREV_INSN (tmp);
2000 else
2001 after = get_last_insn ();
2004 /* If the source has one successor and the edge is not abnormal,
2005 insert there. Except for the entry block.
2006 Don't do this if the predecessor ends in a jump other than
2007 unconditional simple jump. E.g. for asm goto that points all
2008 its labels at the fallthru basic block, we can't insert instructions
2009 before the asm goto, as the asm goto can have various of side effects,
2010 and can't emit instructions after the asm goto, as it must end
2011 the basic block. */
2012 else if ((e->flags & EDGE_ABNORMAL) == 0
2013 && single_succ_p (e->src)
2014 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2015 && (!JUMP_P (BB_END (e->src))
2016 || simplejump_p (BB_END (e->src))))
2018 bb = e->src;
2020 /* It is possible to have a non-simple jump here. Consider a target
2021 where some forms of unconditional jumps clobber a register. This
2022 happens on the fr30 for example.
2024 We know this block has a single successor, so we can just emit
2025 the queued insns before the jump. */
2026 if (JUMP_P (BB_END (bb)))
2027 before = BB_END (bb);
2028 else
2030 /* We'd better be fallthru, or we've lost track of what's what. */
2031 gcc_assert (e->flags & EDGE_FALLTHRU);
2033 after = BB_END (bb);
2037 /* Otherwise we must split the edge. */
2038 else
2040 bb = split_edge (e);
2042 /* If E crossed a partition boundary, we needed to make bb end in
2043 a region-crossing jump, even though it was originally fallthru. */
2044 if (JUMP_P (BB_END (bb)))
2045 before = BB_END (bb);
2046 else
2047 after = BB_END (bb);
2050 /* Now that we've found the spot, do the insertion. */
2051 if (before)
2053 emit_insn_before_noloc (insns, before, bb);
2054 last = prev_nonnote_insn (before);
2056 else
2057 last = emit_insn_after_noloc (insns, after, bb);
2059 if (returnjump_p (last))
2061 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2062 This is not currently a problem because this only happens
2063 for the (single) epilogue, which already has a fallthru edge
2064 to EXIT. */
2066 e = single_succ_edge (bb);
2067 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2068 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2070 e->flags &= ~EDGE_FALLTHRU;
2071 emit_barrier_after (last);
2073 if (before)
2074 delete_insn (before);
2076 else
2077 gcc_assert (!JUMP_P (last));
2080 /* Update the CFG for all queued instructions. */
2082 void
2083 commit_edge_insertions (void)
2085 basic_block bb;
2087 /* Optimization passes that invoke this routine can cause hot blocks
2088 previously reached by both hot and cold blocks to become dominated only
2089 by cold blocks. This will cause the verification below to fail,
2090 and lead to now cold code in the hot section. In some cases this
2091 may only be visible after newly unreachable blocks are deleted,
2092 which will be done by fixup_partitions. */
2093 fixup_partitions ();
2095 checking_verify_flow_info ();
2097 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2098 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2100 edge e;
2101 edge_iterator ei;
2103 FOR_EACH_EDGE (e, ei, bb->succs)
2104 if (e->insns.r)
2105 commit_one_edge_insertion (e);
2110 /* Print out RTL-specific basic block information (live information
2111 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2112 documented in dumpfile.h. */
2114 static void
2115 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
2117 rtx_insn *insn;
2118 rtx_insn *last;
2119 char *s_indent;
2121 s_indent = (char *) alloca ((size_t) indent + 1);
2122 memset (s_indent, ' ', (size_t) indent);
2123 s_indent[indent] = '\0';
2125 if (df && (flags & TDF_DETAILS))
2127 df_dump_top (bb, outf);
2128 putc ('\n', outf);
2131 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2132 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
2133 insn = NEXT_INSN (insn))
2135 if (flags & TDF_DETAILS)
2136 df_dump_insn_top (insn, outf);
2137 if (! (flags & TDF_SLIM))
2138 print_rtl_single (outf, insn);
2139 else
2140 dump_insn_slim (outf, insn);
2141 if (flags & TDF_DETAILS)
2142 df_dump_insn_bottom (insn, outf);
2145 if (df && (flags & TDF_DETAILS))
2147 df_dump_bottom (bb, outf);
2148 putc ('\n', outf);
2153 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2154 for the start of each basic block. FLAGS are the TDF_* masks documented
2155 in dumpfile.h. */
2157 void
2158 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags)
2160 const rtx_insn *tmp_rtx;
2161 if (rtx_first == 0)
2162 fprintf (outf, "(nil)\n");
2163 else
2165 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2166 int max_uid = get_max_uid ();
2167 basic_block *start = XCNEWVEC (basic_block, max_uid);
2168 basic_block *end = XCNEWVEC (basic_block, max_uid);
2169 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2170 basic_block bb;
2172 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2173 insns, but the CFG is not maintained so the basic block info
2174 is not reliable. Therefore it's omitted from the dumps. */
2175 if (! (cfun->curr_properties & PROP_cfg))
2176 flags &= ~TDF_BLOCKS;
2178 if (df)
2179 df_dump_start (outf);
2181 if (flags & TDF_BLOCKS)
2183 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2185 rtx_insn *x;
2187 start[INSN_UID (BB_HEAD (bb))] = bb;
2188 end[INSN_UID (BB_END (bb))] = bb;
2189 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2191 enum bb_state state = IN_MULTIPLE_BB;
2193 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2194 state = IN_ONE_BB;
2195 in_bb_p[INSN_UID (x)] = state;
2197 if (x == BB_END (bb))
2198 break;
2203 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2205 if (flags & TDF_BLOCKS)
2207 bb = start[INSN_UID (tmp_rtx)];
2208 if (bb != NULL)
2210 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
2211 if (df && (flags & TDF_DETAILS))
2212 df_dump_top (bb, outf);
2215 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2216 && !NOTE_P (tmp_rtx)
2217 && !BARRIER_P (tmp_rtx))
2218 fprintf (outf, ";; Insn is not within a basic block\n");
2219 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2220 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2223 if (flags & TDF_DETAILS)
2224 df_dump_insn_top (tmp_rtx, outf);
2225 if (! (flags & TDF_SLIM))
2226 print_rtl_single (outf, tmp_rtx);
2227 else
2228 dump_insn_slim (outf, tmp_rtx);
2229 if (flags & TDF_DETAILS)
2230 df_dump_insn_bottom (tmp_rtx, outf);
2232 if (flags & TDF_BLOCKS)
2234 bb = end[INSN_UID (tmp_rtx)];
2235 if (bb != NULL)
2237 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
2238 if (df && (flags & TDF_DETAILS))
2239 df_dump_bottom (bb, outf);
2240 putc ('\n', outf);
2245 free (start);
2246 free (end);
2247 free (in_bb_p);
2251 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2253 void
2254 update_br_prob_note (basic_block bb)
2256 rtx note;
2257 if (!JUMP_P (BB_END (bb)))
2258 return;
2259 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2260 if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability)
2261 return;
2262 XINT (note, 0) = BRANCH_EDGE (bb)->probability;
2265 /* Get the last insn associated with block BB (that includes barriers and
2266 tablejumps after BB). */
2267 rtx_insn *
2268 get_last_bb_insn (basic_block bb)
2270 rtx_jump_table_data *table;
2271 rtx_insn *tmp;
2272 rtx_insn *end = BB_END (bb);
2274 /* Include any jump table following the basic block. */
2275 if (tablejump_p (end, NULL, &table))
2276 end = table;
2278 /* Include any barriers that may follow the basic block. */
2279 tmp = next_nonnote_insn_bb (end);
2280 while (tmp && BARRIER_P (tmp))
2282 end = tmp;
2283 tmp = next_nonnote_insn_bb (end);
2286 return end;
2289 /* Sanity check partition hotness to ensure that basic blocks in
2290   the cold partition don't dominate basic blocks in the hot partition.
2291 If FLAG_ONLY is true, report violations as errors. Otherwise
2292 re-mark the dominated blocks as cold, since this is run after
2293 cfg optimizations that may make hot blocks previously reached
2294 by both hot and cold blocks now only reachable along cold paths. */
2296 static vec<basic_block>
2297 find_partition_fixes (bool flag_only)
2299 basic_block bb;
2300 vec<basic_block> bbs_in_cold_partition = vNULL;
2301 vec<basic_block> bbs_to_fix = vNULL;
2303 /* Callers check this. */
2304 gcc_checking_assert (crtl->has_bb_partition);
2306 FOR_EACH_BB_FN (bb, cfun)
2307 if ((BB_PARTITION (bb) == BB_COLD_PARTITION))
2308 bbs_in_cold_partition.safe_push (bb);
2310 if (bbs_in_cold_partition.is_empty ())
2311 return vNULL;
2313 bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS);
2315 if (dom_calculated_here)
2316 calculate_dominance_info (CDI_DOMINATORS);
2318 while (! bbs_in_cold_partition.is_empty ())
2320 bb = bbs_in_cold_partition.pop ();
2321 /* Any blocks dominated by a block in the cold section
2322 must also be cold. */
2323 basic_block son;
2324 for (son = first_dom_son (CDI_DOMINATORS, bb);
2325 son;
2326 son = next_dom_son (CDI_DOMINATORS, son))
2328 /* If son is not yet cold, then mark it cold here and
2329 enqueue it for further processing. */
2330 if ((BB_PARTITION (son) != BB_COLD_PARTITION))
2332 if (flag_only)
2333 error ("non-cold basic block %d dominated "
2334 "by a block in the cold partition (%d)", son->index, bb->index);
2335 else
2336 BB_SET_PARTITION (son, BB_COLD_PARTITION);
2337 bbs_to_fix.safe_push (son);
2338 bbs_in_cold_partition.safe_push (son);
2343 if (dom_calculated_here)
2344 free_dominance_info (CDI_DOMINATORS);
2346 return bbs_to_fix;
2349 /* Perform cleanup on the hot/cold bb partitioning after optimization
2350 passes that modify the cfg. */
2352 void
2353 fixup_partitions (void)
2355 basic_block bb;
2357 if (!crtl->has_bb_partition)
2358 return;
2360 /* Delete any blocks that became unreachable and weren't
2361 already cleaned up, for example during edge forwarding
2362 and convert_jumps_to_returns. This will expose more
2363 opportunities for fixing the partition boundaries here.
2364 Also, the calculation of the dominance graph during verification
2365 will assert if there are unreachable nodes. */
2366 delete_unreachable_blocks ();
2368 /* If there are partitions, do a sanity check on them: A basic block in
2369   a cold partition cannot dominate a basic block in a hot partition.
2370 Fixup any that now violate this requirement, as a result of edge
2371 forwarding and unreachable block deletion.  */
2372 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2374 /* Do the partition fixup after all necessary blocks have been converted to
2375 cold, so that we only update the region crossings the minimum number of
2376 places, which can require forcing edges to be non fallthru. */
2377 while (! bbs_to_fix.is_empty ())
2379 bb = bbs_to_fix.pop ();
2380 fixup_new_cold_bb (bb);
2384 /* Verify, in the basic block chain, that there is at most one switch
2385 between hot/cold partitions. This condition will not be true until
2386 after reorder_basic_blocks is called. */
2388 static int
2389 verify_hot_cold_block_grouping (void)
2391 basic_block bb;
2392 int err = 0;
2393 bool switched_sections = false;
2394 int current_partition = BB_UNPARTITIONED;
2396 /* Even after bb reordering is complete, we go into cfglayout mode
2397 again (in compgoto). Ensure we don't call this before going back
2398 into linearized RTL when any layout fixes would have been committed. */
2399 if (!crtl->bb_reorder_complete
2400 || current_ir_type () != IR_RTL_CFGRTL)
2401 return err;
2403 FOR_EACH_BB_FN (bb, cfun)
2405 if (current_partition != BB_UNPARTITIONED
2406 && BB_PARTITION (bb) != current_partition)
2408 if (switched_sections)
2410 error ("multiple hot/cold transitions found (bb %i)",
2411 bb->index);
2412 err = 1;
2414 else
2415 switched_sections = true;
2417 if (!crtl->has_bb_partition)
2418 error ("partition found but function partition flag not set");
2420 current_partition = BB_PARTITION (bb);
2423 return err;
2427 /* Perform several checks on the edges out of each block, such as
2428 the consistency of the branch probabilities, the correctness
2429 of hot/cold partition crossing edges, and the number of expected
2430 successor edges. Also verify that the dominance relationship
2431 between hot/cold blocks is sane. */
2433 static int
2434 rtl_verify_edges (void)
2436 int err = 0;
2437 basic_block bb;
2439 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2441 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2442 int n_eh = 0, n_abnormal = 0;
2443 edge e, fallthru = NULL;
2444 edge_iterator ei;
2445 rtx note;
2446 bool has_crossing_edge = false;
2448 if (JUMP_P (BB_END (bb))
2449 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2450 && EDGE_COUNT (bb->succs) >= 2
2451 && any_condjump_p (BB_END (bb)))
2453 if (XINT (note, 0) != BRANCH_EDGE (bb)->probability
2454 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2456 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2457 XINT (note, 0), BRANCH_EDGE (bb)->probability);
2458 err = 1;
2462 FOR_EACH_EDGE (e, ei, bb->succs)
2464 bool is_crossing;
2466 if (e->flags & EDGE_FALLTHRU)
2467 n_fallthru++, fallthru = e;
2469 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2470 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2471 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2472 has_crossing_edge |= is_crossing;
2473 if (e->flags & EDGE_CROSSING)
2475 if (!is_crossing)
2477 error ("EDGE_CROSSING incorrectly set across same section");
2478 err = 1;
2480 if (e->flags & EDGE_FALLTHRU)
2482 error ("fallthru edge crosses section boundary in bb %i",
2483 e->src->index);
2484 err = 1;
2486 if (e->flags & EDGE_EH)
2488 error ("EH edge crosses section boundary in bb %i",
2489 e->src->index);
2490 err = 1;
2492 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2494 error ("No region crossing jump at section boundary in bb %i",
2495 bb->index);
2496 err = 1;
2499 else if (is_crossing)
2501 error ("EDGE_CROSSING missing across section boundary");
2502 err = 1;
2505 if ((e->flags & ~(EDGE_DFS_BACK
2506 | EDGE_CAN_FALLTHRU
2507 | EDGE_IRREDUCIBLE_LOOP
2508 | EDGE_LOOP_EXIT
2509 | EDGE_CROSSING
2510 | EDGE_PRESERVE)) == 0)
2511 n_branch++;
2513 if (e->flags & EDGE_ABNORMAL_CALL)
2514 n_abnormal_call++;
2516 if (e->flags & EDGE_SIBCALL)
2517 n_sibcall++;
2519 if (e->flags & EDGE_EH)
2520 n_eh++;
2522 if (e->flags & EDGE_ABNORMAL)
2523 n_abnormal++;
2526 if (!has_crossing_edge
2527 && JUMP_P (BB_END (bb))
2528 && CROSSING_JUMP_P (BB_END (bb)))
2530 print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS);
2531 error ("Region crossing jump across same section in bb %i",
2532 bb->index);
2533 err = 1;
2536 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2538 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2539 err = 1;
2541 if (n_eh > 1)
2543 error ("too many exception handling edges in bb %i", bb->index);
2544 err = 1;
2546 if (n_branch
2547 && (!JUMP_P (BB_END (bb))
2548 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2549 || any_condjump_p (BB_END (bb))))))
2551 error ("too many outgoing branch edges from bb %i", bb->index);
2552 err = 1;
2554 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2556 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2557 err = 1;
2559 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2561 error ("wrong number of branch edges after unconditional jump"
2562 " in bb %i", bb->index);
2563 err = 1;
2565 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2566 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2568 error ("wrong amount of branch edges after conditional jump"
2569 " in bb %i", bb->index);
2570 err = 1;
2572 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2574 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2575 err = 1;
2577 if (n_sibcall && !CALL_P (BB_END (bb)))
2579 error ("sibcall edges for non-call insn in bb %i", bb->index);
2580 err = 1;
2582 if (n_abnormal > n_eh
2583 && !(CALL_P (BB_END (bb))
2584 && n_abnormal == n_abnormal_call + n_sibcall)
2585 && (!JUMP_P (BB_END (bb))
2586 || any_condjump_p (BB_END (bb))
2587 || any_uncondjump_p (BB_END (bb))))
2589 error ("abnormal edges for no purpose in bb %i", bb->index);
2590 err = 1;
2594 /* If there are partitions, do a sanity check on them: A basic block in
2595   a cold partition cannot dominate a basic block in a hot partition.  */
2596 if (crtl->has_bb_partition && !err)
2598 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2599 err = !bbs_to_fix.is_empty ();
2602 /* Clean up. */
2603 return err;
2606 /* Checks on the instructions within blocks. Currently checks that each
2607 block starts with a basic block note, and that basic block notes and
2608 control flow jumps are not found in the middle of the block. */
2610 static int
2611 rtl_verify_bb_insns (void)
2613 rtx_insn *x;
2614 int err = 0;
2615 basic_block bb;
2617 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2619 /* Now check the header of basic
2620 block. It ought to contain optional CODE_LABEL followed
2621 by NOTE_BASIC_BLOCK. */
2622 x = BB_HEAD (bb);
2623 if (LABEL_P (x))
2625 if (BB_END (bb) == x)
2627 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2628 bb->index);
2629 err = 1;
2632 x = NEXT_INSN (x);
2635 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2637 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2638 bb->index);
2639 err = 1;
2642 if (BB_END (bb) == x)
2643 /* Do checks for empty blocks here. */
2645 else
2646 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2648 if (NOTE_INSN_BASIC_BLOCK_P (x))
2650 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2651 INSN_UID (x), bb->index);
2652 err = 1;
2655 if (x == BB_END (bb))
2656 break;
2658 if (control_flow_insn_p (x))
2660 error ("in basic block %d:", bb->index);
2661 fatal_insn ("flow control insn inside a basic block", x);
2666 /* Clean up. */
2667 return err;
2670 /* Verify that block pointers for instructions in basic blocks, headers and
2671 footers are set appropriately. */
2673 static int
2674 rtl_verify_bb_pointers (void)
2676 int err = 0;
2677 basic_block bb;
2679 /* Check the general integrity of the basic blocks. */
2680 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2682 rtx_insn *insn;
2684 if (!(bb->flags & BB_RTL))
2686 error ("BB_RTL flag not set for block %d", bb->index);
2687 err = 1;
2690 FOR_BB_INSNS (bb, insn)
2691 if (BLOCK_FOR_INSN (insn) != bb)
2693 error ("insn %d basic block pointer is %d, should be %d",
2694 INSN_UID (insn),
2695 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2696 bb->index);
2697 err = 1;
2700 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2701 if (!BARRIER_P (insn)
2702 && BLOCK_FOR_INSN (insn) != NULL)
2704 error ("insn %d in header of bb %d has non-NULL basic block",
2705 INSN_UID (insn), bb->index);
2706 err = 1;
2708 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2709 if (!BARRIER_P (insn)
2710 && BLOCK_FOR_INSN (insn) != NULL)
2712 error ("insn %d in footer of bb %d has non-NULL basic block",
2713 INSN_UID (insn), bb->index);
2714 err = 1;
2718 /* Clean up. */
2719 return err;
2722 /* Verify the CFG and RTL consistency common for both underlying RTL and
2723 cfglayout RTL.
2725 Currently it does following checks:
2727 - overlapping of basic blocks
2728 - insns with wrong BLOCK_FOR_INSN pointers
2729 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2730 - tails of basic blocks (ensure that boundary is necessary)
2731 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2732 and NOTE_INSN_BASIC_BLOCK
2733 - verify that no fall_thru edge crosses hot/cold partition boundaries
2734 - verify that there are no pending RTL branch predictions
2735 - verify that hot blocks are not dominated by cold blocks
2737 In future it can be extended check a lot of other stuff as well
2738 (reachability of basic blocks, life information, etc. etc.). */
2740 static int
2741 rtl_verify_flow_info_1 (void)
2743 int err = 0;
2745 err |= rtl_verify_bb_pointers ();
2747 err |= rtl_verify_bb_insns ();
2749 err |= rtl_verify_edges ();
2751 return err;
2754 /* Walk the instruction chain and verify that bb head/end pointers
2755 are correct, and that instructions are in exactly one bb and have
2756 correct block pointers. */
2758 static int
2759 rtl_verify_bb_insn_chain (void)
2761 basic_block bb;
2762 int err = 0;
2763 rtx_insn *x;
2764 rtx_insn *last_head = get_last_insn ();
2765 basic_block *bb_info;
2766 const int max_uid = get_max_uid ();
2768 bb_info = XCNEWVEC (basic_block, max_uid);
2770 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2772 rtx_insn *head = BB_HEAD (bb);
2773 rtx_insn *end = BB_END (bb);
2775 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2777 /* Verify the end of the basic block is in the INSN chain. */
2778 if (x == end)
2779 break;
2781 /* And that the code outside of basic blocks has NULL bb field. */
2782 if (!BARRIER_P (x)
2783 && BLOCK_FOR_INSN (x) != NULL)
2785 error ("insn %d outside of basic blocks has non-NULL bb field",
2786 INSN_UID (x));
2787 err = 1;
2791 if (!x)
2793 error ("end insn %d for block %d not found in the insn stream",
2794 INSN_UID (end), bb->index);
2795 err = 1;
2798 /* Work backwards from the end to the head of the basic block
2799 to verify the head is in the RTL chain. */
2800 for (; x != NULL_RTX; x = PREV_INSN (x))
2802 /* While walking over the insn chain, verify insns appear
2803 in only one basic block. */
2804 if (bb_info[INSN_UID (x)] != NULL)
2806 error ("insn %d is in multiple basic blocks (%d and %d)",
2807 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2808 err = 1;
2811 bb_info[INSN_UID (x)] = bb;
2813 if (x == head)
2814 break;
2816 if (!x)
2818 error ("head insn %d for block %d not found in the insn stream",
2819 INSN_UID (head), bb->index);
2820 err = 1;
2823 last_head = PREV_INSN (x);
2826 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2828 /* Check that the code before the first basic block has NULL
2829 bb field. */
2830 if (!BARRIER_P (x)
2831 && BLOCK_FOR_INSN (x) != NULL)
2833 error ("insn %d outside of basic blocks has non-NULL bb field",
2834 INSN_UID (x));
2835 err = 1;
2838 free (bb_info);
2840 return err;
2843 /* Verify that fallthru edges point to adjacent blocks in layout order and
2844 that barriers exist after non-fallthru blocks. */
2846 static int
2847 rtl_verify_fallthru (void)
2849 basic_block bb;
2850 int err = 0;
2852 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2854 edge e;
2856 e = find_fallthru_edge (bb->succs);
2857 if (!e)
2859 rtx_insn *insn;
2861 /* Ensure existence of barrier in BB with no fallthru edges. */
2862 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2864 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2866 error ("missing barrier after block %i", bb->index);
2867 err = 1;
2868 break;
2870 if (BARRIER_P (insn))
2871 break;
2874 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2875 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2877 rtx_insn *insn;
2879 if (e->src->next_bb != e->dest)
2881 error
2882 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2883 e->src->index, e->dest->index);
2884 err = 1;
2886 else
2887 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2888 insn = NEXT_INSN (insn))
2889 if (BARRIER_P (insn) || INSN_P (insn))
2891 error ("verify_flow_info: Incorrect fallthru %i->%i",
2892 e->src->index, e->dest->index);
2893 fatal_insn ("wrong insn in the fallthru edge", insn);
2894 err = 1;
2899 return err;
2902 /* Verify that blocks are laid out in consecutive order. While walking the
2903 instructions, verify that all expected instructions are inside the basic
2904 blocks, and that all returns are followed by barriers. */
2906 static int
2907 rtl_verify_bb_layout (void)
2909 basic_block bb;
2910 int err = 0;
2911 rtx_insn *x;
2912 int num_bb_notes;
2913 rtx_insn * const rtx_first = get_insns ();
2914 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2916 num_bb_notes = 0;
2917 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2919 for (x = rtx_first; x; x = NEXT_INSN (x))
2921 if (NOTE_INSN_BASIC_BLOCK_P (x))
2923 bb = NOTE_BASIC_BLOCK (x);
2925 num_bb_notes++;
2926 if (bb != last_bb_seen->next_bb)
2927 internal_error ("basic blocks not laid down consecutively");
2929 curr_bb = last_bb_seen = bb;
2932 if (!curr_bb)
2934 switch (GET_CODE (x))
2936 case BARRIER:
2937 case NOTE:
2938 break;
2940 case CODE_LABEL:
2941 /* An ADDR_VEC is placed outside any basic block. */
2942 if (NEXT_INSN (x)
2943 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2944 x = NEXT_INSN (x);
2946 /* But in any case, non-deletable labels can appear anywhere. */
2947 break;
2949 default:
2950 fatal_insn ("insn outside basic block", x);
2954 if (JUMP_P (x)
2955 && returnjump_p (x) && ! condjump_p (x)
2956 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2957 fatal_insn ("return not followed by barrier", x);
2959 if (curr_bb && x == BB_END (curr_bb))
2960 curr_bb = NULL;
2963 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2964 internal_error
2965 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2966 num_bb_notes, n_basic_blocks_for_fn (cfun));
2968 return err;
2971 /* Verify the CFG and RTL consistency common for both underlying RTL and
2972 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2974 Currently it does following checks:
2975 - all checks of rtl_verify_flow_info_1
2976 - test head/end pointers
2977 - check that blocks are laid out in consecutive order
2978 - check that all insns are in the basic blocks
2979 (except the switch handling code, barriers and notes)
2980 - check that all returns are followed by barriers
2981 - check that all fallthru edge points to the adjacent blocks
2982 - verify that there is a single hot/cold partition boundary after bbro */
2984 static int
2985 rtl_verify_flow_info (void)
2987 int err = 0;
2989 err |= rtl_verify_flow_info_1 ();
2991 err |= rtl_verify_bb_insn_chain ();
2993 err |= rtl_verify_fallthru ();
2995 err |= rtl_verify_bb_layout ();
2997 err |= verify_hot_cold_block_grouping ();
2999 return err;
3002 /* Assume that the preceding pass has possibly eliminated jump instructions
3003 or converted the unconditional jumps. Eliminate the edges from CFG.
3004 Return true if any edges are eliminated. */
3006 bool
3007 purge_dead_edges (basic_block bb)
3009 edge e;
3010 rtx_insn *insn = BB_END (bb);
3011 rtx note;
3012 bool purged = false;
3013 bool found;
3014 edge_iterator ei;
3016 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3018 insn = PREV_INSN (insn);
3019 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3021 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3022 if (NONJUMP_INSN_P (insn)
3023 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3025 rtx eqnote;
3027 if (! may_trap_p (PATTERN (insn))
3028 || ((eqnote = find_reg_equal_equiv_note (insn))
3029 && ! may_trap_p (XEXP (eqnote, 0))))
3030 remove_note (insn, note);
3033 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3034 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3036 bool remove = false;
3038 /* There are three types of edges we need to handle correctly here: EH
3039 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3040 latter can appear when nonlocal gotos are used. */
3041 if (e->flags & EDGE_ABNORMAL_CALL)
3043 if (!CALL_P (insn))
3044 remove = true;
3045 else if (can_nonlocal_goto (insn))
3047 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3049 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3051 else
3052 remove = true;
3054 else if (e->flags & EDGE_EH)
3055 remove = !can_throw_internal (insn);
3057 if (remove)
3059 remove_edge (e);
3060 df_set_bb_dirty (bb);
3061 purged = true;
3063 else
3064 ei_next (&ei);
3067 if (JUMP_P (insn))
3069 rtx note;
3070 edge b,f;
3071 edge_iterator ei;
3073 /* We do care only about conditional jumps and simplejumps. */
3074 if (!any_condjump_p (insn)
3075 && !returnjump_p (insn)
3076 && !simplejump_p (insn))
3077 return purged;
3079 /* Branch probability/prediction notes are defined only for
3080 condjumps. We've possibly turned condjump into simplejump. */
3081 if (simplejump_p (insn))
3083 note = find_reg_note (insn, REG_BR_PROB, NULL);
3084 if (note)
3085 remove_note (insn, note);
3086 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3087 remove_note (insn, note);
3090 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3092 /* Avoid abnormal flags to leak from computed jumps turned
3093 into simplejumps. */
3095 e->flags &= ~EDGE_ABNORMAL;
3097 /* See if this edge is one we should keep. */
3098 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3099 /* A conditional jump can fall through into the next
3100 block, so we should keep the edge. */
3102 ei_next (&ei);
3103 continue;
3105 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3106 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3107 /* If the destination block is the target of the jump,
3108 keep the edge. */
3110 ei_next (&ei);
3111 continue;
3113 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3114 && returnjump_p (insn))
3115 /* If the destination block is the exit block, and this
3116 instruction is a return, then keep the edge. */
3118 ei_next (&ei);
3119 continue;
3121 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3122 /* Keep the edges that correspond to exceptions thrown by
3123 this instruction and rematerialize the EDGE_ABNORMAL
3124 flag we just cleared above. */
3126 e->flags |= EDGE_ABNORMAL;
3127 ei_next (&ei);
3128 continue;
3131 /* We do not need this edge. */
3132 df_set_bb_dirty (bb);
3133 purged = true;
3134 remove_edge (e);
3137 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3138 return purged;
3140 if (dump_file)
3141 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3143 if (!optimize)
3144 return purged;
3146 /* Redistribute probabilities. */
3147 if (single_succ_p (bb))
3149 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3150 single_succ_edge (bb)->count = bb->count;
3152 else
3154 note = find_reg_note (insn, REG_BR_PROB, NULL);
3155 if (!note)
3156 return purged;
3158 b = BRANCH_EDGE (bb);
3159 f = FALLTHRU_EDGE (bb);
3160 b->probability = XINT (note, 0);
3161 f->probability = REG_BR_PROB_BASE - b->probability;
3162 /* Update these to use GCOV_COMPUTE_SCALE. */
3163 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
3164 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
3167 return purged;
3169 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3171 /* First, there should not be any EH or ABCALL edges resulting
3172 from non-local gotos and the like. If there were, we shouldn't
3173 have created the sibcall in the first place. Second, there
3174 should of course never have been a fallthru edge. */
3175 gcc_assert (single_succ_p (bb));
3176 gcc_assert (single_succ_edge (bb)->flags
3177 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3179 return 0;
3182 /* If we don't see a jump insn, we don't know exactly why the block would
3183 have been broken at this point. Look for a simple, non-fallthru edge,
3184 as these are only created by conditional branches. If we find such an
3185 edge we know that there used to be a jump here and can then safely
3186 remove all non-fallthru edges. */
3187 found = false;
3188 FOR_EACH_EDGE (e, ei, bb->succs)
3189 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3191 found = true;
3192 break;
3195 if (!found)
3196 return purged;
3198 /* Remove all but the fake and fallthru edges. The fake edge may be
3199 the only successor for this block in the case of noreturn
3200 calls. */
3201 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3203 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3205 df_set_bb_dirty (bb);
3206 remove_edge (e);
3207 purged = true;
3209 else
3210 ei_next (&ei);
3213 gcc_assert (single_succ_p (bb));
3215 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3216 single_succ_edge (bb)->count = bb->count;
3218 if (dump_file)
3219 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3220 bb->index);
3221 return purged;
3224 /* Search all basic blocks for potentially dead edges and purge them. Return
3225 true if some edge has been eliminated. */
3227 bool
3228 purge_all_dead_edges (void)
3230 int purged = false;
3231 basic_block bb;
3233 FOR_EACH_BB_FN (bb, cfun)
3235 bool purged_here = purge_dead_edges (bb);
3237 purged |= purged_here;
3240 return purged;
3243 /* This is used by a few passes that emit some instructions after abnormal
3244 calls, moving the basic block's end, while they in fact do want to emit
3245 them on the fallthru edge. Look for abnormal call edges, find backward
3246 the call in the block and insert the instructions on the edge instead.
3248 Similarly, handle instructions throwing exceptions internally.
3250 Return true when instructions have been found and inserted on edges. */
3252 bool
3253 fixup_abnormal_edges (void)
3255 bool inserted = false;
3256 basic_block bb;
3258 FOR_EACH_BB_FN (bb, cfun)
3260 edge e;
3261 edge_iterator ei;
3263 /* Look for cases we are interested in - calls or instructions causing
3264 exceptions. */
3265 FOR_EACH_EDGE (e, ei, bb->succs)
3266 if ((e->flags & EDGE_ABNORMAL_CALL)
3267 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3268 == (EDGE_ABNORMAL | EDGE_EH)))
3269 break;
3271 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3273 rtx_insn *insn;
3275 /* Get past the new insns generated. Allow notes, as the insns
3276 may be already deleted. */
3277 insn = BB_END (bb);
3278 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3279 && !can_throw_internal (insn)
3280 && insn != BB_HEAD (bb))
3281 insn = PREV_INSN (insn);
3283 if (CALL_P (insn) || can_throw_internal (insn))
3285 rtx_insn *stop, *next;
3287 e = find_fallthru_edge (bb->succs);
3289 stop = NEXT_INSN (BB_END (bb));
3290 BB_END (bb) = insn;
3292 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3294 next = NEXT_INSN (insn);
3295 if (INSN_P (insn))
3297 delete_insn (insn);
3299 /* Sometimes there's still the return value USE.
3300 If it's placed after a trapping call (i.e. that
3301 call is the last insn anyway), we have no fallthru
3302 edge. Simply delete this use and don't try to insert
3303 on the non-existent edge. */
3304 if (GET_CODE (PATTERN (insn)) != USE)
3306 /* We're not deleting it, we're moving it. */
3307 insn->set_undeleted ();
3308 SET_PREV_INSN (insn) = NULL_RTX;
3309 SET_NEXT_INSN (insn) = NULL_RTX;
3311 insert_insn_on_edge (insn, e);
3312 inserted = true;
3315 else if (!BARRIER_P (insn))
3316 set_block_for_insn (insn, NULL);
3320 /* It may be that we don't find any trapping insn. In this
3321 case we discovered quite late that the insn that had been
3322 marked as can_throw_internal in fact couldn't trap at all.
3323 So we should in fact delete the EH edges out of the block. */
3324 else
3325 purge_dead_edges (bb);
3329 return inserted;
3332 /* Cut the insns from FIRST to LAST out of the insns stream. */
3334 rtx_insn *
3335 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3337 rtx_insn *prevfirst = PREV_INSN (first);
3338 rtx_insn *nextlast = NEXT_INSN (last);
3340 SET_PREV_INSN (first) = NULL;
3341 SET_NEXT_INSN (last) = NULL;
3342 if (prevfirst)
3343 SET_NEXT_INSN (prevfirst) = nextlast;
3344 if (nextlast)
3345 SET_PREV_INSN (nextlast) = prevfirst;
3346 else
3347 set_last_insn (prevfirst);
3348 if (!prevfirst)
3349 set_first_insn (nextlast);
3350 return first;
3353 /* Skip over inter-block insns occurring after BB which are typically
3354 associated with BB (e.g., barriers). If there are any such insns,
3355 we return the last one. Otherwise, we return the end of BB. */
3357 static rtx_insn *
3358 skip_insns_after_block (basic_block bb)
3360 rtx_insn *insn, *last_insn, *next_head, *prev;
3362 next_head = NULL;
3363 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3364 next_head = BB_HEAD (bb->next_bb);
3366 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3368 if (insn == next_head)
3369 break;
3371 switch (GET_CODE (insn))
3373 case BARRIER:
3374 last_insn = insn;
3375 continue;
3377 case NOTE:
3378 switch (NOTE_KIND (insn))
3380 case NOTE_INSN_BLOCK_END:
3381 gcc_unreachable ();
3382 continue;
3383 default:
3384 continue;
3385 break;
3387 break;
3389 case CODE_LABEL:
3390 if (NEXT_INSN (insn)
3391 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3393 insn = NEXT_INSN (insn);
3394 last_insn = insn;
3395 continue;
3397 break;
3399 default:
3400 break;
3403 break;
3406 /* It is possible to hit contradictory sequence. For instance:
3408 jump_insn
3409 NOTE_INSN_BLOCK_BEG
3410 barrier
3412 Where barrier belongs to jump_insn, but the note does not. This can be
3413 created by removing the basic block originally following
3414 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3416 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3418 prev = PREV_INSN (insn);
3419 if (NOTE_P (insn))
3420 switch (NOTE_KIND (insn))
3422 case NOTE_INSN_BLOCK_END:
3423 gcc_unreachable ();
3424 break;
3425 case NOTE_INSN_DELETED:
3426 case NOTE_INSN_DELETED_LABEL:
3427 case NOTE_INSN_DELETED_DEBUG_LABEL:
3428 continue;
3429 default:
3430 reorder_insns (insn, insn, last_insn);
3434 return last_insn;
3437 /* Locate or create a label for a given basic block. */
3439 static rtx_insn *
3440 label_for_bb (basic_block bb)
3442 rtx_insn *label = BB_HEAD (bb);
3444 if (!LABEL_P (label))
3446 if (dump_file)
3447 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3449 label = block_label (bb);
3452 return label;
3455 /* Locate the effective beginning and end of the insn chain for each
3456 block, as defined by skip_insns_after_block above. */
3458 static void
3459 record_effective_endpoints (void)
3461 rtx_insn *next_insn;
3462 basic_block bb;
3463 rtx_insn *insn;
3465 for (insn = get_insns ();
3466 insn
3467 && NOTE_P (insn)
3468 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3469 insn = NEXT_INSN (insn))
3470 continue;
3471 /* No basic blocks at all? */
3472 gcc_assert (insn);
3474 if (PREV_INSN (insn))
3475 cfg_layout_function_header =
3476 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3477 else
3478 cfg_layout_function_header = NULL;
3480 next_insn = get_insns ();
3481 FOR_EACH_BB_FN (bb, cfun)
3483 rtx_insn *end;
3485 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3486 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3487 PREV_INSN (BB_HEAD (bb)));
3488 end = skip_insns_after_block (bb);
3489 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3490 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3491 next_insn = NEXT_INSN (BB_END (bb));
3494 cfg_layout_function_footer = next_insn;
3495 if (cfg_layout_function_footer)
3496 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3499 namespace {
3501 const pass_data pass_data_into_cfg_layout_mode =
3503 RTL_PASS, /* type */
3504 "into_cfglayout", /* name */
3505 OPTGROUP_NONE, /* optinfo_flags */
3506 TV_CFG, /* tv_id */
3507 0, /* properties_required */
3508 PROP_cfglayout, /* properties_provided */
3509 0, /* properties_destroyed */
3510 0, /* todo_flags_start */
3511 0, /* todo_flags_finish */
3514 class pass_into_cfg_layout_mode : public rtl_opt_pass
3516 public:
3517 pass_into_cfg_layout_mode (gcc::context *ctxt)
3518 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3521 /* opt_pass methods: */
3522 virtual unsigned int execute (function *)
3524 cfg_layout_initialize (0);
3525 return 0;
3528 }; // class pass_into_cfg_layout_mode
3530 } // anon namespace
3532 rtl_opt_pass *
3533 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3535 return new pass_into_cfg_layout_mode (ctxt);
3538 namespace {
3540 const pass_data pass_data_outof_cfg_layout_mode =
3542 RTL_PASS, /* type */
3543 "outof_cfglayout", /* name */
3544 OPTGROUP_NONE, /* optinfo_flags */
3545 TV_CFG, /* tv_id */
3546 0, /* properties_required */
3547 0, /* properties_provided */
3548 PROP_cfglayout, /* properties_destroyed */
3549 0, /* todo_flags_start */
3550 0, /* todo_flags_finish */
3553 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3555 public:
3556 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3557 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3560 /* opt_pass methods: */
3561 virtual unsigned int execute (function *);
3563 }; // class pass_outof_cfg_layout_mode
3565 unsigned int
3566 pass_outof_cfg_layout_mode::execute (function *fun)
3568 basic_block bb;
3570 FOR_EACH_BB_FN (bb, fun)
3571 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3572 bb->aux = bb->next_bb;
3574 cfg_layout_finalize ();
3576 return 0;
3579 } // anon namespace
3581 rtl_opt_pass *
3582 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3584 return new pass_outof_cfg_layout_mode (ctxt);
3588 /* Link the basic blocks in the correct order, compacting the basic
3589 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3590 function also clears the basic block header and footer fields.
3592 This function is usually called after a pass (e.g. tracer) finishes
3593 some transformations while in cfglayout mode. The required sequence
3594 of the basic blocks is in a linked list along the bb->aux field.
3595 This functions re-links the basic block prev_bb and next_bb pointers
3596 accordingly, and it compacts and renumbers the blocks.
3598 FIXME: This currently works only for RTL, but the only RTL-specific
3599 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3600 to GIMPLE a long time ago, but it doesn't relink the basic block
3601 chain. It could do that (to give better initial RTL) if this function
3602 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3604 void
3605 relink_block_chain (bool stay_in_cfglayout_mode)
3607 basic_block bb, prev_bb;
3608 int index;
3610 /* Maybe dump the re-ordered sequence. */
3611 if (dump_file)
3613 fprintf (dump_file, "Reordered sequence:\n");
3614 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3615 NUM_FIXED_BLOCKS;
3617 bb = (basic_block) bb->aux, index++)
3619 fprintf (dump_file, " %i ", index);
3620 if (get_bb_original (bb))
3621 fprintf (dump_file, "duplicate of %i ",
3622 get_bb_original (bb)->index);
3623 else if (forwarder_block_p (bb)
3624 && !LABEL_P (BB_HEAD (bb)))
3625 fprintf (dump_file, "compensation ");
3626 else
3627 fprintf (dump_file, "bb %i ", bb->index);
3628 fprintf (dump_file, " [%i]\n", bb->frequency);
3632 /* Now reorder the blocks. */
3633 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3634 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3635 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3637 bb->prev_bb = prev_bb;
3638 prev_bb->next_bb = bb;
3640 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3641 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3643 /* Then, clean up the aux fields. */
3644 FOR_ALL_BB_FN (bb, cfun)
3646 bb->aux = NULL;
3647 if (!stay_in_cfglayout_mode)
3648 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3651 /* Maybe reset the original copy tables, they are not valid anymore
3652 when we renumber the basic blocks in compact_blocks. If we are
3653 are going out of cfglayout mode, don't re-allocate the tables. */
3654 if (original_copy_tables_initialized_p ())
3655 free_original_copy_tables ();
3656 if (stay_in_cfglayout_mode)
3657 initialize_original_copy_tables ();
3659 /* Finally, put basic_block_info in the new order. */
3660 compact_blocks ();
3664 /* Given a reorder chain, rearrange the code to match. */
3666 static void
3667 fixup_reorder_chain (void)
3669 basic_block bb;
3670 rtx_insn *insn = NULL;
3672 if (cfg_layout_function_header)
3674 set_first_insn (cfg_layout_function_header);
3675 insn = cfg_layout_function_header;
3676 while (NEXT_INSN (insn))
3677 insn = NEXT_INSN (insn);
3680 /* First do the bulk reordering -- rechain the blocks without regard to
3681 the needed changes to jumps and labels. */
3683 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3684 bb->aux)
3686 if (BB_HEADER (bb))
3688 if (insn)
3689 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3690 else
3691 set_first_insn (BB_HEADER (bb));
3692 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3693 insn = BB_HEADER (bb);
3694 while (NEXT_INSN (insn))
3695 insn = NEXT_INSN (insn);
3697 if (insn)
3698 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3699 else
3700 set_first_insn (BB_HEAD (bb));
3701 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3702 insn = BB_END (bb);
3703 if (BB_FOOTER (bb))
3705 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3706 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3707 while (NEXT_INSN (insn))
3708 insn = NEXT_INSN (insn);
3712 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3713 if (cfg_layout_function_footer)
3714 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3716 while (NEXT_INSN (insn))
3717 insn = NEXT_INSN (insn);
3719 set_last_insn (insn);
3720 if (flag_checking)
3721 verify_insn_chain ();
3723 /* Now add jumps and labels as needed to match the blocks new
3724 outgoing edges. */
3726 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3727 bb->aux)
3729 edge e_fall, e_taken, e;
3730 rtx_insn *bb_end_insn;
3731 rtx ret_label = NULL_RTX;
3732 basic_block nb;
3733 edge_iterator ei;
3735 if (EDGE_COUNT (bb->succs) == 0)
3736 continue;
3738 /* Find the old fallthru edge, and another non-EH edge for
3739 a taken jump. */
3740 e_taken = e_fall = NULL;
3742 FOR_EACH_EDGE (e, ei, bb->succs)
3743 if (e->flags & EDGE_FALLTHRU)
3744 e_fall = e;
3745 else if (! (e->flags & EDGE_EH))
3746 e_taken = e;
3748 bb_end_insn = BB_END (bb);
3749 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3751 ret_label = JUMP_LABEL (bb_end_jump);
3752 if (any_condjump_p (bb_end_jump))
3754 /* This might happen if the conditional jump has side
3755 effects and could therefore not be optimized away.
3756 Make the basic block to end with a barrier in order
3757 to prevent rtl_verify_flow_info from complaining. */
3758 if (!e_fall)
3760 gcc_assert (!onlyjump_p (bb_end_jump)
3761 || returnjump_p (bb_end_jump)
3762 || (e_taken->flags & EDGE_CROSSING));
3763 emit_barrier_after (bb_end_jump);
3764 continue;
3767 /* If the old fallthru is still next, nothing to do. */
3768 if (bb->aux == e_fall->dest
3769 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3770 continue;
3772 /* The degenerated case of conditional jump jumping to the next
3773 instruction can happen for jumps with side effects. We need
3774 to construct a forwarder block and this will be done just
3775 fine by force_nonfallthru below. */
3776 if (!e_taken)
3779 /* There is another special case: if *neither* block is next,
3780 such as happens at the very end of a function, then we'll
3781 need to add a new unconditional jump. Choose the taken
3782 edge based on known or assumed probability. */
3783 else if (bb->aux != e_taken->dest)
3785 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3787 if (note
3788 && XINT (note, 0) < REG_BR_PROB_BASE / 2
3789 && invert_jump (bb_end_jump,
3790 (e_fall->dest
3791 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3792 ? NULL_RTX
3793 : label_for_bb (e_fall->dest)), 0))
3795 e_fall->flags &= ~EDGE_FALLTHRU;
3796 gcc_checking_assert (could_fall_through
3797 (e_taken->src, e_taken->dest));
3798 e_taken->flags |= EDGE_FALLTHRU;
3799 update_br_prob_note (bb);
3800 e = e_fall, e_fall = e_taken, e_taken = e;
3804 /* If the "jumping" edge is a crossing edge, and the fall
3805 through edge is non-crossing, leave things as they are. */
3806 else if ((e_taken->flags & EDGE_CROSSING)
3807 && !(e_fall->flags & EDGE_CROSSING))
3808 continue;
3810 /* Otherwise we can try to invert the jump. This will
3811 basically never fail, however, keep up the pretense. */
3812 else if (invert_jump (bb_end_jump,
3813 (e_fall->dest
3814 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3815 ? NULL_RTX
3816 : label_for_bb (e_fall->dest)), 0))
3818 e_fall->flags &= ~EDGE_FALLTHRU;
3819 gcc_checking_assert (could_fall_through
3820 (e_taken->src, e_taken->dest));
3821 e_taken->flags |= EDGE_FALLTHRU;
3822 update_br_prob_note (bb);
3823 if (LABEL_NUSES (ret_label) == 0
3824 && single_pred_p (e_taken->dest))
3825 delete_insn (as_a<rtx_insn *> (ret_label));
3826 continue;
3829 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3831 /* If the old fallthru is still next or if
3832 asm goto doesn't have a fallthru (e.g. when followed by
3833 __builtin_unreachable ()), nothing to do. */
3834 if (! e_fall
3835 || bb->aux == e_fall->dest
3836 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3837 continue;
3839 /* Otherwise we'll have to use the fallthru fixup below. */
3841 else
3843 /* Otherwise we have some return, switch or computed
3844 jump. In the 99% case, there should not have been a
3845 fallthru edge. */
3846 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3847 continue;
3850 else
3852 /* No fallthru implies a noreturn function with EH edges, or
3853 something similarly bizarre. In any case, we don't need to
3854 do anything. */
3855 if (! e_fall)
3856 continue;
3858 /* If the fallthru block is still next, nothing to do. */
3859 if (bb->aux == e_fall->dest)
3860 continue;
3862 /* A fallthru to exit block. */
3863 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3864 continue;
3867 /* We got here if we need to add a new jump insn.
3868 Note force_nonfallthru can delete E_FALL and thus we have to
3869 save E_FALL->src prior to the call to force_nonfallthru. */
3870 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3871 if (nb)
3873 nb->aux = bb->aux;
3874 bb->aux = nb;
3875 /* Don't process this new block. */
3876 bb = nb;
3880 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3882 /* Annoying special case - jump around dead jumptables left in the code. */
3883 FOR_EACH_BB_FN (bb, cfun)
3885 edge e = find_fallthru_edge (bb->succs);
3887 if (e && !can_fallthru (e->src, e->dest))
3888 force_nonfallthru (e);
3891 /* Ensure goto_locus from edges has some instructions with that locus
3892 in RTL. */
3893 if (!optimize)
3894 FOR_EACH_BB_FN (bb, cfun)
3896 edge e;
3897 edge_iterator ei;
3899 FOR_EACH_EDGE (e, ei, bb->succs)
3900 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3901 && !(e->flags & EDGE_ABNORMAL))
3903 edge e2;
3904 edge_iterator ei2;
3905 basic_block dest, nb;
3906 rtx_insn *end;
3908 insn = BB_END (e->src);
3909 end = PREV_INSN (BB_HEAD (e->src));
3910 while (insn != end
3911 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3912 insn = PREV_INSN (insn);
3913 if (insn != end
3914 && INSN_LOCATION (insn) == e->goto_locus)
3915 continue;
3916 if (simplejump_p (BB_END (e->src))
3917 && !INSN_HAS_LOCATION (BB_END (e->src)))
3919 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3920 continue;
3922 dest = e->dest;
3923 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3925 /* Non-fallthru edges to the exit block cannot be split. */
3926 if (!(e->flags & EDGE_FALLTHRU))
3927 continue;
3929 else
3931 insn = BB_HEAD (dest);
3932 end = NEXT_INSN (BB_END (dest));
3933 while (insn != end && !NONDEBUG_INSN_P (insn))
3934 insn = NEXT_INSN (insn);
3935 if (insn != end && INSN_HAS_LOCATION (insn)
3936 && INSN_LOCATION (insn) == e->goto_locus)
3937 continue;
3939 nb = split_edge (e);
3940 if (!INSN_P (BB_END (nb)))
3941 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3942 nb);
3943 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3945 /* If there are other incoming edges to the destination block
3946 with the same goto locus, redirect them to the new block as
3947 well, this can prevent other such blocks from being created
3948 in subsequent iterations of the loop. */
3949 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3950 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3951 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3952 && e->goto_locus == e2->goto_locus)
3953 redirect_edge_and_branch (e2, nb);
3954 else
3955 ei_next (&ei2);
3960 /* Perform sanity checks on the insn chain.
3961 1. Check that next/prev pointers are consistent in both the forward and
3962 reverse direction.
3963 2. Count insns in chain, going both directions, and check if equal.
3964 3. Check that get_last_insn () returns the actual end of chain. */
3966 DEBUG_FUNCTION void
3967 verify_insn_chain (void)
3969 rtx_insn *x, *prevx, *nextx;
3970 int insn_cnt1, insn_cnt2;
3972 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3973 x != 0;
3974 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3975 gcc_assert (PREV_INSN (x) == prevx);
3977 gcc_assert (prevx == get_last_insn ());
3979 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3980 x != 0;
3981 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3982 gcc_assert (NEXT_INSN (x) == nextx);
3984 gcc_assert (insn_cnt1 == insn_cnt2);
3987 /* If we have assembler epilogues, the block falling through to exit must
3988 be the last one in the reordered chain when we reach final. Ensure
3989 that this condition is met. */
3990 static void
3991 fixup_fallthru_exit_predecessor (void)
3993 edge e;
3994 basic_block bb = NULL;
3996 /* This transformation is not valid before reload, because we might
3997 separate a call from the instruction that copies the return
3998 value. */
3999 gcc_assert (reload_completed);
4001 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4002 if (e)
4003 bb = e->src;
4005 if (bb && bb->aux)
4007 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4009 /* If the very first block is the one with the fall-through exit
4010 edge, we have to split that block. */
4011 if (c == bb)
4013 bb = split_block_after_labels (bb)->dest;
4014 bb->aux = c->aux;
4015 c->aux = bb;
4016 BB_FOOTER (bb) = BB_FOOTER (c);
4017 BB_FOOTER (c) = NULL;
4020 while (c->aux != bb)
4021 c = (basic_block) c->aux;
4023 c->aux = bb->aux;
4024 while (c->aux)
4025 c = (basic_block) c->aux;
4027 c->aux = bb;
4028 bb->aux = NULL;
4032 /* In case there are more than one fallthru predecessors of exit, force that
4033 there is only one. */
4035 static void
4036 force_one_exit_fallthru (void)
4038 edge e, predecessor = NULL;
4039 bool more = false;
4040 edge_iterator ei;
4041 basic_block forwarder, bb;
4043 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4044 if (e->flags & EDGE_FALLTHRU)
4046 if (predecessor == NULL)
4047 predecessor = e;
4048 else
4050 more = true;
4051 break;
4055 if (!more)
4056 return;
4058 /* Exit has several fallthru predecessors. Create a forwarder block for
4059 them. */
4060 forwarder = split_edge (predecessor);
4061 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4062 (e = ei_safe_edge (ei)); )
4064 if (e->src == forwarder
4065 || !(e->flags & EDGE_FALLTHRU))
4066 ei_next (&ei);
4067 else
4068 redirect_edge_and_branch_force (e, forwarder);
4071 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4072 exit block. */
4073 FOR_EACH_BB_FN (bb, cfun)
4075 if (bb->aux == NULL && bb != forwarder)
4077 bb->aux = forwarder;
4078 break;
4083 /* Return true in case it is possible to duplicate the basic block BB. */
4085 static bool
4086 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4088 /* Do not attempt to duplicate tablejumps, as we need to unshare
4089 the dispatch table. This is difficult to do, as the instructions
4090 computing jump destination may be hoisted outside the basic block. */
4091 if (tablejump_p (BB_END (bb), NULL, NULL))
4092 return false;
4094 /* Do not duplicate blocks containing insns that can't be copied. */
4095 if (targetm.cannot_copy_insn_p)
4097 rtx_insn *insn = BB_HEAD (bb);
4098 while (1)
4100 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4101 return false;
4102 if (insn == BB_END (bb))
4103 break;
4104 insn = NEXT_INSN (insn);
4108 return true;
4111 rtx_insn *
4112 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4114 rtx_insn *insn, *next, *copy;
4115 rtx_note *last;
4117 /* Avoid updating of boundaries of previous basic block. The
4118 note will get removed from insn stream in fixup. */
4119 last = emit_note (NOTE_INSN_DELETED);
4121 /* Create copy at the end of INSN chain. The chain will
4122 be reordered later. */
4123 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4125 switch (GET_CODE (insn))
4127 case DEBUG_INSN:
4128 /* Don't duplicate label debug insns. */
4129 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4130 break;
4131 /* FALLTHRU */
4132 case INSN:
4133 case CALL_INSN:
4134 case JUMP_INSN:
4135 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4136 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4137 && ANY_RETURN_P (JUMP_LABEL (insn)))
4138 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4139 maybe_copy_prologue_epilogue_insn (insn, copy);
4140 break;
4142 case JUMP_TABLE_DATA:
4143 /* Avoid copying of dispatch tables. We never duplicate
4144 tablejumps, so this can hit only in case the table got
4145 moved far from original jump.
4146 Avoid copying following barrier as well if any
4147 (and debug insns in between). */
4148 for (next = NEXT_INSN (insn);
4149 next != NEXT_INSN (to);
4150 next = NEXT_INSN (next))
4151 if (!DEBUG_INSN_P (next))
4152 break;
4153 if (next != NEXT_INSN (to) && BARRIER_P (next))
4154 insn = next;
4155 break;
4157 case CODE_LABEL:
4158 break;
4160 case BARRIER:
4161 emit_barrier ();
4162 break;
4164 case NOTE:
4165 switch (NOTE_KIND (insn))
4167 /* In case prologue is empty and function contain label
4168 in first BB, we may want to copy the block. */
4169 case NOTE_INSN_PROLOGUE_END:
4171 case NOTE_INSN_DELETED:
4172 case NOTE_INSN_DELETED_LABEL:
4173 case NOTE_INSN_DELETED_DEBUG_LABEL:
4174 /* No problem to strip these. */
4175 case NOTE_INSN_FUNCTION_BEG:
4176 /* There is always just single entry to function. */
4177 case NOTE_INSN_BASIC_BLOCK:
4178 /* We should only switch text sections once. */
4179 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4180 break;
4182 case NOTE_INSN_EPILOGUE_BEG:
4183 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4184 emit_note_copy (as_a <rtx_note *> (insn));
4185 break;
4187 default:
4188 /* All other notes should have already been eliminated. */
4189 gcc_unreachable ();
4191 break;
4192 default:
4193 gcc_unreachable ();
4196 insn = NEXT_INSN (last);
4197 delete_insn (last);
4198 return insn;
4201 /* Create a duplicate of the basic block BB. */
4203 static basic_block
4204 cfg_layout_duplicate_bb (basic_block bb)
4206 rtx_insn *insn;
4207 basic_block new_bb;
4209 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4210 new_bb = create_basic_block (insn,
4211 insn ? get_last_insn () : NULL,
4212 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4214 BB_COPY_PARTITION (new_bb, bb);
4215 if (BB_HEADER (bb))
4217 insn = BB_HEADER (bb);
4218 while (NEXT_INSN (insn))
4219 insn = NEXT_INSN (insn);
4220 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4221 if (insn)
4222 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4225 if (BB_FOOTER (bb))
4227 insn = BB_FOOTER (bb);
4228 while (NEXT_INSN (insn))
4229 insn = NEXT_INSN (insn);
4230 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4231 if (insn)
4232 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4235 return new_bb;
4239 /* Main entry point to this module - initialize the datastructures for
4240 CFG layout changes. It keeps LOOPS up-to-date if not null.
4242 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4244 void
4245 cfg_layout_initialize (unsigned int flags)
4247 rtx_insn_list *x;
4248 basic_block bb;
4250 /* Once bb partitioning is complete, cfg layout mode should not be
4251 re-entered. Entering cfg layout mode may require fixups. As an
4252 example, if edge forwarding performed when optimizing the cfg
4253 layout required moving a block from the hot to the cold
4254 section. This would create an illegal partitioning unless some
4255 manual fixup was performed. */
4256 gcc_assert (!(crtl->bb_reorder_complete
4257 && flag_reorder_blocks_and_partition));
4259 initialize_original_copy_tables ();
4261 cfg_layout_rtl_register_cfg_hooks ();
4263 record_effective_endpoints ();
4265 /* Make sure that the targets of non local gotos are marked. */
4266 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4268 bb = BLOCK_FOR_INSN (x->insn ());
4269 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4272 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4275 /* Splits superblocks. */
4276 void
4277 break_superblocks (void)
4279 bool need = false;
4280 basic_block bb;
4282 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4283 bitmap_clear (superblocks);
4285 FOR_EACH_BB_FN (bb, cfun)
4286 if (bb->flags & BB_SUPERBLOCK)
4288 bb->flags &= ~BB_SUPERBLOCK;
4289 bitmap_set_bit (superblocks, bb->index);
4290 need = true;
4293 if (need)
4295 rebuild_jump_labels (get_insns ());
4296 find_many_sub_basic_blocks (superblocks);
4300 /* Finalize the changes: reorder insn list according to the sequence specified
4301 by aux pointers, enter compensation code, rebuild scope forest. */
4303 void
4304 cfg_layout_finalize (void)
4306 checking_verify_flow_info ();
4307 free_dominance_info (CDI_DOMINATORS);
4308 force_one_exit_fallthru ();
4309 rtl_register_cfg_hooks ();
4310 if (reload_completed && !targetm.have_epilogue ())
4311 fixup_fallthru_exit_predecessor ();
4312 fixup_reorder_chain ();
4314 rebuild_jump_labels (get_insns ());
4315 delete_dead_jumptables ();
4317 if (flag_checking)
4318 verify_insn_chain ();
4319 checking_verify_flow_info ();
4323 /* Same as split_block but update cfg_layout structures. */
4325 static basic_block
4326 cfg_layout_split_block (basic_block bb, void *insnp)
4328 rtx insn = (rtx) insnp;
4329 basic_block new_bb = rtl_split_block (bb, insn);
4331 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4332 BB_FOOTER (bb) = NULL;
4334 return new_bb;
4337 /* Redirect Edge to DEST. */
4338 static edge
4339 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4341 basic_block src = e->src;
4342 edge ret;
4344 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4345 return NULL;
4347 if (e->dest == dest)
4348 return e;
4350 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4351 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4353 df_set_bb_dirty (src);
4354 return ret;
4357 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4358 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4360 if (dump_file)
4361 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4362 e->src->index, dest->index);
4364 df_set_bb_dirty (e->src);
4365 redirect_edge_succ (e, dest);
4366 return e;
4369 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4370 in the case the basic block appears to be in sequence. Avoid this
4371 transformation. */
4373 if (e->flags & EDGE_FALLTHRU)
4375 /* Redirect any branch edges unified with the fallthru one. */
4376 if (JUMP_P (BB_END (src))
4377 && label_is_jump_target_p (BB_HEAD (e->dest),
4378 BB_END (src)))
4380 edge redirected;
4382 if (dump_file)
4383 fprintf (dump_file, "Fallthru edge unified with branch "
4384 "%i->%i redirected to %i\n",
4385 e->src->index, e->dest->index, dest->index);
4386 e->flags &= ~EDGE_FALLTHRU;
4387 redirected = redirect_branch_edge (e, dest);
4388 gcc_assert (redirected);
4389 redirected->flags |= EDGE_FALLTHRU;
4390 df_set_bb_dirty (redirected->src);
4391 return redirected;
4393 /* In case we are redirecting fallthru edge to the branch edge
4394 of conditional jump, remove it. */
4395 if (EDGE_COUNT (src->succs) == 2)
4397 /* Find the edge that is different from E. */
4398 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4400 if (s->dest == dest
4401 && any_condjump_p (BB_END (src))
4402 && onlyjump_p (BB_END (src)))
4403 delete_insn (BB_END (src));
4405 if (dump_file)
4406 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4407 e->src->index, e->dest->index, dest->index);
4408 ret = redirect_edge_succ_nodup (e, dest);
4410 else
4411 ret = redirect_branch_edge (e, dest);
4413 /* We don't want simplejumps in the insn stream during cfglayout. */
4414 gcc_assert (!simplejump_p (BB_END (src)));
4416 df_set_bb_dirty (src);
4417 return ret;
4420 /* Simple wrapper as we always can redirect fallthru edges. */
4421 static basic_block
4422 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4424 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4426 gcc_assert (redirected);
4427 return NULL;
4430 /* Same as delete_basic_block but update cfg_layout structures. */
4432 static void
4433 cfg_layout_delete_block (basic_block bb)
4435 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4436 rtx_insn **to;
4438 if (BB_HEADER (bb))
4440 next = BB_HEAD (bb);
4441 if (prev)
4442 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4443 else
4444 set_first_insn (BB_HEADER (bb));
4445 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4446 insn = BB_HEADER (bb);
4447 while (NEXT_INSN (insn))
4448 insn = NEXT_INSN (insn);
4449 SET_NEXT_INSN (insn) = next;
4450 SET_PREV_INSN (next) = insn;
4452 next = NEXT_INSN (BB_END (bb));
4453 if (BB_FOOTER (bb))
4455 insn = BB_FOOTER (bb);
4456 while (insn)
4458 if (BARRIER_P (insn))
4460 if (PREV_INSN (insn))
4461 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4462 else
4463 BB_FOOTER (bb) = NEXT_INSN (insn);
4464 if (NEXT_INSN (insn))
4465 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4467 if (LABEL_P (insn))
4468 break;
4469 insn = NEXT_INSN (insn);
4471 if (BB_FOOTER (bb))
4473 insn = BB_END (bb);
4474 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4475 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4476 while (NEXT_INSN (insn))
4477 insn = NEXT_INSN (insn);
4478 SET_NEXT_INSN (insn) = next;
4479 if (next)
4480 SET_PREV_INSN (next) = insn;
4481 else
4482 set_last_insn (insn);
4485 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4486 to = &BB_HEADER (bb->next_bb);
4487 else
4488 to = &cfg_layout_function_footer;
4490 rtl_delete_block (bb);
4492 if (prev)
4493 prev = NEXT_INSN (prev);
4494 else
4495 prev = get_insns ();
4496 if (next)
4497 next = PREV_INSN (next);
4498 else
4499 next = get_last_insn ();
4501 if (next && NEXT_INSN (next) != prev)
4503 remaints = unlink_insn_chain (prev, next);
4504 insn = remaints;
4505 while (NEXT_INSN (insn))
4506 insn = NEXT_INSN (insn);
4507 SET_NEXT_INSN (insn) = *to;
4508 if (*to)
4509 SET_PREV_INSN (*to) = insn;
4510 *to = remaints;
4514 /* Return true when blocks A and B can be safely merged. */
4516 static bool
4517 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4519 /* If we are partitioning hot/cold basic blocks, we don't want to
4520 mess up unconditional or indirect jumps that cross between hot
4521 and cold sections.
4523 Basic block partitioning may result in some jumps that appear to
4524 be optimizable (or blocks that appear to be mergeable), but which really
4525 must be left untouched (they are required to make it safely across
4526 partition boundaries). See the comments at the top of
4527 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4529 if (BB_PARTITION (a) != BB_PARTITION (b))
4530 return false;
4532 /* Protect the loop latches. */
4533 if (current_loops && b->loop_father->latch == b)
4534 return false;
4536 /* If we would end up moving B's instructions, make sure it doesn't fall
4537 through into the exit block, since we cannot recover from a fallthrough
4538 edge into the exit block occurring in the middle of a function. */
4539 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4541 edge e = find_fallthru_edge (b->succs);
4542 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4543 return false;
4546 /* There must be exactly one edge in between the blocks. */
4547 return (single_succ_p (a)
4548 && single_succ (a) == b
4549 && single_pred_p (b) == 1
4550 && a != b
4551 /* Must be simple edge. */
4552 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4553 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4554 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4555 /* If the jump insn has side effects, we can't kill the edge.
4556 When not optimizing, try_redirect_by_replacing_jump will
4557 not allow us to redirect an edge by replacing a table jump. */
4558 && (!JUMP_P (BB_END (a))
4559 || ((!optimize || reload_completed)
4560 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4563 /* Merge block A and B. The blocks must be mergeable. */
4565 static void
4566 cfg_layout_merge_blocks (basic_block a, basic_block b)
4568 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4569 rtx_insn *insn;
4571 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4573 if (dump_file)
4574 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4575 a->index);
4577 /* If there was a CODE_LABEL beginning B, delete it. */
4578 if (LABEL_P (BB_HEAD (b)))
4580 delete_insn (BB_HEAD (b));
4583 /* We should have fallthru edge in a, or we can do dummy redirection to get
4584 it cleaned up. */
4585 if (JUMP_P (BB_END (a)))
4586 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4587 gcc_assert (!JUMP_P (BB_END (a)));
4589 /* When not optimizing and the edge is the only place in RTL which holds
4590 some unique locus, emit a nop with that locus in between. */
4591 if (!optimize)
4592 emit_nop_for_unique_locus_between (a, b);
4594 /* Move things from b->footer after a->footer. */
4595 if (BB_FOOTER (b))
4597 if (!BB_FOOTER (a))
4598 BB_FOOTER (a) = BB_FOOTER (b);
4599 else
4601 rtx_insn *last = BB_FOOTER (a);
4603 while (NEXT_INSN (last))
4604 last = NEXT_INSN (last);
4605 SET_NEXT_INSN (last) = BB_FOOTER (b);
4606 SET_PREV_INSN (BB_FOOTER (b)) = last;
4608 BB_FOOTER (b) = NULL;
4611 /* Move things from b->header before a->footer.
4612 Note that this may include dead tablejump data, but we don't clean
4613 those up until we go out of cfglayout mode. */
4614 if (BB_HEADER (b))
4616 if (! BB_FOOTER (a))
4617 BB_FOOTER (a) = BB_HEADER (b);
4618 else
4620 rtx_insn *last = BB_HEADER (b);
4622 while (NEXT_INSN (last))
4623 last = NEXT_INSN (last);
4624 SET_NEXT_INSN (last) = BB_FOOTER (a);
4625 SET_PREV_INSN (BB_FOOTER (a)) = last;
4626 BB_FOOTER (a) = BB_HEADER (b);
4628 BB_HEADER (b) = NULL;
4631 /* In the case basic blocks are not adjacent, move them around. */
4632 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4634 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4636 emit_insn_after_noloc (insn, BB_END (a), a);
4638 /* Otherwise just re-associate the instructions. */
4639 else
4641 insn = BB_HEAD (b);
4642 BB_END (a) = BB_END (b);
4645 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4646 We need to explicitly call. */
4647 update_bb_for_insn_chain (insn, BB_END (b), a);
4649 /* Skip possible DELETED_LABEL insn. */
4650 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4651 insn = NEXT_INSN (insn);
4652 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4653 BB_HEAD (b) = BB_END (b) = NULL;
4654 delete_insn (insn);
4656 df_bb_delete (b->index);
4658 /* If B was a forwarder block, propagate the locus on the edge. */
4659 if (forwarder_p
4660 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4661 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4663 if (dump_file)
4664 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4667 /* Split edge E. */
4669 static basic_block
4670 cfg_layout_split_edge (edge e)
4672 basic_block new_bb =
4673 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4674 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4675 NULL_RTX, e->src);
4677 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4678 BB_COPY_PARTITION (new_bb, e->src);
4679 else
4680 BB_COPY_PARTITION (new_bb, e->dest);
4681 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4682 redirect_edge_and_branch_force (e, new_bb);
4684 return new_bb;
4687 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4689 static void
4690 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4694 /* Return true if BB contains only labels or non-executable
4695 instructions. */
4697 static bool
4698 rtl_block_empty_p (basic_block bb)
4700 rtx_insn *insn;
4702 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4703 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4704 return true;
4706 FOR_BB_INSNS (bb, insn)
4707 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4708 return false;
4710 return true;
4713 /* Split a basic block if it ends with a conditional branch and if
4714 the other part of the block is not empty. */
4716 static basic_block
4717 rtl_split_block_before_cond_jump (basic_block bb)
4719 rtx_insn *insn;
4720 rtx_insn *split_point = NULL;
4721 rtx_insn *last = NULL;
4722 bool found_code = false;
4724 FOR_BB_INSNS (bb, insn)
4726 if (any_condjump_p (insn))
4727 split_point = last;
4728 else if (NONDEBUG_INSN_P (insn))
4729 found_code = true;
4730 last = insn;
4733 /* Did not find everything. */
4734 if (found_code && split_point)
4735 return split_block (bb, split_point)->dest;
4736 else
4737 return NULL;
4740 /* Return 1 if BB ends with a call, possibly followed by some
4741 instructions that must stay with the call, 0 otherwise. */
4743 static bool
4744 rtl_block_ends_with_call_p (basic_block bb)
4746 rtx_insn *insn = BB_END (bb);
4748 while (!CALL_P (insn)
4749 && insn != BB_HEAD (bb)
4750 && (keep_with_call_p (insn)
4751 || NOTE_P (insn)
4752 || DEBUG_INSN_P (insn)))
4753 insn = PREV_INSN (insn);
4754 return (CALL_P (insn));
4757 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4759 static bool
4760 rtl_block_ends_with_condjump_p (const_basic_block bb)
4762 return any_condjump_p (BB_END (bb));
4765 /* Return true if we need to add fake edge to exit.
4766 Helper function for rtl_flow_call_edges_add. */
4768 static bool
4769 need_fake_edge_p (const rtx_insn *insn)
4771 if (!INSN_P (insn))
4772 return false;
4774 if ((CALL_P (insn)
4775 && !SIBLING_CALL_P (insn)
4776 && !find_reg_note (insn, REG_NORETURN, NULL)
4777 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4778 return true;
4780 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4781 && MEM_VOLATILE_P (PATTERN (insn)))
4782 || (GET_CODE (PATTERN (insn)) == PARALLEL
4783 && asm_noperands (insn) != -1
4784 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4785 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4788 /* Add fake edges to the function exit for any non constant and non noreturn
4789 calls, volatile inline assembly in the bitmap of blocks specified by
4790 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4791 that were split.
4793 The goal is to expose cases in which entering a basic block does not imply
4794 that all subsequent instructions must be executed. */
4796 static int
4797 rtl_flow_call_edges_add (sbitmap blocks)
4799 int i;
4800 int blocks_split = 0;
4801 int last_bb = last_basic_block_for_fn (cfun);
4802 bool check_last_block = false;
4804 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4805 return 0;
4807 if (! blocks)
4808 check_last_block = true;
4809 else
4810 check_last_block = bitmap_bit_p (blocks,
4811 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4813 /* In the last basic block, before epilogue generation, there will be
4814 a fallthru edge to EXIT. Special care is required if the last insn
4815 of the last basic block is a call because make_edge folds duplicate
4816 edges, which would result in the fallthru edge also being marked
4817 fake, which would result in the fallthru edge being removed by
4818 remove_fake_edges, which would result in an invalid CFG.
4820 Moreover, we can't elide the outgoing fake edge, since the block
4821 profiler needs to take this into account in order to solve the minimal
4822 spanning tree in the case that the call doesn't return.
4824 Handle this by adding a dummy instruction in a new last basic block. */
4825 if (check_last_block)
4827 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4828 rtx_insn *insn = BB_END (bb);
4830 /* Back up past insns that must be kept in the same block as a call. */
4831 while (insn != BB_HEAD (bb)
4832 && keep_with_call_p (insn))
4833 insn = PREV_INSN (insn);
4835 if (need_fake_edge_p (insn))
4837 edge e;
4839 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4840 if (e)
4842 insert_insn_on_edge (gen_use (const0_rtx), e);
4843 commit_edge_insertions ();
4848 /* Now add fake edges to the function exit for any non constant
4849 calls since there is no way that we can determine if they will
4850 return or not... */
4852 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4854 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4855 rtx_insn *insn;
4856 rtx_insn *prev_insn;
4858 if (!bb)
4859 continue;
4861 if (blocks && !bitmap_bit_p (blocks, i))
4862 continue;
4864 for (insn = BB_END (bb); ; insn = prev_insn)
4866 prev_insn = PREV_INSN (insn);
4867 if (need_fake_edge_p (insn))
4869 edge e;
4870 rtx_insn *split_at_insn = insn;
4872 /* Don't split the block between a call and an insn that should
4873 remain in the same block as the call. */
4874 if (CALL_P (insn))
4875 while (split_at_insn != BB_END (bb)
4876 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4877 split_at_insn = NEXT_INSN (split_at_insn);
4879 /* The handling above of the final block before the epilogue
4880 should be enough to verify that there is no edge to the exit
4881 block in CFG already. Calling make_edge in such case would
4882 cause us to mark that edge as fake and remove it later. */
4884 if (flag_checking && split_at_insn == BB_END (bb))
4886 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4887 gcc_assert (e == NULL);
4890 /* Note that the following may create a new basic block
4891 and renumber the existing basic blocks. */
4892 if (split_at_insn != BB_END (bb))
4894 e = split_block (bb, split_at_insn);
4895 if (e)
4896 blocks_split++;
4899 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4902 if (insn == BB_HEAD (bb))
4903 break;
4907 if (blocks_split)
4908 verify_flow_info ();
4910 return blocks_split;
4913 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4914 the conditional branch target, SECOND_HEAD should be the fall-thru
4915 there is no need to handle this here the loop versioning code handles
4916 this. the reason for SECON_HEAD is that it is needed for condition
4917 in trees, and this should be of the same type since it is a hook. */
4918 static void
4919 rtl_lv_add_condition_to_bb (basic_block first_head ,
4920 basic_block second_head ATTRIBUTE_UNUSED,
4921 basic_block cond_bb, void *comp_rtx)
4923 rtx_code_label *label;
4924 rtx_insn *seq, *jump;
4925 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4926 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4927 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4928 machine_mode mode;
4931 label = block_label (first_head);
4932 mode = GET_MODE (op0);
4933 if (mode == VOIDmode)
4934 mode = GET_MODE (op1);
4936 start_sequence ();
4937 op0 = force_operand (op0, NULL_RTX);
4938 op1 = force_operand (op1, NULL_RTX);
4939 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label, -1);
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]
5032 += insn_rtx_cost (PATTERN (insn), false);
5033 if (profile_status_for_fn (cfun) == PROFILE_READ)
5034 record->time[after_pass]
5035 += insn_rtx_cost (PATTERN (insn), true) * bb->count;
5036 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5037 record->time[after_pass]
5038 += insn_rtx_cost (PATTERN (insn), true) * bb->frequency;
5042 /* Implementation of CFG manipulation for linearized RTL. */
5043 struct cfg_hooks rtl_cfg_hooks = {
5044 "rtl",
5045 rtl_verify_flow_info,
5046 rtl_dump_bb,
5047 rtl_dump_bb_for_graph,
5048 rtl_create_basic_block,
5049 rtl_redirect_edge_and_branch,
5050 rtl_redirect_edge_and_branch_force,
5051 rtl_can_remove_branch_p,
5052 rtl_delete_block,
5053 rtl_split_block,
5054 rtl_move_block_after,
5055 rtl_can_merge_blocks, /* can_merge_blocks_p */
5056 rtl_merge_blocks,
5057 rtl_predict_edge,
5058 rtl_predicted_by_p,
5059 cfg_layout_can_duplicate_bb_p,
5060 rtl_duplicate_bb,
5061 rtl_split_edge,
5062 rtl_make_forwarder_block,
5063 rtl_tidy_fallthru_edge,
5064 rtl_force_nonfallthru,
5065 rtl_block_ends_with_call_p,
5066 rtl_block_ends_with_condjump_p,
5067 rtl_flow_call_edges_add,
5068 NULL, /* execute_on_growing_pred */
5069 NULL, /* execute_on_shrinking_pred */
5070 NULL, /* duplicate loop for trees */
5071 NULL, /* lv_add_condition_to_bb */
5072 NULL, /* lv_adjust_loop_header_phi*/
5073 NULL, /* extract_cond_bb_edges */
5074 NULL, /* flush_pending_stmts */
5075 rtl_block_empty_p, /* block_empty_p */
5076 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5077 rtl_account_profile_record,
5080 /* Implementation of CFG manipulation for cfg layout RTL, where
5081 basic block connected via fallthru edges does not have to be adjacent.
5082 This representation will hopefully become the default one in future
5083 version of the compiler. */
5085 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5086 "cfglayout mode",
5087 rtl_verify_flow_info_1,
5088 rtl_dump_bb,
5089 rtl_dump_bb_for_graph,
5090 cfg_layout_create_basic_block,
5091 cfg_layout_redirect_edge_and_branch,
5092 cfg_layout_redirect_edge_and_branch_force,
5093 rtl_can_remove_branch_p,
5094 cfg_layout_delete_block,
5095 cfg_layout_split_block,
5096 rtl_move_block_after,
5097 cfg_layout_can_merge_blocks_p,
5098 cfg_layout_merge_blocks,
5099 rtl_predict_edge,
5100 rtl_predicted_by_p,
5101 cfg_layout_can_duplicate_bb_p,
5102 cfg_layout_duplicate_bb,
5103 cfg_layout_split_edge,
5104 rtl_make_forwarder_block,
5105 NULL, /* tidy_fallthru_edge */
5106 rtl_force_nonfallthru,
5107 rtl_block_ends_with_call_p,
5108 rtl_block_ends_with_condjump_p,
5109 rtl_flow_call_edges_add,
5110 NULL, /* execute_on_growing_pred */
5111 NULL, /* execute_on_shrinking_pred */
5112 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5113 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5114 NULL, /* lv_adjust_loop_header_phi*/
5115 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5116 NULL, /* flush_pending_stmts */
5117 rtl_block_empty_p, /* block_empty_p */
5118 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5119 rtl_account_profile_record,
5122 #include "gt-cfgrtl.h"